PKCS#1（v.1.5）に対する適用的選択暗号文攻撃の拡張

2.1.2

^における

Bleichenbacher

の攻撃は暗号学的に安全ではないが、実用的な攻撃ではな かった。

Klima

^、

Pokorny

^、

Rosa

^は

2003

^年、

Bleichenbacher

の攻撃を拡張した、現実的 に攻撃可能なサイドチャネル攻撃を提案した

[34]

^{。そこでは、}

SSL/TLS

^{プロトコルに利用}

されている

PKCS#1

^（

v.1.5

）の拡張フォーマットに対し、サーバの復号した平文が正しい フォーマットであるとき、その平文に含まれるバージョン値をチェックした結果から、ク ライアントに返すエラーメッセージが異なるという脆弱性が指摘されている。本攻撃は、

平文のフォーマットのチェックに加えて、

SSL/TLS

のバージョン値もチェックするオラク ルを用いて平文の一部を露呈させることにより、

Bleichenbacher

の攻撃と同様の手法を利 用できる攻撃である。さらに、本攻撃は、

Bleichenbacher

の攻撃における平文を得るアル ゴリズムを改良することにより、実用的な攻撃となっている。ランダムに選択したインタ

2/3

HASH Parameter

Seed Hash Padding Secret

Hash

Mask2 Mask1

Plaintext 00

Ciphertext RSA MGF

MGF

=

図

2.1.3.1 RSAES-OAEP Decording

スト結果も紹介されている。この攻撃に関し、

2003

^年

3

^月

19

^日、

OpenSSL 0.9.6b

^～

0.9.6i

^、

0.9.7

^及び

0.9.7a

に対するセキュリティパッチが公開されている。

SSL/TLS

プロトコルにおける暗号化フォーマット（

S-PKCS-conforming

^{）は次のとおりで}

ある。

EB = 00∥

BlockType

^∥

PaddingString

^∥00∥

DataBlock

ここで、EB は k

bytes

^{の長さを有し、}

BlockType

^{は 02、}

PaddingString

^は(k-51)

bytes

^長の

非零擬似乱数、

DataBlock

^{は 48}

bytes

^{の暗号化対象（例えば}

premaster-secret

^{）であり、}

最初の 2

bytes

^が

SSL/TLS

のバージョン値になっている。ただし、k は RSA の公開鍵 n の byte 単位の長さを表している。

本フォーマットに対し、RSA 暗号処理により得られる暗号文 c は、

n m

c

^{= e}

mod

となる。ただし、m は EB の整数値、e は RSA の公開鍵を表している。SSL では、RSA に よる鍵交換プロトコルにおいて、暗号文 c をサーバに送信する。サーバは、受け取った暗号 文 c に対し、次のように動作する。

ⅰ）サーバは復号された平文が

S-PKCS-conforming

であるかどうかをチェックする。その 結果、平文が

S-PKCS-conforming

でなければ、サーバは新しい

premaster-secret

^をラン

ダムに生成する。そして、クライアントの

Finished

メッセージを受信後、すぐに通信は切 断される。

ⅱ）サーバは各

S-PKCS-conforming

^{平文をチェックして、}

SSL/TLS

^{のバージョン値が正}

しいかどうかを判断する（現在のバージョンは

3.0

^と

3.1

である）。このバージョン値テス トに失敗したら、サーバは区別可能なエラーメッセージを出す。ただし、テストは

S-PKCS-conforming

ではない平文には行われない。

オラクル（

bad-version-oracle: BVO

）は、攻撃者から送られてきた暗号文の復号結果が

S-PKCS-conforming

^{であり、かつ}

SSL/TLS

のバージョン値が正しいかどうかをチェック し、その結果を攻撃者に返す役割をする。

BVO

を用いた攻撃手法の詳細は以下のとおりである。

攻撃者は、上記の暗号文 c に対し、以下の計算により得られた c’を

BVO

^に送る。

n cs

c

'

^{= e}

mod

BVO における復号結果は次のようになり、

BVO

^{は EB’が}

S-PKCS-conforming

^{であるとき、}

バージョン値が正しいかどうかをチェックして、攻撃者にその結果を返す。

n ms

n s

c n c

m '

⁼

'

^d

mod

^{= d}

mod

⁼

mod

ただし、EB’は m’の暗号化フォーマット、d は RSA の秘密鍵を表している。約 1/2¹⁶の確率

で、EB’は以下のような復号結果となる。

EB’ = 00∥02∥

stuff1

^∥00∥

major

^∥

minor

^∥

stuff2

ただし、

major

^、

minor

^{はそれぞれ}

SSL/TLS

^の

major

^{バージョン値、}

minor

^{バージョン値}

を表している。ここで、

stuff1

^と

stuff2

は、一般的に不正な復号結果になるが、もともと の EB の情報が一部露呈していることになる。

さらに、攻撃者は

Bleichenbacher

の攻撃と同様のアルゴリズムを用いることにより、EB を得ることができる。

ただし、暗号化フォーマットを

S-PKCS-conforming

^{、オラクルを}

BVO

、E と F をそれぞれ

1 256

* 255 3

) 256 256

256 (

* 255 0 ) 256 256

256 (

* 255 2

255 / ) 1 256 ( 256 2

256

* 1 256

* 1 256

* 1 2

48

0 46

47 49

4 3

51 49

49 4

3

−

−

=

+ + +

+ + +

+ +

+

=

− +

= +

+ +

+

=

−

−

−

−

−

B B F

B B

E

k k

k k

k

K K

K

と置き換えることとする。

また、アルゴリズムの各ステップにおいて、次の手法や性質により攻撃の効率化が行われ ている。

ⅰ）step 2: Parallel-Threads Method

Parallel-Threads Method はM_i−1における複数の区間に対して、多重処理を行う手法であ る。この手法は、すべての区間に対し暗号文cs^e

mod

n^が

S-PKCS-conforming

^{であるよう}

な s の探索を行い、その s を見つけた場合には、その都度全区間の更新及び不要な区間の消 去を行うというものである。

ⅱ）step 2.b: Beta Method

Beta Method は暗号文cs^e

mod

n^が

S-PKCS-conforming

であるような s を効率良く探索す る手法である。この手法は、c

(

s_i

)

^e

mod

n^とc

(

^sj

)

^e

mod

^{nがともに}

S-PKCS-conforming

であるような sⁱ、s^jを線形結合して得られた s に対し、cs^e

mod

n^{も S-PKCS-}

conforming

であるという性質を利用している。

ⅲ）

step 3:

^{範囲の対称性}

範囲の対称性は暗号文cs^e

mod

n^が

S-PKCS-conforming

であるような大きい s をより小さ い値に変換するために利用される性質である。この変換は、対称性を保存しながら平文の 取りうる値の範囲を変換可能であるという性質を利用している。

攻撃の複雑性は

BVO

コール数により決定される。

1200

^{個の暗号文に対し、}

50

％の攻撃が成功するのに必要な

BVO

コール数として次のよう な測定結果が記されており、サーバの公開鍵の法は長さ8r（r

:

^整数）

bits

^{を使用すべき}

であると述べられている。

・N =

1024 bits

^：

13.34 million

^以下

・N =

1025 bits

^：

1.20 million

^以下

・N =

2048 bits

^：

19.9 million

^以下

・N =

2049 bits

^：

3.47 million

^以下

鍵長

1024 bits

^の

RSA

^を用いた

SSL

^サーバ（

2x Pentium

^Ⅲ

/1.4 GHz, 1GB RAM, 100 Mb/s, OS RedHat 7.2, Apache 1.3.27

）における攻撃テストとして、以下のような結果が記されて いる。

・

67.7 BVO calls/s

・全攻撃に対する中間時間：

54

^時間

42

^分

さらに、常に成功するというわけではないが、インターネット上の

611

^個の

SSL/TLS

^サー

バの

2/3

^が

BVO

による攻撃が可能であることも示されている。

ドキュメント内 SSL 安 全 性 調 査 報 告 書 改 訂 第 2 版 2004 年 2 月 6 日 ( 株 )KDDI 研 究 所 1 (ページ 63-66)