Mathematik zum Montag

[Indianerversteher]

Wie oft könnte man mit rand() wohl 200 oder 2000 Salts mit 16 Zeichen aus [0-9A-Za-z/.] konstruieren bis man das erste Mal den Fall hat, dass dabei pseudozufällig 2 gleiche Salts in der gleichen Gruppe entstehen? (Das ist das einzige, um was es geht!) Ein paar Millionen oder ein paar Billionen mal?

Wer Fehler findet mag's korrigieren:

[0-9A-Za-z/.] -> 58 Symbole

Salts mit 16 Zeichen -> 16 Stellen

58^16 = 16400152899115243850138976256 mögliche Iterationen

Durchschnittlich wird also (bei perfektem Zufall) aller 58^16/2 = 8200076449557621925069488128 Versuchen der gleiche Salt wie ein bestimmter (z.B.)vorheriger erzeugt.

Erzeugt man Gruppen von 200 Salts dann ergäbe sich, dass durchschnittlich nach 58^16/(2*200) = 41000382247788109625347440 Versuchen eine Gruppe von 200 Salts erzeugt wurde, welche mindestens 2 identische Salts enthält.

Wenn man mit einem derzeitig gebräuchlichem Server und PHP sowie rand() rangeht

<?php
class saltMaker {
    private $s='0123456789abcdefghijklmnopqrstyuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ/.';
   
    public function generate( $l=16 ) {
        $s='';
        for ($i = 0; $i < 16; $i++ ) {
           $s = $s . $this -> s[ rand( 0, 57 ) ];
        }
        return $s;
    }
}

$tests = 1000000;
$sm = new saltMaker();

$start = microtime( true );
for ( $i=0; $i < $tests; $i++ ) {
   $sm -> generate();
}
$end = microtime( true );
echo  ($end - $start) . ' Sekunden (' . ($end - $start)/$tests . ' Sekunden pro Salt.)';

dann kann man z.B. 100.000 Salts in einer Sekunde erzeugen. (Habs grad getan)

Dann dauert es also durchschnittlich 410003822477881096253 Sekunden bis eine Datei erzeugt wurde, die 200 Salts enthält von denen mindestens 2 identisch sind.

Ein Jahr hat rund (365.252460*60 = 31557600 Sekunden. Also würde es durchschnittlich 410003822477881096253/31557600 = 12992237130766 Jahre dauern bis man zwei solche Dateien erzeugt erzeugt hat. Die Erde wird voraussichtlich noch 1500000000 Jahre existieren. Man braucht also (mit heutiger Rechentechnik) nur rund 6900 mal so lange wie die Erde noch existieren wird.

Nach diversen Schätzungen ist der Zufall von rand() gegenüber kryptographischen Zufallsfunktionen um 20% "schlechter".

Demnach braucht man nur 58^16/(2200) 0.8 = 32800305798230487700277952 Versuche um eine Datei zu erzeugen, die 200 Salts enthält von denen mindestens 2 identisch sind. Und nur 3400 mal so lange, wie die Erde noch existiert…

Was spart ein Angreifer?

Nun, wenn jemand die Passwörter in einer Datei mit nur 199 statt 200 verschiedenen Salts zu knacken hat, dann spart er ein halbes Prozent der für die Erzeugung der Rainbow-Tables benötigten Zeit. Wie schon beschrieben durchschnittlich in jedem 41000382247788109625347440. Fall bei perfektem Zufall und in jedem 32800305798230487700277952. Fall bei Pseudo-Zufall.

Da kann er also ganz oft richtig zeitig Feierabend machen!