---

Det er snart et år siden, der blev publiceret en
kollision for MD5 hash funktionen.

Det har givet anledning til en række misforståelser.

Mange personer uden tilstrækkelig kendskab til
kryptologi har troet, at en kollision er ikke noget
stort problem fordi man ikke kan komme ud for, at
begge filer har et meningsfyldt indhold.

Det er naturligvis forkert. Og ved Eurocrypt 2005
blev det beskrevet hvordan metoden til at finde en
kollision forholdsvis nemt kan bruges til at
konstruere to postscript filer med forskelligt valgt
indhold og samme hash.

http://www.cits.rub.de/MD5Collisions/

Ikke nok med at de giver to konkrete filer. De
beregninger, der allerede er foretaget kan bruges
til at konstruere flere kollisioner uden det kræver
nogen yderligere beregninger.

Jeg skrev det her indlæg fordi jeg kan forestille
mig at der er flere, som gerne vil se sådan en
kollision med egne øjne.

--
Kasper Dupont -- der bruger for meget tid på usenet.
Note to self: Don't try to allocate 256000 pages
with GFP_KERNEL on x86.

---

Kasper Dupont wrote:
> Jeg skrev det her indlæg fordi jeg kan forestille
> mig at der er flere, som gerne vil se sådan en
> kollision med egne øjne.

Tak for det..
Har du andet spaendende dernedefra skal du endelig ikke toeve.. :)

---

Morten Dahl wrote:
>
> Kasper Dupont wrote:
> > Jeg skrev det her indlæg fordi jeg kan forestille
> > mig at der er flere, som gerne vil se sådan en
> > kollision med egne øjne.
>
> Tak for det..
> Har du andet spaendende dernedefra skal du endelig ikke toeve.. :)

Det meste af det var jo noget langhåret noget, men
du kan da gå ind på https://www.brics.dk/eurocrypt05/
og se det meste. Og hvis du har mod på at læse nogen
af artiklerne kan jeg forestille mig, at de findes på
eprint.

Der blev præsenteret flere resultater omkring hash
funktioner. Jeg havde set frem til at høre, hvordan
kineserne havde båret sig ad med at bryde MD5.
Desværre var hendes evner til at tale engelsk
uhyggeligt ringe.

Daum og Lucks kollision er sikkert også konstrueret
vha. den algoritme kineserne udviklede.

Der blev også givet en algoritme til second preimage,
som virker med mange hash funktioner og er væsentligt
hurtigere end brute force. Jo større beskeden er, des
hurtigere kan man udregne et second preimage. Men det
skal lige siges, at det stadigt er hurtigere at finde
en kollision end at finde et second preimage.

Der var også en artikel, som beviser, at man ikke kan
konstruere en beviselig sikker hash funktion ved blot
at bruge en block cipher med en fast nøgle. Men så
vidt jeg forstod findes der sikre konstruktioner, som
bruger dele af beskeden som nøgle. Den artikel var dog
for kompliceret til at de kunne nå at gå i detaljer,
på de 25 minutter der er afsat til sådan en
præsentation.

Der blev nu også berørt mange andre områder end hash
funktioner, men hvis jeg skulle give et resume af det
hele ville jeg jo ikke blive færdig i dag.

--
Kasper Dupont -- der bruger for meget tid på usenet.
Note to self: Don't try to allocate 256000 pages
with GFP_KERNEL on x86.

---

Kasper Dupont wrote:
> Det meste af det var jo noget langhåret noget, men
> du kan da gå ind på https://www.brics.dk/eurocrypt05/
> og se det meste. Og hvis du har mod på at læse nogen
> af artiklerne kan jeg forestille mig, at de findes på
> eprint.

Sidst jeg kiggede paa eprint synes jeg ikke der var ret mange af dem
derinde.. Kan de ligger under en anden titel (hvorfor de skulle goere
det ved jeg ikke)?

> Der blev præsenteret flere resultater omkring hash
> funktioner. Jeg havde set frem til at høre, hvordan
> kineserne havde båret sig ad med at bryde MD5.
> Desværre var hendes evner til at tale engelsk
> uhyggeligt ringe.

Aergerligt; har de frigivet deres artikel?

> Der blev nu også berørt mange andre områder end hash
> funktioner, men hvis jeg skulle give et resume af det
> hele ville jeg jo ikke blive færdig i dag.

Det lyder bestemt interessant.. Har du mod/lyst, maa du da meget gerne
lave et kort dagligt resume

---

Morten Dahl wrote:
>
> Sidst jeg kiggede paa eprint synes jeg ikke der var ret mange af dem
> derinde.. Kan de ligger under en anden titel (hvorfor de skulle goere
> det ved jeg ikke)?

Der var i hvert fald nogen, som fortalte, at deres
artikler kunne hentes online. Og jeg mener det var fra
eprint. Men det kan godt være, at det kun var dem, der
havde lavet en forbedret udgave i forhold til den, der
var kommet med i proceedings.

>
> > Der blev præsenteret flere resultater omkring hash
> > funktioner. Jeg havde set frem til at høre, hvordan
> > kineserne havde båret sig ad med at bryde MD5.
> > Desværre var hendes evner til at tale engelsk
> > uhyggeligt ringe.
>
> Aergerligt; har de frigivet deres artikel?

Alle artiklerne står jo i proceedings, så jeg har ikke
haft nogen grund til at lede efter den.

Det er kun indlægene til rump session, som ikke er med.
Under rump session blev der præsenteret ting, som enten
ikke var helt færdige, eller ikke er af så stor betydning.

Eksemplet med postscript filerne var blevet præsenteret
under denne rump session, men ved den lejlighed fik jeg
desværre ikke skrevet URLen ned, så det var først i dag,
jeg fandt den.

>
> > Der blev nu også berørt mange andre områder end hash
> > funktioner, men hvis jeg skulle give et resume af det
> > hele ville jeg jo ikke blive færdig i dag.
>
> Det lyder bestemt interessant.. Har du mod/lyst, maa du da meget gerne
> lave et kort dagligt resume

Konferencen sluttede i går.

--
Kasper Dupont -- der bruger for meget tid på usenet.
Note to self: Don't try to allocate 256000 pages
with GFP_KERNEL on x86.

---

Kasper Dupont wrote:
> Konferencen sluttede i går.

Der kan man bare se ja - ved jeg skal aflevere projekt paa tirsdag, men
saa stopper min tidsfornemmelse ogsaa der :)

Nevermind, men tak for linkene..

---

On Fri, 27 May 2005 13:36:30 +0200, Kasper Dupont wrote:

> Mange personer uden tilstrækkelig kendskab til
> kryptologi har troet, at en kollision er ikke noget
> stort problem fordi man ikke kan komme ud for, at
> begge filer har et meningsfyldt indhold.

> Det er naturligvis forkert. Og ved Eurocrypt 2005
> blev det beskrevet hvordan metoden til at finde en
> kollision forholdsvis nemt kan bruges til at
> konstruere to postscript filer med forskelligt valgt
> indhold og samme hash.

Men hvilken betydning har det i praksis for andet end MD5 hash
verificering af dokumenters ægthed ?

Man bruger jo nogen steder at gemme en MD5 hash af et password og så
sammenligne det med en MD5 hash af det brugeren indtaster. Her vil det vel
være stort set umuligt at gætte sig til en indtastning der giver den
korrekt hash men ikke er det korrekte password ?

--
mvh Henrik Stidsen - http://henrikstidsen.dk/

---

Henrik Stidsen wrote:
> Men hvilken betydning har det i praksis for andet end MD5 hash
> verificering af dokumenters ægthed ?

Taenk digital signatur

> Man bruger jo nogen steder at gemme en MD5 hash af et password og så
> sammenligne det med en MD5 hash af det brugeren indtaster. Her vil det vel
> være stort set umuligt at gætte sig til en indtastning der giver den
> korrekt hash men ikke er det korrekte password ?

Hvis hash-vaerdien er kendt, kan Second Preimage algoritmen Kasper
naevner bruges til at finde en passede adgangskode..

---

Morten Dahl wrote:
>
> Henrik Stidsen wrote:
> > Men hvilken betydning har det i praksis for andet end MD5 hash
> > verificering af dokumenters ægthed ?
>
> Taenk digital signatur

Jeps. Scenariet de betragter er, at du modtager et
dokument og bliver bedt om at signere det. Du læser
så dokumentet igennem og beslutter dig for, at det
vil du godt skrive under på. Hvad du ikke er klar
over, at de allerede har konstrueret et andet
dokument med samme hash.

Hvis din signatur basserer sig på en MD5 hash af
dokumentet kan selve dokumentet udskiftes og
signaturen vil stadig være gyldig.

>
> Hvis hash-vaerdien er kendt, kan Second Preimage algoritmen Kasper
> naevner bruges til at finde en passede adgangskode..

Nej, det kan den nu ikke. Og det er der tre grunde
til. For det første drejer second preimage problemet
sig om at udfra et input konstruere et andet input,
som giver samme resultat. Da man ikke har det første
input hjælper den ikke meget.

For det andet er den algoritme som blev præsenteret
endnu ikke praktisk anvendelig. Den er som sagt
hurtigere end brute force, men stadig mere krævende
en konstruktion af en vilkårlig kollision ved brute
force.

Og kunne man endeligt få algoritmen til at virke, så
er den stadig kun relevant til store inputs. Jo større
det givne input er, des nemmere vil det være at
konstruere et andet input med samme hash.

Man kunne forestille sig algoritmen anvendt på f.eks.
en DVD iso. Hvis input er på 4.5GB kan man konstruere
et second preimage 75 millioner gange hurtigere end
brute force.

--
Kasper Dupont -- der bruger for meget tid på usenet.
Note to self: Don't try to allocate 256000 pages
with GFP_KERNEL on x86.

---

Kasper Dupont wrote:
>>Hvis hash-vaerdien er kendt, kan Second Preimage algoritmen Kasper
>>naevner bruges til at finde en passede adgangskode..
>
> Nej, det kan den nu ikke. Og det er der tre grunde
> til. For det første drejer second preimage problemet
> sig om at udfra et input konstruere et andet input,
> som giver samme resultat. Da man ikke har det første
> input hjælper den ikke meget.

Jeg kan ogsaa i tvivl om jeg ikke var for hurtigt ude der, men kunne
ikke overbevise mig selv.. Beklager..

Kan de ikke bindes sammen? Eller er det kun collision/2ndpreimage og
collision/preimage?

---

Morten Dahl wrote:
>
> Kan de ikke bindes sammen? Eller er det kun collision/2ndpreimage og
> collision/preimage?

Der er tale om tre forskellige problemer. Hvor kollision
er det nemmeste og preimage er (normalt) det sværeste.

Tiden for at lave et brute force angreb er for en n-bits
hash følgende:

kollision 2^(n/2)
2nd preimage 2^n
preimage 2^n

Har man en algoritme til at beregne et preimage vil den
næsten altid kunne bruges til 2nd preimage. Og har man
en algoritme til 2nd preimage kan den trivielt bruges til
at konstruere en kollision.

Den nye måde der blev beskrevet til at finde 2nd preimage
for mange hash funktioner er væsentligt hurtigere end 2^n,
men stadigvæk væsentligt langsommere end 2^(n/2).

Rent faktisk er tidsforbruget 2^n divideret med antal
blokke i det første input. Hvis det første input f.eks.
var et 4.5GB DVD image ville man altså kunne finde et
2nd preimage 75 millioner gange hurtigere end brute force.

For at lave et angreb mod md5 anvendt til passwords er
det sandsynligvis et preimage angreb, du har brug for.
Derfor kan ingen af de nye metoder bruges.

For at angribe en digital signatur afhænger det af ejeren
af signaturen, om du har brug for 2nd preimage eller om
en kollision kan gøre det. Er ejeren bare en smule
godtroende er en kollision nok.

Håber ikke forklaringen blev for kringlet.

--
Kasper Dupont -- der bruger for meget tid på usenet.
Note to self: Don't try to allocate 256000 pages
with GFP_KERNEL on x86.

---

Kasper Dupont wrote:
> Rent faktisk er tidsforbruget 2^n divideret med antal
> blokke i det første input. Hvis det første input f.eks.
> var et 4.5GB DVD image ville man altså kunne finde et
> 2nd preimage 75 millioner gange hurtigere end brute force.

Maaske er det bare sent, men synes ikke jeg kan faa det til 75 mill.?
Med antal blokke i foerste input, mener du da 4.5GB/128b?

Kender du noget til tilsvarende resultater for SHA1?

---

Morten Dahl wrote:
>
> Maaske er det bare sent, men synes ikke jeg kan faa det til 75 mill.?
> Med antal blokke i foerste input, mener du da 4.5GB/128b?

MD5 compression funktionen tager 16 bytes IV og 64 bytes
blok hvorfra der udregnes et 16 bytes IV til næste blok.
Så det bliver altså 4.5GB/64B.

>
> Kender du noget til tilsvarende resultater for SHA1?

Algoritmen til hurtigere second preimage virker så vidt
jeg husker også på SHA1. Men da SHA1 har 32 bits mere end
MD5 bliver tidsforbruget fire milliarder gange større end
for et tilsvarende angreb mod MD5.

Hvad angår at finde en kollision er det lykkedes at finde
en kollision for SHA0 og for en reduceret SHA1. Jeg mener
der er fundet en kollision for en SHA1 med 40 runder i
stedet for de 80 runder, som bruges i den rigtige SHA1.

Jeg har endnu ikke hørt om nogen successfulde angreb mod
SHA1 med effektivitet bedre end 2^80 (som er hvad en brute
force kollision kræver).

--
Kasper Dupont -- der bruger for meget tid på usenet.
Note to self: Don't try to allocate 256000 pages
with GFP_KERNEL on x86.

---

Kasper Dupont wrote:
> Morten Dahl wrote:
>
>>Maaske er det bare sent, men synes ikke jeg kan faa det til 75 mill.?
>>Med antal blokke i foerste input, mener du da 4.5GB/128b?
>
>
> MD5 compression funktionen tager 16 bytes IV og 64 bytes
> blok hvorfra der udregnes et 16 bytes IV til næste blok.
> Så det bliver altså 4.5GB/64B.

Doh..

>>Kender du noget til tilsvarende resultater for SHA1?
> Jeg har endnu ikke hørt om nogen successfulde angreb mod
> SHA1 med effektivitet bedre end 2^80 (som er hvad en brute
> force kollision kræver).

Ok, tak for svar :)

---

On Fri, 10 Jun 2005 12:20:35 +0200, Kasper Dupont
<kasperd@daimi.au.dk> wrote:

>Jeg har endnu ikke hørt om nogen successfulde angreb mod
>SHA1 med effektivitet bedre end 2^80 (som er hvad en brute
>force kollision kræver).

.... plus ca. 17,7%, hvis vi skal gå i detaljer

--
- Peter Brodersen

---

Peter Brodersen wrote:
>
> On Fri, 10 Jun 2005 12:20:35 +0200, Kasper Dupont
> <kasperd@daimi.au.dk> wrote:
>
> >Jeg har endnu ikke hørt om nogen successfulde angreb mod
> >SHA1 med effektivitet bedre end 2^80 (som er hvad en brute
> >force kollision kræver).
>
> ... plus ca. 17,7%, hvis vi skal gå i detaljer

Det skal man ikke, når man snakker om kryptografiske
primitiver. Og når jeg snakker om 2^80 er det
underforstået 2^80 evalueringer af hash funktionen
som er det antal, der ca. skal til for at have en god
sandsynlighed for at finde en kollision.

--
Kasper Dupont -- der bruger for meget tid på usenet.
Note to self: Don't try to allocate 256000 pages
with GFP_KERNEL on x86.

---

On 2005-05-27, Henrik Stidsen <nntpspam@hs235.dk> wrote:
> Men hvilken betydning har det i praksis for andet end MD5 hash
> verificering af dokumenters ægthed ?

Rigtig meget af den open-source software, der bliver distribueret på
Internettet benytter md5 til at signere ægtheden af softwaren. Hvorvidt
det aktuelle angreb kan bruges til at generere software med f.eks.
bagdøre, men med samme md5 sum kan jeg dog ikke gennemskue.

--
Med venlig hilsen
- Jacob Atzen