Zoek- en sorteeralgoritmen en hashing Femke Berendsen (3689301) en Merel van Schieveen (3510190) 9 april 2013
1
Inhoudsopgave 1 Inleiding
3
2 Zoek- en sorteeralgoritmen 2.1 Grote O notatie . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Zoekalgoritmen . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Sorteermethoden . . . . . . . . . . . . . . . . . . . . . . . . .
3 3 3 4
3 Hashfuncties 3.1 Inleiding . . . . 3.2 Herbruikbaar . 3.3 Onomkeerbaar 3.4 Vaste Lengte . 3.5 Geen Collisions
. . . . .
5 5 5 5 6 6
output-lengte van MD5 (128 bit) Het Hexadecimaal systeem . . . . . . . . . . . . . . . . . . . . Het Binaire systeem . . . . . . . . . . . . . . . . . . . . . . . Collision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6 6 7 8
4 De 4.1 4.2 4.3
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
5 Het verjaardagsprobleem
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
9
6 Conclusie
11
7 Opgaven 12 7.1 Opgave 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 7.2 Opgave 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 7.3 Opgave 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2
1
Inleiding
Het kan voorkomen dat je een enorme lijst met data hebt waarin je ´e´en bepaald gegeven zoekt. Dit kan zijn een lijst met namen van mensen, of een bepaald getal. Om zo’n gegeven te zoeken zijn talloze mogelijkheden. In de informatica zijn verschillende algoritmen ontwikkeld om dit te doen. In dit verslag zullen we ingaan op deze zoek- en sorteeralgoritmen. Iedereen heeft er mee te maken: steeds meer dingen gebeuren via internet. Waar vroeger nog een brief gestuurd werd, wordt nu een mail verzonden. Zaken waar je vroeger nog voor naar de bank moest, zijn nu allemaal via internet te regelen. Dit is heel handig, maar ook enigszins gevaarlijk. Als er geen goede beveiliging is van deze zaken kan hier flink misbruik van gemaakt worden. Daarom is het noodzakelijk dat vertrouwelijke informatie die via internet verzonden wordt veilig versleuteld is. Ook moet er een goede manier zijn om wachtwoorden op te slaan: als bij een website wordt ingebroken, mag het niet zo zijn dat zomaar alle vertrouwelijke informatie of wachtwoorden zichbaar zijn. Wel moet het zo zijn dat een website kan herkennen of iemand het goede wachtwoord invoert. Hoe zorg je nou dat je met een wachtwoord veilig naar binnen kan, zonder dat het ergens opgeslagen staat? Hier liggen veel wiskundige methoden aan ten grondslag. In dit verslag zullen we uitleggen welke methoden hieraan ten grondslag liggen.
2 2.1
Zoek- en sorteeralgoritmen Grote O notatie
De grote O notatie wordt in de informatica gebruikt om een tijdsindicatie voor een bepaald algoritme te geven. Hierbij wordt uitgegaan van het slechtste geval. Stel dat een algoritme op zijn langst n stappen nodig heeft om tot een oplossing te komen, dan wordt de geschatte tijd voor dat algoritme gegeven door O(n). Bij de volgende algoritmen zullen we ook bekijken wat de tijd is die de algoritmen nodig hebben, en daarbij deze notatie gebruiken.
2.2
Zoekalgoritmen
We zullen twee verschillende zoekalgoritmen bekijken, namelijk Lineair zoeken en Binair zoeken.
3
Bij Lineair zoeken bekijk je het eerste element in de lijst en bekijk je vervolgens elk volgend element totdat het gezochte element gevonden is. Wanneer de data n elementen bevatten is de benodigde tijd van dit algoritme O(n). Wanneer n heel groot is kan het zoekproces dus heel erg lang duren. Lineair zoeken kan worden gebruikt om een ongesorteerde lijst te doorzoeken. Wanneer een lijst wel gesorteerd is, wordt het zoekproces al een stuk eenvoudiger. Wanneer de lijst gesorteerd is kunnen we Binair zoeken. Bij dit algoritme zijn de data gesorteerd (bijvoorbeeld van klein naar groot, of van A naar Z) en wordt het gezochte gegeven gevonden door halvering van de data. We nemen een gesorteerde rij data en bekijken de middelste waarde. Wanneer deze kleiner is dan de gezochte waarde bekijken we de helft die groter is dan deze waarde, wanneer deze groter is dan de gezochte waarde bekijken we de helft die kleiner is dan deze waarde. Vervolgens voeren we op die helft weer hetzelfde uit. Zo krijg je een proces waarbij je steeds de zoekruimte halveert en uiteindelijk de goede waarde vindt. Omdat je elke keer halveert, is de tijd die het algoritme nodig heeft is maximaal log2 (n) dus dit algoritme heeft tijd O(log n).
2.3
Sorteermethoden
Voordat we binair kunnen zoeken moeten we eerst de rij data nog sorteren. Hiervoor zijn ook twee algoritmen die we zullen behandelen, namelijk Insertion sort en Merge sort. Bij Insertion sort bekijk je de twee eerste elementen en zet je die op volgorde. Vervolgens bekijk je het volgende element in de rij en kijk je waar deze in het gesorteerde rijtje moet, en zo verder met alle elementen. Voor ieder afzonderlijk element moet je het gesorteerde rijtje af om te kijken waar dit element hoort te staan, en dit moet je doen voor alle n elementen. Daarom is de tijd die dit algoritme nodig heeft O(n2 ). Een ander sorteeralgoritme is Merge sort. Bij dit algoritme verdeel je de rij data in twee rijen, die twee rijen halveer je ook weer, en dit doe je net zo lang totdat je allemaal rijen met ´e´en element overhoudt. Vervolgens ga je deze rijen weer twee aan twee samenvoegen. Hiervoor bekijk je uit elk van de twee rijtjes het voorste element, om te bepalen welk element eerst moet. Zo voeg je alle rijen weer samen en krijg je uiteindelijk een gesorteerde rij met 4
data. Voor het bepalen welk element eerst moet bekijk je alle elementen, dit is dus O(n), en er moeten log(n) keer rijen samengevoegd worden dus de totale tijd van dit algoritme is O(n log n).
3 3.1
Hashfuncties Inleiding
Het is belangrijk om veilig te kunnen internetten. Er zijn veel hackers actief die op internet zoeken naar wachtwoorden van mensen, zodat ze bijvoorbeeld geld van hun bankrekening af kunnen halen. Daarom is het belangrijk dat er een goede beveiliging is op internet, en een goede manier om wachtwoorden op te slaan. Als een wachtwoord gewoon op internet opgeslagen wordt, is het voor hackers heel makkelijk om er achter te komen wat je wachtwoord is. Verder heeft de aanvaller dan niet alleen de wachtwoorden van alle geregisteerden op deze website, maar misschien ook de wachtwoorden van deze mensen voor andere websites, als mensen hetzelfde wachtwoord voor meerdere websites gebruiken. Daarom is het belangrijk dat een wachtwoord op zo’n manier wordt opgeslagen, dat niet makkelijk (of helemaal niet) te achterhalen is wat het wachtwoord oorspronkelijk was. Het wachtwoord moet dus op zo’n manier vervormd worden dat na vervorming niet meer te zien is wat het wachtwoord was. Functies die hiervoor gebruikt worden, worden hashfuncties genoemd. Maar aan welke eigenschappen moet zo’n hashfunctie eigenlijk voldoen?
3.2
Herbruikbaar
Ten eerste willen we dat de hashfunctie voor dezelfde input ook altijd dezelfde output, ook wel hash genoemd, geeft. Het orginele wachtwoord wordt namelijk niet opgeslagen, alleen de hash van het wachtwoord wordt opgeslagen. Dus als hetzelfde wachtwoord niet altijd dezelfde hashes geeft, wordt je wachtwoord niet geaccepteerd, en zul je niet kunnen inloggen.
3.3
Onomkeerbaar
Een bekende versleuteling is de Caesarrotatie. Julius Caesar versleutelde zijn berichten door de A te vervangen door de D, de B door de E enzovoort. Deze manier van versleuteling kan weergegeven worden in de volgende formule: E(x) = (x + 3)
5
mod 26
Hierbij is x de plaats van de letter in het alfabet, en E(x) de plaats in het alfabet van de versleutelde letter. Hierbij staat A op plaats 0 en Z op plaats 25. Dus voor het wachtwoord 0 W ACHT W OORD0 , zal 0 ZDF KW ZRRU G0 opgeslagen worden. Om deze manier van versleutelen te ontcijferen is echter niet moeilijk. Daarom wordt deze bekende methode ook niet meer gebruikt. Een andere belangrijke eigenschap van de hashfunctie is dus dat het versleutelde wachtwoord niet terug te rekenen is naar het orginele wachtwoord.
3.4
Vaste Lengte
Wat in het voorbeeld over Caesarrotatie ook goed te zien is, is dat de lengte van het versleutelde wachtwoord informatie kan geven over de lengte van het originele wachtwoord. In het voorbeeld is namelijk de lengte van het versleutelde wachtwoord gelijk aan de lengte van het originele wachtwoord. We willen dus dat lengte van de hash (de output van de hashfunctie) geen enige informatie geeft over het originele wachtwoord. We stellen daarom de voorwaarde dat de hash altijd dezelfde lengte heeft, ongeacht de input.
3.5
Geen Collisions
De laatste belangrijke eigenschap van een hashfunctie is dat er geen collisions mogen voorkomen. Dit betekent dat er niet dezelfde hash mag uitkomen voor verschillende wachtwoorden. Dit komt later nog uitgebreider aan bod.
4
De output-lengte van MD5 (128 bit)
MD5 is een veelgebruikte hashfunctie met een 128 bit hashwaarde. MD5 is ontworpen door Ronald Rivest in 1991 om de voorgaande hashfunctie MD4 te vervangen. MD5 is een 128 bit functie, we zullen uitwerken wat dit precies inhoudt.
4.1
Het Hexadecimaal systeem
MD5 gebruikt het hexadecimaal systeem. Het hexadecimaal systeem is een getalstelsel met niet 10 tekens als basis, wat het geval is bij ons normale getalstelsel, maar het heeft een basis van 16 tekens. De cijfers 0 tot en met 9 worden aangevuld met A tot en met F , die ook wel gezien kunnen worden als 10 tot en met 15.
6
Voorbeeld 53F 2A9C = 5 × 166 + 3 × 165 + 15 × 164 + 2 × 163 + 10 × 162 + 9 × 161 + 12 × 160 = 88, 025, 756
4.2
Het Binaire systeem
De computer werkt echter met het binaire systeem, en niet met het hexadecimaal systeem. Met het binaire systeem, ookwel het tweetallige systeem genoemd, worden getallen weergegeven door een rijtje met alleen de tekens 0 en 1. In dit binaire systeem worden 0 en 1 ook wel bits genoemd. MD5 is een 128-bit hashfunctie, dit betekent dat de hashfunctie een output van 128 nullen of enen genereert. De output die uiteindelijk gegeven wordt, de hash, is echter in het hexadecimaal getalsysteem. De binaire output wordt dus nog omgezet naar een hexadecimaal getal. Nu is de vraag hoe we van het binaire getalstelsel naar het hexadecimaal getalstelsel omrekenen. Het hexadecimaal getalstelsel bestaat uit 0 tot en met 9 en A tot en met F , ofwel 0 tot en met 15. Het grootste getal 15 kun je schrijven als 15 = 8 + 4 + 2 + 1 = 1 × 23 + 1 × 22 + 1 × 21 + 1 × 20 ofwel 1111 in het binaire stelsel. Er zijn dus minstens 4 digits nodig om een teken van het hexadecimaal stelsel om te zetten in het binaire stelsel. Hoe de andere tekens van het hexadecimaal stelsel uitgedrukt kunnen worden in het binaire stelsel is weergegeven in de onderstaande tabel.
7
Binair 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
Decimaal 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Hexadecimaal 0 1 2 3 4 5 6 7 8 9 A B C D E F
Voorbeeld 0101 − 0011 − 1111 − 0010 − 1010 − 1001 − 1100 = 5 − 3 − 15 − 2 − 10 − 9 − 12 = 53F 2A9C Elke teken uit het hexadecimaalstelsel heeft dus 4 digits nodig, ofwel 4 bits. MD5 is een 128-bit hashfunctie en geeft als output dus 128 digits. Als deze 128 digits omgezet worden naar een hexadecimaal getal, zijn er dus 128 4 = 32 tekens van het hexadecimaal systeem als output. De hash bestaat dus uit 32 tekens.
4.3
Collision
Zoals hiervoor aangetoond bestaat een hash uit 32 tekens uit het hexadecimaalstelsel. Voor alle 32 plekken zijn dus 16 mogelijke tekens. Het aantal mogelijke hashes is dus: 1632 = 340, 282, 366, 920, 938, 463, 463, 374, 607, 431, 768, 211, 456 De kans dat twee verschillende inputs dezelfde output geeft zou dus bijna onmogelijk zijn. Maar dan moeten wel alle mogelijke hashes gebruikt worden. Een perfecte hashfunctie zou dus zo ontworpen moeten worden dat de 8
hashes uniform worden verdeeld over de output-ruimte. We hebben gezien dat er ontzettend veel mogelijke hash-waarden zijn, en dat daarom de kans dat twee verschillende wachtwoorden dezelde hash-waarden geven heel klein is. Wanneer dit toch het geval is, dan worden deze twee wachtwoorden een collision genoemd (letterlijke vertaling: botsing). Toch gebeurd het wel eens dat er sprake is van een collision. Hoe dit komt, zullen we uitleggen aan de hand van het verjaardagsprobleem.
5
Het verjaardagsprobleem
Stel je hebt een groep van k mensen, en we gaan bekijken hoe groot de kans is dat twee van die mensen op dezelfde dag jarig zijn. Gegeven de functie f , willen we dus x en y vinden zodat f (x) = f (y) met f een functie die de dag aangeeft dat persoon x jarig is. Het paar (x, y) heet dan een collision. Wanneer er 366 mensen zijn, is de kans dat er twee mensen tegelijk jarig zijn 100%. Wanneer we een groep hebben van k mensen, hebben we k2 verschillende combinaties van 2 mensen. De kans dat een persoon op een 1 bepaalde dag jarig is, is 365 , we gaan er dus vanuit dat iedere dag evenveel kans heeft. Wat is de kleinste waarde van k, zodanig dat de kans dat ten minste twee mensen in een groep van k mensen op dezelfde dag jarig zijn, groter is dan 0, 5? We definieren P (n, k) = P [minstens ´e´en duplikaat per k items, waarbij elk item een waarde tussen 1 en n aan kan nemen die allen even waarschijnlijk zijn]. We zoeken dus naar de kleinste waarde van k zodat P (365, k) > 0, 5. De kans dat er geen duplikaten zijn definieren we als Q(365, k). Als k > 365 dan is het onmogelijk dat alle waarden verschillen. Daarom nemen we aan dat k ≤ 365. We beschouwen nu het aantal verschillende manieren N dat we k waarden zonder duplicaten kunnen hebben. We zien dat N = 365 × 365! 364 × · · · × (365 − k + 1) = (365−k)! . Als we stellen dat er wel duplikaten mogen zijn dan is het aantal totale mogelijkheden 365k . De kans dat er geen duplicaten zijn is dus 365!/(365−k)! manieren zonder duplicaten N 365! Q(365, k) = AantalTotaal = 365 = (365−k)!365 k = k aantal manieren 365k 365! en P (365, k) = 1 − Q(365, k) = 1 − (365−k)!365 k. Voor k = 23 geldt dat P (365, 23) = 0.5073. Er zijn dus maar 23 mensen nodig om een kans van 0.5 te hebben dat twee mensen op dezelfde dag jarig zijn. Als k = 41 is deze kans al meer dan 0.9. We zien dus dat de kans op
9
twee mensen op dezelfde dag jarig al heel snel heel erg groot wordt, terwijl de groep mensen dan niet eens heel erg groot is. We kunnen het verjaardagsprobleem generaliseren tot het volgende probleem: gegeven een random variabele die een gehele waarde aanneemt tussen 1 en n, en k waarden (met k ≤ n) van de random variabele. Wat is de kans P (n, k) dat er minstens ´e´en duplikaat is? Het verjaardagsprobleem is een speciaal geval, met n = 365. Net als hiervoor hebben we weer n! P (n, k) = 1 − (n−k)!n k . We kunnen dit herschrijven als n×(n−1)×···×(n−k+1) nk n n−1 = 1 − ( n × n × · · · × n−(k−1) ) n = 1 − (1 − n1 ) × (1 − n2 ) × ... × (1 − k−1 n ) −x Met de ongelijkheid (1 − x) ≤ e krijgen
P (n, k) = 1 −
we dan: P (n, k) = 1 − (1 − n1 ) × (1 − n2 ) × ... × (1 − k−1 n ) 1
2
k−1
≥ 1 − e− n e− n . . . e− n k−1 1 1 = 1 − e−( n + n +···+ n ) = 1 − e−k(k−1)/2n
We willen nu weten voor welke k geldt dat P (n, k) > 0.5. Hiervoor lossen we de gelijkheid P (n, k) = 12 op. Dan geldt 1 −k(k−1)/2n 2 =1−e k(k−1)/2n 2=e ln(2) = k×(k−1) 2n Voor we k × (k − 1) vervangen door k 2 en krijgen we √ grote k kunnen √ √ k = 2n ln 2 = 1, 18 n ≈ n. We kunnen dit controleren door ons verjaardagsprobleem weer in te voe√ ren, als we n = 365 nemen krijgen we k = 1, 18 × 365 = 22, 54, wat heel erg dicht bij 23 ligt. De verjaardagsaanval kunnen we nu ook toepassen op hashfuncties. We bekijken in het bijzonder weer MD5, dit is een 128 bit hashfunctie. Deze functie heeft dan 2128 mogelijke uitvoerwaarden. Als MD5 wordt toegepast op k willekeurige invoerwaarden, kunnen we bekijken wat k minimaal moet zijn om te zorgen dat er een kans van minstens ´e´en duplicaat bestaat. Met √ de benadering van hierboven vinden we dan dat k = 2128 = 2128/2 = 264 . Je zou in eerste instantie denken dat een hashfunctie heel veilig is. Met
10
een bericht M heb je hash H(M ), je moet dus een M 0 zoeken waarvoor geldt H(M ) = H(M 0 ). Er zijn ontzettend veel hashwaarden, maar zoals we hierboven gezien hebben hoef je dus ’maar’ 264 waarden in te voeren om een redelijke kans op een collision te hebben. Gegeven een bepaalde hashwaarde, is het dus mogelijk om een wachtwoord te vinden met dezelfde hashwaarde. Hier kan dan misbruik van gemaakt worden. Oorschot en Wiener ontworpen in 1994 een 10 miljoen dollar kostende botsing-zoekmachine voor MD5. Deze machine was in staat om in 24 dagen een collision te vinden. Hierdoor was MD5 niet meer zo veilig als eerst gedacht. Er worden nog steeds nieuwe hashfuncties ontwikkeld om hackers voor te blijven.
6
Conclusie
De beveiliging van wachtwoorden is tot op heden nog steeds in volle ontwikkeling. Hashfuncties worden steeds beter maar hackers slagen er toch steeds weer in om misbruik te maken van de imperfecties van deze functies. Door betere computers wordt de rekentijd ook steeds korter en is het voor hackers makkelijker om achter wachtwoorden te komen. Het is daarom belangrijk om voorzichtig te zijn op internet!
11
7 7.1
Opgaven Opgave 1
Gegeven de volgende rij met getallen: 65, 81, 66, 74, 44, 79, 91, 59. Bekijk met welke zoekmethode je het snelst het getal 91 vind. Hoeveel stappen kost dit? Vergelijk de methoden lineair zoeken, en binair zoeken (waarbij je beide sorteermethoden insert sort en merge sort gebruikt). Leg precies uit hoeveel stappen deze methoden in dit geval kosten. Wat kun je voor conclusie(s) trekken?
7.2
Opgave 2
Gegeven is de volgende hash: 293C4E8F0A. Wat is de oorspronkelijke binaire hashcode? En wat is de waarde in ons tientallig stelsel? Geef je berekeningen.
7.3
Opgave 3
Brute krachtaanval: Bij een brute krachtaanval probeert een hacker alle mogelijke wachtwoorden om achter het goede wachtwoord te komen. Neem aan dat een wachtwoord lengte 6 heeft en dat zowel kleine letters, hoofdletters en cijfers gebruikt mogen worden. Hoe lang doe je er gemiddeld over met de brute krachtaanval om het wachtwoord te kraken, er vanuit gaande dat er geen collisions zijn, als: a) het 0.1 seconde duurt om een wachtwoord te testen? b) het 10−6 seconde duurt om een wachtwoord te testen? c) Wat gebeurt er als de wachtwoorden lengte 10 hebben? Vergelijk je antwoord met a) en b).
12
Referenties [1] Bruce Schneier, 1996, Applied Cryptography; Protocols, Algorithms, and Source Code in C, John Wiley & Sons, Inc. [2] William Stallings, 1999, Netwerkbeveiliging en cryptografie; Beginselen en praktijk, Academic Service, Schoonhoven. [3] Gerard Tel, 2002, Cryptografie; Beveiliging van de digitale maatschappij, Pearson Education Benelux. [4] Steve Friedl, 2005, An Illustrated Guide to Cryptographic Hashes, http://www.unixwiz.net/techtips/iguide-crypto-hashes.html.
13
