最近更新: 2007-08-06

在 C 程式中使用 MD5 library 及其應用

簡單地說, MD5 是一種單向雜湊(hashing)演算法,可將你所給予的任何長度字串,藉由 MD5 雜湊演算得出一個長度為 128 位元 (術語稱之為 "digest code")的計算結果。後述以鍵值稱呼 digest code。MD5 演算法,是由 RSA Data Security, Inc 公司所提出的。演算原理參閱 MD5 - Wikipedia

舉例而言,將 "ROCK" 這個字串使用 MD5 演算,就會得到一個 128 位元的鍵值。用字串表示時,是把 128 位元的計算結果轉成十六進位碼形式的字串,故此字串需要32個字元空間 (即256位元)。以字串型式表示如下:

MD5 ("ROCK") = afeb717aa2a101f7f64840e0be38c171

MD5 的其他說明條列於下:

  1. 固定的字串內容必定會得出一個固定的鍵值,而非每次都算出不同的。
  2. 這是一個單向的雜湊演算,意味著,它雖可每次都將同樣的字串內容,算 出同樣的鍵值,但它無法從鍵值反推算出原本的字串內容。
  3. 不同字串內容所演算出來的鍵值,有可能相同(此稱"碰撞)。但根據統計,重覆的機率小於百萬分之一。以重覆率來說,是相當好的演算法。
  4. 演算速度快,對硬體的要求很低。
  5. 它可以演算任意長度的字串內容,而且能得出固定長度的鍵值。
  6. 就算字串內容只相差一個字,它也能算出完全不同的鍵值。
  7. 鍵值長達 128 位元,而且可接受任何長度的字串,就密碼的安全性來講,比過去常用的 DES 編碼法還好。DES 編碼法只能接受 8 個字元長度的字串,產生的鍵值只有56位元。

就最後兩項,舉個例子來驗證:

MD5 ("ROCK") = afeb717aa2a101f7f64840e0be38c171
MD5 ("RACK") = 1ece4bad0efe8b897c6e7f8bd101759f
MD5 ("ROCKY") = 6cd910740cbbbbd0f55238a93fba157d
MD5 ("Rock'S saying") = 7dca0df0dfa7f76b652e53daa4852640

Make MD5 library

目前的 Linux/FreeBSD 系統中,大多已安裝 MD5 library 。若是在 Windows 平台上使用 MinGW32 的使用者,可以下載此版本: md5.tar.gz 並安裝。此版本屬於 Public Domain (公眾軟體)。解壓後得源碼, make 後可得 libmd5.a 之靜態函數庫(Archive) 。將 md5.h 複製到 MinGW\include 目錄中, libmd5.a 複製到 MinGW\lib 目錄中,即完成安裝動作。

C:\User\fbtip\others\md5> make
gcc -O2 -c md5.c
ar ruv libmd5.a md5.o
ar: creating libmd5.a
a - md5.o
gcc -O2 -o md5sum md5sum.c md5.o
md5sum.c: In function `main':
md5sum.c:42: warning: return type of 'main' is not `int'
gcc -O2 -o md5digest md5digest.c md5.o

除了 libmd5.a 此函數庫文件,還會產生兩個工具: md5sum, md5digest 。md5sum 可以計算指定的檔案內容之鍵值;md5digest 可計算指定字串之鍵值。如果你是要計算檔案內容的鍵值,只要在指令 md5sum 後直接加上檔案名稱做為參數即可。你可以用它檢查兩個同名檔案是否相同。有些 FTP 站台會提供每個檔案的 md5 檢核文件,供使用者在下載後檢查下載檔的內容是否正確。

指令 md5digest 後緊跟著字串內容,可得鍵值。本文上述所舉的幾個例子,都是用這個工具算的。

在程式中呼叫 MD5

你可以閱讀上述 md5sum 和 md5digest 工具的源碼。此外,我以前維護學校的 Firebird BBS 系統時,寫了一套 library ,其中亦包含了 MD5 library 的使用函數。源碼可於此下載: bbslib2 sources tarball。其中的 strexp/md5ap.c 包含了一組 MD5 處理函數,將原本 MD5 library 中的演算函數包裝在一起,以便使用。源碼不另行列出。

基本上只要引入 md5.h 即可。在編譯程式時,則須告知 linker 將 libmd5 連結進來, 通常是為 cc 或 gcc 加上參數 -lmd5 。

應用一:儲存密碼

這是 MD5 最常被使用的用途。首先,我們將新使用者所輸入的密碼字串內容 (術語稱為明碼,也就是編碼前的密碼) ,傳給 MD5 演算函數算出暗碼 (編碼後的密碼) 。暗碼的產生,可以使用前述 md5ap.c 中的 md5()。之後我們將該暗碼,連同使用者 ID 及其他資料一併存入資料庫中。例如使用者帳號為 rock ,密碼為 iloverock ,儲存在資料庫中的帳號資料格式及內容如下列,第二個欄位儲存的就是暗碼。

rock:85782f5e159d638811a7a8a7fa318754:Shih Yuncheng

稍後,當使用者欲再簽入時,先以使用者 ID 為鍵值,自資料庫中讀取帳號資料。再將使用者輸入的明碼,同樣地傳給 MD5 演算函數得出一結果。將此結果與帳號資料中的暗碼比對是否完全相符。

應用二:資料查核

這是 MD5 另一種常見的應用,一般用在網路檔案傳輸上或資料備份。當使用者下傳回檔案後,可用 md5sum (前述所說的那個 md5sum 工具) 去算出一個鍵值 (一般稱為 "check sum" 或 md5sum)。將此鍵值與檔案來源站台所提供的鍵值比對。如果相同,就可以證明使用者下傳的檔案和原始檔案是相同的,沒有在傳輸過程中遭修改。資料備份的檢核亦為同理。檔案在傳輸過程中遭修改的可能性有:

  1. 網路異常或雜訊干擾
  2. 病毒感染或遭植入木馬程式

使用這個方法就可以證明檔案沒有問題,遠比安裝網路防毒軟體方便。因為防毒軟體可能誤判,而且只能檢查檔案是否遭感染,卻無法檢查檔案內容是否正確無誤。而在電子郵件愈來愈普及之後,又沿生了一種 MD5 的應用,使用它來阻擋垃圾信件。大致做法是:

  1. 接收信件的同時,將信件的本文部份 (body) ,透過 MD5 去計算,例如使用 md5ap.c 中的 md5_filter() ,得到一個鍵值。不需要包含信件的標頭部份 (header)。
  2. 從信件鍵值資料庫中,搜尋此鍵值。找不到就跳到第三步,找到則跳到第四步。
  3. 未找到此鍵值,表示這信件的內容,是第一次接收到,將鍵值及計數值 (初值 1) 存入信件鍵值資料庫。再跳到第七步。
  4. 若找到了,表示這信件的內容,以前已經收過了。
  5. 接著檢查計數值是否超過上限 (這上限自定) ,如果超過了,我們就中止接收這封信,結束。
  6. 如果未超過上限,將計數值加一後,再存回信件鍵值資料庫。
  7. 將所接收到的信件內容,儲存起來,完成收信動作。

以虛擬碼表示如下:

open connect as fh

do {
  read line
  save mail header
} while end of mail header

do {
  read line
  md5 filter & save mail body
} while end of mail

final md5 filter and get a key

select key from mail-key database

if not found then
  store key and count value
else
  if the count not up then limit then
    inc count
    store key and count
  else
    deny this mail
    close connect
  end if
end if

store thie mail
close connect

由於透過網路傳遞的文件及檔案愈來愈多,我們也可以將上述方法用在文件的管理上,減少那些來自四面八方的重複檔案。

MD5的安全性

到目前為止,仍然是以碰撞法或稱暴力猜測法破解 MD5 加密的密碼。即隨意產生一組字串計算鍵值,賭鍵值相同的機率。

近年來,還有人預先將字典中的字彙先行計算出鍵值後建檔儲存,又謂 "Rainbow table"。俟取得對方系統中的密碼檔內容後,再反過來以鍵值查詢密碼。例如 md5encryption 網站所提供的線上工具,即為一例。各位可以本文中出現的例子試試。輸入 "rock" 的鍵值時,可成功反查出 "rock";輸入 "iloverock" 的鍵值時,則無法反查。此因 "rock" 是字典中的字彙,"iloverock" 則是隨意組合字彙。雖然不同的字串可能具有相同的鍵值 (此稱"碰撞"),但 "iloverock" 之鍵值找不到碰撞的其他字串內容,顯示 Rainbow table 尚未將 128位元所能涵蓋的全部鍵值來源建檔。

樂多舊網址: http://blog.roodo.com/rocksaying/archives/3873017.html

樂多舊回應
未留名 (#comment-14094083)
Mon, 06 Aug 2007 20:29:29 +0800
1. 把 MD5 和 DES 拿來比較蠻奇怪的,一個是雜湊,一個是加密,性質並不相同。
2. MD5 已經很不安全了,至少用 SHA-1 會是相對比較好的選擇。用一般電腦找 MD5 的碰撞已經非常快速,與密碼相關的工作採用 MD5 已非常不適合了。
HACGIS@gmail.com(tokimeki) (#comment-14101193)
Mon, 06 Aug 2007 22:20:20 +0800
MD5我很早就不用了~
http://freesf.tnc.edu.tw/modules/news/article.php?storyid=1389&com_id=1821&com_rootid=1813&com_mode=thread&

請注意,MD5仍然是不可逆的,但可以偽造,只要你拿的到MD5編碼後的字串。
未留名 (#comment-14104561)
Tue, 07 Aug 2007 00:15:55 +0800
MD5 的應用相當廣。雖然作為密碼系統已被證明不安全,但資料檢核的動作,MD5 還是勝任愉快,優於CRC32。

to wctang:
我一開頭就說 MD5 是單向雜湊演算法,沒說它跟 DES 編碼法一樣。但確實有很長一段時間, MD5 取代了 DES 做為系統密碼編碼算法。我記得大約在1997~2005年這段時間中,Linux/FreeBSD 系統預設採用 MD5 進行帳號密碼加密。

我在最後一段提到了。因為MD5確實是不可逆的,故目前只能用碰撞法/暴力法去猜。

事實上,目前常見的加密技術,幾乎都可用碰撞法/暴力法破解,差別僅在於次數多寡(即猜中時間)。在量子電腦相關書中提到,在量子電腦眼中,現階段所有密碼加密技術 (包含SHA-512) 都不安全。我們該慶幸量子電腦的發展還在原始階段。

最後,熟悉系統安全的管理者知道系統安全不是只靠一道密碼保護,還有其他關卡。例如保護密碼檔(.passwds) - 這就是為什麼 Linux 系統早期直接將密碼暗碼存在 .passwds 中,後來卻改到 .shadows 的原因;密碼輸入錯誤重試次數限制;防火牆限制;要求使用者使用不規則字元組合作為密碼等。
未留名 (#comment-14109433)
Tue, 07 Aug 2007 02:05:38 +0800
或許和作者的用詞習慣不同,通常 MD5, SHA1 之類的就是稱為雜湊,而不是加密,加密通常是指用 key(s) 把明文加密或密文還原的演算法。作者說"就密碼的安全性來講,比過去常用的 DES 編碼法還好"並不適合,這兩者無法比較安全性的。

當然所有的加密算法都可以用暴力法破解,所以用暴力法不算破解,而 MD5 是本身就有弱點,wikipedia 上的資料目前是用 notebook 一分鐘就可以找到碰撞,像密碼或其他原文沒特定格式的文件,用 MD5 來做為正確性驗證已是完全不安全的。當然用做為 checksum 防止傳輸錯誤還是適合的。
playercd8@hotmail.com(player) (#comment-14189659)
Fri, 10 Aug 2007 15:14:43 +0800
1.Mysql裡的password(), 好像也是預設用MD5去算的
2.MD5在一般應用上, 已經很好用了,MD5是雜湊演算, 而任何的雜湊必然會發生碰撞, 所以只是機率高低的問題

這裡有一份以前在用的 class CMD5, 敬請笑納
http://ez-templates.cvs.sourceforge.net/ez-templates/cpp/Class/HashKey/
當初中了MFC的餘毒, 所以常在class的命名上加 C
未留名 (#comment-14278117)
Tue, 21 Aug 2007 20:40:03 +0800
MD5 不能處理 "任意長度" 的字串,
只是它能處理的長度足夠目前的需要,
如果你有實作過它的 padding,
應該就知道是怎麼一回事.

To 一樓:
SHA/SHA1 也是半斤八兩,
真的要強調安全,
SHA256 才是基本需求.
未留名 (#comment-14283303)
Wed, 22 Aug 2007 13:48:58 +0800
那就請教樓上,MD5 長度上的限制是怎麼回事?

SHA-256, SHA-512 都是比較晚近才出現的選擇,一來比較不普遍,再者是不是真的就很安全也要經過時間考驗。當然目前對 SHA-1 的攻擊已越來越強,但如"和 MD5 比較"仍是較好的且普遍的選擇。
未留名 (#comment-14284957)
Wed, 22 Aug 2007 18:09:49 +0800
對不起我記錯了,
SHA-1 才有限制.

另外,
Schneier 的文章:

http://www.schneier.com/blog/archives/2005/02/sha1_broken.html

兩年前的事了...
未留名 (#comment-14284985)
Wed, 22 Aug 2007 18:16:25 +0800
補充一下,
MD5 在訊息長度大於 64 bits 整數能表示的情形下,
會使用低 64 bits 來表示.
(大多情形下足夠安全)

而 SHA-1 直接規範不能使用.
nba61222@yahoo.com.tw(CCWANG) (#comment-18171235)
Wed, 17 Dec 2008 11:15:29 +0800
請問版主:
1.解壓後得源碼, make 後可得 libmd5.a 之靜態函數庫(Archive) 。將 md5.h 複製到 MinGW\include 目錄中, libmd5.a 複製到 MinGW\lib 目錄中,即完成安裝動作。
這個要怎麼安裝呀??MAKE要怎麼使用??

2.基本上只要引入 md5.h 即可。在編譯程式時,則須告知 linker 將 libmd5 連結進來, 通常是為 cc 或 gcc 加上參數 -lmd5
在VC++中怎麼使用??
3Q~~版主~~程式初學者請大家幫忙!!