該文章來自我的博客
摘要：本文根據(jù) RFC4226 和 RFC6238 文檔咪啡，詳細的介紹 HOTP 和 TOTP 算法的原理和實現(xiàn)。
兩步驗證已經(jīng)被廣泛應用于各種互聯(lián)網(wǎng)應用當中暮屡，用來提供安全性撤摸。對于如何使用兩步驗證，大家并不陌生褒纲，無非是開啟兩步驗證准夷，然后出現(xiàn)一個二維碼，使用支持兩步驗證的移動應用比如 Google Authenticator 或者 LassPass Authenticator 掃一下二維碼莺掠。這時候應用會出現(xiàn)一個6位數(shù)的一次性密碼衫嵌，首次需要輸入驗證從而完成開啟過程。以后在登陸的時候彻秆，除了輸入用戶名和密碼外楔绞，還需要把當前的移動應用上顯示的6位數(shù)編碼輸入才能完成登陸。
這個過程的背后主要由兩個算法來支撐：HOTP 和 TOTP唇兑。也分別對應著兩份 RFC 協(xié)議 RFC4266 和 RFC6238酒朵。前者是 HOTP 的標準，后者是 TOTP 的標準扎附。本文將使用圖文并茂的方式詳細介紹 HOTP 和 TOTP 的算法原理蔫耽，并在最后分析其安全性。當然所有內(nèi)容都是基于協(xié)議的留夜，通過自己的理解更加直觀的表達出來匙铡。
協(xié)議解決的核心問題
通過前面兩步驗證的使用場景分析，不難看出問題的核心在于如何能夠讓用戶手機應用產(chǎn)生的驗證碼和服務器產(chǎn)生的驗證碼一致香伴，或者是在一定范圍內(nèi)一致慰枕。參考下圖
所以我們的算法就是在解決如何更好的生成這個驗證碼具则，既能保證服務器端和客戶端同步即纲，還能保證驗證碼不重復并且不容易被別人反向破解出共享密鑰。其中如果是計數(shù)博肋，則是 HOTP低斋， 如果是使用時間來生成驗證碼，則是 TOTP匪凡。
HOTP 算法圖解
符號定義
對于 HOTP膊畴，通過上圖我們已經(jīng)看到輸入算法的主要有兩個元素，一個是共享密鑰病游，另外一個是計數(shù)唇跨。在 RFC 算法中用一下字母表示：
K 共享密鑰稠通，這個密鑰的要求是每個 HOTP 的生成器都必須是唯一的。一般我們都是通過一些隨機生成種子的庫來實現(xiàn)买猖。
C 計數(shù)器改橘，RFC 中把它稱為移動元素（moving factor）是一個 8個 byte的數(shù)值，而且需要服務器和客戶端同步玉控。
另外一個參數(shù)比較好理解飞主，
Digit 表示產(chǎn)生的驗證碼的位數(shù)
最后兩個參數(shù)可能暫時不好理解，我們先放在這高诺，等用到在解釋
T 稱為限制參數(shù)（Throttling Parameter）表示當用戶嘗試 T 次 OTP 授權(quán)后不成功將拒絕該用戶的連接碌识。
s 稱為重新同步參數(shù)（Resynchronization Parameter）表示服務器將通過累加計數(shù)器，來嘗試多次驗證輸入的一次性密碼虱而，而這個嘗試的次數(shù)及為 s筏餐。該參數(shù)主要是有效的容忍用戶在客戶端無意中生成了額外不用于驗證的驗證碼，導致客戶端和服務端不一致牡拇，但同時也限制了用戶無限制的生成不用于驗證的一次性密碼胖烛。
算法流程
核心步驟主要是使用 K C 和 Digit。
第一步：使用 HMAC-SHA-1 算法基于 K 和 C 生成一個20個字節(jié)的十六進制字符串（HS）诅迷。關于如何生成這個是另外一個協(xié)議來規(guī)定的佩番，RFC 2104 HMAC Keyed-Hashing for Message Authentication. 實際上這里的算法并不唯一，還可以使用 HMAC-SHA-256 和 HMAC-SHA-512 生成更長的序列罢杉。對應到協(xié)議中的算法標識就是
HS = HMAC-SHA-1(K,C)
第二步：選擇這個20個字節(jié)的十六進制字符串（HS 下文使用 HS 代替 ）的最后一個字節(jié)趟畏，取其低4位數(shù)并轉(zhuǎn)化為十進制。比如圖中的例子滩租，第二個字節(jié)是 5a赋秀，第四位就是 a，十六進制也就是 0xa律想，轉(zhuǎn)化為十進制就是 10猎莲。該數(shù)字我們定義為 Offset，也就是偏移量技即。
第三步：根據(jù)偏移量 Offset著洼，我們從 HS 中的第 10（偏移量）個字節(jié)開始選取 4 個字節(jié)，作為我們生成 OTP 的基礎數(shù)據(jù)而叼。圖中例子就是選擇 50ef7f19身笤，十六進制表示就是 0x50ef7f19，我們成為 Sbits
以上兩步在協(xié)議中的成為 Dynamic Truncation （DT）算法葵陵，具體參考以下偽代碼：
Let Sbits = DT(HS) // DT, defined below,
// returns a 31-bit string
展開就是
DT(String) // String = String[0]...String[19]
Let OffsetBits be the low-order 4 bits of String[19]
Offset = StToNum(OffsetBits) // 0 <= OffSet <= 15
Let P = String[OffSet]...String[OffSet+3]
Return the Last 31 bits of P
第四步：將上一步4個字節(jié)的十六進制字符串 Sbits 轉(zhuǎn)化為十進制液荸，然后用該十進制數(shù)對 10的Digit次冪 進行取模運算叫编。其原理很簡單根據(jù)取模運算的性質(zhì)滚躯，比如 比10大的數(shù) MOD 10 結(jié)果必然是 0到9僧鲁， MOD 100 結(jié)果必然是 0-99并扇。圖中的例子，50ef7f19 轉(zhuǎn)化為十進制為 1357872921文搂，然后如果需要6位 OTP 驗證碼响迂，則 1357872921 MOD 10^6 = 872921。 872921 就是我們最終生成的 OTP细疚。
對應到協(xié)議中的算法為：
Let Snum = StToNum(Sbits) // Convert S to a number in
// 0...2^{31}-1
Return D = Snum mod 10^Digit // D is a number in the range
// 0...10^{Digit}-1
這一步可能還需要注意一點就是圖中案例 Digit 不能超過10蔗彤，因為即使超過10，
1357872921 取模后也不會超過10位了疯兼。所以如果我們希望獲取更長的驗證碼然遏，需要在三步中拿到更多的十六進制字節(jié)，從而得到更大的十進制數(shù)吧彪。這個十進制決定了生成的 OTP 編碼的長度待侵。
TOTP 算法圖解
在 HOTP 算法的基礎上，對于 TOTP 算法的解釋是不難了姨裸，因為 TOTP 實際上是基礎 HOTP 的秧倾，只不過 HOTP 的計數(shù)器在 TOTP 中不再是直接的計數(shù)器了，而是使用時間來簡介計數(shù)的傀缩。下圖將會詳細介紹 TOTP 是如何在 HOTP 基礎上使用時間來計數(shù)的那先。
符號定義
時間窗口 X ：表示多長時間算作計數(shù)器的一步，通常會設為30秒
初始計數(shù)時間戳 $T_0$： 使用 Unix 時間戳來表示 OTP 生成的時候的初始計數(shù)時間赡艰。
算法流程
TOTP 算法的關鍵在于如何更具當前時間和時間窗口計算出計數(shù)售淡，也就是如何根據(jù)當前時間和 X 來計算 HOTP 算法中的 C。
HOTP 算法中的 C 是使用當前 Unix 時間戳 減去初始計數(shù)時間戳慷垮，然后除以時間窗口而獲得的揖闸。
算法安全性分析
上一節(jié)我們的算法中有兩個參數(shù)沒有用，T 和 s料身。這兩個參數(shù)對安全有重要的作用汤纸。
官方協(xié)議在這里給出了5點安全要求，其中第一點是協(xié)議本身的要求芹血，理論上進行約束贮泞，我們主要關心另外4點，分別是 HOTP 的驗證祟牲，限制訪問參數(shù)隙畜，重新同步參數(shù)以及共享密鑰的管理。
對于二步驗證的安全問題實際上就是如何保證第二步驗證盡可能不被攻擊的前提下向用戶提供更方便的服務说贝。
通過下圖我們可以詳細的了解 HOTP 的驗證過程，同時還可以了解參數(shù) s 和 T 的用途慎颗。
如果用戶嚴格按照生成一次 OTP乡恕，然后驗證一次的話言询，服務器直接可以驗證成功。因為算法將會輸入相同的參數(shù)傲宜。
如果用戶無意間多生成了若干次 OTP 但是沒有用來驗證运杭，服務器和客戶端就產(chǎn)生差異，這時候服務器端會自動累積計數(shù)器來嘗試匹配用戶輸入的 OTP函卒，但是這種嘗試是有限制的辆憔，這也就是前面說到的參數(shù) s 的作用。一旦服務器嘗試 s 次仍未匹配成功报嵌，那么就會通知客戶端需要重新生成驗證來驗證虱咧，只要驗證成功。
協(xié)議中對于參數(shù) s 給出的建議是：服務器建議設置該參數(shù)锚国，但是在保證可用性的前提下腕巡，盡可能小。另外還可以要求用戶輸入一個 HOTP 序列（比如連續(xù)生成多個 OTP 發(fā)送到服務器進行驗證）來進行重新同步計數(shù)器血筑。
既然涉及到重試绘沉，服務器同樣對重試次數(shù)有所限制，從而防止暴力破解豺总。這里當用戶重試次數(shù)超過了閾值 T车伞，服務器就應該將該賬號標記為有安全風險，需要提醒用戶喻喳。
協(xié)議中對個參數(shù) T 給出的建議是：同樣 T 也不建議設的很大帖世。另外還提供了另外一個基于延時的策略還防止暴力破解攻擊，服務器設置一個懲罰時間沸枯，一旦用戶驗證失敗日矫，需要在懲罰時間乘以失敗次數(shù)的時間內(nèi)禁止用戶重新嘗試驗證。這個延時需要跨不同的登陸會話绑榴，以防止并發(fā)的攻擊哪轿。
總結(jié)
通過上面的圖解，基本解釋了 HOTP 和 TOTP 兩種算法的關鍵步驟翔怎，并且通過驗證的場景對其安全要求進行了分析窃诉。
