Challenge: weak RSA – Secgroup Ca' Foscari

Criminals have been storing all information about illegal activities on a password-protected server. They exchange the password encrypted. Here is an intercepted ciphertext:

44d9b36bc73ab46e2c9d446d7776f42ca005ff4052e7218ffae6df3b49c4842a3ad3c6f7159753dce09b227454aea156e03973
c9a4195296bb2506f2578b2c2796f080c8a6f17c99b18646a967146c732d2bf251cab400f4adc2537138cf23a7847cd6c8f0fa
dc4157ab20bd69cf67971e265931b20e35f597186597da5199b8

We have managed to find out the public key used for encryption:

Rumors say the encrypted message is only 43 bytes long. Finding the encrypted password is of ultimately importance. Can you help us?

5 thoughts on “Challenge: weak RSA”

Hi everybody!

I’ve been able to find the password! 😀

First of all I used OpenSSL to get the public exponent and the modulus starting from the key in PEM format. I immediately noticed that the modulus is 1024 bits long but the public exponent is 3. Given that the message is only 43 bytes long I guessed that this challenge could be won with a small exponent attack!
The ciphertext is 1023 bits long and initially I got fooled by the math: if the plaintext was made of 341 bits (43 characters, the first char with the three most significant bits set to 0), once raised to the 3rd i’d have got a result of 1023 bits… That would have meant that the mod didn’t change the result of exponentiation… But trying to compute the cubic root I immediately noticed that it wasn’t a perfect cube!
So the mod actually took place!
The maximum amount of bits of plaintext raised to the 3rd is 43 * 8 * 3 = 1032. So it means 8 bits (1 byte) more than the length of the modulus…
The easiest way to compute a % b is to subtract b from a as long as a > b. When a < b then a is the result! So i tried to reverse this process by adding the modulus to the ciphertext and I took into account all the results a number of bits in the range [1024:1032]. I found 298 possible results.
On the internet I found a rather efficient algorithm to compute the cubic root and I adapted it to be used. This algorithm found that only 1 number out 298 is a perfect cube and once computed I tried to print it as a normal string made of ASCII chars…

The result is this: password = 55a2b5543421fe8cccb01aa020f4a1bc

All the computation has been done with a Python (I followed Prof. Riccardo's suggestion 😉 ) program written by me.
The following is the code (which is perfectly working). Modulus and message are hardcoded!

# It computes n such that n % mod = number. The range covers the length in bit from len(number) to precision
def reverseModulus(number,mod,precision):
    startLength = len(bin(mod)[2:])
    toRet = []

    current = len(bin(number)[2:])
    while current <= precision:
        number = number + mod # to compute mod we subtract, so here we add!
        current = len(bin(number)[2:])
        if current >= startLength and current <= precision: # if the length in bit is the one we want
            toRet.append(number) # we save it

    return toRet

# It computes the cubic root
def cuberoot(x):
    y, y1 = None, 2

    while y != y1:
        y = y1
        y3 = y ** 3
        d = (2 * y3 + x)
        y1 = (y * (y3 + 2 * x) + d // 2) // d

    if y * y * y != x: # if it's not a perfect cube
        return -1 # we're not dealing with negative numbers so -1 can be use as a flag
    else: # if it is a perfect cube we return it (without 0x and L)
        toRet = hex(y)[2:]
        return toRet[0:len(toRet) - 1]

# We try to print the decrypted string!
def toASCII(hexString):
    charList = []
    ind = 0

    while hexString != "":
        ind += 1

        currentChar = hexString[len(hexString) - 2:]
        hexString = hexString[0:len(hexString) - 2]
        charList.append(chr(int(currentChar,16)))

    toRet = ""
    for item in charList[::-1]:
        toRet = toRet + item

    return toRet


message = 0x44d9b36bc73ab46e2c9d446d7776f42ca005ff4052e7218ffae6df3b49c4842a3ad3c6f7159753dce09b227454aea156e03973c9a4195296bb2506f2578b2c2796f080c8a6f17c99b18646a967146c732d2bf251cab400f4adc2537138cf23a7847cd6c8f0fadc4157ab20bd69cf67971e265931b20e35f597186597da5199b8
modulus = 0x00db030db2516421d01b48a005e6191118b5cbcd66634670fc21c067b7bbf3c257ae5695966a1627ab1055f1ce6dbdfe4fa654e1bf81f797fbf69aabeb710227298233dd72d51d429f32759ec44902c2ab39daf6ab75a5a28ac34d87921d54e96adc31a3689479446fc1a171ba4dfa7df1683c79481e5d471738d655c04259c2fb

candidates = reverseModulus(message,modulus,1032)

for i in range(len(candidates)):
    check = cuberoot(candidates[i])
    if check != -1:
        print toASCII(check)

I wish everybody a nice evening (and weekend).

Oh no, what happened??
I used the tags to write the source code (as usual) but everything is messed up!! The indentations are gone! 🙁
Sorry but I don’t know why it’s happened 🙁

Alessio, I’ve fixed the source code. Very good!

One minor note: in python you have functions to convert from hex to ascii and viceversa. Here you can replace toASCII(check) with check.decode(‘hex’) (encode does the other conversion)

I like the idea of reusing code for the cube root. There’s also a very powerful library for math: gmpy (a python interface to GMP). You have to install it. There you have gmpy.root that already tells you if the number is a perfect cube. For example

root = gmpy.root(cipher,3)
    if root[1] != 0: # this is a perfect cube
        print root[0] # this is the cube root

Thank you for the advice! 🙂
I suspected there was a standard function to convert from hex to ASCII, but it was rather late so I didn’t google for it and I wrote the algorithm. :p

Obviously using the decode method is way better!

I installed the gmpy (2) library but I think that it doesn’t work very well on my computer since it is a MacOS X and I read that gmpy has some troubles with the Mac environment… In fact I tried to use your code but the root method does not return an array but a floating point value… I’ll try to understand what’s wrong! 🙂

Thank you so much for all the hints! 🙂

Ah yes gmpy is not obvious to install on MAC. If you succeed let me know 🙂

Comments are closed.