TOTPを完全に理解した

こんばんは。@Esperna です。
今回も車輪の再発明ながら、自身の理解を深めるためTOTPについて書きます。

# 背景

何年か前から２段階認証を目にする機会が増えてきた気がします。
[Googleが2021年5月6日に２段階認証](https://gigazine.net/news/20210507-google-two-step-verification-phone/)を呼びかけてたんですね。
アカウントにログインしようとすると、メッセージアプリに番号が飛んでくるやつですね。
この番号がどうやって生成されてるのか気になったので調べてみました。

## TOTP

上記の番号を生成するのにTOTP(Time Based One Time Password)というアルゴリズムを使っているそうです。どんなアルゴリズムか簡単に言うと秘密鍵とパスワードの更新回数のカウント(unixtimeでの経過時間をパスワード更新周期で割ったもの)を入力として任意の桁数の番号を作るアルゴリズムです。

[RFC4226](https://www.rfc-editor.org/rfc/rfc4226)や[RFC6238](https://www.rfc-editor.org/rfc/rfc6238)によれば、TOTPは下記式で表されます。

```
TOTP = HOTP(K, T) 
K:秘密鍵(, T:パスワード更新回数

T = (Current Unix time - T0) / X
X:パスワード更新周期

HOTP(K,C) = Truncate(HMAC-SHA-1(K,C))
C:カウント(T:パスワード更新回数と同じ)
```
HMAC-SHA1は暗号化で用いる汎用のハッシュ関数の1つです。
ハッシュ関数は任意の長さのデータ（ビット列）を一定の長さのデータ（ビット列）に変換する関数です。
TruncateはHMAC-SHA-1で算出したHash valueから(HOTPで定義されてる)4byte文字列に変換する処理です。

(特にTruncate周りが)何のことやらわからないので、
nasa9084さんの[TOTPを実装する](https://blog.web-apps.tech/implementing_totp/)を参考にさせていただいてコードを書きつつ、[RFC4226](https://www.rfc-editor.org/rfc/rfc4226)や[RFC6238](https://www.rfc-editor.org/rfc/rfc6238)、[Base32](https://ja.m.wikipedia.org/wiki/%E4%B8%89%E5%8D%81%E4%BA%8C%E9%80%B2%E6%B3%95#Base32)あたりを参考にしながら理解しました。

```go
package main

import (
	"crypto/hmac"
	"crypto/sha1"
	"encoding/base32"
	"encoding/binary"
	"fmt"
	"math"
	"os"
	"time"
)

func main() {
	key, err := base32.StdEncoding.DecodeString(os.Args[1])
	if err != nil {
		fmt.Fprintf(os.Stderr, "invalid secret: %s", err.Error())
		return
	}
	fmt.Printf("One time number: %d\n", totp(key))
}

//秘密鍵を受け取ってパスワードを生成する
func totp(key []byte) uint32 {
	var currentUnixTime = time.Now().Unix()
	const X = 30                                //パスワード更新周期
	return hotp(key, uint64(currentUnixTime/X)) //currentUnixTime/Xは何周期目かを表す
}

//秘密鍵と何周期目かを受け取って、hmacSha1でhash valueを計算し、hash valueが長いのでtruncateする
func hotp(key []byte, counter uint64) uint32 {
	return truncate(hmacSha1(key, counter))
}

//20byteのHash valueから4byte文字列の生成
func truncate(hmacResult []byte) uint32 {

	//Hashの最後の文字の下位4bit取得。4bitなので0<=offset<=15
	offset := hmacResult[len(hmacResult)-1] & 0x0F

	//offsetから4byte取り出して下位31bit mask
	binCode := binary.BigEndian.Uint32(hmacResult[offset:offset+4]) & 0x7FFFFFFF

	const digit = 6
	return binCode % uint32(math.Pow10(digit)) //6桁(パスワードの桁数)にするため10^桁数で割る
}

//秘密鍵と何周期目かを受け取ってhash valueを返す
func hmacSha1(key []byte, counter uint64) []byte {
	counterBytes := make([]byte, 8)
	binary.BigEndian.PutUint64(counterBytes, counter)

	hm := hmac.New(sha1.New, key)
	hm.Write(counterBytes)
	return hm.Sum(nil)
}
```

上記コードを3回ほど実行してみると、30秒経過して番号が878553から934554になったようです。これで二段階認証時に生成されるパスワードと同じようなものができました！ちなみに引数の秘密鍵はコードを見る限り[Base32](https://ja.m.wikipedia.org/wiki/%E4%B8%89%E5%8D%81%E4%BA%8C%E9%80%B2%E6%B3%95#Base32)だったので、Base32の定義に倣って適当な数値を秘密鍵としました。

```
esperna (i386):~/workspace/go/totp
% go run ./main.go 'ABCDEFGHIJKLMNOPQRSTUVWXYZ234567'
One time number: 878553
esperna (i386):~/workspace/go/totp
% go run ./main.go 'ABCDEFGHIJKLMNOPQRSTUVWXYZ234567'
One time number: 934554
esperna (i386):~/workspace/go/totp
% go run ./main.go 'ABCDEFGHIJKLMNOPQRSTUVWXYZ234567'
One time number: 934554
```

## 所感

* TOTP動かしてみると意外に簡単に計算できるものだなと思いました
* 面倒臭がらずRFCをきちんと読むことが大事だなと思いました


# 参考資料

* [RFC4226](https://www.rfc-editor.org/rfc/rfc4226)
* [RFC6238](https://www.rfc-editor.org/rfc/rfc6238)
* [Base32](https://ja.m.wikipedia.org/wiki/%E4%B8%89%E5%8D%81%E4%BA%8C%E9%80%B2%E6%B3%95#Base32)
* [TOTPを実装する](https://blog.web-apps.tech/implementing_totp/)
* [Googleが間もなく「自動でアカウントの2段階認証をオンにする」と発表](https://gigazine.net/news/20210507-google-two-step-verification-phone/)