作問者から見た SECCON 2014 オンライン予選 Crypto 400 (2014-12-14)

今回の SECCON 2014 オンライン予選においては、Crypto 400 の "Ms.Fortune? Misfortune. : 4096-bit RSA" の作問を担当させて頂きました。ここでは作問者から見た今回の問題の意義について解説してみようと思います。

なおこの記事には本問題の完全なネタバレが、特にネタバレ防止措置もなく含まれています。最初のセクションで問題ファイルをダウンロードした後はすぐにブラウザを閉じるのが良いでしょう。

問題 : "Ms.Fortune? Misfortune. : 4096-bit RSA"

次のファイルは実際に 4096-bit RSA で暗号化されている。それでも、君ならこれを復号できるはずだ。

seccon-2014-online-quals-crypto400-problem.tar.xz (5,004 バイト; MD5=20aafe655a39bd5173f314991508b904)

背景 (1) : "解析されやすい" RSA

RSA は、公開鍵暗号方式として、また電子署名方式として最も有名なアルゴリズムでしょう。初等整数論を用いるだけで理論の解説や証明ができ、素因数分解という有名な問題を (おそらく) 安全性の基礎とする方式です。しかし、それ故に RSA は最も深く解析されたアルゴリズムとも言えるでしょう。実のところ、適切な方式でカプセル化を行っていない RSA は状況によって安全でないことがあり、PKCS#1 などの方法はこれらの攻撃を防ぎます (蛇足ではありますが、電子投票スキームなどにはこのような弱さを意図的に良い性質に転化するものがあります)。また、そのようなことを知らなくとも、RSA が素因数分解を行えば解読できる問題であることはおそらくこの暗号を知るほぼ全ての方が知っていることでしょう。

この問題は、そんな RSA 暗号をある一面から解析し、何とか正面から解いてもらうための裏口を用意した、作問時点では難易度 300 (ヒントの出し方によっては 200) の問題でした (難易度振り分けの都合上 400 に再配置された上、一時期 500 に上げるという議論が進んだほどですが)。

初期解析

アーカイブの中には、次のファイルが含まれています。

encrypted.gpg
key.gpg.masked
key.pub.gpg
recover.py

key.pub.gpg はどうということもない公開鍵です。何のトラップも無く、encrypted.gpg を暗号化するのに用いた公開鍵が格納されています。key.gpg.masked は秘密鍵のようですが、インポートすることができません。recover.py は、key.gpg.masked と与えられた引数を元にして key.gpg というファイルを作成する Python スクリプトのようです。

さて、PGP ファイルを解析するのに役立つソフトウェアとしてここで挙げられるのが、pgpdump です。このツールを用いることで、PGP ファイルの中身をわかりやすい形で表示できるのです。試しに key.gpg.masked を与えてみましょう。ここでは、各種数値をそのまま表示する -i オプションを付加しています。

Old: Secret Key Packet(tag 5)(1816 bytes)
        Ver 4 - new
        Public key creation time - Fri Jan  2 09:00:00 JST 1970
        Pub alg - RSA Encrypt or Sign(pub 1)
        RSA n(4096 bits) - b1 88 52 a9 12 0e e3 1e 8a 0e 86 35 62 fc ...
        RSA e(17 bits) - 01 00 01 
        RSA d(4091 bits) - 05 69 26 06 ff 1e 7f d5 f6 a4 67 14 bd 0f ...
        RSA p(2048 bits) - d3 82 fb df bf 63 72 4d 4a c0 f1 37 91 2b ...
        RSA q(2048 bits) - d6 df b4 5a 34 10 69 bd 19 76 81 1a 9c a6 ...
        RSA u(2047 bits) - 73 55 16 38 cc 8a 28 7e 98 66 d4 d8 a7 9e ...
        Checksum - 84 cc 
Old: User ID Packet(tag 13)(31 bytes)
        User ID - SECCON ____Key <____key@seccon>
Old: Signature Packet(tag 2)(555 bytes)
        Ver 4 - new
        Sig type - Positive certification of a User ID and Public Key packet(0x13).
        Pub alg - RSA Encrypt or Sign(pub 1)
        Hash alg - SHA1(hash 2)
        Hashed Sub: signature creation time(sub 2)(4 bytes)
                Time - Fri Jan  2 09:00:00 JST 1970
        Hashed Sub: key flags(sub 27)(1 bytes)
                Flag - This key may be used to certify other keys
                Flag - This key may be used to sign data
        Hashed Sub: preferred symmetric algorithms(sub 11)(1 bytes)
                Sym alg - AES with 256-bit key(sym 9)
        Hashed Sub: preferred hash algorithms(sub 21)(1 bytes)
                Hash alg - SHA1(hash 2)
        Hashed Sub: features(sub 30)(1 bytes)
                Flag - Modification detection (packets 18 and 19)
        Hashed Sub: key server preferences(sub 23)(1 bytes)
                Flag - No-modify
        Sub: issuer key ID(sub 16)(8 bytes)
                Key ID - 0xF1D5D0238C2E1A7D
        Hash left 2 bytes - 2b 66 
        RSA m^d mod n(4095 bits) - 71 cc c6 4a 2b 2f 08 ea 3c 61 07 f5 1f 78 ...
                -> PKCS-1
Old: Secret Subkey Packet(tag 7)(1816 bytes)
        Ver 4 - new
        Public key creation time - Fri Jan  2 09:00:00 JST 1970
        Pub alg - RSA Encrypt or Sign(pub 1)
        RSA n(4096 bits) - fd 7f c4 9e 20 04 f3 b7 ee 67 c3 6f 7a 86 ...
        RSA e(17 bits) - 01 00 01 
        RSA d(4094 bits) - 3f ff ff ff ff ff ff ff ff ff ff ff ff ff ...
        RSA p(2048 bits) - ff ff ff ff ff ff ff ff ff ff ff ff ff ff ...
        RSA q(2048 bits) - ff ff ff ff ff ff ff ff ff ff ff ff ff ff ...
        RSA u(2048 bits) - ff ff ff ff ff ff ff ff ff ff ff ff ff ff ...
        Checksum - 6d e7 
Old: Signature Packet(tag 2)(543 bytes)
        Ver 4 - new
        Sig type - Subkey Binding Signature(0x18).
        Pub alg - RSA Encrypt or Sign(pub 1)
        Hash alg - SHA1(hash 2)
        Hashed Sub: signature creation time(sub 2)(4 bytes)
                Time - Fri Jan  2 09:00:00 JST 1970
        Hashed Sub: key flags(sub 27)(1 bytes)
                Flag - This key may be used to encrypt communications
                Flag - This key may be used to encrypt storage
        Sub: issuer key ID(sub 16)(8 bytes)
                Key ID - 0xF1D5D0238C2E1A7D
        Hash left 2 bytes - c6 78 
        RSA m^d mod n(4095 bits) - 5d be 35 e8 c3 36 2d 8d c4 6b b6 09 98 23 ...
                -> PKCS-1

このように、公開鍵の具体的な数値 (16 進) を含めて様々な情報を取得することができます。ここで注目すべきは Secret Subkey Packet の RSA パラメータの一部がマスクされていることです。ここでマスクされている部分は recover.py によって書き換えられる部分とちょうど一致します。recover.py の解析によってこれが受け取る引数が RSA パラメータの p と q (素数) であることが分かれば、これが素因数分解が鍵になる問題だと分かるはずです。

公開されなかったヒントには、このことが分からなかった人のために次のような指示を与えていました。

暗号化に使われた秘密鍵は非常に弱い。あまりにも弱く、簡単に因数分解ができるくらいだ。
ただし、実用的な因数分解ソフトウェアで分解することはできないだろう。Mathematicaも、MSIEVEも、CADO-NFSも使うな！コイツらは使えない、私が保証する。
教科書を持ってこよう。数学をやろう。

実際、これらのソフトウェアを使っても実用的な時間内には出ないであろうことをテストしています。というのも、この公開鍵の素因数分解を行うためにはこれらの "実用的な" ソフトウェアには実装されていないような "原始的な" アルゴリズムを用いる必要があるためです。この点は非常に作問に対して有利に働きました。おそらくカスタムスクリプトを書くことなく、解くことはできないだろうという障壁として働いたのです。

ただ作問時点では、ここから使用すべき RSA 因数分解アルゴリズムの特定にはもう少し時間がかかると予想していました。最悪、このヒントよりさらに先の、ネタバレとも言えるヒントすら作っていたのです。この点については、解答者の意欲を侮っていたとしか言いようがありません。

素因数分解

では、そのヒントを見てみましょう。

難しいことはないんだ！
ところで、中学校の教科書にも載っている因数分解の公式に、奇数の素因数分解に役立つ公式があるのを知っているかな？

"中学校の教科書にも載っている因数分解の公式"。冗談ではありません。具体的には、次の式が役に立ちます (というより、素因数分解ならこれ以外の候補はおそらく出ないでしょう)。

x^{2} - y^{2} = (x + y) (x - y)

平方数の差は、特定の数の積として現すことができる。この公式を直接使うのがポイントです。具体的には、 $y$ の値を順番に増やしながら (同時に $x$ を適当に調整しながら)、式の結果が素因数分解したい数になるか否かをチェックする。この方法を直接用いる因数分解アルゴリズムは、フェルマーの因数分解法と呼びます。

フェルマーの因数分解法は、表現によって幾つかの変形があります。ひとつは先ほどのもの、もうひとつは、素因数分解したい数 $n$ から平方数を足した結果が平方数になるかをチェックするものです。式変形の結果はこんなところ。

(x + y) (x - y) + y^{2} = x^{2}

n + y^{2} = x^{2}

MMA チームが使った方法は前者、作問者が当初使った方法が後者です。後者は平方数を足した結果が平方数になるか確かめなければならないのですが、GMP には整数が平方数か否かチェックする関数があるので、それを使えます。

さて、これを使うと、あっさりと素因数分解ができてしまいます。具体的な素数ペアの導出は自分でやってみることをオススメします。

解答 (フラグ)

SECCON{g^2-f^2=(g+f)(g-f)~is~still~important~to~factor~BIG~numbers,.025f0ddfdc463a24bf0350c15b175eee}

背景 (2) : 今でも重要な公式

さて、ここまで来られた方は鍵を知っているでしょう。ですが、フラグの文字列が指す意味が分からないかもしれません。 ―意外かもしれませんが、この公式は形を大幅に変えてなお大きな数の因数分解に重要な役目を果たしているのです。

現在、RSA に用いられるほどの大きな数の素因数分解をするのに適したと言われるアルゴリズムは、一般数体篩法 (General Number Field Sieve; GNFS) です。環論を含む代数学の集大成とも呼ぶべきこのアルゴリズムですが、このアルゴリズムが最終的に導き出すのは大まかにいえば次の式を満たす異なる (自明でない) 数 $x$ と $y$ の組です。

x^{2} \equiv y^{2} (mod n)

これは言い換えると、先ほどの中学校レベルの式 $x^{2} - y^{2} = (x + y) (x - y)$ で得られる結果が、因数分解したい数 $n$ の 0 でない倍数である組を見つける、ということになります。これを効率良く見つけるために最新の数学を駆使しているのが GNFS というわけです。面白くありませんか？

背景 (3) : 実際に作られうる "弱い鍵"

さて、この問題で出したような弱い公開鍵ですが、実際に作られる可能性はあります。そして、OpenSSL や libgcrypt (GnuPG で使用されているライブラリ) はそのような組を排除しません。これで本当に大丈夫なのでしょうか？……確率論的に言えば、平気です。というのも、そのような素数ペアが選択される確率があまりにも小さく、その確率を狙うくらいなら GNFS などの実用的な因数分解を行った方が早いからです。

具体的な確率は、素数ひとつを固定したとき、十分近くにある素数が選択される確率として概算することができます。素数定理によって素数の数を近似することで、大まかな確率は実際に求めることが可能です。

libgcrypt や OpenSSL は RSA のために上位 2 ビットが 1 の素数を探索する (これによって、1024-bit RSA と銘打っているものが実際には 1023-bit の RSA であることを避ける) ため、選ばれる素数の区間は特定のビット数を持つ区間の半分になります。これを考慮し、1024-bit RSA において 112-bit セキュリティパラメータを適用した場合、そのような鍵が得られる確率はおよそ…… $3.1 \times 10^{-120}$ 。

これはとても有り得そうにない値です。ちなみに、今回 CTF で用いた素数の組ほど近いペアが 4096-bit RSA において見つかる確率というのは、 $10^{-600}$ を大きく下回ります。とんでもない幸運どころか、とんでもない不運となってしまった訳です。もちろん偶然見つかるわけがなく、GMP を用いた素数ペアジェネレータを書き、それを Python スクリプトが GnuPG 鍵の形に変形しました。

a4lg.com