文章作者：Loking
■内容提要■
◎ 前言
◎ IDEA 的安全性问题
◎ RSA 的安全性问题
● 选择密文攻击
● 过小的加密指数 e
● RSA的计时攻击法
● 其他对RSA的攻击法
◎ MD5 的安全性问题
● 对MD5的普通直接攻击
● 对MD5的生日攻击
● 其他对MD5的攻击
● 口令长度和信息论
◎ 随机数的安全性问题
● ANSI X9.17 PRNG
● 用户击键引入随机性
● X9.17 用MD5进行预洗
● randseed.bin 的后洗操作
◎ PGP的密匙和口令的安全性问题
◎ 没有完全删除的文件
◎ 物理安全性
◎ 多用户系统下的泄密
◎ PGP的时间标戳可靠性
◎ 流量分析
◎ 现实的PGP攻击
被动攻击：
● 击键窥探
● 电磁泄露窥探
● 内存空间窥探
● 磁盘缓存窥探
● 报文嗅探
主动攻击：
● 特洛伊木马
● 篡改PGP代码
◎ 结语
**************************************************************************
这可能是个最难写的题目了，PGP本身就是一个数据安全产品，它会有什么安全性问题呢？PGP的作者 Phil Zimmermann 在PGP文档中说到：“没有哪个数据安全系统是牢不可破的。”PGP也不例外。我们研究它的安全漏洞就是为了让用户知道哪些事会降低PGP的安全性，以及如何避免它们。下面是这些漏洞：
口令或私匙的泄密、公匙被篡改、你删除的文件被人恢复、病毒和特洛伊木马、物理安全受到侵犯（物理安全指计算机等物理资源的安全）、电磁泄露、暴露在多用户系统中、网络数据流分析，甚至会有可能被直接从密码学分析的角度被解密（这当然是可能性最小的了）。
我们先分别看看PGP加密体系的四个关键部分的安全性问题。PGP是个杂合算法，所谓“杂合”体现在它包含：一个对称加密算法（IDEA）、一个非对称加密算法（RSA）、一个单向散列算法（MD5）以及一个随机数产生器（从用户击键频率产生伪随机数序列的种子）。每种算法都是PGP不可分割的组成部分，对它们各有不同的攻击方式。
◎ IDEA 的安全性问题
IDEA是PGP密文实际上的加密算法，对于采用直接攻击法的解密者来说，IDEA是PGP密文的第一道防线。
关于IDEA的原理请参见《PGP简介》，在这里我主要谈谈与安全性有关的部分。IDEA，一种由 Lai 和 Massey 在 1992 年完成的对64bit大小的数据块的传统加密算法。
IDEA是 International Data Encryption Algorithm 的缩写。它基于“相异代数群上的混合运算”设计思想，它比DES在软件实现上快得多，和DES一样，它也支持“反馈加密（CFB）”和“链式加密（CBC）”两种模式，在PGP中采用IDEA的64-bits CFB模式。
IDEA比同时代的算法象：FEAL, REDOC-II, LOKI, Snefru 和 Khafre都要坚固，而且最近的证据表明即使是在DES上取得巨大成功的 Biham 和 Shamir 的微分密码分析法对IDEA也无能为力。Biham 和 Shamir 曾对IDEA的弱点作过专门分析，但他们没有成功。直到目前没有任何关于IDEA的密码学分析攻击法的成果发表，据目前我接触到的文档中谈到无论是NSA还是hacker们都还没有办法对IDEA进行密码学分析，因此对IDEA的攻击方法就只有“直接攻击”或者说是“密匙穷举”一种了。
那么对IDEA的直接攻击难度如何呢？我们知道IDEA的密匙空间（密匙长度）是128位，用十进制表示所有可能的密匙个数将是一个天文数字：
340,282,366,920,938,463,463,374,607,431,768,211,456.
为了试探出一个特定的密匙，平均要试探一半上面的可能性。即使你用了十亿台每秒钟能够试探十亿个密匙的计算机，所需的时间也比目前所知的宇宙的年龄要长，而即使是在当代制造每秒试探十亿个密匙的计算机还是不可能的。因此对IDEA进行明文攻击也是不可能的，更何况从PGP的原理看一个IDEA的密匙失密只会泄露一次加密的信息，对用户最重要的密匙——RSA密匙对的保密性没有什么影响。
那么看来IDEA是没有什么问题了，因为你既不能从算法中找到漏洞又没法明文攻击实际上呢？漏洞还是有的，大家知道 Netscape 的安全性风波吧，就是因为忽视了密匙随机生成的问题，Netscape的随机密匙生成算法生成的密匙很有“规律”，而且远远没有均布到整个密匙空间去，所以尽管Netscape的美国版采用128bits的密匙，还是被用很小的机时代价破掉了。那么PGP是不是也有这个毛病呢？我将在下面谈到随机数生成时再详细说，这里提到它是为了说明PGP各个部分之间的依存关系。
当有人发现PGP实际上不是一种“纯粹的”RSA加密算法时，他们担心由于加密链中IDEA的弱点而被攻破。实际上这是由于一种误解：他们认为公匙加密生来就比传统加密安全得多。实际上密码分析专家计算过，穷举128-bit IDEA密匙和分解3100-bitRSA密匙的工作量相当，而实际上1024-bit的RSA密匙已被认为是机密级的，而且1024-bit的纯粹RSA加密要比128-bit的IDEA加密要慢4000多倍。RSA的长处在于它的易用性而不是它的坚固性，相反加密链的弱点不在IDEA上而是在RSA上。当然这只是相对而言，我们马上会看到RSA对直接攻击的抵御也是足够强的。
随便提一句，在PGP的未来版本中将提供密匙长度为112-bit的Triple DES加密算法作为用户选项。56-bit的标准DES密匙已经被证明是可以攻破的。
◎ RSA 的安全性问题
先看看RSA的基本原理，我们知道RSA的保密性基于一个数学假设：对一个很大的合数进行质因数分解是不可能的。RSA用到的是两个非常大的质数的乘积，用目前的计算机水平是无法分解的。但是这说明不了什么，没有“证明”RSA的安全性。这既不说明分解这个大数是攻击RSA唯一的（或者说是最佳的）途径，也不能证明这种分解真的那么困难。
RSA有可能存在一些密码学方面的缺陷，随着数论的发展也许会找到一种耗时以多项式方式增长的分解算法。不过目前这还只是展望，甚至连发展的方向都还没有找到。有三种事物的发展会威胁到RSA的安全性：分解技术、计算机能力的提高和计算机造价的降低。特别是第一条对RSA的威胁最大，因为只要大数分解的问题不解决，做乘法总是比分解因数快得多，计算机能力强大了尽可以加长密匙来防御，因为那时加密也会快得多的。
RSA的密匙生成步骤可以分为七步：
－ 找到两个大质数 p,q
－ 做乘法 n=p*q
－ 选择一个数 e，满足 e<n 且与 (p-1)*(q-1) 互质
－ 计算 d=e^-1 mod [(p-1)(q-1)]
－ e 就是公开指数，d 是私密指数
－ 公匙就是(n,e)，私匙是(n,d)
－ p 和 q 应该被销毁掉（PGP为了用中国的同余理论加快加密运算保留了p和q，
不过它们是用IDEA加密过再存放的）
加密算法是这样的，把明文分成比 n 小的数据块用公开指数作乘方取模运算：
c=m^e mod n （m是明文块(message)，c是密文块(cipher)）
解密过程正相反，把密文数据块用私密指数作乘方取模运算：
m=c^d mod n
攻击者有公匙，就是 e 和 n ，他想获得私匙，换句话就是 d 。对 n 进行因数分解来获得 p,q 从而算出 d 是最好的RSA攻击方法，直接穷举 d 或 推断 (p-1)(q-1) 都要慢许多。下面是几种因数分解的算法：
－ 试探除法：最老也是最笨的方法，穷举所有小于 sqrt(n) 的质数，耗时以指数率增长。
－ 二次筛法(QS)：对 10^110 以内的数是最快的算法。
－ MPQS：QS的改进版本，要快一些。
－ 分区筛法(NFS)：目前对大于10^110的数是最快的算法。曾被用来成功地分解过第九费马数。
这些算法代表了人们对大数分解（也就是对RSA攻击）的探索历程。最好的算法具有超多项式率（次指数率）的时间复杂度，NFS具有最接近于多项式率的表现。
大数分解仍然是困难的，可是随着数论和计算能力的发展，它变得容易了。1977年，Ron Rivest 说过分解一个125位的数需要花费 4*10^13 年。在 1994 年 RSA129 被分解了，花费了 5000 MIPS·年 的机时，是利用 internet 上一些计算机的空闲CPU周期一共花了8个月完成的。1995年，Blacknet密匙被分解，用了几十台工作站和一台MarPar，共用 400 MIPS·年，历时3个月。随着时间的推移，可能被分解的密匙长度还会增加。
下面的表格是常用的几种PGP密匙长度与它对应的NFS分解算法耗费的MIPS·年数。
密匙长 用NFS来分解的 MIPS·年 数
-----------------------------------------------------------------
512 30,000
768 200,000,000
1024 300,000,000,000
2048 300,000,000,000,000,000,000
下面一张表示用直接攻击方法耗时相当的对称式与非对称式加密对应密匙长度。
对称式 非对称式
------------------------------------------------------------------
56-bits 384-bits
64-bits 512-bits
80-bits 768-bits
112-bits 1792-bits
128-bits 2304-bits
分解过Blacknet密匙的四个人说过：“目前几乎可以肯定，拥有合适资源的组织可以破译512-bits的密匙。”这并不意味着有这么个组织认为值得动用如此之大的计算能力去破译别人的信息。话虽这么说，知道自己所用的加密体系可能会被攻破每个人都不会心安理得的。专家的建议是使用加密体系实现所提供的最大码长。如果哪一种实现不能提供足够的码长，最好不要用它。
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 一定是合数。
