パディングオラクル攻撃

暗号学において、パディング オラクル攻撃とは、暗号メッセージのパディング検証を使用して暗号文を解読する攻撃です。暗号学では、可変長の平文メッセージは、基盤となる暗号プリミティブと互換性を持たせるためにパディング (拡張) される必要があります。この攻撃は、メッセージが正しくパディングされているかどうかの問い合わせに自由に応答する「パディングオラクル」の存在に依存しています。情報は直接提供される場合もあれば、サイドチャネルを通じて漏洩される場合もあります。

パディングオラクルを使用した最も古い攻撃は、 1998年のBleichenbacherの攻撃であり、PKCS #1 v1.5パディングを使用してRSAを攻撃します。 ^[1]「パディングオラクル」という用語は、対称ブロック暗号内で使用されるCBCモード復号化に対するSerge Vaudenayの攻撃の後、2002年に文献に登場しました。 [ ^{2 ]}両方の攻撃の変種は、最初の発表から10年以上経った今でも成功を収めています。^{[1] [4] [5]}

1998 年、ダニエル ブライヘンバッハは、後にブライヘンバッハの攻撃(「ミリオン メッセージ攻撃」とも呼ばれる)として知られるようになった攻撃に関する重要な論文を発表しました。この攻撃では、 PKCS #1 v1.5パディングを使用したRSAに対してパディング オラクルを使用しますが、この用語は含まれていません。後の著者は、この攻撃をパディング オラクル攻撃として分類しました。^[1]

Manger (2001)は、PKCS #1 v1.5パディングの代替であるPKCS #1 v2.0「OAEP」に対する攻撃を報告している。^[6]

対称暗号化では、パディングオラクル攻撃をCBC モードの動作に適用できます。パディングの有効性に関するデータが漏洩すると、攻撃者は暗号化キーを知らなくても、オラクルのキーを使用してオラクルを介してメッセージを復号化 (場合によっては暗号化) できるようになります。

Bleichenbacher による PKCS #1 v1.5 を使用した RSA への攻撃と比較すると、Vaudenay による CBC への攻撃ははるかに効率的です。^[1]どちらの攻撃も、当時一般的に使用されていた暗号システムをターゲットにしています。CBC は、Secure Sockets Layer (SSL) で使用されていた元のモードであり、TLS でも引き続きサポートされていました。^[4]

復号ソフトウェアがオラクルとして動作することを防ぐために、いくつかの緩和策が実行されてきましたが、タイミングに基づく新しい攻撃により、このオラクルが繰り返し復活しています。TLS 1.2では、CBCに依存しない追加のデータモードを備えた認証された暗号化がいくつか導入されています。 ^[4]

ブロック暗号における CBC 復号化の標準的な実装は、すべての暗号文ブロックを復号化し、パディングを検証し、PKCS7 パディングを削除し、メッセージのプレーンテキストを返すことです。サーバーが一般的な「復号化に失敗しました」エラーではなく「無効なパディング」エラーを返す場合、攻撃者はサーバーをパディング オラクルとして使用して、メッセージを復号化 (場合によっては暗号化) できます。

CBC復号の数式は

${\displaystyle P_{i}=D_{K}(C_{i})\oplus C_{i-1},}$

${\displaystyle C_{0}=IV.}$

上に示したように、CBC 復号化では、各プレーンテキスト ブロックを前のブロックと XOR します。その結果、ブロック内の 1 バイトの変更は、内の 1 バイトに対応する変更を加えます。 ${\displaystyle C_{1}}$${\displaystyle P_{2}}$

攻撃者が 2 つの暗号文ブロックを持っていて、2 番目のブロックを復号化して平文 を取得したいとします。攻撃者は の最後のバイトを変更し( を作成)、サーバーに送信します。サーバーは、最後に復号化されたブロック ( ) のパディングが正しいかどうか (有効な PKCS#7 パディング) を返します。パディングが正しい場合、攻撃者は の最後のバイトがであること、最後の 2 バイトが 0x02 であること、最後の 3 バイトが 0x03、…、最後の 8 バイトが 0x08 であることがわかります。攻撃者は、最後のバイトが 0x01 になるように、最後から 2 番目のバイトを変更 (任意のビットを反転) できます。 （あるいは、攻撃者は前のバイトを反転し、その位置をバイナリ検索してパディングを特定することもできます。たとえば、最後から3番目のバイトの変更は正しくても、最後から2番目のバイトの変更が間違っている場合、最後の2バイトは0x02であることがわかっているため、両方とも復号化できます。）したがって、 の最後のバイトは に等しくなります。パディングが正しくない場合、攻撃者は の最後のバイトを次の可能な値に変更できます。最大で、攻撃者は の最後のバイトを見つけるために256回の試行を行う必要があります。これは、可能性のあるバイトごとに255回の試行（256の可能なバイトから鳩の巣原理によ​​り1つを引いたもの）と、あいまいなパディングを排除するための追加の試行を1回行う必要があります。^[7]${\displaystyle C_{1},C_{2}}$${\displaystyle P_{2}}$${\displaystyle C_{1}}$${\displaystyle C_{1}'}$${\displaystyle (IV,C_{1}',C_{2})}$${\displaystyle P_{2}'}$${\displaystyle D_{K}(C_{2})\oplus C_{1}'}$${\displaystyle \mathrm {0x01} }$${\displaystyle D_{K}(C_{2})}$${\displaystyle C_{1}'\oplus \mathrm {0x01} }$${\displaystyle C_{1}'}$${\displaystyle P_{2}}$

の最後のバイトを決定した後、攻撃者は同じ手法を使用して、 の最後から 2 番目のバイトを取得できます。攻撃者は、 の最後のバイトを に設定することにより、 の最後のバイトを に設定します。次に、攻撃者は上記と同じアプローチを使用し、今度はパディングが正しくなるまで (0x02、0x02)、最後から 2 番目のバイトを変更します。 ${\displaystyle P_{2}}$${\displaystyle P_{2}}$${\displaystyle P_{2}}$${\displaystyle \mathrm {0x02} }$${\displaystyle C_{1}}$${\displaystyle D_{K}(C_{2})\oplus \mathrm {0x02} }$

ブロックが 128 ビット (たとえばAES )、つまり 16 バイトで構成されている場合、攻撃者は256⋅16 = 4096 回以内の試行で平文を取得できます。これは、128 ビットのキーをブルートフォース攻撃するために必要な試行回数よりも大幅に高速です。 ${\displaystyle P_{2}}$${\displaystyle 2^{128}}$

CBC-R ^[8]は 復号化オラクルを暗号化オラクルに変換し、主にパディングオラクルに対して実証されています。

パディングオラクル攻撃を使用すると、CBC-R は任意の平文に対して初期化ベクトルと暗号文ブロックを作成できます。

• 任意の暗号文を復号するP _i = PODecrypt( C _i ) XOR C _i−1、
• 前の暗号ブロックC _x−1を自由に選択し、
• 有効な暗号文/平文のペアC _x-1 = P _x XOR PODecrypt( C _i )を生成します。

Nブロックの長さの暗号文を生成するには、攻撃者はN回のパディング オラクル攻撃を実行する必要があります。これらの攻撃は連鎖しており、メッセージの末尾 ( C _N ) からメッセージの開始 ( C ₀ 、IV) まで逆順に適切な平文が構築されます。各ステップで、パディング オラクル攻撃を使用して、前に選択された暗号文の IV が構築されます。

CBC-R 攻撃は、復号化する前に暗号文を認証する (メッセージ認証コードなどを 使用して) 暗号化方式に対しては機能しません。

CBCに対する最初の攻撃は、2002年にSerge Vaudenayによって公開されました。^[3]この攻撃の具体的なインスタンス化は、後にSSL ^[9]とIPSec [ ^{10 ] に対して実現されました。 [ 11]また、} JavaServer Faces、Ruby on Rails ^[12]、ASP.NET ^{[13] [14] [15]}などのいくつかのWebフレームワークや、 Steamゲームクライアントなどの他のソフトウェアにも適用されました。^{[16] 2012年には、} PKCS 11暗号化トークンに対して有効であることが示されました。^[1]

これらの初期の攻撃は、TLSの公開発表後にほとんどのTLS実装者によって修正されましたが、2013年に公開された新しい亜種であるLucky Thirteen攻撃では、タイミングサイドチャネルを使用して、以前に修正された実装でも脆弱性が再び発生しました。2014年初頭の時点で、この攻撃は実際の運用では脅威とは見なされなくなりましたが、特定のクラスのマシンに対しては理論上はまだ実行可能です（信号対雑音比を参照）。2015年現在^{[アップデート]}、インターネットトラフィックの保護に使用される暗号化プロトコルに対する攻撃の開発で最も活発な分野は、Logjam ^[17]やExport RSA/FREAK ^[18]攻撃などのダウングレード攻撃であり、より安全な暗号化操作が利用可能な場合に、クライアントをだましてレガシークライアントとの互換性のために提供されている安全性の低い暗号化操作を使用させます。POODLE ^[19]と呼ばれる攻撃（2014年後半）は、SSL 3.0へのダウングレード攻撃と、古くて安全でないプロトコルに対するパディングオラクル攻撃の両方を組み合わせて、送信データの侵害を可能にします。2016年5月、CVE - 2016-2107で、OpenSSLのLucky Thirteenに対する修正により、別のタイミングベースのパディングオラクルが導入されたことが明らかになりました。^{[20] [21]}