Hacknite Wiki

AES (Advanced Encryption Standard), poznat i pod svojim originalnim nazivom Rijndael, sustav je simetrične kriptografije temeljen na supstitucijsko-permutacijskim poljima.
AES koristi fiksnu veličinu bloka od 128 bitova te veličinu ključa od 128, 192 ili 256 bitova. Provodi se nad matricom 4×4, odnosno nad pravokutnim nizom bajtova u 4 retka i 4 stupca. Na sličan način tretira se i ključ koji je pohranjen u 4 retka i N stupaca, gdje je N ovisan o veličini ključa i može biti 4,6 ili 8. AES se pri enkripciji koristi operacijama zamjene znakova, posmicanja redova, miješanja stupaca te dodavanja potključa.

Funkcije koje AES koristi matematički su opisane u nastavku:
1) Zamjena znakova

znak = Sbox[znak] 

2) Dodaj potključ

blok = blok ⊕ potključ[i]

3) Posmakni redove
Rotira (kružno posmiče) znakove ulijevo u svim retcima osim prvog za unaprijed poznati broj mjesta koji je ovisan o N.

4) Pomiješaj stupac bloka
Množi se stupac po stupac bloka s fiksnim polinomom:

a(x) = 03Hx3 + 01Hx2 + 01Hx + 02H mod x4+1 

Odnosno, za svaki stupac bloka računa se stupac novog stanja:

Postoje razni načini AES kriptiranja koji određuju kako se ulazni podatci dijele u blokove, kako se blokovi kriptiraju i kombiniraju, kako enkripcija upravlja problemima kao što su integritet podataka ili inicijalizacijski vektori (IV) i slično.

Često korišteni AES načini kriptiranja su:
1) ECB (Electronic Codebook)

• Svaki blok teksta kriptira se odvojeno s istim ključem
• Identični blokovi jasnog teksta rezultiraju identičnim blokovima skrivenog teksta
• Nije siguran za enkripciju većih količina ulaznih podataka zbog mogućnosti ponavljanja uzoraka
• Korištenje ovog načina kriptiranja se ne preporučuje

2) CBC (Cipher Block Chaining)

• Svaki blok jasnog teksta se XOR-a sa skrivenim tekstom prošlog kruga enkripcije
• Potreban je inicijalizacijski vektor IV koji se mora izabrati nasumično
• IV se šalje zajedno sa skrivenim tekstom
• Potrebno nadopuniti poruku tako da je duljina višekratnik veličine bloka
• Sigurna enkripcija pod razumnim pretpostavkama

3) CFB (Cipher Feedback) i OFB (Output Feedback)

• Slični protočnoj enkripciji, tj. jednokratnoj bilježnici
• Dekripcija jednaka enkripciji
• Trebalo bi svaki put koristiti različit inicijalizacijski vektor

4) CTR (Counter Mode)

• sličan protočnoj enkripciji, tj. jednokratnoj bilježnici
• na temelju ključa i IV izračuna se niz bitova koji se XOR-a s jasnim tekstom
• može se paralelizirati
• ne zahtijeva nadopunjavanje poruke (eng. padding)

5) GCM (Galois/Counter Mode)

• način autentifikacijskog kriptiranja koji je primjenjiv samo za simetrične blok algoritme s veličinom bloka od 128 bitova
• samo za autentifikaciju – koristi MAC
• ulaz: jasni tekst, IV, povezani autentifikacijski podaci (Associated Data, AD), duljina povezanih podataka i duljina kriptiranog teksta
• izlaz: autentifikacijska značka (Auth Tag)

Generalno se ne preporučuje koristiti način kriptiranja ECB. Inicijalizacijski se vektor ne smije ponavljati i mora biti generiran slučajno, a ne smije se ponavljati ni simetrični ključ.

PRIMJER -Zadatak s Hacknite platforme - AES kriptirana poruka

Ivan je na faksu učio o modernim kriptografskim algoritmima. Toliko je očaran AES algoritmom da je odlučio
samostalno napraviti program za šifriranje svojih najtajnijih informacija. Pokušaj dešifrirati ciphertext
kako bi provjerio je li Ivanov program zaista siguran.

ciphertext (u zasebnoj datoteci):
991262a3123d702aaa296e36e4054dcb0031479d8affcae34dd12757b19868eee63f79e83e9687e10fc74dbd3c1a61bfdb4ec98a75
38f2c75eed1402d3edfd8dc28531c6d75a3786750afa0f48524d9adb4ec98a7538f2c75eed1402d3edfd8ddb4ec98a7538f2c75eed
1402d3edfd8d64019b35eac50ab04f0239080a879f000b42253688df27967c492e721c9e91407edcf9ebd01fd7a17bc0219784322b
5f0b42253688df27967c492e721c9e91402b5bebae08f2851e97e139390d4d6245925a96bbca45277ebecfd06fa54b510edb4ec98a
7538f2c75eed1402d3edfd8d7edcf9ebd01fd7a17bc0219784322b5f3454fe7467cd0e2b6036f48a3c2246930b42253688df27967c
492e721c9e91403856820345c0e11691b05d22b6005906668020a4b98905a562e051955ea720177edcf9ebd01fd7a17bc021978432
2b5fec0e366b9ea7d725dc81fdec29b57bb3

Napomena: u ciphertextu nema znakova novog reda, ali su ovdje dodani radi lakše čitljivosti.

telnet chal.platforma.hacknite.hr 8083
netcat chal.platforma.hacknite.hr 8083

Flag je u formatu CTF2022[brojevi]

U prilogu se nalazi i datoteka encrypt.py.

Pokušajmo se spojiti na chal.platforma.hacknite.hr i port 8083. Imamo mogućnost pisanja, a kao rezultat dobijemo ispis kodiranog teksta koji smo unijeli. U encrypt.py datoteci. vidimo da se koristi AES ECB mod (linija 19: cipher = AES.new(key, AES.MODE_ECB)) te da se svaki znak jasnog teksta tretira kao zasebni blok. U ECB načinu rada se svaki isti blok jasnog teksta uvijek šifrira u isti ciphertext. Uvjerimo se da je zaista tako. Upišimo jedno slovo, a zatim ponovimo to isto slovo tri puta:

Vidimo da se svaka pojava istog znaka šifrira jednako, što i odgovara AES ECB modu. Sad upišimo dio flaga koji znamo, a zatim i cijeli ciphertext da vidimo gdje u njemu počinje flag:

Vidimo da počne odmah na početku. Sad nam preostaje dešifrirati ostatak teksta da bismo dobili flag. Napišimo jednostavnu Python skriptu za to:

data = "CTF2022["
import subprocess
def get_enc(i):
    return str(subprocess.check_output(f"echo \"{i}\" | nc chal.platforma.hacknite.hr 8083",
     shell=True))[2:-3]
 
cipher = open("ciphertext", "r").read()
 
while data[-1] != "]":
    #print(data)
    for x in "123456789[]":
        #print(data + x)
        r = get_enc(data + x)
        if cipher.startswith(r):
            data += x
            break
print(data)

Objasnimo što skripta radi. Kao podatak (data) uzeli smo dio zastavice koji nam je poznat. Nakon toga, dok ne dođemo do kraja flaga (znak “]”), uključujući i njega, brute force pogađamo koji je idući znak u skupu svih mogućih znakova koji se mogu pojaviti u flagu (brojevi i uglate zagrade). Svaki taj mogući znak kodiramo (funkcija get_enc) i, ako se kod poklapa s onime što slijedi u tekstu, znači da je taj znak idući i dodajemo ga na konačni flag. Funkcija get_enc jednostavno se spaja netcatom na stranicu zadanu u zadatku i ispisuje rezultat koji se dobije kodiranjem trenutnog znaka. Važno je napomenuti da uzima samo od indeksa 2 s početka do trećeg znaka od kraja jer python dodaje stringovima b' na početak stringa i '\n na kraj pa da se i ti znakovi ne kodiraju.
Zakomentirani printovi služe za bolje razumijevanje skripte. Poželjno je dodati sleep() između svake iteracije petlje kako se poslužitelj ne bi preopteretio prevelikim brojem zahtjeva.

PRIMJER -Zadatak s Hacknite platforme - Brojač

Mnogi od vas već znaju da je AES ECB način rada nesiguran. 
Zato smo odlučili šifrirati tajnu poruku koristeći AES CTR način rada. 
Dostupan ti je ciphertext, djelomični plaintext te program koji se koristio za šifriranje poruke, 
ali ne i tajni AES ključ.

Možeš li dešifrirati poruku?

Ideja zadatka jest pronaći ranjivost u AES implementaciji s CTR načinom rada. CTR način rada jest definiran sljedećom formulom za enkripciju:

C = P ⊕ AES(key,CTR)

gdje je C ciphertext, P plaintext, a CTR kombinacija nonce vrijednosti (neka nasumična vrijednost) i brojača (u našoj implementaciji su kombinirani pomoću XOR operacije). Funkcija AES ovdje ne šifrira sam plaintext, nego CTR vrijednost koja se zatim XOR-a s plaintextom. Rezultat funkcije AES(key,CTR) zovemo keystream.

Ne šifrira se cijeli plaintext odjednom već se radi u blokovima od 16 bajtova. Prvi ciphertext blok jest veličine 16 te je nastao xoranjem keystreama (za prvu iteraciju) s prvim blokom (također 16 bajtova) plaintexta, drugi ciphertext xoranjem keystreama (za drugu iteraciju) s drugim blokom plaintexta itd… U odnosu na CBC način rada, gdje se svaki novi blok xora s prijašnjim, CTR-om nastali blokovi nisu međusobno ovisni.

AES je funkcija koja prima dva parametra, key i CTR. CTR jest kombinacija noncea i countera. Nonce jest fiksna vrijednost koja se nikada ne mijenja tijekom enkripcije i dekripcije svih blokova, a counter jest vrijednost koja se inkrementira sa svakom novom iteracijom (krećući od 0 u implementaciji). Key jest tajna koja se koristi za enkripciju i dekripciju te se također nikada ne mijenja. AES je funkcija koja interno ne koristi randomizirane vrijednost jer dekripcija ne bi bila moguća. Proces dekripcije je opisan sljedećom formulom (suprotan proces od enkripcije):

P = C ⊕ AES(key,CTR)

Dakle, kako bi dekripcija bila moguća, za isti broj iteracije enkripcije i dekripcije koristi se isti keystream.

U ZIP datoteci priloženoj uz zadatak dan je algoritam za enkripciju, cijeli ciphertext te parcijalni plaintext. Proučavanjem ciphertext datoteke vidimo da se ciphertext sastoji od 4160 bajtova (260 blokova), a u plaintext datoteci se nalazi 4138 bajtova. Budući da se jedan blok sastoji od 16 bajtova, možemo zaključiti da imamo cijeli plaintext do 257. bloka (bitno je zapamtiti da brojimo od nule!) , pola 258. bloka, a uopće nemamo 259. blok.

Dakle, moramo pronaći način da dešifriramo 258. i 259. blok ciphertexta.

Kod za enkripciju unutar encrypt.c jest sljedeći:

	AES_EncryptInit(&ctx, key); 
	    
	    
	    unsigned char counter = 0;

	    for (unsigned int offset = 0; offset < (4160); offset += AES_BLOCK_SIZE) { //CTR mode
		unsigned char nonce_xor_counter[AES_BLOCK_SIZE];
		unsigned char enc_output[AES_BLOCK_SIZE];
		for(int i=0;i<16;i++){
		    nonce_xor_counter[i] = nonce[i] ^ counter;

		}
		counter +=1;
		AES_Encrypt(&ctx, nonce_xor_counter, enc_output);

		for(int i=offset;i<(offset+AES_BLOCK_SIZE);i++){ 
		    ciphertext[i] = enc_output[i%16]^plaintext[i];

		}
	    }

	    output("\nEncrypted: 0x", ciphertext, (4160));

Ranjivost implementacije je u tome da se za varijablu brojača (counter) koristi tip podatka char . Char jest veličine bajt, odnosno prima vrijednosti 0-255.

Zbog toga, nakon vrijednosti 255 inkrementiranjem nastaje integer overflow te se vrijednost resetira na 0. To znači da je counter za iteraciju 258/259 zapravo 2/3 što onda znači da je keystream za navedene parove iteracija isti.

Budući da imamo ciphertext i parcijalni plain text, moguće je doći do keystreama po formuli:

C ⊕ P = AES(key,CTR)

U nastavku se prikazuje postupak kojim se dolazi do rješenja, bitno je zapamtiti da brojač počinje od nule!

plaintext[2] ⊕ ciphertext[2] = keystream [2]
keystream[258] = keystream[2] // zbog integer overflowa, keystream kojim se šifrirao 258. blok jednak je onom kojim se šifrirao 2. blok
plaintext[258] = keystream[258] ⊕ ciphertext[258] // ovako dobivamo plaintext 258. bloka

// zatim ponovimo postupak za 259. blok

plaintext[3] ⊕ ciphertext[3] = keystream [3]
keystream[259] = keystream[3] // zbog integer overflowa, keystream kojim se šifrirao 259. blok jednak je onom kojim se šifrirao 3. blok
plaintext[259] = keystream[259] ⊕ ciphertext[259] // ovako dobivamo plaintext 259. bloka

[1] Christof Paar, Jan Pelzl, Understanding Cryptography, Springer-Verlag Berlin Heidelberg, 2009.
[2] https://platforma.hacknite.hr/challenges
[3] Kriptografija i kriptoanaliza, predavanja, FER
[4] Budin, L.; Golub, M; Jakobović, D., Jelenković, L (2010.) (2013.), Operacijski sustavi, Element, Zagreb
[5] https://csrc.nist.gov/csrc/media/projects/cryptographic-standards-and-guidelines/documents/aes-development/rijndael-ammended.pdf