Mit tennél ha kezedben lenne az SHA2 törésének kulcsa?

Fórumok

Kérdés a tárgyban, illetve milyen hatással lenne mindez security világra?

Törés alatt értem, hogy záros határidőn belül (max. pár óra) egy adott pl. sha256-os hash-hez tudsz produkálni egy inputot.

A kérdés apropóját később leírom.

 

Eljött a később, itt az apropó:

A történet 2010-ig nyúlik vissza, Karsten Nohl akkor demózta a GSM A5/1 kódolás törését rainbow tábla segítségével. Csak az összehasonlítás végett, a 64 bites key az akkori számítási kapacitással brute force technikával való törése ha jól emlékszem 100 éves nagyságrendbe esett. Ranbow táblával 2 év precomputing (= rainbow tábla előállítása, csak egyszer kell megcsinálni) mellett, 2TB tárkapacitás felhasználásával 2 percre redukálódott.

Ekkor ástam bele magam a rainbow tábla rejtelmeibe és jött az a megállapításom, hogy a raibow tábla valójában egy két dimenziós bruta force technika, egy pici matekkal megspékelve, ami a dimenziók kezelésre hivatott. Ekkor jött az ötlet, hogy ha van 1 és 2 dimenziós brute force technika, akkor lehet 3, 4, 5, ... n dimenziós is. Számításaim szerint az 1-ről 2 dimenzióra váltás hozza a legtöbbet, de 3-ról 4-re váltás is majdnem annyit hoz, egészen addig amíg a dimenziók száma el nem éri a bitszám felét. Itt ugye a hozamnál már több dolgot kell is figyelembe kell venni, a precomputing időt, a tábla méretét és végső kalkulációs időt.

Amit eddig olvasható, azt ezidáig két emberrel osztottam meg.

Némi matekot végeztem abban az időben, sajnos a doksi egy géphalál következtében elveszett. Amire emlékszem, hogy 256 bit esetén 127 dimenziós táblánál 500 év körül volt a precomputing idő, viszont a tábla méretéből csak annyi maradt meg, hogy összemérhető volt a világ teljes tárolókapacitásával. Na de ez 11 éve volt. Fogalmam sincs mekkora most a globális tárkapacitás, és fogalmam sincs, hogy egy országban, pl. Kínában mennyi van összesen. Arról nem is beszélve, ha minden évben a bevont számítási kapacitás csak 1.5-szöröződik, akkor az az 500 év precomputing 11 év alatt 6-7 évre csökkent. Ja, én a matekot a Karsten Nohl féle gép számítási kapacitásával végeztem, amiben 2db akkori csúcskategóriás ATI kártya tette a dolgát.

Fogalmam sincs jól számoltam e a dolgokat, de - és itt jön a csavar - az egyik beavatott nem oly rég elmondta a kínai főnökének. Pár hónapra rá jött a megkeresés, hogy menjek ki, csináljuk meg, gyakorlatilag végtelen kapacitású szerverfarmot raknak a seggem alá. Több okból is nemet mondtam és alig tudtam levakarni őket, szinte már könyörögtek. Amit nem is értettem, mert alig tudok többet annál mint amit itt leírtam, igazából csak az elvi ötlet érdekelt, a gyakorlati megvalósításhoz kevés vagyok meg nincs is kedven vele foglalkozni.

Mindenesetre a megkeresés azt mutatja, hogy ők is metekoltak valamennyit és lehet reális alapja a dolognak. Sőt, attól hogy én nemet mondtam, lehet már ezerrel dolgoznak rajta. Két dolog kell az egészhez, minél nagyobb számítási kapacitás a feltörni kívát algoritmushoz, ez Kínában az üzemen kívüli BTC farmokon SHA256-ra szinte végtelenül rendelkezésre áll, illetve egy jó matek a dimenziók szelektálásához, amihez szintén nem árt a hardveres támogatás.

Ha belefutottatok ilyen több dimenziós brute force vagy rainbow tábla publikációba, ne tartsátok magatokban. Én nem találtam az elmúlt években.

(Lehet néhány adat nem pontos, 11 éves visszaemlékezés alapján írtam. Valószínűleg nagyságrendi tévedés sehol nincs.)

Hozzászólások

"sha256-os hash-hez tudod produkálni az inputot."

Mármint tudsz produkálni egy inputot...

Amúgy meg nem tudom.

“The trouble with having an open mind, of course, is that people will insist on coming along and trying to put things in it.”

Hát, akkor bele lehetne nyúlni dolgokba. Szakértő csapat és oldja meg a klímaválságot, a top milliárdosok erőforrásaival :D

Mármint, hogy miután valahogy bitcoin milliárdos lettem, mi a második dolog? Asszem a világbéke. Ha jól tudom, akkor a szépségkirálynők is mind ezt akarják, szóval rendelnék belőlük egy tucatot, őőő, tanácsadónak. Aztán jöhet a világbéke projekt. Bár a fene se akar már ilyen gazdagon dolgozni, szóval azt lehet, hogy kiszervezem, és mással végeztetem el. Jó, tudom, nem vagyok egy angyal, ez van. :-)

Mondjuk ha a kezemben lenne, feltételezném hogy nagyon gyorsan más kezében is ott lehet, ezzel kellene valamit kezdeni.

“The trouble with having an open mind, of course, is that people will insist on coming along and trying to put things in it.”

Karikát fűznék rá és a nyakamba akasztanám.

:(

a kvantumszámítógépek korában? kinek nincs?

Egyfelől. Másfelől meg amit én meg tudok törni, azt más is meg fogja tudni és egy ilyen infót nem szabad hagyni, hogy rossz kezekbe kerüljön; akkor már inkább tudjon róla mindenki, hogy védekezni is lehessen ellene.

Megpróbálnék pénzt csinálni belőle. Minél többet.

A "törés" megint azt jelenti, hogy a matematikai 2^n komplexitás helyett mondjuk 2^(n-3)? Mert az nem törés.

Mi lenne "igy"? Egy teoretikus kerdest tett fel (egyelore en nem latok mast). Szoval szamomra ertelmezhetetlen, amikor azt irod:

Nem siklottam el felette, csak nem gondolom hogy így lenne.

 

Van meg egy ilyen a inditoban:

A kérdés apropóját később leírom.

De e sorok irasakor meg nincs leirva az apropo (vagy legalabibs en nem latom).

/sza2

Digital? Every idiot can count to one - Bob Widlar

Ez nem olyan, amire egy delutan alatt ra lehet jonni. Szoval ha valaki elkezd ilyesmivel foglalkozni (feltehetoen egy nagyobb kutatocsoport tagjakent), valoszinuleg mar elore eldonti mit kezdene vele ha megoldana.

When you tear out a man's tongue, you are not proving him a liar, you're only telling the world that you fear what he might say. -George R.R. Martin

Amugy nekem is pont ez jutott eszembe (csak sajnos javitva lett a topic :) ). Ha elo tudom allitani az inputot sha256 alapjan, akkor a mindent (IS) 32byte-ba tomoritoprogramot megcsinalnam belole. :D

Aztan pedig ezt felhasznalva kilepnek a szimulaciobol es feladnek egy bugreportot Az Architectnek. :)

Régóta vágyok én, az androidok mezonkincsére már!

Régen volt, de valami olyasmi rémlik, hogy az egerek rendeltek meg valamit. Az jön ezen gondolkozva csak az agyamba, hogy a nagy számítógépet ami kiszámolja a nagy kérdésre a választ, de tudom, hogy ott humanoidok voltak, szóval az valószínű rossz válasz, hacsak nem az egerek irányították a humanoidokat vagy valami.

De valami hasonló volt.

Feltételezem, hogy szintén Douglas Adams.

disclaimer: ha valamit beidéztem és alá írtam valamit, akkor a válaszom a beidézett szövegre vonatkozik és nem mindenféle más, random dolgokra.

Én asszem, itt már keveredés van... Az Isten kilencmilliárd neve egy Clarke novella, ahol tibeti szerzetesek vesznek egy gépet, hogy kiszámolják Isten összes nevét és amikor sikerül nekik, véget ér a világ, mert az emberiség teljesítette a feladatát. A nagy számítógép, ahol kiszámolja a nagy kérdésre a választ, az ugyan lehet más is, de nekem Asimov Tréfamestere ugrik be, ahol azt a kérdést teszi fel egy tudós a gépnek, hogy honnan van a humor és mi történik, ha ez kiderül, a válaszok meg az, hogy a földönkívüliektől, kísérlet céljából és véget ér a kísérlet, ha ez kiderül. Egyik sem Adams. Az egerest nem tudom.

Én nem erre a kettőre gondoltam, hanem a Galaxis útikalaúz stopposoknak sorozatban van ugye a nagy elme, ami kiszámolja a választ a nagy kérdés, az élet értelme meg minden-re. Ez ugye 42. Jó hosszú ideig számolta, a két csóka, akik meghallják először a választ, berezel, hogy őket most akkor meglincseli a nép. Erre mondja a nagy elme, hogy hát a válasz az tuti jó, csak a kérdés nem volt megfelelően specifikálva. Mondja, hogy ő nem tudja kiszámolni a jó kérdést, de meg tudja tervezni a számítógépet, ami igen. Ez ugye a Föld, amit a kalkuláció befelyezése előtt a vogonok lebontanak valami galaktikus szupersztráda építése miatt.

Na ebben eddig nem szerepelnek egerek, de valahogy az agyam mégis ezzel kapcsolja össze az egereket. Az biztos, hogy az egerek megrendeltek valamit (valami könyvben), de már nem emlékszem, hogy egy bolygót rendeltek, vagy a Földet, ami bolygó is és a nagy számítógép is, vagy esetleg keverek valamit.

Na jó, gyors Google keresés talált egy idézetet, és úgy tűnik, az agyam okosabb mint én :-D

“The mice were furious."
[...]
"Oh yes," said the old man mildly.
"Yes well so I expect were the dogs and cats and duckbilled platypuses, but..."
"Ah, but they hadn't paid for it you see, had they?"
"Look," said Arthur, "would it save you a lot of time if I just gave up and went mad now?"
[...]
"Earthman, the planet you lived on was commissioned, paid for, and run by mice. It was destroyed five minutes before the completion of the purpose for which it was built, and we've got to build another one."
Only one word registered with Arthur.
"Mice?" he said.
"Indeed Earthman."
"Look, sorry - are we talking about the little white furry things with the cheese fixation and women standing on tables screaming in early sixties sit coms?"
Slartibartfast coughed politely.
"[...] These creatures you call mice, you see, they are not quite as they appear. They are merely the protrusion into our dimension of vast hyperintelligent pandimensional beings. The whole business with the cheese and the squeaking is just a front."
The old man paused, and with a sympathetic frown continued.
"They've been experimenting on you, I'm afraid.”

Douglas Adams, The Hitchhiker's Guide to the Galaxy

disclaimer: ha valamit beidéztem és alá írtam valamit, akkor a válaszom a beidézett szövegre vonatkozik és nem mindenféle más, random dolgokra.

Szerkesztve: 2021. 11. 10., sze – 00:26

amire ez megvalosul mar sha9-et fogunk hasznalni kb

amugy azzal, hogy tudsz hozza generalni egy inputot meg nem mesz sokra. lasd md5...  max ilyen file checksumnal lehetne trukkozni vele, felteve hogy a generalt inputodnak legalabb az eleje tetszoleges lehet (pl. egy malware file). de fontos dolgokon mar most is tobbfele checksum van, amiket egyidoben kb lehetetlen atverni. es semeddig nem tart atterni sha3-ra vagy barmi masra, ha ez megis bekovetkezne.  ssl/ipsec eseten meg nem sokra mesz a tetszoleges inputoddal.

es nem veletlen leteznek mar most is post-quantum crypto algoritmusok, mert arra nagyobb az esely, hogy hamarosan az osszes regi cryptot sok nagysagrenddel gyorsabban fogjak tudni torni quantum gepekkel. de mar most a kritikusabb helyeken ezt is kivedik, pedig ma meg nem is lehetseges (vagy nem tudunk rola).

Az egy fegyver lenne a kezemben ha tudnék inputot produkálni. Hogy mit tennék? Megvenném az egész világot kilóra! Kim Jong Un lenne a testőröm, Putyin a legfőbb tanácsadóm, Orbán Viktor az építészem, Gyuri báttyánk meg a bankárom! A bankom székhelyét Schweiz-ból Izraelbe költöztetném mert azoknak a pénz az Istenük és a vagyonomat meg tudnák többszörözni! Aztán felébredtem és bilibe lógott a kezem... :-)

Mit értesz a rainbow táblánál a dimenzió alatt? 

Ezt csak egy példával tudom megvilágítani.

Vegyünk egy 12 bites számot. Ezt 1D-s brute force módszerrel 4096 próbálkozásból tudod megfejteni. 2D-s módszerrel létrehozol egy 64x64-es táblát (ez a rainbow tábla), melyben az implementált matek segít eldönteni, hogy először melyik oszlopban van a keresett szám, aztán az adott oszlopon belül melyik sorban. Így max. 128 próbálkozásból meg van a keresett szám. 3D-s táblánál létrehozol egy 16x16x16-os táblát. Ebben - a 2D-s módszer analógiájából belátható, hogy - 48 próbálkozás után megvan a keresett szám.

Sajnos nem vagyok otthon a rainbow táblákban, de nem értem ez miért jobb, mint a bináris keresés egy rendezett táblában. Én a leírás alapján azt gondoltam, hogy a dimenziók növelése csökkenti a tábla méretét. Viszont a 64x64 is 4096, akár a 16x16x16 is 4096-ot ad. Mert egy 2^256 elemű táblát tárolni, kiszámolni, egyelőre reménytelennek tűnik.

Tehát ki kell számolni a 2^256 elemet? Mert az jelen technikával tárolhatatlan, és még nagyon sok nagyságrend hiányzik hozzá.

Ezt találtam legfrissebbnek: https://www.storagenewsletter.com/2020/05/14/total-ww-storage-data-at-6…

A jelenleg tárolt adat 2^73 byte körül van, nagyon messze még a 2^256-tól (és egy elem sem egy byte, de azt már el is hanyagolhatjuk).

A trükk az hogy nincs minden tábla fullra kitöltve, hanem az első találattól függ a következő keresés. Így nem kell 1 db gépen tárolni az eredényt, tehát nem kell 1 egybefüggő adattároló, innentől meg csak a pénz és az IPV6 címmező a határ. 

Nincs tárolva a teljes tábla. A fenti 2D-s példát alapul véve - a minimális táblaméret a 16 oszlop matekkal kiszámolt speciális checksum-a, melyből eldönthető, hogy az adott oszlopban van e keresett szém. Ha van találat akkor kerül kibontásra teljes oszlop.

A rendelkezésre álló erőforrás alapján lehet balanszírozni a minimális 16, illetve a maximális 4096 db letárol érték között.

Na ennek megértése nekem is problémát okozott és 11 év távlatából már nem is tudom elmagyarázni. Viszont van a YT-n egy videó, amiben elhangzik, hogy a matek gyakorlatilag majdnem mindegy. A "majdnem mindegy"-et úgy kell érteni, hogy szinte független a feltörni kívánt algoritmustól, a tábla kezelésére kell összpontosítani a matekkal, főleg ha tudsz mögé tenni hardver támogatást. Annak idején példákból értettem meg.

Néhai: ugye nem miattad nem tudok ákciós mikrót rendelni a hülyeazértnemvagyoktól? :D

" egy pici matekkal megspékelve, ami a dimenziók kezelésre hivatott"

Ezt nem vágom. Nem pont ez egy jó hash algoritmus ismérve, hogy egy bitnyi változtatás is lavinaszerű hatást indít el, és végül nem megtippelhető, hogy a megoldás melyik szektorban lesz?

Erdemes megnezni a SHAttered oldalat hogy ok mit csinaltak anno + milyen implikacioi voltak amikor a SHA1-gyel sikerult ugyanez: https://shattered.io valszinu SHA-2-vel ugyanez lenne pepitaban, mert sokszor a SHA1-re a SHA2 volt a valasz.