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

:::note alert
2024-03-31: コメントでの指摘でこの記事の正確性に問題があると判断したので、記事全体をコメントアウトしました。
:::

<!--
# はじめに

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

# アイディア

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

> [パスワードの最適変更間隔とその定量的効果の評価](https://docs.google.com/document/d/1RWDerFjLc24nr_lDhF8s0vEOJ8DPKhEnEAYG9qr_oBY/pub)

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

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

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

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

|  記号 |          意味          |
|:------:|:----------------------:|
|  $n$  |    パスワードの空間    |
| $\tau$ | 一度の試行に必要な時間 |


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

```math
T_e = \sum^n_{i=1}{\frac{(i - 1)\tau}{n}} = \frac{n\tau}{2}
```

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

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

```math
T_{j=1} = \sum^m_{i=1}{\frac{(i - 1)\tau}{n}} = \frac{m(m - 1)\tau}{2n}
```

## 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}$で成功する、という確率となるので、次の式で求められる。

```math
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$の場合を考える。

```math
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\tau$からスタートとなる。時間の期待値は“確率×時間”なので、次のようになる。

```math
T_{j=2} = \sum^{2m}_{i=m+1}\frac{(i-1)\tau(n-m)}{n^2} = \frac{3m(m-1)\tau(n-m)}{2n^2} 
```
## 2回目のパスワード変更が行われた次の試行でパスワードが正解する確率

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

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

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

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

同様に、

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

よって、

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

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

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

```math
T_{j=3} = \sum^{3m}_{i=2m+1}\frac{(i-1)\tau(n-m)^2}{n^3} = \frac{5m(m-1)\tau(n-m)^2}{2n^2}
```

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

上記の結果から次のようになると推測される[^maybe]。

```math
P_j = \frac{m(n-m)^{j-1}}{n^j} \\
p_{jm+1} = \frac{(n-m)^j}{n^{j+1}}
```

[^maybe]: 参考サイトでは証明をしているが、ここでは省略する。

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

これは次のようになる。

```math
T_j = \sum^{jm}_{i=(j-1)m+1}p_{(j-1)m+1} = \frac{(2j-1)m(m-1)\tau(n-m)^{j-1}}{2n^j}
```

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

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

```math
T_c = \sum^{∞}_{j=1}T_j = \frac{(m-1)(2n-m)\tau}{2m}
```

# TOTPへの応用

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


|  変数 |          値        |
|:------:|:----------------------:|
|  $n$  |    $25 \cdot 10^4$[^why]    |
| $m \cdot \tau$ | $30$（秒） |

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

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

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

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

![スクリーンショット 2016-03-01 0.15.23.png](https://qiita-image-store.s3.amazonaws.com/0/10815/cc973049-436f-8c16-29f3-f01e7346a908.png)

![スクリーンショット 2016-03-05 18.39.25.png](https://qiita-image-store.s3.amazonaws.com/0/10815/5a25371d-4943-29cb-3800-32382f8e50dc.png)

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

# まとめ

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