Hello, Let's level up this blog with some crypto challenges :)

Intro
Shmoocon 2011 released their crypto challenges http://crackmes.de/users/andrewl.us/shmoocon_2011_crypto_challenge_pack/ and we'll try to solve them.

Ok :

dad@gambas /tmp % wget http://crackmes.de/users/andrewl.us/shmoocon_2011_crypto_challenge_pack/download --2011-02-08 17:25:08-- http://crackmes.de/users/andrewl.us/shmoocon_2011_crypto_challenge_pack/download Résolution de crackmes.de... 88.198.55.82 Connexion vers crackmes.de|88.198.55.82|:80...connecté. requête HTTP transmise, en attente de la réponse...200 OK Longueur: 22865 (22K) [application/zip] Sauvegarde en : «download» 100%[===============================================================>] 22 865 --.-K/s ds 0,07s 2011-02-08 17:25:08 (303 KB/s) - «download» sauvegardé [22865/22865] dad@gambas /tmp % unzil -l download zsh: correct 'unzil' to 'unzip' [nyae]? y Archive: download Length Date Time Name --------- ---------- ----- ---- 1094 2011-01-27 13:16 crypto1.py 1000 2011-01-27 13:19 crypto2.py 5027 2011-01-27 13:20 crypto3.py 28336 2011-01-27 13:20 crypto4.py 15075 2011-01-31 20:40 crypto5.py 1349 2011-01-27 13:24 README 2886 2011-01-27 13:20 warmup.py --------- ------- 54767 7 files

Seems that crypto 1 is the easiest part so we're gonna start with it

Crypto 1dad@gambas /tmp % python2 crypto1.py usage: crypto1.pydad@gambas /tmp % python2 crypto1.py name 1010 bad

While browsing the code we see that 'good' is printed while pow(c, d, n) == m. Given d and n, c is int(serial) and m = hex(name). So we have to solve serial^d%n == name, RSA ?! Ok sounds like some old school maths will appear, the time to define some functions :

def iterative_egcd(a, b): x,y, u,v = 0,1, 1,0 while a != 0: q,r = b/a,b%a; m,n = x-u*q,y-v*q b,a, x,y, u,v = a,r, u,v, m,n return b, x, y def modinv(a, m): g, x, y = iterative_egcd(a, m) # or recursive_egcd(a, m) if g != 1: return None else: return x % m

It is needed as we will find serial = name^modinv(d, phi_n) mod n. phi_n is calculated thanks to the factorization of n :

# listFactors = sympy.factorint(n).keys() listFactors = [1431655777,572662309,1717986953,2290649227,1145324633,858993503,2004318077,286331173] # phi_n = phi_n = 1 for i in listFactors: phi_n*= i-1 dad@gambas /tmp % python2 crypto1_sol.py Gr@L@nD 1 Gr@L@nD => 20110343829220932 phi_n = 1821668770858768688568830104173455278614348858086775854542934108212297728 modinv(d, phi_n) = 174725878413998504300527427786354881690797517767573630493566745566969857 Found c:229078519703809131552789955890563407627700764338566985398325879250838863 c^d%n = 20110343829220932 m = 20110343829220932 good

RSA!!! No need for sources ? :)

Crypto2dad@gambas /tmp % python2 crypto2.py usage: crypto2.pydad@gambas /tmp % python2 crypto2.py name 1010 bad

A fast analyze of the code shows that a checksum is calculated on the value generated from the name. This checksum is reversible and can be shown as an error code (XORed). Then msb is dropped and the error code is appended to the variable. This operation is made 0x10001 times.

for i in range(65537): temp = state & 0x800000000000000D sum = 1 while temp: sum ^= (temp & 1); temp >>= 1; state = ((state <<>

Luckily for us, 0x800000000000000D is exactly what we need to reverse the algorithm! The mask is 2**64-1 and so the dropped bit is calculated by the error code. The only step to recover it is to calculate the checksum again, if the recovered sum match, it was a 0; otherwise a 1. Btw we'll loop as done before :

for i in range(65537): state_ori = state state = state >> 1 temp = state & 0x800000000000000D #print "temp:" + str(temp) sum = 1 while temp: sum ^= (temp & 1); # print " sum:"+ str(sum) temp >>= 1; # print " temp:" + str(temp) if (state_ori & 1) != sum: state |= (1 <<>

Let's try our snippet :

dad@gambas /tmp % python2 crypto2_sol.py Gr@L@nD 1 state to find: 20110343829220932 reverse state:15623916848929268887 sum: 1 temp: 0 bad dad@gambas /tmp % python2 crypto2.py Gr@L@nD 15623916848929268887 good

Yipie! Had a hard time trying to reverse the algorithm operation by operation, should always think of the associated state machine :)

Crypto 3Ok difficulty 5/9 it should be harder! As a quick analysis, two lists are calculated from both name and serial derivated from two distincts subsitution boxes. Solution is found when lists are equals, so we have to reverse engineer final list generation algorithm and calculate the associated number. [To finish :]

Referenceshttp://code.activestate.com/recipes/474129-extended-great-common-divisor-function/ http://python.jpvweb.com/mesrecettespython/doku.php?id=restes_chinois

Nice work! I hope you try the others :) The crackmes.de page now has Dcoder's full solution too if needed.

ReplyDelete