まとめ
- 現代暗号の主流は、計算量的安全性に基づく方式
- 復号方式（公開）＋復号鍵（非公開）の構成
- 力ずくの解読法である全鍵探索を事実上不可能にする、復号鍵の多様さが必要
- ただし、全鍵探索 ≠ 解読 に着目した戦略もある
- 全鍵探索できても、解読できない場合もある
- 典型的にはワンタイムパッド
- イメージとしては
- 主流暗号の強度（bit数） ≒ ゲーム機のスペック
- 実質的な暗号強度 ≒ ゲーム機の面白さ
背景
クロム拡張作成で、他者とのノート共有をリリース予定です。他者との共有で問題になるのは、メールや名前などの情報の扱いです。うっかりDOM上やログ上に出そうものなら、そのページの他のスクリプトに漏れてしまいます。
情報自体の扱いに気を付けるのはもちろんですが、生で情報を持つこと自体がリスクであるため、暗号化について復習・考察してみました。
暗号が解けるという事
現代の主流暗号（共通鍵）の場合
| 元データ | 暗号鍵 | 暗号データ | 復号鍵 | 復号データ |
|---|---|---|---|---|
| こんにちは | A | l�3��t | A | こんにちは |
| こんにちは | A | l�3��t | B | ��U�B |
| こんにちは | A | l�3��t | C | 2C�l� |
暗号鍵に対応した正しい復号鍵を用いた場合、当然元データが復元されます。ここで違う鍵で復号処理を行った場合、一見ランダムのデータになるため、ほとんどの場合で文字化けが発生します。つまり、復号鍵が間違っている、というヒントを与える事になります。
このヒントは、元データの性質について文脈から予測できるほど、元データが長いほど大きな情報になります。
- メールアドレスと分かっていれば、UTF16の1文字の16bitの中、高々6bitしか有効な文字がない
- メールアドレスが30文字もあれば、300bit分の情報になるので、256bit鍵なら正解か不正解かがほぼ確実にわかる
もちろん、鍵のbit数を安全性の根拠とした主流暗号の場合、こういうヒントを与えても、なお十分な強度を持つように設計されています。つまり、ヒントを与えるという質的弱点を、圧倒的な鍵という量でカバーしていることになります。DQで言えば、必ず痛恨の一撃を食らっても、味方が1077人もいれば大丈夫
ワンタイムパッドの場合
| 元データ | 暗号鍵 | 暗号データ | 復号鍵 | 復号データ |
|---|---|---|---|---|
| こんにちは | A | l�3��t | A | こんにちは |
| こんにちは | A | l�3��t | B | さようなら |
| こんにちは | A | l�3��t | C | お腹減った |
ちょっと強調して書いていますが、重要なのは元データと同じ長さの、あらゆるデータに復号される可能性があることです。このため、仮に全鍵探索できたとしても、妥当な復号データ候補が事実上無数にあって、どの鍵が正しいか分かりません。DQで言えば、マヌーサ掛けているので攻撃が当たらない
マヌーサをかける鍵数以外で実質的な暗号強度を上げるには
例えば、メールアドレスを暗号化しようと思ったら、以下の様な点に気を付けると、実質的な暗号強度が上がるでしょう。
- 使われる文字種だけを最小限のbit数に押し込めるshrinkされたバイナリ表現に変換してから暗号化
- 文字種だけでなく、複数文字のパターン（.comとか.co.jpとか）を最小限に押し込める様、辞書固定の圧縮をする
上記の様な点に気を付ければ、復号パターンに「correct@sample.co.jp」以外に「wrong@test.net」や「foo-bar@baz.com」などが多数混ざります。攻撃者に対するこうかはばつぐんだ