多步驗證那些事
作者 小山（ArcBlock 後端工程師）
現如今，越來越多的網站開啟了多步驗證模式進行登入。在 ArcBlock，我們開發的 BlockAuth 模組就很好地支援了 MFA，讓開發者可以很容易在自己開發的區塊鏈應用中使用多步驗證來提高安全性。
開啟驗證時候的 QR Code 到底藏了什麼不能說的祕密？手機上身分驗證器的核心功能只要6行程式碼就能實現？多步驗證的過程中蘊藏了哪些有趣的密碼學原理？多步驗證安全嗎？如何破解多步驗證？本文將和你聊聊多步驗證那些事。
什麼是多步驗證？
多步驗證即 Multi-Factor Authentication（MFA），顧名思義，就是需要進行多步的驗證。如果只驗證兩步，那就叫兩步驗證 Two-Factor Authentication（2FA）。
以兩步驗證為例。當我們登入 GitHub 的時候，首先輸入使用者名稱和密碼進行第一步驗證；接下來輸入手機上的身分驗證器 app 所產生的六位數密碼進行第二步驗證，之後便可順利登入。
多步驗證背後用到了不少密碼學的知識，還有一系列 RFC 的規範。
一次性密碼 otp
我們把時間拉回到1998年，IETF 發布了 rfc 2289。這套規範定義了一次性密碼（one-time password, otp）。為什麼要用一次性密碼呢？因為當使用者透過使用者名稱和密碼進行登入時，如果密碼一旦被取得，駭客就可以用該密碼進行登入，這叫做重放攻擊。如何避免重放攻擊呢？用一次性密碼就行了。一次性密碼就像免洗筷一樣，用完丟掉即可，別人撿起來也沒什麼用。
MD5 ENCODINGS
Pass Phrase Seed Cnt Hex Six Word Format
====================================================================================
This is a test. TeSt 0 9E87 6134 D904 99DD INCH SEA ANNE LONG AHEM TOUR
This is a test. TeSt 1 7965 E054 36F5 029F EASE OIL FUM CURE AWRY AVIS
This is a test. TeSt 99 50FE 1962 C496 5880 BAIL TUFT BITS GANG CHEF THY
AbCdEfGhIjK alpha1 0 8706 6DD9 644B F206 FULL PEW DOWN ONCE MORT ARC
AbCdEfGhIjK alpha1 1 7CD3 4C10 40AD D14B FACT HOOF AT FIST SITE KENT
AbCdEfGhIjK alpha1 99 5AA3 7A81 F212 146C BODE HOP JAKE STOW JUT RAP
OTP's are good correct 0 F205 7539 43DE 4CF9 ULAN NEW ARMY FUSE SUIT EYED
OTP's are good correct 1 DDCD AC95 6F23 4937 SKIM CULT LOB SLAM POE HOWL
OTP's are good correct 99 B203 E28F A525 BE47 LONG IVY JULY AJAR BOND LEE這是 RFC 裡給出的一個例子。當伺服器選定一個密碼、種子和計數器時，會產生一個固定長度的二進位數，透過查表得到6個由大寫字母組成的字串，這就是一次性密碼。使用者輸入這些字串來進行登入，用後即棄。伺服器的計數器改變後，下次再登入會產生另一個一次性密碼。
1998年那時網際網路才剛興起，有個使用者名稱和密碼登入就不錯了，用一次性密碼登入還不是很流行，而且使用者每次要輸入6個英文單字，比較麻煩。於是2005年 IETF 又發布了一套 rfc 4226，定義了基於 HMAC 的一次性密碼（hmac-based one-time password, hotp）。HMAC 又是什麼呢？
hmac
直接講 HMAC 是什麼會比較沒有上下文，我們先問自己一個問題：我們為什麼需要雜湊函式？
假設 Alice 要向 Bob 傳送一則訊息 show me the money。當 Bob 收到該訊息的時候，他怎麼知道這則訊息在傳送的過程中沒有被人竄改過？於是他和 Alice 商量了一下，傳送訊息時，不僅傳送訊息，再附加上該訊息的雜湊值。雜湊值就是對於任意輸入，雜湊函式會產生一個固定長度的輸出。當 Bob 收到訊息的時候，他也進行一次雜湊計算，如果他算出來的雜湊值和 Alice 傳過來的雜湊值相符，就表示該訊息沒有被竄改過。
show me the money
alice ------------------------------------------------------------------> bob
3f3a323ba2bc但是這樣會有一個問題。假設 Eve 在監聽 Alice 與 Bob 的通訊，她可以把 Alice 傳送的訊息改成 show me the honey，然後她把改過的訊息的雜湊值算出來，附加後傳給 Bob。當 Bob 收到訊息並進行雜湊計算驗證時，發現和 Eve 傳過來的雜湊值一致。於是 Bob 認為這則訊息沒有被竄改過。但其實這並不是 Alice 傳送的原始訊息。
show me the money show me the honey
alice ----------------------------> eve ----------------------------> bob
3f3a323ba2bc 37954357d876也就是說，單靠雜湊值只能保證資料的完整性，卻不能保證資料的真實性，因為任何人都可以計算雜湊值。那麼有什麼方法能既保證資料完整性，又保證資料真實性呢？
一個可能的解決方案
我們還是來傳送 show me the money 這則訊息，但是這次我們選一個金鑰 rA9。演算法很簡單，把金鑰和要傳送的資訊連起來，計算一次雜湊；接著把金鑰和剛才算出的雜湊連起來，再計算一次雜湊。我們把第二次的雜湊值和訊息一起傳送給 Bob。如下圖所示：
sha
rA9show me the money -------> f023a7d109f1
sha
rA9f023a7d109f1 -------> b15c701d5e63
show me the money
alice ------------------------------------------------------------------> bob
rA9 b15c701d5e63 rA9我們假設 Alice 和 Bob 都有該金鑰 rA9，當 Bob 收到訊息和雜湊的時候，也做兩次雜湊並比較。如果一致，就證明訊息不僅沒有被竄改過，而且傳送者擁有 rA9 這個金鑰，也就是說訊息是從 Alice 傳來的。
如果此時 Eve 在中間監聽，她可以竄改訊息，但是因為她沒有金鑰 rA9，所以她無法計算出新的雜湊值。因此當 Bob 收到訊息時驗證一下，會發現雜湊不一致，於是他可以得出結論：該訊息被竄改過了。
show me the money show me the honey
alice ----------------------------> eve ----------------------------> bob
rA9 b15c701d5e63 b15c701d5e63 rA9
233999963a1dhotp
剛才描述的演算法，就是 HMAC 的演算法。了解這一點之後，我們就可以描述一下基於 HMAC 的一次性密碼（HOTP）演算法。
rA9
hmac(sha,"rA9","0000000000000000")
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
d8 41 ef 1c 96 ac 02 0c d1 a3 32 06 15 58 ec 69 4d d2 3f 32
*
** ** ** ** 2
ef 1c 96 ac
1110 1111 0001 1100 1001 0110 1010 1100
110 1111 0001 1100 1001 0110 1010 1100
1864144556
144556演算法如上圖所示，首先選定一個金鑰 rA9。用 HMAC 演算法計算出一個訊息驗證碼。這裡我們不再用 show me the money，而是用一個32位元的整數，上面的例子是用0來計算。算出一個20位元組的驗證碼後，我們取最後一個位元組的後半個位元組，也就是2，找到索引2之後的4個位元組，也就是 ef 1c 96 ac，把該32位元用二進位表示出來，之後去掉最左邊一位的符號位，剩下31位，把該二進位對應的十進位寫出來就是 1864144556，取末尾的6位即是最後結果 144556。這個數字就是我們平日用身分驗證器產生的6位數一次性密碼。
totp
基於 HMAC 的一次性密碼需要用一個整數作為參數，伺服器和用戶端之間需要對這個計數器進行同步，而我們更常用的一次性密碼則是基於時間的（time-based otp, totp）。
時間在電腦中的儲存方式其實就是一個整數，Unix 時間表示從1970年1月1日0點0時0分開始算起，到目前時間所經過的秒數。整個 TOTP 演算法如下：
unix epoch time
1970-01-01 00:00:00 0
2018-10-23 17:00:00 1540314000
2038-01-19 03:14:07 2147483647
1901-12-13 20:45:52 -2147483648
hotp("rA9",1540314000/30)
386452把目前時間的 Unix 時間計算出來，除以30後傳給 HOTP 函式即可。為什麼要除以30呢？因為使用者輸入這個六位數密碼需要時間，給個30秒時間應該足夠了，30秒過後這個一次性密碼就失效了。
如何交換金鑰
還記得之前的金鑰 rA9 嗎？伺服器和使用者之間是如何交換該金鑰的？這就是啟用多步驗證時所出現的 QR Code 裡面的內容。
該 QR Code 是一種叫做金鑰 URI 格式的編碼，長這樣：
otpauth://totp/GitHub:hellokitty?secret=4fakhx6cibvwwngp&issuer=GitHub其中的 secret 就是伺服器產生的金鑰的 Base32 編碼。
一個簡單身分驗證器的實作
mfa.erl
totp(Key0) ->
T = calendar:datetime_to_gregorian_seconds(calendar:now_to_datetime(erlang:timestamp())) - ?epoch,
Key = decode32(string:uppercase(Key0)),
hotp(Key,T div 30).
hotp(Key,C) ->
<<_:156,Sz:4>> = Hmac = crypto:hmac(sha,Key,<<C:64>>),
<<_:Sz/binary,_:1,N:31,_/binary>> = Hmac,
N rem 1000000.這是一個 TOTP/HOTP 的 Erlang 實作，核心部分只要6行程式碼，執行一下看看：
$ cat ~/.mfa/config
{github,"somerandpassword"}.
{gitlab,"somecoolpassword"}.
{google,"somegoodpassword"}.
$ escript mfa.erl
github: 583309, valid in 26s
gitlab: 166210, valid in 26s
google: 704368, valid in 26s多步驗證安全嗎？
我們可以看到，實作多步驗證並不困難，那麼多步驗證到底有多安全？我們可以看看如何破解多步驗證。因為多步驗證的核心其實就是 HMAC，破解 HMAC 的唯一方法就是用暴力方式破解金鑰。我們可以透過寫一個小程式來模擬破解過程。
先隨機產生一個3位元組長的金鑰，再透過暴力演算法計算，用1個 CPU 大約16秒可以破解。
$ erl
1> hack:run().
Key is <<91,101,252>>, hotp for 73 is 076127
potential key found <<12,243,176>>, hotp is 076127
potential key found <<41,163,60>>, hotp is 076127
potential key found <<54,214,149>>, hotp is 076127
potential key found <<57,134,46>>, hotp is 076127
potential key found <<57,206,238>>, hotp is 076127
potential key found <<68,189,61>>, hotp is 076127
potential key found <<70,78,253>>, hotp is 076127
potential key found <<90,172,149>>, hotp is 076127
potential key found <<91,101,252>>, hotp is 076127
potential key found <<96,226,141>>, hotp is 076127
...
*** found key <<91,101,252>> in 16s ***因為是用 Erlang，所以可以稍微修改一下程式，用全部的 CPU 來進行破解：
$ erl
1> phack:run(3).
Started 12 worker processes.
Random generated key is <<154,226,246>>, hotp for 360 is 917202
potential key <<22,72,233>> found by worker <0.172.0>, hotp is 917202
potential key <<67,6,87>> found by worker <0.170.0>, hotp is 917202
potential key <<110,133,18>> found by worker <0.168.0>, hotp is 917202
potential key <<153,173,223>> found by worker <0.166.0>, hotp is 917202
potential key <<197,0,181>> found by worker <0.164.0>, hotp is 917202
potential key <<154,226,246>> found by worker <0.166.0>, hotp is 917202
key <<154,226,246>> found by worker <0.166.0> in 1s在這裡，我們在一台6核心筆記型電腦上執行，等同於12個 CPU，速度快了12倍，大約1秒就破解了。
當然破解的只是3個位元組的金鑰。如果我們嘗試破解4個位元組：
2> phack:run(4).
Started 12 worker processes.
Random generated key is <<81,10,150,35>>, hotp for 375 is 655173
potential key <<170,170,211,211>> found by worker <0.111.0>, hotp is 655173
potential key <<64,3,113,77>> found by worker <0.116.0>, hotp is 655173
potential key <<106,175,21,120>> found by worker <0.114.0>, hotp is 655173
potential key <<0,5,110,147>> found by worker <0.119.0>, hotp is 655173
potential key <<149,93,101,149>> found by worker <0.112.0>, hotp is 655173
potential key <<170,179,226,52>> found by worker <0.111.0>, hotp is 655173
potential key <<213,98,135,55>> found by worker <0.109.0>, hotp is 655173
potential key <<0,21,166,137>> found by worker <0.119.0>, hotp is 655173
potential key <<149,107,68,31>> found by worker <0.112.0>, hotp is 655173
...
key <<81,10,150,35>> found by worker <0.116.0> in 849s花了大概14分鐘。每增加一個位元組，就相當於增加 2^8=256 倍破解的難度。下表展示了在一台筆記型電腦上破解 MFA 要花的時間。
key length bits crack time
1 8 ~0s
2 16 ~0s
3 24 ~16s
4 32 ~1.1h
5 40 ~11.7d
6 48 ~8.2y
7 56 ~2099y
8 64 ~537ky
9 72 ~137my
10 80 ~35kmy可以看到，10位元組的金鑰透過暴力方式根本無法破解。目前大多數網站都會用至少10個位元組作為伺服器隨機產生的金鑰。
以上所有的程式碼都可以在 GitHub 上找到：https://github.com/sunboshan/mfa。
和本文配套的影片講解可以在這裡找到。
希望透過本篇部落格讓大家對多步驗證有所了解。在 ArcBlock，我們的工程師會對我們所用的工具和技術進行總結，並且分享給大家，希望我們可以一起共同進步。我們還在招募人才，有興趣的朋友請點擊這裡。