CODE BLUE CTF 2017 - Common Modulus series

There are 3 challenges in this series, all of which are based on the same problem with varying conditions. Therefore, we’ll go through them in increasing order of difficulty and build solutions incrementally.

N.B. All files related to the problems for these challenges and their solutions are available here

Common Modulus 1

We made RSA Encryption Scheme/Tester. Can you break it? Common_Modulus_1.zip

Common Modulus 2

The previous one is very easy. so is this also easy? Common_Modulus_2.zip

Common Modulus 3

try harder! Common_Modulus_3.zip

The common setting is that we’re given two RSA-encrypted messages (c1,c2) which are the encryptions of the flag m such that c1 is the encryption of m with the public key (n,e1) and c2 is the encryption of m with the public key (n,e2). In other words, we have two encryptions of the same message with public keys that share the same modulus. To be precise, what we have is

  1. c1=me1modn
  2. c2=me2modn
  3. e1,e2 are randomly generated primes in the first challenge, which are each multiplied by 3 and 17 for the second and third challenges respectively.
  4. n which is the common modulus to both public keys, a large randomly generated semiprime of length 2048, 4096 and 8192 bits respectively for the first, second and third challenges.

In terms of operations that we can do, we can multiply both ciphertexts to get a third ciphertext cm. That is because textbook RSA is homomorphic with regards to (integer) multiplication. This operation would yield

cmmodn=c1c2modn=me1me2modn=me1+e2modn

And if we were to raise c1 and c2 to the powers of x and y, respectively, then multiply them together

cm=c1xc2y=(me1)x(me2)ymodn=me1xme2ymodn=mxe1mye2modn=mxe1+ye2modn

At this point, we can take advantage of Bézout’s identity, which simply states

For a,bZ+ and their greatest common divisor d, there are x,yZ such that xa+yb=d

We can calculate x and y efficiently using the Extended Euclidean Algorithm. If one of the coefficients happens to be negative, then we compute the modular inverse of the respective ciphertext modn first, and raise it to the power of the absolute value of the coefficient. After calculating cm, we have three different cases. One for each challenge

Common Modulus 1

This is the simplest variation, because e1 and e2 are relatively prime, meaning that their greatest common divisor is 1, so it yields

cm=c1xc2y=me1xme2ymodn=me1x+e2ymodn=m1modnBy Bézout's identity=m

So we’ve successfully recovered the first message, and hence the the first flag: CBCTF{6ac2afd2fc108894db8ab21d1e30d3f3}.

Common Modulus 2

For this variation, we don’t recover the message itself but instead we get m3modn. However, we know that the flag is of the form

CBCTF{ ... 32 characters representing a hex-encoded MD5 hash ... }

Meaning that the bit length of the flag is

  1. 32 characters of the hash, at 8-bits per character, 256 bits +
  2. 5 characters of CBCTF, at 8-bits per character, 40 bits +
  3. 2 charactes for { and }, at 8-bits per character, 16 bits =

312 bits, and when multiplied by 3 (because this is the 3rd power), would be in the vicinity of 936 bits. This is a lot less than the bit length of n, which is 4096 bits for the second challenge. What this means is that we can simply take the cubic root of m3modn, yielding m and hence the flag: CBCTF{d65718235c137a94264f16d3a51fefa1}.

Common Modulus 3

In this variation, the hardest of the three, not only is the greatest common divisor of e1 and e2 17, but the flag is also right-padded with null bytes (bytes with the value 0) until it’s in the vicinity of ~8192 bits (a few bits less) before being encrypted. To start, we utilize the same method to get mp17modn, where mp is the padded flag. But we need to retrieve m, not mp17. How do we do that? Well, there are two things to keep in mind:

  1. The modulus is quite large at 8192, meaning that the - unpadded - message must be at least 482 bits (8192 / 17 bits) so that the 17th power becomes sort of a problem. Therefore, knowing the length of the message is 312 bits because it follows the same format as the other challenges in this CTF, we can actually calculate the 17th root of m17modn and successfully recover the flag IF there were no padding.
  2. The padding is deterministic and linear. It is the equivalent of multiplying the flag with a very large power of 2, since the bitstring representation would be XXXXX00000000000000 where XXXXX is the binary representation of the coveted flag.

Using these two facts stated above, we can unpad the message by first calculating the padding coefficient1 which is 2Bmodn where B= the number of bits needed to pad the message to be close to 8192 bits, which is 8192312= 7880 bits. Afterwards, we get the modular inverse for the previously calculated padding coefficient, yielding 2Bmodn. We then calculate 2B17modn by raising the previous value to the power of 17. Now, if we multiply that with mp17 what we get is

mp172B17modn=(m2B)172B17modn=(m172B17)2B17modn=m17(2B172B17modn=m17(2(B17)+(B17))modn=m171modn

So we’ve successfully calculated m17modn and, as previously mentioned, we can also calculate the 17th root to recover m itself.

But wait, we haven’t actually decided what B is! Well, in the worst case, we’re going to be a few bits off from the real value, so we can simply write a program that does all the steps described above, retrieves a candidate m and checks that it starts with the expected CBCTF. We can use a conservative starting value B=7868, and within only 4 attempts, we recover the flag: CBCTF{b5c96e00cb90d11ec6eccdc58ef0272d}.

  1. Probably not a real term. It simply seemed apt.