SECCON 2014 Online Quals Crypto 400 from Perspective of "Composer" (2014-12-14)

On this SECCON 2014 online quals, I designed and "composed" problem Crypto 400 "Ms.Fortune? Misfortune. : 4096-bit RSA". I will try to describe what was important to it.

Please note that this article contains complete spoiler about this problem. If you haven't tried yet, feel free to download the file and close the browser immediately after it.

Problem : "Ms.Fortune? Misfortune. : 4096-bit RSA"

This file is actually encrypted by 4096-bit RSA. But I'm sure that you can decrypt it.

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

Index

Background (1) : RSA, "Easy to Analyze"

RSA is probably the well-known public key encryption and digital signature system. We can prove properties by using only elementary number theory and (probably; intesrestingly, this is not proven yet but) based on integer factorization problem of big numbers. On the other hand, RSA is the most deeply-analyzed cryptosystem due to its simplicity. Actually, RSA without proper capsulization is not safe enough (sometimes) and methods like PKCS#1 prevents such attacks. If you do not know all about such attacks, you should know that RSA can be broken if we could factor the big integer.

This problem was originally designed and composed as a problem of difficulty 300 and I prepared a backdoor to make solvers have fun by analyzing RSA and and breaking it. Because of dicculty adjustments, it was relocated to difficulty 400 and there was a proposal to raise this problem to difficulty 500 (I insisted that this problem is not THAT difficult and removing clues will make the problem unsolvable).

Initial Analysis

The archive contains following files.

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

key.pub.gpg is just a PGP format public key. There's no trap and this is actually a key used to encrypt encrypted.gpg. key.gpg looks a private key but you will fail to import it. recover.py looks a Python script which makes key.gpg based on key.gpg.masked and given arguments.

Now we have to look inside PGP files. You can use software such as pgpdump to dump PGP files. Let's give it a try. By giving it key.gpg.masked with additional -i option which makes pgpdump to print raw numbers, you will get:

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

You can see all contents inside PGP file including actual public key number (in hexadecimal format). One thing to note is, that some of RSA parameters are masked. This matches where recover.py overwrites. If you find that the argument you have to give to recover.py is the RSA parameter primes p and q, you will know that the key of this problem is how to factor it.

I gave a clue for people who didn't find out in unpublished hint 1.

Private key used to encrypt the file is *very* weak and you can easily factor.
But you won't factor the private key using "practical" software. Don't use Mathematica! Don't use MSIEVE! Don't use CADO-NFS! They don't work, I guarantee.
Bring your textbool! Do the math!

I actually tested these software to make sure thay they can't solve the problem in a few hours. This is because you have to use very "primitive" algorithm to factor this public key (which is not implemented in "practical" facotization software). It did work as a obstacle which expects solvers to write custom scripts and this was very good for SECCON problem.

However, I didn't expect that the first team solved the problem so fast. Actually, I expected they will take much more time to identify the RSA factorization algorithm they should use and made another hint which you can call "a spoiler". In this point, I was making light of solvers' passion.

Factorization

Now, you can look that hint.

It can't be *really* hard!
Anyway, did you know that most of elementary algebra textbooks have a factorization formula which may help factorizing odd integers?

This is not a joke. Actually, this formula will help (and you won't find anything else on such elementary textbooks).

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

The fact is, difference of two square numbers can be represented as a product of certain numbers. You should you this formula directly. Specifically, you can increase the number $y$ gradually (and adjusting $x$ at the same time) and each time check whether the result is equal to the number is equal to the number you want to factor. This method is called, Fermat's factorization method.

This method has several variants and alternative representations. On another representation is, adding square number to $n$ which is the number you want to factor and checking whether the result is a square number.

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

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

The method used by MMA team (Japanese) was the first one and I initially used the latter one. The latter one requires ability to check whether the given number is square or not but GMP has fast function to do this.

Anyway, by using this algorithm, you can factor that big number. You can try computing actual prime pair.

Answer (the Flag)

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

Background (2) : A Formula "Still Important"

Now, you know the key. However, you may not know what this flag mean. Interestingly, this formula is still used on a modern factorization algorithm and used to factor big numbers.

Today, the fastest algorithm which is considered best to factor such RSA public keys is general number field sieve (GNFS). GNFS, which consists of many complex formula based on complex theories such as ring theory, is the algorithm which finds the different pair of numbers $x$ and $y$ which satisfies:

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

In other words, GNFS finds the number pair which the result of $x^{2} - y^{2} = (x + y) (x - y)$ is a non-zero multiple of $n$ . It uses complex theorem just to find the pair. Intesresting, is it?

Background (3) : "Weak Keys" - How likely to happen?

BTW, this problem is focused on "weak RSA keys" and there is a possibility to be generated. Interestingly, OpenSSL and libgcrypt (backend of GnuPG) both won't reject such prime pairs. Are they safe? --Yes, statistically. The probability of such weak keys are so small, so that using GNFS is much faster and reliable.

Actual probability can be roughly computed by assuming that the first prime is constant and computing the probability which selects near second prime. You can compute actual (but rough) probability by using prime number theorem.

libgcrypt and OpenSSL both selects the prime which upper 2 bits are 1 (to prevent overestimate of security parameter) and this makes the prime range you should consider is actually half of all primes. By considering it, you can roughly compute the probability (with 1024-bit RSA; 112-bit security parameter) ... about... $3.1 \times 10^{-120}$ .

This is very unlikely. Actually, the probability you find a close (as used in this problem) prime pair from random prime pairs is under $10^{-600}$ . What a great misfortune. Of course you won't find it by coincidence. So I wrote a GMP-based prime pair generator and transformed it to a GnuPG key by using custom Python script.

a4lg.com