Protecting Poorly Chosen Secrets from Guessing Attacks論文筆記

Protecting Poorly Chosen Secrets from Guessing Attacks

作者：Li Gong, T.Mark, A.Lomas, Roger M.Needham, Jerome H.Saltzer

發表：IEEE Journal on Selected Areas in Communications, June 1993

一、猜測攻擊

（一）UNIX密碼系統

UNIX使用的是一個密碼檔案 /etc/passwd。這個檔案對于每一個使用者的密碼p進行hash，每個密碼進行hash時都有一個鹽值s，鹽值s和hash值g(p, s)都被存在密碼檔案中。

攻擊者可以猜測p的值然後進行hash，對于hash值進行驗證來判斷p的猜測是否正确。

一種解決辦法是限制/etc/passwd檔案的通路權限。

（二）SunOS安全NFS

去掉了/etc/passwd，轉而使用公鑰系統去加強安全性。SunOS-4.0引入了檔案/etc/publickey，其中包括使用者網絡名稱、使用者的公鑰和對應的私鑰（私鑰是用DES加密過的，其中DES的密鑰是由使用者的密碼派生出的）。使用者登入時即可通過密碼解密私鑰，然後伺服器驗證私鑰與公鑰是否比對即可驗證密碼的正确性。

因為/etc/publickey是公開的，攻擊者依舊可以猜測密碼p，然後解密私鑰。再随意選取一段文本，利用已知的公鑰和猜測出的私鑰進行加密解密，觀察結果是否一緻即可驗證p猜測的正确性。

一種解決方法是限制/etc/publickey的通路權限。

（三）Kerberos認證系統

伺服器最開始給使用者傳回的響應中包括一些可識别的資訊比如說時間戳t和伺服器S，而且這個響應是由使用者的密碼加密得到的。

是以攻擊者可以對于截獲的消息 { t , S , . . . } p \{t, S,...\}_p {t,S,...}p​進行猜測攻擊，解密後的資料可以通過對比，很明顯地發現t是否是一個合理的時間或者S是否為合理的伺服器名字元串，即可判斷解密是否正确。

二、已知明文和驗證文本

通過上面猜測攻擊章節的閱讀，大家可能已經總結出其中的特點。攻擊者在發動猜測攻擊時，往往需要一些驗證性的資訊來判斷其猜測是否正确。

已知明文攻擊對于對稱密碼系統來說，可以通過猜測密鑰對已知的密文進行解密，然後判斷其對應的明文是否一緻，進而進行攻擊；對于非對稱密碼系統來說，猜測私鑰是不現實的，是以可以猜測明文文本資訊，然後利用公鑰進行加密，來比對對應的密文是否一緻，進而驗證猜測是否正确。

由上可知，已知明文攻擊主要就是利用了具有驗證性的文本來對其猜測攻擊進行驗證。

驗證文本具有以下特點：

• 攻擊者可以識别，能夠利用其驗證
• 攻擊者能夠進行某種運算，比如說hash運算。來進行得到與驗證文本進行比對的文本。

三、基本的保護技術

（一）基本二路握手

A用密鑰k加密随機數n發送給B

A → B :   { n } k A\to B:\ \{n\}_k A→B: {n}k​

f()用來確定不是簡單地将原消息傳回

B → A :   { f ( n ) } k B\to A:\ \{f(n)\}_k B→A: {f(n)}k​

注：n是随機數，是以 { n } k \{n\}_k {n}k​和 { f ( n ) } k \{f(n)\}_k {f(n)}k​是各自安全的，但是如果被放在一起，則可以用f()驗證，反而不安全了。

（二）雙密鑰二路握手

用兩個密鑰可以避免上述問題，公私鑰也可以。

A → B :   { n } k 1 A\to B:\ \{n\}_{k_1} A→B: {n}k1​​

B → A :   { f ( n ) } k 2 B\to A:\ \{f(n)\}_{k_2} B→A: {f(n)}k2​​

注：必須k1和k2都猜對才能攻擊成功，可能需要多次驗證，大大增加難度。但是如果k1加密的 { n } k 1 \{n\}_{k1} {n}k1​已知了（比如說k1是公鑰），那麼k2可能被比對出來結果。用k2解密得到n’，用 { n ′ } k 1 \{n'\}_{k1} {n′}k1​與 { n } k 1 \{n\}_{k1} {n}k1​比對。這種比對主要是依賴于f()的作用，如果隻是 f ( n ) = n + 1 f(n)=n+1 f(n)=n+1這種可逆的簡單運算，那麼攻擊便可成功。

（三）随機數幹擾因子

引入大随機數作為公鑰加密的幹擾因子，進而避免公鑰加密密文成為驗證文本。

A → B :   { c , n } k 1 A\to B:\ \{c, n\}_{k_1} A→B: {c,n}k1​​

B → A :   { f ( n ) } k 2 B\to A:\ \{f(n)\}_{k_2} B→A: {f(n)}k2​​

注：随機數c的加入可以形成一次一密，但是n或f(n)可能仍然有時間戳等含有某些含義的資料，會被用來驗證。

（四）掩碼

引入掩碼進而掩蓋住具有含義的資訊，進而解決驗證文本的問題。

A → B :   { c 1 , c 2 , n } k 1 A\to B:\ \{c_1, c_2, n\}_{k_1} A→B: {c1​,c2​,n}k1​​

B → A :   { c 2 ⊕ f ( n ) } k 2 B\to A:\ \{c_2\oplus f(n)\}_{k_2} B→A: {c2​⊕f(n)}k2​​

四、認證協定

（一）互相認證協定

1. A → S : { A , B , n a 1 , n a 2 , c a , { t a } K a } K s A\to S: \{A,B,na1,na2,ca,\{ta\}_{Ka}\}_{Ks} A→S:{A,B,na1,na2,ca,{ta}Ka​}Ks​
2. S → B : A , B S\to B:A,B S→B:A,B
3. B → S : { B , A , n b 1 , n b 2 , c b , { t b } K a } K s B\to S:\{B,A,nb1,nb2,cb,\{tb\}_{Ka}\}_{Ks} B→S:{B,A,nb1,nb2,cb,{tb}Ka​}Ks​
4. S → A : { n a 1 , k ⊕ n a 2 } K a S\to A:\{na1,k\oplus na2\}_{Ka} S→A:{na1,k⊕na2}Ka​
5. S → B : { n b 1 , k ⊕ n b 2 } K b S\to B:\{nb1, k\oplus nb2\}_{Kb} S→B:{nb1,k⊕nb2}Kb​
6. A → B : { r a } k A\to B:\{ra\}_{k} A→B:{ra}k​
7. B → A : { f 1 ( r a ) , r b } k B\to A:\{f1(ra),rb\}_{k} B→A:{f1(ra),rb}k​
8. A → B : { f 2 ( r b ) } k A\to B:\{f2(rb)\}_k A→B:{f2(rb)}k​

其中Ka和Kb是A,B與S的共享密鑰，k是AB之間的會話密鑰，Ks是server的公鑰，S代表server，ta和tb代表兩個時間戳。

• 第一條和第三條消息：包括三個随機數na1，na2，ca；一個隻能由A産生的新鮮性消息 { t a } K a \{ta\}_{Ka} {ta}Ka​；聲明A要與B進行通信A,B
• 第四條和第五條消息：na1代表對于第一條消息的正确破解，na1和na2在多次通信中不能重用；na2用于隐藏k，防止外來攻擊或者B本身圖謀不軌（沒有了na2，第四條消息後面的k可以被用來驗證對于Ka的猜測）。
• ca：随機數幹擾因子，用于防止B的惡意。如果沒有ca的話，那麼B一旦截獲了第四條消息，B可以去猜測Ka，然後B可以得到na1、na2、k（本身B就有）、A、B、Ks，是以B隻要去對第一條消息驗證是否相同，即可确定Ka
• 第六、七、八條消息：挑戰應答機制

（二）減少消息數目

1. A → B : { A , B , n a 1 , n a 2 , c a , { t a } K a } K s , r a A\to B:\{A,B,na1,na2,ca,\{ta\}_{Ka}\}_{Ks},ra A→B:{A,B,na1,na2,ca,{ta}Ka​}Ks​,ra
2. B → S : { A , B , n a 1 , n a 2 , c a , { t a } K a } K s , { B , A , n b 1 , n b 2 , c b , { t b } K b } K s B\to S:\{A,B,na1,na2,ca,\{ta\}_{Ka}\}_{Ks},\{B,A,nb1,nb2,cb,\{tb\}_{Kb}\}_{Ks} B→S:{A,B,na1,na2,ca,{ta}Ka​}Ks​,{B,A,nb1,nb2,cb,{tb}Kb​}Ks​
3. S → B : { n a 1 , k ⊕ n a 2 } K a , { n b 1 , k ⊕ n b 2 } K b S\to B:\{na1,k\oplus na2\}_{Ka},\{nb1, k\oplus nb2\}_{Kb} S→B:{na1,k⊕na2}Ka​,{nb1,k⊕nb2}Kb​
4. B → A : { n a 1 , k ⊕ n a 2 } K a , { f 1 ( r a ) , r b } k B\to A:\{na1,k\oplus na2\}_{Ka},\{f1(ra),rb\}_k B→A:{na1,k⊕na2}Ka​,{f1(ra),rb}k​
5. A → B : { f 2 ( r b ) } k A\to B:\{f2(rb)\}_k A→B:{f2(rb)}k​

壓縮了協定的條目，内容不變

（三）增強的Kerberos協定

1. A → S : { A , B , n a 1 , n a 2 , c a , { t a } K a } K s A\to S:\{A,B,na1,na2,ca,\{ta\}_{Ka}\}_{Ks} A→S:{A,B,na1,na2,ca,{ta}Ka​}Ks​
2. S → A : { n a 1 , k ⊕ n a 2 } K a , { A , k , t s } K b S\to A:\{na1, k\oplus na2\}_{Ka},\{A,k,ts\}_{Kb} S→A:{na1,k⊕na2}Ka​,{A,k,ts}Kb​
3. A → B : { A , k , t s } K b A\to B:\{A,k,ts\}_{Kb} A→B:{A,k,ts}Kb​

（四）使用随機數挑戰

不用時間戳，改用随機數挑戰。

1. A → S : A , B A\to S:A,B A→S:A,B
2. S → A : A , B , n s S\to A:A,B,ns S→A:A,B,ns
3. A → B : { A , B , n a 1 , n a 2 , c a , { n s } K a } K s , n s , r a A\to B:\{A,B,na1,na2,ca,\{ns\}_{Ka}\}_{Ks}, ns,ra A→B:{A,B,na1,na2,ca,{ns}Ka​}Ks​,ns,ra
4. B → S : { A , B , n a 1 , n a 2 , c a , { n s } K a } K s , { B , A , n b 1 , n b 2 , c b , { n s } K b } K s B\to S:\{A,B,na1,na2,ca,\{ns\}_{Ka}\}_{Ks},\{B,A,nb1,nb2,cb,\{ns\}_{Kb}\}_{Ks} B→S:{A,B,na1,na2,ca,{ns}Ka​}Ks​,{B,A,nb1,nb2,cb,{ns}Kb​}Ks​
5. S → B : { n a 1 , k ⊕ n a 2 } K a , { n b 1 , k ⊕ n b 2 } K b S\to B:\{na1,k\oplus na2\}_{Ka},\{nb1, k\oplus nb2\}_{Kb} S→B:{na1,k⊕na2}Ka​,{nb1,k⊕nb2}Kb​
6. B → A : { n a 1 , k ⊕ n a 2 } K a , { f 1 ( r a ) , r b } k B\to A:\{na1, k\oplus na2\}_{Ka}, \{f1(ra),rb\}_k B→A:{na1,k⊕na2}Ka​,{f1(ra),rb}k​
7. A → B : { f 2 ( r b ) } k A\to B:\{f2(rb)\}_k A→B:{f2(rb)}k​

（五）身份協定

像ATM卡、信用卡、通行卡、電子通行、電話卡等。這種情況下通信不需要會話密鑰，也不需要雙向認證，隻需要簡單的身份認證即可。

1. A → S : A A\to S:A A→S:A
2. S → A : n s S\to A:ns S→A:ns
3. A → S : { A , c a , { n s } K a } K s A\to S:\{A,ca,\{ns\}_{Ka}\}_{Ks} A→S:{A,ca,{ns}Ka​}Ks​

（六）秘密公鑰協定

無需記錄公鑰，由server發送。

1. A → S : A , B A\to S:A,B A→S:A,B
2. S → A : A , B , n s , { K s a } K a , { K s b } K b S\to A:A,B,ns,\{Ksa\}_{Ka},\{Ksb\}_{Kb} S→A:A,B,ns,{Ksa}Ka​,{Ksb}Kb​
3. A → B : { A , B , n a 1 , n a 2 , c a , { n s } K a } K s a , n s , r a , { K s b } K b A\to B:\{A,B,na1,na2,ca,\{ns\}_{Ka}\}_{Ksa},ns,ra,\{Ksb\}_{Kb} A→B:{A,B,na1,na2,ca,{ns}Ka​}Ksa​,ns,ra,{Ksb}Kb​
4. B → S : { A , B , n a 1 , n a 2 , c a , { n s } K a } K s a , { B , A , n b 1 , n b 2 , c b , { n s } K b } K s b B\to S:\{A,B,na1,na2,ca,\{ns\}_{Ka}\}_{Ksa},\{B,A,nb1,nb2,cb,\{ns\}_{Kb}\}_{Ksb} B→S:{A,B,na1,na2,ca,{ns}Ka​}Ksa​,{B,A,nb1,nb2,cb,{ns}Kb​}Ksb​
5. S → B : { n a 1 , k ⊕ n a 2 } K a , { n b 1 , k ⊕ n b 2 } K b S\to B:\{na1,k\oplus na2\}_{Ka},\{nb1,k\oplus nb2\}_{Kb} S→B:{na1,k⊕na2}Ka​,{nb1,k⊕nb2}Kb​
6. B → A : { n a 1 , k ⊕ n a 2 } K a , { f 1 ( r a ) , r b } k B\to A:\{na1,k\oplus na2\}_{Ka},\{f1(ra),rb\}_k B→A:{na1,k⊕na2}Ka​,{f1(ra),rb}k​
7. A → B : { f 2 ( r b ) } k A\to B:\{f2(rb)\}_k A→B:{f2(rb)}k​

注：公鑰也要保密好，不然随意洩露出去會成為驗證文本

（七）直接認證

已經共享密鑰Kab，直接進行身份的認證即可。Kab1是公鑰。

1. A → B : r a , { K a b 1 } K a b A\to B:ra,\{Kab1\}_{Kab} A→B:ra,{Kab1}Kab​
2. B → A : { B , A , n b 1 , n b 2 , c b , { r a } K a } K a b 1 B\to A:\{B,A,nb1,nb2,cb,\{ra\}_{Ka}\}_{Kab1} B→A:{B,A,nb1,nb2,cb,{ra}Ka​}Kab1​
3. A → B : { n b 1 , k ⊕ n b 2 } K a b A\to B:\{nb1,k\oplus nb2\}_{Kab} A→B:{nb1,k⊕nb2}Kab​
4. B → A : { f 1 ( r a ) , r b } k B\to A:\{f1(ra),rb\}_k B→A:{f1(ra),rb}k​
5. A → B : { f 2 ( r b ) } k A\to B:\{f2(rb)\}_k A→B:{f2(rb)}k​