Grain-v1 快速相关攻击的改进*

张英杰, 胡 磊, 史丹萍, 王 鹏, 孙思维, 魏 荣,4

1. 中国科学院 信息工程研究所 信息安全国家重点实验室, 北京100093

2. 中国科学院 数据与通信保护研究教育中心, 北京100093

3. 中国科学院大学 网络空间安全学院, 北京100093

4. 北京卫星信息工程研究所, 北京100086

1 引言

流密码算法是对称密码算法的重要分支, 包括同步流密码算法和自同步流密码算法. 其中, 同步流密码算法是指将密钥流与明文直接异或得到密文的流密码算法, 其密钥流仅与密钥(Key) 和初始向量(IV)有关. 许多同步流密码算法分为两个阶段: 初始化阶段和密钥流生成阶段. 初始化阶段的目的是将Key 和IV 充分混淆, 此阶段不输出密钥流. 密钥流生成阶段将初始化阶段结束后的状态作为初始状态, 通过不断地更新中间状态生成密钥流.

LFSR 结构经常用于构造同步流密码算法, 其状态更新函数通常由一个或多个LFSR 和一个非线性函数构成. 基于Grain 结构的流密码算法是一组典型的基于LFSR 结构的同步流密码算法, 包括Grain-128a[1], Grain-v1[2], Grain-128[3]以及一些轻量级的流密码算法等[4-6]. 其中, Grain-v1 是序列密码征集eSTREAM 计划的最终获胜算法之一.

流密码的相关攻击是一种统计分析, 该分析方法与分组密码的线性分析[7]类似, 但更具有针对性, 主要针对基于LFSR 结构的同步流密码算法. 攻击目标为密钥流生成阶段LFSR 的初始状态. 相关攻击最早可追溯到对非线性组合生成器的分析, 我国著名密码学家肖国镇教授曾提出Xiao-Massey 定理[8]来说明输出序列与LFSR 的初始状态之间具有……