第四講基本協(xié)議

1、基本協(xié)議密鑰交換通常的密碼技術是用單獨的密鑰對每一次單獨的會話加密，這個密鑰稱為會話密鑰，因為它只在一次特殊的通信中使用。這個會話密鑰怎么到達會話者的手中可能是很復雜的事情。對稱密碼的密鑰交換這個協(xié)議假設alice和bob（網絡上的用戶）每人和密鑰分配中心（kdc）共享一個秘密密鑰，我們的協(xié)議中的trent就是kdc。在協(xié)議開始執(zhí)行前，這些密鑰必須在適當?shù)奈恢茫▍f(xié)議忽略了怎么分配這些秘密密鑰這個非常實際的問題，只是假設它們在適當?shù)奈恢茫⑶襪allory不知道它們是什么）。（1）alice呼叫trent，并請求一個與bob通信的會話密鑰。（2）trent產生一隨機會話密鑰，并對它的兩個副本加密

2、：一個用alice的密鑰，另一個用bob的密鑰加密。trent發(fā)送這兩個副本給alice。（3）alice對她的會話密鑰的副本解密。（4）alice將bob的會話密鑰副本送給bob。（5）bob對他的會話密鑰的副本解密。（6）alice和bob用這個會話密鑰安全地通信。這個協(xié)議依賴于trent的絕對安全性。trent更可能是可信的計算機程序，而不是可信的個人。如果mallory破壞了trent，整個網絡都會遭受損害。他有trent與每個用戶共享的所有秘密密鑰；他可以讀所有過去和將來的通信業(yè)務。他所做的事情就是對通信線路進行搭線竊聽，并監(jiān)視加密的報文業(yè)務。這個系統(tǒng)的另外一個問題是trent可能會

3、成為瓶頸。他必須參與每一次密鑰交換，如果trent失敗了，這個系統(tǒng)就會被破壞。公開密鑰密碼的密鑰交換alice和bob使用公開密鑰密碼協(xié)商會話密鑰，并用協(xié)商的會話密鑰加密數(shù)據(jù)。在一些實際的實現(xiàn)中，alice和bob簽了名的公開密鑰可在數(shù)據(jù)庫中獲得。這使得密鑰交換協(xié)議更容易，即使bob從來沒有聽說過alice，alice也能夠把信息安全地發(fā)送給bob。（1）alice從kdc得到bob的公開密鑰。（2）alice產生隨機會話密鑰，用bob的公開密鑰加密它，然后將它傳給bob。（3）bob用他的私鑰解密alice的信息。（4）他們兩人用同一會話密鑰對他們的通信進行加密。中間人攻擊eve除了試圖破譯

4、公開密鑰算法或者嘗試對密文作唯密文攻擊之外，沒有更好的辦法。mallory比eve更有能力，他不僅能監(jiān)聽alice和bob之間的信息、還能修改信息、刪除信息、并能產生全新的信息。當mallory同alice談話時，他能模仿bob，他也能模仿alice同bob談話。（1）alice將她的公開密鑰傳送給bob。mallory截取了這個密鑰并將自己的公開密鑰傳送給bob。（2）bob將他的公開密鑰傳送給alice。mallory截取這個密鑰，并將自己的公開密鑰傳送給alice。（3）當alice將用“bob”的公開密鑰加了密的信息傳送給bob時，mallory截取它。由于信息實際上是用mallory

5、的公開密鑰加密的，他就用自己的私鑰解密。再用bob的公開密鑰對信息重新加密，并將它傳送給bob。（4）當bob將用“alice”的公開密鑰加密的信息傳送給alice時，mallory截取它。由于信息實際上是用他自己的公開密鑰加密的，他用他的私鑰解密信息，再用alice的公開密鑰重新加密，并將它傳送給alice。即使alice和bob的公開密鑰存儲在數(shù)據(jù)庫中，這種攻擊也是可行的。mallory能夠截取alice的數(shù)據(jù)庫查詢，并用自己的公開密鑰代替bob的公開密鑰，對bob他也能做同樣的事情，用自己的公開密鑰代替alice的公開密鑰。他也能秘密地侵入數(shù)據(jù)庫，用他自己的密鑰代替alice和bob的密

6、鑰。接下來他就簡單地等著alice和bob互相談話，然后截取和修改信息，他成功了！“中間人攻擊”是可行的，因為alice和bob無法驗證他們正在作的互相交談。假設mallory沒有導致任何值得注意的網絡延遲，他們兩人就沒有辦法知道有人正在他們中間閱讀他們自認為是秘密的消息。聯(lián)鎖協(xié)議聯(lián)鎖協(xié)議是阻止“中間人攻擊”的好辦法。下面是這個協(xié)議怎么工作的：（1）alice將她的公開密鑰傳送給bob。（2）bob將他的公開密鑰傳送給alice。（3）alice用bob的公開密鑰加密她的報文，并將加密報文的一半傳送給bob。（4）bob用alice的公開密鑰加密他的報文，并將加密報文的一半傳送給alice。（

7、5）alice將加了密的另一半報文傳送給bob。（6）bob將alice的兩半報文合在一起，并用他的私鑰解密；bob將他加了密的另一半報文傳送給alice。（7）alice將bob兩半報文合在一起，并用她的私鑰解密。這里重要的一點是：只有報文的一半，沒有另一半，報文是毫無用處的。bob只有到步驟（6）步才能讀alice的報文，alice只有到步驟（7）步才能讀bob的報文。有很多辦法實現(xiàn)它：（1）如果采用分組加密算法，每一分組的一半（例如，每隔一比特）能在每半個報文中發(fā)送。（2）報文的解密依賴于初始矢量，初始矢量可以在報文的另一半中發(fā)送。（3）首先發(fā)送的一半報文可能是加密報文的單向hash函數(shù)

8、，并且加密報文本身可能是另一半。為了了解這樣做是怎樣對mallory制造麻煩的，讓我們再看看他破壞協(xié)議的企圖。他仍然能夠在第（1）步和第（2）步中用自己的公開密鑰代替alice和bob公開密鑰。但現(xiàn)在，當他在第（3）步截取alice的一半報文時，他不能用他的私鑰對報文解密，然后用bob的公開密鑰再加密，他不得不虛構一完全不同的新報文，并將它的一半發(fā)送給bob。當他在第（4）步截取bob給alice的一半報文時，他有同樣的問題，他不能用他的私鑰解密，并用alice的公開密鑰再加密，他又不得不虛構一完全不同的新報文，并將它的一半發(fā)送給alice。當他在第（5）步和第（6）步截取到實際報文的另一半時

9、，他再去把他虛構新報文改回來，就太遲了。alice和bob之間的會話必會是完全不同的。mallory也可以不用這種辦法。如果他非常了解alice和bob，他就可以模仿他們之中的一個同另一人通話，他們絕不會想到正受到欺騙。但這樣做肯定比坐在他們之間截取和讀他們的報文更難。使用數(shù)字簽名的密鑰交換在會話密鑰交換協(xié)議期間采用數(shù)字簽名也能防止“中間人攻擊”。trent對alice和bob的公開密鑰簽名。簽名的密鑰包括一個已簽名的所有權證書。當alice和bob收到密鑰時，他們每人都能驗證trent的簽名。那么，他們就知道公開密鑰是哪個人的。密鑰的交換就能進行了。mallory會遇到嚴重的阻力。他不能假冒

10、bob或者alice，因為他不知道他們的私鑰。他也不能用他的公開密鑰代替他們兩人的公開密鑰，因為當他有由trent簽名的證書時，這個證書是為mallory簽發(fā)的。他所能做的事情就是竊聽往來的加密報文，或者破壞通信線路，阻止alice和bob談話。這個協(xié)議也動用trent，但kdc遭受損害的風險比第一種協(xié)議小。如果mallory危及到trent的安全（侵入kdc），他所得到的只是trent的私鑰。這個密鑰使他僅能對新的密鑰簽名；它不會讓他對任何會話密鑰解密，或者讀取任何報文。為了能夠讀往來的報文，mallory不得不冒充網絡上的某個用戶，并且欺騙合法用戶用他的假的公開密鑰加密報文。mallory

11、能夠發(fā)起這種攻擊：持有trent的私鑰，他能夠產生假的簽名密鑰去愚弄alice和bob。然后mallory就能夠在數(shù)據(jù)庫中交換他們真正的簽名密鑰，或者截取用戶向數(shù)據(jù)庫的請求，并用他的假密鑰代替。這使他能夠發(fā)起“中間人攻擊”，并讀取他人的通信。這種攻擊是可行的，但記住mallory必須能夠截取和修改信息。在一些網絡中，截取和修改報文比被動地坐在網絡旁讀取往來的報文更難。在廣播信道上，如無線網中，幾乎不可能用其他報文來替代某個報文（整個網絡可能被堵塞）。在計算機網絡中做這種事要容易些，并且隨時日的推移變得越來越容易，例如ip欺騙、路由攻擊等等；主動攻擊并不一定表示有人用數(shù)據(jù)顯示儀摳出數(shù)據(jù)，且也不限

12、于三字符的代理。密鑰和報文傳輸alice和bob在交換報文前不需要完成密鑰交換協(xié)議。在下面的協(xié)議中，alice在沒有任何以前的密鑰交換協(xié)議的情況下，將報文m傳送給bob：（1）alice產生一隨機會話密鑰k，并用k加密m。 ek（m）（2）alice從數(shù)據(jù)庫中得到bob的公開密鑰。（3）alice用bob的公開密鑰加密k。 eb（k）（4）alice將加密的報文和加密的會話密鑰傳送給bob。 ek（m），eb（k）為了增加安全性，防止“中間人攻擊”，alice可對傳輸簽名。（5）bob用他的私鑰將alice的會話密鑰k解密。（6）bob用會話密鑰將alice的報文解密。這個混合系統(tǒng)表示，公開密

13、鑰密碼怎樣被經常用于通信系統(tǒng)的。它可以和數(shù)字簽名、時間標記以及任何其它安全協(xié)議組合在一起使用。密鑰和報文廣播alice可能把加了密的報文傳送給幾個人。在這個例子中，alice就把加密報文傳送給bob、carol和dave：（1）alice產生一隨機會話密鑰k，并用k加密報文m。 ek（m）（2）alice從數(shù)據(jù)庫中得到bob、carol和dave的公開密鑰。（3）alice用bob的公開密鑰加密k，用carol的公開密鑰加密k，用dave的公開密鑰加密k。 eb（k），ec（k），ed（k）（4）alice廣播加密的報文和所有加密的密鑰，將它傳送給要接收它的人。 eb（k），ec（k），ed（

14、k），ek（m）（5）只有bob、carol和dave能用他們的私鑰將k解密。（6）只有bob、carol和dave能用k將alice的報文解密。這個協(xié)議可以在存儲轉發(fā)網絡上實現(xiàn)。中央服務器能夠將alice的報文，連同特別加密的密鑰一起轉發(fā)給bob、carol和dave。服務器不一定是安全的或者可信的，因為它不可能對任何報文解密。鑒別當alice登錄進入計算機（或自動柜員機、電話銀行系統(tǒng)、或其它的終端類型）時，計算機怎么知道她是誰呢？計算機怎么知道她不是其他人偽造alice的身份呢？傳統(tǒng)的辦法是用通行字來解決這個問題的。alice先輸入她的通行字，然后計算機確認它是正確的。alice和計算機兩

15、者都知道這個秘密通行字，當alice每次登錄時，計算機都要求alice輸入通行字。利用單向函數(shù)的鑒別roger needham和mike guy意識到計算機沒有必要知道通行字。計算機只需有能力區(qū)別有效通行字和無效通行字就成。這種辦法很容易用單向函數(shù)來實現(xiàn)。計算機存儲通行字的單向函數(shù)而不是存儲通行字。（1）alice將她的通行字傳送給計算機。（2）計算機完成通行字的單向函數(shù)計算。（3）計算機把單向函數(shù)的運算結果和它以前存儲的值進行比較。由于計算機不再存儲每人的有效通行字表，所以某些人侵入計算機，并偷取通行字的威脅就減少了。由通行字的單向函數(shù)生成通行字表是沒用的，因為單向函數(shù)不可能逆向恢復出通行字

16、。字典式攻擊和salt用單向函數(shù)加密的通行字文件還是脆弱的。mallory在他的業(yè)余時間編制1，000，000個最常用的通行字表，他用單向函數(shù)對所有1，000，000個通行字進行運算，并將結果存儲起來。如果每個通行字大約是8個字節(jié)，運算結果的文件不會超過8m字節(jié)，幾張軟盤就能存下。現(xiàn)在mallory偷出加密的通行字文件。把加密的通行字和已加密的可能通行字文件進行比較，再觀察哪個能匹配。這就是字典式攻擊，它的成功率令人吃驚。salt是使這種攻擊更困難的一種方法。salt是一隨機字符串，它與通行字連接在一起，再用單向函數(shù)對其運算。然后將salt值和單向函數(shù)運算的結果存入主機數(shù)據(jù)庫中。如果可能的sa

17、lt值的數(shù)目足夠大的話，它實際上就消除了對常用通行字采用的字典式攻擊，因為mallory不得不產生每個可能的salt值的單向hash值。這是初始化矢量的簡單嘗試。這兒的關鍵是確信當mallory試圖破譯其他人的通行字時，他不得不每次試驗字典里的每個通行字的加密，而不是只對可能的通行字進行大量的預先計算。許多salt是必需的。大多數(shù)unix系統(tǒng)僅使用12比特的salt。即使那樣，daniel klein開發(fā)了一個猜測通行字的程序，在大約一星期里，經常能破譯出一個給定的系統(tǒng)中的40%的通行字。david feldmeier和philip karn編輯了大約732，000個常用的通行字表，表中的通行

18、字都和4096個可能的salt值中的每個值都有聯(lián)系。采用這張表，他們估計在一給定系統(tǒng)中，大約能夠破譯出30%的通行字。salt不是萬靈藥，增加salt的比特數(shù)不能解決所有問題。salt只防止對通行字文件采用的一般的字典式攻擊，不能防止對單個通行字的一致攻擊。在多個機器上有相同的通行字的人使人難以理解，因為這樣做并不比拙劣選用的通行字更好。skeyskey是一種鑒別程序這很容易理解。為了設置系統(tǒng)，alice輸入隨機數(shù)r，計算機計算f（r）、f（f（r）、f（f（f（r）等等大約100次。調用x1 ，x2 ，x3 ，。，x100這些數(shù)。計算機打印出這些數(shù)的列表，alice把這些數(shù)放入口袋妥善保管，

19、計算機也順利地在登錄數(shù)據(jù)庫中alice的名字后面存儲x101的值。當alice第一次登錄時，她輸入她的名字和x100，計算機計算f（x100），并把它和x101比較，如果它們匹配，那么證明alice身份是真的。然后，計算機用x101代替數(shù)據(jù)庫中的x100。alice將從她的列表中取消x100。alice每次登錄時，都輸入她的列表中未取消的最后的數(shù)xi，計算機計算f（xi），并和存儲在它的數(shù)據(jù)庫中的xi+1比較。因為每個數(shù)只被用一次，并且這個函數(shù)是單向的，所以eve不可能得到任何有用的信息。同樣的，數(shù)據(jù)庫對攻擊者也毫無用處。當然，當alice用完了她的列表上面的數(shù)后，她必須重新初始化系統(tǒng)。采用公

20、開密鑰密碼的鑒別謹慎而言，第一個協(xié)議有嚴重的安全問題。當alice將她的通行字發(fā)給她的主機時，能夠進入她的數(shù)據(jù)通道的任何人都可讀取她的通行字?？梢酝ㄟ^迂回的傳輸路徑訪問她的主機，在信道的任何一點eve都有可能竊聽alice的登錄序列。如果eve可以存取主機的處理機存儲器，那么在主機對通行字hash前，eve都能夠看到通行字。公開密鑰密碼能解決這個問題。主機保存每個用戶的公開密鑰文件，所有用戶保存自己的私鑰。這里給出一個協(xié)議。當?shù)卿洉r，協(xié)議按下面進行：（1）主機發(fā)送一個隨機字符串給alice。（2）alice用她的私鑰對此隨機字符串加密，并將此字符串他和她的名字一起傳送回主機。（3）主機在它的數(shù)

21、據(jù)庫中查找alice的公開密鑰，并用公開密鑰解密。（4）如果解密后的字符串與主機在第一步中發(fā)送給alice的字符串匹配，則允許alice訪問系統(tǒng)。沒有其他人能訪問alice的秘密密鑰，因此不可能有任何人冒充alice。更重要的是，alice決不會在傳輸線路上將她的私鑰發(fā)送給主機。竊聽這個交互過程中的eve，不可能得到任何信息使她能夠推導出alice的私鑰和冒充alice。私鑰既長又難記，它可能是由用戶的硬件或通信軟件自動處理的。這就需要一個alice信任的智能終端。但主機和通信線路都不必是安全的。安全的身份證明協(xié)議采用下面更復雜的形式：（1）alice根據(jù)一些隨機數(shù)和她的私鑰進行計算，并將結果

22、傳送給主機。（2）主機將一不同的隨機數(shù)傳送給alice。（3）alice根據(jù)這些隨機數(shù)（她產生的和她從主機接收的）和她的私鑰進行一些計算，并將結果傳送給主機。（4）主機用從alice那里接收來的各種數(shù)據(jù)和alice的公開密鑰進行計算，以此來驗證alice是否知道自己的私鑰。（5）如果她知道，則她的身份就被證實了。如果alice不相信主機，就像主機不相信她一樣，那么alice將要求主機用同樣方式證實其身份。用聯(lián)鎖協(xié)議互相鑒別alice和bob是想要互相鑒別的兩個用戶。他們每人有一個另一人知道的通行字：alice通行字是pa，bob的是pb。下面的協(xié)議是行不通的：（1）alice和bob的交換公開

23、密鑰。（2）alice用bob的公開密鑰加密pa，并將它傳送給bob。（3）bob用alice的公開密鑰加密pb，并發(fā)送給alice。（4）alice解密她在第（3）步中接受到的信息并驗證它是正確的。（5）bob解密他在第（2）步中接受到的信息并驗證它是正確的。mallory能夠成功發(fā)起“中間人攻擊”。（1）alice和bob交換公開密鑰。mallory截取這兩個報文，他用自己的公開密鑰代替bob的，并將它發(fā)送給alice。然后，他又用他的公開密鑰代替alice的，并將它發(fā)送給bob。（2）alice用“bob”的公開密鑰對pa加密，并發(fā)送給bob。mallory截取這個報文，用他的私鑰對pa

24、解密，再用bob的公開密鑰加密，并將它發(fā)送給bob。（3）bob用“alice”的公開密鑰對pb加密，并發(fā)送給alice。mallory截取它，用他的私鑰對pb解密。再用alice的公開密鑰對它加密，并發(fā)送給alice。（4）alice對pb解密，并驗證它是正確的。（5）bob對pa解密，并驗證它是正確的。從alice和bob處看并沒有什么不同，然而mallory知道pa和pb。秘密分割設想你已發(fā)明了一種新的、特別粘、特別甜的奶油餅的餡，或者你已經制作了一種碎肉夾餅的調味料。重要的是：你都必須保守秘密。你只能告訴最信賴的雇員各種成分準確的調合，但如果他們中的一個背叛到對手方時怎么辦呢？秘密就會

25、泄漏，不久，每個出售黃油的工廠將做出和你的一樣的調味料。這種情況就要求秘密分割。有各種方法把消息分割成許多碎。每一片本身并不代表什么，但把這些碎片放到一塊，消息就會重現(xiàn)出來。如果消息是一個秘方，每一個雇員有一部分，那么只有他們放在一起才能做出這種調味料。如果任意一雇員辭職帶走一部分制法，這個信息本身是毫無用處的。在兩個人之間分割一消息是最簡單的共享問題。下面是trent把一消息分割給alice和bob的一個協(xié)議：（1）trent產生一隨機比特串r，和消息m一樣長。（2）trent用r異或m得到s： m r = s（3）trent把r給alice，將s給bob。為了重構此消息，alice和bob

26、只需一起做一步：（4）alice和bob將他們的消息異或就可得到此消息： r s = m.如果做得適當，這種技術是絕對安全的。每一部分本身是毫無價值的。實質上，trent是用一次一密亂碼本加密消息，并將密文給一人，亂碼本給另一人。前面討論過一次一密亂碼本，它們具有完全保密性。無論有多大計算能力都不能根據(jù)消息碎片之一就確定出此消息來。把這種方案推廣到多人也是容易的。為了在多個人中分割一消息，將此消息與多個隨機比特異或成混合物。在下面的例子中，trent把信息劃分成四部分：（1）trent產生三個隨機比特串r、s、t，每個隨機串與消息m一樣長。（2）trent用這三個隨機串和m異或得到u： m r

27、 s t = u（3）trent將u給alice，s給bob，t給carol，u給dave。alice、bob和carol、dave在一起可以重構此消息：（4）alice、bob、carol和dave一起計算： r s t u = m這是一個裁決協(xié)議，trent有絕對的權力，并且能夠做他想做的任何事情。他可以把毫無意義的東西拿出來，并且申明是秘密的有效部分。在他們將秘密重構出來之前，沒有人能夠知道它。他可以分別交給alice、bob、carol和dave一部分，并且在以后告訴每一個人，只要alice、carol和dave三人就可以重構出此秘密，然后解雇bob。由于這是由trent分配的秘密，這

28、對于他恢復信息是沒有問題的。然而，這種協(xié)議存在一個問題：如果任何一部分丟失了，并且trent又不在，就等于將消息丟掉了。如果carol有調味料制法的一部分，他跑去為對手工作，并帶走了他的那一部分，那么其他人就很不幸了， carol不可能重新產生這個秘方，但alice、bob、dave在一起也不行。carol的那一部分對消息來說和其它部分的組合一樣重要。alice、bob和dave知道的僅是消息的長度，沒有其它更多的信息了。這是真的，因為r、s、t、u和m都有同樣的長度；見到他們中的任何一個都知道它的長度。記住，m不是通常單詞意義的分割，它是用隨機數(shù)異或的。你正在為核導彈安裝發(fā)射程序。你想確信一

29、個瘋子是不能夠啟動發(fā)射。你也想確信兩個瘋子也不能啟動發(fā)射。在你允許發(fā)射前，五個官員中至少有三個是瘋子。這是一個容易解決的問題。做一個機械發(fā)射控制器，給五個官員每人一把鑰匙，并且你在允許他們起爆時，要求至少三個官員的鑰匙插入合適的槽中。一個叫做門限方案門限方案的更復雜的共享方案，可在數(shù)學上做到這些甚至做得更多。起碼，你可以取任何消息（秘密的秘方，發(fā)射代碼，你的洗衣價目表），并把它分成n部分，每部分叫做它的“影子影子”或共享，這樣它們中的任何m部分能夠用來重構消息，更準確地說，這叫做（m,n）門限方案。拿（3，4）門限方案來說，trent可以將他的秘密調味料秘方分給alice、bob、carol和dave，這樣把他們中的任意三個“影子”放在一起就能重構消息。如果carol正在渡假，那么alice、bob和dave可以做這樣的事。如果bob被汽車撞了，那么alice、carol和dave能夠做這件事。然而如果carol正在渡假期間，bob被