wat is hash-tabel

[Gast]

Nog even over hash functies en tabellen...

 

Een hash functie is een functie die van een reeks data een 'getal' maakt. De grootte van dit getal in bits ligt meestal vast. Een hash functie voor gebruik in een tabel als boven is meestal 32-bit (omdat de CPU daar het snelst mee kan rekenen, en een tabel met 4 miljard entries past nu toch niet in je geheugen...)

 

Hashes worden niet alleen voor hash tabellen gebruikt, maar ook in datacommunicatie. Een van de meest voorkomende is de 'checksum' (tel alle bytes op), deze wordt voor TCP/IP (internet dus) nog steeds gebruik. De zender rekent een checksum uit van het te versturen bericht. De ontvanger doet dit ook, en als de uitkomst niet overeenkomt, zat er een fout in de transmissie. CRC (16 of 32 bit) is een heel leuke hash. Als je deze uitrekent voor een reeks tekens, dan is de CRC van de (reeks + CRC), ofwel het volledige bericht altijd gelijk aan 0.

 

Ook in encryptie en security worden hashes gebruikt. Een hash, als hij maar ingewikkeld genoeg is, geeft vrijwel zekerheid over of de inhoud van een bericht ongewijzigd is. Als de hash van twee berichten gelijk is, is het heel, heel waarschijnlijk dat de hele inhoud gelijk is. Al heel lang staat in de password file van een UNIX system (/etc/passwd dacht ik) een encrypted versie van je wachtwoord. Deze is NIET te decrypten, het is een hash. Zelfs mijn simpele hash[n] = hash[n-1]*23+array[n] functie voldoet hier al aan, je kunt niet berekenen wat het bericht was.

Om in te loggen, tik je je password in. De hash hiervan wordt berekend, en als de uitkomst van die berekening hetzelfde is als de hash die in de password tabel staat, had je dus het goede password. Zo hoeft het password zelf dus niet opgeslagen te worden. Ongetwijfeld heeft ook SAT4ALL dit met je login gegevens gedaan. Op unix was 'crypt' de standaard hash functie, met een woordenboekje en een snelle PC (hack programmaatje dus) kun je in een dag tijd wel een aantal passwoorden vinden. Tegenwoordig wordt meestal MD5 (128-bit hash) of RSA gebruikt.

 

Nou komt het grappige: Een password tabel is dus een tabel met hashes. Het is dus niet wat gewoonlijk onder een hash tabel verstaan wordt, maar het is toch een hash tabel...

 

Nou nog een leuke. Ik 'deel' een geheimpje met iemand. Een wachtwoord bijvoorbeeld. Nou wil ik verifieren of de ander mijn geheimpje kent. Nou, gewoon een hash ervan sturen he? Maar dan is het probleem: Iemand die de lijn afluistert, kan de hash opvangen. Dan weet hij het wachtwoord niet, maar dat hoeft ook niet want hij hoeft alleen de hash te sturen om door mij herkend te worden. Dus dat werkt niet goed.

 

Nieuw truukje. Ik stuur een willekeurige reeks cijfers (bijvoorbeeld de datum/tijd). Aan de andere kant wordt dan de hash van deze reeks + wachtwoord berekend. De uitkomst stuurt hij naar mij terug. Ik weet nu vrij zeker of hij het goede wachtwoord heeft, want de uitkomst is vrij uniek voor die combinatie. Deze methode van authenticatie wordt een 'challenge' genoemd, ik stuur een challenge reeks, en de respons reeks moet hierop berekend worden.

 

Nu de sateliet smartcards. Die doen eigenlijk niks anders dan antwoorden op een 'key challenge'. Ze krijgen van de CAM een reeks tekens, ze prutsen ermee, en sturen dan een reeks terug. Met de uitkomst van de smartcard kan de CAM dan het signaal gaan decoderen. Maar je kunt dus (bijna) niet berekenen wat er 'in' de smartcard zit, want de uitkomst is te onvoorspelbaar door het gebruik van hash functies. Een SECA2 kaart gaat nog een stapje verder - als je hem twee keer dezelfde 'vraag' stuurt, krijg je twee keer een ander antwoord. De volgorde van vragen doet er dus toe, niet alleen de inhoud. Dat maakt de kaart bijna onkraakbaar...

[Psychosammie]

Niks meer aan toe te voegen! <img src="/ubbthreads/images/graemlins/biggthumpup.gif" alt="" />

[realist]

@ MiLo

Aha,! Bedoel je dit.

Nu voel ik mij ook verplicht om de hash af te maken.

0x01 * 23 + 0x23 = 0x3A

0x3A * 23 + 0x45 = 0x57B

0x57B * 23 + 0x67 = 0x7E74 etcetera (de rest wordt als oefening voor de student gelaten)

7E74 * 23 +89 =B5CF5

B5CF5*23 +AB =1055AAE

1055AAE*23 +CD =177B266F

177B2266F*23 +EF =1C1074E8

De hash waarde van mijn string (key) is dus 1C1074E8

[Tonskidutch]

gave uitleg .. Milo,

 

helder als een kristalmatrix

 

cheers

[Tonskidutch]

een 3d matrix !!!!!

 

voor de flatlanders onder ons <img src="/ubbthreads/images/graemlins/smile.gif" alt="" />

[Tonskidutch]

als je die nu even kunt doorrekenen voor ons hebben we weer beeld... <img src="/ubbthreads/images/graemlins/smile.gif" alt="" />

 

cheers