技術者ブログ

はじめに

この秋にウェブアプリケーションセキュリティの分野で大きな注目を集めたBEAST(Browser Exploit Against SSL/TLS)の全貌が、ほぼ明らかになってきました。事前に話題になっていたほどの大きなインパクトを現状のインターネットに及ぼすものではなさそうですが、その中で使われている攻撃テクニックは今後、さらに応用されていく可能性を秘めています。HTTPSに対する攻撃という意味ではひとつの大きなターニングポイントであったと感じます。

私たちが開発しているSaaS型WAFサービス「Scutum(スキュータム)」はWAFであると同時にHTTPSサーバでもあるため、BEASTが及ぼす影響について非常に気になっており、このたび調査を行いました。本エントリから数回に分けて、BEASTについての情報を中心にお届けします。まず今回は、BEASTの攻撃技術のベースとなっている「CBCモードに対する選択平文攻撃(Chosen Plaintext Attack)」について、実際にJavaのコードを用いて検証してみます。

なお、BEASTに関連するエントリ中、文章中に登場するアリスとボブは正規のユーザあるいはサーバ管理者を意味し、イヴは攻撃者を意味します。

選択平文攻撃とは

「選択平文攻撃」はChosen Plaintext Attackのことで、「選択された平文を用いた攻撃」を意味しますが、ここで「選択する」のは攻撃者であるイヴです。アリスがボブへ秘密のメッセージを送る際に、イヴはすべての（ブロックについて）暗号文が入手可能であり、さらに任意の平文をアリスが送るメッセージ内に挿入することができる、ということが前提となる攻撃になります。選択平文攻撃では攻撃の目的として秘密鍵そのものの入手が挙げられることがありますが、ことBEASTに関してはそうではなく、アリスが書いた平文を手に入れること（つまり復号）が目的となります。

平文全体は、アリスが書いた部分と、イヴが書いた部分から成り立ちます。このうちアリスが書いた内容は、イヴからはわからない、という状態です。なお、アリスが書いた部分が先頭に位置するのか、あるいは別の場所に位置するのか、等についてはここではひとまず置いておくものとしますが、本エントリ後半で解説するJavaのコードを用いた検証の段階では、アリスは先頭の部分を書いているものとしています。

暗号化された秘密の手紙が郵便などの手段で送られる様子をイメージする場合、イヴが、アリスが送るメッセージ内に任意の平文を紛れ込ませる、というケースは通常考えられません。しかしHTTPSのようにコンピュータネットワーク上で行われる暗号通信になると、この攻撃が現実味を帯びてきます。

CBCモードに対する選択平文攻撃とは

共通鍵を使ったブロック暗号では、同じ平文がいつも同じ暗号文になってしまわないようにするため、CBCモードが使われることが一般的です。最初にIV(Initialization Vector)と呼ばれるランダムなバイト列を生成し、暗号化する前に平文とxor処理を行います。2ブロック目では、1ブロック目の暗号文をIV代わりに使い、平文とxorしてから暗号化します。これを繰り返すことで、たとえ同じ平文が繰り返し登場するような場合でも、暗号文からはそれが見抜けないことになります。

BEAST以前にSSLに対する選択平文攻撃を指摘していたこちらの記事のASCIIアートがわかりやすいので、お借りして掲載します。

      IV      P1      P2     P3

      |       |       |       |
      |       v       v       v
      |    > XOR   > XOR   > XOR
      |   /   |   /   |   /   |
      |  /    v  /    v  /    v
      | /     E /     E /     E
      |/      |/      |/      |
      v       v       v       v

      IV      C1      C2      C3

• IV:　Initialization Vector
• Pn:　平文(nは何ブロック目かを表す数字)
• Cn:　暗号文
• E:　暗号化処理

ここで、選択平文攻撃が実施される例として、以下のような場合を考えます。

• P1の内容はアリスが決める（ボブに送りたい、秘密のメッセージ）
• P2以降の内容はイヴがコントロールできる
• イヴの目的はP1を知ること
• イヴはメッセージ全体の長さをコントロールできる（好きなだけ、平文に任意のデータを追加できる

IVとP1をxorしたものを暗号化するとC1になるので、次の式が成り立ちます。

E( IV xor P1 ) = C1

また、C1は2ブロック目でIV代わりに使用されるので、次の式が成り立ちます。

E( C1 xor P2 ) = C2

iブロック目について考えると、次の式が成り立ちます。

E( Ci-1 xor Pi ) = Ci

P1を得るために、イヴは単純にP1を予想して、片っ端から試していきます。前述したようにIVが使用されるCBCモードであるため、ブルートフォース攻撃が成功しイヴがP1と同じ内容の平文を暗号化しても、暗号化された結果はC1とは等しくなりません。そのため、イヴはブルートフォース攻撃に成功したことに気づくことができないはずです。

しかし、暗号文を入手可能であるイヴは平文のXORで使用される値がCi-1であることがわかっているため、CBCモードであることの（アリスとボブにとっての）利点を打ち消すことができます。これは次のように行われます。

イヴは、自分自身がブルートフォース攻撃に成功したかどうかを知るためには、暗号化された（i番目のブロックの)Ciの値が、C1の値とまったく同じとなるかどうかを調べるしかありません。仮に予想に成功した場合には、次の式が成り立ちます。

Ci = C1

前述した式の内容より、このときは次が成立することになります。

E( Ci-1 xor Pi ) = C1

さらにC1を展開すると次のようになります。

E( Ci-1 xor Pi ) = E( IV xor P1 )

暗号化処理であるEは両辺で共通であるため、これを打ち消します。

Ci-1 xor Pi = IV xor P1

両辺にIVでxorを行います。

IV xor Ci-1 xor Pi = IV xor IV xor P1

IV同士のxorを打ち消すことができます。

IV xor Ci-1 xor Pi = P1

最終的に、左右を入れ替えて次のようになります。

P1 = IV xor Ci-1 xor Pi

このときイヴはIVとCi-1、Piという右辺の値をすべて入手しているので、xorの計算を行うことにより、目的であったP1の内容を手に入れることができます。これがCBCモードに対する選択平文攻撃です。

特徴的な点として、以下が挙げられます。

• ブルートフォース攻撃の試行回数は暗号化に用いられているアルゴリズム、鍵長と関係がない（ブロックサイズについては影響を受ける場合があります）
• 攻撃に成功しても秘密鍵を得ることはできない

実際には上の例のように、P1のブロックの内容をまるごとブルートフォースで推測するのは時間がかかりすぎる（メッセージ全体のサイズが大きくなりすぎる）ため現実的ではありません。そのため、ブロック中の一部のデータのみが不明である（アリスが決定している）というケースに対する攻撃が現実的となります。

Javaのコードを用いた検証

前項のような暗号に関する内容は、文章だけ読んでいると難しく感じるかもしれませんが、コードを書いてみると一目瞭然となります。CBCモードに対する選択平文攻撃は暗号のアルゴリズムに関わらず攻撃可能であるため、ここではBEASTが攻撃したAESとは異なるものとして、Blowfishを選択してみました。AESでは1ブロックのサイズが16バイトであるのに対し、Blowfishでは半分の長さの8バイトとなります。

ここでは非常に単純化したケースを想定して検証を行います。アリスはメッセージの最初の1バイト目にデータを配置します。この1バイト目が何であるかはイヴにはわからず、これを知ることが攻撃の目的となります。2バイト目以降はすべてイヴのコントロール下となり、イヴは好きなだけ、好きな値をここに配置することができるものとします。これは非常に極端な例にも見えますが、実際にはBEASTが行う攻撃はこれに非常に似た形となります。

検証に用いたコードはこちらよりダウンロード可能です（ライセンスはGPLです）。次のように実行することができます。

java -jar cbc_attack_example.jar

実行すると、Blowfishで暗号化された通信に対して選択平文攻撃が実行され、次のような出力となります。IVはランダムに生成されるため、出力の詳細は毎回異なります。

IV:ccdff23f7b826d4f
C1:cd726e91e1f90f93
--Brute force attack started--
C0 : 6b761f9f5fa73671
C1 : 74be09ca7181473b
C2 : 653316d29be790f6
C3 : 0520ddd7a8358793
C4 : 46ba98768ef6ac6e
(中略)
C64 : 7fef52caaafda9bb
C65 : b7774b6dd7d33104
C66 : a22a37c54fa84425
C67 : 65ce8fa069305ba3
C68 : f282fc03b096a4bc
C69 : cd726e91e1f90f93
--FOUND--
The value of the target is 'E'

上記出力の中で、2行目のC1の値と、下から3行目のC69の値が一致しており、ブルートフォース攻撃が成功していることがわかります。

コード内容の解説

検証コードの中心となるクラスであるMApp1クラスについて、簡単なコードの解説を掲載します。

String keyStr = "DEADBEEF";
byte[] keyByte = MStringUtil.hexStringToByteArray( keyStr );
key = new SecretKeySpec( keyByte, ALG );

暗号化に使われる共通鍵を定義しています。

encryptCipher = Cipher.getInstance( ALG + "/" + MODE + "/" + PADDING );

in = new PipedInputStream();
pout = new PipedOutputStream( in );

encryptCipher.init( Cipher.ENCRYPT_MODE, key );
OutputStream out = new CipherOutputStream( pout, encryptCipher );

暗号化を実行するCipherクラスのインスタンスを生成し、続いて通信経路をシミュレートするためのストリームを定義します。ここではCipherOutputStreamと組み合わせてPipedStreamを使います。ストリームへのデータの書き込みは自動的に暗号化されますが、ストリームからの読み込みは暗号化されたバイト列がそのまま出てきます（復号されていません）。これによって、イヴのネットワーク上での盗聴をシミュレートします。

SecureRandom random = new SecureRandom();
byte[] ivSeed = new byte[ 8 ];
random.nextBytes( ivSeed );
out.write( ivSeed );
byte[] encIV = read();
System.out.println( "IV:" + MStringUtil.byteToHexString( encIV ) );

ランダムなバイト列を生成し、ストリームに書き込みます。そして暗号化されたバイト列をIVとして使用します（通常のCBCモードの通信では、生成したバイト列は暗号化せず、そのままIVとして利用することが多いようです）。read()関数はストリームから読み込み可能なバイト列を取得するユーティリティメソッドで、イヴの盗聴によるデータ取得をシミュレートします。

String valueOfAlice	= "E";		//1byte
String valueOfEve	= "FFFFFFF";	//7bytes
String p1Str = valueOfAlice + valueOfEve;

アリスが送る秘密の文字を定義します。ここでは前述したようにたった1バイトでの検証となります。ここでは例として大文字の「E」を使用していますが、これはE以外にしても問題ありません。イヴの目的はこの「E」という文字を得ることとなります。

続いてイヴは「FFFFFFF」という7バイトのデータをまず最初に送るものとします。これは、7バイトの長さであれば内容はどんなものでも意味的に変わりはありません。7バイトのデータをアリスの1バイトのデータにくっつけることで、ちょうどBlowfishの暗号化ブロックの長さである8バイトとなります。これによって、平文の1ブロック目であるP1の内容は「EFFFFFFF」となります。

byte[] p1 = p1Str.getBytes();
out.write( p1Str.getBytes() );
out.flush();
byte[] c1 = read();
String c1Str = MStringUtil.byteToHexString( c1 );
System.out.println( "C1:" + c1Str );

P1が暗号化されてネットワーク上を通る様子をイメージします。read()によって、イヴが盗聴可能な値である、「P1が暗号化されたデータ」つまりC1のバイト列が得られます。

byte[] ci_1 = Arrays.copyOf( c1, c1.length );
byte[] p1expected = Arrays.copyOf( p1, p1.length );
System.out.println( "--Brute force attack started--" );
for( int i = 0; i < 256; ++i )
    {
    p1expected[ 0 ] = ( byte )i;
    byte[] bi = MSecurityUtil.xor( encIV, p1expected );
    byte[] pi = MSecurityUtil.xor( bi, ci_1 );
    out.write( pi );
    out.flush();
    byte[] ci = read();
    String ciStr = MStringUtil.byteToHexString( ci );
    System.out.println( "C" + i + " : " + ciStr );
    if( ciStr.equals( c1Str ) )
        {
        System.out.println( "--FOUND--" );
        System.out.println( "The value of the target is '" + new String( p1expected ).substring( 0, 1 ) + "'" );
        break;
        }
    ci_1 = ci;
    }

アリスが決めた1バイト目は256通りの可能性があります。ここでは単純に0から順番にブルートフォース攻撃を行います。先述したように下記が成り立ちます。

P1 = IV xor Ci-1 xor Pi

そのため、「P1と予想されるバイト列」であるp1expectedとIVでxor処理を行い、さらにCi-1を意味するCi_1との間でxor処理をしてからストリームに書き込みます。暗号化の結果得られるバイト列が1ブロック目の暗号化の結果であるC1と同じであれば、ブルートフォース攻撃に成功したと判断し、p1expectedの内容はP1と等しいと判断できます。

このように、たった256回の試行で必ずアリスの文字を特定することができます。仮にアリスのメッセージの長さが2バイトであれば、256*256となり、最大で65536回の試行が必要となります。3バイトであればさらに256倍の試行が必要になる可能性があります。つまりCBCモードに対する選択平文攻撃では、イヴが、アリスのメッセージを含むブロックについて、何バイトを制御可能であるか、という点が攻撃の可能性を大きく左右する要素となります。

BEASTが目を付けたのはまさにこの点であるのですが、これについては次回詳しく解説を行いたいと思います。