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?