パスワードの「OOを1文字以上含む」の条件はパスワードの強度のどのくらい下げるのか

Streamlitの勉強がてら、パスワード生成アプリを作りました。
その際に、意外とパスワード生成も考えると面白いなと思ったので、パスワードの強度などについてPythonを使って計算してみました。

疑問：
パスワード作成時のバリデーションで「〇〇を1文字以上含む」はパスワードのパターンを減らさないか？

## パスワードの基本的な話

パスワードを突破してくる方法はたくさんあります。
代表的なものを下記に記します。

| 攻撃方法                  | 概要                                                                 | 対策                                                                 |
|---------------------------|----------------------------------------------------------------------|----------------------------------------------------------------------|
| ブルートフォース           | 可能なすべてのパスワードを試す総当たり攻撃。                          | 長く複雑なパスワード、ログイン試行回数の制限、多要素認証           |
| 辞書攻撃                  | よく使われる単語やフレーズを試す攻撃。                                | ランダムなパスワード、辞書にない単語を使用                         |
| クレデンシャルスタッフィング | 流出したパスワードを他のサービスで試す攻撃。                          | サービスごとに異なるパスワード、多要素認証                         |
| フィッシング               | 偽のウェブサイトやメールを使いパスワードを盗む攻撃。                  | URLの確認、怪しいメールやリンクを避ける                             |
| パスワードハッシュ攻撃     | 流出したハッシュ化されたパスワードを元に戻す攻撃。                    | 強力なハッシュアルゴリズムとソルトの利用                            |
| ソーシャルエンジニアリング  | 人的な弱点を突いてパスワードを聞き出す攻撃。                          | セキュリティ教育、認証情報を不用意に共有しない                     |
| キーロガー攻撃            | キーボード入力を記録するマルウェアでパスワードを盗む攻撃。             | セキュリティソフトでデバイスを保護、ソフトウェアを最新に保つ       |
| ショルダーサーフィング      | 肉眼でパスワード入力をのぞき見る攻撃。                                | 周囲に注意を払う、画面フィルターを使用                             |
| セキュリティ質問の悪用     | パスワードリセットの質問の答えを推測してアカウントにアクセスする攻撃。  | 答えに予測困難な情報を使用、多要素認証を利用                       |
| マルウェアによる攻撃       | マルウェアを使ってパスワードを記録し盗む攻撃。                        | 信頼できるソフトのみをインストール、セキュリティソフトで保護       |
| パスワードの使い回し        | 同じパスワードを複数サービスで使うことで攻撃される方法。               | サービスごとに異なるパスワードを使用、パスワードマネージャーを利用 |

色々な攻撃手段があり、開発者としてはそれぞれの対策が必要です。
今回はパスワードの生成、ブルートフォース攻撃への対策の観点を考えていきます。

## よくあるパスワードの作り(読み飛ばしOK)

パスワードは基本的に文字数と使用するオブジェクト(文字・数字・記号)の種類で強度が決まります。
(ただし辞書攻撃を考慮したランダムな文字列でないとダメです)

よくあるパターンは下記のようなものです。

- 英小文字のみ
- 英小文字と大文字
- 英小文字と数字
- 英小文字と大文字と数字
- 英小文字と大文字と数字と記号

文字数としては12文字以上ということがよく言われます。
そこで6文字から20文字のパスワードをリスト１の組み合わせで何通りあるかを計算してみます。

|   文字数 |   小文字のみ |   小文字と大文字 |   小文字と数字 |   小文字と大文字と数字 |   小文字と大文字と数字と記号 |
|---------:|-------------:|-----------------:|---------------:|-----------------------:|-----------------------------:|
|        6 |  3.08916e+08 |      1.97706e+10 |    2.17678e+09 |            5.68002e+10 |                  6.8987e+11  |
|        7 |  8.03181e+09 |      1.02807e+12 |    7.83642e+10 |            3.52162e+12 |                  6.48478e+13 |
|        8 |  2.08827e+11 |      5.34597e+13 |    2.82111e+12 |            2.1834e+14  |                  6.09569e+15 |
|        9 |  5.4295e+12  |      2.77991e+15 |    1.0156e+14  |            1.35371e+16 |                  5.72995e+17 |
|       10 |  1.41167e+14 |      1.44555e+17 |    3.65616e+15 |            8.39299e+17 |                  5.38615e+19 |
|       11 |  3.67034e+15 |      7.51687e+18 |    1.31622e+17 |            5.20366e+19 |                  5.06298e+21 |
|       12 |  9.5429e+16  |      3.90877e+20 |    4.73838e+18 |            3.22627e+21 |                  4.7592e+23  |
|       13 |  2.48115e+18 |      2.03256e+22 |    1.70582e+20 |            2.00029e+23 |                  4.47365e+25 |
|       14 |  6.451e+19   |      1.05693e+24 |    6.14094e+21 |            1.24018e+25 |                  4.20523e+27 |
|       15 |  1.67726e+21 |      5.49604e+25 |    2.21074e+23 |            7.6891e+26  |                  3.95292e+29 |
|       16 |  4.36087e+22 |      2.85794e+27 |    7.95866e+24 |            4.76724e+28 |                  3.71574e+31 |
|       17 |  1.13383e+24 |      1.48613e+29 |    2.86512e+26 |            2.95569e+30 |                  3.4928e+33  |
|       18 |  2.94795e+25 |      7.72788e+30 |    1.03144e+28 |            1.83253e+32 |                  3.28323e+35 |
|       19 |  7.66467e+26 |      4.0185e+32  |    3.71319e+29 |            1.13617e+34 |                  3.08624e+37 |
|       20 |  1.99282e+28 |      2.08962e+34 |    1.33675e+31 |            7.04423e+35 |                  2.90106e+39 |

一般的に12文字以上がいいと言われていますが、これは複数のセキュリティ基準（例: NIST SP 800-63、ISO/IEC 27001）が指定していることもありますが、必要十分な文字数が12文字以上だからとも言えます。

12文字以上であればブルートフォース攻撃でもかなり時間がかかるらしいので、1つの基準になっているそうです。ただコンピュータの処理速度が上がれば意外とすぐに突破されるかもしれませんが。

私が使用してるMacBookPro(M3 Max)のPythonで、パスワードで保護されたExcelに対して軽く試したところ、１試行あたり約0.034秒かかりました。12文字のパスワードの場合、下記のように時間がかかります。

| 種類                         | 総組み合わせ数   | 総試行時間   |
|:-----------------------------|:-----------------------------|:-------------------------------|
| 英小文字のみ                 | 95428.96 兆                  | 1.03 億年                      |
| 英小文字と大文字             | 3908.77 京                   | 4214.17 億年                   |
| 英小文字と数字               | 4.74 京                      | 51.09 億年                     |
| 英小文字と大文字と数字       | 322.63 京                    | 3.48 兆年                      |
| 英小文字と大文字と数字と記号 | 47.59 垓                    | 513.11 兆年                    |

Pythonがあまり早い言語ではないので、C言語とかを使えばもう少し早いのだと思いますが、それでもそう簡単に突破されることはないと思います。

ちなみに最近は、マシンスペックが上がって15文字以上がアメリカでは推奨されているらしいです。

## 本格的に計算

素人感覚で組み合わせの多さを計算していましたが、調べてみるとどうやらパスワードの強度を計算する方法があるようです(下記)。

**log2(文字の種類の数^文字数) = パスワードのエントロピー**

パスワードのエントロピーとは「パスワードのランダム性(予測しづらさ)」のことで、平均して何ビットの情報を持つかが分かります。

エントロピーが高いほど、ブルートフォース攻撃にかかる時間が指数関数的に増えます。

では、1bitがどのくらい強度を上げるのか。
1bit増える毎に、組み合わせの数は倍になります。そのため、ブルートフォース攻撃の場合は単純計算で倍の時間がかかることになります。
そのため、bit数が上がる毎に指数関数的に強度は上がります。

あとは現実的に「１秒間に何回の攻撃ができるか？」とということですが、これはマシンのハードスペックや暗号化の方法などによってかなりの幅が出るので一旦ここでは考えません。
また現実的には、一定回数パスワードが間違っていた場合の対応もあったりするので、どこまでブルートフォース攻撃を考えるかはまた難しい話です。

chatGPTに聞いた目安は下記のようになっているそうです。
40ビット未満: 弱いパスワード。簡単に解読される可能性が高い。
40〜60ビット: 中程度。推測されるリスクがある。
60ビット以上: 強いパスワード。
128ビット以上: 非常に強いパスワード。解読は事実上不可能。

## ここから本題

さて、ここからが本番です。
12文字のパスワードを作成するとします。
その場合のよくある文字指定でのエントロピーは下記のようになります。

| 種類                         |   文字種数 |   総当たりエントロピー (bits) |
|:-----------------------------|-----------:|------------------------------:|
| 英小文字のみ                 |         26 |                         56.41 |
| 英小文字と大文字             |         52 |                         68.41 |
| 英小文字と数字               |         36 |                         62.04 |
| 英小文字と大文字と数字       |         62 |                         71.45 |
| 英小文字と大文字と数字と記号 |         94 |                         78.66 |


<details><summary>計算コード</summary>

```python
import math

def calculate_entropy(charset_size, password_length):
    return password_length * math.log2(charset_size)
```

</details>

英小文字以外は60bit以上になっているので、最低でも２種類以上を混ぜることが推奨される理由この表なのだと思います。そして上記の場合"英小文字と英大文字"でも"英小文字のみ"のパスワードが、生成される可能性があります。ランダムなのでその可能性はもちろんあります。

では、"1文字以上含む(制限付き)"場合を計算してみます。

| 種類                         |   文字種数 |   総当たりエントロピー (bits) |   制約付きエントロピー (bits) |
|:-----------------------------|-----------:|------------------------------:|------------------------------:|
| 英小文字のみ                 |         26 |                         56.41 |                         56.41 |
| 英小文字と大文字             |         52 |                         68.41 |                         66.41 |
| 英小文字と数字               |         36 |                         62.04 |                         59.72 |
| 英小文字と大文字と数字       |         62 |                         71.45 |                         66.31 |
| 英小文字と大文字と数字と記号 |         94 |                         78.66 |                         70.16 |


<details><summary>計算コード</summary>

```python
new_scenarios = {
    "英小文字のみ": [26],
    "英小文字と大文字": [26, 26],
    "英小文字と数字": [26, 10],
    "英小文字と大文字と数字": [26, 26, 10],
    "英小文字と大文字と数字と記号": [26, 26, 10, 32],  # Common symbols = 32
}

# Calculate entropy for each new pattern
new_data = {
    "種類": [],
    "総当たりエントロピー (bits)": [],
    "制約付きエントロピー (bits)": [],
}

for name, sizes in new_scenarios.items():
    # Brute-force entropy
    brute_force_entropy = calculate_entropy(sum(sizes), password_length)
    # Constrained entropy
    constrained_entropy = calculate_constrained_entropy(sizes, password_length)
    new_data["種類"].append(name)
    new_data["総当たりエントロピー (bits)"].append(round(brute_force_entropy, 2))
    new_data["制約付きエントロピー (bits)"].append(round(constrained_entropy, 2))

# Convert to DataFrame
new_df = pd.DataFrame(new_data)

# Display DataFrame in Markdown format
new_markdown_table = new_df.to_markdown(index=False)
new_markdown_table
```
</details>

「1文字以上含む」にした場合、「英小文字と数字」の組み合わせが60bit以下になります。
「1文字以上含む」とすると、組み合わせが一部限定されるためパスワードのエントロピーが下がってしまいます。しかし、「小文字と大文字と数字」　などにしておけばエントロピーが下がっても、許容できる範囲であれば制限してしまった方が良いかもしれません。ユーザーが賢明なら、「1文字以上含む」の制限がない方がパスワードの強度が高まりますが、制限をしない場合は小文字英語のみで書く人がいるのでパスワードが想定的に弱くなるかもしれません。
しかしそのような人は、結局パターンを作ってしまうこともあるので厳しい制約でもあまり意味がないような気もします。ここから先は、ブルートフォース攻撃以外の検討になると思います。

## 蛇足

パスワードの生成についてこれまで「英小文字・大文字・数字・記号」の4つを比較してきましたが、日本語はもっと文字種が多いので「日本語を使ったパスワードの方が、パターンが増えるのでは？」と思ったので、ここからは完全な蛇足です。

### 日本語の文字数

さて使用可能な日本語文字一覧をまずは確認してみましょう。

ひらがな一覧はPythonの標準にないので、Unicodeをベースに一覧を出力しました。
その結果、ひらがな一覧が83種あります。

<details><summary>計算コード</summary>

```python
# 日本語の文字数を出力
hiragana = "".join(
    chr(i) for i in range(0x3040, 0x30A0) if "ぁ" <= chr(i) <= "ん"
)

print(f"ひらがなの文字数: {len(hiragana)}")
print(hiragana)
```

</details>

次にカタカナは84種(「ー」を含める)あります。

<details><summary>計算コード</summary>

```python

# カタカナの文字数を出力
katakana = "".join(
    chr(i)
    for i in range(0x30A0, 0x30FF + 1)
    if "ァ" <= chr(i) <= "ン" or "ー" == chr(i)
)
print(f"カタカナの文字数: {len(katakana)}")
print(katakana)
```

</details>

文化庁によると、常用漢字は2136字[(出典)](chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/https://www.bunka.go.jp/kokugo_nihongo/sisaku/joho/joho/kijun/naikaku/pdf/joyokanjihyo_20101130.pdf)あります。

さて、計算してみましょう。
パスワードの長さは12文字です。

<details><summary>計算コード</summary>

```python
# Define the scenarios for Japanese password character sets
japanese_scenarios = {
    "ひらがなのみ": [83],
    "カタカナのみ": [84],
    "常用漢字のみ": [2136],
    "ひらがなとカタカナ": [83, 84],
    "ひらがなとカタカナと常用漢字": [83, 84, 2136],
}

# Password length
password_length = 12

# Calculate entropy for each Japanese scenario
japanese_data = {
    "種類": [],
    "文字種数": [],
    "総当たりエントロピー (bits)": [],
}

for name, sizes in japanese_scenarios.items():
    # Total charset size
    total_charset_size = sum(sizes)
    # Calculate brute-force entropy
    entropy = calculate_entropy(total_charset_size, password_length)
    japanese_data["種類"].append(name)
    japanese_data["文字種数"].append(total_charset_size)
    japanese_data["総当たりエントロピー (bits)"].append(round(entropy, 2))

# Convert to DataFrame
japanese_df = pd.DataFrame(japanese_data)

# Display DataFrame in Markdown format
japanese_markdown_table = japanese_df.to_markdown(index=False)
japanese_markdown_table

```

</details>


| 種類                         |   文字種数 |   総当たりエントロピー (bits) |
|:-----------------------------|-----------:|------------------------------:|
| ひらがなのみ                 |         83 |                         76.5  |
| カタカナのみ                 |         84 |                         76.71 |
| 常用漢字のみ                 |       2136 |                        132.73 |
| ひらがなとカタカナ           |        167 |                         88.6  |
| ひらがなとカタカナと常用漢字 |       2303 |                        134.03 |

流石に漢字が入るとエントロピーが増大しています。
ひらがなのみでも、「英小文字と大文字と数字と記号」に匹敵しているので、これは強そうです。
文字数が少なくなるメリットを考えると、日本語パスワードも結構面白いのではないかなと思いました。

## 最後に

蛇足も長くなりましたが、最初の疑問である「パスワード作成時のバリデーションで「〇〇を1文字以上含む」はパスワードのパターンを減らさないか？」に対する答えとしては、「使用文字の種類による」ということでした。「使用文字の種類」を確保しておけば、必須にしても許容できる程度のパスワードの強度にはなると思います。

むしろ最低文字数を確保して、上限を大きくしておくことの方が効果がありそうです。

最後に日本語パスワードの可能性があると思いました。しかし、ハッシュ化やデータとしての扱いづらさもあるの中と思いました。そこで日本語でパスワードを入れてもらって、それを英語に変換するなどの関数があればパスワードのハッシュ化とかもできるかなと考えています。