---

Hej NG

Jeg tænkte på om der ikke er måder at MD5 og SHA kan dekrypteres på?

Jeg er nysgerrig fordi jeg havde en diskussion med en kammerat der mente at
kan man kryptere må processen kunne vendes og dermed dekryptere.
Jeg mener bare at have hørt at MD5 og SHA er umulige(eller tilnærmelsesvis)
at dekryptere.

mhv. Henrik

---

In article <ammkgt$2tmk$1@news.cybercity.dk>, Henrik wrote:
>
> Jeg tænkte på om der ikke er måder at MD5 og SHA kan dekrypteres på?

MD5 og SHA1 er såkaldte digest-funktioner, det vil sige at de ikke
indeholder de oprindelige data, men en matematisk checksum beregnet på
disse data, så nej.

--
Andreas Plesner Jacobsen | Satire is tragedy plus time.
|    -- Lenny Bruce

---

Andreas Plesner Jacobsen wrote:
> MD5 og SHA1 er såkaldte digest-funktioner, det vil sige at de ikke
> indeholder de oprindelige data, men en matematisk checksum beregnet på
> disse data, så nej.

Hvis man har _masser_ af tid, kan man nok finde en _stor_ mænde af
mulige løsninger :)




--
Christian E. Lysel, http://www.spindelnet.dk/

---

> Hvis man har _masser_ af tid, kan man nok finde en _stor_ mænde af
> mulige løsninger :)

man kan jo altid brute_force... men jeg tænkte nærmere på hvis man
forestillede sig en simplificeret version...

Encode:

password=abc

ANSI(password) * 2 + 5

hvis vi siger at ansiværdien er 255 er det

255*2+5 =515

515-5=510/2= 255 = ANSIværdien... herefter skal man naturligvis finde ud af
hvilke bogstaver der giver denne værdi... men, er det helt i skoven? hvordan
fungerer MD5 ellers?

\Henrik

---

Hejsa Henrik kan du ikke svarer i nyhedsgruppen?

Henrik wrote:
>>Hvis man har _masser_ af tid, kan man nok finde en _stor_ mænde af
>>mulige løsninger :)
> man kan jo altid brute_force... men jeg tænkte nærmere på hvis man
> forestillede sig en simplificeret version...
>
> Encode:
>
> password=abc
>
> ANSI(password) * 2 + 5
>
> hvis vi siger at ansiværdien er 255 er det
>
> 255*2+5 =515
>
> 515-5=510/2= 255 = ANSIværdien... herefter skal man naturligvis finde
ud af
> hvilke bogstaver der giver denne værdi... men, er det helt i skoven?
hvordan
> fungerer MD5 ellers?

Det er mere over i en anden boldgade, eksempel,

password=abc

skrevet i decimaltal er abc = 97, 98, 99

Her kan en simpel hash funktion fx være summen af tallene , 97+98+99=294

Hvordan vil du komme fra 294 til 97, 98, 99?

"1+1+1+...+1 (294 gange)" vil være en gyldig løsning.
"1+1+1+...+1 (292 gange + 2" vil også være en gyldig løsning

Ovenstående er ikke en gennemgang af hverken MD5 eller SHA1, men blot et
eksempel på problemstillingen.

--
Christian E. Lysel, http://www.spindelnet.dk/

---

"Christian E. Lysel" <sunsite.dk.nntp@spindelnet.dk> writes:

> Ovenstående er ikke en gennemgang af hverken MD5 eller SHA1, men blot
> et eksempel på problemstillingen.

For klarhedens skyld er det måske værd at nævne at flere inputs til en
hashfunktion som fx MD5 godt kan give samme output. Funktionen er dog
designet så det sker (meget) sjældent.

En funktion der gjorde det modsatte af MD5 ville således ikke være
entydig. En hashfunktion er en envejs-funktion.

--
Jacob - www.bunk.cc
Some people have no respect for age unless it's bottled.

---

Jacob Bunk Nielsen <spam@bunk.cc> writes:

> For klarhedens skyld er det måske værd at nævne at flere inputs til en
> hashfunktion som fx MD5 godt kan give samme output. Funktionen er dog
> designet så det sker (meget) sjældent.

Men alligevel må der findes mindst en MD5-sum, der er frembragt af
uendelig mange forskellige strenge.

--
Morten Bakkedal

---

Morten Bakkedal <news20020825@bakkeland.dk> writes:

> Men alligevel må der findes mindst en MD5-sum, der er frembragt af
> uendelig mange forskellige strenge.

Jep, og hvis funktionen er god vil der sandsynligvis være uendeligt
mange frembringere for hvert muligt resultat. Det er bare så forbandet
svært at finde en af dem når man skal bruge den.
/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
'Faith without judgement merely degrades the spirit divine.'

---

Morten Bakkedal <news20020825@bakkeland.dk> writes:
> Jacob Bunk Nielsen <spam@bunk.cc> writes:
>
>> For klarhedens skyld er det måske værd at nævne at flere inputs til en
>> hashfunktion som fx MD5 godt kan give samme output. Funktionen er dog
>> designet så det sker (meget) sjældent.
>
> Men alligevel må der findes mindst en MD5-sum, der er frembragt af
> uendelig mange forskellige strenge.

Ja, naturligvis.

Jeg burde nok have tilføjet et "i praksis" til sidst i den citerede
tekst, så sætningen sluttede "... sker (meget) sjældent i praksis".

--
Jacob - www.bunk.cc
It's hard to be humble when you're perfect.

---

Henrik wrote:

> Jeg er nysgerrig fordi jeg havde en diskussion med en kammerat der mente at
> kan man kryptere må processen kunne vendes og dermed dekryptere.

Det er ikke sikkert. Tag f.eks. modulus (rest) operatoren: x divideret med 10
giver rest 5. Man kan ud fra den oplysning finde uendeligt mange værdier af x,
der passer, men man kan ikke vide hvilken værdi, der oprindeligt blev brugt.
Bruger man større tal og har "mange" rest-beregninger, skal man sammenligne
(tilnærmelsesvis) uendeligt mange mulige løsninger til "mange" beregninger for
at finde én løsning, der passer til alle rest-beregningerne.
- Og det er så bare et simpelt eksempel...

M.v.h.

Jonathan

--
Nyt alternativ til egen server: JSP Enterprise hotel med adgang til
Enterprise Java Beans, egen Java Virtual Machine og egen IP-adresse
(giver mulighed for eget SSL-certifikat).
http://www.jsp-hotel.dk/

---

In article <ammkgt$2tmk$1@news.cybercity.dk>, Henrik wrote:
> Hej NG
>
> Jeg tænkte på om der ikke er måder at MD5 og SHA kan dekrypteres på?
>
> Jeg er nysgerrig fordi jeg havde en diskussion med en kammerat der mente at
> kan man kryptere må processen kunne vendes og dermed dekryptere.
> Jeg mener bare at have hørt at MD5 og SHA er umulige(eller tilnærmelsesvis)
> at dekryptere.

Selvfølgelig kan du dekryptere en MD5 sum. MD5 er jo en suveræn
komprimeringsalgoritme. Uanset hvor mange gigabytes af data du
hælder ind i den, så fylder resultatet kun 128 bit.

Så i stedet for at downloade 650MB store ISO images downloader du
bare md5sum filen, og rekonstruerer dem.

Hvis du i stedet mener om det er muligt at lave et statistiks angreb på
en klartekst, ja så er det. Hvis du ved at det du har en sum af er en
engelsk tekst på omkring en side, så kan du prøve alle mulige
engelske ordkombinationer indtil du rammer rigtigt.

---

"Povl H. Pedersen" <povlhp@povl-h-pedersens-computer.local> writes:

> Hvis du ved at det du har en sum af er en engelsk tekst på omkring
> en side, så kan du prøve alle mulige engelske ordkombinationer
> indtil du rammer rigtigt.

Her skal "du" naturligvis læses som "dig og alle dine efterkommere et
par tusinde generationer frem" :).

(Hurtigt skøn: der er ca. 2000 tegn på en side, et engelsk ord er
ca. fem tegn i gennemsnit (højt skud), og der er 1.5 tegn mellem dem
(mellemrum og punktuering). Det giver ca. 300 ord per side. Vi er
flinke og sætter det til 200. Lad os sige at der er 1000 ord i
almindeligt brug på engelsk (meget lavt sat), så bliver der 1000^200
mulige kombinationer af ord på en side ... det vil tage lang tid at nå
igennem dem. Det er dog bedre end de 39^2000 forskellige kombinationer
af bogstaver, tal, mellemrum, komma og puntum :).)

/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
'Faith without judgement merely degrades the spirit divine.'

---

In <wupccwtc.fsf@hotpop.com> Lasse Reichstein Nielsen <lrn@hotpop.com> writes:

>"Povl H. Pedersen" <povlhp@povl-h-pedersens-computer.local> writes:

>> Hvis du ved at det du har en sum af er en engelsk tekst på omkring
>> en side, så kan du prøve alle mulige engelske ordkombinationer
>> indtil du rammer rigtigt.

>Her skal "du" naturligvis læses som "dig og alle dine efterkommere et
>par tusinde generationer frem" :).

>(Hurtigt skøn: der er ca. 2000 tegn på en side, et engelsk ord er
>ca. fem tegn i gennemsnit (højt skud), og der er 1.5 tegn mellem dem
>(mellemrum og punktuering). Det giver ca. 300 ord per side. Vi er
>flinke og sætter det til 200. Lad os sige at der er 1000 ord i
>almindeligt brug på engelsk (meget lavt sat), så bliver der 1000^200
>mulige kombinationer af ord på en side ... det vil tage lang tid at nå
>igennem dem. Det er dog bedre end de 39^2000 forskellige kombinationer
>af bogstaver, tal, mellemrum, komma og puntum :).)

Der findes jo "kun" 2^128 forskellige MD5-summer, hvis jeg husker
rigtigt, saa rigtige mange forskellige engelske tekster paa en side,
vil have den "rigtige" md5-sum.

/Martin

---

> Så i stedet for at downloade 650MB store ISO images downloader du
> bare md5sum filen, og rekonstruerer dem.

årh ja - hvor smart... okay, jeg har den... jeg lader være med at stille
spørgsmål der åbentlyst udstiller mig som en snotskovl

men, tak alligevel 8)

\Henrik

---

In article <amnv65$1ikc$1@news.cybercity.dk>, Henrik wrote:
>
>> Så i stedet for at downloade 650MB store ISO images downloader du
>> bare md5sum filen, og rekonstruerer dem.
>
> årh ja - hvor smart... okay, jeg har den... jeg lader være med at stille
> spørgsmål der åbentlyst udstiller mig som en snotskovl
>
> men, tak alligevel 8)

Du er velkommen.

Det er lidt i samme stil med dem der siger at de har en krypterings-
algoritme som kan komprimere ALT til halv størrelse.

Så kan man vel bare køre output igennem igen og igen til
man har komprimeret data ned til 1 bit.

---

On Mon, 23 Sep 2002 10:51:43 +0200, "Henrik"
<henrik@REMOVE_MEhejboel.dk> wrote:

>Hej NG
>
>Jeg tænkte på om der ikke er måder at MD5 og SHA kan dekrypteres på?
>
>Jeg er nysgerrig fordi jeg havde en diskussion med en kammerat der mente at
>kan man kryptere må processen kunne vendes og dermed dekryptere.
>Jeg mener bare at have hørt at MD5 og SHA er umulige(eller tilnærmelsesvis)
>at dekryptere.
>
>mhv. Henrik
>

MD5 og SHA er hash algoritmer, der kan anvendes til at bestemme en
hash værdi.

Resultatet af en MD5 operation på en given mængde data, vil være
128 bits lang (10^38 mulige hash værdier).

Eksempel:
MD5String('Kan MD5 og SHA dekrypteres?') =
c92b1c0035061dae0910226cab6773fa

Ændrers data sker følgende:

MD5String('Kan MD5 og SHA dekrypteres!') =
79d48604ad316a2380c89ba8012d6b82

Hash værdierne er ikke længere ens!

MD5 hash værdien af A er:
MD5String('A') = 7fc56270e7a70fa81a5935b72eacbe29

En god hash algoritme er en funktion, hvor det vil være overordentlig
svært at ændre i meddelelsen, der sendes til en modtager uden at hash
værdien også ændres. En god hash funktioner er kendetegnet ved, at
have en god avalanche effekt. Det betyder, at ca. halvdelen af bittene
i hashværdien ændres hvis bare én bit ændres i data. Det skal
ligeledes være overordentlig svært at finde to meddelelser, der giver
samme hash værdi.

Jeg mener ikke at MD5 har vist nogen svagheder endnu, men der er måske
én, out there, der har hørt om én, der har påvist en svaghed?

Jeg ved ikke om du evt. tænker på at man typisk krypterer hash værdien
med en privat RSA nøgle og dekrypterer med en offentlig nøgle? I dette
tilfælde mener jeg godt, man kan SIGE at man dekrypterer MD5 eller
SHA.

Venlig hilsen
Jan

---

Jan Beyer wrote:
||
|| Jeg mener ikke at MD5 har vist nogen svagheder endnu, men der er
|| måske én, out there, der har hørt om én, der har påvist en svaghed?
||

MD5 er ihvertfald ikke blevet brudt (ie. man kan ikke konstruere en besked
med en på forhånd fastlagt hash værdi, eller danne 2 beskeder med samme
hashværdi).

Til gengæld er der vist nogle svagheder i den komprimeringsrutine der
anvendes.

Prøv at se på: http://home.clara.net/scramdisk/pgpfaq.html#SubMD5Broke

Jeg håber at andre her i gruppen med væsentlig større viden om kryptering
end jeg, der kan give nogle kommentarer til dette.

/Freeman

---

In article <amvui5$6i2$1@sunsite.dk>, FreeMan wrote:
>||
>|| Jeg mener ikke at MD5 har vist nogen svagheder endnu, men der er
>|| måske én, out there, der har hørt om én, der har påvist en svaghed?
>||
>
> MD5 er ihvertfald ikke blevet brudt (ie. man kan ikke konstruere en besked
> med en på forhånd fastlagt hash værdi, eller danne 2 beskeder med samme
> hashværdi).

Med tilstrækkelig tid kan man godt, men der er ikke nogen generiske
metoder til det, nej.

--
Andreas Plesner Jacobsen | perfect guest:
| One who makes his host feel at home.

---

"Andreas Plesner Jacobsen" <apj@daarligstil.dk> wrote in message
news:slrnap801s.n3h.apj@slartibartfast.nerd.dk...
> In article <amvui5$6i2$1@sunsite.dk>, FreeMan wrote:
> >||
> >|| Jeg mener ikke at MD5 har vist nogen svagheder endnu, men der er
> >|| måske én, out there, der har hørt om én, der har påvist en svaghed?
> >||
> >
> > MD5 er ihvertfald ikke blevet brudt (ie. man kan ikke konstruere en
besked
> > med en på forhånd fastlagt hash værdi, eller danne 2 beskeder med samme
> > hashværdi).
>
> Med tilstrækkelig tid kan man godt, men der er ikke nogen generiske
> metoder til det, nej.

Det glemte jeg lige at få med. Det er selvfølgelig en ret vigtig pointe. Har
man tid nok, kan man selvfølgelig prøve sig frem.

Tak for rettelsen.

/Freeman

---

FreeMan wrote:
>
> "Andreas Plesner Jacobsen" <apj@daarligstil.dk> wrote in message
> news:slrnap801s.n3h.apj@slartibartfast.nerd.dk...
> > In article <amvui5$6i2$1@sunsite.dk>, FreeMan wrote:
> > >||
> > >|| Jeg mener ikke at MD5 har vist nogen svagheder endnu, men der er
> > >|| måske én, out there, der har hørt om én, der har påvist en svaghed?
> > >||
> > >
> > > MD5 er ihvertfald ikke blevet brudt (ie. man kan ikke konstruere en
> besked
> > > med en på forhånd fastlagt hash værdi, eller danne 2 beskeder med samme
> > > hashværdi).
> >
> > Med tilstrækkelig tid kan man godt, men der er ikke nogen generiske
> > metoder til det, nej.
>
> Det glemte jeg lige at få med. Det er selvfølgelig en ret vigtig pointe. Har
> man tid nok, kan man selvfølgelig prøve sig frem.

Et bruteforce angreb kan nemt udføres, hvis man har ca. 256EB harddisk plads.
Der skal udføres en sortering, som vil kræve at alle data læses og skrives 3
gange. Med en overførselshastighed på 133MB/s vil det dermed tage ca.
400 000 år. Et bruteforce angreb kan udføres med mindre diskplads, men så
tager det længere tid.

256EB svarer til ca. 1.7mia 160GB harddiske, og med et distribueret system
kan man nok gøre algoritmen hurtigere da alle harddiske kan arbejde på
samme tid, til gengæld får man et problem med at flytte data mellem maskinerne.

Det er stadig urealistisk, men om ti år er det måske mere realistisk at
bryde md5 ved bruteforce.

--
Kasper Dupont -- der bruger for meget tid på usenet.
For sending spam use mailto:aaarep@daimi.au.dk
or mailto:mcxumhvenwblvtl@skrammel.yaboo.dk

---

In article <3D94302F.159F47F7@daimi.au.dk>, Kasper Dupont wrote:
>> Det glemte jeg lige at få med. Det er selvfølgelig en ret vigtig pointe. Har
>> man tid nok, kan man selvfølgelig prøve sig frem.
>
> Et bruteforce angreb kan nemt udføres, hvis man har ca. 256EB harddisk plads.
> Der skal udføres en sortering, som vil kræve at alle data læses og skrives 3
> gange. Med en overførselshastighed på 133MB/s vil det dermed tage ca.
> 400 000 år. Et bruteforce angreb kan udføres med mindre diskplads, men så
> tager det længere tid.
>
> 256EB svarer til ca. 1.7mia 160GB harddiske, og med et distribueret system
> kan man nok gøre algoritmen hurtigere da alle harddiske kan arbejde på
> samme tid, til gengæld får man et problem med at flytte data mellem maskinerne.

Hvorfor skal man bruge diske ? De er ikke tidssvarende. En maskine som
www.google.com har eksempelvis databasen i RAM på en flok unix
æsker.

---

"Povl H. Pedersen" wrote:
>
> In article <3D94302F.159F47F7@daimi.au.dk>, Kasper Dupont wrote:
> >> Det glemte jeg lige at få med. Det er selvfølgelig en ret vigtig pointe. Har
> >> man tid nok, kan man selvfølgelig prøve sig frem.
> >
> > Et bruteforce angreb kan nemt udføres, hvis man har ca. 256EB harddisk plads.
> > Der skal udføres en sortering, som vil kræve at alle data læses og skrives 3
> > gange. Med en overførselshastighed på 133MB/s vil det dermed tage ca.
> > 400 000 år. Et bruteforce angreb kan udføres med mindre diskplads, men så
> > tager det længere tid.
> >
> > 256EB svarer til ca. 1.7mia 160GB harddiske, og med et distribueret system
> > kan man nok gøre algoritmen hurtigere da alle harddiske kan arbejde på
> > samme tid, til gengæld får man et problem med at flytte data mellem maskinerne.
>
> Hvorfor skal man bruge diske ? De er ikke tidssvarende. En maskine som
> www.google.com har eksempelvis databasen i RAM på en flok unix
> æsker.

Fordi jeg tror 256EB harddisk er billigere end 256EB RAM.

--
Kasper Dupont -- der bruger for meget tid på usenet.
For sending spam use mailto:aaarep@daimi.au.dk
or mailto:mcxumhvenwblvtl@skrammel.yaboo.dk

---

On Fri, 27 Sep 2002 10:34:46 +0200, FreeMan <bkb18633a@post.cybercity.dk> wrote:
> Det glemte jeg lige at få med. Det er selvfølgelig en ret vigtig pointe. Har
> man tid nok, kan man selvfølgelig prøve sig frem.
>

Definer tid nok. Hvis du skal benytte 10*universets levealder, så er det
nok ikke muligt at bryde det via brute force. MD5 er sandsynligvis
svagere end SHA1, da der eksisterer et par teoretiske angrebsmetoder.
Schneier kan ikke lide den, da dens kompressionsfunktion har været
benyttet til at skabe kollisioner.

--
Jesper

---

Jesper Louis Andersen wrote:
>
> On Fri, 27 Sep 2002 10:34:46 +0200, FreeMan <bkb18633a@post.cybercity.dk> wrote:
> > Det glemte jeg lige at få med. Det er selvfølgelig en ret vigtig pointe. Har
> > man tid nok, kan man selvfølgelig prøve sig frem.
> >
>
> Definer tid nok. Hvis du skal benytte 10*universets levealder, så er det
> nok ikke muligt at bryde det via brute force. MD5 er sandsynligvis
> svagere end SHA1, da der eksisterer et par teoretiske angrebsmetoder.

Min vurdering er at MD5 kan brydes på nogle 100 000 år med nuværende
computeres hastighed, hvis man ellers kunne finde diskcapacitet nok.
SHA1 vil nok kræve ca. 82 000 gange så meget diskplads og tid at
bryde ved brute force.

--
Kasper Dupont -- der bruger for meget tid på usenet.
For sending spam use mailto:aaarep@daimi.au.dk
or mailto:mcxumhvenwblvtl@skrammel.yaboo.dk