This is an old revision of the document!
Tiny Encryption Algorithm (TEA) je jednostavan simetrični enkripcijski algoritam izumljen 1994. Iako je otporan na brojne vrste kriptoanaliza, zbog nekih svojih svojstava se ne smije koristiti u hash funkcijama.
PRIMJER -Zadatak s Hacknite platforme - Ultrasecure Hash
Mirjana je osmislila novi hash algoritam koji se brzo izvodi i zauzima jako malo prostora. Zna koliko je bitno testirati algoritme prije nego što ih se stavi u proizvod, pa te moli da testiraš postoje li praktični napadi protiv njega, konkretno za jako je bitno da algoritam nije ranjiv na "second preimage" napad (https://en.wikipedia.org/wiki/Preimage_attack) . Dostupna ti je implementacija algoritma u pythonu, a na njezin se servis se možeš spojiti naredbom: nc chal.platforma.hacknite.hr 13012 ako koristite Linux odnosno telnet chal.platforma.hacknite.hr 13012 ako koristite Windows
Cilj zadatka je izvesti second preimage napad nad algoritmom. Second preimage napadom se pronalazi par inputa koji rezultiraju istim outputom:
- hash(x1) = y
- hash(x2) = y
Pronalazak rješenja jest zapravo vrlo jednostavan jednom kada se sazna da je riječ o TEA algoritmu (Tiny Encryption Algorithm). Do te informacije se može doći pomoću dijela koda:
DELTA = 0x9E3779B9
Pretragom te DELTA vrijednosti, moguće je pronaći brojne primjere koda koji implementiraju TEA.
Ključan dio koda jest sljedeći:
v0, v1 = constants[0], constants[1] k0, k1, k2, k3 = k sum_val = 0 for _ in range(32): sum_val = (sum_val + DELTA) & 0xFFFFFFFF v0 = (v0 + (((v1 << 4) + k0) ^ (v1 + sum_val) ^ ((v1 >> 5) + k1))) & 0xFFFFFFFF v1 = (v1 + (((v0 << 4) + k2) ^ (v0 + sum_val) ^ ((v0 >> 5) + k3))) & 0xFFFFFFFF v = hex(v0).split("0x")[1]+hex(v1).split("0x")[1] v = v.zfill(16) return v
k0,k1,k2 i k3 su 32-bitni dijelovi inputa koji je uvijek duljine 16 bajta (padding u slučaju da nije).
Runde TEA algoritma mogu biti opisane sljedećim pseudokodom (runde su iteracije):
Yi+1 ← Yi + Fi(Zi, K0, K1); Zi+1 ← Zi + Fi(Yi+1, K2, K3);
a opis F funkcije:
Fi(z, k, k′) = (ShiftLeft(z, 4) + k) ⊕ (z + Ci) ⊕ (ShiftRight(z, 5) + k′)
gdje bi Y i Z varijable odgovarale v0 i v1.
Ranjivost algoritma proizlazi iz F funkcije s obzirom da se radi o operacijama zbrajanja i xoranja. Sjetimo se da je cilj zadatka pronaći dva inputa koja daju isti output. Kada bi se funkcija navela da su outputi na svakoj iteraciji “i” jednaki za oba ključa (odnosno varijable v0 i v1), output sveukupne hash funkcije bi također bio isti. S obzirom da je output isti u svakoj iteraciji član (z + Ci) se može zanemariti. Ci je sum_val koji ne ovisi o inputu, a z jest v0/v1 koji se mijenjaju s obzirom na output funkcije F, ali jer smo outpute funkcije F fiksirali na iste vrijednosti u oba slučaja po iteraciji, one se isto mogu gledati kao konstante (od nulte iteracije počinju od iste vrijednosti). Isto se može primijeniti i na ShiftLeft i ShiftRight funkcije. Stoga gledamo sljedeću funkciju:
Fi(z, k, k′) = (const1 + k) ⊕ (const2 + k')
Može li se izmjenom barem jednog bita u “k” ili “k'” na poziciji “n” funkcija navesti da vrati jednaku vrijednost (neovisno o vrijednostima const1 i const2) kao i s originalnim vrijednostima “k” i “k'”. Izmjenom bita očito je da će operacija zbrajanja uvijek dati drukčiji rezultat, stoga to mora biti moguće kroz operaciju xor. Na poziciji “n” gdje je bit izmijenjen operacijom zbrajanja, na ekvivalentoj poziciji u drugom članu se također mora izmijeniti bit kako bi xor ostao isti. Međutim, zbrajanje na razini bitova ima tranzitivno svojstvo, odnosno prijenos. Ako se bit izmijeni može nastati (ne)prijenos i time izmijeniti sljedeći bit. Hoće li se prijenos dogoditi ovisi o vrijednosti const1/const2 na poziciji n. Ukoliko je na poziciji “n” unutar const1/const2 postavljena jedinica, izmjenom “k” ili “k'” na poziciji “n” će stvoriti prijenos ako je 0 izmijenjena u 1 te se neće dogoditi prijenos ako je 1 izmijenjena u 0. U oba slučaja izmijeni se i bit (ili više njih) na višim pozicijama što onda treba biti popraćeno i u drugom članu xor operacije. S obzirom da se const vrijednosti dinamički mijenjaju kroz iteracije, ne može se predvidjeti kada će se 1 pojaviti na izmijenjenoj poziciji (odnosno može jer nam je dan “flagflagflagflag” kao ključ, te bi bilo potrebno naći poziciju za oba člana u funkciji F na kojoj se pojavljuje jednaka duljina niza bitova 1 po svakoj iteraciji što za ovaj ključ nije slučaj). Svejedno, problem se može zaobići na vrlo jednostavan način. Prijenos se ne događa na najvišem bitu. Stoga, ako se bitovi na najvišoj poziciji izmijene unutar oba ključa “k” i “k'”, ne moramo se brinuti o prijenosu te će rezultat xor operacije vratiti istu vrijednost kao i u originalnim vrijednostima “k” i “k'”.
Imajući navedeno na umu, zadatak ima 3 rješenja. Komplementiraju se najviši bitovi u “k0” i “k1”, u “k2” i “k3” ili oboje.