[GreHack 2023][Write Up – Crypto] Middle-Grade

middle-grade.py

from random import SystemRandom 
from Crypto.Cipher import AES 
from Crypto.Util.number import long_to_bytes , bytes_to_long 
from hashlib import sha256 
from functools 
import reduce random = SystemRandom() 

def encrypt(plain, key): 
    Ks = [(key >> (12*i)) & (pow(2, 12) - 1) for i in range(4)] 
    reduce(lambda D,K:print(D,K) , Ks, plain) 
    return reduce(lambda D,K:AES.new(sha256(long_to_bytes(K)).digest(), AES.MODE_ECB).encrypt(D) , Ks, plain) 

if __name__ == "__main__": 
    key = random.getrandbits(48) 
    flag = b"GH{__fakeflag__}" 
    assert (len(flag) == 16) 
    plain = b"iloveGH!"*2 
    print("plain = '{}'".format(plain.decode())) 
    print("cipher = '{}'".format(encrypt(plain, key).hex())) 
    print("encrypted_flag = '{}'".format(encrypt(flag, key).hex()))
    plain = 'iloveGH!iloveGH!' 
    cipher = '0f973d8234b8086847b9d423617a19b0' 
    encrypted flag = 'bc4daf41f71e4dd958a852bbbbf8dfec'

Explication du programme

Le programme génère une clé de taille 48 bits. Ce nombre est ensuite séparé en base 4096 (2**12):

>>> from random import SystemRandom 
>>> random = SystemRandom() 
>>> key = random.getrandbits(48) 
>>> key 146736011813222 
>>> Ks = [(key >> (12*i)) & (pow(2, 12) - 1) for i in range(4)] 
>>> Ks 
[358, 3522, 1187, 2135] 
>>> sum([Ks[i] * 4096**i for i in range(4)]) 
146736011813222

Chacun de ces nombres va être converti en bytes, puis hashé en sha256. L’ensemble va composer les 4 clefs AES, qui vont successivement chiffrer le clair, en mode ECB, dans la fonction encrypt.

Exploitation

De base, le nombre de possibilité est de 4096 * 4096 * 4096 * 4096 = 2**48.
Cependant, vu qu’on a accès à un clair et son chiffré, et vu le nombre faible de possibilité à chaque étape, il est possible d’effectuer une attaque dite « Meet in the middle« .
Pour cela, on va tester toutes les possibilités pour la moitié des étapes dans un sens (4096 * 4096 possibilités), puis dans l’autre (4096 * 4096).
Le nombre de possibilités devient alors 2 * 4096 * 4096 = 2**25, qui est nettement moins.

from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes , bytes_to_long
from hashlib import sha256
import binascii

plain = b'iloveGH!iloveGH!'
cipher = binascii.unhexlify('0f973d8234b8086847b9d423617a19b0')

possibilities = ""
for i in range(4096):
s1 = AES.new(sha256(long_to_bytes(i)).digest(),AES.MODE_ECB).encrypt(plain)
for j in range(4096):
s2 = AES.new(sha256(long_to_bytes(j)).digest(),AES.MODE_ECB).encrypt(s1)
possibilities += "%s %d %d\n"%(s2.hex(),i,j)
with open('possibilities.txt','w') as f:
f.write(possibilities)

possibilities = ""
for i in range(4096):
s1 = AES.new(sha256(long_to_bytes(i)).digest(),AES.MODE_ECB).decrypt(cipher)
for j in range(4096):
s2 = AES.new(sha256(long_to_bytes(j)).digest(),AES.MODE_ECB).decrypt(s1)
possibilities += "%s %d %d\n"%(s2.hex(),i,j)
with open('possibilities_reverse.txt','w') as f:
f.write(possibilities)

Le script va nous générer l’ensembles des différentes possibilités (en chiffrant dans « possibilities.txt », et en déchiffrant dans « possibilities.txt »). Plus qu’à trouver l’élément commun:

# On trie les deux listes cat possibilities.txt |awk '{ print $1 }'|sort > p1.txt 
cat possibilities_reverse.txt.txt |awk '{ print $1 }'|sort > p2.txt 
# On récupère l'élément commun des deux listes comm -12 p1.txt p2.txt 
# 81e11c88273f0f7ea2fded6c389189c0 
# On récupère les clefs de chiffrement 
cat possibilities.txt possibilities_reverse.txt |grep 81e11c88273f0f7ea2fded6c389189c0 
# 81e11c88273f0f7ea2fded6c389189c0 638 2697 
# 81e11c88273f0f7ea2fded6c389189c0 2557 2561

On peut alors déchiffrer le flag avec Ks (638, 2697, 2561 et 2557).

from Crypto.Cipher import AES 
from Crypto.Util.number import long_to_bytes , bytes_to_long 
from hashlib import sha256 import binascii 
plain = b'iloveGH!iloveGH!' 
cipher = '0f973d8234b8086847b9d423617a19b0' 7
encrypted_flag = 'bc4daf41f71e4dd958a852bbbbf8dfec' 
Ks = [638,2697,2561,2557] 
tmp = binascii.unhexlify(encrypted_flag) 
for i in Ks[::-1]: 
    tmp = AES.new(sha256(long_to_bytes(i)).digest(),AES.MODE_ECB).decrypt(tmp) 
print(tmp)

Flag

GH{m33t_t1me_:)}