轉載自：http://blog.seetee.me/archives/73.html
我們往往會在不同的網站上使用相同的密碼，這樣一旦一個網站賬戶的密碼泄露，就會危及到其他使用相同密碼的賬戶的安全，這也是最近的密碼泄露事件造成如此大影響的原因。為了解決這個問題，一些網站在登錄時要求除了輸入賬戶密碼之外，還需要輸入另一個一次性密碼。銀行常用的動態口令卡就是這種一次性密碼的例子，在線支付網站的一次性短信密碼則是另一種實現。
Google現在也推薦用戶啟用兩步驗證（Two-step verification）功能（Youtube上的視頻介紹），并且除了以短信或者電話的方式發送一次性密碼之外，還提供了另一種基于時間的一次性密碼（Time-based One-time Password，簡稱TOTP），只需要在手機上安裝密碼生成應用程序，就可以生成一個隨著時間變化的一次性密碼，用于帳戶驗證，而且這個應用程序不需要連接網絡即可工作。仔細看了看這個方案的實現原理，發現挺有意思的。下面簡單介紹一下。
Google的兩步驗證算法源自另一種名為HMAC-Based One-Time Password的算法，簡稱HOTP。HOTP的工作原理如下：
客戶端和服務器事先協商好一個密鑰K，用于一次性密碼的生成過程，此密鑰不被任何第三方所知道。此外，客戶端和服務器各有一個計數器C，并且事先將計數值同步。
進行驗證時，客戶端對密鑰和計數器的組合(K,C)使用HMAC（Hash-based Message Authentication Code）算法計算一次性密碼，公式如下：
HOTP(K,C) = Truncate(HMAC-SHA-1(K,C))
上面采用了HMAC-SHA-1，當然也可以使用HMAC-MD5等。HMAC算法得出的值位數比較多，不方便用戶輸入，因此需要截斷（Truncate）成為一組不太長十進制數（例如6位）。計算完成之后客戶端計數器C計數值加1。用戶將這一組十進制數輸入并且提交之后，服務器端同樣的計算，并且與用戶提交的數值比較，如果相同，則驗證通過，服務器端將計數值C增加1。如果不相同，則驗證失敗。
這里的一個比較有趣的問題是，如果驗證失敗或者客戶端不小心多進行了一次生成密碼操作，那么服務器和客戶端之間的計數器C將不再同步，因此需要有一個重新同步（Resynchronization）的機制。這里不作具體介紹，詳情可以參看RFC 4226。
介紹完了HOTP，Time-based One-time Password（TOTP）也就容易理解了。TOTP將HOTP中的計數器C用當前時間T來替代，于是就得到了隨著時間變化的一次性密碼。非常有趣吧！
雖然原理很簡單，但是用時間來替代計數器會有一些特殊的問題，這些問題也很有意思，我們選取幾個進行一下探討。
首先，時間T的值怎么選取？因為時間每時每刻都在變化，如果選擇一個變化太快的T（例如從某一時間點開始的秒數），那么用戶來不及輸入密碼。如果選擇一個變化太慢的T（例如從某一時間點開始的小時數），那么第三方攻擊者就有充足的時間去嘗試所有可能的一次性密碼（試想6位數字的一次性密碼僅僅有10^6種組合），降低了密碼的安全性。除此之外，變化太慢的T還會導致另一個問題。如果用戶需要在短時間內兩次登錄賬戶，由于密碼是一次性的不可重用，用戶必須等到下一個一次性密碼被生成時才能登錄，這意味著最多需要等待59分59秒！這顯然不可接受。綜合以上考慮，Google選擇了30秒作為時間片，T的數值為從Unix epoch（1970年1月1日 00:00:00）來經歷的30秒的個數。
第二個問題是，由于網絡延時，用戶輸入延遲等因素，可能當服務器端接收到一次性密碼時，T的數值已經改變，這樣就會導致服務器計算的一次性密碼值與用戶輸入的不同，驗證失敗。解決這個問題個一個方法是，服務器計算當前時間片以及前面的n個時間片內的一次性密碼值，只要其中有一個與用戶輸入的密碼相同，則驗證通過。當然，n不能太大，否則會降低安全性。
事實上，這個方法還有一個另外的功能。我們知道如果客戶端和服務器的時鐘有偏差，會造成與上面類似的問題，也就是客戶端生成的密碼和服務端生成的密碼不一致。但是，如果服務器通過計算前n個時間片的密碼并且成功驗證之后，服務器就知道了客戶端的時鐘偏差。因此，下一次驗證時，服務器就可以直接將偏差考慮在內進行計算，而不需要進行n次計算。
以上就是Google兩步驗證的工作原理，推薦大家使用，這確實是保護帳戶安全的利器。
參考資料
- TOTP: Time-based One-time Password Algorithm, RFC Draft, http://tools.ietf.org/id/draft-mraihi-totp-timebased-06.html
- HOTP: An HMAC-Based One-Time Password Algorithm, RFC 4226, http://tools.ietf.org/html/rfc4226
- Google Authenticator project, http://code.google.com/p/google-authenticator/