时间存储折衷分析.docVIP

时间存储折衷分析(martin hellman) 1、思想简介 时间存储折衷攻击是一种选择明文攻击方法。Martin Hellman这篇开山之作主要是针对分组密码算法进行分析的，其弱点在于仅仅使用一个明密文对，无法使用更多的明密文对，从而导致其分析结果并不是最优。目前如何使用更多的明密文对从而减少攻击时间是个非常困难的问题。尽管如此，其分析方法比密钥穷举攻击的时间复杂度小，比查表攻击的空间复杂度要小。实际上，密钥穷举攻击和查表攻击分别是在时间和空间上的两个极端做法，而该篇阐述的方法是上述两种方式的一种折衷。该方法的总体思路：由于分组密码算法fk(x0)=y，将k作为输入，y作为输出，其函数称作Sx0(.)。在已知y和分组密码算法是安全的情况下，求取k是困难的，因此Sx0(k)=R(y)是单向函数，仿照【1】R. C. Merkle and M.E.Hellman,Hiding information and signatures in trapdoor knapsacks, IEEE Inform Theory 1978.和【2】S. C.Pohlig and M.E.Hellman,An improved algorithm for computing logarithms over GF(p) and its cryptographic significance,IEEE Inform Theory 1978.的思路将Sx0(.)作为离散对数函数（即：单向函数））…,km,0,然后将Sp0(k1,0)反复迭代产生一个链条(上面有t+1个元素，仅用前t个元素)，以此类推--共得到m个这样的链条，最终形成m*t（仅仅计算所使用的点的数目）个元素的矩阵。如下图所示： 图1 假设刚开始m个路径是不相交的，但接下来的一个路径却与前面的路径之一有公共点。由于每条路径最多有t个元素，因此为了保证第m+1路径的每个元素和前m个路径没有交集，就必须满足t*(mt)(N，否则mt个元素的集合和t个元素的集合相交的概率（1-P(n,t,mt,0)）大于0.5（其中P是泊松分布的密度函数）m*t2(N，这两个集合就很可能不相交，这样我们就选择满足关系m*t2=N的m和t，我们称之为矩阵中止规则。如果我们仅仅使用上述一个矩阵点进行攻击，其攻击成功概率是多少呢？上述一个矩阵所覆盖的点仅仅有mt=N/t个。因此，如果t较大时，根据生日攻击可知：寻找uk成功概率很低。一个矩阵最多也就m行，不可能再大了。如何解决这个问题呢？ Martin Hellman的伟大之处在于他发现可以使用fi(x)=h(f(x))所定义的原始f的变形fi，其中hi是其简单输出的变体（即：将f(x)的比特重新排序）。这些修改的f变形具有下面三个性质： 1．? 对于i≠j，fi和fj矩阵中的点是根本无关的，因为这两个不同矩阵中存 在一个共同点并不意味着两条路径中的后续点一定相等。因此，t个矩阵的并集（每个包含mt个点）很可能含有固定的一部分空间。 2．? 在修正后的点yi＝fi(x)＝hi(f(x))上反转任意修正函数fi，可以解决已知的 y＝f(x)计算x的问题。 3．? 即使我们不知道x的值也可以将hi应用于已知的y＝f(x)来计算yi＝fi(x) 的值。 通过w个修改的fi，产生w个矩阵（每个矩阵有m*t个点））)中。 2、下面介绍时间存储折衷攻击的预处理和攻击过程： 第1部分预处理过程如下： 输入：明文p0,密文c0和约减函数R。 参数：w个表，m个随机起始点，每个链条有t个数。 预处理开始： For s=1 to w do { 随机选择约减函数Rs=Hs(R并且定义fs：k(Rs(fk(p0)； For i=1 to m do { 随机选择k_start； k_end(k_start； for j=1 to t do {计算 k_end(fs(k_end);} 将(k_end,k_start)点插入到Ts中。 } } 第2部分攻击过程如下： 输入：明文p0,密文c0。 参数：w个表，m个随机起始点，每个链条有t个数。 For s=1 to w do { 设置i为0; 设置k_init(fs(p0);k(k_init; While Ts[k_init][]数组没有元素或者it时，do { i++; k (fs(k);} if Ts[k]数组有元素 {得到Ts[k][0]=(k_start,k); 用fs反复迭代k_start，得到k_init所在链条的前一个元素key,输出key, 该key就是明密文对(p0,c0)对应的密钥了。 Printf(“寻找密钥成功,程序结束