Regnbågsbord

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 22 februari 2021; kontroller kräver 4 redigeringar .

Rainbow table ( engelsk  regnbågstabell ) är en specialversion av uppslagstabeller ( engelsk  lookup table ) för att invertera kryptografiska hashfunktioner , med hjälp av mekanismen för en rimlig kompromiss mellan tabelluppslagningstid och upptaget minne ( engelsk  time-memory tradeoff ).

Regnbågstabeller används för att knäcka svåråtervändbara hash - lösenord och för att attackera symmetriska chiffer baserat på känd klartext .

Att använda funktionen för härledning av saltnyckeln gör denna attack omöjlig. Regnbågstabeller är en utveckling av en tidigare och enklare algoritm som föreslagits av Martin Hellman [1] .

Förutsättningar för uppkomsten av

Datorsystem som använder lösenord för autentisering måste på något sätt avgöra om det angivna lösenordet är korrekt. Det enklaste sättet att lösa detta problem är att föra en lista över alla giltiga lösenord för varje användare. Nackdelen med denna metod är att i händelse av obehörig åtkomst till listan kommer angriparen att ta reda på alla användarlösenord. Ett vanligare tillvägagångssätt är att lagra kryptografiska hashvärden från lösenfrasen. Men de flesta hasharna beräknas snabbt, så en angripare med tillgång till hasharna kan snabbt kontrollera listan över möjliga lösenord för giltighet. För att undvika detta måste du använda längre lösenord, vilket ökar listan över lösenord som en angripare måste kontrollera. För enkla lösenord som inte innehåller ett salt kan en angripare förberäkna hashvärden för alla vanliga och korta lösenord och lagra dem i en tabell. Nu kan du snabbt hitta en matchning i en förhandsinhämtad tabell. Men ju längre lösenord, desto större tabell, och desto mer minne behövs för att lagra det. Ett alternativ är att endast lagra de första delarna av hashkedjor. Detta kommer att kräva mer beräkning för att slå upp lösenordet, men kommer att avsevärt minska mängden minne som krävs. Och regnbågsbord är en förbättrad version av denna metod som undviker kollisioner.

Förberäknade hashkedjor

Hash-kedjorna som beskrivs i den här artikeln skiljer sig från de som beskrivs i Hash-kedjans artikel .

Antag att vi har en hashfunktion H med hashlängd n och en ändlig uppsättning lösenord P. Vårt mål är att skapa en datastruktur som , för vilket hashvärde h som helst , antingen kan hitta ett element p av P så att H( p )= h , eller bestäm att inget sådant element existerar. Det enklaste sättet att göra detta är att beräkna H( p ) för alla p i P, men en sådan tabell skulle kräva Θ (|P| n ) minne, vilket är för mycket.

Hash-kedjor är en teknik för att minska detta minneskrav. Huvudidén är att definiera en reduktionsfunktion R som mappar hashvärden till värden från P. Observera att R inte är en hashfunktionsinversion. Om vi ​​börjar med det ursprungliga lösenordet och växelvis tillämpar H och R på varje resulterande värde, får vi en kedja av alternerande lösenord och hash. Till exempel, för en lösenordsuppsättning på 6 tecken lång och en hashfunktion som producerar 32-bitars värden, kan kedjan se ut så här:

Det enda kravet för reduktionsfunktionen är att returnera värden från samma alfabet som lösenorden.

För att generera tabellen väljer vi en slumpmässig uppsättning initiala lösenord från P, beräknar kedjor med någon fast längd k för varje lösenord och lagrar endast det första och sista lösenordet från varje kedja.

För varje hash h , vars värde vi vill vända (hitta lösenordet som motsvarar det), beräknar vi sekvensen R(…R(H(R(h)))...). Om något av de mellanliggande värdena sammanfaller med någon ände av någon kedja, tar vi början av denna kedja och återställer den helt. Med hög sannolikhet kommer hela kedjan att innehålla hashvärdet h och lösenordet som föregår det kommer att vara det önskade.

För exemplet ovan, om vi initialt har en hash på 920ECF10, kommer det att generera följande sekvens:

Eftersom kiebgtär slutet av kedjan från vår tabell, tar vi motsvarande initiala lösenord aaaaaaoch beräknar kedjan tills vi hittar hashen 920ECF10:

Det önskade lösenordet är alltså sgfnyd.

Det är värt att notera att den återställda kedjan inte alltid innehåller det erforderliga hashvärdet h . Detta är möjligt när det sker en kollision av H- eller R-funktionen. Låt till exempel hashen FB107E70 ges, som i ett visst skede genererar lösenordet kiebgt:

Men FB107E70 visas inte i kedjan som genereras av lösenordet aaaaaa. Detta kallas ett falskt positivt . I det här fallet ignorerar vi matchningen och fortsätter att utvärdera sekvensen som genereras av h . Om den genererade sekvensen når längden k utan bra matchningar, betyder detta att det sökta lösenordet aldrig har hittats i de förberäknade kedjorna.

Innehållet i tabellen beror inte på värdet på den omvända hashen, den beräknas i förväg och används endast för snabbsökning. Att öka längden på kedjan minskar storleken på bordet, men ökar tiden det tar att hitta det önskade elementet i kedjan.

Enkla hash-kedjor har flera nackdelar. Det allvarligaste är möjligheten att slå samman två kedjor till en (generera samma värde i olika kedjor). Alla värden som genereras efter sammanslagningen kommer att vara desamma i båda kedjorna, vilket minskar antalet lösenord som täcks. Eftersom de förgenererade kedjorna inte sparas i sin helhet är det omöjligt att effektivt jämföra alla genererade värden med varandra. Som regel sköts hashfunktionen H av den part som tillhandahåller lösenordskryptering, så huvudproblemet ligger i reduktionsfunktionen R.

Ett annat allvarligt problem är valet av en sådan R-funktion som kommer att generera lösenord med den täckning och distribution som krävs. Den utgående alfabetiska begränsningen är en allvarlig begränsning för valet av en sådan funktion.

Regnbågstabeller

Regnbågsbord är en förlängning av idén med ett hashkedjebord. De löser effektivt problemet med kollisioner genom att införa en sekvens av reduktionsfunktioner R 1 , R 2 , …, Rk . Reduktionsfunktionerna tillämpas i tur och ordning, varvat med hashfunktionen: H, R 1 , H, R 2 , …, H, Rk . Med detta tillvägagångssätt kan två kedjor slås samman endast om värdena på samma iteration matchar . Därför är det tillräckligt att kontrollera för kollisioner endast de slutliga värdena för kedjorna, vilket inte kräver ytterligare minne. I det sista skedet av sammanställningen av tabellen kan du hitta alla sammanslagna kedjor, lämna bara en av dem och generera nya för att fylla tabellen med det antal olika kedjor som krävs. De resulterande kedjorna är inte helt fria från kollisioner, men de kommer inte att smälta samman helt.

Användningen av sekvenser av reduktionsfunktioner ändrar hur tabellen söks. Eftersom hashen kan hittas var som helst i kedjan måste k olika kedjor genereras:

Definitionen av en falsk positiv kommer också att ändras: om vi felaktigt "gissar" positionen för den önskade hashen, kommer detta att förkasta endast en av de k genererade kedjorna; samtidigt kan det fortfarande vara möjligt att hitta rätt hash för denna bordskedja, men på en annan position.

Även om regnbågstabeller kräver fler kedjor att hålla reda på, har de en högre täthet av lösenord per tabellpost. Till skillnad från en hash-kedjetabell minskar användningen av flera reduktionsfunktioner antalet potentiella kollisioner i tabellen, vilket gör att den kan växa utan risk för ett stort antal kedjesammanslagningar.

Exempel

Det finns en hash ( re3xes) att vända (återställa motsvarande lösenord) och en regnbågstabell som erhålls med tre reduceringsfunktioner.

  1. Beräkna en kedja med längden 1 från den initiala hashen: R 3 ("re3xes")="rambo". Detta lösenord är inte slutet på någon tabellkedja.
  2. Beräkna en kedja med längd 2: R 3 (H(R 2 ("re3xes")))="linux23".
  3. Detta lösenord finns i tabellen. Vi tar början av den hittade kedjan (lösenord passwd).
  4. Vi återställer tabellkedjan tills vi får den ursprungliga hashen re3xes.
  5. Den önskade hashen finns i kedjan, attacken är framgångsrik. Lösenordet som föregår detta hashvärde är lösenordet culturesom ska sökas.

Tid och minne

En regnbågstabell skapas genom att bygga kedjor av möjliga lösenord. Skapandet av sådana tabeller kräver mer tid än det tar att skapa vanliga uppslagstabeller, men mycket mindre minne (upp till hundratals gigabyte, med volymen för vanliga tabeller med N ord, behöver regnbågstabeller bara cirka N 2/3 ). Samtidigt, även om de kräver mer tid (jämfört med enkla metoder som en ordboksattack ) för att återställa det ursprungliga lösenordet, är de mer genomförbara i praktiken (för att bygga en vanlig tabell för ett 6-teckens lösenord med byte-tecken, behöver du 256 6 = 281 474 976 710 656 minnesblock, medan för regnbågen - endast 256 6 ⅔ = 4 294 967 296 block).

Tabeller kan bara knäcka hash-funktionen de skapades för, dvs MD5- tabeller kan bara knäcka MD5-hash. Teorin om denna teknologi utvecklades av Philippe Oechslin [2] som en snabb variant av tidsminne kompromiss [3] . Tekniken användes först i Ophcrack- programmet för att knäcka LanMan-hash ( LM-hash ) som används i Microsoft Windows . Mer avancerat program RainbowCrack utvecklades senare , som kan fungera med ett stort antal hash, till exempel LanMan, MD5, SHA1 och andra.

Nästa steg var skapandet av programmet The UDC , som låter dig bygga Hybrid Rainbow- tabeller inte med en uppsättning tecken, utan med en uppsättning ordböcker, som låter dig återställa längre lösenord (i själva verket obegränsad längd).

Applikation

När du genererar tabeller är det viktigt att hitta det bästa förhållandet mellan relaterade parametrar:

Ovanstående parametrar beror på de inställningar som angavs under generering av tabeller:

I det här fallet beror genereringstiden nästan uteslutande på den önskade sannolikheten för val, vilken teckenuppsättning som används och längden på lösenordet. Utrymmet som upptas av tabellerna beror på den önskade hastigheten för att välja ett lösenord från färdiga tabeller.

Även om användningen av regnbågstabeller underlättar användningen av brute force (det vill säga brute force ) för att gissa lösenord, tillåter i vissa fall den processorkraft som krävs för att generera/använda dem inte en enskild användare att uppnå de önskade resultaten inom en acceptabel tid . Till exempel, för lösenord som inte är längre än 8 tecken, bestående av bokstäver, siffror och specialtecken !@#$%^&*()-_+=hashade med MD5-algoritmen, kan tabeller genereras med följande parametrar:

Samtidigt kommer sannolikheten att hitta ett lösenord med dessa tabeller vara 0,7542 (75,42%), själva tabellerna kommer att ta 596 GiB , att generera dem på en Pentium-3 1 GHz -dator tar 3 år och att söka efter 1 lösenord att använda färdiga bord tar inte mer än 22 minuter.

Tabellgenereringsprocessen kan dock parallelliseras, till exempel tar beräkningen av en tabell med ovanstående parametrar cirka 33 timmar. I det här fallet, om vi har 100 datorer till vårt förfogande, kan alla tabeller genereras på 11 dagar.

Skydd mot regnbågsbord

En av de vanligaste metoderna för skydd mot hackning med regnbågstabeller är användningen av irreversibla hashfunktioner, som inkluderar salt (" salt ", "modifierare"). Det finns många möjliga scheman för att blanda seed och lösenord. Tänk till exempel på följande funktion för att skapa en hash av ett lösenord:

hash = MD5( lösenord + salt)

För att återställa ett sådant lösenord behöver en angripare tabeller för alla möjliga saltvärden. När man använder ett sådant schema måste saltet vara tillräckligt långt (6‒8 tecken), annars kan en angripare beräkna tabeller för varje saltvärde, slumpmässigt och olika för varje lösenord. Således kommer två identiska lösenord att ha olika hash-värden om inte samma salt används.

I grund och botten ökar saltet längden och möjligen komplexiteten hos lösenordet. Om tabellen är designad för en viss längd eller för någon begränsad uppsättning tecken, kan saltet förhindra lösenordsåterställning. Till exempel använde gamla Unix-lösenord ett salt som bara var 12 bitar långt. För att knäcka sådana lösenord behövde en angripare endast räkna 4096 tabeller, som fritt kan lagras på terabyte hårddiskar. Därför, i moderna tillämpningar, tenderar de att använda ett längre salt. Till exempel använder bcrypt - hashningsalgoritmen ett 128-bitars salt [4] . Denna längd på saltet gör förberäkningen helt enkelt meningslös. Ett annat möjligt sätt att bekämpa precomputation attacker är key stretching .  Till exempel:

nyckel = hash(lösenord + salt) för 1 till 65536 do nyckel = hash(nyckel + lösenord + salt)

Denna metod minskar effektiviteten av förberäkning, eftersom användningen av mellanvärden ökar tiden som krävs för att beräkna ett lösenord, och därmed minskar antalet beräkningar som en angripare kan utföra inom en given tidsram [5] Denna metod används i följande hashalgoritmer: MD5 , som använder 1000 repetitioner, och bcrypt . [6] . Ett alternativ är att använda nyckelförstärkning , som ofta förväxlas med nyckelsträckning .  Med denna metod ökar vi nyckelstorleken genom att lägga till ett slumpmässigt salt, som sedan tyst avlägsnas, i motsats till nyckelsträckning, där saltet bevaras och används i efterföljande iterationer [7] .

Användning

Praktiskt taget alla Unix- , GNU/Linux- och BSD OS-distributioner använder hash med ett salt för att lagra systemlösenord, även om många applikationer, såsom Internet-skript, använder en enkel hash (vanligtvis MD5 ) utan ett "salt". Microsoft Windows och Windows NT OS använder LM-hash och NTLM hash , som inte heller använder "salt", vilket gör dem till de mest populära för att skapa regnbågstabeller.

Anteckningar

  1. ↑ Hellman M. A cryptanalytic time-memory trade-off  // IEEE Transactions on Information Theory. - 1980. - Juli ( vol. 26 , nr 4 ). - S. 401-406 . — ISSN 0018-9448 . - doi : 10.1109/TIT.1980.1056220 .
  2. ↑ Philippe Oechslin . Hämtad 28 augusti 2006. Arkiverad från originalet 23 november 2005.
  3. ↑ Philippe Oechslins presentation vid CRYPTO'03-konferensen Arkiverad 26 september 2007 på Wayback Machine (PDF)
  4. ↑ Alexander, Steven. Lösenordsskydd för moderna operativsystem  //  ;login:. - USENIX Association, 2004. - Juni ( vol. 29 , nr 3 ).
  5. ↑ Ferguson, Neils; Bruce Schneier. Praktisk kryptografi  . - Indianapolis: John Wiley & Sons , 2003. - ISBN 0-471-22357-3 .
  6. ↑ Provos, Niels; Mazières, David A Future-Adaptable Password Scheme  (obestämd tid)  // Proceedings of the FREENIX Track: 1999 USENIX Annual Technical Conference. - Monterey, CA, USA: USENIX Association, 1999. - 6 juni.
  7. ↑ U. Manber , "Ett enkelt schema för att göra lösenord baserade på envägsfunktioner mycket svårare att knäcka," Computers & Security, v.15, n.2, 1996, pp.171-176. (Engelsk)

Länkar