はじめに

TOTPは多要素認証（二段階認証）の一つで、ワンタイムパスワード（OTP）をスマートフォンなどにインストールされたソフトウェアで生成し、それをログインの際に用いる認証方法である。この記事では、攻撃者が総当たり攻撃を用いてTOTPを破るまでに必要な時間を計算することにする。
なお、筆者は数学の知識がそれほどあるわけではないので、もし微妙な部分があったら気軽にコメントなどで指摘してほしいと思う。

アイディア

この記事のアイディアは、「TOTPが30秒に一度パスワードが変更される認証」と考えることで、下記の記事の数式を用いることである。

パスワードの最適変更間隔とその定量的効果の評価

パスワードが変更される際の、攻撃者がパスワードを知るために必要な平均時間

これは上記の記事で述べられていることを、僕が再度書き下したものなので、最後の結論以外はあまり読む必要がない。

攻撃者がパスワードを知るために必要な時間

まず、計算に必要なパラメータを次のように定義する。

記号	意味
$n$	パスワードの空間
$τ$	一度の試行に必要な時間

まず、攻撃者が $n$ 通りのパスワードの中から正解のパスワードを知るために必要な時間を計算する。 $n$ 通りのパスワードの中から正解のパスワードを知るためには、最大で $n - 1$ 回の試行をすればよいので、パスワードを知るために必要な平均時間 $T_{e}$ は次のようになる。

T_{e} = \sum_{i = 1}^{n} \frac{(i - 1) τ}{n} = \frac{n τ}{2}

m回の試行でパスワードが判明する時間の期待値

TOTPのパスワードが $m τ$ 秒で変更されるとすると、攻撃者はパスワードが変更される前までに $m$ 回の試行を行うことができる。
これは、さきほどと同じように、次のようになる。

T_{j = 1} = \sum_{i = 1}^{m} \frac{(i - 1) τ}{n} = \frac{m (m - 1) τ}{2 n}

m+1, m+2回の試行でパスワードが正解する確率

$m + 1$ 回の試行でパスワードが正解するということは、まず1回目の試行で $\frac{n - 1}{n}$ の確率で失敗し、さらに2回目の試行では $\frac{n - 2}{n - 1}$ の確率で失敗し……と失敗をひたすら繰り返してゆき、 $m$ 回目の試行で $\frac{n - m}{n - (m - 1)}$ の確率で失敗した後、パスワードが変更されて $m + 1$ 回目の試行で $\frac{1}{n}$ で成功する、という確率となるので、次の式で求められる。

p_{m + 1} = \frac{n - 1}{n} \cdot \frac{n - 2}{n - 1} \cdot \dots \cdot \frac{n - m}{n - (m - 1)} \cdot \frac{1}{n} = \frac{n - m}{n^{2}}

$m > 2$ として、同様に $m + 2$ の場合を考える。

p_{m + 2} = \frac{n - 1}{n} \cdot \frac{n - 2}{n - 1} \cdot \dots \cdot \frac{n - m}{n - (m - 1)} \cdot \frac{n - 1}{n} \cdot \frac{1}{n - 1} = \frac{n - m}{n^{2}}

最初のパスワード変更から2回目の変更までの間にパスワードが正解する時間の期待値

最初のパスワード変更があったということは、攻撃者はすでに $m$ 回の試行をしていることになるので、時間は $m τ$ からスタートとなる。時間の期待値は“確率×時間”なので、次のようになる。

T_{j = 2} = \sum_{i = m + 1}^{2 m} \frac{(i - 1) τ (n - m)}{n^{2}} = \frac{3 m (m - 1) τ (n - m)}{2 n^{2}}

2回目のパスワード変更が行われた次の試行でパスワードが正解する確率

これは、最初のパスワード変更までにパスワードが正解する確率 $P_{j = 1}$ と、最初のパスワード変更から2回目のパスワード変更までにパスワードが正解する確率 $P_{j = 2}$ を用いて次のように表せる。

p_{2 m + 1} = (1 - P_{j = 1} - P_{j = 2}) \cdot \frac{1}{n}

まず、最初のパスワード変更から $m$ 回の試行でパスワードが正解する確率 $P_{j = 1}$ は $\frac{1}{n}$ を $m$ 回試行したものなので、次のようになる。

P_{j = 1} = \frac{m}{n}

同様に、

P_{j = 2} = \frac{m (n - m)}{n^{2}}

よって、

p_{2 m + 1} = \frac{n^{2} - m n - m (n - m)}{n^{3}} = \frac{(n - m)^{2}}{n^{3}}

2回目のパスワード変更から3回目のパスワード変更までの間にパスワードが正解する時間の期待値

さきほどの $T_{j = 2}$ と同様に次のようになる。

T_{j = 3} = \sum_{i = 2 m + 1}^{3 m} \frac{(i - 1) τ (n - m)^{2}}{n^{3}} = \frac{5 m (m - 1) τ (n - m)^{2}}{2 n^{2}}

j回目のパスワード変更が行われた次の試行でパスワードが正解する確率

上記の結果から次のようになると推測される¹。

P_{j} = \frac{m (n - m)^{j - 1}}{n^{j}} p_{j m + 1} = \frac{(n - m)^{j}}{n^{j + 1}}

j回目のパスワード変更からj+1回目のパスワード変更までの間にパスワードが正解する時間の期待値

これは次のようになる。

T_{j} = \sum_{i = (j - 1) m + 1}^{j m} p_{(j - 1) m + 1} = \frac{(2 j - 1) m (m - 1) τ (n - m)^{j - 1}}{2 n^{j}}

攻撃者が定期的に変更されるパスワードを知るためにかかる平均時間

これは $T_{j}$ を無限回足したものであるので、次のようになる。

T_{c} = \sum_{j = 1}^{\infty} T_{j} = \frac{(m - 1) (2 n - m) τ}{2 m}

TOTPへの応用

TOTPでは上で求めた変数のうち、いくつかを埋めることができる。

変数	値
$n$	$25 \cdot 10^{4}$ ²
$m \cdot τ$	$30$ （秒）

すると、 $m = \frac{30}{τ}$ となるので、 $T_{c}$ から $m$ を排除することができ、 $τ$ （一回の試行に必要な時間）とパスワードが正解する平均時間 $T_{c}$ の関数を次のように作ることができる。

y = \frac{(\frac{30}{τ} - 1) (2 n - \frac{30}{τ}) τ}{2 \cdot \frac{30}{τ}} = \frac{(\frac{30}{τ} - 1) (2 n - \frac{30}{τ}) τ^{2}}{60}

これをプロットすると次のようになる。なお、横軸が1回の試行に必要な時間 $τ$ であり、縦軸が攻撃者がパスワードを知るために必要な時間 $y$ である。

もし0.2秒で1回の試行ができるとすると、約5万秒（半日）でTOTPの正解に辿りつくということになる。

まとめ

今回はTOTPをパスワードを変更するという操作とみなすことで、攻撃者がTOTPを総当たり攻撃で破るために必要な時間を計算することができたと思う。また計算が正しいとすれば、30秒に一度パスワードが変更されるとはいえ、総当たり攻撃に対しては別の対策を講じる必要があると思う。

参考サイトでは証明をしているが、ここでは省略する。 ↩
この記事で考えているTOTPは、6桁の数字で構成され、「現在」と「未来」と「過去1」「過去2」の合計4つのパスワードを許容するため、やや雑だが $\frac{4}{10^{6}} = \frac{1}{25 \cdot 10^{4}}$ より、 $n$ を $25 \cdot 10^{4}$ としている。 ↩

TOTPを総当たり攻撃で破るのに必要な時間