發(fā)信人: far (白開水), 信區(qū): Security 

標  題: PGP的安全問題分析 

發(fā)信站: 武漢白云黃鶴站 (Wed Sep 16 16:48:00 1998) , 站內(nèi)信件 

  

******清華的星一將其從英文翻譯成中文，真是我輩之幸也,Thank you,loking!***** 

  

*************************************************************************** 

Subject: PGP 的安全性(轉(zhuǎn)寄) 

X-Forwarded-By: highway (highway) 

X-Disclaimer: BBS 水木清華站 對本信內(nèi)容恕不負責。 

Precedence: junk 

Status: RO 

X-Status: 

  

發(fā)信人: loking (星一), 信區(qū): Security 

標  題: PGP 的安全性 

發(fā)信站: BBS 水木清華站 (Fri Apr 18 12:01:16 1997) 

  

-----BEGIN PGP SIGNED MESSAGE----- 

  

                              PGP的安全性 

  

                       by Loking  01/23/1997 

  

*************************************************************************** 

  

                            ■內(nèi)容提要■ 

  

         ◎ 前言 

         ◎ IDEA 的安全性問題 

         ◎ RSA 的安全性問題 

             ● 選擇密文攻擊 

             ● 過小的加密指數(shù) e 

             ● RSA的計時攻擊法 

             ● 其他對RSA的攻擊法 

         ◎ MD5 的安全性問題 

             ● 對MD5的普通直接攻擊 

             ● 對MD5的生日攻擊 

             ● 其他對MD5的攻擊 

             ● 口令長度和信息論 

         ◎ 隨機數(shù)的安全性問題 

             ● ANSI X9.17 PRNG 

             ● 用戶擊鍵引入隨機性 

             ● X9.17 用MD5進行預洗 

             ● randseed.bin 的后洗操作 

         ◎ PGP的密匙和口令的安全性問題 

         ◎ 沒有完全刪除的文件 

         ◎ 物理安全性 

         ◎ 多用戶系統(tǒng)下的泄密 

         ◎ PGP的時間標戳可靠性 

         ◎ 流量分析 

         ◎ 現(xiàn)實的PGP攻擊 

            被動攻擊： 

             ● 擊鍵窺探 

             ● 電磁泄露窺探 

             ● 內(nèi)存空間窺探 

             ● 磁盤緩存窺探 

             ● 報文嗅探 

            主動攻擊： 

             ● 特洛伊木馬 

             ● 篡改PGP代碼 

         ◎ 結語 

  

************************************************************************** 

  

    這可能是個最難寫的題目了，PGP本身就是一個數(shù)據(jù)安全產(chǎn)品，它會有什么安全 

  

性問題呢？PGP的作者 Phil Zimmermann 在PGP文檔中說到：“沒有哪個數(shù)據(jù)安全 

  

系統(tǒng)是牢不可破的?！盤GP也不例外。我們研究它的安全漏洞就是為了讓用戶知道 

  

哪些事會降低PGP的安全性，以及如何避免它們。下面是這些漏洞： 

  

    口令或私匙的泄密、公匙被篡改、你刪除的文件被人恢復、病毒和特洛伊木馬、 

  

物理安全受到侵犯（物理安全指計算機等物理資源的安全）、電磁泄露、暴露在多用 

  

戶系統(tǒng)中、網(wǎng)絡數(shù)據(jù)流分析，甚至會有可能被直接從密碼學分析的角度被解密（這當 

  

然是可能性最小的了）。 

  

    我們先分別看看PGP加密體系的四個關鍵部分的安全性問題。PGP是個雜合算法， 

  

所謂“雜合”體現(xiàn)在它包含：一個對稱加密算法（IDEA）、一個非對稱加密算法 

  

（RSA）、一個單向散列算法（MD5）以及一個隨機數(shù)產(chǎn)生器（從用戶擊鍵頻率產(chǎn)生偽 

  

隨機數(shù)序列的種子）。每種算法都是PGP不可分割的組成部分，對它們各有不同的攻擊 

  

方式。 

  

◎ IDEA 的安全性問題 

  

    IDEA是PGP密文實際上的加密算法，對于采用直接攻擊法的解密者來說，IDEA是 

  

PGP密文的第一道防線。 

  

    關于IDEA的原理請參見《PGP簡介》，在這里我主要談談與安全性有關的部分。 

  

IDEA，一種由 Lai 和 Massey 在 1992 年完成的對64bit大小的數(shù)據(jù)塊的傳統(tǒng)加密算法。 

  

IDEA是 International Data Encryption Algorithm 的縮寫。它基于“相異代數(shù)群上的 

  

混合運算”設計思想，它比DES在軟件實現(xiàn)上快得多，和DES一樣，它也支持“反饋加密 

  

（CFB）”和“鏈式加密（CBC）”兩種模式，在PGP中采用IDEA的64-bits CFB模式。 

  

IDEA比同時代的算法象：FEAL, REDOC-II, LOKI, Snefru 和 Khafre都要堅固，而且最 

  

近的證據(jù)表明即使是在DES上取得巨大成功的 Biham 和 Shamir 的微分密碼分析法對IDEA 

  

也無能為力。Biham 和 Shamir 曾對IDEA的弱點作過專門分析，但他們沒有成功。直到 

  

目前沒有任何關于IDEA的密碼學分析攻擊法的成果發(fā)表，據(jù)目前我接觸到的文檔中談到 

  

無論是NSA還是hacker們都還沒有辦法對IDEA進行密碼學分析，因此對IDEA的攻擊方法就 

  

只有“直接攻擊”或者說是“密匙窮舉”一種了。 

  

    那么對IDEA的直接攻擊難度如何呢？我們知道IDEA的密匙空間（密匙長度）是128 

  

位，用十進制表示所有可能的密匙個數(shù)將是一個天文數(shù)字： 

  

          340,282,366,920,938,463,463,374,607,431,768,211,456. 

  

    為了試探出一個特定的密匙，平均要試探一半上面的可能性。即使你用了十億臺每 

  

秒鐘能夠試探十億個密匙的計算機，所需的時間也比目前所知的宇宙的年齡要長，而即 

  

使是在當代制造每秒試探十億個密匙的計算機還是不可能的。因此對IDEA進行明文攻擊 

  

也是不可能的，更何況從PGP的原理看一個IDEA的密匙失密只會泄露一次加密的信息，對 

  

用戶最重要的密匙——RSA密匙對的保密性沒有什么影響。 

  

    那么看來IDEA是沒有什么問題了，因為你既不能從算法中找到漏洞又沒法明文攻擊 

  

實際上呢？漏洞還是有的，大家知道 Netscape 的安全性風波吧，就是因為忽視了密匙 

  

隨機生成的問題，Netscape的隨機密匙生成算法生成的密匙很有“規(guī)律”，而且遠遠沒 

  

有均布到整個密匙空間去，所以盡管Netscape的美國版采用128bits的密匙，還是被用 

  

很小的機時代價破掉了。那么PGP是不是也有這個毛病呢？我將在下面談到隨機數(shù)生成 

  

時再詳細說，這里提到它是為了說明PGP各個部分之間的依存關系。 

  

    當有人發(fā)現(xiàn)PGP實際上不是一種“純粹的”RSA加密算法時，他們擔心由于加密鏈中 

  

IDEA的弱點而被攻破。實際上這是由于一種誤解：他們認為公匙加密生來就比傳統(tǒng)加密 

  

安全得多。實際上密碼分析專家計算過，窮舉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密匙已經(jīng)被證明是可以攻破的。 

  

◎ RSA 的安全性問題 

  

    先看看RSA的基本原理，我們知道RSA的保密性基于一個數(shù)學假設：對一個很大的合 

  

數(shù)進行質(zhì)因數(shù)分解是不可能的。RSA用到的是兩個非常大的質(zhì)數(shù)的乘積，用目前的計算機 

  

水平是無法分解的。但是這說明不了什么，沒有“證明”RSA的安全性。這既不說明分解 

  

這個大數(shù)是攻擊RSA唯一的（或者說是最佳的）途徑，也不能證明這種分解真的那么困難。 

  

RSA有可能存在一些密碼學方面的缺陷，隨著數(shù)論的發(fā)展也許會找到一種耗時以多項式方 

  

式增長的分解算法。不過目前這還只是展望，甚至連發(fā)展的方向都還沒有找到。有三種 

  

事物的發(fā)展會威脅到RSA的安全性：分解技術、計算機能力的提高和計算機造價的降低。 

  

特別是第一條對RSA的威脅最大，因為只要大數(shù)分解的問題不解決，做乘法總是比分解因 

  

數(shù)快得多，計算機能力強大了盡可以加長密匙來防御，因為那時加密也會快得多的。 

  

    RSA的密匙生成步驟可以分為七步： 

  

    － 找到兩個大質(zhì)數(shù) p,q 

  

    － 做乘法 n=p*q 

  

    － 選擇一個數(shù) e，滿足 e<n 且與 (p-1)*(q-1) 互質(zhì) 

  

    － 計算 d=e^-1 mod [(p-1)(q-1)] 

  

    － e 就是公開指數(shù)，d 是私密指數(shù) 

  

    － 公匙就是(n,e)，私匙是(n,d) 

  

    － p 和 q 應該被銷毀掉（PGP為了用中國的同余理論加快加密運算保留了p和q， 

       不過它們是用IDEA加密過再存放的） 

  

    加密算法是這樣的，把明文分成比 n 小的數(shù)據(jù)塊用公開指數(shù)作乘方取模運算： 

  

            c=m^e mod n       （m是明文塊(message)，c是密文塊(cipher)） 

  

    解密過程正相反，把密文數(shù)據(jù)塊用私密指數(shù)作乘方取模運算： 

  

            m=c^d mod n 

  

    攻擊者有公匙，就是 e 和 n ，他想獲得私匙，換句話就是 d 。對 n 進行因數(shù)分 

  

解來獲得 p,q 從而算出 d 是最好的RSA攻擊方法，直接窮舉 d 或 推斷 (p-1)(q-1) 都 

  

要慢許多。下面是幾種因數(shù)分解的算法： 

  

    － 試探除法：最老也是最笨的方法，窮舉所有小于 sqrt(n) 的質(zhì)數(shù)，耗時以指數(shù) 

                 率增長。 

  

    － 二次篩法(QS)：對 10^110 以內(nèi)的數(shù)是最快的算法。 

  

    － MPQS：QS的改進版本，要快一些。 

  

    － 分區(qū)篩法(NFS)：目前對大于 10^110 的數(shù)是最快的算法。曾被用來成功地分解 

  

                 過第九費馬數(shù)。 

  

    這些算法代表了人們對大數(shù)分解（也就是對RSA攻擊）的探索歷程。最好的算法具有 

  

超多項式率（次指數(shù)率）的時間復雜度，NFS具有最接近于多項式率的表現(xiàn)。 

  

    大數(shù)分解仍然是困難的，可是隨著數(shù)論和計算能力的發(fā)展，它變得容易了。1977年， 

  

Ron Rivest 說過分解一個125位的數(shù)需要花費 4*10^13 年。在 1994 年 RSA129 被分解 

  

了，花費了 5000 MIPS·年 的機時，是利用 internet 上一些計算機的空閑CPU周期一 

  

共花了8個月完成的。1995年，Blacknet密匙被分解，用了幾十臺工作站和一臺MarPar， 

  

共用 400 MIPS·年，歷時3個月。隨著時間的推移，可能被分解的密匙長度還會增加。 

  

  下面的表格是常用的幾種PGP密匙長度與它對應的NFS分解算法耗費的MIPS·年數(shù)。 

  

               密匙長                   用NFS來分解的 MIPS·年 數(shù) 

   ----------------------------------------------------------------- 

                512                     30,000 

                768                     200,000,000 

                1024                    300,000,000,000 

                2048                    300,000,000,000,000,000,000 

  

  下面一張表示用直接攻擊方法耗時相當?shù)膶ΨQ式與非對稱式加密對應密匙長度。 

  

                對稱式                          非對稱式 

        ------------------------------------------------------------------ 

                56-bits                         384-bits 

                64-bits                         512-bits 

                80-bits                         768-bits 

                112-bits                        1792-bits 

                128-bits                        2304-bits 

  

    分解過Blacknet密匙的四個人說過：“目前幾乎可以肯定，擁有合適資源的組織可 

  

以破譯512-bits的密匙。”這并不意味著有這么個組織認為值得動用如此之大的計算能 

  

力去破譯別人的信息。話雖這么說，知道自己所用的加密體系可能會被攻破每個人都不