Lösenordslängden – Den magiska gränsen

Längden på ett lösenord spelar roll och det finns faktiskt magiska gränser som gör ett lösenord enormt mycket svårare att knäcka. Lyckligtvis är det också relativt enkelt att demonstrera.

Låt oss anta att vi konstruerar ett lösenord utifrån det engelska alfabetet, aA-zZ (stora och små bokstäver). Totalt ger detta oss 52 olika tecken vilka vi kan kombinera i en godtycklig längd för att skapa ett lösenord.

Längden på ett lösenord innebär en exponentiell ökning i antalet möjliga kombinationer som vi kan konstruera utifrån våra tillgängliga tecken. Om vi använder två tecken som lösenord ger detta totalt 2704 möjliga kombinationer och uträkningen är enkel, 52^2.

Och så fortsätter det, exponentiell tillväxt i antelet möjliga lösenord. Om vi nu skippar några längder, hela vägen upp till 8 tecken (här börjar det nämligen bli intressant). Med 52 möjliga tecken och en längd på 8 får vi totalt 53 459 728 531 456 (ungefär 53 biljoner, eller 53 tera-lösenord).

Nu behöver vi sätta det här i relation till något, så att det blir… vettigt. oclHashcat är ett verktyg för att cracka lösenord. Det kan använda alla möjliga fancy funktioner för att uppnå smått otroliga hastigheter. På en PC med ett modernt grafikkort (HD Radeon 6990) kan man för SHA1-algoritmen nå nästan 3.2 miljarder gissningar per/sekund.

(OBS: Allting nedan här, gäller för SHA1!)
Relationen. 53 biljoner, eller 53 000 miljarder lösenord, och 3,2 miljarder gissningar per sekund ger oss en total tid på 16 562 sekunder, eller ungefär 4 1/2 timme. Det skulle alltså ta i ren bruteforce-kraft cirka 4 timmar för att knäcka ett lösenord på 8 tecken som består av endast vanliga bokstäver, a-z, stora som små.

Här uppstår det vanliga missförståndet. Men om jag använder 2 datorer, då går det ju dubbel så snabbt. Korrekt. Det går dubbelt så snabbt, eller vi får en linjär prestandaökning. Fyra datorer skulle således knäcka lösenordet på 1 timme istället för fyra.

Men här i ligger också den viktiga skillnaden. Vi kan endast uppnå en linjär prestandaökning genom att lägga till fler noder i vårt crackingkluster. Lägger vi till en bokstav i lösenordet har vi ökat komplexiteten exponentiellt. Siffror brukar hjälpa, åtminstone fungerar det så för mig.

Exemplet. Nytt lösenord, 9 tecken aA-zZ, ger totalt 2 779 905 883 635 710 möjliga lösenordskombinationer. Nu börjar det bli riktigt stort. Detta är alltså 2 biljarder, eller 2 779 biljoner att jämföra med tidigare 53 biljoner. Och tiden? I sekunder 868 437, eller 10 dagar. Från 4 timmar, till 10 dagar… bara genom att lägga till ytterligare ett tecken, och nu har vi inte ens börjat göra lösenorden ”komplexa”.

Nå väl, och med detta sagt vill jag säga vad? Under förutsättning att ett lösenord konstrueras helt slumpmässigt med bara alfanumeriska tecken (aA-zZ och 0-9) och en längd på runt 10 tecken har du ett starkt lösenord, som utan tvekan kommer motstå bruteforcing och även rainbowtables-attacker eftersom, det mig veterligen, inte finns några sådana upprättade för sha1 med kombinationen 10 tecken, alfanumerisk samt stora och små bokstäver. (Det skulle nämligen kräva ungefär, om jag räknat rätt, 17 exabytes av lagringsutrymme! 20 bytes per sha1 digest multiplicerat med 62^10 = 1.7^19 och eftersom exponent 18 = exa, torde 1.7^19 bli 17 exabytes, eller?)

TL;DR – Väljer du ett lösenord (helt slumpmässigt) som är ungefär 10 tecken långt, kombinerat av alfanumeriska tecken (stora och små bokstäver) och hashas genom SHA1 har du ett lösenord som inte inom en nära framtid att knäckas genom ren bruteforce-kraft. Jag antar att mr. Moore fortsätter förutspå framtiden korrekt och att SHA1 står stark. Mängder av andra antaganden är också gjorda, men de ska inte spela någon större roll. Exponentiell komplexitet vs linjär beräkningskraft, do the math!

Uppdatering 2012-06-11 8:55: Stefan Pettersson påpekar att mina beräkningar för att estimera nödvändigt lagringsutrymme för en regnbågstabell är felaktiga, stryker texten tills det att jag har ordentliga siffror, för mycket utrymme krävs det, så långt är vi nog alla överens.

Uppdatering 2012-06-11 10:45: Olle påpekar att slutsatsen är felaktig eftersom ett ”användarvalt” lösenord med hög sannolikt kommer väljas för att vara lätt att komma ihåg och således skulle kunna utsättas för t.ex. ordboks-attacker. Detta är ett korrekt påstående och jag uppaterade texten för att inkludera ett viktigare antagande om att lösenordet måste väljas slumpmässigt.