Markov

Andrei_MarkovAndrei Markov var en rysk matematiker verksam under slutet av 1800-talet. Det visar sig att den gamla Markov dyker upp som gubben i graven och förändrar spelplanen för säkerhet vid val av lösenord med sina Markov-kedjor.

Atom har på sistone lagt in stöd för just … Markov-kedjor i sina olika hashcatprogram. Det går till som så att kedjorna först tränas med ett träningsset, en lista med lösenord som liknar de som ska knäckas. Sen används det tränade setet för att generera de mest troliga lösenorden först. Ta t.ex. programmet pwgen. Utan argument genererar det åtta tecken långa lösenord ur de tre spannen [a-z], [A-Z] och [0-9]. Så här kan det se ut:

ye0OoJah Kooj3lah Phoh6ith
jeF0hahz uzaeW6Di Ahgeesh1
Ohy9nooy viLoop7U Ojai2xei

En snabb titt på lösenorden ger en intuition om att något inte ser helt slumpmässigt ut, men det går inte riktigt att sätta fingret på vad. Människans hjärna fungerar så. Datorn däremot är bra på att sätta sitt virtuella finger på vilka mönster som förekommer. Det är liksom detta som Markov-kedjor gör.

För att testa hur det fungerar i praktiken, generera en miljon lösenord och spara dem i filen pwgen.txt:

pwgen -1 -c -n 8 1000000 > pwgen.txt

argument:

-1 = ett lösenord per rad
-c = minst en versal
-n = minst en siffra
 8 = åtta tecken

Ladda sen ner hashcat utils och generera en markov-fil med kommandot:

./hcstatgen.bin pwgen.hcstat < pwgen.txt

Detta skapar filen pwgen.hcstat, som är c:a 33Mb stor. Skapa nu en fil med tusen ”skarpa” lösenord att testa på:

pwgen -1 -c -n 8 1000 > pw.txt

och hasha dessa med algoritmen MD5 (går snabbast att knäcka) och spara i filen pwgen.hashes. T.ex. med loopen:

for i in `cat pw.txt`; do
  echo -n $i | md5sum | awk '{print $1}'
done > pwgen.hashes

Antalet tecken i de tre spannen är 26 + 26 + 10 = 62. Åtta tecken ger 62^8 möjliga kombinationer. Min laptop har jag mätt upp till 252 miljoner kombinationer per sekund. På den skulle en ren exhaustive search (även kallat brute force) ta c:a 62^8/252000000 = 866428 sekunder. Antal per sekund blir då 1000/866428 = 0.001154.

Med Markov-kedjor borde det gå att köra betydligt kortare tid och ändå hitta en stor del av lösenorden. Ange parametern -t till oclHashcat-plus för att ange hur djupt Markov-kedjorna ska traverseras. Ju högre siffra efter -t, desto längre tid tar det, och desto fler lösenord hittas. Låt se hur lång tid det tar med olika värden på t, första kolumnen nedan. Andra kolumnen är antalet lösenord hittade, tredje kolumnen är tiden i sekunder, fjärde kolumnen är kolumn 2 / kolumn 3 = antal per sekund och den sista kolumnen anger hur lång tid det skulle ta att hitta lika många med traditionell, linjär brute force (n/0.001154).

Argumenten till oclHashcat-plus är:

Brute force mode: -a 3
Med Markov-kedjor: -t <värde>
Träningsdata: --markov-hcstat=pwgen.hcstat
Mask: -1 ?l?u?d ?1?1?1?1?1?1?1?1

-1 ?l?u?d anger att ?1 ska betyda liten bokstav, stor bokstav eller siffra. Själva mönstret är sen åtta stycken ?1.

-t  n     tid   n/s   Brute
    antal (s)         (s)
10  12    1     12    10397
15  43    11    3.9   37262
20  108   103   1.05  93587
25  186   607   0.396 161178
30  295   2615  0.113 255632
33  365   5581  0.065 316291
38  497   17250 0.029 430676

8 tecken

Fortfarande vid -t 38 så har bara 49.7% av lösenorden hittats. Antal/s är då nere i 0.029, men så länge antal hittade lösenord per sekund är större än 0.001154 så har det lönat sig att använda Markov-kedjor. Faktum är att det kommer löna sig ända in på mållinjen, vid 100% av lösenorden borde det sluta med dött lopp. Sätt så stort t som du har tid att köra.

Mitt experiment tog dock lite för lång tid med åtta tecken, så jag testade samma sak på en snabbare dator som håller en hastighet på 1.323 miljarder lösenord per sekund (5.25 ggr snabbare än laptopen), och minskade till sju tecken, vilket ger en brute force tid på 62^7/1323000000 = 2662 sekunder, vilket ger 0.38 lösenord per sekund. Så det går betydligt snabbare att få fram statistiken här:

-t  n     tid   n/s   Brute
    antal (s)         (s)
10  21    <1    ?     62
15  84    1     84    221
20  156   2     78    410
25  235   5     47    618
30  326   18    18.1  858
35  452   51    8.86  1189
40  591   126   4.69  1555
45  725   265   2.74  1908
50  864   594   1.45  2273
55  961   1155  0.83  2529

7 tecken

Även här syns tydligt att det går bra att justera t efter vilka resultat som eftersträvas. Vid -t 50 hittas t.ex. 86.4% av lösenorden, på c:a 1/4 av tiden det skulle ta att traversera alla kombinationer och fortfarande vid -t 55, som knäcker 96.1% av lösenorden, går det mer än dubbelt så snabbt som att köra alla kombinationer i ordning tills 96.1% hittats. Statistiken är aningen sämre för åtta tecken eftersom det finns flera möjliga kombinationer. Generellt verkar andelen knäckta lösenord släpa efter med ett till två t-värden mellan tabellerna. Genom att jämföra tabellerna går det t.ex. att förutsäga att -t 50 borde ge lite över 80% för åtta tecken, utan att genomföra körningen (vilket skulle ta hyfsat lång tid på den här datorn).

Slutsatsen är att ju högre t-värde, desto högre andel av lösenorden knäcks, men det tar också längre tid vilket gör att man tjänar mindre och mindre jämfört med brute force för höga t-värden. Brute force kommer ikapp på den allra sista procenten före 100% och det slutar med jämt skägg. Det lönar sig också att analysera t-värden för kortare lösenord för att lista ut vilket t-värde som är lämpligast att sätta för de stora körningarna. Eller så sätts helt enkelt ett så högt t-värde som möjligt, som inte tar orimligt lång tid att köra.

Det går även att använda markov-kedjor i kombination med ordlisteattacker. Exempel (?a innebär små bokstäver+ stora bokstäver + siffror + specialtecken):

-a 6 -t <värde>
--markov-hcstat=rockyou.hcstat hash.txt rockyou.txt
-j]]] ?a?a?a -o utfil.txt

Exemplet ovan är taget från ob-security.info. -j]]] tar bort tre tecken från början av varje ord i ordlistan rockyou.txt och testar sen att lägga till alla kombinationer av ?a?a?a efter varje ord. Att köra detta utan -t skulle ta mycket lång tid, leta reda på ett -t värde som passar. Testa också andra varianter, som: -a 7 -t <värde> … mask ordlista … osv (se även statsprocessor).

Annonser

Om albertveli

Grävande programmerare.
Det här inlägget postades i Säkerhet. Bokmärk permalänken.

Kommentera

Fyll i dina uppgifter nedan eller klicka på en ikon för att logga in:

WordPress.com Logo

Du kommenterar med ditt WordPress.com-konto. Logga ut / Ändra )

Twitter-bild

Du kommenterar med ditt Twitter-konto. Logga ut / Ändra )

Facebook-foto

Du kommenterar med ditt Facebook-konto. Logga ut / Ändra )

Google+ photo

Du kommenterar med ditt Google+-konto. Logga ut / Ändra )

Ansluter till %s