pgp的安全问题分析.txt

当今

会心安理得的。专家的建议是使用加密体系实现所提供的最大码长。如果哪一种实现不 
  
能提供足够的码长，最好不要用它。 
  
    RSA的安全性依赖于大数分解的难度。因此PGP需要一些产生非常大的质数的方法。 
  
目前还没有一种迅捷的产生一个大质数的算法。因此，PGP实际采用的方法是产生一个大 
  
奇数，然后测试它的质数性。顺便提一句，质数的个数是无穷的，甚至它的分布密度也 
  
超出一般人的想象，数论给出的结论表明，n 以内的质数的个数趋近于 n/ln(n)。 
  
    为了测试一个数的质数性，一个显而易见的方法是作试探除法，将n用2到sqrt(n)的 
  
每个整数来除。如果n是质数，所有这些数都不能整除它。如果n是质数的话，这个算法的 
  
耗时是指数方式增长的，这对PGP需要测试的大数来说太不经济了。从这里也可以看出试 
  
探除法不是一条可行的RSA攻击道路。 
  
    PGP实际采用的方法是对候选奇数做费马测试。费马测试并不能确定它是否质数，但 
  
通过费马测试以后的数不是质数的概率微乎其微。下面是费马测试的细节： 
  
       － 待测奇数 n 
  
       － 在质数集合中依次选取一个质数 b ，b = 2,3,5,7...... 
  
       － 计算 w = b^(n-1) % n 
  
       － 如果对于所有 b ，w都为1，n 很可能是质数。否则 n 一定是合数。 
  
    取前四个质数的测试称为四阶费马测试，PGP采用的就是它。一阶测试误判的概率 
  
是 10^-13 ，二阶后是 10^-26 ，作完四阶测试后是 10^-52。而且它绝对不会漏掉一个 
  
质数。当然将合数误判为质数的可能性是存在的，这种能通过费马测试的合数被称为 
  
Carmichael 数，象 561,1105,1729 等等。它们很稀少，在 10^9 范围内只有 255 个。 
  
    下面是几种针对RSA有效的攻击方法，它们实际上对PGP没有效力，因为它们攻击的 
  
是加密协议环节上的漏洞，而不是RSA本身的。从这些例子可以看到PGP是如何在实现上 
  
堵住这些漏洞的。 
  
  ● 选择密文攻击 
  
    由于RSA密文是通过公开渠道传播的，攻击者可以获取密文。我们假设攻击者为A， 
  
密文收件人为T，A得到了发往T的一份密文c，他想不通过分解质因数的方法得到明文。 
  
换句话说，他需要 m = c^d 。 
  
    为了恢复 m，他找一个随机数 r ， r < n，当然他有T的公匙(e,n)。他计算： 
  
        x=r^e % n  （用 T 的公匙加密 r） 
  
        y=x*c % n  （将临时密文x与c相乘） 
  
        t=r^-1 % n 
  
    A 知道RSA具有下面的一个特性： 
  
        如果 x=r^e % n，那么 r=x^d % n 
  
    因此他想办法让T对 y 用T自己的私匙签名（实际上就是把 y 解密了），然后将 
  
结果 u=y^d % n 寄回给A。A只要简单地计算： 
  
        m = t*u % n 
  
    上面结论的推导是这样的： 
  
        t*u % n = (r^-1)*(y^d) & n 
                = (r^-1)*(x^d)(c^d) % n 
                = (c^d) % n 
                = m 
  
    要防止这种攻击的办法就是不要对外来的随机信息签名，或者只对信息的MD5特征值 
  
签名。在这里就很容易明白为什么要强调MD5的单向性了，因为MD5的结果是不能预定的， 
  
就是说A难以凑出一份刚好能产生 y 这样的MD5特征值的明文来让T签名。 
  
  ● 过小的加密指数 e 
  
    看起来，e 是一个小数并不降低RSA的安全性。从计算速度考虑，e 越小越好。可 
  
是，当明文也是一个很小的数时就会出现问题。例如我们取 e=3 ，而且我们的明文 m 
  
比 n 的三次方根要小，那么密文 c = m^e % n 就会等于 m^3。这样只要对密文开三次 
  
方就可以得到明文。 
  
    PGP对这个漏洞的处理是在明文上加上一个随机数，这样保证 m > n ，而且缺省的 
  
e 值为17，如果不行再用19，23 等等。 
  
  ● RSA的计时攻击法 
  
    这是一种另辟蹊径的方法。是由 Paul Kocher 发表的。大家可以发现，RSA的基本 
  
运算是乘方取模，这种运算的特点是耗费时间精确取决于乘方次数。这样如果 A 能够监 
  
视到RSA解密的过程，并对它计时，他就能算出d来。细节我就不复述了。我想说的是如 
  
何抵御它。Rivest说，最简单的方法就是使RSA在基本运算上花费均等的时间，而与操作 
  
数无关。其次在加密前对数据做一个变换（花费恒定时间），在解密端做逆变换，这样 
  
总时间就不再依赖于操作数了。 
  
    至于PGP根本不用担心计时攻击，因为PGP采用了中国余数理论的方法加速了运算，同 
  
时也使耗时与操作数无关。同时计时攻击对攻击者资源的要求太高，实时监视加密过程 
  
不是任何人都可能做到的。在这里提出这种攻击是因为：虽然它目前还不实用，但从理论 
  
上是一个崭新的思路，值得注意。 
  
  ● 其他对RSA的攻击法 
  
    还有一些对RSA的攻击，象公共模数攻击。它是指几个用户公用一个模数 n ，各自 
  
有自己的 e 和 d，在几个用户之间公用 n 会使攻击者能够不用分解 n 而恢复明文。 
  
但是PGP是不会在用户之间公用模数的。 
  
    最后谈谈RSA密匙长度的问题，多长的密匙是安全的。专家指出，任何预言都是不 
  
理智的，就目前的计算机水平用1024-bits的密匙是安全的，2048-bits是绝对安全的。 
  
但是他们并不指望这个局面延续到下世纪，他们只是指出：如果RSA象有些人说的那样 
  
脆弱，就不可能从1977年一直保持到现在还没有被攻破。 
  
◎ MD5 的安全性问题 
  
     MD5是一种在PGP中被用来单向变换用户口令和对信息签名的单向散列算法。 
  
     一种单向散列的强度体现在它能把任意的输入随机化到什么程度并且能产生唯一 
  
的输出。对单向散列的直接攻击可以分为普通直接攻击和“生日”攻击。 
  
  ● 对MD5的普通直接攻击 
  
    所谓直接攻击又叫野蛮攻击。攻击者为了找到一份和原始明文 m 散列结果相同的 
  
明文 m' ，就是 H(m)=H(m') 。普通直接攻击，顾名思义就是穷举可能的明文去产生一 
  
个和 H(m) 相同的散列结果。对MD5来说散列结果为128-bits，就是说如果攻击者有一台 
  
每秒尝试1,000,000,000条明文的机器需要算约10^22年，同时兴许会同时发现m本身:))。 
  
  ● 对MD5的生日攻击 
  
    生日攻击实际上只是为了找到两条能产生同样散列结果的明文。记得那个有名的 
  
概率生日问题吗？在 N 个人中至少有两个人生日相同的概率是多少？所谓生日攻击 
  
实际上只是用概率来指导散列冲突的发现，对于MD5来说如果尝试2^64条明文，那么它 
  
们之间至少有一对发生冲突的概率就是 50％。仅此而已，对当今的科技能力来说，它 
  
也是不可能的。一台上面谈到的机器平均需要运行585年才能找到一对，而且并不能马 
  
上变成实际的攻击成果。因为码长和速度的关系，对crypt(3)的生日攻击就成功得多。 
  
  ● 其他对MD5的攻击 
  
    微分攻击被证明对MD5的一次循环是有效的，但对全部4次循环无效。（微分攻击是 
  
通过比较分析有特定区别的明文在通过加密后的变化传播情况来攻击加密体系的。） 
  
    有一种成功的MD5攻击，不过它是对MD5代码本身做了手脚，是一种crack而不是hack 
  
更算不上cryptanalysis了。而且如果你做了PGP发行包的签名校验，是容易发现代码被 
  
替换过了的。 
  
  ● 口令长度和信息论 
  
    根据传统信息论，英语的每个8-bits字母的信息熵为1.3bits。如果口令足够长， 
  
MD5的结果就会足够随机。对 128-bits 的MD5输出来说，一个长达98个字符的口令将给 
  
出一个随机的密匙。 
  
     (8/1.3)*(128/8) = 98.46 chars 
  
    可是谁会用一个象下面这样长的口令呢？ 
  
        12345678901234567890123456789012345678901235678901234567890 
        1234567890123456789012345678 
  
    1.3 bits 的信息熵来自于英语语法的规律性这个事实，字母出现概率的不等造成了 
  
熵的减小。如果26个拉丁字母出现的概率均等，信息熵将会增至 
  
      log(26)/log(2) = 4.7 bits 
  
    这样一个随机密匙所需口令长度就减为 27.23 chars 了，如果再加上大小写和几个 
  
符号还可以减少。关于选择口令的问题可以参考任何关于安全性的书籍，它们都适用， 
  
上面是关于PGP本身特色的部分。 
  
◎ 随机数的安全性问题 
  
    PGP使用两个伪随机数发生器（PRNG)，一个是ANSI X9.17发生器，另一个是从用户 
  
击键的时间和序列中计算熵值从而引入随机性。ANSI X9.17 PRNG使用IDEA而不是 3DES 
  
来产生随机数种子。Randseed.bin 文件最初是利用用户击键信息产生的，每次加密前后 
  
都会引入新的随机数，而且随机数种子本身也是加密存放的。 
  
  ● ANSI X9.17 PRNG 
  
    官方发布的 ANSI X9.17 标准使用的是 Triple DES 作为内核，这个很容易改用 
  
IDEA实现。 X9.17 需要randseed.bin中的 24 bytes 的随机数，PGP把其他384 bytes 
  
用来存放其他信息。X19.7 工作过程大致如下： 
  
        E() = IDEA 加密函数，使用一个可复用的密匙（使用明文产生）。 
        T =  从 randseed.bin 文件中来的时间 
        V =  初始化向量 
        R =  生成的随机密匙（用来加密一次PGP明文） 
  
        R = E[E(T) XOR V] 
  
        下一次的初始化向量计算如下： 
  
        V = E[E(T) XOR R] 
  
  ● 用户击键引入随机性 
  
    这是真正的随机数，没有什么好说的，只是尽量使击键无规则就行。输入的熵越大 
  
输出的随机数的熵就越大。 
  
  ● X9.17 用MD5进行预洗 
  
    所谓“洗”就是指象洗牌一样把数据打乱，加密前叫预洗，加密后为下一次加密的 
  
准备叫后洗。PGP的日常随机数产生器 X19.7 是用明文的MD5值来预洗的，它基于攻击 
  
者不知道明文这样一个假设。如果攻击者知道明文他就没有太大必要去攻击了，当然也 
  
有这种可能，不过这只是会削弱一点PRNG的随机性罢了。下面我们将看到还有后洗操作。 
  
  ● randseed.bin 的后洗操作 
  
    后洗操作被认为是更安全的。更多的随机字节被用来重新初始化 randseed.bin 文 
  
件，它们被用当前的随机临时PGP密匙来加密。同样如果攻击者知道这个密匙，他就不用 
  
攻击 randseed.bin 文件，相反他更关心 randseed.bin 文件当前的状态，因为可能从 
  
中获得下次加密的部分信息。因此对 randseed.bin 文件的保护和公匙环及私匙环文件 
  
同样重要。当然，如果不是密码专家这些文件都给他也没事。 
  
◎ PGP的密匙和口令的安全性问题