TheRomanXpl0it

Codeblue CTF 2017 - Common Modulus 3

by chq-matteo
November 10, 2017

If you haven’t already, check out Common Modulus 1 Writeup and Common Modulus 2 Writeup!

We have solved Common Modulus 1 and Common Modulus 2, but now there’s even more!

Bigger public exponent? Check

e = 17 * get_random_prime(20)

Padding? Check

while len(flag) * 4 < 8192:
  flag += '00'

FLAG = long(flag[:-2], 16)

Proper padding? Luckily not!

We have to:

  1. Remove the padding
  2. take the seventeen-th root of the message (at least hope we can)

The bigger public modulus let’s us hope for the best ($8192 / 17 = 481$ bits or circa 60 bytes).

Since flag is parsed as a base 16 integer the 00 padding is just a multiplication by $2^4$. We don’t know how many 00 of padding there are, but we know that it is more than 0 and less that 8192/4 so we can happily brute force that!

Remember that multiplication for $2^{-4} \mod N$ is actually just like dividing by $2^{4} \mod N$ or cancelling a 00

for i in range(0, 2048):
    try:
        m17unpadded = (m17padded * pow(2, -17*4*i, n)) % n
    ...

Then we try to take the 17-th root

m, _ = ZZ(m17unpadded).nth_root(d, truncate_mode=1)

And check for a known plaintext like CBCTF

flag = unhexlify(hex(long(m))[2:].replace('L', ''))
    if 'CBCTF{' in flag:
        print flag
        break

I did mess up a couple of times during the competition, but in the end we got the flag.

N.B. I renamed a couple of variables and didn’t test the code again

Solution SageMath script

from binascii import unhexlify
import string
def solve(e1, e2, n, c1, c2):
    d, x, y = xgcd(e1, e2)
    print d
    m17padded = (pow(c1, x, n) * pow(c2, y, n)) % n # (flag * 2**x)**17 = flag ** 17 * 2**17x
    for i in range(0, 2048):
        try:
            m17unpadded, _ = ZZ(m17padded * pow(2, -d*4*i, n)).nth_root(d, truncate_mode=1)
            flag = unhexlify(hex(long(m17unpadded))[2:].replace('L', ''))
            if 'CBCTF{' in flag:
                print flag
                break
        except TypeError as e:
            # debugging debugging debugging
            print e
            print long(m17unpadded)
            pass

Related Posts