資訊與網路安全技術 第四章 雜湊與亂數演算法  上一頁      下一頁

 

4-5 破解雜湊函數

內容:

基本上,雜湊函數是將原來訊息打亂,得到另一個亂無章法的雜湊值,而且是越亂越好。很不幸的,我們發現大部分的傳輸訊息都有一定的格式,譬如,信件一開始就有 “Dear”,結束時又出現 “Your Best Regards”。或者資料檔案都有一定的格式,攻擊者既然知道了明文,就可以依照這些標準格式去修改內容,以達到相同的雜湊值。我們用一個例子來說明,假設春嬌希望約志明明天見面(See you tomorrow),寫好了信件,並建立了雜湊值(也許經過加密),她想應該很安全就交由世雄去發送;世雄原來就愛慕著春嬌,看了這封信當然很不高興,就利用他的資訊安全專長,找出 {See you yesterday}{See you upset}{don’t see you again} 等等,只要能符合相同的雜湊值即可,再將偽造信與春嬌簽署的簽署碼(加密的雜湊值)一起發送給志明,如此一來,就達到破壞他們之間的感情目的。接下來,我們來看看世雄到底用什麼技巧來攻擊雜湊演算法。

4-5-1 生日攻擊法

從數學的觀點來看,訊息經由雜湊演算法計算後,所產生的雜湊碼越長,則可能遺失的訊息就越少;如果採用較短的雜湊碼,可能遺失的訊息相對較多,不同訊息之間產生相同雜湊碼的機會也相對較大,這種觀念如同加密演算法,雜湊碼的位元數越長就越安全。攻擊者嘗試以不同的訊息來產生相同的雜湊碼,像是『暴力攻擊法』,但在雜湊演算法常稱為『生日攻擊法』(Birthday Attack;首先就『生日迷失』(Birthday Paradox的特性來觀察 [58]

『生日迷失』是機率的問題(這裡僅簡略說明,請參考 [136])。話說某位教授於課堂上向學生提出一個問題,問到需要多少位學生才能找出生日相同的機率大於 1/2。這個問題許多學生可能會利用一般機率的配對方式來計算,在 n 個學生之間的配對組合是 n(n-1)/2;而可能出現相同生日的機會是 1/365(一年 365 天);如果欲得到的機率是 1/2,則 n 的最小值應該不難算出。許多學生相繼算出n 值,其中幾乎都超過 100。然而正確答案只有 23,也就是說,只要在 23 位學生之中,發生在任意兩個學生是相同生日的機率就會超過 1/2。這種觀念換成雜湊演算法就是,在 n 的訊息當中,需要嘗試過多少種訊息才可以找出相同的雜湊碼?一般雜湊碼的長度皆以二進位的長度來度量,譬如,某一雜湊演算法所產生的雜湊碼為 64 個位元,可能出現的組合是 264 種雜湊碼,但依照生日迷失的計算,只要嘗試 232 個訊息,就可以找到相同的雜湊碼。

生日攻擊的構想是由 Yuval [136] 所提出,其攻擊策略如下:(假設雜湊碼為 64 個位元)

  • 攻擊者已得到一份經由簽署者簽署過的文件,簽署方式是明文後面加上已加密的雜湊值(使用簽署者的私有鑰匙)。

  • 攻擊者利用明文與已知的雜湊演算法,計算出原明文的雜湊值。

  • 接著,再依照該明文的格式修改其內容,譬如,保留原來空白鍵、使用較接近的文字,製造出其它偽造明文;並經過雜湊演算法計算出是否與原明文相同的雜湊值。

  • 攻擊者針對此明文產生 232 個不同的變形,一定可以找出相同雜湊值的偽造明文。

  • 攻擊者將偽造的明文與原來的簽署碼(原雜湊值經過加密或簽署的)結合起來,一併送出。

  • 接收者收到文件,利用簽署者的公開鑰匙驗證該簽署碼無誤之後,則判定該文件的確是由簽署者所發沒錯;如此一來,攻擊者便達到目的了。

簽署者沒有想到利用私有鑰匙簽署過的文件,還是會被攻擊者冒充,主要關鍵在於雜湊演算法的複雜度不夠,與加密演算法(或簽署演算法)的強度無關,所以64位元的雜湊碼仍然過於脆弱,唯有增加長度才可確保安全。

4-5-2 中途相遇攻擊法

『中途相遇攻擊法』(Meet-in-the-Middle Attack的先決條件是得到一份明文與發送者所簽署的數位簽章。一般來講,雜湊演算法都是公開的,攻擊者可依此計算出明文的雜湊值;接著,依照雜湊值的長度,將明文分割為若干個區塊(如圖 5-3 所示,容後介紹),再將偽造的明文區分為同樣大小的區塊,使用每一區塊所產生的雜湊值來比較,如果不相同,則改變偽造明文使其中間值相同,依此類推,便可找到相同雜湊碼的偽造文。其步驟如下:(假設雜湊值長度為64位元)

  • 根據已知的明文,產生雜湊值

  • 將明文(P)依照雜湊值的長度(64 個位元),區分為若干個區塊(P1, P2, …, Pn)。

  • 攻擊者製造另一個偽造文(Q,也依照 64 個位元的雜湊值長度,區分為若干個區塊(Q1, Q2, …, Qn)。

  • 將明文與偽造文的相對區塊,送給雜湊函數計算,如得到 H(Pj) = H(Qj),則接下一區塊;否則修改偽造文,使其達到目的(故稱為中途相遇攻擊法),最多在 232 個不同的 Qj 便可找到相同的雜湊值。搜尋完畢之後,再比較最後的雜湊值是否與原文的雜湊值相同。

  • 找出相同的雜湊值之後,將此偽造文連同原文傳送給接收端。

由上述的推演,無論使用何種加密演算法,還是會被破解掉;其中最主要關鍵在於攻擊者根本不用理會加密演算(或加密鑰匙),只要找出相同雜湊值,便可達到攻擊目的;根本解決之道,除了不斷加強雜湊演算法的複雜度之外,增加雜湊值的長度方能達到安全效果。

 

主講人:粘添壽博士

 

資訊與網路安全技術