---

Hej.

Da jeg i aftes har været til et foredrag om kryptologi, er jeg lige kommet i
tanke om følgende spørgsmål. Måske nogle kender noget til det.

Er hashfunktioners (som MD5, SHA-1, etc.) output uniformt fordelt og
overholder den i øvrigt de statistiske tests som en tilfældighedsgenerator
også skal?

Jeg er lidt i tvivl, men hvis den nu ikke overholder dette - f.eks. hvis nu
man skal beskrive det meget simpelt: Lad os sige tekster med mange tal i
giver hashværdier der mest ligger i ét område - og tekster uden så mange tal
giver hashværdier i alle andre områder. Så kan man jo udelukkende på
hashværdien se noget information fra input-teksten, som det måske ikke var
meningen man skulle have lov til at se. Men på den anden side, selvom der er
sådanne tendenser for en hashfunktion, er de måske så komplicerede at man
ikke lige kan finde dem - og så er det vel ligemeget.
Foredragsholderen nævnte bl.a. også at en hashfunktion straks vil blive
trukket tilbage, hvis blot én eneste f.eks. finder to tekster der giver
samme output. Og der er vist mange som prøver på at finde sådanne fejl. Så
der er vel ret skarp kontrol med disse funktioner, kan man sige.

Selvom det ikke har så meget med kryptologi at gøre kunne et sjovt forsøg jo
være at lave en tilfældighedsgenerator utrolig simpelt - noget i retningen
af h(s) / h_max, hvor h betegner funktionen der giver hashværdien af input
(tilfældighedsgeneratorens frø) s (kaldes det ikke frø på dansk?) og h_max
er den maksimale outputværdi. Man kunne så enten udregne det iterativt, så
output blev input ved næste generering - eller man kunne lade s være et
index, der blot hver gang bliver forhøjet med én. Ville det være en god
tilfældighedsgenerator?

Mvh. Bjarke

---

"Bjarke Walling Petersen" <bwp.news@bwp.dk> writes:


> Da jeg i aftes har været til et foredrag om kryptologi, er jeg lige kommet i
> tanke om følgende spørgsmål. Måske nogle kender noget til det.
>
> Er hashfunktioners (som MD5, SHA-1, etc.) output uniformt fordelt og
> overholder den i øvrigt de statistiske tests som en tilfældighedsgenerator
> også skal?

Ja. Ellers ville de ikke vere "kryptografisk stærke".

> Jeg er lidt i tvivl, men hvis den nu ikke overholder dette - f.eks. hvis nu
> man skal beskrive det meget simpelt: Lad os sige tekster med mange tal i
> giver hashværdier der mest ligger i ét område - og tekster uden så mange tal
> giver hashværdier i alle andre områder. Så kan man jo udelukkende på
> hashværdien se noget information fra input-teksten, som det måske ikke var
> meningen man skulle have lov til at se.

Nemlig, så gode kryptografiske metoder sørger for at undgå denne slags
statistiske afhængigheder.

> Men på den anden side, selvom der er sådanne tendenser for en
> hashfunktion, er de måske så komplicerede at man ikke lige kan finde
> dem - og så er det vel ligemeget.

Kompleksitet er vigtig. Det er f.eks. nemt at bryde enhver public-key
kode (bare prøv alle mulige nøgler igennem), men det er
beregningsmæssigt kompliceret (dvs. tidskrævende). Konceptuel
kompleksitet er der dog ingen sikkerhed i, så hvis der er en svaghed i
en kode, skal den nok blive fundet.

> Foredragsholderen nævnte bl.a. også at en hashfunktion straks vil
> blive trukket tilbage, hvis blot én eneste f.eks. finder to tekster
> der giver samme output. Og der er vist mange som prøver på at finde
> sådanne fejl. Så der er vel ret skarp kontrol med disse funktioner,
> kan man sige.

Ja. Der findes selvfølgelig to tekster med samme hashnøgle, men
chancen for at man tilfældigt støder på et eksempel er _meget_ lille,
så et konkret eksempel må antages at være konstrueret ud fra en
svaghed i koden og ikke ved bare at prøve sig frem.

> Selvom det ikke har så meget med kryptologi at gøre kunne et sjovt
> forsøg jo være at lave en tilfældighedsgenerator utrolig simpelt -
> noget i retningen af h(s) / h_max, hvor h betegner funktionen der
> giver hashværdien af input (tilfældighedsgeneratorens frø) s (kaldes
> det ikke frø på dansk?) og h_max er den maksimale outputværdi. Man
> kunne så enten udregne det iterativt, så output blev input ved næste
> generering - eller man kunne lade s være et index, der blot hver
> gang bliver forhøjet med én. Ville det være en god
> tilfældighedsgenerator?

Du mener nok h(s) modulo hmax i.s.f. h(s)/hmax. Men, ja, det vil være
en udmærket tilfældighedsgenerator (sålænge den initielle værdi af s
er ukendt). Hvis du bruger den iterative metode, skal du lade den nye
s være h(s) inden du reducerer intervallet til 0 - hmax-1.

   Torben

---

Torben Ægidius Mogensen wrote:
> Konceptuel
> kompleksitet er der dog ingen sikkerhed i, så hvis der er en svaghed i
> en kode, skal den nok blive fundet.

Jeg er helt enig i at der ingen sikkerhed er i "konceptuel kopleksitet".
Men jeg er nu ikke enig i at svagheder nødvendigvis vil blive fundet.
Derfor kan man argumentere for at konceptuel kompleksitet faktisk giver
lavere sikkerhed...

Med venlig hilsen Preben

---

Preben Mikael Bohn <nospam@nospam.com> writes:

> Torben Ægidius Mogensen wrote:
> > Konceptuel
> > kompleksitet er der dog ingen sikkerhed i, så hvis der er en svaghed i
> > en kode, skal den nok blive fundet.
>
> Jeg er helt enig i at der ingen sikkerhed er i "konceptuel kopleksitet".
> Men jeg er nu ikke enig i at svagheder nødvendigvis vil blive fundet.

Hvis koden er udbredt nok, og der er tilstrækkeligt mange, der vil
have stor personlig fordel af at finde svagheder i den, så vil de
blive fundet før eller siden.

> Derfor kan man argumentere for at konceptuel kompleksitet faktisk giver
> lavere sikkerhed...

Heri er jeg enig. Det er langt nemmere at bevise sikkerhed (mod
bestemte typer af angreb) for simple kodningsmetoder. F.eks. kan man
nogle gange vise, at brydning af kode er mindst ligeså svært som
faktorisering af tal (kompleksiteten herfor er dog ikke er kendt).

   Torben

---

Torben Ægidius Mogensen wrote:
> Hvis koden er udbredt nok, og der er tilstrækkeligt mange, der vil
> have stor personlig fordel af at finde svagheder i den, så vil de
> blive fundet før eller siden.

Ikke nødvendigvis. Men til gengæld: Hvis der aldrig er nogen der finder
svagheden/erne så gør det jo heller ikke noget...

Med venlig hilsen Preben

---

Bjarke Walling Petersen wrote:
> Er hashfunktioners (som MD5, SHA-1, etc.) output uniformt fordelt
Det vil jeg tro, ellers er det en uhyre dårlig tilfældighedsgenerator.

> og overholder den i øvrigt de statistiske tests som en
> tilfældighedsgenerator også skal?
Jeg ved ikke hvilke statistiske tests du referere til.

En pseudo tilfældig generator vil generere en sekvens af tal der
næsten har de samme egenskaber som en sand tilfældig sekvens,
men da koden til sådan en generator har en endelig størrelse,
kan den aldrig være sand tilfældig.

I praksis kan du sample korrelationsfunktioner, før eller siden
vil du se en korrelation der er forskellige fra en sand tilfældigheds
generator der ikke har nogen korrelationer overhovedet.

Mht. enkryption er et mere relevant spørgsmål om koden kan brydes
inden for f.eks. 10^9 år. Om sekvensen så er sand eller pseudo-
tilfældig er irrelevant.

> Selvom det ikke har så meget med kryptologi at gøre kunne et sjovt forsøg
> jo være at lave en tilfældighedsgenerator utrolig simpelt - noget i
> retningen af h(s) / h_max, hvor h betegner funktionen der giver
> hashværdien af input (tilfældighedsgeneratorens frø) s (kaldes det ikke
> frø på dansk?) og h_max er den maksimale outputværdi. Man kunne så enten
> udregne det iterativt, så output blev input ved næste generering - eller
> man kunne lade s være et index, der blot hver gang bliver forhøjet med én.
> Ville det være en god tilfældighedsgenerator?

Prøv at udregne C(n)=<h(s[i])*h(s[i-n])> hvor du tager gennemsnit over i,
og hvor du sampler den for en række ofsets n.

Plotter du denne er C(0)=<h²> hvorimod C(n)=0 for n>1.

Det er den mest basale test, ud over at fordelingen af h(s) er flad.
Du kan så prøve C2(n,m)=<h(s[i])*h(s[i-n])*h(s[i-m])> osv.

--
Mvh. Carsten Svaneborg
http://www.softwarepatenter.dk

---

Bjarke Walling Petersen skrev

> Selvom det ikke har så meget med kryptologi at gøre kunne et sjovt forsøg
jo
> være at lave en tilfældighedsgenerator utrolig simpelt - noget i retningen
> af h(s) / h_max, hvor h betegner funktionen der giver hashværdien af input
> (tilfældighedsgeneratorens frø) s (kaldes det ikke frø på dansk?) og h_max
> er den maksimale outputværdi.

Jeg mener, at Numerical Recipies engang angav (og måske stadig angiver) en
metode hvor DES bruges til at generere tilfældige tal.

Mere generelt kan man sige, at man i forbindelse med "stream ciphers" ofte
benytter en eller anden form for kryptologisk sikker tilfældighedsgenerator.
Har man kun brug for tilfældige tal, kan man enten tage generator-delen af
en sådan krypteringsmetode, eller, med lidt forsigtighed, anvende
krypteringsmetoden direkte på et tilfældighedsfrø for dermed at generere en
tilfælding bitstrøm.


Mvh,
--
Filip Larsen