Lucky ThirteenはTLS, DTLSのCBCモードを利用する暗号の脆弱性を突く攻撃です。具体的に言うと、CBCモードに対するPadding処理の弱い部分を狙ったPadding Oracle攻撃の一種です。
その影響とか、脅威とか、対処法とかは結構いろんな所で説明されているのですが、単純な興味とか、知識とか、内容を実感したい、というような方が読むことを想定した記事はあまりないように思われたので、その仕組みを説明したいと思います。
TLSパケットの仕組み
まずはじめに、TLSパケットの暗号処理の仕組みを簡単に説明します。
イメージとしてはこんなかんじで、ヘッダ+平文データのMAC(チェックサム的なもの)をとる→パディングをつける→暗号化する、
と言った流れでパケット(レコード)を構築します。
TLSのパディング
ブロック暗号はそのままではブロックの幅に合わないデータを取り扱えないので、パディングを付与して使用します。TLSのパディング処理はとてもシンプルです。(そしてありきたりです)
このように、ブロック長の残りがnのとき、(n-1)をn個埋めるのがTLSのパディングです。
TLSのMAC処理
MACは、復号後にデータが変更されていないことを確認するために使用します。
現在、最もよく使われているのはHMAC-SHA1です。ハッシュを繰り返して
20バイトのMACを生成します。
ここで実はちょっとしたポイントがあります。
HMAC-SHA1はデータ長によって使用されるハッシュ処理の回数が違います。
例えば、~55Byteだと4回のハッシュで済むのですが、56Byte~だと5回必要になります。
タイミングリーク
タイミングリークとは、処理のタイミングからデータや鍵に関する情報が漏れてしまうことを言います。
よくあるのは不正なパケットに対するエラー処理のタイミングリークで、Lucky Thirteenもこのケースに当たります。
適当な64バイトのシーケンスを受信者に復号させてみた場合、基本的にエラーになるわけですが、このエラーパターンは激レアなケースを除くと概ね下記のように分類されます。
- パディングエラー … ほぼ 255/256の確率
- 0x00 で終わる(1Byteパディング) ほぼ 1/256 の確率
- 0x01 0x01で終わる(2Byteパディング) ほぼ 2^-16 の確率
- : (その他レアケース)
ところで、これらについてMACを計算すると、実は0x01 0x01で終わるケースだけが必要なハッシュが少なくなっています。
実装に工夫がないと、この2^-16の確率で発生するケースだけが微妙に早くエラーパケットを返すことになります。
これぐらいの差、そうそう発見できないだろ?って思いますよね。でも、外からの観測で実際にわかった、というのがLucky Thirteen Attackの報告の主旨なのです。
Lucky Thirteen Attack
攻撃者がC*という暗号ブロックを復号したい場合、下記のようなヘッダ+4ブロックのレコードパケットを復号者に送りつけます。
ヘッダ || ブロック1 || ブロック2 || 調整ブロック || 解析対象ブロックC*
復号者は最終ブロックC*を下記のようにCBCモードで復号します。
復号後のブロック = (復号後の(解析対象ブロックC*)) XOR 調整ブロック
この復号後のブロックは先に述べたとおり下記のどれかに類型されます。
- パディングエラー … ほぼ 255/256の確率
- 0x00 で終わる(1Byteパディング) ほぼ 1/256 の確率
- 0x01 0x01で終わる(2Byteパディング) ほぼ 2^-16 の確率
- : (その他レアケース)
3.の「0x01 0x01で終わる」ケースだった場合、C*の最後の2バイトは
調整ブロックの最後の2バイト XOR 0x01 0x01
で得られるわけです。
攻撃者は2^-16の確率でこのケースを手に入れます。このケースが手に入ったかどうかはエラーが返ったタイミングで判断します。
タイミングを検出出来れば攻撃者は調整ブロックとのXORによりC*の最終ブロックの平文の最後の2バイトを取り出せます。
このような調子で次々にブロックを復号できるのですが、実は大変なのは最初の2^-16の部分だけで、
残りは2^-8の確率で見つけることができます。
こうやって攻撃者は2^16+14*2^8回のトライで暗号文を復号できます。
最後に
2^16という数字は小さいでしょうか?大きいでしょうか?
統計的な攻撃方法については述べませんでしたが、同じ平文を送信するセッションが260万回ぐらい、半分程度だとしても130万回ぐらい必要です。検索サイトのログインクッキーだったらこれくらい行ってしまうでしょうか?ちょっとわからないですね。。。
また、攻撃者の位置によってはネットワークノイズの影響をかなり受けると思われます。
いずれにせよ、リスクと投資のバランスを考えた対応が重要だとは思います。
参考
今回、参考にしたのは下記の文書のみです。おそらく、他にも良資料があるとは思いますが。