Differences

This shows you the differences between two versions of the page.

--- tea [2025/01/22 11:52] – lss
+++ tea [2025/12/01 11:40] (current) – external edit 127.0.0.1
@@ Line 9: / Line 9: @@
 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,
+pa te moli da testiraš postoje li praktični napadi protiv njega.
-konkretno za jako je bitno da algoritam nije ranjiv na "second preimage"
+Konkretno jako joj je bitno da algoritam nije ranjiv na "second preimage"
 napad (https://en.wikipedia.org/wiki/Preimage_attack) .
@@ Line 25: / Line 25: @@
   - hash(x2) = y
+Konkretno potrebno je pronaći unos koji nije jednak vrijednosti "flagflagflagflag", a koji daje istu hash vrijednost.
 Pronalazak rješenja jest zapravo vrlo jednostavan jednom kada se sazna da je riječ o
@@ Line 32: / Line 33: @@
 Pretragom te DELTA vrijednosti, moguće je pronaći brojne primjere koda koji implementiraju TEA.
-U kodu se koristi TEA kao hash algoritam tako da se konstantne vrijednosti "0x123456789" i "0x9ABCDEF0" šifriraju s našim unosom koji se koristi kao ključ (sličan "hash" algoritam se koristio i u Xbox konzoli).
+U kodu se koristi TEA kao hash algoritam tako da se konstantne vrijednosti "0x123456789" i "0x9ABCDEF0" šifriraju s našim unosom koji se koristi kao ključ (sličan "hash" algoritam se koristio i u Xbox igraćoj konzoli).
-Istraživanjem javno poznatih napada na TEA algoritam, moguće je pronaći [znanstveni rad [https://www.schneier.com/wp-content/uploads/2016/02/paper-key-schedule.pdf]]
+Istraživanjem javno poznatih napada na TEA algoritam, moguće je pronaći [[https://www.schneier.com/wp-content/uploads/2016/02/paper-key-schedule.pdf|članak]] koji kaže kako TEA ima ranjivost povezanih ključeva (za bolje razumijevanje ranjivosti, preporučuje se pročitati članak). To znači da mogu postojati različiti enkripcijski ključevi koji za isti plaintext daju isti ciphertext. U članku je objašnjeno da se takav par povezanih ključeva (ključ je uvijek iste dužine, 128 bitova, odnosno 4 32-bitne riječi) može konstruirati na tri načina, tako da se napravi "bit-flip" na najvišem bitu prve i druge 32-bitne riječi ključa, najvišem bitu treće i i četvrte 32-bitne riječi ključa ili bit flip najviših bitova svih četiriju 32-bitnih riječi ključa. Ova ranjivost se može iskoristiti kako bi se zavarao hash algoritam implementiran u zadatku, budući da se naš unos zapravo koristi kao ključ u TEA algoritmu.
+Tekst "flagflagflagflag" u binarnom zapisu glasi:
+<file>
+01100110 01101100 01100001 01100111
+01100110 01101100 01100001 01100111
+01100110 01101100 01100001 01100111
+01100110 01101100 01100001 01100111
+</file>
+Bit-flipom najviših bitova svih 32-bitnih riječi dobivamo:
+<file>
+11100110 01101100 01100001 01100111
+11100110 01101100 01100001 01100111
+11100110 01101100 01100001 01100111
+11100110 01101100 01100001 01100111
+</file>
+Zadatak prihvaća tekst u base64 kodiranom formatu, pa možemo koristiti [[https://gchq.github.io/CyberChef/#recipe=From_Binary('Space',8)To_Base64('A-Za-z0-9%2B/%3D')&input=MTExMDAxMTAgMDExMDExMDAgMDExMDAwMDEgMDExMDAxMTEgMTExMDAxMTAgMDExMDExMDAgMDExMDAwMDEgMDExMDAxMTEgMTExMDAxMTAgMDExMDExMDAgMDExMDAwMDEgMDExMDAxMTEgMTExMDAxMTAgMDExMDExMDAgMDExMDAwMDEgMDExMDAxMTE|CyberChef recept]] da dobijemo vrijednost potrebnu za rješavanje zadatka.
-Ključan dio koda jest sljedeći:
+Zadatak pokazuje kako je bitno istražiti javno poznate napade na kriptografske algoritme, budući da je često moguće uspješno izvesti napad i bez matematičkog razumijevanja ranjivosti.
-<code python>
-	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
-</code>
-TODO: ovdje opisati kako se može riješiti na script kiddie način
-TODO: Nakon tog objasniti zašto to radi
-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.