pgp的安全问题分析.txt

当今

发信人: far (白开水), 信区: Security 
标  题: PGP的安全问题分析 
发信站: 武汉白云黄鹤站 (Wed Sep 16 16:48:00 1998) , 站内信件 
  
******清华的星一将其从英文翻译成中文，真是我辈之幸也,Thank you,loking!***** 
  
*************************************************************************** 
Subject: PGP 的安全性(转寄) 
X-Forwarded-By: highway (highway) 
X-Disclaimer: BBS 水木清华站 对本信内容恕不负责。 
Precedence: junk 
Status: RO 
X-Status: 
  
发信人: loking (星一), 信区: Security 
标  题: PGP 的安全性 
发信站: BBS 水木清华站 (Fri Apr 18 12:01:16 1997) 
  
-----BEGIN PGP SIGNED MESSAGE----- 
  
                              PGP的安全性 
  
                       by Loking  01/23/1997 
  
*************************************************************************** 
  
                            ■内容提要■ 
  
         ◎ 前言 
         ◎ 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的密匙。”这并不意味着有这么个组织认为值得动用如此之大的计算能 
  
力去破译别人的信息。话虽这么说，知道自己所用的加密体系可能会被攻破每个人都不