聊聊生日悖論和生日攻擊

轉自 數學345 聊聊生日悖論和生日攻擊

我們先聊生日悖論問題，後面再看看什麼是生日攻擊。

也許你的數學老師問過這樣的問題，同學們，我們班上有30個人，你認為至少兩個人擁有相同生日的機率會很高嗎，比如超過50%？這個問題也可以這樣問：至少需要多少人的聚會,才能使得至少兩個人擁有相同生日的機率足夠高，比如超過50%？

這裡為了簡單，我們不考慮閏年的情況，不妨認為一年就365天。直覺可能會告訴我們需要大概183個人(即應該為一年所擁有天數的一半)才會較大機率的出現相同的生日。然而你也許已經知道了這個直覺是不正确的，事實上,我們需要的人數遠遠小于這個數目。

我們首先計算兩個人不是同一天生日的機率,即他們的生日沒有沖突的機率。

對1個人而言,不沖突的機率是1,這個問題非常簡單,因為單個生日不可能與任何其他人的生日沖突。

對2個人而言,不沖突的機率為364/365,因為他/他隻會與第一個人的生日出現沖突,即2個人不沖突的機率為

P ( 2 ) = 1 − 1 365 P(2)=1-\frac{1}{365} P(2)=1−3651​

如果第3個人加入這個聚會,他/她可能與前2個人已經在那裡的人出現沖突,是以3個人不沖突的機率為:

P ( 3 ) = ( 1 − 1 365 ) ⋅ ( 1 − 2 365 ) P(3) = (1-\frac{1}{365}) \cdot (1-\frac{2}{365}) P(3)=(1−3651​)⋅(1−3652​)

是以,t個人之間生日不沖突的機率為:

P ( t ) = ( 1 − 1 365 ) ⋅ ( 1 − 2 365 ) … ( 1 − t − 1 365 ) P(t) = (1-\frac{1}{365}) \cdot (1-\frac{2}{365}) \dots (1-\frac{t-1}{365}) P(t)=(1−3651​)⋅(1−3652​)…(1−365t−1​)

當t=366個人時,沖突的機率為1,因為一年隻有365天。

現在回歸到我們最初的問題:總共需要多少人才能使兩個沖突生日的機率達到50%?

從上面的等式可以得到,僅需要23個人就能使出現生日沖突的機率達到0.5,因為至少一個沖突的機率:

P = 1 − ( 1 − 1 365 ) ⋅ ( 1 − 2 365 ) … ( 1 − 23 − 1 365 ) = 0.507 P=1-(1-\frac{1}{365}) \cdot (1-\frac{2}{365}) \dots (1-\frac{23-1}{365})=0.507 P=1−(1−3651​)⋅(1−3652​)…(1−36523−1​)=0.507

注意:如果聚會有40個人參加,則出現生日沖突機率大概為90%由于這個思想實驗的結果令人匪夷所思,是以它通常也叫生日悖論。

那什麼是生日攻擊呢？生日悖論和生日攻擊有又什麼關系呢？我們經常使用電子錢包，在網絡上支付、轉賬、收款，是以必須有種機制來保證這些資金的安全。比如你購買一個東西，下了訂單，這個訂單從你的手機上發到商家手機上，必須得保證訂單沒有被修改過。如何保證呢？這裡會使用到一種簽名的技術，就像是我們的紙質合同上蓋了印章一樣，可以進行校驗是否被篡改了。一種常見的簽名技術是使用RSA算法。RSA算法是建立在整數因式分解問題上的：兩個大素數相乘在計算上是非常簡單的；但是反過來，知道其乘積結果，要想對乘積結果進行因式分解确是非常困難的。這裡不對RSA算法展開讨論，但是需要知道在實際上簽名的時候，不是直接對原始資訊進行RSA簽名，而是先對原始資訊計算出一串很短的固定的哈希值，然後對該哈希值進行簽名。對哈希值進行簽名有很多好處，比如由于哈希值非常短，是以比起對原始資訊簽名來說快很多，簽名的結果也相對變短了，重要的是更加安全（這裡就不展開闡述了）。這裡重點關注的是哈希值。

哈希值是通過哈希函數 z = h ( x ) z=h(x) z=h(x)計算的，比如MD5就是一種hash函數，經常用來保護我們輸入的密碼。比如你在設定密碼時候，輸入一串密碼"123456"，那麼背景伺服器實際上儲存的z,

其中

z=h(“123456”)=“e10adc3949ba59abbe56e057f20f883e”，

下一次你登入的時候，輸入相同的密碼"123456",

那麼背景伺服器隻需要比較此次計算出來的 z 1 = h ( " 123456 " ) z_1=h("123456") z1​=h("123456")和你之前設定密碼時儲存的z是否相同即可。如果 z 1 = z z_1=z z1​=z，那麼密碼驗證通過，如果

z 1 ≠ z z_1 \neq z z1​​=z 那麼密碼驗證失敗。

為什麼不直接儲存密碼，比較密碼是否相等呢？因為如果背景伺服器直接儲存你設定的密碼，那麼你的密碼就非常容易洩露了:任何人看到了這個明文密碼都知道怎麼登入你的賬号了。儲存哈希函數計算的值z，能提高安全性，這是因為哈希函數有以下幾種特性：

1.任意的消息大小 h(x)對任何大小的消息x都适用。

2.固定的輸出長度

h(x)生成的哈希值z的長度是固定的。比如MD5的哈希值長度為128比特，即16個位元組，也就說32個16進制字元(比如前面提到的例子"e10adc3949ba59abbe56e057f20f883e")。

3.有效性 h(x)的計算相對簡單。

4.單向性 給定一個輸出z, 找到滿足h(x)=z的輸入x是不可能的。

5.弱抗沖突性

給定 x 1 x_1 x1​和 h ( x 1 ) h(x_1) h(x1​),找到滿足 h ( x 1 ) = h ( x 2 ) h(x_1)=h(x_2) h(x1​)=h(x2​)的 x 2 x_2 x2​在計算上是不可能的。

6.強抗沖突性

找到滿足 h ( x 1 ) = h ( x 2 ) h(x_1)=h(x_2) h(x1​)=h(x2​)的一對 x 1 ≠ x 2 x_1 \neq x_2 x1​​=x2​在計算上也是不可行的。這裡 x 1 , x 2 x_1,x_2 x1​,x2​都是可以随意構造的消息。

其中4,5特性保證了密碼哈希的安全性：因為特性4，使得攻擊者即使知道z,也無法知道你的明文密碼x；因為特性5，使得攻擊者無法找到另外一個不同于你的明文密碼 x 2 x_2 x2​登入你的賬号。

密碼的安全性不需要特性6強抗沖突性，已經足夠安全，但是特性6可以用來保護上面提到的簽名。簡單的說如果哈希函數不具備特性6，那麼攻擊者可以制造出兩份簽名一樣的訂單，但是實際上這2份訂單的内容是不一樣的。

事實上，由于z是固定長度的，也就z的總數是固定的，根據鴿籠原理，沖突始終存在。是以我們隻能說在計算上是不可行的，意思是使用現在已知的計算機技術是很難的。

現在的問題是,找到沖突的難度有多大?

比如假設哈希值z總共有 2 80 2^{80} 280種，那麼請問攻擊者大概要嘗試多少次才能找到找到不同的一對消息x，但他們的哈希值都一樣。

這個問題其實和前面提到的生日悖論問題一樣。我們的直覺可能又會犯錯，我們可能猜想需要檢查 2 80 2^{80} 280個消息x。然而事實證明,攻擊者隻需要檢查 2 40 2^{40} 240個消息!這個結果非常令人驚訝。這種攻擊叫生日攻擊，它是密碼分析學中經常使用的一個非常強大的工具。下面我們将進行闡明為什麼攻擊者隻需要檢查 2 40 2^{40} 240個消息!

在哈希函數中,每個元素對應的可能值不是365個,而是 2 n 2^n 2n個,其中n為h的輸出寬度。實際上,n是哈希函數最重要的安全參數。問題是,對于標明的 x i x_i xi​和 x j x_j xj​而言,

攻擊者需要對多少個消息 ( x 1 , x 2 , … , x t ) (x_1,x_2,\dots,x_t) (x1​,x2​,…,xt​)進行哈希才能使得 h ( x i ) = h ( x j ) h(x_i)=h(x_j) h(xi​)=h(xj​)的機率足夠大?

t個哈希值之間不存在沖突的機率為: P (  沒有沖突  ) = ( 1 − 1 2 n ) ( 1 − 2 2 n ) ⋯ ( 1 − t − 1 2 n ) = ∏ i = 1 t − 1 ( 1 − i 2 n ) \begin{aligned} \begin{aligned} P(\text { 沒有沖突 }) &=\left(1-\frac{1}{2^{n}}\right)\left(1-\frac{2}{2^{n}}\right) \cdots\left(1-\frac{t-1}{2^{n}}\right) \\ &=\prod_{i=1}^{t-1}\left(1-\frac{i}{2^{n}}\right) \end{aligned} \end{aligned} P( 沒有沖突 )​=(1−2n1​)(1−2n2​)⋯(1−2nt−1​)=i=1∏t−1​(1−2ni​)​​

從指數函數的 Taylor

級數表示: e − x = 1 − x + x 2 / 2 ! − x 3 / 3 ! + ⋯ e^{-x}=1-x+x^{2} / 2 !-x^{3} / 3 !+\cdots e−x=1−x+x2/2!−x3/3!+⋯知, 以下近似值成立

e − x ≈ 1 − x e^{-x} \approx 1-x e−x≈1−x 因為 i / 2 n < < 1 i/2^n << 1 i/2n<<1.是以這個機率可以近似為:

P (  沒有沖突  ) ≈ ∏ i = 1 t − 1 e − i 2 n ≈ e − 1 + 2 + 3 + ⋯ + t − 1 2 n \begin{aligned} \begin{aligned} P(\text { 沒有沖突 }) & \approx \prod_{i=1}^{t-1} e^{-\frac{i}{2^{n}}} \\ & \approx e^{-\frac{1+2+3+\cdots+t-1}{2^{n}}} \end{aligned} \end{aligned} P( 沒有沖突 )​≈i=1∏t−1​e−2ni​≈e−2n1+2+3+⋯+t−1​​​

而 1 + 2 + ⋯ + t − 1 = t ( t − 1 ) / 2 , 1+2+\dots +t-1=t(t-1)/2 , 1+2+⋯+t−1=t(t−1)/2, 是以機率的近似值可以寫作

P ( 沒有沖突 ) ≈ e − t ( t − 1 ) 2 ⋅ 2 n P(\text{沒有沖突}) \approx e^{-\frac{t(t-1)}{2\cdot 2^n}} P(沒有沖突)≈e−2⋅2nt(t−1)​

回顧一下,我們的目标是确定找到一個沖突所需要的消息個數 ( x 1 , x 2 , … , x t ) (x_1,x_2,\dots,x_t) (x1​,x2​,…,xt​),是以現在要做的就是求解等式中的t。如果将至少存在一個沖突的機率表示為 λ = 1 − P ( 沒有沖突 ) \lambda=1-P(\text{沒有沖突}) λ=1−P(沒有沖突),則

λ ≈ 1 − e − t ( t − 1 ) 2 n + 1 ln ⁡ ( 1 − λ ) ≈ − t ( t − 1 ) 2 n + 1 t ( t − 1 ) ≈ 2 n + 1 ln ⁡ ( 1 1 − λ ) \begin{aligned} \begin{aligned} \lambda & \approx 1-e^{-\frac{t(t-1)}{2^{n+1}}} \\ \ln (1-\lambda) & \approx-\frac{t(t-1)}{2^{n+1}} \\ t(t-1) & \approx 2^{n+1} \ln \left(\frac{1}{1-\lambda}\right) \end{aligned} \end{aligned} λln(1−λ)t(t−1)​≈1−e−2n+1t(t−1)​≈−2n+1t(t−1)​≈2n+1ln(1−λ1​)​​

由于實際中 t > > 1 t>>1 t>>1,則 t 2 ≈ t ( t − 1 ) t^2 \approx t(t-1) t2≈t(t−1) 始終成立,是以,

t ≈ 2 n + 1 ln ⁡ ( 1 1 − λ ) t ≈ 2 ( n + 1 ) / 2 ln ⁡ ( 1 1 − λ ) ( 1 ) \begin{aligned} \begin{array}{l} t \approx \sqrt{2^{n+1} \ln \left(\frac{1}{1-\lambda}\right)} \\ t \approx 2^{(n+1) / 2} \sqrt{\ln \left(\frac{1}{1-\lambda}\right)} \quad \quad (1)\end{array} \end{aligned} t≈2n+1ln(1−λ1​)

​t≈2(n+1)/2ln(1−λ1​)

​(1)​​

等式(1)非常重要:它将尋找一個沖突所需要哈希的消息t的數目表示為哈希輸出長度n和沖突機率 λ \lambda λ的函數。生日攻擊最重要的結論就是:找到一個沖突所需要哈希的消息的數目大概等于可能輸出值個數的平方根,即大概為 2 n = 2 n / 2 \sqrt{2^n}=2^{n/2} 2n

​=2n/2。

例如,假設我們想找到輸出長度為80位的一個哈希函數(此函數是假設的)的沖突。為了使成功的機率達到50%,我們需要對

t = 2 81 / 2 ln ⁡ ( 1 / ( 1 − 0.5 ) ) ≈ 2 40.2 t=2^{81 / 2} \sqrt{\ln (1 /(1-0.5))} \approx 2^{40.2} t=281/2ln(1/(1−0.5))

​≈240.2

個輸入值進行哈希。使用目前的計算機完成 2 40 2^{40} 240左右哈希值的計算并檢查沖突是可能的!正因為這個原因,所有哈希函數的輸出長度必須至少為128位,而大多數現代哈希函數的輸出長度會更長。比如

SHA-1輸出長度為160位, SHA-256輸出長度為256位。

歡迎關注我的微信公衆号[數學345]：長按"識别圖中二維碼"；或打開微信掃一掃。