AWSのMFAの仕組みを実装して読み解いてみた

AWSのMFAの仕組みを実装して読み解いてみた

こんにちは、奥です。
最近認証や認可の話題が度々でていますね。
ふとAWSのMFAはどのような実装になっているか気になったので調べて実装してみました。

目次

MFAについて

MFAの設定は済んでますか。もしまだの方や、うろ覚えの方がいましたらこちらの記事を先に見て設定することをお勧めします。

IAMユーザーのMFA(多要素認証)は有効になっていますか?現状を確認→是正→適切な状態を維持するまでの流れを整理してみた

MFAの設定が終わったところで、本題に入っていきましょう。
AWSの多要素認証のページを見るとこんなことが書いてあります。

オープン TOTP スタンダードをサポートするアプリケーションを実行するスマートフォンやタブレットをご使用ください。
https://aws.amazon.com/jp/iam/details/mfa/

オープン TOTP スタンダードは何かわからないですが、私たちは、MFAのためにAuthyやGoogle Authenticatorをスマートフォンにインストールしています。
なので、TOTPがMFAにとって非常に重要な何かなのでしょう。

TOTP(Time-Based One-Time Password Algorithm)

TOTPはRFC6238で策定されているOTP(ワンタイムパスワード)生成のアルゴリズムです。
AWSへのログイン時に入力する6桁の数字がOTPで、それを生成するためのアルゴリズムがTOTPです。
そして、このような流れでAuthyやGoogle Authenticatorを使用してログインしています。

123456はMFAクライアントアプリで表示された数字だと思ってください。
共通の秘密鍵と、UNIX時間を使用してOTP(123456)を生成しています。
クライアント、サーバ両者で同じようにOTPを生成して一致した場合に認証が完了します。

秘密鍵はいつ生成され、渡されているのでしょうか。
実はMFAクライアントアプリでQRコードを読み込んだ時に渡されています。

QRコードは、URIにパースされ、URIにクエリとして含まれている秘密鍵をMFAクライアントアプリは取得します。
Google AuthenticatiorのWikiにURIがどのようなフォーマットになっているか詳しく記載があります。

ここまでの話をまとめると、MFAはTOTPアルゴリズムを使用しています。
TOTPはクライアント、サーバサイドで時間と同じ秘密鍵を用いることで、認証を実装しています。

MFAで何をしているかなんとなく理解できたでしょうか。
ここまで理解できたのでついでにTOTPを実装して理解を深めましょう。

TOTPを実装する

RFCで仕様が公開されているので実装することも可能です。
今回はPythonを使用して実装していきます。
本記事に掲載されたコードは本番環境で使用しないでください。

TOTPは数式で表すとこのようになります。

\[ TOTP = HOTP(K, T) \]

\[ T = \frac{CurrentUnixTime - T0}{X} \]

Kは共有する秘密鍵ですが、それ以外はよくわかりませんね。
Tについては一旦置いといて、HOTPについて書いてみます。

HOTPはRFC4226で策定されたOTP生成のためのアルゴリズムです。
HOTPは認証回数と、秘密鍵を元にOTPを生成します。TOTPは内部でHOTPを使用しているので似ていますね。

HOTPは数式で表すとこのようになります。
Kが秘密鍵で、Cが認証回数です。

\[ HOTP(K,C) = Truncate(HMAC-SHA-1(K,C)) \]

これで何を実装すればいいかわかりましたね。
HMAC-SHA-1TruncateHOTPTOTPの順に実装していけばスッキリ作れそうです。

HMAC-SHA-1の実装

HMAC(Hash-based Message Authentication Code)は、秘密鍵とメッセージ、ハッシュ関数を元に、生成されるメッセージ認証符号です。
ハッシュ関数としてSHA-1を使用するので、HMAC-SHA-1と呼ばれています。

Pythonにはありがたいことに、標準ライブラリにHMACが含まれています。
なのでこれを使って実装していきます。
先ほど出てきた数式の、Kがgenerate_hsの第一引数、keyに、Cが第二引数のcounterに対応します。

def generate_hs(key: str, counter: int) -> bytes:
    msg: bytes = (counter).to_bytes(8, byteorder="big")
    return hmac.new(key.encode("utf-8"), msg=msg, digestmod=hashlib.sha1).digest()

秘密鍵とメッセージをバイト型に変換して、この部分でHMACを生成しています。
処理の都合的にバイト型だとありがたいので返り値には、バイト型に変換したものを渡しています。

return hmac.new(key.encode("utf-8"), msg=msg, digestmod=hashlib.sha1).digest()

Truncateの実装

Truncate関数は、先ほど生成した値を元にOTPを生成します。
まずは、先ほど生成したHMACの20文字目の下位4ビットを取り出します。
先ほど作成したgenerate_hsを使用して、HMACを求めます。

HS: bytes = generate_hs(key, counter)

HSの20文字目の値から、下位4ビットoffsetとして取り出します。

HS: bytes = generate_hs(key, counter)
offset: int = HS[19] & 0xF

ちょっとわかりづらいですね。
HSの中身を下記の内容で仮定しましょう。

   -------------------------------------------------------------
   | Byte Number                                               |
   -------------------------------------------------------------
   |00|01|02|03|04|05|06|07|08|09|10|11|12|13|14|15|16|17|18|19|
   -------------------------------------------------------------
   | Byte Value                                                |
   -------------------------------------------------------------
   |1f|86|98|69|0e|02|ca|16|61|85|50|ef|7f|19|da|8e|94|5b|55|5a|
   ----------------------------------------------------------**|

# https://tools.ietf.org/html/rfc4226

この場合、20文字目の値は0x5aですね。また、2進数に変換すると、01011010になります。

これの下位4ビット(1010)を取り出せばいいので、00001111と01011010でAND演算を行います。
AND演算は同じ位の値を比較してどちらも1なら1を、どちらか一方でも0の場合は0を返す演算です。
なので、00001010、10進数に変換すると10が返ってきます。

ここで、コードを見直してみましょう。

HS: bytes = generate_hs(key, counter)
offset: int = HS[19] & 0xF

20文字目と、0xF(00001111)をAND演算していますね。

これで取得できたoffsetの値を元にさらに計算を進めていきます。

HS: bytes = generate_hs(key, counter)
offset: int = HS[19] & 0xF
p: int = int.from_bytes(HS[offset : offset + 4], "big")

offsetの値から4つ分、HSから値を取り出します。そして終端の31ビットを取り出します。 先ほどと同じように、AND演算でマスクをかけます。
今回は31ビットなので16進数で0x7FFFFFFFですね。

HS: bytes = generate_hs(key, counter)
offset: int = HS[19] & 0xF
p: int = int.from_bytes(HS[offset : offset + 4], "big")
sNum: int = p & 0x7FFFFFFF

先ほどの図に当てはめて考えてみましょう。

   -------------------------------------------------------------
   | Byte Number                                               |
   -------------------------------------------------------------
   |00|01|02|03|04|05|06|07|08|09|10|11|12|13|14|15|16|17|18|19|
   -------------------------------------------------------------
   | Byte Value                                                |
   -------------------------------------------------------------
   |1f|86|98|69|0e|02|ca|16|61|85|50|ef|7f|19|da|8e|94|5b|55|5a|
   -------------------------------***********------------------|

# https://tools.ietf.org/html/rfc4226

HSの10から13までを取り出すので、0x500xef0x7f0x19が取り出されます。 0x50ef7f19と0x7FFFFFFFをAND演算すると、0x50ef7f19、10進数に変換すると1357872921が返ってきます。

最後に先ほど求めた値と、OTPの桁数を用いてOTPを生成します。

HS: bytes = generate_hs(key, counter)
digit: int = 6

offset: int = HS[19] & 0xF
p: int = int.from_bytes(HS[offset : offset + 4], "big")
sNum: int = p & 0x7FFFFFFF

OTP: int = sNum / 10 ** digit

digitはOTPの桁数のことで、6桁や8桁が一般的です。
10のdigit乗と、sNumで除算を行った剰余がOTPになります。

今まで使用してきた例だと、OTPは872921になります。

HOTPの実装の全体像

最終的にHOTPはこのようなコードで実装しました。  

import hmac
import hashlib


def dynamic_truncate(HS: bytes) -> int:
    offset: int = HS[19] & 0xF
    p: int = int.from_bytes(HS[offset : offset + 4], "big")
    return p & 0x7FFFFFFF


def generate_hs(key: str, counter: int) -> bytes:
    msg: bytes = (counter).to_bytes(8, byteorder="big")
    return hmac.new(key.encode("utf-8"), msg=msg, digestmod=hashlib.sha1).digest()


def HOTP(key: str, counter: int, digit: int = 6) -> int:
    hs: bytes = generate_hs(key, counter)
    Snum = dynamic_truncate(hs)
    return Snum % 10 ** digit

かなりシンプルに実装できてますね。

テストの実施

HOTPが正しく実装されているかテストを書いて確認しましょう。
先ほど作った、totp.pyのテストを下記のように実装しました。

RFC 4226のAppendix Dにテスト用の秘密鍵とHMAC、OTPが記載されています。
これを元にunittestを書いていきます。

import unittest
from totp import HOTP, generate_hs


class TestHOTP(unittest.TestCase):
    """
    values are from 'https://tools.ietf.org/html/rfc4226#page-32'
    """
    def testGenerate_hs(self):
        hmac = [
            (0, 1167930367309285312005596601021756572164281984176),
            (1, 671621272684320937409877521318622462759792358315),
            (2, 66650653283009457561317849190025484387936042820),
            (3, 586654741337511506906521291626811842010522418894),
            (4, 964926153040537641885976775533781669694032702748),
            (5, 933385863934924909351594421429601242960995615510),
            (6, 1076787520132409865560930714813912004980420801198),
            (7, 941885044401839697916538057165991173425022211834),
            (8, 155492813742301833322568025090426734566011253467),
            (9, 126829964866090503319337399760956829531729091045),
        ]
        for counter, hex_hmac in hmac:
            hs = generate_hs("12345678901234567890", counter)
            hs_decimal = int.from_bytes(hs, "big")
            self.assertEqual(hex_hmac, hs_decimal)

    def testHOTP(self):
        hotp_code = [
            (0, 755224),
            (1, 287082),
            (2, 359152),
            (3, 969429),
            (4, 338314),
            (5, 254676),
            (6, 287922),
            (7, 162583),
            (8, 399871),
            (9, 520489),
        ]
        for counter, code in hotp_code:
            self.assertEqual(code, HOTP("12345678901234567890", counter))


if __name__ == "__main__":
    unittest.main(verbosity=2)

テストが通るかを確認しましょう。

$ python test_totp.py
testGenerate_hs (__main__.TestHOTP) ... ok
testHOTP (__main__.TestHOTP) ... ok

----------------------------------------------------------------------
Ran 2 tests in 0.000s

OK

問題なさそうですね。

TOTPの実装

再度アルゴリズムを確認しましょう。

\[ T = \frac{CurrentUnixTime - T0}{X} \]

\[ TOTP = HOTP(K, T) \]

HOTPの部分はもう問題ありませんね。
それではT関数を確認して、TOTPを実装しましょう。
T関数に出てくる値は下記のようになっています。

説明
CurrentUnixTime 現在のUnix時間
T0 数え始めの時間 Unix時間を使うのが通常なので、0がデフォルト
X TOTPを再生成するまでの時間 30秒がデフォルト

T関数は簡単に実装できますね。
このようになります。

import time

def T(t0: int, interval_time: int) -> int:
    now: int = int(time.time())
    return int(now - t0 / interval_time)

ここまでできたらTOTPはすぐに実装できますね。

import time

def T(t0: int, interval_time: int) -> int:
    now: int = int(time.time())
    return int(now - t0 / interval_time)

def TOTP(key: str, t0: int = 0, interval_time: int = 30):
    return HOTP(key, T(t0, interval_time))

全体像

コードの全体像は下記のようになっています。

さいごに

TOTP、HOTPともにアルゴリズム自体が非常にシンプルでわかりやすいものでした。
普段気にしない内容ですが、実装してみることでMFAクライアントで何をしているかがよくわかりました。