Google Authenticator みたいな認証アプリの仕組みを調べたらわりと単純だったので、練習がてら認証コードを計算するプログラムを書いてみました。
3行でまとめると
・認証アプリはTOTPという規格で共有Secretと現在時刻から認証コードを計算している
・簡単な規格なので仕様を読んで実装する練習にちょうどいい
・Javascriptで書きましたコードはこちら → totp.js
認証アプリを使った2段階認証
例えば Qiita の 2段階認証を設定するページ に行くと次のような QR コードが表示されます。
これを認証アプリで読み取って登録すると一定時間ごとに認証コードが生成されるので、ログイン時にコードの入力を要求することで登録した端末を持っている人しかログインできなくする仕組みです。
認証コードを生成する
この認証コードは TOTP (Time-Based One-Time Password Algorithm, RFC6238) という規格にのっとって生成されています。
ざっくりいうとサーバーとクライアントで共有されたSecretと現在時刻をもとに認証コードを計算し、これを検証することで認証するといった感じになります。
具体的な計算方法を読み解いて実装していきましょう。
言語は Javascript、実行環境は Node.js v10.15.3 を用いました。
TOTP value の計算
TOTP のベースは HOTP (HMAC-Based One-Time Password Algorithm, RFC4226) というワンタイムパスワードの規格です。HOTP では Secret と Counter からパスワードを生成しますが、TOTP ではこの Counter を時間によって定めます。
具体的には T0 = Inital Unix time(1970-01-01T00:00:00) での Counter を 0 として、X = Time Step 秒ごとに1ずつカウントしていきます。現在の Counter の値 T は
T = (Current Unix time - T0) / X
で計算できます。
Time Step は当然サーバーとクライアントで共通の値を用います。RFC ではデフォルトで30秒にすることが推奨されています(RECOMMEND)。
const TIME_STEP = 30;
/**
* Calculate TOTP value defined in [RFC6238](https://tools.ietf.org/html/rfc6238)
*
* @param {Buffer} key shared secret between client and server
* @param {Date} date date to calculate totp value.
*
* @return {string} 6-digit decimal TOTP value
*/
function totp(key, date) {
// count TIME_STEP from base Unix Time
const counter = Math.floor(date.getTime() / 1000 / TIME_STEP);
return hotp(key, counter);
}
hotp は次で実装します。
HOTP value の計算
HOTP value の計算方法は RFC4226 で次のように定められています。
HOTP(K,C) = Truncate(HMAC-SHA-1(K,C))
K は Secret、C は 8byte の Counter でどちらもバイトオーダーはビッグエンディアンです。
HMAC-SHA-1 は RFC2104 で定められているメッセージ認証符号です。ハッシュ関数として SHA-1 を使うので 20byte の値が返されます。
Truncate は RFC4226 §5.3 で定められている関数で、20byte のハッシュ値から digit 桁の10進数を作り出します。桁数には6桁がよく用いられます。
const DIGIT = 6;
/**
* Calculate HOTP value defined in [RFC4226](https://tools.ietf.org/html/rfc4226).
*
* @param {Buffer} key shared secret between client and server
* @param {number} counter counter value
*
* @return {string} 6-digit decimal HOTP value
*/
function hotp(key, counter) {
// pack counter to 8-byte buffer in big-endian
const buf = Buffer.alloc(8);
buf.writeUInt32BE(Math.floor(counter/2**32), 0);
buf.writeUInt32BE(counter, 4);
const val = trunc(hmacsha1(key, buf));
return val.toString().padStart(DIGIT, '0');
}
HMAC関数は入力としてバイト列を受け取るので、Counter をバイト列に詰める必要があります。
規格では Counter は 8byte の値で、バイトオーダーはビッグエンディアン (high-order byte first) と定められているので、8byte のバッファに上位 21bit1 と下位 32bit をそれぞれ writeUInt32BE で書き込んでいます。
ビット演算を行うと 32bit 整数として扱われてしまうので、割り算でビットシフトをしています。
trunc , hmacsha1 は次で実装します。
HMAC-SHA-1 の実装
Node.js には HMAC を計算するライブラリが用意されているので、これを用います。
const crypto = require('crypto');
/**
* Calculate HMAC-SHA-1 value defined in [RFC2104](https://tools.ietf.org/html/rfc2104).
*
* @param {Buffer} key secret key. (up to 64Bytes)
* @param {Buffer} message stream data to calc HMAC.
*
* @return {Buffer} 20-byte binary string.
*/
function hmacsha1(key, message) {
const hmac = crypto.createHmac('sha1', key);
hmac.update(message);
return hmac.digest();
}
なお、今回は HOTP の仕様にのっとってハッシュ関数として SHA-1 を使いましたが、TOTP の仕様では代わりに SHA-256 や SHA-512 を使うこともできる (MAY) ことになっています。
Truncate関数の実装
次の手順で HMAC-SHA-1 が出力した 20byte のハッシュ値から digit 桁の10進数を作ります。
まず 20byte の入力のうち offset として最後の 4bit を取り出します。( offset は0～15の整数になります)
次に 20byte のうち offset 番目から 4byte を取り出して下位 31bit を整数として解釈します。
得られた整数を10進数で表した時の最後の digit 桁が認証コードになります。
/**
* Convert 20-byte binary string to a number less than 10**digit.
* defined in [RFC4226 §5.3](https://tools.ietf.org/html/rfc4226#section-5.3)
*
* @param {Buffer} data 20-byte binary string.
*
* @return {number} calculated number that is less than 10**digit.
*/
function trunc(data) {
const offset = data[data.length-1] & 0x0f; // 0 <= offset <= 15
// get last 31bits of data[offset]...data[offset+3];
const code = data.readUInt32BE(offset) & 0x7fffffff;
return code % 10**DIGIT;
}
ハッシュ関数に SHA-1 以外の関数を用いると入力の長さが 20byte 以上になりますが、値を取り出す手順は同じです。
これで TOTP value を計算することができるようになりました。
Secret の共有方法
TOTP の RFC では Secret の共有方法までは規定されていません。
一般的に QR コードを読み取る方法と、Secret を手入力する方法が提供されていますが、この共有方法は Google Authenticator の実装によるものです。(たぶん)
QR コードの内容は
otpauth://totp/waaaarapy?secret=THISISASECRETKEY&issuer=Qiita&algorithm=SHA1&digits=6&period=30
のような URI になっていて、詳しいフォーマットは Key Uri Format に書かれています。
手入力用に表示されるものは TOTP の Secret を base32 (RFC3548) でエンコードしたものです。パディング('=')は必要なく、省略する(should)と URI の仕様に書いてあります。
Secret の長さについて
いくつかのサービスの Secret の長さを調べてみましたが、10byte (base32で16文字) か 20byte (base32で32文字) が多いようです。
TOTP の Secret は HMAC関数の Secret Key として用いられるので、長さが足りない場合は0埋めされます2。
| HMAC関数 | Secret Key の長さ |
|---|---|
| HMAC-SHA-1 | 20byte |
| HMAC-SHA-256 | 32byte |
| HMAC-SHA-512 | 64byte |
Secret Key の長さはハッシュ関数の出力の長さになっています。これより長い Secret Key が入力された場合はいったんハッシュ関数を通した値が Secret Key として用いられます2。
AWS では 40byteの Secret が使われていましたが、ハッシュ関数は SHA-1 なので、上の理由から 20byteの Secret と安全性は変わりません。手入力が大変になるだけなのでみなさんがTOTPをサポートするときは適切な長さの Secret を用いましょうね！
ちなみに RFC では TOTP の Secret の長さは HMAC関数の出力の長さと同じにするべき (SHOULD) とされています。
base32 のデコード
デコードにライブラリを使ってもよかったのですが、そこまで複雑でもないので自前で実装してみました。
const base32table = {
'A': 0, 'J': 9, 'S': 18, '3': 27,
'B': 1, 'K': 10, 'T': 19, '4': 28,
'C': 2, 'L': 11, 'U': 20, '5': 29,
'D': 3, 'M': 12, 'V': 21, '6': 30,
'E': 4, 'N': 13, 'W': 22, '7': 31,
'F': 5, 'O': 14, 'X': 23,
'G': 6, 'P': 15, 'Y': 24,
'H': 7, 'Q': 16, 'Z': 25,
'I': 8, 'R': 17, '2': 26,
};
/**
* decode base32 string to Buffer
*
* @param {string} str input string
*
* @return {Buffer}
*/
function base32decode(str) {
// ignore char not used in base32
str = str.toUpperCase().replace(/[^A-Z234567]/g, '');
// make length be a multiple of 8, padding 0 (='A')
str = str.padEnd(Math.ceil(str.length / 8) * 8, 'A');
// array of numbers in 0..31
const data = Array.from(str).map((value) => base32table[value]);
const buf = Buffer.alloc(data.length / 8 * 5);
for (let i=0, j=0; i < data.length; i+=8, j+=5) {
buf[j] = data[i+0] << 3 | data[i+1] >> 2;
let tmp = 0;
for (let shift=30, k=1; shift >= 0; shift-=5, k++) {
tmp |= data[i+k] << shift;
}
buf.writeUInt32BE(tmp >>> 0, j + 1);
}
return buf;
}
まず、 base32 に関係ない文字は取り除いてしまいます。
base32 では1文字で 5bit を表すことになるので、 8文字 → 5byteに変換していきます。
Secret の長さが足りない場合は0埋めされる仕様だったので、8の倍数文字になるようにパディングしてから処理してしまってかまいません3。
Javascript のビット演算では 32bit までしか扱えないので、1byte目と残りの 4byteに分けて処理しています。
動作テスト
最後に Secret を入力すると認証コードを表示するようにして完成です。せっかくなので残り時間を表示するようにしました。
const readline = require('readline');
rl = readline.createInterface(process.stdin, process.stdout);
rl.question('Input Secret Key: ', (answer) => {
const key = base32decode(answer);
rl.close();
setInterval(()=>{
const code = totp(key, new Date);
const current = Math.floor((Date.now() / 1000) % TIME_STEP);
const gauge = '='.repeat(current) + '-'.repeat(TIME_STEP - current);
process.stdout.write(`\r${code} [${gauge}]`);
}, 500);
});
Google Authenticator と照らし合わせてみましょう。
うまくいきました。
本来であれば関数ごとにいろいろなテストケースでの動作をチェックするテストコードを書くべきですが、それはまた今度にしましょう(おい)。
ちなみに Authenticator Test で QR コードを生成したり認証コードをテストしたりできます。
今回書いたコードは Gist に置いてあります。
あとがき
TOTP の RFC は Secret を共有する際の経路や保管方法、サーバー・クライアント間でのタイムスタンプのギャップを考慮した検証方法などにも言及しています。そんなに長くないので興味のある人は読んでみましょう。
感想としては、コード生成の仕様はかなり簡単なので、自力で仕様を読んで実装する練習にはお手軽でちょうどいいと思いました。
みなさんも週末に暇なときなんかに好きな言語で実装してみてはいかがでしょうか？