中文模板

Size: px

Start display at page:

Download "中文模板"

笃秦
5 years ago
Views:

1 -985/4/55)767 4 Journal of Software 软件学报 Vol5, o5 对一个基于细胞自动机的分组密码变形的分析张文涛 +, 卿斯汉,, 吴文玲信息安全国家重点实验室中国科学院研究生院 ) 北京 9) 信息安全国家重点实验室中国科学院软件研究所 ) 北京 8) 中国科学院信息安全技术工程研究中心, 北京 8) Cryptanalysis of a Variant of a Cellular Automata Based Cryptosystem ZHAG Wen-Tao +, QIG Si-Han,, WU Wen-Ling State Key Laboratory of Information Security Graduate School, The Chinese Academy of Sciences), Beijing 9, China) State Key Laboratory of Information Security Institute of Software, The Chinese Academy of Sciences), Beijing 8, China) Engineering Research Center for Information Security Technology, The Chinese Academy of Sciences, Beijing 8, China) + Corresponding author: Phn: ext 4, wentaozhang@sinacomcn Received -- Accepted -4-8 Zhang WT, Qing SH, Wu WL Cryptanalysis of a variant of a cellular automata based cryptosystem Journal of Software, 4,55):767~77 Abstract: Subhayan Sen et al have proposed a block cipher system CAC cellular automata based cryptosystem) based on cellular automata theory, but they have not given a detailed description of some of its modules rom the point of view of application, one module of CAC is fixed, and the variant is called SCAC same major-ca CAC) The analysis of SCAC is given, and the results show that the variant of this cipher is very insecure under chosen-plaintext attacks Using cryptanalysis of the variant for reference, attacks on the cipher itself may be found when some of the design details of the cipher are known Key words: block cipher system cellular automata security analysis chosen-plaintext attack 摘要 : Subhayan Sen 等人提出了一个基于细胞自动机的分组密码系统 cellular automata based cryptosystem, 简称 CAC), 但并没有给出 CAC 的某些构造模块的细节描述, 从应用角度考虑, 将其中的一个模块固定得到 CAC 的变形 SCACsame major-ca CAC) 对 SCAC 进行密码分析, 结果表明,CAC 的这种变形在选择明文攻击下是极不安全的对 SCAC 进行分析的意义在于, 知道 CAC 的具体设计细节以后, 借鉴对 SCAC 的分析, 有可能对 CAC 密码系统本身的安全性造成威胁关键词 : 分组密码系统细胞自动机安全性分析选择明文攻击 Supported by the ational atural Science oundation of China under Grant os 6747, 947 国家自然科学基金 ) the ational Grand undamental Research 97 Program of China under Grant og99958 国家重点基础研究发展规划 97)) 作者简介 : 张文涛 977-), 女, 陕西丹凤人, 博士生, 主要研究领域为分组密码设计与分析卿斯汉 99-), 男, 研究员, 博士生导师, 主要研究领域为信息安全理论和技术吴文玲 966-), 女, 博士, 副研究员, 主要研究领域为分组密码设计与分析

2 768 Journal of Software 软件学报 4,55) 中图法分类号 : TP9 文献标识码 : A 一个细胞自动机 cellular automata, 简称 CA) 可以被看作一个模拟离散动态系统的并行机,CA 中细胞单元并行的简单性及其交互的局部性使得它易于硬件实现人们已经设计了许多基于 CA 的密码系统, 比如, 文献 [] 中提出了一个基于 CA 的伪随机序列生成器, 文献 [] 构造了一个基于 CA 的公钥密码系统, 文献 [] 给出了基于 CA 的分组密码系统和流密码系统 Subhayan Sen 等人在文献 [4] 中提出了一个新的基于 CA 的分组密码系统 CACcellular automata based cryptosystem), 设计者称 CAC 密码系统的安全性与高级加密标准 AES 相当, 并且 CAC 的加解密的速度要优于 AES 然而, 在文献 [4] 中, 设计者并没有给出 CAC 的某些构造模块的细节描述从应用角度考虑, 我们将其中的一个模块固定得到 CAC 的一个变形 SCACsame major-ca CAC) 下面我们将对 SCAC 用两种方法进行密码分析, 结果表明,CAC 的这种变形在选择明文攻击下是极不安全的本文在第节给出 CAC 密码系统的描述, 然后从应用角度考虑, 固定 CAC 密码系统的一个模块, 将 CAC 的这种变形记为 SCAC 第节给出对 SCAC 的密钥恢复的一个选择明文攻击第节给出对 SCAC 的一个部分明文恢复的选择明文攻击第 4 节总结全文 CAC 密码系统的描述细胞自动机的一些基本概念细胞自动机由一系列细胞单元按一定方式排列而成, 每个细胞单元状态的演变依赖于与它邻近的一些细胞单元的状态在 CAC 中用到的细胞自动机的每一个细胞单元的下一个状态依赖于自身及相邻的两个细胞单元的当前 t 状态用 q 表示第 i 个细胞单元在时刻 t 的状态, 该细胞单元在下一个时刻 t + 时的状态由 i t t q + i = + t t f qi, qi, qi ) 给出, 称 f 为该细胞自动机的规则将细胞单元的状态在 G p ) 中取值的 CA 称作 G p ) -CA 如果一个 CA 的每个细胞单元的状态在经过有限次演化后都可以恢复到原来的初始状态, 就称该 CA 为一个群 CA CAC 密码系统的描述 CAC 是一个基于细胞自动机的分组密码系统它的分组长度和密钥长度都是 8 比特, 密码系统基于两类具有 6 个细胞单元的 G p ) -CA, 分别称作 ajor CA 和 inor CAajor CA 是一个周期为的群 CA, 即经过次演化后, 每个细胞单元的状态都会恢复到初始状态 inor CA 也是一个群 CA, 它的周期达到了可能的最大值 8 ) 文献 [4] 中指出, 可以把 inor CA 看作一个性能好的伪随机序列生成器将明文消息划分成 8 比特的明文块, 分别对每一个明文块进行加密下面用变量 Γ 表示待加密的明文块用 K 表示 8 比特长的用户选择密钥, 在给第一个明文块加密时, 令 S = K 解密过程由加密过程惟一确定, 这里不再给出解密过程的详细描述, 只在每一步中给出这一步的逆运算 Step 预计算子密钥 : 将 S 作为 inor CA 的初始输入状态, S 经过 d 次演化后的状态记为 S, S 即为加解密过程中要用到的子密钥将这个变换用表示, 即 S = S ) inor CA 的周期为 8, 因此只需将 S 作为 inor CA 的输入经过这个逆变换记作 S = S ) n Step 线性变换 : 从 S 中获取 δ, 将 8 比特的明文块 Γ 的每个字节循环移位 δ 比特, 结果记为 Γ 解密时, 将相应状态的每个字节朝相反方向循环移位 δ 比特 Step 仿射变换 : 从 S 中获取 8 ) 次演化后就得到了 S, 将 d

3 张文涛等 : 对一个基于细胞自动机的分组密码变形的分析 769 以作为参数, 用特定的有效算法合成一个 ajor CA 将 Γ 作为该 ajor CA 的初始输入状态, 经过次 S 演化后的状态记为 Γ ajor CA 的周期为, 因此在解密时, 只需将合成的 ajor CA 经过 ) 次演化即可 Step 非线性变换 : 先定义非线性函数 CC 由 y = x { c c ) c c) c c)} 给出, 其中, x 是输入比特, y 是输出比特, 是逻辑运算 AD c, c c 是个控制比特, 由 S 决定, 从 Γ 中抽取 5 个比特抽取的方式由 S 决定 ), 称它们为固定比特如果这 5 个固定比特中取值为的个数大于, 则除了这 5 个固定比特保持不变以外, 特经过 C 变换要强调的是, 由 Γ S 中其余的每个比生成两组控制比特, 得到两组 C 变换, 在这里交替使用 ), 所得结果记为如果这 5 个固定比特中取值为的个数小于或等于, 则令 Γ = Γ, 即保持 Γ 不变无论怎样, 固定比特在这一步骤中都保持不变, 从而保证了解密算法的可行 Step 4 子密钥加运算 : 将 Γ 与 S 异或, 所得结果 Γ 即为 Γ 所对应的密文 encr 至此也就完成了对一个 8 比特的明文块的加密, 将加密过程中的 Γ 存储起来, 作为加密下一个明文块时要用到的 inor CA 的初始输入状态 S Step 5 如果还有未加密的明文块, 则返回 Step, 对下一个明文块进行加密操作对 CAC 的初步分析和 CAC 的变形 SCAC 在 CAC 中, 加密不同的明文块所使用的子密钥也不同, 子密钥不仅与用户选择密钥有关, 还与上一次所加密的明文块有关加密过程中对明文块进行的循环移位运算所使用的 ajor CA ajor CA 演化的次数两组控制比特固定比特位置的选择都与当前使用的子密钥有关加密不同的明文块, 因为子密钥的不同, 导致了加密过程中使用的这些参数或模块 ) 也不相同设计者称这样做的目的是使得 CAC 的加密行为接近于一次一密系统, 从完善保密性的角度提升 CAC 的安全性而传统中, 使用分组密码对一个明文消息加密时, 对于各个明文块, 所使用的子密钥都是相同的, 比如使用常见的 CBC,CTR 等工作模式利用 DES 或 AES 算法构造分组密码系统并且, 在文献 [4] 中,CAC 的设计者并没有描述这些参数或模块是怎样通过子密钥来选取的, 这就为算法的分析带来了很大的困难另外, 传统中在设计分组密码时, 是将一个密码学性质不是很好的函数轮函数 ) 经过多次迭代来形成一个密码学性质好的分组算法 CAC 密码没有采取迭代的设计方式, 设计者声称在加密不同的明文块时, 选用不同的密钥就能够在很大程度上保证算法的安全性而正是由于 CAC 没有采用迭代结构, 才使得下面我们对 CAC 的一个变形的分析变得简单在 CAC 加密过程的第个步骤中, 需要在子密钥的控制下随机生成一个 ajor CA 文献 [4] 中指出, 满足周期为的 ajor CA 的个数大于 8 这个数字正是 8 比特明文空间中明文块的个数 ) 在假设每次加密中所使用的子密钥随机的前提下, 所使用的 ajor CA 也具有随机性然而, 文献 [4] 并没有给出利用子密钥合成 ajor CA 的具体算法从应用角度考虑, 对 CAC 软硬件实现时利用特定的合成算法生成的不同 ajor CA 之间不可能相互独立, 攻击者完全有可能从合成算法中获取大量的冗余信息假定在加密过程中,CAC 始终使用相同的 ajor CA, 下面的分析结果表明, 在这样的假设下,CAC 是非常不安全的将 CAC 的这种变形算法记为 SCAC 这样做的一个好处是, 如果知道利用子密钥合成 ajor CA 的具体算法, 利用选择明文攻击, 通过寻找和揭示不同明文块所对应的 ajor CA 间的关系, 借鉴下面对 SCAC 的分析方法, 就可以直接对 CAC 进行分析, 从而有可能对 CAC 密码系统本身的安全性造成威胁因此, 对 SCAC 的分析是有意义的 Γ

4 77 Journal of Software 软件学报 4,55) 对 SCAC 在选择明文攻击下的一个密钥恢复攻击这一节利用选择明文攻击, 目的是恢复出 SCAC 加密系统的用户选择密钥 K 在 SCAC 的加密算法中, δ, 的取值都与所使用的子密钥有关对于每一个明文块, δ 的取值有 8 种可能性, 即 δ {,,,,7} 的取值有种可能性, 即 {,,,,}, 因此, 在不知道子密钥的情况下, 可以将一个明文块经过 Step 以后的结果限定在 8*= 8 个可能的取值中 Step 的非线性变换是 SCAC 中惟一的非线性模块, 在这一步中, 如果 5 个固定比特中取值为的比特个数小于或等于, 则这一步相当于恒等变换在另一种情况下, 即当 5 个固定比特中取值为的比特个数大于时, 因为有 / 的概率使得控制比特 c, c c 满足, c ) c c) c c) = c ) 那么, 在两组控制比特独立选取的假设下, 将有 /4 的概率使得两组控制比特都满足式 ), 这时,Step 也相当于恒等变换总共有 /+/*/4=5/8 的概率使得 Step 相当于恒等变换下面给出对 SCAC 在选择明文攻击下的一个密钥恢复攻击的步骤 : a) 随机选取一个 56 比特长的比特串作为明文消息, 记为 PP P, P 的长度都是 8 比特 ), 设明文块 P, P 经过 SCAC 加密后所对应的密文分别为 C 和 C P P ), ),, 55) b) 让 δ 和遍历每一个可能的取值, 计算出和经过 Step 以后的 56 个可能的取值, 分别记为 ), ),, 55) 和设实际上 P 经过 Step 后的结果为 ), P 经过 Step 后的结果为 j) i c) 如果 P, P 经过 Step 时的变换都是恒等变换, 由 Step 4, 有 i) K = C ) ) j) = C ) 其中, K) 是加密 P 时所使用的子密钥, 是加密 P 时所使用的子密钥对每一个 n 55, 计算和 C n), 如果集合 { } 中的某一个元素和集合 { C )} 中的某一个元素相等, 就说明有碰撞发生如果 P, P 经过 Step 时的变换不全是恒等变换, 由于和 P n 选取的随机性以及 inor CA 函数 ) 良好的伪随机特性, 从而在这种情况下有碰撞发生的概率非常小, 可以忽略不计因此, 我们可以近似地认为有碰撞发生当且仅当 P, P 经过 Step 时的变换都是恒等变换 c) 当有碰撞发生时, 设 u)) = C v), u, v 55 由式 ), 则有 i = u, j = v 再由式 ), 有 K = i) C ), 这样就恢复出了用户选择密钥 K c) 如果没有碰撞发生, 则返回步骤 a), 重新选取两个明文块, 按照上述步骤运行, 直到有碰撞发生为止 P Step 为恒等变换的概率为 5/8, 在明文消息和子密钥独立均匀分布的假设下, 式 ) 和式 ) 同时成立的概率为 5/8*5/8=5/64 因此, 上述的攻击步骤平均运行次, 就会有碰撞发生, 从而恢复出用户选择密钥该攻击的数据复杂度为 *=6 个选择明密文对忽略异或运算, 时间复杂度大约为 * 9 次 Step +Step ) 运算再加上 * 9 次运算上述事实表明,SCAC 在选择明文攻击的情况下, 利用很小的计算代价就能够恢复出它的用户选择密钥对 SCAC 在选择明文攻击下的一个部分明文恢复攻击本节讨论的明文恢复攻击是针对选择明文攻击而言的攻击者的任务是 : 给定一个随机选取的明文所对应的密文, 解密这个密文, 恢复出它所对应的明文在攻击过程中, 攻击者与加密系统有下面的交互 : 攻击者可以选择很多明文, 加密系统给出它们所对应的密文, 即攻击是指选择明文攻击有关明文恢复攻击的定义和讨论参见文献 [5] 中的第 6 节下面给出对 SCAC 在选择明文攻击下的一个部分明文恢复攻击的步骤该攻击不直接恢复用户选择密钥, 而是恢复第个明文块在经过 Step 以后的结果, 从而由加密算法, 通过链接计算, 也就知道了加密第个明文块之后的每一个明文块时所使用的子密钥

5 张文涛等 : 对一个基于细胞自动机的分组密码变形的分析 77 a) 选取第个明文块为 8 比特的全字符串即 8 个比特都取 ), 记为的密文分别为和 C P P 记第个明文块及其对应 b) 经过 Step 以后保持不变, 经过 Step 以后, 有个可能的取值, 分别记为 ), ),, ) P 对每一个 n, 计算, 则加密下一个明文块 P 时所使用的子密钥在集合 { } 中 c) 让 n 从开始取值, 每次增加 : 以作为加密时所使用的子密钥, 对 P 进行加密操作如果以某一个 i ) 作为子密钥, 加密所得的密文与相等, 则终止操作并且以几乎为的概率确认, 加密所用的子密钥为 P P C, P 经过 Step 以后的结果为 i) 恢复出 P 经过 Step 以后的结果 i), 则由加密过程, 可以计算出加密第个明文块时所使用的子密钥, 并且通过递推, 可以计算出在加密其后的每一个明文块时所使用的子密钥也就是说, 该攻击可以恢复出第个明文块以后包括第个明文块 ) 的所有明文块的加密过程, 从而给定任意一个密文, 就可以通过计算加密时所用的子密钥来恢复它所对应的明文该攻击的数据复杂度为个选择明密文对, 时间复杂度为次 Step +Step ) 运算和次加密过程以及次运算从上面的结果可以看出, 当 SCAC 对一个明文消息进行加密时, 利用选择明文攻击, 使用很小的计算代价就能够恢复出第个明文块以后包括第个明文块 ) 的所有明文块的加密过程 4 总结 Subhayan Sen 等人在文献 [4] 中提出了一个新的基于细胞自动机的分组密码系统 CAC), 但保密了其中某些密码模块的细节描述, 这就增加了对 CAC 进行密码分析的难度从应用角度考虑, 我们将其中的一个模块固定, 得到 CAC 的一个变形 SCAC 本文用两种方法对 SCAC 进行密码分析, 两种方法分析的结果都表明,CAC 的这种变形在选择明文攻击下是极不安全的对 SCAC 进行分析的意义在于, 知道 CAC 的具体设计细节以后, 借鉴对 SCAC 的分析, 有可能对 CAC 密码系统本身的安全性造成威胁本文的分析结果表明,CAC 分组密码系统存在一定的安全隐患通过初步的调研, 我们相信, 作为密码系统的一种构造模块, 细胞自动机具有许多良好的密码学性质然而, 目前还没有一种公众认可的安全高效的基于细胞自动机的分组密码系统那么, 如何把细胞自动机用于分组密码系统的设计, 构造出安全高效的分组密码系统, 还值得进一步研究 P References: [] Wolfram S Cryptography with cellular automata In: Williams HC, ed Advances in Cryptology 85 Santa Barbara: Springer-Verlag, ~4 [] Guan P Cellular automaton public-key systems Complex System, 987,):5~57 [] andi S, Kar BK, Chaudhuri PP Theory and application of cellular automata in cryptograph IEEE Trans on Computers, 994, 4):46~57 [4] Sen S, Shaw C Cellular automata based cryptosystem CAC) In: Deng RH, Qing SH, Bao, Zhou JY, eds Information and Communications Security LCS 5, Berlin: Springer-Verlag, ~4 [5] Goldwasser S, Bellare Lecture otes on Cryptography

92

* ** ** 9 92 % 80.0 70.0 60.0 50.0 40.0 30.0 20.0 0.0 0.0 % 60.0 50.0 40.0 30.0 20.0 0.0 0.0 990 2000 200 2002 2003 2004 2005 2006 2007 2008 2009 200 978 979 980 98 982 983 984 985 986 987 988 989 990