ASIS CTF Finals 2014 - Ultra Secure (Crypto 400)

 

The server welcomed us with the following message:

Here we use a well-known cryptosystem, which introduced in late 90s as a part of PhD Thesis. This cryptosystem is a probabilistic asymmetric algorithm, so computer nerds are familiar with the basics. The power of this cryptosystem is based on the fact that no efficient general method for computing discrete logarithms on conventional computers is known. In real world it could be used in a situation where there is a need for anonymity and a mechanism to validate, like election.

What's the name of this cryptosystem?

The answer is "Paillier" (https://en.wikipedia.org/wiki/Paillier_cryptosystem). It's a public-key cryptosystem, which has an interesting property - it's homomorphic. I'll explain this term in a moment, after we see what we need to solve the challenge.

After solving the riddle, the server sends a secret (same value for every connection):

The secret is: 45710623737087701711820134797542238364727935815041561117965550719730211404995880962189849763186419941404256428269541230638298594081804054803929405338706331501510355769791788035782101048794197150178174026969607210826909631760346060869225182396182048777369368142016863385200586265163953840808342248328628488558966204179925698305553258440383522033840372138701862745580428470631799476191017336213672662419943702985732053645939959855799510630518494500337262650866518227631714070805564029135334485129969768206948775297659476280347999959347004640627153560223776086816027050734375066512946795924861244218488564290260122095

Afterwards, it asks in a loop:

Tell us your choise:
------------------------
[E]ncrypt: [D]ecrypt:

We are able to encrypt and decrypt arbitrary messages (numbers). It is clear that the encryption scheme uses the Paillier cryptosystem, but we don't know the keys (neither private nor public key).
Let's try to decrypt the secret:

[E]ncrypt: [D]ecrypt: D
Tell us your secret to decrypt: 45710623737087701711820134797542238364727935815041561117965550719730211404995880962189849763186419941404256428269541230638298594081804054803929405338706331501510355769791788035782101048794197150178174026969607210826909631760346060869225182396182048777369368142016863385200586265163953840808342248328628488558966204179925698305553258440383522033840372138701862745580428470631799476191017336213672662419943702985732053645939959855799510630518494500337262650866518227631714070805564029135334485129969768206948775297659476280347999959347004640627153560223776086816027050734375066512946795924861244218488564290260122095
Don't fool me! X-(

That would be too easy ;) But now we can be sure, that the objective is to decrypt that number with server's private key. It's a time for more information about the cipher. Paillier cryptosystem is homomorphic, which means that we can make some computations on ciphertext (without knowing plaintext nor private key) which will result in predictable changes in plaintext after decryption. One of Paillier properties allows us to add any value to a plaintext:

$$D(E(m_1)*E(m_2)\ mod\ n^2) \equiv m_1+m_2 \pmod{n}$$

where D is the decryption function, E is the encryption function (which is randomized, I hid the random argument for simplicity), n is a number contained in both the private and public key, and m1 and m2 are plaintext messages.

Random interesting note: Unpadded RSA has a homomorphic property too: multiplication of ciphertexts results in multiplication of plaintexts after decryption.

What we want to do is to fool the server into decrypting something which is not the original secret, but we are able to recover it after decryption. The simplest idea is to just add 1 to the secret and ask server to decrypt it:

$$secret = E(secret\_plaintext)\\ D(secret * E(1)\ mod\ n^2) \equiv secret\_plaintext + 1 \pmod{n}$$

To do that, we need to know the modulo n. We will use the property that E() can encrypt only values that are smaller than n. Let's check what we get after querying some really big value to E():

[E]ncrypt: [D]ecrypt: E
Tell us your message to encrypt: 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
Your message is too long! :(

Bingo ;) We can find the modulo using binary search. Now we have everything we need to write a solver. Here's mine:

import socket

host = 'asis-ctf.ir'
port = 12445

# cut_between('smth: 123; adsf; ', 'smth: ', '; ') == '123'
def cut_between(source, before, after):
    pos1 = source.find(before)
    pos2 = source.find(after, pos1 + len(before) + 1)
    assert pos1 != -1
    assert pos2 != -1
    return source[pos1 + len(before) : pos2]

# decrypts or encrypts given input, mode: 'E' or 'D'
def ask(input, mode):
    global conn
    while True:
        try:
            conn.sendall(mode + '\r\n')
            data = conn.recv(1024) # 'Tell us your message to encrypt: '
            conn.sendall('%d\r\n' % input)
            data = ''
            while '[D]ecrypt:' not in data:
                data += conn.recv(1024)
            if 'too long' in data:
                return -1
            if 'None' in data:
                return None
            return int(cut_between(data, 'Your secret is: ', '\n'))
        except IOError:
            print 'Connection failed!'

def E(input):
    return ask(input, 'E')

def D(input):
    return ask(input, 'D')

def find_N():
    # length of N should be similar to the length of the secret
    start = 10**307
    end = 10**311

    assert ask(p, 'E') != -1
    assert ask(k, 'E') == -1

    # binary search
    while start < end:
        mid = (start + end) / 2
        res = ask(mid, 'E')
        if res == None:
            # server sends 'None' for 0 and n-1
            return mid + 1
        if res == -1:
            end = mid
        else:
            start = mid + 1

        print '[%d, %d]' % (start,end)
    return start

if __name__ == '__main__':
    conn = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    conn.connect((host, port))
    print conn.recv(1024) # riddle
    print conn.recv(1024) # question
    answer = 'Paillier'
    print answer
    conn.sendall(answer + '\r\n')
    data = conn.recv(1024)
    secret = int(cut_between(data, 'is: ', '\n'))
    data = conn.recv(1024)

    n = find_N()

    secret_plaintext = D((E(1) * secret) % (n**2)) - 1
    # flag: ASIS_85c9febd4c15950ab1f19a6bd7a94f85
    print hex(secret_plaintext)[2:].rstrip('L').decode('hex')