TOTPの仕様だけではAuthアプリを上手く使えなかった
今回は技術的な話なのかも。
いきさつ
ちょうど1年前、大学に入学した時に学内用のアカウントやら大学用Googleアカウントやらをもらいました。セキュリティの面から2要素認証を付けろとの事で選択肢を見てみたところ、1番楽そうだったのはOTP(ワンタイムパスワード, One-Time Password)でした。他にメール認証やら物理トークンやらあった気がしますが、メールはいちいち受け取る手間があるし、物理トークンは持ち合わせていないので。
OTPのアプリを入れて認証を登録しましたが、この6桁の数値で認証できるというのは魅力的です。どうやって認証しているのか、調べて実装してみようと思ってました。ところが大学で課題やら遊びやらバイトやら忙しくしてたらあっという間に一年経ってしまい、春休みになってようやく重い腰を上げて実装しましたのでいろいろ書いておきます。
TOTPの仕組み
他のサイトを全力で眺め、仕様を理解しました。最後の方に参考にしたサイトを乗っけておきます。TOTPを計算するのに必要なものはSHA-1とHMACです。
SHA-1
暗号学的ハッシュ関数、仲間にはMD5とかSHA-2とかがいます。詳しいことはWikipedia先生に聞いてもらえるとうれしいです。ざっくりと説明すると
- どんな長さの入力でも固定長の出力になる
- 同じ入力では同じ出力になる
- 異なる入力で同じ出力になるものを探すのが困難
- 出力から入力を探すのも困難
- 入力がちょっと変わっても出力がめっちゃ変わったように見える
という感じの関数です。
HMAC
さっきの暗号学的ハッシュ関数を使って、メッセージと秘密鍵からメッセージ認証符号を出力する関数です。これを使うとこのメッセージは偽造されてないよ～っていうのを証明することができます。これも詳しいことはWikipedia先生に聞いてもらえるとうれしいです。
HOTPとTOTP
ではTOTPの実装を…と行きたいのですがそのためにはHOTP(HMAC-based One-Time Password)という別のOTPについて知っておく必要があります。HOTPはカウンタと秘密鍵を入力するとSHA-1関数とHMAC関数を利用してOTPを生成します。カウンタというのは例えば認証回数とかですかね。
HOTPのカウンタを使う場合だと、OTPを間違えて入力した時とか悪い人に認証を失敗された時にカウンタが食い違ってしまう可能性があり、ちょっと使いづらいです。そこでTOTP(Time-based One-time Password)が出てきます。TOTPは秘密鍵と、カウンタの代わりに時刻を使ってOTPを生成します。こうすれば双方で数字が食い違うことがなくなります！
プログラムにする
まずは今回作ったプログラムたちの仕様です。言語は何となくでC++、ライブラリもバンバンつかいます。基本的にメッセージやハッシュ値などのビット列はvector<unsigned int>で持つことにしました。SHA-1はなんか他でも使えそうなのでクラス化してますがどうなるかは未定。趣味で書いてるものなので適当なのはご愛敬。なお、この記事に載っている全てのコードは自由に使ってもらって構いませんが、それによって起きる損害等は一切保証しません。責任は負わないけど自由に使ってくださいということです。というか使ってくれたら喜びます。
SHA-1
まずはSHA-1から。RFC 3174を眺めつつ、英語が読めないのでQiitaの先人の知恵も借りつつ書いていきます。宣言はこんな感じ。
class SHA_Func{ protected: unsigned int ROTL(const unsigned int, const int)const; unsigned int ROTR(const unsigned int, const int)const; unsigned int SHR(const unsigned int, const int)const; vector<unsigned>* padding(const vector<unsigned int> &, const unsigned int)const; }; class SHA1 : public SHA_Func{ private: unsigned int hash[5]; unsigned int RotF(const int, const unsigned int, const unsigned int, const unsigned int)const; void calchash(const vector<unsigned int> &, const unsigned int); public: SHA1(const vector<unsigned int> &, const unsigned int); SHA1(const string &); void gethash(unsigned int (&)[5])const; };
SHA-2も実装しようと思って基本的なビット演算関数はclass SHA_Funcに投げてますがいつ書くかわかりません。あとここでvectorとかstringとか使ってるせいで後で詰みます。class SHA1は計算されたハッシュ値を保持しておく配列unsigned int hash[5]をメンバに持ってますが、配列長が5で固定なのはSHA-1のハッシュ長が160ビットで固定だからです。あと、コンストラクタとかgethashは処理を投げたりhash[5]を返したりするだけなのでこの記事では端折ります。
まずSHAシリーズだいたい共通のパディングをします。これはメッセージの後ろに0のビットとかメッセージ長とかを追加して、計算しやすい長さにすることを言います。メッセージの後ろにビットの1を追加、0で埋めて、最後の8バイトにメッセージのビット長を追加します。0埋めは最後のビット長まで含めた長さが64バイトの倍数になるようにうまく埋めます。なおこの64バイトの区切りをブロックと呼んでいます。paddingの定義はこんな感じです。
vector<unsigned int>* SHA_Func::padding(const vector<unsigned int> &msg, const unsigned int msglen)const{ vector<unsigned int> *pdmsg = new vector<unsigned int>; int pdlen = msglen / 512 + 1; if(msglen % 512 > 440) pdlen++; pdlen = pdlen * 16 - 1; int lenlef = msglen; for(int i = 0; i < pdlen; i++){ if(i >= (int)msg.size()){ pdmsg->push_back(0); continue; } if(lenlef >= 32) pdmsg->push_back(msg[i]); else if(lenlef > 0) pdmsg->push_back(msg[i] & (((1 << lenlef) - 1) << (32 - lenlef))); else pdmsg->push_back(0); lenlef -= 32; } pdmsg->push_back(msglen); int adbt = (msglen + 1) / 32; if((msglen + 1) % 32 == 0) adbt--; pdmsg->at(adbt) |= (1 << (32 - (msglen + 1) % 32)); return pdmsg; }
読みづらいですね。だれが書いたんですかこれ。自力で書いた方が早いかもしれないので読み飛ばしてもらって構いません。えっと、unsigned intが4バイト(の環境を想定)なので、1ブロックはunsigned int8つ分になります。その辺を計算してpdmsgの長さ-1をpdlenに入れておいて、地道にmsgから読み取りつつpdmsgに入れていきます。msgから読み取れなくなったらとりあえず0埋めします。わざわざpdlenを長さ-1にしたのは、最後にmsgのビット長msglenを個別に追加するためです。そして最後にmsgの末尾の一つ後ろのビットの位置を計算し1にしておきます。これで無理やりパディング出来ました。
ついでに仕様で定義されているビット演算関数ROTL、ROTR(SHA-1では使われない)、SHR、RotF(SHA-1で定義されている4つの関数を合わせて一関数に)の定義がこんな感じです。
unsigned int SHA_Func::ROTL(const unsigned int x, const int n)const{ return ((x << n) | (x >> (32 - n))); } unsigned int SHA_Func::ROTR(const unsigned int x, const int n)const{ return ((x >> n) | (x << (32 - n))); } unsigned int SHA_Func::SHR(const unsigned int x, const int n)const{ return x >> n; } unsigned int SHA1::RotF(const int t, const unsigned int b, const unsigned int c, const unsigned int d)const{ if(t == 0) return (b & c) | ((~b) & d); else if(t == 2) return (b & c) | (b & d) | (c & d); return b ^ c ^ d; }
RotFのtには本当は0～79を入れるのですが、0～19、20～39、40～59、60～79で同じ処理をするので、関数呼び出しの時にt/20を入れてもらうようにすることにしました。なんで？関数内で計算すればよかったじゃん…
では最後にcalchashです。SHAシリーズは全部そうですが、定数とビット演算関数、メッセージブロックを使い、初期のハッシュ値を変化させることでハッシュを計算します。メッセージブロックが多いほど処理が増えるという感じです。定義通り書いた関数が以下のとおりです。
void SHA1::calchash(const vector<unsigned int> &msg, const unsigned int msglen){ hash[0] = 0x67452301; hash[1] = 0xefcdab89; hash[2] = 0x98badcfe; hash[3] = 0x10325476; hash[4] = 0xc3d2e1f0; const unsigned int K[] = {0x5a827999, 0x6ed9eba1, 0x8f1bbcdc, 0xca62c1d6}; unsigned int a, b, c, d, e, W[80], tmp; vector<unsigned int> *M = padding(msg, msglen); int mlen = M->size() / 16; for(int i = 0; i < mlen; i++){ for(int j = 0; j < 16; j++) W[j] = (*M)[i * 16 + j]; for(int j = 16; j < 80; j++) W[j] = ROTL((W[j-3] ^ W[j-8] ^ W[j-14] ^ W[j-16]), 1); a = hash[0]; b = hash[1]; c = hash[2]; d = hash[3]; e = hash[4]; for(int t = 0; t < 80; t++){ tmp = ROTL(a, 5) + RotF((t / 20), b, c, d) + e + W[t] + K[t / 20]; e = d; d = c; c = ROTL(b, 30); b = a; a = tmp; } hash[0] += a; hash[1] += b; hash[2] += c; hash[3] += d; hash[4] += e; } delete M; return; }
まず、i番目のメッセージブロックを使ってW[80]を計算します。メッセージブロックを16分割してそれらの数を使ってW[80]を計算するのですが、メッセージブロックは64バイトだったのでちょうど16分割で4バイト、さっきunsigned intにした恩恵が出ました。偶然ですけどね。後はひたすらループを回します。さっきのtはここのループ回数だったんですね。80回まわしたらi番目のメッセージブロックの分が終了です。これをメッセージブロックの個数回やれば終わりですね。
もうすでに力尽きかけてます。というか普通SHA-1の実装だけで一記事でしょ、なんでこんなに書いてるんですか？でも書かないと記事が出せないので次に行きます。
HMAC
次はHMACです。これもRFC 2104を眺めながら実装しました。HMACはハッシュ関数を使って認証符号を返してくれるやつでしたね。いろいろなハッシュ関数が使えるので、テンプレートやらポインタやら基底クラス型やら使って一般化すればよかったのですが、ぷよぐやみんぐしてる時も力尽きかけてたのでHMACSHA1関数を作ることで妥協しました。哀れ。
HMACはハッシュ関数h(message)を使って認証符号を作ります。まずはopadとipadという定数を用意します。opadは0x5cを、ipadは0x36をハッシュ関数のブロック長(ここでは512ビット、Bとする)になるまで繰り返した数です。また、数Kを準備しておきます。これは与えられる秘密鍵から計算されます。秘密鍵の長さがBを超えない場合はそのまま鍵がKになります。Bを超える場合は、秘密鍵のハッシュをKとします。なおKの長さがBに満たない場合は後ろを0埋めします。
ここまで用意したらHMACを計算できます。元の符号を計算したいメッセージをtxtとすれば、符号はh(K xor opad, h(K xor ipad, txt))となります。xorは長さをそろえてあるのでxorをとってください。また、ここでのカンマ(,)は連結の意です。前と後ろの数を合体させます。ここまでの計算が以下のコードになります。
void HMACSHA1(const vector<unsigned int> &keyvec, const unsigned int keylen, const vector<unsigned int> &txtvec, const unsigned int txtlen, unsigned int (&hs)[5]){ unsigned int k[16], opad[16], ipad[16], temp[5]; if(keyvec.size() > 16){ SHA1 h(keyvec, keylen); h.gethash(temp); for(int i = 0; i < 5; i++) k[i] = temp[i]; for(int i = 5; i < 16; i++) k[i] = 0; }else{ for(int i = 0; i < (int)keyvec.size(); i++) k[i] = keyvec[i]; for(int i = keyvec.size(); i < 16; i++) k[i] = 0; } for(int i = 0; i < 16; i++){ opad[i] = k[i] ^ 0x5c5c5c5c; ipad[i] = k[i] ^ 0x36363636; } vector<unsigned int> sndvec; for(int i = 0; i < 16; i++) sndvec.push_back(ipad[i]); for(int i = 0; i < (int)txtvec.size(); i++) sndvec.push_back(txtvec[i]); SHA1 h1(sndvec, (unsigned int)(512 + txtlen)); h1.gethash(temp); sndvec.clear(); for(int i = 0; i < 16; i++) sndvec.push_back(opad[i]); for(int i = 0; i < 5; i++) sndvec.push_back(temp[i]); SHA1 h2(sndvec, 672); h2.gethash(hs); return; }
HMACは意外と早くかけました。よしよし。
HOTP
いよいよHOTPです。HOTPが終わればTOTPなんてすぐできます。と思ってたのが完全にフラグでした。HOTPはRFC 4226です。
HOTPは8バイトのカウンタcount(これをメッセージとする)、秘密鍵keyを用いてHMAC-SHA-1で符号hsを生成し、そこからなんやかんやして10進数6桁の数値を取り出します。hsの末尾4ビットを取り出します。これをoffsetとします。hsの前からoffset番目以降の4バイトを取得し、そのうち後方31ビットを取り出します。これを10進数として見たものがHOTPです。6桁欲しければ1000000で剰余をとって返せばよいわけです。コードは以下の感じです。
int HOTP(const string &key, const unsigned int count, const bool nobase = false){ unsigned int hs[5], offset, keylen; vector<unsigned int> keyvec, cntvec; HMAC_StrtoVec(key, keyvec, keylen, nobase); cntvec.push_back(0); cntvec.push_back(count); HMACSHA1(keyvec, keylen, cntvec, 64, hs); int ofb = hs[4] & 0xf; int hsb, hsq; offset = 0; for(int i = 0; i < 4; i++){ hsb = ofb / 4; hsq = (3 - (ofb % 4)) * 8; offset |= ((hs[hsb] & (0xff << hsq)) >> hsq) << (24 - i * 8); ofb++; } offset &= 0x7FFFFFFF; offset %= 1000000; return offset; }
変数名がごちゃごちゃになってしまっています。unsigned intの配列で管理していたせいでoffset番目から4バイト取り出すのに苦戦してますね。ちなみに(当然かもしれないですが)offset番目というのは最上位ビットが0番目です。また、秘密鍵をstringで受け取っていたり謎の引数nobase、関数HMAC_StrtoVecが出現していますが後で説明します。
SHA-1やHMACのときもそうですが、RFCにテストケースが乗っかってるのでちゃんとテストしておきましょうね。テストケースが通ってもうまくいかないことがあったので…
TOTP
やったー！これが実装終われば終わりです(終わらなかった)、というわけでTOTP、RFC 6238です。実はとっても簡単、HOTPのカウンタに時刻を入れるだけです。
まずは時刻に手を加えておきましょう。そのまま時刻を入れたらOTPが毎秒変わってしまい入力が大変になります。TOTPのタイムステップ、有効時間をX(通常は30秒なので30)、カウント開始時刻をt0(通常は0)とし、Unix時間をtとするとTOTPで使う時刻は(t - t0) / Xとなります。これを8バイトにしてHOTPのカウンタの部分に投げてやれば良いわけです。コードを乗っけます。
unsigned int TOTP_time(const int t0 = 0, const int plim = 30){ return (time(NULL) - t0) / plim; } int TOTP(const string &key, const int t0 = 0, const int plim = 30, const bool nobase = false){ return HOTP(key, TOTP_time(t0, plim), nobase); }
なんでunsigned intで投げてるんだろう、まずくないですかね…。まあでもともかく、とっても簡素ですが終わりました！！！……とはならず。
なんかうまくいかない
おのれAuthアプリ
当初、TOTPやHOTPは投げられた秘密鍵の文字列をcharとしてビット列に変換し計算していたのですが、なんかうまくいきません。テストケースはうまくいってるのに。というかテストケースはそんな感じでかいてあるのに。
アプリはMicrosoft Authenticatorを使っていました。なんでか数値が合いません。いろいろ調べていると、各所で出てくるBase32という名前。もしやと思いましたが…。
base32以外受け付けてないなら先に言って
— ryuka (@ryuka_lukas) 2021年4月10日
base32の文字列以外を無視するようで、base32で使われてない文字だけでsecretを構成するとotpを生成しない pic.twitter.com/GcNUokVUmV
— ryuka (@ryuka_lukas) 2021年4月10日
なんだこれ…。Microsoft Authenticatorの仕様探しても見つからなかったし(探し方が悪い)、どこ見てもそんなの書いてなかったやんけー！というわけで仕様変更。プログラミング下手くそか。
Base32
ついでにBase32について説明しておきましょう。Base16、Base64とあわせてRFC 4648です。BaseXXというのは、XX種類の文字を使って数字を表そうという感じのことをやるための規定です。たとえばBase32なら32種類の文字を使うことでで5ビットの数を1文字で表現します。変換表はRFCをのぞいてください。ここでは、Base32文字列を数値表現に置き換える関数を作りました。それがHOTPのところで出てきた謎関数HMAC_StrtoVecです。コードは以下の感じです。
int Base32ChrtoInt(const char c){ int ret = -1; if(('A' <= c) && (c <= 'Z')) ret = (int)(c - 'A'); else if(('a' <= c) && (c <= 'z')) ret = (int)(c - 'a'); else if(('2' <= c) && (c <= '7')) ret = (int)(c - '2' + 26); return ret; } void HMAC_StrtoVec(const string &text, vector<unsigned int> &txtvec, unsigned int &txtlen, const bool nobase = false){ vector<unsigned char> data; if(!nobase){ vector<unsigned char> pd; for(int i = 0; i < (int)text.length(); i++){ int k = Base32ChrtoInt(text[i]); if(k > -1) pd.push_back((unsigned char)k); } if(pd.empty()){ txtlen = 0; return; } int len = pd.size() / 8 + 1; if(pd.size() % 8 == 0) len--; for(int i = 0; i < len; i++){ unsigned char tmp[5] = {0, 0, 0, 0, 0}; for(int j = 0; j < 8; j++){ int k = i * 8 + j; if(k < (int)pd.size()){ int c = (j * 5) / 8; int q = 3 - ((j * 5) % 8); if(q > 0)tmp[c] |= pd[k] << q; else{ q *= -1; tmp[c] |= pd[k] >> q; q = 8 - q; tmp[c + 1] |= pd[k] << q; } } } for(int j = 0; j < 5; j++) data.push_back(tmp[j]); } switch(pd.size() % 8){ case 1: case 2: data.pop_back(); case 3: case 4: data.pop_back(); case 5: data.pop_back(); case 6: case 7: data.pop_back(); break; } }else{ for(int i = 0; i < (int)text.length(); i++) data.push_back((unsigned char)text[i]); } txtlen = data.size() * 8; int len = data.size() / 4 + 1; if(data.size() % 4 == 0) len--; for(int i = 0; i < len; i++){ unsigned int tmp = 0; for(int j = 0; j < 4; j++){ int k = i * 4 + j; if(k < (int)data.size()) tmp |= (data[k] << (24 - j * 8)); } txtvec.push_back(tmp); } return; }
Base32ChrtoIntは定義通りBase32の文字を数値に変換しているだけです。HMAC_StrtoVecでは、引数nobaseがtrueのとき文字列をASCIIとして変換、falseのとき文字列をBase32として変換します。Base32では文字列長が8の倍数でない場合、1文字が5ビットのため数値表現を8ビットごと分けた時に数ビット余ります。文字列長の8の剰余によって余る分が固定なので、ブレイクフォーススルーのswitch文(してはいけない)を使ってうまく整理しています。最後の方はデータのビット長を計算しているだけです。
ようやくできた
やったー pic.twitter.com/zLxiCMoNwA
— ryuka (@ryuka_lukas) 2021年4月11日
出来ました。Base32には英文字は全て使われているので適当な秘密鍵を使って検証、よさそうです。ついでにDxライブラリやらWinAPIやらなんやら使って、画面表示とクリップボードに自動コピー機能がついたプログラムを作りました。大学のアカウントログインが非常に楽になりました。
— ryuka (@ryuka_lukas) 2021年4月11日
表示機つけた pic.twitter.com/2v0Ft56f0O
— ryuka (@ryuka_lukas) 2021年4月11日
改善点とかあとがきとか
何とか書き上げましたが、コードが汚く読みづらいですね。あとHMACは一般化したいです。欲を言えば、std::stringとかstd::vectorを使わずにCっぽく書きたかったです。DLL作ってVisual Basic側で呼び出し、フォームアプリケーションとして作ればもっとスマートだったので。でももう修正するのやです。気が向いたらやります。 あとRFCへのリンクはさんざん貼ってますが英語が読めないのでほとんどテストケースでしか使ってません、準拠してるとは言い難いです。
以前学校の課題でQRコードの生成プログラムを書いたことがあるので、otpauth URIの生成とかしてTOTPで遊びつくしたい気持ちもあります。というかたぶん次の技術記事はQRコードの生成だと思います。いつになるかわかりませんが。
記事を書くのも不慣れなので、日本語やコードが間違っていたら教えてください。頑張って直します。というわけでお疲れさまでした、文字数が大変なことになってる、なんだこれ。リンクもめちゃくちゃ多いぞ、本当に自作と言えるのか、なんだこれ。
参考サイト
今さらTOTPクライアントを実装する｜murakmii｜note
PHP で otpauth URI（TOTP）を作成する方法 | あぱーブログ
ではまた、どこかで。
