---

Hvor lang tid kan vi egentlig forvente, der vil gå før
man ved et bruteforce attack kan finde en kollision for
md5 hash funktionen? En times CPU tid på en 568MHz
Celeron var nok til at finde et par filer, hvis hash
var ens på 100 ud af de 128 bits. Hvor mange gange mere
CPU tid skal der mon til for at finde et par filer, hvor
de sidste 28 bits af hashværdien også er ens?

--
Kasper Dupont -- der bruger for meget tid på usenet.
For sending spam use mailto:aaarep@daimi.au.dk
for(_=52;_;(_%5)||(_/=5),(_%5)&&(_-=2))putchar(_);

---

Kasper Dupont <kasperd@daimi.au.dk> wrote:
> Hvor lang tid kan vi egentlig forvente, der vil gå før
> man ved et bruteforce attack kan finde en kollision for
> md5 hash funktionen? En times CPU tid på en 568MHz
> Celeron var nok til at finde et par filer, hvis hash
> var ens på 100 ud af de 128 bits. Hvor mange gange mere
> CPU tid skal der mon til for at finde et par filer, hvor
> de sidste 28 bits af hashværdien også er ens?

Hvis det er direkte proportionalt, vel 2^28 gange så længe - eller
268435456 timer (roughly, 30643 år) - måske ikke helt så længe, men
alligevel? ;)

--
Rune B. Broberg
Feel free to GPG-encrypt email sent to me. Keyid: 0x87CD3DBD

---

"Rune B. Broberg" wrote:
>
> Kasper Dupont <kasperd@daimi.au.dk> wrote:
> > Hvor lang tid kan vi egentlig forvente, der vil gå før
> > man ved et bruteforce attack kan finde en kollision for
> > md5 hash funktionen? En times CPU tid på en 568MHz
> > Celeron var nok til at finde et par filer, hvis hash
> > var ens på 100 ud af de 128 bits. Hvor mange gange mere
> > CPU tid skal der mon til for at finde et par filer, hvor
> > de sidste 28 bits af hashværdien også er ens?
>
> Hvis det er direkte proportionalt, vel 2^28 gange så længe - eller
> 268435456 timer (roughly, 30643 år) - måske ikke helt så længe, men
> alligevel? ;)

Ja, men hvad nu hvis jeg smed 2000 gange så meget CPU kraft
efter problemet? (OK, jeg får nok ikke lov til at lægge
beslag på sådan et cluster 15 år i træk, men hvad nu om ti
år, når computerne er blevet 1000 gange så hurtige?)

--
Kasper Dupont -- der bruger for meget tid på usenet.
For sending spam use mailto:aaarep@daimi.au.dk
for(_=52;_;(_%5)||(_/=5),(_%5)&&(_-=2))putchar(_);

---

Kasper Dupont <kasperd@daimi.au.dk> wrote:
> "Rune B. Broberg" wrote:
>>
>> Kasper Dupont <kasperd@daimi.au.dk> wrote:
>> > Hvor lang tid kan vi egentlig forvente, der vil gå før
>> > man ved et bruteforce attack kan finde en kollision for
>> > md5 hash funktionen? En times CPU tid på en 568MHz
>> > Celeron var nok til at finde et par filer, hvis hash
>> > var ens på 100 ud af de 128 bits. Hvor mange gange mere
>> > CPU tid skal der mon til for at finde et par filer, hvor
>> > de sidste 28 bits af hashværdien også er ens?
>>
>> Hvis det er direkte proportionalt, vel 2^28 gange så længe - eller
>> 268435456 timer (roughly, 30643 år) - måske ikke helt så længe, men
>> alligevel? ;)
>
> Ja, men hvad nu hvis jeg smed 2000 gange så meget CPU kraft
> efter problemet? (OK, jeg får nok ikke lov til at lægge
> beslag på sådan et cluster 15 år i træk, men hvad nu om ti
> år, når computerne er blevet 1000 gange så hurtige?)

Til den tid har man forhåbentlig fundet på at bruge noget nyt - måske en
1024-bit hash? :) Jeg ville i alt fald ikke pt. bruge md5 til noget jeg
forventer skal holde mere end nogle år...

--
Rune B. Broberg
Feel free to GPG-encrypt email sent to me. Keyid: 0x87CD3DBD

---

"Rune B. Broberg" wrote:
>
> Til den tid har man forhåbentlig fundet på at bruge noget nyt - måske en
> 1024-bit hash? :)

Ja, man holder forhåbentligt op med at bruge md5. Der findes jo allerede
nogle forholdsvis stamdardiserede hash funktioner med mere end 128 bits.
Man kunne f.eks. allerede nu bruge sha1 som giver en 160 bits hash værdi.
Det er nok mest på grund af hastighedsforskellen at man stadig bruger md5,
den er jo trods alt dobbelt så hurtig. Jeg tror ikke en 1000 gange så
hurtig computer ændrer ret meget på det problem, man vil jo bare ønske
at hashe 1000 gange så store data. Med mindre selvfølgelig det ender med,
at båndbredden til hukommelsen bliver flaskehalsen i steddet for CPUen.

> Jeg ville i alt fald ikke pt. bruge md5 til noget jeg
> forventer skal holde mere end nogle år...

OK, den del er vi så nok enige om. Men hvilken hash ville du så egentlig
vælge i stedet?

--
Kasper Dupont -- der bruger for meget tid på usenet.
For sending spam use mailto:aaarep@daimi.au.dk
for(_=52;_;(_%5)||(_/=5),(_%5)&&(_-=2))putchar(_);

---

Kasper Dupont <kasperd@daimi.au.dk> writes:

>Ja, men hvad nu hvis jeg smed 2000 gange så meget CPU kraft
>efter problemet? (OK, jeg får nok ikke lov til at lægge
>beslag på sådan et cluster 15 år i træk, men hvad nu om ti
>år, når computerne er blevet 1000 gange så hurtige?)

I "gamle" dage var der ikke nogen grund til at bruge shadow
password-filer, for det var totalt utænkeligt, at nogen
brute-forcede /etc/passwd.

I dag er Unix ikke nævneværdigt mere usikker end dengang -
på trods af at brute-forcing er ret nemt. Man har bare
fundet en ny metode.

Mvh.
   Klaus.

---

Den Sun, 25 May 2003 14:49:33 +0000 (UTC) skrev Klaus Ellegaard:
>Kasper Dupont <kasperd@daimi.au.dk> writes:
>
>>Ja, men hvad nu hvis jeg smed 2000 gange så meget CPU kraft
>>efter problemet? (OK, jeg får nok ikke lov til at lægge
>>beslag på sådan et cluster 15 år i træk, men hvad nu om ti
>>år, når computerne er blevet 1000 gange så hurtige?)
>
>I "gamle" dage var der ikke nogen grund til at bruge shadow
>password-filer, for det var totalt utænkeligt, at nogen
>brute-forcede /etc/passwd.

Hvornår er det blevet realistisk at brute-force en tripple-DES, som
typisk bruges i /etc/passwd? (bortset fra når der bruges md5 for at
tillade længere passwords).

Mvh
Kent
--
If you think about it, Windows XP is actually the OS that
started as "Microsoft OS/2 NT 3.0"

---

leeloo@phreaker.net (Kent Friis) writes:

>Hvornår er det blevet realistisk at brute-force en tripple-DES, som
>typisk bruges i /etc/passwd? (bortset fra når der bruges md5 for at
>tillade længere passwords).

I 1995 fandt vi på min arbejdsplads et par hundrede "nemme"
passwords med en 170 MHz microSPARC.

Så det er skam længe siden.

Mvh.
   Klaus.

---

Den Sun, 25 May 2003 14:55:18 +0000 (UTC) skrev Klaus Ellegaard:
>leeloo@phreaker.net (Kent Friis) writes:
>
>>Hvornår er det blevet realistisk at brute-force en tripple-DES, som
>>typisk bruges i /etc/passwd? (bortset fra når der bruges md5 for at
>>tillade længere passwords).
>
>I 1995 fandt vi på min arbejdsplads et par hundrede "nemme"
>passwords med en 170 MHz microSPARC.

Med "nemme" mener du vel dictionary attack? Det har altid været muligt,
og er ikke afhængig af hvor stærk krypteringen er.

At brute-force password-filen er principielt lige nemt for alle
passwords af samme længde, uanset om det er "password" eller "d7jci4h1".
Nogen vil dog blive fundet før andre, afhængig af rækkefølgen man tester
- går man fx a->z0->9, vil "d7jci4h1" faktisk blive fundet før
"password".

Mvh
Kent
--
Motion: andet ord for "ondt i fødderne".

---

leeloo@phreaker.net (Kent Friis) writes:

>Med "nemme" mener du vel dictionary attack? Det har altid været muligt,
>og er ikke afhængig af hvor stærk krypteringen er.

Ja, men det var ikke reelt muligt i 1969. Eller, det var det.
Men det var urealistisk at tro, at man kunne komme 1000 gange
rundt om en ordbog uden at blive opdaget undervejs. I dag er
det et spørgsmål om sekunder.

>At brute-force password-filen er principielt lige nemt for alle
>passwords af samme længde, uanset om det er "password" eller "d7jci4h1".
>Nogen vil dog blive fundet før andre, afhængig af rækkefølgen man tester
>- går man fx a->z0->9, vil "d7jci4h1" faktisk blive fundet før
>"password".

Dictionary- og brute-force-attacks er det samme (eller det
første er i hvert fald en delmængde af det andet). Passwordet
"d7jci4h1" vil blive fundet af begge, hvis dictionary-rutinen
køres så langt ud, at det bliver gætværk. Blot vil "password"
og "p@ssw0rd" blive fundet hurtigere med et dictionary-angreb
end et lige-på-og-hårdt bruteforce-angreb.

Mvh.
   Klaus.

---

Den Sun, 25 May 2003 15:11:37 +0000 (UTC) skrev Klaus Ellegaard:
>leeloo@phreaker.net (Kent Friis) writes:
>
>>Med "nemme" mener du vel dictionary attack? Det har altid været muligt,
>>og er ikke afhængig af hvor stærk krypteringen er.
>
>Ja, men det var ikke reelt muligt i 1969. Eller, det var det.
>Men det var urealistisk at tro, at man kunne komme 1000 gange
>rundt om en ordbog uden at blive opdaget undervejs. I dag er
>det et spørgsmål om sekunder.

Hvis man kører det på en anden maskine, er der ikke nogen der opdager
der før det er for sent.

>>At brute-force password-filen er principielt lige nemt for alle
>>passwords af samme længde, uanset om det er "password" eller "d7jci4h1".
>>Nogen vil dog blive fundet før andre, afhængig af rækkefølgen man tester
>>- går man fx a->z0->9, vil "d7jci4h1" faktisk blive fundet før
>>"password".
>
>Dictionary- og brute-force-attacks er det samme (eller det
>første er i hvert fald en delmængde af det andet).

Alt er vel en delmænge af brute-force attacks.

>Passwordet
>"d7jci4h1" vil blive fundet af begge, hvis dictionary-rutinen
>køres så langt ud, at det bliver gætværk.

Så er det jo reelt en blanding, der starter med et rent dictionary
attack, og bevæger sig over imod brute-force. Men de "nemme" passwords
er jo netop nemme fordi dictionary attack'et alene kommer tæt på.

Mvh
Kent
--
Desuden kan jeg ikke se nogen grund til at springe over hvor gærdet er
lavest, når man kan vente på at det alligevel bliver revet ned fordi
der skal bygges en omfartsvej...
- Claus Frørup og Asbjørn Christensen i dk.snak.

---

leeloo@phreaker.net (Kent Friis) writes:

>>Ja, men det var ikke reelt muligt i 1969. Eller, det var det.
>>Men det var urealistisk at tro, at man kunne komme 1000 gange
>>rundt om en ordbog uden at blive opdaget undervejs. I dag er
>>det et spørgsmål om sekunder.

>Hvis man kører det på en anden maskine, er der ikke nogen der opdager
>der før det er for sent.

Man havde "liiiiige" en anden Unix-maskine stående derhjemme
dengang?

>>Dictionary- og brute-force-attacks er det samme (eller det
>>første er i hvert fald en delmængde af det andet).

>Alt er vel en delmænge af brute-force attacks.

Filosofien i dictionary- og bruteforce er præcis den samme:
tag et vilkårligt password og prøv med det. Den absolut
eneste forskel er, at der er lidt logik i dictionary's valg
af rækkefølge.

Mvh.
   Klaus.

---

Den Sun, 25 May 2003 15:30:08 +0000 (UTC) skrev Klaus Ellegaard:
>leeloo@phreaker.net (Kent Friis) writes:
>
>>>Ja, men det var ikke reelt muligt i 1969. Eller, det var det.
>>>Men det var urealistisk at tro, at man kunne komme 1000 gange
>>>rundt om en ordbog uden at blive opdaget undervejs. I dag er
>>>det et spørgsmål om sekunder.
>
>>Hvis man kører det på en anden maskine, er der ikke nogen der opdager
>>der før det er for sent.
>
>Man havde "liiiiige" en anden Unix-maskine stående derhjemme
>dengang?

Ud fra den tankegang, kan man stadig finde personer for hvem
det er "ikke reelt muligt i 2003".

>>>Dictionary- og brute-force-attacks er det samme (eller det
>>>første er i hvert fald en delmængde af det andet).
>
>>Alt er vel en delmænge af brute-force attacks.
>
>Filosofien i dictionary- og bruteforce er præcis den samme:
>tag et vilkårligt password og prøv med det. Den absolut
>eneste forskel er, at der er lidt logik i dictionary's valg
>af rækkefølge.

Nej, bruteforce er "forsøg med samtlige mulige passwords".

Dictionary attacks er en systematisk afgrænsning, og dermed ikke
"samtlige".

Mvh
Kent
--
Motion: andet ord for "ondt i fødderne".

---

leeloo@phreaker.net (Kent Friis) writes:

>Nej, bruteforce er "forsøg med samtlige mulige passwords".

>Dictionary attacks er en systematisk afgrænsning, og dermed ikke
>"samtlige".

Det kommer an på, hvordan det er implementeret. Jeg tror ikke,
du kan finde en password-cracker, der følger din definition på
dictionary attacks i praksis.

Mvh.
   Klaus.

---

Den Sun, 25 May 2003 15:53:45 +0000 (UTC) skrev Klaus Ellegaard:
>leeloo@phreaker.net (Kent Friis) writes:
>
>>Nej, bruteforce er "forsøg med samtlige mulige passwords".
>
>>Dictionary attacks er en systematisk afgrænsning, og dermed ikke
>>"samtlige".
>
>Det kommer an på, hvordan det er implementeret. Jeg tror ikke,
>du kan finde en password-cracker, der følger din definition på
>dictionary attacks i praksis.

Den vigtige forskel, er at dictionary attacks er grunden til at vi
altid indskærper overfor brugere at de skal vælge et "svært" password,
ikke bare navnet på deres hund, eller "password". Så hvis du
seriøst mener at dictionary attacks og brute-force er det samme,
så kan vi lige så godt begynde at bruge almindelige ord.

Mvh
Kent
--
A computer without Windows is like a chocolate cake without mustard.

---

leeloo@phreaker.net (Kent Friis) writes:

>ikke bare navnet på deres hund, eller "password". Så hvis du
>seriøst mener at dictionary attacks og brute-force er det samme,
>så kan vi lige så godt begynde at bruge almindelige ord.

Det har jeg netop skrevet, at jeg ikke mener.

Mvh.
   Klaus.

---

Den Sun, 25 May 2003 16:08:24 +0000 (UTC) skrev Klaus Ellegaard:
>leeloo@phreaker.net (Kent Friis) writes:
>
>>ikke bare navnet på deres hund, eller "password". Så hvis du
>>seriøst mener at dictionary attacks og brute-force er det samme,
>>så kan vi lige så godt begynde at bruge almindelige ord.
>
>Det har jeg netop skrevet, at jeg ikke mener.

I så fald har jeg IKKE fået svar på mit oprindelige spørgsmål - om
det er realistisk at brute-force et tripple-des krypteret password.

Dictionary-attacks er kun interessante over for "dumme brugere",
os andre der kan huske et autogenereret random password, hjælper
de ikke overfor.

Mvh
Kent
--
Journalist: En der har forstand på at skrive artikler, men typisk
ikke på det artiklerne handler om.

---

leeloo@phreaker.net (Kent Friis) writes:

>Dictionary-attacks er kun interessante over for "dumme brugere",
>os andre der kan huske et autogenereret random password, hjælper
>de ikke overfor.

Et brute-force-angreb kan også gætte dit "svære" password på en
milliontedel af et sekund. Hvem siger, den starter ved " " hver
gang?

Jeg har ikke interesseret mig nærmere for, hvor hurtigt et
forholdsvis billigt cluster kan klare sagen.

Mvh.
   Klaus.

---

Den Sun, 25 May 2003 16:35:14 +0000 (UTC) skrev Klaus Ellegaard:
>leeloo@phreaker.net (Kent Friis) writes:
>
>>Dictionary-attacks er kun interessante over for "dumme brugere",
>>os andre der kan huske et autogenereret random password, hjælper
>>de ikke overfor.
>
>Et brute-force-angreb kan også gætte dit "svære" password på en
>milliontedel af et sekund. Hvem siger, den starter ved " " hver
>gang?

Ja, men hvis man er *så* heldig, vil jeg anbefale lotto i stedet for.
Det er der flere penge i, og det er endda lovligt.

Mvh
Kent
--
A computer without Windows is like a chocolate cake without mustard.

---

Kasper Dupont <kasperd@daimi.au.dk> writes:

>> Jeg ville i alt fald ikke pt. bruge md5 til noget jeg
>> forventer skal holde mere end nogle år...
>
> OK, den del er vi så nok enige om. Men hvilken hash ville du så egentlig
> vælge i stedet?

OpenSSL-manualsiderne anbefaler at man bruger SHA-1 til nye
applikationer og det er også den GnuPG normalt bruger til at lave
signature med.

Det giver godt nok kun 160 bit

--
Peter Makholm | We constantly have to keep in mind why natural
peter@makholm.net | languages are good at what they're good at. And to
http://hacking.dk | never forget that Perl is a human language first,
| and a computer language second

---

Kasper Dupont <kasperd@daimi.au.dk> wrote:

>Hvor lang tid kan vi egentlig forvente, der vil gå før
>man ved et bruteforce attack kan finde en kollision for
>md5 hash funktionen? En times CPU tid på en 568MHz
>Celeron var nok til at finde et par filer, hvis hash
>var ens på 100 ud af de 128 bits.

Var det nogle bestemte 100 bit (fx de første) i summen du forsøgte at
få ens, eller bare 100 ud af de 128? Hvis det bare var 100 ud af de
128, så er det jo langt langt nemmere end 100 bestemte, og så kan jeg
måske godt forstå det (der vil jo fx i snit være 64 matchende bit i to
uafhængige tilfældige 128-bit-tal). Sandsynligheden for at få plat i
100 af 128 kast med en mønt er meget større end sandsynligheden for at
få plat i 100 af 100 kast.

Hvis derimod dine 100 bit var bestemte på forhånd (fx de første), så
lyder det utroligt.

Var det specielt korte filer? (Jeg ved ikke om fx alle filer af
længde 128 bit = 16 bytes har forskellige MD5-summer, eller om der er
kollisioner i filer <= 16 bytes.)

Hvor mange forskellige filer prøvede du før kollisionen blev fundet?
Det kan jo ikke have været noget der bare minder om 2^99 (så skulle
hver kun have taget ca. 2^(-68) sekund, og så ville det være en
imponerende Celeron!).

>Hvor mange gange mere
>CPU tid skal der mon til for at finde et par filer, hvor
>de sidste 28 bits af hashværdien også er ens?

Hvis dine 100 bit var bestemte på forhånd, så bør svaret være 2^28
gange mere. Hvis ikke, så meget mere.
--
Jesper Dybdal, Denmark.
http://www.dybdal.dk (in Danish).

---

Jeg skrev:

>Hvor mange forskellige filer prøvede du før kollisionen blev fundet?
>Det kan jo ikke have været noget der bare minder om 2^99 (så skulle
>hver kun have taget ca. 2^(-68) sekund, og så ville det være en
>imponerende Celeron!).

Men det er da vist noget vås: det er jo et tilfælde af
fødselsdagssyndromet, så det relevante antal er ikke i
størrelsesordenen 2^100, men derimod 2^50 (de tager til gengæld lang
tid: hver ny md5sum skal jo sammenlignes med i snit 2^49 andre). Det
kræver stadig en ufatteligt hurtig og stor maskine eller ufatteligt
held eller en systematisk ulempe i MD5 - eller at det faktisk ikke var
100 faste bit der var ens.

>>Hvor mange gange mere
>>CPU tid skal der mon til for at finde et par filer, hvor
>>de sidste 28 bits af hashværdien også er ens?
>
>Hvis dine 100 bit var bestemte på forhånd, så bør svaret være 2^28
>gange mere.

Og det er tilsvarende noget vås: det er nok ca. 2^14.

>Hvis ikke, så meget mere.

Det er til gengæld rigtigt, og det var jo nok det du mente (altså ikke
100 faste bit) med din beskrivelse.

--
Jesper Dybdal, Denmark.
http://www.dybdal.dk (in Danish).

---

Jesper Dybdal wrote:
>
> Hvis derimod dine 100 bit var bestemte på forhånd (fx de første), så
> lyder det utroligt.

De 40 positioner havde jeg selv valgt. Ud af alle de kollisioner jeg
fandt på 40 valgte positioner fandt jeg så den, hvor der var flest
andre ens bits. Det vil sige at ud af de 88 positioner, jeg ikke havde
valgt var der 60 ens bits.

>
> Var det specielt korte filer? (Jeg ved ikke om fx alle filer af
> længde 128 bit = 16 bytes har forskellige MD5-summer, eller om der er
> kollisioner i filer <= 16 bytes.)

De var specielt korte, kun 3 bytes hver. Men jeg tror ikke længden har
haft nogen væsentlig indflydelse på mit resultat (bortset fra, at det
tager lidt længere tid at beregne md5 på en større fil). Jeg tror, det
vil være meget usandsynligt, at alle filer på 16 bytes hare forskellige
md5sum. Faktisk tror jeg det mindste par af filer med en kollision nok
vil være på otte bytes hver, evt. ni bytes i den ene af filerne.

>
> Hvor mange forskellige filer prøvede du før kollisionen blev fundet?

2^24


Det, der overrasker mig mest er altså, at jeg finder 60 ens bits ud
af 88 positioner, der burde have været tilfældige.

--
Kasper Dupont -- der bruger for meget tid på usenet.
For sending spam use mailto:aaarep@daimi.au.dk
for(_=52;_;(_%5)||(_/=5),(_%5)&&(_-=2))putchar(_);

---

Kasper Dupont <kasperd@daimi.au.dk> wrote:

>Jesper Dybdal wrote:
>>
>> Hvis derimod dine 100 bit var bestemte på forhånd (fx de første), så
>> lyder det utroligt.
>
>De 40 positioner havde jeg selv valgt. Ud af alle de kollisioner jeg
>fandt på 40 valgte positioner fandt jeg så den, hvor der var flest
>andre ens bits. Det vil sige at ud af de 88 positioner, jeg ikke havde
>valgt var der 60 ens bits.

Umiddelbart synes jeg ikke det lyder specielt bekymrende.

>> Hvor mange forskellige filer prøvede du før kollisionen blev fundet?
>
>2^24

>Det, der overrasker mig mest er altså, at jeg finder 60 ens bits ud
>af 88 positioner, der burde have været tilfældige.

I snit er der jo altså 44 ens bit ud af de 88. Nu skriver du ikke
hvor mange kollisioner på de 40 bit du fandt, men det bør vel være i
størrelsesordenen 2^4 = 16.

Der er (hvis MD5-algoritmen er perfekt og inddata er tilfældig) en
fast 50% sandsynlighed for at en bestemt bit i et givet resultat er
magen til den samme bit i et andet resultat.

Så du har foretaget i størrelsesordenen 16 eksperimenter der hver
svarer til at kaste en terning 88 gange. I ét af eksperimenterne fik
du plat i 60 af de 88 kast. Med forbehold for at det er *længe* siden
jeg har lært om binomialfordelingen, så får jeg det med lidt
lommeregnerarbejde til at sandsynligheden for at ét sådant eksperiment
giver præcis 60 stk. plat er ca. 0,02%. Sandsynligheden for at det
giver *mindst* 60 er naturligvis en del større og er nok den relevante
her (det er jo ikke "præcis 60" der er interessant, men "så mange som
60").

Jeg har svært ved at se at dit eksperiment viser noget interessant om
MD5's kvaliteter.

Der er svjh fundet nogle algoritmemæssige problemer med MD5 som gør at
man i visse situationer kan finde kollisioner (i meget mindre end de
ca. 2^64 forsøg der statistisk skal til en brute-force). Det er en
god grund til ikke at bruge MD5 til at underskrive dokumenter som
potentielt skurkagtige matematikere har fremstillet.

Men det er ikke nogen grund til at være bange for at bruge MD5 til at
underskrive noget man selv har fremstillet (eller bare ændret en
lillebitte smule på). Der skal formodentlig i snit de teoretiske
2^127 forsøg til at finde en kollision med en given tilfældig fil.

2^127 er et stort tal. Hvis man kunne regne én MD5-sum ud på et
nanosekund (og dermed 2*10^25 på en time), så tager det 5*10^21 år at
prøve 2^127 filer.

Og selv hvis vi en dag har maskiner der er en milliard gange hurtigere
end det, og vi bruger en milliard af dem, så tager det stadig i snit
5000 år.

--
Jesper Dybdal, Denmark.
http://www.dybdal.dk (in Danish).

---

Den Sun, 25 May 2003 20:34:48 +0200 skrev Jesper Dybdal:
>Så du har foretaget i størrelsesordenen 16 eksperimenter der hver
>svarer til at kaste en terning 88 gange. I ét af eksperimenterne fik
>du plat i 60 af de 88 kast.

Kan vi lige få formlen for at beregne sandsynligheden for at få plat
ved kast med en terning?

Mvh
Kent
--
Gilthoniel, A Elbereth
Aiya elenion ancalima!
- Tolkien, "The Lord of the Rings"

---

leeloo@phreaker.net (Kent Friis) wrote:

>Den Sun, 25 May 2003 20:34:48 +0200 skrev Jesper Dybdal:
>>Så du har foretaget i størrelsesordenen 16 eksperimenter der hver
>>svarer til at kaste en terning 88 gange. I ét af eksperimenterne fik
>>du plat i 60 af de 88 kast.
>
>Kan vi lige få formlen for at beregne sandsynligheden for at få plat
>ved kast med en terning?

Ja: 0,5 (sådan ca.)

Binomialfordelingen: Man gentager n gange en hændelse som har
sandsynligheden s for ét udfald (fx plat, eller at bit 50 i en MD5-sum
er magen til bit 50 i en anden MD5-sum) og 1-s for et andet udfald.

Sandsynligheden for at netop p af de n udfald er det med
sandsynligheden s, er
n! / (p! * (n-p)!) * s^p * (1-s)^(n-p)

eller, i dette tilfælde
88!/(60!*28!) * (1/2)^60 * (1/2)^28

--
Jesper Dybdal, Denmark.
http://www.dybdal.dk (in Danish).

---

leeloo@phreaker.net (Kent Friis) wrote:

>Den Sun, 25 May 2003 20:34:48 +0200 skrev Jesper Dybdal:
>>Så du har foretaget i størrelsesordenen 16 eksperimenter der hver
>>svarer til at kaste en terning 88 gange. I ét af eksperimenterne fik
>>du plat i 60 af de 88 kast.
>
>Kan vi lige få formlen for at beregne sandsynligheden for at få plat
>ved kast med en terning?

Det var først lige efter at jeg havde svaret på det at jeg lagde mærke
til hvad det sidste ord var - seniliteten slår sommetider tidligt til.
--
Jesper Dybdal, Denmark.
http://www.dybdal.dk (in Danish).

---

Den Sun, 25 May 2003 22:25:44 +0200 skrev Jesper Dybdal:
>leeloo@phreaker.net (Kent Friis) wrote:
>
>>Den Sun, 25 May 2003 20:34:48 +0200 skrev Jesper Dybdal:
>>>Så du har foretaget i størrelsesordenen 16 eksperimenter der hver
>>>svarer til at kaste en terning 88 gange. I ét af eksperimenterne fik
>>>du plat i 60 af de 88 kast.
>>
>>Kan vi lige få formlen for at beregne sandsynligheden for at få plat
>>ved kast med en terning?
>
>Det var først lige efter at jeg havde svaret på det at jeg lagde mærke
>til hvad det sidste ord var - seniliteten slår sommetider tidligt til.

ROTFL

Der er altså ingen af mine terninger der har en side der hedder plat -
det nærmeste jeg kan komme er vist globus'en på en ludo-terning.

Mvh
Kent
--
IE is the only thing capable of making Netscape look good
- D. Spider in comp.os.linux.advocacy

---

Jesper Dybdal wrote:
>
> Så du har foretaget i størrelsesordenen 16 eksperimenter der hver
> svarer til at kaste en terning 88 gange. I ét af eksperimenterne fik
> du plat i 60 af de 88 kast. Med forbehold for at det er *længe* siden
> jeg har lært om binomialfordelingen, så får jeg det med lidt
> lommeregnerarbejde til at sandsynligheden for at ét sådant eksperiment
> giver præcis 60 stk. plat er ca. 0,02%. Sandsynligheden for at det
> giver *mindst* 60 er naturligvis en del større og er nok den relevante
> her (det er jo ikke "præcis 60" der er interessant, men "så mange som
> 60").

Det er også længe siden jeg har lært om binomialfordelingen. Men det
lyder alt sammen meget rigtigt. Bortset fra, at jeg ikke kan se, hvor
du har fået de 16 fra, burde det ikke være 128?

--
Kasper Dupont -- der bruger for meget tid på usenet.
For sending spam use mailto:aaarep@daimi.au.dk
for(_=52;_;(_%5)||(_/=5),(_%5)&&(_-=2))putchar(_);

---

Kasper Dupont <kasperd@daimi.au.dk> wrote:

>Jesper Dybdal wrote:
>>
>> Så du har foretaget i størrelsesordenen 16 eksperimenter der hver
>> svarer til at kaste en terning 88 gange. I ét af eksperimenterne fik
>> du plat i 60 af de 88 kast. Med forbehold for at det er *længe* siden
>> jeg har lært om binomialfordelingen, så får jeg det med lidt
>> lommeregnerarbejde til at sandsynligheden for at ét sådant eksperiment
>> giver præcis 60 stk. plat er ca. 0,02%. Sandsynligheden for at det
>> giver *mindst* 60 er naturligvis en del større og er nok den relevante
>> her (det er jo ikke "præcis 60" der er interessant, men "så mange som
>> 60").
>
>Det er også længe siden jeg har lært om binomialfordelingen. Men det
>lyder alt sammen meget rigtigt. Bortset fra, at jeg ikke kan se, hvor
>du har fået de 16 fra, burde det ikke være 128?

Nu må du altså snart røbe præcis hvor mange kollisioner du fandt

Min tanke var at det vel koster ca. 2^20 filer at finde en kollision
blandt de faste 40 bit. ("Ca." betyder at jeg ikke lige kan overskue
om det måske er en faktor 2 forkert.)

Hvis det er rigtigt, så tænkte jeg at du formodentlig har fundet ca.
2^4 kollisioner i dine 2^24 forsøg. Men nu du siger det, er det
forkert - fødseldagssyndromet slår også til her, så det er snarere
(2^4)^2 = 256.

Så hvis du faktisk fandt ca. 128 kollisioner, så er jeg efterhånden
kun en enkelt faktor 2 galt et eller andet sted.
--
Jesper Dybdal, Denmark.
http://www.dybdal.dk (in Danish).

---

Jesper Dybdal wrote:
>
> Nu må du altså snart røbe præcis hvor mange kollisioner du fandt

Jeg har ikke talt dem. De 128 var bare hvad jeg forventede.

>
> Min tanke var at det vel koster ca. 2^20 filer at finde en kollision
> blandt de faste 40 bit. ("Ca." betyder at jeg ikke lige kan overskue
> om det måske er en faktor 2 forkert.)
>
> Hvis det er rigtigt, så tænkte jeg at du formodentlig har fundet ca.
> 2^4 kollisioner i dine 2^24 forsøg. Men nu du siger det, er det
> forkert - fødseldagssyndromet slår også til her, så det er snarere
> (2^4)^2 = 256.
>
> Så hvis du faktisk fandt ca. 128 kollisioner, så er jeg efterhånden
> kun en enkelt faktor 2 galt et eller andet sted.

Den måde jeg regnede på var, at med 2^24 filer er der ca.
2^47 forskellige måder at udtage et par af filer på. For
hvert par er sandsynligheden for at de er ens på de 40
bits 2^-40. Dermed burde der være ca. 2^7 kollisioner på
de 40 bits. Nå, nu bliver jeg vist nødt til at tælle efter.

--
Kasper Dupont -- der bruger for meget tid på usenet.
For sending spam use mailto:aaarep@daimi.au.dk
for(_=52;_;(_%5)||(_/=5),(_%5)&&(_-=2))putchar(_);

---

Kasper Dupont wrote:
>
> Den måde jeg regnede på var, at med 2^24 filer er der ca.
> 2^47 forskellige måder at udtage et par af filer på. For
> hvert par er sandsynligheden for at de er ens på de 40
> bits 2^-40. Dermed burde der være ca. 2^7 kollisioner på
> de 40 bits. Nå, nu bliver jeg vist nødt til at tælle efter.

Jeg har lavet 12 kørsler med forskellige valg af de første 40
bits. Antallet af kollisioner på de første 40 bits og antal
kollisioner, der matchede på 95 eller flere bits var som
følger:

153 1
119 3
133 2
140 0
121 3
122 2
154 3
114 2
121 1
154 1
123 0
134 1

--
Kasper Dupont -- der bruger for meget tid på usenet.
For sending spam use mailto:aaarep@daimi.au.dk
for(_=52;_;(_%5)||(_/=5),(_%5)&&(_-=2))putchar(_);

---

Kasper Dupont <kasperd@daimi.au.dk> wrote:

>Den måde jeg regnede på var, at med 2^24 filer er der ca.
>2^47 forskellige måder at udtage et par af filer på. For
>hvert par er sandsynligheden for at de er ens på de 40
>bits 2^-40. Dermed burde der være ca. 2^7 kollisioner på
>de 40 bits. Nå, nu bliver jeg vist nødt til at tælle efter.

Det lyder overordentlig plausibelt, ikke mindst når vi nu har set at
du faktisk får ca. 2^7 hver gang

--
Jesper Dybdal, Denmark.
http://www.dybdal.dk (in Danish).