Shattered: Az első SHA1 ütközés

HUP cikkturkáló

We have broken SHA-1 in practice.
This industry cryptographic hash function standard is used for digital signatures and file integrity verification, and protects a wide spectrum of digital assets, ranging credit card transactions, electronic documents, open-source software repositories and software updates.
It is now practically possible to craft two colliding PDF files and obtain a SHA-1 digital signature on the first PDF file which can also be abused as a valid signature on the second PDF file.
For example, by crafting the two colliding PDF files as two rental agreements with different rent, it is possible to trick someone to create a valid signature for a high-rent contract by having him or her sign a low-rent contract.

https://shattered.it/
https://security.googleblog.com/2017/02/announcing-first-sha1-collision…

  • 2593 megtekintés

( Caro | 2017. 02. 23., cs – 21:31 )

Tök jó, épp nemrég az SHA-1-et választottam egy projekthez, mondván az annyira biztonságos :D

Bár ez a pdf dolog nekem sántít. A fájlok mérete egyforma? Amúgy egy újabb érv, hogy lényeges információt csakis plaintextben továbbítunk. Na azt azért nehezebb lesz megtörni :)

( zwt | 2017. 02. 23., cs – 21:40 )

akkor mindenki törheti fel az adóbevallásokat mostmár :D

> sha512sum *.exe
5eea230f43ca237c29fc87ebee48a486c5e4de5b932f410f5304717803ad1bbe0be962e70d2629226c4ec854eb8da9aa485d55eac51bb6de2d0404a75bbedf6e sample1.exe
5eea230f43ca237c29fc87ebee48a486c5e4de5b932f410f5304717803ad1bbe0be962e70d2629226c4ec854eb8da9aa485d55eac51bb6de2d0404a75bbedf6e sample2.exe
>

( hajbazer v | 2017. 03. 08., sze – 14:41 )

A matematika skatulya elvét figyelembe véve, mindig generálható lesz ütközés olyan algoritmusoknál, melyek kevesebb bájton szeretnének reprezentálni, vagy egyediesíteni egy sokkal több bájtot tartalmazó fájlt. Kellően jó brute force algoritmus és magas számítási kapacitás kell hozzá.

-- https://betanews.com/2017/02/23/sha-1-collision-google/

  • Nine quintillion (9,223,372,036,854,775,808) SHA1 computations in total
  • 6,500 years of CPU computation to complete the attack first phase
  • 110 years of GPU computation to complete the second phase

Tehát, a Google ezt a saját erőműveivel oldotta meg, gondolom azért, hogy 1) megnyerje az elméleti csatározást, hogy miért tiltotta ki a Chrome-ból az SHA1-et (nehogy véletlenül el kelljen ismerniük, hogy feleslegesen, csak azért, hogy ők tüntessék fel magukat a legbiztonságosabbnak), 2) később majd elterjeszthessen valami saját eljárást, amivel növeli a saját marketing értékét. Megnézem majd, egy hacker botnet mikor fog egy ilyet kiszámolni.

A skatulyaelv igaz, de valamit még vegyél figyelembe. Ha a hash értékkészlete jóval nagyobb, mint az emberiség által valaha előállított összes adathalmaz számossága, akkor nincs gond avval, hogy kevés biten van reprezentálva. Már az SHA1-nél is csillagászatilag kevés az esélye egy véletlen ütközésnek. A direkt ütközés ellen kétféle védelem van, egyrészt több bit (nagyságrendekkel gyorsabban növekszik, mint az emberiség teljes számítási kapacitása), másrészt okosabb algoritmus (ami kizár minden trükközést és csak a brute force marad, az SHA1-ben konkrét gyengeséget találtak, ami miatt a brute force-nál sokkal gyorsabban törhető). Tehát igenis van helye a hashnek és az elvi ütközés lehetősége a gyakorlatban nem igazán számít, ha kellőképpen kicsi.

A Google számítási kapacitása valóban elég nagy. De egyrészt gondolj bele, hogy a Google szolgáltatásai nem álltak le X időre az SHA1 támadás alatt, tehát a teljes kapacitás töredéke elég lehetett a támadáshoz. Másrészt abba is gondolj bele, hogy milyen gyorsan növekszik a felhős iparág és a számítási kapacitás, ha a Google meg tudta csinálni most, másoknak is hamarosan megérheti, akár bérelt infrastruktúrán. Egy ilyen majdnem praktikus támadás valóban az SHA1 végét jelenti és ezt már tudták pár éve is.

--

Az, hogy a hash függvény tökéletes, az azt jelenti, hogy brute-force-szal lehet csak hash-ütközést találni: minden esetben annyi féle inputot kell végigvizsgálni, amekkora a hash mérete. Ezt jelenti a kriptográfiailag biztonságos hashfüggvény. A hashfüggvény sosem lesz bijekció, nem is lehet az. Viszont kritpgráfiailag tökéletes lehet.

Például egy 160 bites hashnél (SHA-1) 2^160-on különböző inputot kelljen kipróbálni hash ütközéshez. Ekkor persze természetesen mindig is lesz ütközés, a skatulyaelv miatt.

És egy hashfüggvény törése meg azt jelenti, hogy találnak egy olyan módszert, amelynél jóval kevesebb próbálkozásból biztosan található ütközés.
Például az SHA-1 esetében 2^63.1 input elegendő a biztos ütközéshez. Ez pedig jóval kevesebb, mint a 2^160-on. Na, ezért van megtörve az SHA-1.

"Már az SHA1-nél is csillagászatilag kevés az esélye egy véletlen ütközésnek."
Nem, pont ezt bizonyítja be a törés. A 2^160-on különböző input helyett valójában 2^63-on különböző input elég, azaz az SHA-1 valódi hashmérete kevesebb, mint 64 bit. És ez azért már nem éppen a biztonságos szint.

Én úgy értettem ezt a támadást, hogy nagyon specifikus bitsorozatnak kell lennie az inputban ahhoz, hogy működjön, és ilyen a valós használat közben kb. sose fordul elő (ezért tudják pl. a támadást detektálni, sőt tiltani). Pont azt írtam, hogy a véletlen ütközés esélye nem lett kisebb, csak a szándékos ütközésé.

--

Viszont aki hasht akar törni, az szándékos ütközést akar csinálni. A véletlen ütközés mindig is ugyanakkora fog maradni, a hash mérete nem változott meg :D

Attól jó egy hash, ha a szándékos ütközés pont annyira valószínű, mint a véletlen ütközés.
Mivel ez nincs így az SHA-1nél, az rossz hash.

Linust pl. a gittel kapcsolatban szinte csak az érdekli :).

Mondok jobbat és konkrétabbat. Van egy backupom a felhőben, és SHA1-el van indexelve, ebből gyorsan kiderül, hogy ha egy fájl át lett helyezve vagy módosult. Csak én férek hozzá, és csak megbízható tartalmat töltök fel. (A netről letöltött SHA1 ütköző PDF-eket letöltöttem, de töröltem is, nincs rájuk szükségem.) Milyen támadástól kellene tartanom? Csak akkor van baj, ha két különböző fájl véletlen azonos SHA1-el rendelkezik. Bízok benne, hogy nem fog, és nekem ez így jó. Sőt, ha ezt dobozos termékként árulnám másnak, akkor se lenne gond vele. A git határeset, részben egyet értek a Linus-féle érveléssel, részben nem.

--