多要素認証を読み解く
著者 小山（ArcBlock バックエンドエンジニア）
現在、ログイン時に多要素認証を採用するウェブサイトが増えています。ArcBlock が開発した BlockAuth モジュールも MFA をしっかりサポートしており、開発者は自分のブロックチェーンアプリケーションに多要素認証を簡単に導入して、セキュリティを高めることができます。
認証を有効にするときの QR コードには、いったいどんな秘密が隠されているのでしょうか？スマートフォンの認証アプリの中核機能は、わずか6行のコードで実装できるのでしょうか？多要素認証の過程には、どのような興味深い暗号学の原理が隠されているのでしょうか？多要素認証は安全なのでしょうか？多要素認証を破るにはどうすればよいのでしょうか？この記事では、多要素認証について詳しくお話しします。
多要素認証とは？
多要素認証は Multi-Factor Authentication（MFA）のことで、その名のとおり複数段階の認証を行うものです。2段階だけを認証する場合は、二要素認証 Two-Factor Authentication（2FA）と呼びます。
二要素認証を例に説明します。GitHub にログインするとき、まずユーザー名とパスワードを入力して第1段階の認証を行います。次に、スマートフォンの認証アプリが生成した6桁のパスワードを入力して第2段階の認証を行うと、無事にログインできます。
多要素認証の背後では、多くの暗号学の知識と一連の 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 は相談し、メッセージを送る際に、メッセージだけでなくそのハッシュ値も添付することにしました。ハッシュ値とは、任意の入力に対してハッシュ関数が生成する固定長の出力です。Bob はメッセージを受信すると自分でもハッシュを計算し、その値が Alice から送られてきたハッシュ値と一致すれば、メッセージは改ざんされていないと判断します。
show me the money
alice ------------------------------------------------------------------> bob
3f3a323ba2bcしかし、これには問題があります。Eve が Alice と Bob の通信を盗聴しているとします。Eve は 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 という鍵を選びます。アルゴリズムは簡単です。まず鍵と送信するメッセージを連結してハッシュを1回計算します。次に、鍵と先ほど計算したハッシュを連結し、もう一度ハッシュを計算します。2回目のハッシュ値をメッセージと一緒に Bob へ送ります。次の図のとおりです。
sha
rA9show me the money -------> f023a7d109f1
sha
rA9f023a7d109f1 -------> b15c701d5e63
show me the money
alice ------------------------------------------------------------------> bob
rA9 b15c701d5e63 rA9Alice と Bob の両方が鍵 rA9 を持っているとします。Bob はメッセージとハッシュを受信すると、自分でも2回ハッシュを計算して比較します。一致すれば、メッセージが改ざんされていないだけでなく、送信者が鍵 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で割るのでしょうか？ユーザーがこの6桁のパスワードを入力するには時間が必要であり、30秒あれば十分と考えられるからです。30秒が過ぎると、このワンタイムパスワードは無効になります。
鍵を交換する方法
先ほどの鍵 rA9 を覚えていますか？サーバーとユーザーの間では、どのようにこの鍵を交換するのでしょうか？その答えが、多要素認証を有効にするときに表示される QR コードの内容です。
この QR コードは、キー 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分かかりました。1バイト増えるごとに、解読の難しさは 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 では、エンジニアが使用しているツールや技術をまとめ、皆さんと共有しています。ともに成長していけることを願っています。現在も採用を行っていますので、興味のある方はこちらをクリックしてください。