【正文】 k≤n，則第一輪就可以產生一個唯一對應。仍然可以有多于一個 key產生這一配對，這時攻擊者只需對一個新的(message, MAC)進行相同的測試。 考慮以下的 MAC算法 M = (X1 || X2 || … || Xm) 是一個由 64位 Xi數(shù)據(jù)塊連接而成， 定義 ?(M) = X1?X2?...?Xm CK(M) = EK[?(M)] 其中 ? 為異或操作； E為 ECB工作模式的 DES算法。 Key length = 56 bit MAC length = 64 bit 強力攻擊需要至少 256次加密來決定 K。 但攻擊者可以不用找到 K就可以實施攻擊。 設 M? = ( Y1 || Y2 || … || Ym 1 || Ym) 其中 Y1, Y2, …, Ym 1是替換 X1, X2,…,Xm 1的任意值，而 Ym = Y1?Y2 ?, …, ? Ym1 ? ?(M) 這時 消息 M’ 和 MAC= CK(M) = EK[?(M)]是一對可被接收者認證 的消息。 CK(M ?) = EK[?(M ?)] = EK[Y1?Y2 ?, …, ? Ym1 ? Ym ] = EK[Y1?Y2 ?, …, ? Ym1 ? (Y1?Y2 ?, …, ? Ym1 ? ?(M)) ] = EK[?(M)] 用此方法，任何長度為 64?(m1)位的消息可以 作為 欺騙性 信息被插入 ！ 為了防止以上可能的攻擊， MAC函數(shù)應具有以下性質： ? 如果一個攻擊者得到 M和 CK(M)，則攻擊者構造一個消息 M ?使得 CK(M ?)=CK(M)應在計算上不可行。 ? CK(M)應均勻分布，即：隨機選擇消息 M和 M ? ， CK(M)= CK(M ?)的概率是 2n，其中 n是 MAC的位數(shù)。 ? 令 M ?為 M的某些變換，即： M ? =f(M)，（例如： f可以涉及 M中一個或多個給定位的反轉），在這種情況下， Pr[CK(M)= CK(M ?)] = 2n。 基于 DES的 MAC ? Data Authentication Algorithm – FIPS publication (FIPS PUB 113) – ANSI standard () ? 使用 CBC(Cipher Block Chaining)方式，初始向量為 0。 ? 最廣泛的用法 將數(shù)據(jù)按 64位分組， D1, D2, … , D N，必要時最后一個數(shù)據(jù)塊用 0向右填充。運用 DES算法 E，密鑰 K, 數(shù)據(jù)鑒別碼 (DAC)的計算如下： O1 = EK(D1) O2 = EK(D2?O1) O3 = EK(D3?O2) … ON = EK(DN?ON1) M的大小可由通信雙方約定。美國聯(lián)邦電信建議采用 24bit[見 FTSC1026],而美國金融系統(tǒng)采用 32bit [ABA,1986] D1 (64bits) Time = 1 DES encrypt K (56bits) O1 (64bits) D2 (64bits) Time = 2 DES encrypt K O2 (64bits) + DN (64bits) Time = N DES encrypt K ON + DAC Mbits (16 to 64 bits) } ... (16=M=64) 工作于 CFB模式下 DES 64bit寄存器 DES 選左邊 k位 選左邊 M位 + yi xi k 問題 ? 若對相當長的文件通過簽名認證怎么辦？如一個合法文件有數(shù)兆字節(jié)長。自然按 64比特分劃成一塊一塊，用相同的密鑰獨立地簽每一個塊。然而，這樣太慢。 解決辦法 ? 解決辦法：引入可公開的密碼散列函數(shù) (Hash function)。它將取任意長度的消息做自變量，結果產生規(guī)定長度的消息摘要。 [如，使用數(shù)字簽名標準 DSS，消息摘要為 160比特 ]，然后簽名消息摘要。對數(shù)字簽名來說，散列函數(shù) h是這樣使用的： 消息： x 任意長 消息摘要： Z=h(x) 160bits 簽名： y=sigk(Z) 320 bits (簽名一個消息摘要 ) ? 驗證簽名 :(x,y),其中 y= sigk(h(x))，使用公開的散列函數(shù) h，重構作 Z ? =h(x)。然后 Verk(y)=Z,來看 Z?=Z39。 新的問題 ? 用以鑒別的散列函數(shù)，能否減弱認證方案的安全性？這個問題是要分析的。簽名的對象由完整消息變成消息摘要，這就有可能出現(xiàn)偽造。 安全威脅一 (a)偽造方式一： Oscar以一個有效簽名 (x,y)開始，此處 y= sigk(h(x))。首先他計算 Z=h(x)，并企圖找到一個 x39。滿足h(x39。)=h(x)。若他做到這一點，則 (x39。,y)也將為有效簽名。為防止這一點，要求函數(shù) h具有無碰撞特性。 定義 1(弱無碰撞 )， 散列函數(shù) h稱為是弱無碰撞的，是指對給定消息 x ∈ X，在計算上幾乎找不到異與 x的 x39。 ∈ X使 h(x)=h(x39。)。 安全威脅二 (b)偽造方式二： Oscar首先找到兩個消息 x=x39。,滿足h(x)=h(x39。),然后 Oscar把 x 給 Bob且使他對 x的摘要 h(x)簽名，從而得到 y,那么 (x39。,y)是一個有效的偽造 。 定義 2(強無碰撞 )散列函數(shù) h被稱為是強無碰撞的 ,是指在計算上幾乎不可能找到相異的 x， x39。使得 h(x)=h(x39。)。 注：強無碰撞自然含弱無碰撞！ 安全威脅三 (c)偽造方式三：在散列函數(shù)的用法 (e)中 , 秘密值 S本身并不發(fā)送 , 如果散列函數(shù)不是單向的 ,攻擊者截獲到 M和H(M||S). 然后通過某種逆變換獲得 M||S, 因而攻擊者就可以得到 S. 定義 3(單向的 )稱散列函數(shù) h為單向的，是指計算 h的逆函數(shù) h1在計算上不可行。 HASH 函數(shù) h = H(M) 滿足： H可以作用于一個任意長度的數(shù)據(jù)塊； H產生一個固定長度的輸出； 對任意給定的 x ,H(x) 計算相對容易，無論是軟件還是硬件實現(xiàn)。 對任意給定碼 h，找到 x滿足 H(x)=h具有計算不可行性；（單向性） 對任意給定的數(shù)據(jù)塊 x，找到滿足 H(y)=H(x)的 y?x具有計算不可行 性。 找到任意數(shù)據(jù)對 (x,y)，滿足 H(x) = H(y)是計算不可行的。 前三條要求具有實用性，第 4條是單向性質，即給定消息可以產生一個 散列碼，而給定散列碼不可能產生對應的消息。第 5條性質是保證一個 給定的消息的散列碼不能找到與之相同的另外的消息。即防止偽造。 第 6條是對已知的生日攻擊方法的防御能力。 目的：“ fingerprint” of messgae Hash函數(shù)的分類 ? 根據(jù)安全水平： ? 定義 1(弱無碰撞 )， 散列函數(shù) h稱為是弱無碰撞的，是指對給定消息 x ∈ X，在計算上幾乎找不到異于 x的 x39。 ∈ X使 h(x)=h(x39。)。 ? 定義 2(強無碰撞 )， 散列函數(shù) h被稱為是強無碰撞的 ,是指在計算上幾乎不可能找到相異的 x，x39。使得 h(x)=h(x39。)。 注：強無碰撞自然含弱無碰撞！ Hash函數(shù)的分類 ? 根據(jù)是否使用密鑰 ? 帶秘密密鑰的 Hash函數(shù) :消息的散列值由只有通信雙方知道的秘密密鑰 K來控制。此時，散列值稱作 MAC。 ? 不帶秘密密鑰的 Hash函數(shù)： 消息的散列值的產生無需使用密鑰。此時，散列值稱作 MDC。 Hash與 MAC的區(qū)別 ? MAC需要對全部數(shù)據(jù)進行加密 ? MAC速度慢 ? Hash是一種直接產生鑒別碼的方法 生日攻擊 ? 假定使用 64位的散列碼 ,是否安全 ? ? 如果采用傳輸加密的散列碼和不加密的報文 M,對手需要找到 M ?,使得H(M?)=H(M),以便使用替代報文來欺騙接收者 . ? 一種基于生日悖論的攻擊可能做到這一點 . 生日悖論 ? 生日問題：一個教室中，最少應有多少學生，才使至少有兩人具有相同生日的概率不小于 1/2？ ? 概率結果與人的直覺是相違背的 . ? 實際上只需 23人 ,即任找 23人，從中總能選出兩人具有相同生日的概率至少為 1/2。 相關問題 ? 給定一個散列函數(shù) ,有 n個可能的輸出 ,輸出值為 H(x),如果 H有 k個隨機輸入 , k必須為多大才能使至少存在一個輸入 y,使得 H(y)=H(x)的概率大于 . ? 對單個 y, H(y)=H(x)的概率為 1/n,反過來 H(y)?H(x)的概率為 1(1/n). ? 如果產生 k個隨機值 y,他們之間兩兩不等的概率等于每個個體不匹配概率的乘積 ,即 [1(1/n)]k,這樣 ,至少有一個匹配的概率為 1[1(1/n)]k?1[1(k/n)]=k/ 概率等于,只需 k=n/2. ? 對長度為 m位的散列碼，共有 2m個可能的散列碼，若要使任意的 x,y 有 H(x)=H(y)的概率為 ,只需 k=2m/2 Birthday Attacks: example ?A準備兩份合同 M和 M? ，一份 B會同意，一份會取走他的財產而被拒絕 ?A對 M和 M?各做 32處微小變化 (保持原意 ),分別產生232個 64位 hash值 ?根據(jù)前面的結論 ,超過 M和一個M?,它們的 hash值相同 ?A提交 M,經 B審閱后產生 64位 hash值并對該值簽名 ,返回給 A ?A用 M?替換 M ?Hash必須足夠長 (64 ? 128 ? 160) 散列函數(shù)的安全性 ? 強行攻擊：生日攻擊 ? MD5 128位， 24小時找到一個沖突 單向 2n 弱無碰撞 2n 強無碰撞 2n/2 Hash函數(shù)的構造 ? 基于數(shù)學難題的構造方法： 計算速度慢，不實用 ? 利用對稱密碼體制來設計 Hash ? 直接設計 分組鏈接 Block Chaining ?用對稱加密算法構造 hash函數(shù) ?M=(M1,M2,…,M t), H0=Initial value Hi=f(Mi,Hi1), 例如 Hi=EMi(Hi1)