分组密码算法Lattice的滑动攻击*

潘向荣

（中国西南电子技术研究所，四川 成都 610036）

0 引 言

短波通信由于其设备质量轻、机动灵活和抗毁性强等优点，在军事通信领域占有极其重要的地位。自动链路建立（Automatic Link Establishment，ALE）[1]是一种无需用户操作即可使短波台站寻找一个合适的频率并建立链路的自动化技术，是短波通信系统中的重要组成部分。自20世纪70年代末至今，自动链路建立协议已经发展至第三代，即3G-ALE。与第二代ALE技术相比，3G-ALE技术提高了链路建立速度、信道利用率、数据吞吐率，能够在更低信噪比下实现连接，并支持Internet协议及应用等。全球许多政府和非政府组织均在使用利用ALE技术的无线电通信技术。

SoDark族算法[2]是面向ALE应用的分组密码算法，实现对ALE标准中协议数据单元（Protocol Data Unit，PDU）中敏感数据的机密性。SoDark族算法包括Lattice算法、SoDark-3算法和SoDark-6算法。Lattice算法应用于第二代ALE（2G ALE），分组长度为24 bit，密钥长度为56 bit，迭代轮数8轮。3G ALE标准中使用了称为SoDard-3的版本对26位协议数据单元（PDU）中的24位数据进行加密。SoDark-3的迭代轮数为16轮，其轮函数与Lattice算法相同。由于3G ALE还使用48位的PDU，因此SoDark-3已扩展为具有48位大小的版本，称为SoDark-6。

Lattice算法是SoDark族算法中的基本算法。对Lattice算法的分析成果将极大地促进对SoDark族算法的成功分析，进而实现对短波通信情报信息的破译，对获取其语义内容具有重要意义。本文简述了Lattice算法、SoDark族算法在短波通信系统中所起的作用及破译SoDark族算法的意义。第1部分简要描述Lattice算法；第2部分介绍滑动攻击的基本原理；第3部分详细介绍滑动攻击对Lattice算法的攻击；第4部分对滑动攻击算法性能进行分析；第5部分总结全文。

1 Lattice算法介绍

Lattice算法[3]是SoDark族算法中的基本算法，分组长度为24 bit，密钥长度为56 bit，迭代轮数8轮。Lattice加密算法的输入包括密钥（Key）、种子（S eed）和待加密数据3组数据。算法以每24 bit明文数据为单位分别进行加密计算。完整加密过程共包含8次迭代运算，每次迭代运算中的操作数据包括1 Byte密钥、1 Byte种子和1 Byte源数据。每个步骤运算结果从256×8 bit的加密运算表中查询相应行列，得到本次计算的8 bit结果。加密算法流程如图1所示。

加密使用56 bit密钥和64 bit种子，其中种子由TOD、频率、Word等构成，结构如图2所示。64 bit种子包含频率、当前时间、日期以及wordnumber，其中TOD时间要求是非递减的。月域由4 bit构成，1代表1月，12代表12月；日期域由5 bit构成，代表从1号～31号；粗时间域采用11 bit，代表从午夜开始的分钟数，午夜粗时间域和精时间域都清0；精时间域采用6 bit，表示更精确的秒级时间，当时间精度大于分钟时，精时间域默认为全1（时间质量为6或7）。采用时间同步协议获取精确时间后，精时间域更新为获取的精确时间。频率域每4 bit代表一个十进制数。

Lattice加密算法流程如下。Lattice算法中使用的S盒是一个从域GF(28)到GF(28)的映射，不妨表示为f:GF(28)→GF(28)，如图3所示。

不妨采用矢量V表示密钥变量字节，s表示TOD或频率种子字节。每次加密算法循环从矢量V和s中依次选取1 Byte进行计算，共包括8次循环,完成对24 bit源数据的加密。

假设A为每次加密循环共3个字节中的第1个字节，B为第2个字节，C为第3个字节，A´、B´和C´是本轮运算的输出，则每一轮中，计算方法如下：

2 滑动攻击的基本原理

滑动攻击由David Wagner和Alex Biryukov于1999年提出[4]，适用于算法的迭代过程具有一定的自相似性的密码算法。在多数情况下，滑动攻击与迭代轮函数的具体性质和执行轮数无关。，任何可以被分解为执行若干次轮函数F的密码算法都可以尝试采用滑动攻击来分析。换句话说，滑动攻击的特点是不依赖于密码算法的轮数，即如果采用滑动攻击能对某密码算法进行有效攻击，则将该密码算法的迭代轮数增加任意轮后所得到的新算法仍然不能抵抗滑动攻击。由于SoDark算法的轮函数与Lattice算法的轮函数相同，只是迭代轮数是Lattice算法的2倍，因此采用滑动攻击对Lattice算法的分析成果能极大地促进对SoDark算法的成功破译。

用 Fr○Fr-1○Fr-2○…○F1表 示 一 个 轮 数 为 r的迭代分组密码。滑动攻击的基本思想[5]是将一个加密过程相对于另一个加密过程“滑动”一轮。如果明密文对(P,C)和(P*,C*)满足条件F1(P)=P*和Fr*(C)=C*，则称该密文对为一个滑动对（Slide pair），如图4所示。滑动对实际上为分析者提供两组一轮的密码变换的输入和输出。

老师在鼓励学生阅读的同时不妨创设情境，让几个学生结为一个阅读小组布置一篇有趣的文章。例如在人教版小学语文二年级上册的课本中就有《曹冲称象》、《狐假虎威》等我国有名的短故事，但是很少有涉及到外国寓言童话的小文章，所以老师们不妨给学生布置一些《伊索寓言》、《格林童话》等，每周选择一个阅读小组让小组自行选择一篇最近阅读过的小故事进行小组课堂表演，利用表演的方式激发起学生的阅读兴趣。

根据滑动对的定义，滑动攻击将按以下步骤对密码算法进行攻击。假设密码算法输入为N个比特，由于轮函数Fi与其使用的轮密钥相关，若能选择轮密钥对(K,K*)使得Fi*=Fi+1，则根据生日攻击原理，需要2N/2个明文-密文对就能找到满足上述条件的滑动对。

假定分组密码算法的分组长度为N，如果采用滑动攻击能成功破译该算法，滑动攻击的复杂度通常接近于O(2N/2)。以色列学者Achiya Bar-On等人[6]针对采用代换-置换网络（Substitution Permutation Network，SPN）和Feistel结构的密码算法、GOST及其变体算法，提出了改进的滑动攻击方法。改进后的滑动攻击极大地降低了攻击的时间复杂度。

3 Lattice的滑动攻击

Lattice算法循环使用7 Byte密钥V与8 Byte种子s，轮函数Fn+1如下：

若选择另一个密钥V*和种子S*，满足：

则Fi*=Fi+1,1≤i≤7，恰好满足对其实施滑动攻击的条件。基于上述讨论，本文分析采用滑动攻击能有效破译Lattice算法的可行性。下面对Lattice算法实施滑动攻击的过程如图5所示。

注意到轮函数F1：

使用密钥V[0]、V[1]、V[2]，轮函数F9为：

使用密钥 V[3]、V[4]、V[5]，若两组明文 - 密文 对 (P,C)和 (P*,C*)满 足 F1(P)=P*， 由 于 Fi*=Fi+1，1≤i≤7，则一定有F8*(C)=C*，也就是已知轮函数F1、F9的输入与输出。在已知种子s的前提下，可以计算出 V[0]、V[1]、V[2]、V[3]、V[4]、V[5]，具体计算表达式如下：

计算出的6 Byte密钥不一定是正确的密钥，穷举V[6]，可得到完整的7 Byte密钥。通过两个明文-密文对，可验证分析得到的密钥是否正确。不妨假设N是明文-密文对的个数，攻击算法的伪代码如下：

攻击算法成功的关键在于存在两组明文-密文对(P,C)和(P*,C*)满足F1(P)=P*。在明文随机选取的前提下，它的概率Pr为：

4 对Lattice算法的滑动攻击算法性能分析

本文通过计算机仿真实现了对Lattice算法的滑动攻击实例。本文设置Lattice算法的56 bit密钥为C2 28 4A 1C E7 BE 2F，种子为543bd88000017550。通过使用上述滑动攻击方法和对应的攻击算法，分析得到Lattice密码算法的密钥与预置的密钥完全一致，如图6所示，表明本文成功地利用了滑动攻击方法对Lattice密码算法实施了完全破译。

5 结 语

SoDark族分组密码算法用于实现第二代和第三代自动链路建立（Automatic Link Establishment，ALE）系统所发送消息的机密性。Lattice算法是SoDark家族算法中的基本算法。本文基于滑动攻击原理，设计了采用滑动攻击分析Lattice算法的攻击算法，并通过计算机仿真给出了对Lattice算法采用滑动攻击进行密钥恢复的实例。仿真结果表明，本文采用滑动攻击方法对Lattice算法实施攻击的正确性和有效性。本文的分析成果对分析具有更高轮数的SoDark-3和SoDark-6密码算法提供了坚实基础。在后续的研究工作中，将进一步采用滑动攻击方法开展对SoDark-3和SoDark-6两个密码算法的分析。