Maze was a fun cryptography challenge which wasn’t all that challenging once i figured out what I had to do. That took me a while though!

The challenge

Original data

We’re given, in a zip file:

• A cipher.txt file which contains a big number (the cipher, supposedly)
• 101 public keys

And that’s it, we have to decipher it. Oof, that’s not a whole lot of information.

Examining the data

I decided to look at the modulus and exponents in each file, moved all the decoded files to a clear/ folder with this command: for file in pub*; do openssl rsa -pubin -inform PEM -text -noout < $file > "./clear/$file"; done

Ok so now I have 101 files that look like:

RSA Public-Key: (2048 bit)
Modulus:
    00:dd:a2:f9:b5:2c:68:3f:35:bc:41:da:f5:26:b2:
    49:6e:da:c0:59:ed:04:90:71:49:a9:71:8c:33:72:
    71:50:64:20:7e:24:fa:b0:6c:33:d0:eb:c2:5a:d5:
    4f:fa:48:e7:cf:e1:5f:54:b5:97:1a:0f:f0:be:3d:
    0d:a8:b1:10:0a:d1:77:88:87:a1:9c:9e:29:49:bd:
    5f:82:4f:b2:1f:4d:68:85:c8:14:52:6f:27:23:f5:
    56:ce:29:b3:06:bf:59:bd:43:cc:a1:1d:ea:fe:20:
    d0:db:b8:46:ce:ed:18:44:09:74:cd:8b:f4:94:5d:
    f1:fb:5c:01:f7:91:ac:63:1a:19:b2:8d:d1:67:2a:
    cd:ea:08:ce:7d:e9:65:e9:95:bb:06:3c:61:38:15:
    98:f9:3f:81:6e:dc:b6:26:8e:e5:a2:92:43:a0:3b:
    e7:39:74:60:b2:3a:74:44:eb:00:fc:42:00:bc:95:
    d1:17:d9:30:a3:13:1c:fa:8d:95:22:60:a1:bc:bb:
    46:af:4c:52:a6:7c:5c:df:d3:4b:09:66:c8:d6:9f:
    82:0f:4f:25:bd:e5:04:46:b4:c8:c0:70:8c:2a:39:
    3a:04:67:d4:e3:51:b6:66:2d:46:25:99:54:a2:5e:
    21:2a:44:65:be:a7:ed:a9:f9:51:1c:b1:f4:69:c4:
    e7:29
Exponent: 65537 (0x10001)

I wasted way too much time establishing these few basic facts:

• Every file has a different modulus
• Every file has the same exponent

The RSA Cryptosystem

If you’re familiar with RSA you can skip this entire section, I’ll simply remind everyone how RSA works so every reader can follow along.

RSA is made up of a public key (2 numbers, really) and a private key (1 number). You share the public key with everyone, and they can use it to encrypt messages meant for you and only you. From there, only the holder of the private key (you) can decrypt the message.

Maths

RSA’s security is based on a single fact: it’s very very hard, given a multiplication result, to find which numbers were used to make it, especially if both numbers were prime (so there’s a single multiplication possible). Here’s how you generate a public and private key pair:

• Generate two large prime numbers p and q
• Multiply them, giving n: p * q = n. n is called the modulus for reasons that wil become obvious later.
• Calculate λ(n), which is lcm(p-1, q-1) where lcm is the least common multiple.
• Choose an integer e so that 1 < e < λ(n) and so that e and λ(n) are coprime. e is usually simply 65537.
• Find the modular multiplicative inverse of e by λ(n), so find d so that: e * d % λ(n) = 1

And that’s it, d is now the private key, n and e make up the public key. Now you can take any plaintext message M and generate a ciphertext with: C = (M^e) % d

Why? Simply because you can then decrypt the message with C^d % n, which gives you the plaintext again. If you’d like to know how that works precisely, here’s a good article on it.

Anyway the important part is that the public key is (e, n) where n = pq, and finding p and q from n is basically impossible. And that’s good because once you have p, q and e, you can deduce d and you now have the private key

Solving

Options, options, options

So I had to figure out what was up with all these files. I had a few possibilities to explore:

• All of these were all public keys derivated from the same private key and I had to somehow find the private key from all these files
• The ciphertext had been encrypted using all of these public keys
• A single one of those keys was used to encrypt the plaintext and I somehow have to find which one

Option #1 was basically impossible, and wouldn’t have helped me anyway. I was pretty set on option #2 but before doing my script I decided to ask an admin since the math involved might lose me a lot of time. He told me I was on the wrong track. So… It has to be #3.

Common factor attack

I hadn’t known of Common Factor Attack before this chall, I don’t know how I didn’t! It’s really powerful, though not very applicable to real-world keys. The idea is that if you have a bunch of keys that were generated by the same source, that was using really bad values for its prime generation for p and q, then there’s a chance both keys have one of those prime numbers in common. And that’s really good news because we can calculate gcd (greatest common divisor) between large integers very fast, which will let us find p values! So, first of all, write a sagemath script that reads all of the modulus and puts them in a file:

vals = []

cipher = 12225682126551187619399843891561465899608952498495120851070778192443023261485900560363269700242510941697365921981918056191408738905974825435324679841994232057252389709580959723999122054844144379187848417389566267322902673441312265008128249280701778727420570269893119286011513549800540500264752909082405313097299590601819529975638766522951170517766409850156769569563924473524368177233982270360715976884639307240445794551655637991803019693125040126171348043927410721121473304998359286936518573367417946711868112216965614586268606230443139176878435753744068734717043992817907788262531021387616180516736397859628481024223
e = 65537

for n in range(101):
    f = open("pub{}.pem".format(n), 'r')
    lines=[x.rstrip().lstrip() for x in f.readlines()[2:-1]]
    hexa = ''
    for part in lines:
        hexa += part.replace(":", "")
    val = Integer(int(hexa, 16))
    if cipher < val:
        vals.append(val)

# vals now contains all modulus

Ok cool, now to check if 2 modulus have common factors:

# Find keys that share common factors
for x in range(len(vals)):
    for y in range(x+1, len(vals)):
        if x == y:
            continue
        valX = vals[x]
        valY = vals[y]
        g = gcd(valX, valY)
        if g == 1:
            continue
        print("{} and {} share a common factor: {}".format(x, y, g))

And the output:

38 and 44 share a common factor: 168736462866079204789584058199620418225526506348478399447895958829038354002285480486576728303147995561507709511105490546002439968559726489519296139857978907240880718150991015966920369123795034196767754935707681686046233424449917085120027639055362329862072939086970892956139024391556483288415208981014264336691

Boom! Now we have a p value, we can compute q for both moduli and that’s it, we’ve broken both private keys. All we need now is to decipher the ciphertext with both private keys and see which of the two make sense:

p = Integer(168736462866079204789584058199620418225526506348478399447895958829038354002285480486576728303147995561507709511105490546002439968559726489519296139857978907240880718150991015966920369123795034196767754935707681686046233424449917085120027639055362329862072939086970892956139024391556483288415208981014264336691)

for i in [38, 44]:
    n = vals[i]
    # Find q
    q = n // p
    # Comute Lambda(n):
    l = lcm(p-1, q-1)
    # Compute d
    d = inverse_mod(e, l)
    # Calculate (cipher^d) % n
    R = IntegerModRing(n)
    plaintext = R(cipher)
    plaintext = plaintext ^ d
    print(hex(Integer(plaintext)))

One of the two outputted values looks a LOT like ASCII, so I convert it and: securinets{rs4_1s_g00d_s0m3t1m3s!}

That’s it!