Summary: attacking password-based key exchange schemes based on SPEKE with MITM.
In these two challenges we were given a service which simply sends a flag after a session of some Password Authenticated Key Exchange (PAKE) scheme.
PAKE (The first challenge)
fail unless is_safe_prime(p) # each password is an integer in 1..16 passwords = IO.readlines('passwords').map(&:to_i) fail unless passwords.grep_v(1..16).empty? fail unless passwords.size == 11 passwords.map!{|pass| Digest::SHA512.hexdigest(pass.to_s).to_i(16)} key = 0 puts "p = #{p}" passwords.each.with_index(1) do |password, i| puts "Round #{i}" w = pow(password, 2, p) # NO to Legendre b = 2 + SecureRandom.random_number(p - 2) bb = pow(w, b, p) puts "Server send #{bb}" aa = gets.to_i if aa < 514 || aa >= p - 514 puts 'CHEATER!' exit end k = pow(aa, b, p) key ^= Digest::SHA512.hexdigest(k.to_s).to_i(16) end flag ^= key puts "Flag is (of course after encryption :D): #{flag}" |
The server has 11 very small password – integers from 1 to 16. For each password a simple Diffie-Hellman key exchange is done, however the generator depends on the password (this is SPEKE protocol). Then all the resulting keys for all passwords are xored.
Clearly, we can’t guess all the keys at once. On the other hand, if we don’t guess even a single key, the final key is xored with something “random” to us, something about what we don’t have any information at all. From this point of view this challenge looks unsolvable and I was stuck on it for the whole day. The challenge author even increased the points from 150 to 250 since nobody solved it for some time.
The key idea is that we can do a Man-In-The-Middle attack here, between the server and… the server itself! Indeed, the server is the only “person” who knows the passwords and can pass the protocol in a meaningful way. We can maintain two connections and for each password $p$ we will exchange the $g_p^a$ and $g_p^b$ send to us by the server in two connections. Then they will obtain same secret for each of the passwords: $g_p^{ab}$ and the same final master key too!
It is cool that we managed to connect the server to itself, but.. the flag is still encrypted… However, now we can perform attacks on single passwords! Indeed, if we guess a password $p$ correctly, then we can compute the generator $g_p$ and perform the basic MITM attack against classical Diffie-Hellman. For example, we allow the servers to exchange keys related to the first 10 passwords, and then for the 11-th password $p$ we try to guess it and send $g_p^1$ to both servers. Then the servers will compute 11th shared keys $g_p^{a}$ and $g_p^{b}$ which they have already sent to us. Now, the final xor of the keys will be different on two servers. However, if our password guess was correct, we can unxor the last shared keys and see that the new shared keys are now equal. Thus we have obtained a way to bruteforce each password separately.
Here is solution script (takes a while due to heavy PoW):
import os from hashlib import sha512, sha1 from libnum import * from sock import Sock def getHashes(p1, p2): # bruteforce proof-of-work in C data = os.popen("./sha1 '%s' '%s'" % (p1, p2)).read() return data.split() def numhash(n): return s2n(sha512(str(n)).digest()) p = 285370232948523998980902649176998223002378361587332218493775786752826166161423082436982297888443231240619463576886971476889906175870272573060319231258784649665194518832695848032181036303102119334432612172767710672560390596241136280678425624046988433310588364872005613290545811367950034187020564546262381876467 pws = [8, 15, 9, 15, 7, 7, 13, None, 10, 15, None] pws = [None] * 11 for pwi in xrange(11): if pws[pwi] is not None: continue for pwc in xrange(1, 17): print pwi, pwc, "getting prefixes" f1 = Sock("52.197.112.79 20431") f2 = Sock("52.197.112.79 20431") prefix1 = f1.read_until_re(r"prefix: (\S+)").decode("base64") prefix2 = f2.read_until_re(r"prefix: (\S+)").decode("base64") sol1 = sol2 = getHashes(prefix1, prefix2) f1.send_line(str(sol1.encode("base64").strip())) f2.send_line(str(sol2.encode("base64").strip())) recnum1 = None recnum2 = None for i in xrange(11): num1 = int(f1.read_until_re(r"Server send (\d+)")) num2 = int(f2.read_until_re(r"Server send (\d+)")) if i != pwi: f1.send_line(str(num2)) f2.send_line(str(num1)) else: gp = pow(numhash(pwc), 2, p) f1.send_line(str(gp)) f2.send_line(str(gp)) recnum1 = numhash(num1) recnum2 = numhash(num2) f1.read_until("Flag is") f2.read_until("Flag is") res1 = int(f1.read_until_re(r": (\w+)")) res2 = int(f2.read_until_re(r": (\w+)")) if res1 ^ recnum1 == res2 ^ recnum2: print "MATCH!", "pw[%d] = %d" % (pwi, pwc) pws[pwi] = pwc print pws break |
After we have obtained the all passwords, we can implement the legitimate session and get the flag: hitcon{73n_w34k_p455w0rd5_c0mb1n3d_4r3_571ll_wE4k_QQ}
Pake++ (The second challenge)
In the second challenge, the scheme was slightly altered. There are now 8 different prime moduli, each time the prime to be used is chosen at random. Also there is only one password and it has very high entropy. Finally, we have two rounds at each time. Each round a different prime is chosen, but the password is always the same.
primes = <<-EOS.lines.map(&:to_i) 285370232948523998980902649176998223002378361587332218493775786752826166161423082436982297888443231240619463576886971476889906175870272573060319231258784649665194518832695848032181036303102119334432612172767710672560390596241136280678425624046988433310588364872005613290545811367950034187020564546262381876467 298619967637074381179969535203891334279037109216429406440598651658759350405543564192161651312771530156893413427058175045425757160212464963471306913768112396967665485652095651332292521663596653434043497333804676303590560939622585332770724390627970615864007468306226942254398801398715678948641382895998651226267 298049748677563805780319663628819960854615659462424022507630185085633596966175010904970480952385372951172828141165347514534458425242085310886903778569556019799929063608007455863031014344586675081359600240391009588905845818495639778564642452193502269859322492791462878008970754999615280381704729202349939626979 328517416048692886037451935540065593512994462002198409216093662374867257380362145180594029938263095492728312598227855130627235361314817436633177786884494030007864152308901161140111969980403722704138376439893801083486571959976238463025246682645769458504940248785078868650651872930977987712522710703736396657387 282394389781374199382509925858094901774563649174745796339967395605116291562054020073955455338401167970080036287402587308354538500190221028476399923564634339732689941702464496890308354549764266506953808881910012117986860385319905877301417806557760524821229657147194856430018136428864202922733288830153277890659 323103830544117987011024048071694067643223166857443601288678625077550042396643402625692490043863582981782378717042298512462563264457088124223575174164921578128007273839310675925364961100802146846497562297376569657569712628347758371790366124768858903423043207000026049079160253301902404207920358137230602539643 302103350544659483531131684583742544907887033086695553935842864801685693649953339273310786890360791425112212069129996061391578244584149171226282625727635376367322205108426287980490462476857893899354488802419996817239780781622440165425711955277936322570946121224712118336303389972089563531346006960196427704219 274405967560432033789798999119890457360306712028734789799802515309420810630484361406114488871989143593759704555407742610118391422809479638606936598462341976320928990585877751200977318034499800109548890002507225944134922612505410751207789339655283747859299017222586400523098060723763539689025418276604564593619 EOS fail unless primes.all?{|p| is_safe_prime(p)} password = IO.read('password2').strip fail unless password =~ /\A[a-zA-Z0-9]{20}\z/ password = Digest::SHA512.hexdigest(password).to_i(16) key = 0 2.times do |i| puts "Round #{i + 1}" p = primes[SecureRandom.random_number(primes.size)] puts "p = #{p}" w = pow(password, 2, p) # NO to Legendre b = 2 + SecureRandom.random_number(p - 2) bb = pow(w, b, p) puts "Server send #{bb}" aa = gets.to_i if aa < 514 || aa >= p - 514 puts 'CHEATER!' exit end k = pow(aa, b, p) key ^= Digest::SHA512.hexdigest(k.to_s).to_i(16) end flag ^= key puts "Flag is (of course after encryption :D): #{flag}" |
Now that we know the MITM idea, it is not much harder. If we manage to get the the same primes in two connections and simply exchange the values sent, we will get same key in both connections. Even if the keys are different, we can’t get the flag from having $flag \oplus stuff1$ and $flag \oplus stuff2$. For example, if we xor these two things together, the flag is cancelled. To avoid this we simply add the third connection! Then triple xor of $flag \oplus stuff$ will still have $flag$ and hopefully we can cancel all the stuff.
Indeed, we can try to make the following key exchanges between connections $a, b, c$:
$$\begin{split}
k_1 = key\_exchange(a, b), \\
k_2 = key\_exchange(a, c), \\
k_3 = key\_exchange(b, c).
\end{split}$$
Then we will get:
$$\begin{split}
flag \oplus k_1 \oplus k_2 ~\mbox{from}~ a, \\
flag \oplus k_1 \oplus k_3 ~\mbox{from}~ b, \\
flag \oplus k_2 \oplus k_3 ~\mbox{from}~ c.
\end{split}$$
Xoring everythin results in the flag!
There are some technicalities. We need to distribute these three exchanges between all 2 rounds in all 3 connections. This is easy, since the servers not necessarily need to exchange in the same round.
A slightly harder problem is to wait until the primes match in a right way. We can do the following:
- Open several connections until there is a pair of connections with the same prime $p_{ab}$ in the first round.
- Perform the exchange between them.
- See the second round primes $p_a$ and $p_b$.
- Find a client in the pool or make new connections until we get a connection with the first round prime equal to either $p_a$ or $p_b$.
- Perform the exchange between the corresponding connections.
- Now we have no choice and only one exchange left to do. If the primes do not match, we repeat the full algorithm.
- Otherwise, we get the flag.
The flag: hitcon{m17m_f0r_pr0f1t_bu7_S71ll_d035n7_kn0w_p455w0rd}
