CSAW CTF Quals 2013 Crypto500 Writeup

Problem Description

We’ve found the source to the Arstotzka spies rendevous server, we must find out their new vault key. Source code is here.

So we have to crack sha512 puzzle and calc correct hash. At first i was trying to calculate sEphemeralPriv out, but it seems impossible. after some try, I realized that you can just use “n^m mod === something”.

Code

#!/usr/bin/python
import os
import sys
import time
import struct
import socket
import telnetlib
import random,hashlib,base64
from hashlib import sha512,sha1

def hashToInt(*params):
sha=sha512()
for el in params:
sha.update("%r"%el)
return int(sha.hexdigest(), 16)

def gs(num):
return hashlib.sha1(num).digest()

def crack(sha_p):
print "crack:",sha_p
ss=""
ret=0
for keylen in range(10,40):
if gs(new_msg)[-3:]=="\xff\xff\xff":
print "got one %s"%len(new_msg)
if len(new_msg)==21:
ss=new_msg
print "WE CRACK THE PUZZLE %d\n"%len(ss)
ret=1
return (ret,ss)

return (ret,ss)

#s = socket.create_connection(('128.238.66.222',7788))
s = socket.create_connection(('127.0.0.1',7788))
se=""
for i in range(1,100):
ss=s.recv(1000)
print ss
sha_p=ss[len(ss)-16:]
new_msg=crack(sha_p[-16:])
if new_msg[0]:
se=new_msg[1]
print "send:",se,hashlib.sha1(se).digest()[-3:]
break

s.send(se)
#raw_input()
N = 59244860562241836037412967740090202129129493209028128777608075105340045576269119581606482976574497977007826166502644772626633024570441729436559376092540137133423133727302575949573761665758712151467911366235364142212961105408972344133228752133405884706571372774484384452551216417305613197930780130560424424943100169162129296770713102943256911159434397670875927197768487154862841806112741324720583453986631649607781487954360670817072076325212351448760497872482740542034951413536329940050886314722210271560696533722492893515961159297492975432439922689444585637489674895803176632819896331235057103813705143408943511591629

index=28483644508750028902258833085453121291738558908844640378204850915473006274236033891815596646870094954832384471913373171061099388958373536383247454431214837805096635029244738399662911119306089493137122381562794483801525427601711736403424013966624957471463169984161438593701202381673774894874606950326837142168801614196218030413825361835813060325642766963973454456577907567314093695138863251603368180581162185039224604662844750924047132242103613509637088222461132023037724162558095265336717907895786691004801515830247270579025866384571194244368350362690250445425121639616294300827554006418861422621428030154329451920623#17095359415354811031956139176232822755293333580176796651092816713929142596363160518183074582333639666374490434453616522976528693318889544211598801485465809374370977363040240176466544504447562622451988654983833567639785357067606037932165650485806709538575591881306056180364137612491852807151445333929946180083335184143784040034635507293616742432550220001472750029503246943474764484598756871323795898352813684410952415776064654304191774216122857994311730048413954488815342894838841918071841785821830683677234982197021652871796420412165927837273704381564043458200253387672509280296033910910416083249362331740208987494679

cEphemeral=1
send_num1=str(hex(index))[2:][:-1]
send_num2=str(hex(cEphemeral))[2:]

s.send(struct.pack("H",len(send_num1)))
s.send(send_num1)#send numberc index-->base number

print "1:",s.recv(72)
print "2:",s.recv(60)

s.send(struct.pack("H",len(send_num2)))
s.send(send_num2)#send number cEphemeral

salt=int(s.recv(128),16)
sEphemeral=long(int(s.recv(514),16))

#print "3:salt:",salt
#print "4:sEphemeral:",sEphemeral
tmp=hashToInt(salt,"")
storedKey = pow(index,tmp , N)
cq_sEphemeral=(3 * storedKey) % N
tmp1=(sEphemeral-cq_sEphemeral)%N

#agreedKey_withouthash = (cEphemeral * index^[sha512(salt, password) * slush])^sEphemeralPriv mod Nwhoami
#   cEphemeral=1  -->
#agreedKey_withouthash = (index^[sha512(salt, password) * slush])^sEphemeralPriv mod N
#cause cEphemeral^^3 mod N =1
#so if sha512(salt, password) * slush * sEphemeralPriv mod 3 == 0
#agreedKey_withouthash = 1
#so we don't need to know sEphemeralPriv

slush = hashToInt(cEphemeral, sEphemeral)
salt=hashToInt(index)
agreedKey=hashToInt(1L)
gennedKey=hashToInt(hashToInt(N) ^ hashToInt(index), hashToInt(index), salt,int(cEphemeral), long(sEphemeral), agreedKey)
send_num3=str(hex(gennedKey))[2:][:-1]
s.send(struct.pack("H",len(send_num3)))
s.send(send_num3)

print s.recv(1000)
print s.recv(1000)#-->flag recv
print s.recv(1000)