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 1

dad@gambas /tmp % python2 crypto1.py
usage:  crypto1.py   
dad@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 ? :)

Crypto2

dad@gambas /tmp % python2 crypto2.py
usage:  crypto2.py   
dad@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 3

Ok 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 :]

References

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