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

 

第四章  雜湊與亂數演算法

 人可以利用獨一無二的『指紋』來證明自己的特徵;文件也可以利用雜湊碼來證實其唯一性,但雜湊值真的安全?不可以偽造嗎?

4-1 雜湊函數簡介

內容:

  • 4-1 雜湊函數簡介

  • 4-2 簡單的雜湊函數

所謂『雜湊函數』(Hash Function),是將不定長度訊息的輸入,演算成固定長度雜湊值的輸出,且所計算出來的雜湊值必須符合兩個主要條件:(1) 由雜湊值是無法反推出原來的訊息,(2) 雜湊值必須隨明文改變而改變。也就是說,不同明文所計算出來的雜湊值必須是不相同的,甚至僅改變明文中任何一個字元時,雜湊值的輸出也必須差異很大。由此可見,期望中的雜湊值就好像是一個無法冒充的識別碼,且每一份文件都有其特殊的雜湊值,且無法被偽造,故有『數位指紋』(Digital Fingerprint之稱。雜湊函數在資訊安全技術上所扮演的角色極為重要,應用範圍很廣泛。本章除了介紹一些標準化的雜湊演算法,也會探討其安全性。

雜湊函數的運算及參數表示如下:

訊息輸入:M

雜湊函數:H

雜湊值輸出:h = H(M)

        

我們期望輸出的雜湊值 h,必須隨輸入訊息 M 而改變,而且該值是無法仿冒的,如人類『指紋』功能一般。當然要達到這個功能,主要關鍵在於雜湊函數的複雜程度如何。一般雜湊函數必須具備下列功能:

  • 雜湊函數必須對任意長度的訊息輸入,產生固定長度的雜湊值輸出

  • 對於任意訊息 M,雜湊函數可以輕易的計算出 H(M),並且可經由硬體或軟體來實現。

  • 如果給予雜湊值 h,在計算上是無法找出原訊息 M,使其符合 h = H(M),此特性稱之為『單向雜湊』(One-way Hash

  • 對於一個訊息 M1,在計算上是無法找出另一個訊息 M2 (≠ M1),使得 H(M1) = H(M2)。也就是說,給定一個雜湊值(H(M1)),須無法找出另一個訊息(M2),使其所產生的雜湊值相同。

  • 就兩訊息 M1M2 而言,若他們的雜湊值相等,亦即 H(M1) = H(M2),則 M1 M2 兩訊息也一定相等(M1 = M2;同理, H(M1)H(M2),則 M1M2。也就是說,給定一個明文與雜湊值,須保證無法找出另一個訊息來產生同樣的雜湊值。

4項是雜湊函數最基本功能,亦即給予一段不定長度的訊息,能輕易計算出一個固定長度的雜湊值。如果反過來,給予一個固定長度的雜湊值,是無法計算出原來訊息的,也無法找出可以產生同樣雜湊值的另一段訊息,如能達到此功能,一般稱之為『弱雜湊函數』(Weak Hash Function。若再涵蓋第 5 項功能,則稱為『強雜湊函數』(Strong Hash Function,其表示有了明文與雜湊值,也無法另外偽造一個明文來產生相同的雜湊值。由此可見,欲達到強雜湊函數的功能實不容易,但它可以克服『生日攻擊法』的攻擊(容後介紹)。

4-2 簡單的雜湊函數

其實在網路通訊方面,雜湊函數常被用來偵測傳輸資料是否有發生錯誤,如圖 4-1 所示,發送端傳送資料之前,先將資料經過某一種雜湊函數計算,而得到一個雜湊值。然後將這雜湊值附加在資料後面,一併傳送給接收端;接收端收到資料之後,也以相同的雜湊函數計算出另一個雜湊值;如果此雜湊值與傳送端所計算的相同,則表示資料並沒有發生錯誤。一般來講,在較低層次的通訊協定(如 Ethernet 層)都使用 CRCCyclic Redundancy Check除法器,來產生一個檢查資料的 FCSFrame Check Sequence);至於較高層次(如 TCP/IP 層)則採用檢查集(Checksum)方法居多。

4-1 簡單的雜湊函數

以下就檢查集為例,來說明簡單雜湊函數的製作方法,不難發現這種雜湊函數的脆弱性。它的運作方式如圖 5-2 所示,利用所有字組成的相對位元之間做 XOR(符號為 ⊕)運算,稱為『位元操作- XOR』(Bitwise-XOR。首先將訊息以字元(如 3264 128 bits)區塊排列,再區塊之間相對位元做 XOR運算。假設將訊息切乘 m 個區塊,每個區塊有 n 個位元(如 32 bits),則所產生的檢查集(或稱雜湊值,也是 32 bits)為:

Cj = bj1 bj2 , …, bjm j = 1, 2, …, n

 

位元 1

位元 2

位元 3

 

位元 n

字元 1

B11

B21

B31

……

Bn1

字元 2

B12

B22

B32

……

Bn2

 

….

…..

……

…..

 

字元 m

B1m

B2m

B3m

……

Bnm1

雜湊值

C1

C2

C3

……

Cn

4-2 檢查集的雜湊函數

由上圖 4-2 可知,每一雜湊值的位元(Cj)是由該行所有位元做 XOR 運算而產生,如同位位元(Parity Bit)一般,其中如果有偶數個位元發生錯誤(由 1 0、或 0 1),則該位元的雜湊值將不會發生變化,因此,它的偵錯能力是非常薄弱的。

主講人:粘添壽博士

 

資訊與網路安全技術