mboost-dp1

unknown

SHA1 algoritmen er brudt

- Via Comms Design - , redigeret af Pernicious

På baggrund af en endnu ikke frigivet artikel fra tre forskere fra Shandong Universitetet i Kina, mener bl.a. Bruce Schneier, Ronald Rivest og Adi Shamir, at SHA1 (Secure Hash Algorithm) nu er brudt.

De kinesiske forskere har brudt SHA1 med langt færre beregninger, end man hidtil har troet muligt. Dog mener bl.a. Shamir og andre kryptografer, at der ingen grund er til panik, men at nye produkter ikke bør bruge SHA1.

SHA1 er meget anvendt til digitale signaturer. Det er f.eks. den algoritme, som TDC anvender, ligesom mange kreditkort-transaktioner beskyttes med den.

Udtalelsen fra Ronald Rivest og Adi Shamir kan ses her (under Tuesday Panel Discussion).





Gå til bund
Gravatar #1 - ethereal
17. feb. 2005 10:37
Det er vildt. Man kan ikke føle sig sikker mere... Kontanter, se det er sagen :D
Gravatar #2 - tvinter
17. feb. 2005 10:48
offtopic: synes newz.dk er lidt langsom for tiden.. comon.dk har overhalet jer en del gange ;)
Ontopic: Det er da lidt sygt, men helt ærligt? hvormange bruger den digitale signatur? og nu skal vi så lige se på at det er 3 mand der kan bryde den.. 3 mand og hele verden er rystet ;) sygt...
Gravatar #3 - tvinter
17. feb. 2005 10:49
offtopic: synes newz.dk er lidt langsom for tiden.. comon.dk har overhalet jer en del gange ;)
Ontopic: Det er da lidt sygt, men helt ærligt? hvormange bruger den digitale signatur? og nu skal vi så lige se på at det er 3 mand der kan bryde den.. 3 mand og hele verden er rystet ;) sygt...
Gravatar #4 - unkle
17. feb. 2005 10:51
Hehe... Det er altid godt at se når der er nogle entusiastiske mennesker der kan skabe lidt røre i andedammen så vi kan få højnet sikkerheden... ;)
Men at snakke om at "bryde" algoritmen er da lidt spøjst. SHA1 er jo "one-way" og kan bruges til at skabe en checksum, men det er selvfølgelig uheldigt hvis det virkelig kan lade sig gøre at ændre kilde-data på en sådan måde at man kan kompensere og bibeholde den oprindelige checksum.
Gravatar #5 - nomicbajs
17. feb. 2005 10:59
Neeeeeej!!!!! hele mit liv er baseret på SHA1 algoritmen!! :D
Gravatar #6 - Lobais
17. feb. 2005 11:04
Nogen, der ved om gpg er bygget på SHA1?
Gravatar #7 - sguft
17. feb. 2005 11:06
#3: offtopic: newz.dk er afhængig af nyhedsmedier som comon.dk så det er vel ikke så underligt ?

ontopic: En hel del mennesker bruger den digitale signatur, ifølge flere medier var der tale om 200.000 udstedte signaturer pr. 1 juni 2004 (nyeste optælling jeg lige kunne finde) og mon ikke det tal er steget lidt mere i løbet af de sidste 7 måneder.

"3 mand og hele verden er rystet"
Det er forskere der offentliggør resultaterne indenfor kort tid og således er det ikke længere blot tale om "3 mand" der kender til teknikken bag.

Desuden er der ingen grund til panik, den her nyhed sætter det lidt i perspektiv:

http://www.comon.dk/index.php/news/show/id=21173

Der er altså ikke tale om at den er decideret knækket, blot at man har fundet en metode der kræver færrer beregninger end hidtil antaget.
Gravatar #8 - guppy
17. feb. 2005 11:08
Uhm... algorithmen er altså ikke brudt, de kinesiske forskere har bare fundet en måde at reducerer antallet af kombiniationer man skal igennem for at skabe en kollision - det vil dog stadigt tage på den forkerdte side af 100 år for en privatperson at gå dem igennem...

[edit]nå det var der så også andre der nåede at skrive inden jeg fik trykket "gem" [/edit]
Gravatar #9 - Webmonkey
17. feb. 2005 11:12
#1 Kontanter er da det der er nemmest at frarøve folk.....
Gravatar #10 - raz0
17. feb. 2005 11:29
Nok er algoritmen blevet brudt, men det er altså ikke noget at råbe vagt i gevær over - endnu i hvert fald.

Ifølge denne artikel vil det tage 2^69 hash udregninger at finde en kollision. Hvis man vil bruge god gammeldags brute-force vil det tage 2^80 hash udregninger, hvilket selvfølgelig er væsentlig mere. Vi taler dog stadig om 590.295.810.358.705.651.712 (2^69) hash udregninger, hvilket ikke er noget man kan udregne på et par timer, nogle dage eller nogle måneder (read: århundrede på alm. PC?).

For at komme ned på 2^80 udregninger ved brute-force og 2^69 med brudet, har man endvidere anvendt fødselsdags paradokset. Dette betyder, at man nok kan finde to stykker data med samme hash, men man kan ikke finde en kollision til et stykke vilkårligt data. Med brute-force vil man derfor, for at finde en kollision til f.eks. et password, skulle bruge 2^160 udregninger i stedet - måske mindre med brudet. Man kan altså ikke bruge det til at bryde passwords.

Det er dog stadig et problem for digitale signature. En person kan nemlig underskrive et stykke data, og så sende et andet med samme signatur afsted. Man kan altså ikke være sikker på at det oprindelig dokument ikke er modificeret.

Det er dog uvist om andre typer angreb vil dukke op som følge af brudet. Hvis man laver en ny applikation, bør man nok se sig om efter en anden hashing algoritme.
Gravatar #11 - MNM
17. feb. 2005 11:29
SHA1 er på ingen måde usikker, det kræver stadig 590295810358705651712 (2^69) forsøg at finde 2 værdier med samme hash.

Gad vide om SHA512 entenlig er mere sikker?
Gravatar #12 - Cutepuppy
17. feb. 2005 11:29
#2

Nu er det jo primært brugere der sender nyheder ind, så du kan jo spørge dig selv hvorfor du ikke gjorde det når du nu så nyheden på comon.
Gravatar #13 - SmackedFly
17. feb. 2005 11:33
#11

Kommer an på hvad du bruger SHA1 til, til digitale signaturer er den blevet usikker, til one-way hash encryption er den blevet et par millioner gange hurtigere at bryde, men ikke noget der betyder noget for almindelige menneskers brug af den.
Gravatar #14 - guppy
17. feb. 2005 11:34
#11 SHA-2 ( SHA128, SHA512, mm ) baserer sig på samme algorithme, de er bare XXX bits længre
Gravatar #15 - MortenDahl
17. feb. 2005 12:23
#2 Som poster af nyheden, så vil jeg sige det er fordi nyheden skal godkendes at det går "så langsomt". Jeg indsendte den igår (d. 16.) umiddelbart efter kl 18.
Gravatar #16 - MortenDahl
17. feb. 2005 12:27
En lille sidebemærkning: rart at se at comon har haft fat i Lars Knudsen, og ikke en tilfældig "ekspert". Måske de efterhånden har lært det..
Gravatar #17 - ChrashOverride
17. feb. 2005 13:07
#2
ja ville du ikke også ryste lidt i bukserne hvis du sad i danske bank og havde brugt 2 mil på en kryptering som du regener for noget af det mest sikker i verden og nu er der så en der har brudt denne algorythme, og du ved ikke om han har frigivet sine formler eller om han holder dem hemmelige men før eller siden kommer de jo nok ud.
Og der er ikke nogle nye afløser endnu..
Gravatar #18 - MortenDahl
17. feb. 2005 13:26
#17 der er en flok afloesere, men problemer er nok om de eksisterende systemer kan skifte over uden problemer.
Se f.eks. SHA2 (256, 384 og 512), WHIRLPOOL, TIGER, RIPEMD og Knudsen naevner (paa comon) ogsaa en SMASH.
Gravatar #19 - mrmorris
17. feb. 2005 13:29
#15 Ja jeg må indrømme, jeg kommer kun på newz.dk (og er holdt op med at indsende) pga. diskussionerne, forstår ikke helt man på et nørd-site ikke er mere åben for forbedringer og samarbejde brugerne imellem, i stil med Wikipedia's politik.
Gravatar #20 - ldrada
17. feb. 2005 23:18
*Blip* Jeg er fatløs.
Hvorfor skulle folk gå i panik? Hvorfor er SHA1 nu lige pludselig "usikker"?
Som én nævnte på SecurityFocus' BugTRAQ, vil jeg også nævne det her - Hvorfor kræver vi egentlig kollisionssikkerhed af vores hashing algoritmer?
Gravatar #21 - Klok
18. feb. 2005 07:00
Her er lige et lille udrag fra Jonathan G. Lampe [[email protected]]'s mail til [email protected]:
*****************************
If I am eyeballing this correctly, this makes the "cracked" SHA-1 just a little tougher (32x) than MD-5 was thought to be (2**64 operations) before MD5 was cracked. (I believe, and I could be wrong, that MD5 is now considered to be 2**42 operations strong; one of the papers referenced below suggests the "1 hour IBM" MD5 crack was performed at a 2**25 operation level of difficulty which would only be possible with some
additional knowledge.)

Again, if I am eyeballing this correctly, SHA-1 is still currently 134,217,728x more secure than MD5. Before the SHA-1 announcement, SHA1 was thought to be 274,877,906,944x more secure than MD5, and originally, SHA-1 was thought to be just 65,536x more secure than MD5. (MD5 has been "more cracked" than SHA-1 in recent months.)
*****************************
IMO: Det er nok lidt voldsomt at kalde det "brudt" !
Gravatar #22 - mrmorris
18. feb. 2005 07:59
#21 Det er muligvis en voldsom overskrift på emnet, selv en gammel CRC32 mapper til over 4.3 mia kombinationer.

"This break of SHA-1 is stunning," said Ronald Rivest, a professor at MIT who co-developed the RSA algorithm with Shamir. "Digital signatures have become less secure. This is another reminder that conservatism is needed in the choice of an algorithm," added Rivest at the panel session."

...hvis det nu ligepludselig er muligt ved en smart algoritme og brute-force at generere et dokument med samme SHA1 hash inden for en overskuelig tid (et par døgn?!), så er problemet jo reelt nok set i lyset af hvor mange hvis forretningsgang er afhængig af pålideligheden af denne hashing.
Gravatar #23 - Pally
18. feb. 2005 08:07
#22 mrmorris (og andre)
Det er blevet lettere at lave et dokument med samme SHA-1; men derfra og så til at lave et meningsfyldt dokument med samme SHA-1 er der lang lang vej.
Gravatar #24 - mrmorris
18. feb. 2005 08:15
#23 Tja, men hvis nyheden skal give mening (og forskere fra MIT må regnes som troværdige kilder) så ville jeg tro ideen så er at have et "payload area" hvor man ud fra det eksisterende hash (på den falske fil) kan generere et "payload area" som vil bringe hele files hash til at matche den oprindelige.
Gravatar #25 - ChrashOverride
18. feb. 2005 08:23
Det minder mig lidt om dengang for en snes år siden at det Amerikanske Pentagon sage at "de havde et ubrydeligt sikkerheds system til deres ICBMs som ikke kunne brydes" hvor efter en knægt i tysk land hackede dem stjal koderne og sende koderne til dem på en af deres FAX maskiner som slet ikke eksisterede, nu eksistere han(drengen fra tyskland) så ikke længere, men pentagon har da lært af deres fejl :)
Gravatar #26 - PaNiX
18. feb. 2005 08:33
Det er jo ganske tydeligt for mig.

At finde 2 identiske beskeder vil tage lang tid (et hurtigt bud - 10+ år)... og selv der er det jo ikke sikkert at begge beskeder giver mening.

Den bedste måde at lave et identisk hash hurtigere er stadig den samme: Held! Du skal bare gætte indholdet første gang :-)
Gravatar #27 - mrmorris
18. feb. 2005 08:42
#25 Lyder som en film. Har du et link?!
Gravatar #28 - Pally
18. feb. 2005 10:20
#24 mrmorris
Øh? Den linkede artikel er ikke speciel konkret, det er en 3 siders pdf fra de 3 kinesere jeg har set heller ikke. Hvis du har et mere detaljeret link, så vil jeg meget gerne læse det.

Men jeg er usikker på om de 2^69 beregninger gi'r én kollision eller en familie af kollisioner (de 3 kineseres pdf viser bare to eksempler på kollisioner). Hvis der er tale om én kollision er sandsynligheden for at den er meningsfyldt (og endda så meningsfyldt at den kan udnyttes) stadig uhyre lille.
Gravatar #29 - mrmorris
18. feb. 2005 10:42
Ifølge The Register drejer det sig kun om 2^33 beregninger men yderligere detaljer skulle blive frigivet snarest. Brudt eller ej, nyheden er dog nok til at NIST vil udfase SHA-1 til fordel for SHA-256/512. (http://www.theregister.com/2004/08/19/hash_crypto/)
Gravatar #30 - Pally
18. feb. 2005 10:48
#29 mrmorris
Fuld 80-step SHA-1: 2^69 hashes (mod 2^80 tidligere)
58-step SHA-1: nu mindre end 2^33 hashes
Fuld SHA-0: nu mindre end 2^39 hashes

Men ja, SHA-1 skal da udskiftes men det behøver ikke at være hen over weekenden eller inden påske :)
Gravatar #31 - ks
18. feb. 2005 23:33
Selv om der stadig skal 2^69 operationer til at finde en kollision - så er alvorligheden af angrebet at: 2^80 reduceret til 2^69 .. med procent vil det sige at angrebstiden er reduceret med 99% ... det er dér det uhyggelige er!

Man skal ikke se 2^69 som noget for en "privat-person" - for naturligvis har ingen en jordisk chance for at udregne dét... men sådan vil det altid være. Dem der tilgengæld _vil_ har uhyggelige mængder regnekraft til rådighed.
Gå til top

Opret dig som bruger i dag

Det er gratis, og du binder dig ikke til noget.

Når du er oprettet som bruger, får du adgang til en lang række af sidens andre muligheder, såsom at udforme siden efter eget ønske og deltage i diskussionerne.

Opret Bruger Login