Cryptomix : Write Up
Tl;Dr
Cryptomix était un challenge de reverse orienté crypto comme son nom l’indique, le plus dur n’était pas de reverser le binaire mais de casser l’algorithme de cryptographie derrière.
Au final, il était possible de casser le chiffrement par block via un attaque de Wiener. Celle si était possible du à une faible d’implémentation où le message était chiffré plusieurs fois de suite.
Step 1: Reverse Engineering
Le premier réflexe avant d’éxecuter le binaire est de l’ouvrir dans un désassembleur (IDA dans mon cas).
On repère assez rapidement la fonction main, le fait que le binaire n’est pas strippé ( il y a toujours les symboles ) et le fait qu’il utilise une librairie appelé libtommath ( https://github.com/libtom/libtommath ) utilisée pour des maths sur des grands nombres en C.
N’étant pas familié avec la libtommath, je me suis dis que la méthode la plus simple, au vu de la complexité du code ( trés peu de code ) était de recode ce binaire de mon coté.
Pour ce faire, il nous faut d’abord récupérer les données statiques qui sont dans le binaire et utilisées pour effectuer les opérations mathématiques.
Dans ces cas là Radare2 est plus intéressant parcequ’il permet de directement générer le code dans le langage voulu.
Récupérer des données en C :
pcc length @offset
En python :
pcp length @offset
On récupère donc IV_b, n_b et e_i_b.
Le code en C une fois recodé est le suivant ( les tableau sont dans data.h)
(nb: je me suis permis de remplacer la fonction modular_exp par celle déjà présente dans la libtommath)
#include <stdlib.h>
#include <string.h>
#include "tommath.h"
#include "data.h"
int get_clear_text(char* path,char* out_buffer){
FILE* fp = fopen(path,"r");
long length;
if ( !fp )
{
puts("A file that I can open please :(");
exit(1);
}
fseek(fp, 0, SEEK_END);
length = ftell(fp);
if ( length & 0x7F || length > 1199 )
{
puts("Nah I don't like this file.");
exit(0);
}
fseek(fp, 0, 0);
fread(out_buffer, 1, length, fp);
fclose(fp);
return length / 128;
}
int main(int argc, char** argv){
FILE *write_ptr;
char buffer[1200];
int nb_blocks;
int err;
//tommath specific
mp_int n, e ,exp_result, new_iv, current_block, old_iv, xor_result;
if ( argc != 2 )
{
printf("Gimme some file bruh !\nUsage : %s <file>\n", *argv);
exit(1);
}
write_ptr = fopen("test.bin","wb"); // w for write, b for binary
nb_blocks = get_clear_text(argv[1], buffer);
err = mp_init_multi(&n, &e,&exp_result, &new_iv, ¤t_block, &old_iv, &xor_result, NULL);
// Setting buffer to value
err = mp_read_unsigned_bin(&n, n_b, 128LL);
err = mp_read_unsigned_bin(&old_iv, IV_b, 128LL);
for ( int i = 0; i < nb_blocks; ++i )
{
err = mp_read_unsigned_bin(¤t_block, &buffer[128 * i], 128LL);
// generate iv from block
err = mp_xor(¤t_block,
&old_iv,
&xor_result);
mp_set(&new_iv, 1LL);
for ( int j = 0; j <= 712; ++j )
{
for ( int k = 0; k <= 127; ++k ){e_i_b[128 * j + k] ^= j % 255; }
//e = e[j]
err = mp_read_unsigned_bin(&e, &e_i_b[128 * j], 128LL);
// c = pow(xored, e, n)
err = mp_exptmod(&xor_result, &e, &n, &exp_result);
err = mp_mul(&new_iv, &exp_result, &new_iv);
err = mp_mod(&new_iv,
&n,
&new_iv);
for ( int l = 0; l <= 127; ++l ){ e_i_b[128 * j + l] ^= j % 255; }
}
memset(buffer, 0LL, 128LL);
int v13 = 128 - mp_unsigned_bin_size(&new_iv);
err = mp_to_unsigned_bin(&new_iv,
&buffer[v13]);
// save the current block to the file
fwrite(buffer, 128LL, 1, write_ptr);
err = mp_copy(&new_iv, &old_iv);
}
fclose(write_ptr);
mp_clear_multi(&n, &e, &exp_result, &new_iv, ¤t_block, &old_iv, &xor_result, NULL);
return 0;
}
Et puis bon puisqu’on va pas déconner non plus je l’ai refait en python aussi :
#!/bin/python2
import sys
import struct
from data import *
def read_unsigned_bin(buffer, offset, length):
'''
Converti les valeurs d'un tableau en int
'''
struct_type = str(length) + "B"
out = struct.pack(struct_type, *buffer[offset:offset+length])
return int(out.encode("hex"),16)
def int_to_str(a,length):
'''
Converti un entier en chaine
'''
hex_value = hex(a).replace("L","")[2:]
if(len(hex_value)%2!=0):
hex_value = "0" + hex_value
return hex_value.decode("hex").ljust(length,"\x00")
def encrypt(buffer, nb_blocks, out_file="out_python.bin"):
'''
Processus de chiffrement adapté à python
'''
# Output file
out_file = open(out_file,"wb")
# Initialisating data
n = read_unsigned_bin(n_b,0,128)
old_iv = read_unsigned_bin(IV_b,0,128)
new_iv = 1
for i in range(nb_blocks):
current_block = read_unsigned_bin(buffer ,128*i, 128)
xor_result = current_block ^ old_iv
for j in range(713):
#xoring e
for k in range(128):
e_i_b[128 * j + k] ^= j % 255
e = read_unsigned_bin(e_i_b, 128*j , 128)
# RSA
exp_result = pow(xor_result,e,n)
#new_iv = c % n
new_iv = exp_result * new_iv
new_iv = new_iv % n
# setting e to initial value
for l in range(128):
e_i_b[128 * j + k] ^= j % 255
buffer = new_iv
out_file.write(int_to_str(new_iv,128))
old_iv = new_iv
out_file.close()
def decrypt(buffer, nb_blocks, out_file="out_python.bin"):
pass
if __name__ == '__main__':
if(len(sys.argv) <3):
print("Gimme some file bruh !\nUsage : %s <file> <encrypt|decrypt> [out_file]\n".format(sys.argv[0]))
sys.exit(1)
# Loading input file
buffer = open(sys.argv[1]).read()
buffer = [ord(i) for i in buffer]
nb_blocks = len(buffer) / 128
if(sys.argv[2] == "encrypt"):
if(len(sys.argv) == 3):
encrypt(buffer, nb_blocks)
else:
encrypt(buffer, nb_blocks, sys.argv[3])
elif(sys.argv[2] == "decrypt"):
if(len(sys.argv) == 3):
decrypt(buffer, nb_blocks)
else:
decrypt(buffer, nb_blocks, sys.argv[3])
else:
print("Select an operation between 'encrypt' or 'decrypt'")
sys.exit(1)
Step 2 : Let’s break some crypto
La partie un peu plus compliquée arrive. Maintenant qu’on à le code il faut casser un peu de crypto. Mais pour cela, il est nécessaire de comprendre comment le chiffrement est effectué.
Chiffrement
Le chiffrement est fait de la manière suivante :
Où “RSA yolo” effectue la suite d’opération suivante 713 fois :
- Récupère le e courant
- Chiffre la résultante du xor m en faisant
- le multiplie par un valeur qui correspond à la sortie de la boucle d’avant modulo *n
Step 3 : Attaque
La vulnérabilité vient du fait que le message soit chiffré plusieurs fois successivement. On a la boucle suivante:
Or :
Ce qui permet de simplifier l’équation précedente en :
On a donc dans notre cas :
où
Ce qui nous permet d’effectuer une attaque de Wiener car E se rapproche de n.
Implémentation finale
(merci à https://github.com/orisano/owiener/blob/master/owiener.py pour le copié collé :smile: )
#!/bin/python2
import sys
import struct
from data import *
from typing import Tuple, Iterator, Iterable, Optional
def isqrt(n):
"""
ref: https://en.wikipedia.org/wiki/Integer_square_root
>>> isqrt(289)
17
>>> isqrt(2)
1
>>> isqrt(1000000 ** 2)
1000000
"""
if n == 0:
return 0
# ref: https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Rough_estimation
x = 2 ** ((n.bit_length() + 1) // 2)
while True:
y = (x + n // x) // 2
if y >= x:
return x
x = y
def is_perfect_square(n):
"""
ref: http://d.hatena.ne.jp/hnw/20140503
ref: https://github.com/AlexeiSheplyakov/gmp.pkg/blob/master/mpn/generic/perfsqr.c
>>> is_perfect_square(100)
True
>>> is_perfect_square(2000000000000000000000000000 ** 2)
True
>>> is_perfect_square(2000000000000000000000000000 ** 2 + 1)
False
"""
sq_mod256 = (1,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0)
if sq_mod256[n & 0xff] == 0:
return False
mt = (
(9, (1,1,0,0,1,0,0,1,0)),
(5, (1,1,0,0,1)),
(7, (1,1,1,0,1,0,0)),
(13, (1,1,0,1,1,0,0,0,0,1,1,0,1)),
(17, (1,1,1,0,1,0,0,0,1,1,0,0,0,1,0,1,1))
)
a = n % (9 * 5 * 7 * 13 * 17)
if any(t[a % m] == 0 for m, t in mt):
return False
return isqrt(n) ** 2 == n
def rational_to_contfrac(x, y) :
"""
ref: https://en.wikipedia.org/wiki/Euclidean_algorithm#Continued_fractions
>>> list(rational_to_contfrac(4, 11))
[0, 2, 1, 3]
"""
while y:
a = x // y
yield a
x, y = y, x - a * y
def contfrac_to_rational_iter(contfrac):
"""
ref: https://www.cits.ruhr-uni-bochum.de/imperia/md/content/may/krypto2ss08/shortsecretexponents.pdf (6)
"""
n0, d0 = 0, 1
n1, d1 = 1, 0
for q in contfrac:
n = q * n1 + n0
d = q * d1 + d0
yield n, d
n0, d0 = n1, d1
n1, d1 = n, d
def convergents_from_contfrac(contfrac) :
"""
ref: https://www.cits.ruhr-uni-bochum.de/imperia/md/content/may/krypto2ss08/shortsecretexponents.pdf Section.3
"""
n_, d_ = 1, 0
for i, (n, d) in enumerate(contfrac_to_rational_iter(contfrac)):
if i % 2 == 0:
yield n + n_, d + d_
else:
yield n, d
n_, d_ = n, d
def attack(e, n):
"""
ref: https://www.cits.ruhr-uni-bochum.de/imperia/md/content/may/krypto2ss08/shortsecretexponents.pdf Section.4
>>> attack(2621, 8927)
5
>>> attack(6792605526025, 9449868410449)
569
>>> attack(30749686305802061816334591167284030734478031427751495527922388099381921172620569310945418007467306454160014597828390709770861577479329793948103408489494025272834473555854835044153374978554414416305012267643957838998648651100705446875979573675767605387333733876537528353237076626094553367977134079292593746416875606876735717905892280664538346000950343671655257046364067221469807138232820446015769882472160551840052921930357988334306659120253114790638496480092361951536576427295789429197483597859657977832368912534761100269065509351345050758943674651053419982561094432258103614830448382949765459939698951824447818497599, 109966163992903243770643456296093759130737510333736483352345488643432614201030629970207047930115652268531222079508230987041869779760776072105738457123387124961036111210544028669181361694095594938869077306417325203381820822917059651429857093388618818437282624857927551285811542685269229705594166370426152128895901914709902037365652575730201897361139518816164746228733410283595236405985958414491372301878718635708605256444921222945267625853091126691358833453283744166617463257821375566155675868452032401961727814314481343467702299949407935602389342183536222842556906657001984320973035314726867840698884052182976760066141)
4221909016509078129201801236879446760697885220928506696150646938237440992746683409881141451831939190609743447676525325543963362353923989076199470515758399
"""
f_ = rational_to_contfrac(e, n)
for k, dg in convergents_from_contfrac(f_):
edg = e * dg
phi = edg // k
x = n - phi + 1
if x % 2 == 0 and is_perfect_square((x // 2) ** 2 - n):
g = edg - phi * k
return dg // g
return None
def read_unsigned_bin(buffer, offset, length):
struct_type = str(length) + "B"
out = struct.pack(struct_type, *buffer[offset:offset+length])
return int(out.encode("hex"),16)
def int_to_str(a,length):
hex_value = hex(a).replace("L","")[2:]
if(len(hex_value)%2!=0):
hex_value = "0" + hex_value
return hex_value.decode("hex").ljust(length,"\x00")
def encrypt(buffer, nb_blocks, out_file="out_python.bin"):
# Output file
out_file = open(out_file,"wb")
# Initialisating data
n = read_unsigned_bin(n_b,0,128)
old_iv = read_unsigned_bin(IV_b,0,128)
new_iv = 1
for i in range(nb_blocks):
current_block = read_unsigned_bin(buffer ,128*i, 128)
xor_result = current_block ^ old_iv
for j in range(713):
#xoring e
for k in range(128):
e_i_b[128 * j + k] ^= j % 255
e = read_unsigned_bin(e_i_b, 128*j , 128)
# RSA
exp_result = pow(xor_result,e,n)
new_iv = exp_result * new_iv
new_iv = new_iv % n
# setting e to initial value
for l in range(128):
e_i_b[128 * j + k] ^= j % 255
buffer = new_iv
out_file.write(int_to_str(new_iv,128))
old_iv = new_iv
out_file.close()
def decrypt(buffer, nb_blocks, out_file="out_python.bin"):
# Output file
out_file = open(out_file,"wb")
n = read_unsigned_bin(n_b,0,128)
old_iv = read_unsigned_bin(IV_b,0,128)
current_block = read_unsigned_bin(buffer ,128*0, 128)
old_block = current_block
## Creating sums of E
E = 0
for j in range(713):
for k in range(128):
e_i_b[128 * j + k] ^= j % 255
E += read_unsigned_bin(e_i_b, 128*j , 128)
for l in range(128):
e_i_b[128 * j + k] ^= j % 255
# Performing Wiener attack
print("Sum E : " + str(E) )
d = attack(E,n)
print("Found d : " + str(d))
# Deciphering first block with the initial iv
unciphered = pow(current_block,d,n)
out_file.write(int_to_str(unciphered^old_iv,128))
print("Block 1 = " + int_to_str(unciphered^old_iv,128))
# Deciphering all blocks one by one using the block before as xor
for i in range(1,nb_blocks):
current_block = read_unsigned_bin(buffer ,128*i, 128)
unciphered = pow(current_block,d,n)
out_file.write(int_to_str(unciphered^old_block,128))
print("Block "+str(i)+" = " + int_to_str(unciphered^old_block,128))
old_block = current_block
out_file.close()
if __name__ == '__main__':
if(len(sys.argv) <3):
print("Gimme some file bruh !\nUsage : %s <file> <encrypt|decrypt> [out_file]\n".format(sys.argv[0]))
sys.exit(1)
# Loading input file
buffer = open(sys.argv[1]).read()
buffer = [ord(i) for i in buffer]
nb_blocks = len(buffer) / 128
if(sys.argv[2] == "encrypt"):
if(len(sys.argv) == 3):
encrypt(buffer, nb_blocks)
else:
encrypt(buffer, nb_blocks, sys.argv[3])
elif(sys.argv[2] == "decrypt"):
if(len(sys.argv) == 3):
decrypt(buffer, nb_blocks)
else:
decrypt(buffer, nb_blocks, sys.argv[3])
else:
print("Select an operation between 'encrypt' or 'decrypt'")
sys.exit(1)
Flag
ECSC{RS@CBC_is_militAry_crYpt0}