This challenge is centered around the Diffie–Hellman (DH) key exchange protocol and we're given 4 files:
- server.py: The main server script that performs the DH key exchange
- test_primes.py: A script that tests all their safe primes along with their passwords "to make sure that they're working" (sounds super fishy, right?)
- primes.txt: A list of 40 pre-generated safe primes that are used in the key exchange
- test_primes.log: A log generated from their running of the "test_primes.py" script
After examining the source file server.py, we concluded that the vulnerability probably exists in the test files since the protocol is well-implemented. Here's server.py:
#!/usr/bin/env python import hashlib import socket import SocketServer import sys from random import SystemRandom FLAG = '' PASSWORDS = [] PRIMES = [] class StickyHandler(SocketServer.StreamRequestHandler): def do_pow(self): """Do a simple little proof-of-work handshake.""" rnd = SystemRandom() # Generate a challenge string challenge = '%020x' % rnd.randrange(16**20) self.wfile.write(challenge + "\n") # The client must append some garbage that leads to a hash where the first # 3 bytes are 0. Note that we strip whitespace from it. suffix = self.rfile.readline().strip() # Check the token if hashlib.sha512(challenge + suffix).hexdigest()[0:6] != '000000': self.wfile.write("Sorry, we wanted something beginning 0x000000.\n") sys.exit(0) def do_pake(self, password): """Perform a simple PAKE handshake * The server picks a safe prime `p` and sends it to the client. * Both sides know the password, which is hashed with the result being `w`. * The server generates a random value `b` between 2 and `p`. * The server calculates `B = w ** b mod p` and sends `B` to the client. * The client generates a random value `a` between 2 and `p`. * The client calculates `A = w ** a mod p` and sends `A` to the server. * The server calculates `K = A ** b mod p` * The client calculates `K = B ** a mod p` * The client and server now have the same value for `K` (if their passwords matched). Hash `k` and use it as a key. """ rnd = SystemRandom() # The server picks a safe prime `p` and sends it to the client. p = PRIMES[rnd.randrange(len(PRIMES))] self.wfile.write("%d\n" % p) # Both sides know the password, which is hashed with the result being `w`. w = int(hashlib.sha512(password).hexdigest(), 16) # The server generates a random value `b` between 2 and `p`. b = 2 + rnd.randrange(p - 2) # The server calculates `B = w ** b mod p` and sends `B` to the client. B = pow(w, b, p) self.wfile.write("%d\n" % B) # The client generates a random value `a` between 2 and `p`. # The client calculates `A = w ** a mod p` and sends `A` to the server. A = int(self.rfile.readline().strip(), 10) # Avoid fishy-looking bases. if (A < 100) or (A >= p-1): self.wfile.write("That seems unlikely.\n") sys.exit(0) # The server calculates `K = A ** b mod p` K = pow(A, b, p) # Hash `k` and use it as a key. key = int(hashlib.sha512(str(K)).hexdigest(), 16) return key def handle(self): self.do_pow() key0 = self.do_pake(PASSWORDS[0]) key1 = self.do_pake(PASSWORDS[1]) key2 = self.do_pake(PASSWORDS[2]) # XOR all the keys together to get a final key, then XOR that against the # flag to securely send it to the client. final_key = key0 ^ key1 ^ key2 encrypted_flag = final_key ^ int(FLAG.encode('hex'), 16) self.wfile.write("%d\n" % encrypted_flag) # From http://stackoverflow.com/a/18858817 class ReusableTCPServer(SocketServer.ForkingMixIn, SocketServer.TCPServer): def server_bind(self): self.socket.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, 1) self.socket.bind(self.server_address) if __name__ == "__main__": HOST, PORT = "0.0.0.0", 2308 plain_flag = open('flag.txt', 'r').read().strip() FLAG = '{0:{fill}{align}64}'.format(plain_flag, fill=' ', align='>') PASSWORDS = [line.strip() for line in open('passwords.txt')] PRIMES = [long(line.strip()) for line in open('primes.txt')] # For convenience, the passwords are three random 16-bit integers represented # as base-10 strings. server = ReusableTCPServer((HOST, PORT), StickyHandler) server.serve_forever()
Quite conveniently, the test_primes.log contains the test values and results from a test run.
test_primes.py:
test_primes.log (truncated):
We made a reasonable assumption that the passwords used in the test run are the same as those used in the running server (since they mentioned that they want to make sure all the values work). Therefore, our intuition was to find the three 16-bit integers using the values given to us in the log file (test_primes.log). However, we made very little progress until a hint was revealed to us on the second day:
Based on the hint and with the help of a Professor, we deduced that:test_primes.py:
import hashlib import socket import SocketServer from random import SystemRandom # We want to verify that all the primes work with our PAKE and passwords, so we # have this to test them all. def do_pake(p, password): """Perform a simple PAKE handshake * The server picks a safe prime `p` and sends it to the client. * Both sides know the password, which is hashed with the result being `w`. * The server generates a random value `b` between 2 and `p`. * The server calculates `B = w ** b mod p` and sends `B` to the client. * The client generates a random value `a` between 2 and `p`. * The client calculates `A = w ** a mod p` and sends `A` to the server. * The server calculates `K = A ** b mod p` * The client calculates `K = B ** a mod p` * The client and server now have the same value for `K` (if their passwords matched). Hash `k` and use it as a key. """ rnd = SystemRandom() # The server picks a safe prime `p` and sends it to the client. # (done as an argument to this function) print "For prime %d" % p # Both sides know the password, which is hashed with the result being `w`. w = int(hashlib.sha512(password).hexdigest(), 16) # The server generates a random value `b` between 2 and `p`. b = 2 + rnd.randrange(p - 2) # The server calculates `B = w ** b mod p` and sends `B` to the client. B = pow(w, b, p) print "Server sends %d" % B # The client generates a random value `a` between 2 and `p`. a = 2 + rnd.randrange(p - 2) # The client calculates `A = w ** a mod p` and sends `A` to the server. A = pow(w, a, p) print "Client sends %d" % A # The server calculates `K = A ** b mod p` Ks = pow(A, b, p) # The client calculates `K = B ** a mod p` Kc = pow(B, a, p) # The client and server now have the same value for `K` (if their passwords # matched) if Ks == Kc: print "They match!\n" else: raise Error("Mismatch between Ks and Kc!") # For convenience, the passwords are random 16-bit integers represented as # base-10 strings. This provides 48 bits of security, more than enough! passwords = [line.strip() for line in open('passwords.txt')] # Generating safe primes is time-consuming, so we have a list of 40 # pre-generated. primes = [long(line.strip()) for line in open('primes.txt')] for password_index in range(0, len(passwords)): print "Trying password %d" % password_index for prime in primes: do_pake(prime, passwords[password_index])
test_primes.log (truncated):
Trying password 0 For prime 157510364927853457162948732697927091562089435007374436775741066597889208780038327065751652385164068377927735017928273970581213228590029199633932453805597499108295126465320981255278186718859143136713935437140133249554423579793968151174589883879109611017911993276863582632445099846219449018440096166644536434139 Server sends 83114750359844161445901258531191166124253161513089346382672107157806888542563790180372406255805435772646835444182589535687474720716490149954997898461841687882318369298525051194018597966279839017157840630953780873901534519786733342457314994803807546732597267502772191571869227908717319533860319312103986965377 Client sends 47447145594455101912159946920387584340785369370550873256501525633999549598179376506541175787694479290659494968263551150093219569105435293935822079504045554319964653929703972019451322463203208890783819563592996068094764773046343041710601066007728558228072518931931717544390618410027007552706058349326525018082 They match! For prime 144721147008100395236247483473840090314433028889529017450717068439343933546648210774792311062580529502811258846843386525357313651075871045260355622068383777124938802688176775434943526718695229217992454930086988827985455712681897919356652647425432951289895336188337044266911059723076432026809046853359006912707 Server sends 35722443480982865402472708476043442425733008974338590732740571439288044750399445768309886235608525462062293873640387566873290074297360217999601448400520205132154753756524032439786899791657880276437689282809204924449557965777448664932808409390101871909891527321153325081050617470632260458813075113388946260187 Client sends 127797448842848121954488250882771977830826673465413750936910630658183975071405914450713731278124203164250434930652049036170819535970280804049196553010162633156577141815179464515252279713964271606716715014646766749579510316816748666870072015136797913971348128447740025250894377302071638466698949359526412870651 They match! For prime 142138372489186296934432789074730351120710343583373157254717555280717994617139404108305145798143128240366468124631755320405570042298068398339249487210841144998692688990639462886066547739915554040939860792213045903182506781816342941136645853897954130662162366846026652379079675700182556761759296621432433114527 Server sends 57909437376491263333860128704517062473052581506988000780208589697700160622818657491020927069174334590689005246602491818778042635096235013378062277671080777181647826362344340842627755463864137193709234261563885844860020519492373742821543386511160638153209971202850811075825959919001137970259829456768180860830 Client sends 20666654337689487486565876554686297273490680446102814001264166762996648525385896863313613320374592938205525512887806427115235744743389518580973268390915376804384819970305420712573860717686130208187297259778788490585261457346074805142060584114580062931724664488400436861270340555325260656244428090967506380699 They match! For prime 174377137079990939170850558066906438099440150655995316110138558138505723450081528829521727714057714498216958747545817677518489941020709185114944102877950228162212932746737504382457406311946369209470923136985382133418937190556374104954035107932286311860162734787273808798240097360306990253720953723927074719623 Server sends 168370280500864946818861813957515911202298268746677443018810436328411023284221289114834598070238530169532412632117634900880138854403957856376155207524933920515178578648534250462068896979110766340801649803012392558177526186304192611708534406875129022459998245348339257982710275347450888951174128808331822667650 Client sends 49242303044363650326373344020242147723464019699774115849536941803437211766976320845715152571574388923571241505072674654639154919277937049793219194255349697156909934846832119568247878110947445320525783169779123297961354393708636235906535713704833078551436319583880871889643315498018394963319002937271702194832 They match! ...
We made a reasonable assumption that the passwords used in the test run are the same as those used in the running server (since they mentioned that they want to make sure all the values work). Therefore, our intuition was to find the three 16-bit integers using the values given to us in the log file (test_primes.log). However, we made very little progress until a hint was revealed to us on the second day:
"Legendre would be proud. Some of these clearly can't be square. I'd give you a hint, but I'll need some reciprocity."
- We would probably need to use some expression/function related to Legendre
- Some of the numbers given in the log file are not square
- The solution would involve the Law of Quadratic Reciprocity
A search of "legendre square reciprocity" on Google led us to an article on the Legendre Symbol. The symbol is useful for determining whether a given integer is a quadratic residue modulo p.
The important property of the Legendre Symbol is that "the product of two numbers that are both quadratic residues or quadratic non-residues modulo p is a residue, whereas the product of a residue with a non-residue is a non-residue". This means that if w is a quadratic residue modulo p, then w^x would still be a quadratic residue modulo p, so long as x is a positive integer. The same cannot be said if w is not a quadratic residue modulo p but fortunately we didn't have to worry about that in this challenge.
The important property of the Legendre Symbol is that "the product of two numbers that are both quadratic residues or quadratic non-residues modulo p is a residue, whereas the product of a residue with a non-residue is a non-residue". This means that if w is a quadratic residue modulo p, then w^x would still be a quadratic residue modulo p, so long as x is a positive integer. The same cannot be said if w is not a quadratic residue modulo p but fortunately we didn't have to worry about that in this challenge.
Having established that idea, we now need to know how we can determine if a number is a quadratic residue mod p. This is where the Legendre Symbol comes in useful. The Legendre Symbol of x where x is a quadratic residue modulo p is 1 and (0 or -1) otherwise. With this knowledge, we can narrow down the list of candidate passwords by checking if every quadratic residue w mod p in the log file has corresponding quadratic residues w^a and w^b modulo p. As it turns out, this technique itself helped us to narrow down the list of candidates to only 1 integer per password:
#!/usr/bin/env python from gmpy import legendre, mpz from hashlib import sha512 def get_passwords(): log = open('test_primes.log') pw_file = open('passwords.txt', 'w') primes = [long(line.strip()) for line in open('primes.txt')] passwords = [] for pw in range(3): print "[+] Cracking password %d" % (pw+1) log.readline() log_values = [] candidate_w = [] for prime in primes: prime = mpz(log.readline().split()[-1]) B = mpz(log.readline().split()[-1]) A = mpz(log.readline().split()[-1]) log.readline() log.readline() log_values.append((prime, B, A)) for i in range(2**16): w = mpz(int(sha512(str(i)).hexdigest(), 16)) is_valid = True for (p, B, A) in log_values: r = legendre(w, p) r1 = legendre(B, p) r2 = legendre(A, p) if r == 1 and (r1 != 1 or r2 != 1): is_valid = False break if is_valid: candidate_w.append(w) pw_file.write(str(i)+'\n') # to speed things up, since I already know it works break assert len(candidate_w) == 1 passwords.append(candidate_w[0]) print "[+] Password %d retrieved." % (pw + 1) print '[+] All passwords retrieved!' return passwords
Using these passwords and the following script, we can obtain the flag:
Hooray! Legendre would be proud! :P
#!/usr/bin/env python from get_passwords import get_passwords from gmpy import mpz from pwn import * from itertools import product from random import SystemRandom import hashlib, string def do_pow(r): challenge = r.recvline().strip() print "[-] Challenge issued:", challenge for combo in product(string.printable, repeat=10): suffix = ''.join(combo) work = hashlib.sha512(challenge + suffix).hexdigest()[0:6] if work == '000000': break print "[+] Sending suffix:", suffix r.sendline(suffix) def get_key(r, w): rnd = SystemRandom() p = int(r.recvline().strip()) B = int(r.recvline().strip()) a = 2 + rnd.randrange(p-2) A = pow(w, a, p) r.sendline(str(A)) K = pow(B, a, p) key = int(hashlib.sha512(str(K)).hexdigest(), 16) return key keys = [] passwords = get_passwords() r = remote('54.169.55.13', 2308) do_pow(r) for w in passwords: keys.append(get_key(r, w)) rec_flag = r.recvline().strip() encrypted_flag = int(rec_flag) decrypted_flag = encrypted_flag ^ keys[0] ^ keys[1] ^ keys[2] print "[+] Flag:", hex(decrypted_flag)[2::].decode('hex').strip()
Hooray! Legendre would be proud! :P
Comments
Post a Comment