要約

  • RFC 3218 は、エラー文、応答の有無、処理時間までを暗号インターフェースの出力として扱った。RSAES-PKCS1-v1_5 の不正なブロックと、正しい形式だが誤った内容暗号鍵を持つブロックを区別できれば、反復問い合わせが適応的攻撃になる。
  • random filling は、不正な鍵取り出しを所定長の新しいランダム CEK に置き換え、本文復号と完全性検査まで進める。代替鍵は正解ではない。初期エラーを、通常の誤鍵が起こす後段エラーに見せるための一時的な材料だった。

漏れたのは平文そのものではない。受信者が、隠れた平文の形について下した「はい」か「いいえ」だった。

Daniel Bleichenbacher は 1998 年、その一ビットを積み重ねれば PKCS #1 v1.5 に対する適応的選択暗号文攻撃が成立することを示した。攻撃者は捕捉した RSA 暗号文を数学的に変形し、秘密鍵を持つ相手に送る。復号されたブロックが規定形式に合うかを応答から読み取り、それまでの結果に基づいて次の変形を選ぶ。秘密鍵は一度も外に出ない。それでも受信者の判定列が、隠れた値の範囲を狭めていく。

RFC 3218 はこの問題を Cryptographic Message Syntax に持ち込んだ。2002 年 1 月に Informational として発行され、新しい暗号形式を標準化した文書ではない。CMS ではすでに、本文を守る対称鍵を RSA PKCS #1 v1.5 で運ぶ実装が広く存在した。その互換性を直ちに捨てられない受信者が、どのように振る舞うべきかを扱ったのである。

v1.5 の符号化ブロックは 00 02 で始まり、少なくとも八個の非ゼロ乱数オクテット、区切りの 00、運ばれる値と続く。CMS で最後の値は content-encryption key、CEK である。秘密鍵による RSA 演算が終わっても、出力バイト列がこの文法を満たすとは限らない。

ここには別々の事実が並ぶ。RSA 演算が完了したこと。PKCS #1 の形式が正しいこと。CEK のアルゴリズムと長さが期待通りであること。その CEK が送信者の使った本物であること。本文復号がバイト列を返すこと。MAC、署名、パディング、アプリケーションがその結果を受理すること。内部で区別できなければ運用できないが、外部に区別を渡せばオラクルになり得る。

Million Message Attack という名は、運用上の規模を表していた。捕捉した暗号文 C に対し、攻撃者は乗数 S を選び、C' = C * S^e mod n という関連暗号文を送る。RFC 3218 は、約 2^16 回に一度、変形後の平文が 00 02 で始まり、検討した CMS 条件では全体が 2^20 程度のメッセージと応答になり得ると説明した。

これはあらゆる鍵や実装に共通する固定回数ではない。自動化が脅威の性質を変えることを示す数字である。人間が百万通を一つずつ開いて答えるなら攻撃は目立つ。メーリングリストの自動エージェントや無人ゲートウェイなら、各問い合わせを復号し、分類し、機械的に反応できる。攻撃者は通信量を用意し、受信者が反復能力を提供する。

問い合わせ後の内部状態はいくつもある。PKCS #1 ブロックが不正かもしれない。形式は正しいが CEK が偽物かもしれない。誤った CEK によって完全性検査が落ちるかもしれない。認証されていない CBC なら、ランダムな平文が偶然もっともらしいパディングで終わることもある。変形した問い合わせが本当の CEK を偶然返す可能性は極めて低い。

攻撃者は全ケースを識別する必要がない。最初の「形式不正」と、それ以降の「形式は正しいが鍵が違う」失敗を分けられればよい。別のエラー文字列、応答と沈黙、接続切断、メールのバウンス、署名エラー通知、再現可能な遅延差のどれもが一ビットを運べる。

RFC 3218 の主要対策は random filling だった。PKCS #1 のデコードに失敗した受信者は、そこで停止しない。選択された本文暗号アルゴリズムが要求する長さの CEK を、暗号学的乱数で生成し、RSA からその値が得られたかのように処理を続ける。

架空の鍵で本文を復号し、通常どおりパディング、MAC、署名、アプリケーションの検査を行う。ランダム CEK はほぼ確実に後段で普通の失敗を起こす。外部のエラーと処理時間を、正しく符号化されたブロックが単に誤鍵を含んでいた場合に近づける。

したがって、ランダム CEK は復旧鍵ではない。送信者の秘密を再現せず、本文を救済せず、メッセージを正当化もしない。早期の原因を明かさずに通常の失敗地点まで進むための使い捨て状態である。予測できず、ほぼ確実に間違っていることが、その役割に合っていた。

固定のフォールバック CEK は逆効果になる。テストを再現しやすくし、エラー時の乱数生成を省くため、定数を使いたくなるかもしれない。しかし攻撃者がその値を知れば、その鍵で CMS 本文を暗号化し、意図的に壊した RSA 鍵輸送と組み合わせられる。受信者がフォールバック分岐に入った場合だけ本文が正しく処理される。隠すはずの仕組みが、もっと明瞭な判定器になる。

代替値は毎回新しく、暗号学的に予測不能で、期待された長さでなければならない。再利用すれば、本来観測不能にする分岐へ安定した識別子を与えてしまう。

乱数を作る時点も重要だった。生成器が遅く、失敗後だけ呼び出されるなら、遅延がその分岐を知らせる。RFC 3218 は、すべてのメッセージについてランダム候補を先に作り、鍵取り出しが有効なら捨てる方法を示した。成功と失敗の双方が、同程度の乱数生成コストを負う。

それでも実装全体の定時間性が証明されるわけではない。メモリアクセス、解析、ログ、ワーカーキュー、メール応答、アプリケーション処理には差が残り得る。狙いは、同じエラー文だけで安全になったと思い込まず、目立つ時間分岐も消すことだった。

CEK の長さは別の境界を作る。汎用 RSA/PKCS #1 層は符号化の正当性を判断できても、上位アプリケーションが 8、16、24、32 バイトのどれを期待するか知らない場合がある。下位層が値を返し、CMS 層が異なる例外で不正長を拒否すれば、オラクルは上の層へ移動しただけである。

本文アルゴリズムを知る層も、不正長の値をランダム CEK に置き換える必要がある。安全性はソフトウェア境界をまたぐ。必要な文脈を持たない暗号プリミティブだけでは、隠すべきすべての異常を判断できない。

RFC 3218 は、攻撃コストを上げるため、全パディングオクテット、CEK 長、該当する DES 系のパリティビットまで慎重に検査するよう勧めた。条件が増えるほど、ランダム変形が通る確率は下がる。

しかし、発生頻度の低いオラクルもオラクルである。どの条件で落ちたかを外部応答が示す限り、攻撃者は問い合わせ数を増やして同じ情報を集められる。

認証のない CBC は、「復号できた」という表現の弱さも示す。ランダムな平文が偶然パディングらしく終わることがある。最後の一バイトだけを長さとして切り落とす実装なら、RFC 3218 は見かけ上の成功を約 1/32 と見積もった。必要な全パディングバイトを検査すれば約 1/255 へ下がる。

いずれの一致も、ランダムな本文に意味を与えない。MAC や署名はより信頼できる後段の拒否点になる。それでも初期の PKCS #1 判定を別に公開してよいことにはならない。初期分岐を後段失敗へ溶かすことが防御の中心だからだ。

OAEP は、より根本的な移行先だった。PKCS #1 v2.0 は RSAES-OAEP を規定し、RFC 3218 は今回の攻撃がそれに適用されないとした。ただし OAEP は v1.5 とワイヤ互換ではない。送受信者、証明書、アルゴリズム識別子、既存 CMS ソフトウェアが同じ変更に対応しなければならない。

優れた方式を名指しするだけでは、稼働中の旧方式は消えない。random filling は共存期間の対策だった。移行が終わるまで、レガシー受信者が外部へ返せる情報を狭くする。

TLS も RSA で暗号化した premaster secret に似た危険を抱え、形式やバージョンの異常を明かす代わりにランダム値で処理を続けるよう仕様化した。原理は共通でも、プロトコルの観測点は異なる。TLS ハンドシェイク、CMS メッセージ、メールエージェントは、それぞれ別の状態遷移と応答を持つ。

一般則は RSA のさらに外側にある。内部パーサーは、外部プロトコルが安全に答えられない質問へ答えてはならない。どこまで処理を継続し、どの最終拒否を見せ、どの副作用を抑えるかは、外側のプロトコルが決める。

RFC 3218 は random filling が送信者を認証するとも、全タイミング漏えいを消すとも、特定実装の安全を証明するとも述べていない。配備状況も示さない。その成果はもっと限定的だった。反復可能な内部差異があるなら、エラー処理そのものが暗号システムになると明確にしたのである。