RSA署名の不味い実装の話らしい.

crypt

[鏡] しっぽのさきっちょ 2006/08/29 暗号関連よりBleichenbacher's RSA signature forgery ASN.1based on implementation errorを読む.
そのまま荒川氏が解説するんかなぁと思っていたら

ふたつ目の記事は IETF OpenPGP WG のML からの話題。 RSA 署名においてアルゴリズムの実装の仕方によっては簡単に偽装ができてしまうというものらしいが，英語不得手なのでよく分からない。

とあって（；´Д｀）となったので適当に解説.

SCIS2007で改良されたアタックが出ました. Bleichenbacherの攻撃法ではe=3かつセキュリティパラメータが3の倍数 (k=3072) の場合を考えています. e=17, 65537の場合や, セキュリティパラメータが3の倍数でない場合 (k=1024, 2048, 4096等) については攻撃が可能かどうか分かっていませんでした. つい最近, Bleichenbacherの攻撃法を解析し改良した, Izu, Shimoyama, and Takenaka ``Analysis on Bleichenbacher's Forgery Attack'' (SCIS 2007, 3C4-6) が発表されました. 詳しくは, 該当論文をどうぞ.

前置き

CRYPTO2006のランプセッションでDaniel Bleichenbacherが発表したそうな.
RSA PKCS#1の実装で, 文書に署名をするときは, 文書をハッシュにかけてそのハッシュ値を仕様に則ってパディングした後, 秘密鍵dでd乗する. 検証の際には, 公開鍵 (N,e) でe乗した後, 値をパースしてハッシュ値を取り出し, 元の文書のハッシュ値と比べて検証をおこなう.
Bleichenbacherが言っているのは, 署名が比較的簡単に偽造できてしまうような不味い実装があるということ.

CRYPTO 2006 Rump Schedule
Daniel Bleichenbacher "Forging some RSA signatures with pencil and paper"

方針

貰った署名を公開鍵のe乗してデータを見ると, 

00 01 FF FF FF ... FF 00  ASN.1  HASH

となっている.
末尾にゴミがついている場合を考えよう.

00 01 FF FF ... FF 00  ASN.1  HASH  GARBAGE

こういうデータを貰ったときに, 本来はASN.1中にHASHの長さが格納されているので, それによってHASHの部分をパースする.

00 01 FF FF ... FF 00 || ASN.1 || HASH || GARBAGE

と分けて, ゴミが付いているので正しくパディングしていないと判断して停止するのが正しい実装.
しかし, ダメな実装では検証を続行してしまう.

具体的な偽造法

計算式に間違いがありました. 人伝でツッコミを受けたので訂正します. 某Iさんのご指摘に感謝.

まず適当な文書mを選び, SHA-1に掛けてHASHを得る.
Dを"00 ASN.1 HASH"という文字列を整数に直したものとする. 具体的には, D=T \times 2^{160}+H.
RSA PKCS#1+SHA-1の場合は, Dの長さは36bytes=288bitsになる. 次に, a=2^{288}-(T\times 2^{160}+H)とする. さらにaが3の倍数だとする*1.

Bleichenbacherは3072bitの鍵を用いている場合を例にとって署名の偽造をおこなっている. GARBAGEを大量につけて, hashが右から2072bit目にくるようにする. GARBAGEの部分を整数とみてgとおく. 攻撃者は適当なgについて, 2^{3057}-2^{2360}+D \times 2^{2072}+gをd乗した値を得られれば文書mについての署名が偽造できたことになる.

署名として, 2^{1029}-a \times 2^{34}/3を作る.
すると,
(2^{1019}-a \times 2^{34}/3)^3
=(2^{1019})^3-3(a \times 2^{34}/3)^2+3(a \times 2^{24}/3)^2+(a \times 2^{34}/3)^3
=2^{3057}-a\times 2^{2072}+\frac{1}{3}a^{2} \times 2^{1087}+\frac{1}{27}a^{3} \times 2^{102}.
a=2^{288}-Dなので, は署名を3乗すると, =2^{3057}-2^{2360}+D \times 2^{2072}+gとなっている.
よって偽造に成功する. (ここで, g=\frac{1}{3}a^2 \times 2^{1087}-\frac{1}{27}a^3\times 2^{102}とおいた.)

纏め

Implementors should review their RSA signature verification carefully to make sure that they are not being sloppy here. Remember the maxim that in cryptography, verification checks should err on the side of thoroughness. This is no place for laxity or permissiveness.
Daniel also recommends that people stop using RSA keys with exponents of 3. Even if your own implementation is not vulnerable to this attack, there's no telling what the other guy's code may do. And he is the one relying on your signature.

関連リンク

*1:メッセージをちょこちょこ弄って, 何回か試せばaが3の倍数になるので, これで良い.