彩神彩票

MD5性能報告

        組織：中國互動出版網（http://www.china-pub.com/）

        RFC文檔中文翻譯計劃（http://www.china-pub.com/compters/emook/aboutemook.htm）

        E-mail：ouyang@china-pub.com

        譯者：（）

        譯文發布時間：2001-11-7

        版權：本中文翻譯文檔版權歸中國互動出版網所有。可以用於非商業用途自由轉載，但必須保留本文檔的翻譯及版權信息。

        Network Working Group J. Touch

        Request for Comments: 1810 ISI

        Category: Informational June 1995

        MD5性能報告

        （RFC1810——Report on MD5 Performance）

        本文的地位

        本文並非指定一個Internet標準，而是向互聯網提供信息，本文可以任意傳播，不受限製。

        摘要

        MD5是一個認證算法，它被提議作為IPv6的默認的認證算法，在可能的情況下，MD5能對包括報頭的整個數據包進行操作。本RFC介紹了MD5在軟件和硬件上的執行速度以及它是否支持當前的可用IP帶寬。MD5可在現有的硬件技術下以256 Mbps的速度運行，在現有的軟件技術下以87 Mbps的速度運行。此速率不能支持當前的IP速率（如：在ATM 下100 MbpsTCP 及 130 Mbps UDP）。如果MD5在現有的技術下不支持現有的網絡帶寬，那麽它就跟不上將來網絡速度的提高。本RFC目的是提醒IP社區有關MD5的性能限製，並提議在高速IP應用中采用MD5的替代物。

        1、緒論

        MD5是一個認證算法，在IPv6[1]中它被提議作為默認的認證算法。RFC 1321中描述了MD5算法和一個參考應用程序。在可能的情況下，MD5能對包括報頭的整個數據包進行操作，本RFC介紹了MD5在軟件和硬件上的執行速度以及它是否支持當前的可用IP帶寬。本RFC假設在IPv6中高速進行普通的安全和求校驗和。IPv6沒有求校驗和（IPv4則有），但建議使用整個數據包（包括可變不分置零的報頭）的認證摘要，本RFC特別講述了這種認證機製的性能。

        2、測量

        MD5的性能是標準的，RFC [3]的代碼是MD5參考應用程序的優化版本，它在匿名FTP [7]中可以用到。下麵是"md5 -t"性能測試結果，為防止數據分組的隱藏而作了修改。

        87 Mbps DEC Alpha (190 Mhz)

        33 Mbps HP 9000/720

        48 Mbps IBM RS/6000 7006 (PPC 601 @80 Mhz)

        31 Mbps Intel i486/66 NetBSD

        44 Mbps Intel Pentium/90 NeXTStep

        52 Mbps SGI/IP-20 IRIX 5.2

        37 Mbps Sun SPARC-10/51, SPARC-20/50 SunOS 4.1.3

        57 Mbps Sun SPARC-20/71 SunOS 4.1.3

        這些速率跟不上現有的IP帶寬，如在Sun SPARC-20/71的Fore SBA-200 ATM網絡主機下100Mbps TCP 和130 Mbps UDP。

        據報道對DEC Alpha (190 Mhz)速度可達到100 Mbps，這些值反應了數據在一級緩存中的速度，此時性能的測量同在內存,二級緩存還是一級緩存中區別不明顯，它更依賴於IP的性能。

        3、MD5算法分析

        MD5算法是一種“鏈分組”散列算法，第一個分組用一個初始種子進行Hash運算，得到一個散列值，然後將此散列值加上原始的種子，作為下一個分組的種子，當計算最後一個分組時，它的“下一個種子”就成為了整個數據串的散列值。因此，一個分組的種子就依靠上一個分組產生的散列值和上一個分組的種子，所以，各個分組是不能並列計算的。

        每一個16字（64位）的分組經過64個步驟進行哈希運算，使用一個四個字中間散列值，並在最後拆銷掉中間散列值，64個步驟分為16組四個步驟，每一步用到一個中間散列值，本RFC用到了下麵的符號（引自RFC-1321 [3]）：

        A,B,C,D 中間散列字

        X[i] 輸入數據分組

        T[i] sine 函數查找表

        << i 循環移動i位

        F 3個參數的邏輯函數

        X，I以及<<在每一步中都是故定的，在此處被忽略了，另外還有四個邏輯函數也被忽略了，每個組（4步）如下所示：

        A = B + ((A + F(B,C,D) + X[i] + T[i]) << i)

        D = A + ((D + F(A,B,C) + X[i] + T[i]) << i)

        C = D + ((C + F(D,A,B) + X[i] + T[i]) << i)

        B = C + ((B + F(C,D,A) + X[i] + T[i]) << i)

        注意這有著下麵的一般形式，由於函數f的複雜性這些等式不能轉變成更小的集合。

        A = f(D); B = f(A); C = f(B); D = f(C)

        每一步包括兩個查找表，一個循環和一個三參數的邏輯操作以及四個加法，最好的並行化可能使F(x,y,z)停留到最後一步，一直等到前一步的結果到來，結果樹如下所示：

        (t0) B* C C D X T

        | | | | | |

        | | | | | |

        \/ \/ \ /

        t1 op op A + X T

        \ / \ / | |

        \ / \ / | |

        \/ \/ \ /

        t2 op + (t0) B* C C D A +

        \ / | | | | \ /

        \ / \ | | / \ /

        \ / \\// \/

        t3 + t1 op +

        | \ /

        | \ /

        | \ /

        t4 << B* t2 + B*

        \ / \ /

        \ / << /

        \ / \ /

        t5 + t3 +

        | |

        | |

        | |

        A** A**

        二叉樹 優化的硬件樹

        此表假設每一步操作占用一個單位時間，以上樹展示了依賴於上一步的項目(如B*)，也展示了下一步操作需要用到的項目（如：A**），二叉樹不能折疊，但是優化的硬件樹則可以。

        每個字的輸入對應四步操作，算法的整個耗時依賴於我們在正處理的一個字輸入的帶寬下處理這4步操作的速度。

        二叉樹中每步算法需要5個單位時間並可進行3路並行處理（在t1時刻），在軟件方麵，也就是每字輸入用到5 * 4 = 20個指令，一台M MIPS的計算機能支持M/20 * 32 Mbps的帶寬，也即每秒等於1.6x的MIP速率。因此，一台100 MIPS的機器能支持160Mbp的位流。

        並行軟件速率Mbps = 1.6 * MIPS

        這是假設寄存器讀寫整個的和計算重疊的，沒有任何並行操作情況下，每步包括8個操作，每個字包括4步，所以每個對字的操作包括32步，也就是速率Mbps等同於MIPS速率：

        連續軟件速率Mbps=MIPS 速率

        用SpecInt92作為MIPS的估計值和固定速率進行比較：

        Spec- Predicted MD5

        Int92 Upper-Bound Measured Machine

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

        122 122-195 87 Mbps DEC Alpha (190 Mhz)

        48 48- 77 33 Mbps HP 9000/720

        88 88-141 48 Mbps IBM RS/6000 7006 (PPC 601 @80 Mhz)

        32 32- 51 31 Mbps Intel i486/33 NetBSD

        90 90-144 44 Mbps Intel Pentium/90 NeXTStep

        90 90-144 52 Mbps SGI/IP-20 IRIX 5.2

        65 65-104 37 Mbps Sun SPARC-10/51 SunOS 4.1.3

        126 126-202 57 Mbps Sun SPARC-20/71 SunOS 4.1.3

        硬件速率每一步需要3個單位時間，也就是每個字的輸入需要3 * 4 = 12倍的單位時間。一個操作花費N 納秒（十億分之一秒）的硬件能支持32/12/N bps,也即2/3N bps的數據帶寬。

        硬件速率 Mbps = 8/3N * 1,000

        對CMOS來說，一個操作（32位加法，包括寄存器更新和存儲）花費大約5.2 ns時間（加法2.6秒,鎖存2.6秒），高度並行應用需要6個時鍾，速度也就是對每32位的字操作需要31.2納秒，或256 Mbps，此速率跟不上現有的硬件速率，現有的硬件鏈接速率已超過622Mbps（ATM）。

        比較而言，IPv4使用了Internet Checksum [5]，這種求校驗和操作在32位寬的單元上進行時，在現有的低價PLD（可編程邏輯電路）上速度超過1Gbps，此校驗和可以並行操作，計算部分和以及降低值。

        4、一個解決方案

        有幾種方法可以提高IPv6的認證機製，一種方法是靠稍微改變算法來提高MD5硬件的性能，另一種方法是推薦一種新的替代算法。本RFC簡短的討論一下為得到高速的硬件應用對MD5的修改，速度是MD5算法3.5倍的替代算法在其它地方將討論[6]。

        MD5使用分組的連接來精確確保每個分組的順序，分組連接還可以防止任意的並行操作，這可能對用戶和欺騙者都有用，MD5稍微改變一下就可以適應高帶寬數據率。要求先有一個預先確定的可通過獨立的種子處理的有限數量的分組，這樣第I個分組就是第"I mod K"個鏈的一部分，結果K就計算自己的摘要，形成一個能被MD5通過一個簡單分組算法編碼的消息。這種思想是由作者和RSA的Burt Kaliski 獨立提出的。目的是為了支持有限的並行處理，以在當前的處理速度情況下提供充足的帶寬，而不給欺騙者提供任何能力。還需要更進一步分析以確定它確實提高了安全水平。

        對於當前的技術和網絡帶寬，4路並行處理鏈就能滿足要求了，16路鏈將更好。在CMOS硬件方麵，4路鏈將支持1Gbps的網絡帶寬，為產生完整的分組摘要（每個摘要4個字，每個分組16個字），必須采用4的倍數的並行鏈，這種改變能夠達到MD5目的，不會影響當前的MD5算法的執行。

        5、安全考慮

        全文提供了一種IPv6的安全機製，MD5建議作為IPv6通信的默認認證機製，本RFC特別介紹了象MD5這樣的安全機製使用現有的硬件不支持高速帶寬，這會影響到本身的發展，最終會危及到它要維護的係統安全。

        IPv6必備的文獻強調IPv6應用不應該如IPv4那樣影響到性能，即使能使IPv6功能增加，IPv6的“必需選項”成分也應該包含到同一的標準中。MD5性能受到影響，所以也應重新考慮它作為IPv6的默認認證算法。

        使用MD5作為默認認證算法可能會影響寬帶係統的安全性，因為使用它會引起性能的，所以應取消它作為IPv6的默認認證算法。總之，此算法可能會被完全取消掉。

        IPv6中在開端處就可得到替代的認證機製對在高性能的係統中認證的使用是很重要的。這可能需要多種“必需”鑒定機製的規範，一種是速度慢，但是很可信，一種是速度快但是不可信的成分。

        6、結論

        MD5不能在現有的硬件速度超過256Mbps或軟件速度超過86Mbps的技術上執行，MD5被提議作為IPv6的默認認證機製，IPv6是一種支持現有網絡技術的協議，它的UDP速率是130Mbps。

        總之，MD5以現有的速率不能支持現有網絡的IP鑒定即使MD5在將來隨著技術的提高能夠支持更高的帶寬，但是網絡也同樣在發展。如果MD5不能在現有的技術下支持現有網絡的帶寬那麽將來它就跟不上網絡速度的提高。本RFC提議為了使MD5在現有技術（CMOS硬件）下支持現有網絡速率（1Gbps）對它進行了改變到能支持16路鏈分組，本RFC進一步提議在高速網絡上使用MD5的替代算法。

        7、致謝

        作者在此向BBN的Steve Kent ，RSA的 Burt Kaliski，Victor Chang ，SteveBurnett ，NRL的Ran Atkinson， ISI HPCC的 Division表示感謝，他們對本文的內容作了評論，Burt獨立提出了本文中的分組平行操作的建議。

        8、參考文獻

        [1] Atkinson, R., "IPv6 Authentication Header", Work in Progress,Naval Research Lab, February 1995.

        [2] DiMarco, J., "Spec Benchmark table, V. 4.12",.

        [3] Rivest, R., "The MD5 Message-Digest Algorithm", RFC1321, MIT LCS& RSA Data Security,Inc., April 1992.

        [4] Partridge, C., and F. Kastenholz, "Technical Criteria forChoosing IP The Next Generation (IPng)", RFC 1726, BBN Systems and Technologies, FTP Software, December 1994.

        [5] Postel, J., "Internet Protocol - DARPA Internet Program Protocol Specification," STD 5, RFC 791, USC/Information Sciences Institute, September 1981.

        [6] Touch, J., "Performance Analysis fo MD5," to appear in ACM Sigcomm '95, Boston.

        [7] Touch, J., Optimized MD5 software, .

        作者地址

        Joe Touch

        Information Sciences Institute

        University of Southern California

        4676 Admiralty Way

        Marina del Rey, CA 90292-6695

        USA

        phones: +1 310-822-1511 x151

        Fax: +1 310-823-6714

        URL: ftp://ftp.isi.edu/pub/hpcc-papers/touch

        EMail: touch@isi.edu

        RFC1810——Report on MD5 Performance MD5性能報告

        2

        RFC文檔中文翻譯計劃