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.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.
What's the name of this cryptosystem?
After solving the riddle, the server sends a secret (same value for every connection):
The secret is: 45710623737087701711820134797542238364727935815041561117965550719730211404995880962189849763186419941404256428269541230638298594081804054803929405338706331501510355769791788035782101048794197150178174026969607210826909631760346060869225182396182048777369368142016863385200586265163953840808342248328628488558966204179925698305553258440383522033840372138701862745580428470631799476191017336213672662419943702985732053645939959855799510630518494500337262650866518227631714070805564029135334485129969768206948775297659476280347999959347004640627153560223776086816027050734375066512946795924861244218488564290260122095Afterwards, it asks in a loop:
Tell us your choise: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).
------------------------
[E]ncrypt: [D]ecrypt:
Let's try to decrypt the secret:
[E]ncrypt: [D]ecrypt: DThat 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:
Tell us your secret to decrypt: 45710623737087701711820134797542238364727935815041561117965550719730211404995880962189849763186419941404256428269541230638298594081804054803929405338706331501510355769791788035782101048794197150178174026969607210826909631760346060869225182396182048777369368142016863385200586265163953840808342248328628488558966204179925698305553258440383522033840372138701862745580428470631799476191017336213672662419943702985732053645939959855799510630518494500337262650866518227631714070805564029135334485129969768206948775297659476280347999959347004640627153560223776086816027050734375066512946795924861244218488564290260122095
Don't fool me! X-(
$$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')
