[PHP] Passwords genereren met mt_rand: soms zelfde pass

[Olaf van der Spek]

Ik generereer random passwords met mt_rand (WinNT/Apache/PHP 4.3.3). Soms komt het voor dat een password toch meerdere keren wordt gegenereerd. Omdat ik momenteel alleen passwords voor identificatie gebruik (geen username dus), levert dit direct een probleem op. Maar ook met usernames is het geen veilig idee.
Wat is de oorzaak hiervan?

PHP:

function new_security_code()
{
    $v = "";
    $s = "0123456789ABCDEFGHIJKLMNOPQRSTUVXWXYZabcdefghijklmnopqrstuvxwxyz";
    for ($i = 0; $i < 16; $i++)
        $v .= $s[mt_rand(0, strlen($s) - 1)];
    return $v;
}

[Verwijderd]

Tje, niet zo raar.. hij pakt 16 keer een teken uit je string. Kan ie dus af en toe toevallig een combinatie pakken die al bestaat. Je security code is dus wazig, maar zeker niet random.

[ Voor 6% gewijzigd door Verwijderd op 17-10-2003 15:14 ]

[Verwijderd]

ik zou iets doen in de trend van:

PHP:

md5(uniqid(rand(), true));

Zie ook www.php.net/uniqid

[.oisyn]

Verwijderd schreef op 17 oktober 2003 @ 15:14:
Tje, niet zo raar.. hij pakt 16 keer een teken uit je string. Kan ie dus af en toe toevallig een combinatie pakken die al bestaat. Je security code is dus wazig, maar zeker niet random.

ik weet niet hoe vaak het voorkomt, maar 16 keer hetzelfde teken pakken is wel heel erg onwaarschijnlijk. Het kan natuurlijk voorkomen, maar zoals OlafvdSpek het nu brengt komt het regelmatig voor, en dan klopt er toch iets niet

[curry684]

De kans hierop is theoretisch 1 op 52 ^ 16, en dat is wel redelijk astronomisch klein.

Moet je het ding niet seeden?

[crisp]

curry684 schreef op 17 October 2003 @ 15:26:
De kans hierop is theoretisch 1 op 52 ^ 16, en dat is wel redelijk astronomisch klein.

Moet je het ding niet seeden?

php.net:

Note: As of PHP 4.2.0, there is no need to seed the random number generator with srand() or mt_srand() as this is now done automatically.

ik vind het dus ook wel vreemd...

[curry684]

http://nl.php.net/mt_rand

Theoretisch hoef je met 4.2.0 of later niet de seeden, maar ik zou toch maar even mt_srand aanroepen als ik jou was.... er staat bij het commentaar ook dat Apache soms duplicate seeds veroorzaakt.

[curry684]

On an Apache 1.3.3 server, the seed mt_rand() uses resets to the same value every time the PHP file is uploaded. This means that if mt_rand(1,500) returns 273 the first time it is used in your PHP file, it will return 273 again if you re-upload this file. You have been warned.

[Verwijderd]

Ik ga er van uit dat je deze pass ook opslaat in een DB, wat je kunt doen is kijken of deze al voorkomt in de DB, als dit zo is nog een keer een pass berekenen.

[Olaf van der Spek]

curry684 schreef op 17 October 2003 @ 15:31:
[...]

Ik heb Apache 2.0.47, net 'iets' nieuwer dan 1.3.3.
Ik zal nu inderdaad controleren of het pass al in de DB staat, maar dat lost dit security issue niet op. Als mijn eigen server dezelfde passes genereerd, kan een aanvaller dat natuurlijk ook.

Ik denk dat het tijd is om de PHP code te downloaden en die functie zelf eens te bekijken.

[ Voor 14% gewijzigd door Olaf van der Spek op 17-10-2003 16:15 ]

[Olaf van der Spek]

Verwijderd schreef op 17 October 2003 @ 15:16:
ik zou iets doen in de trend van:

PHP:

md5(uniqid(rand(), true));

Zie ook www.php.net/uniqid

returns a prefixed unique identifier based on the current time in microseconds.

Dat is niet random (genoeg).

curry684 schreef op 17 October 2003 @ 15:26:
De kans hierop is theoretisch 1 op 52 ^ 16, en dat is wel redelijk astronomisch klein.

Moet je het ding niet seeden?

10 + 26 + 26 = 62.

[ Voor 30% gewijzigd door Olaf van der Spek op 17-10-2003 16:18 ]

[Grijze Vos]

pak gewoon een md5 van de huidige tijd geconcateneerd met iets anders. Dat werkt altijd perfect

[Verwijderd]

Verwijderd schreef op 17 October 2003 @ 16:07:
Ik ga er van uit dat je deze pass ook opslaat in een DB, wat je kunt doen is kijken of deze al voorkomt in de DB, als dit zo is nog een keer een pass berekenen.

Kijk, dat is nou de oplossing die /me ook al een paar jaar gebruikt.. de enige goede oplossing lijkt me; niets aan het toeval overlaten...

[ACM]

Hoevaak krijg je een dubbel password?

Ik heb net even 2131000 passes gegenereerd met onderstaande code en er was geen enkele duplicaat gegenereerd. (omgeving, php-4.3.3-cli op glibc 2.2.5, linux 2.4 platform)
En 2170000 op windows XP php-4.3.3-cli ook niks.

PHP:

<?
function new_security_code()
{
    $v = "";
    $s =
"0123456789ABCDEFGHIJKLMNOPQRSTUVXWXYZabcdefghijklmnopqrstuvxwxyz";
    for ($i = 0; $i < 16; $i++)
        $v .= $s[mt_rand(0, strlen($s) - 1)];
    return $v;
}

$passes = array();
for($j = 0; $j < 10000000; $j++)
{
        $key = new_security_code();
        if(isset($passes[$key]))
        {
                echo "duplicate: {$key}\n";
                $passes[$key]++;
        }
        else
        {
                $passes[$key] = 1;
        }

        if($j % 1000 == 0)
        {
                echo "Keys: {$j}\n";
        }
}

print_r($doubles);

echo "Done\n";
?>

't Process gebruikte trouwens zo'n 234MB geheugen... niet echt efficient

[ Voor 3% gewijzigd door ACM op 17-10-2003 19:18 ]

[Olaf van der Spek]

Ik heb < 1000 passwords gegenereerd en minstens zes dubbelen.
Wat is CLI trouwens?

[.oisyn]

command line interface
clear interrupt flag
cache-line interleaving
call level interface
calling line identification
command line interpreter

pick one

[Soultaker]

OlafvdSpek schreef op 17 October 2003 @ 19:49:
Wat is CLI trouwens?

Command line interface; ik vind dat we die benaming moeten uitbannen en reserveren voor Common Language Infrastructure.

[sjokki]

In PHP4.3.3 voor Windows zit een bug. Zie http://bugs.php.net/bug.php?id=25639 . Daardoor werkt het automatisch seeden niet met die versie. Het zou ook deze bug kunnen zijn: http://bugs.php.net/bug.php?id=24050 Die zat in 4.3.2, ook Windows only.

[ Voor 30% gewijzigd door sjokki op 17-10-2003 20:17 ]

[Olaf van der Spek]

sjokki schreef op 17 oktober 2003 @ 20:14:
In PHP4.3.3 voor Windows zit een bug. Zie http://bugs.php.net/bug.php?id=25639 . Daardoor werkt het automatisch seeden niet met die versie. Het zou ook deze bug kunnen zijn: http://bugs.php.net/bug.php?id=24050 Die zat in 4.3.2, ook Windows only.

Ik gok op die tweede. Die eerst gaat over rand en niet over mt_rand. Bedankt voro die link.

[Infinitive]

Als je de seed instelt, let erop wat je als waarde van de seed neemt. Als je daarvoor de tijd in seconden neemt dan zul je heel vaak dezelfde nummers kunnen trekken...

Grijze Vos schreef op 17 October 2003 @ 17:37:
pak gewoon een md5 van de huidige tijd geconcateneerd met iets anders. Dat werkt altijd perfect

Als MD5 een perfect hash algoritme zou zijn dan is de kans op dubbelen erg klein: bij benadering: n / 2^256 (gegeven n gegenereerde passwords en het kiezen van een nummer onafhankelijk). Als je enorm veel pech hebt dan werkt het dus niet

De kans dat het fout gaat is dus klein genoeg om er geen rekening mee te houden (tenzij er erg veel op het spel staat). Als je kan testen of het ding al in gebruik is, dan zou je het process kunnen herhalen totdat je een uniek nummer hebt. Of in php een functie als unique() gebruiken, maar afhankelijk van hoe deze bijhoud welke nummers er al in gebruik zijn, wil je dat voor wachtwoorden niet.

[ Voor 4% gewijzigd door Infinitive op 18-10-2003 09:52 . Reden: woordje veranderd. ]

[Verwijderd]

OlafvdSpek schreef op 17 October 2003 @ 16:16:
[...]


[...]

Dat is niet random (genoeg).

Hier een quote van PHP.net waaruit ik op kan maken dat het wel degelijk erg random is volgens mij:

quote: http://www.php.net

This will create a 32 character identifier (a 128 bit hex number) that is extremely difficult to predict.

[Olaf van der Spek]

Verwijderd schreef op 18 October 2003 @ 09:52:
Hier een quote van PHP.net waaruit ik op kan maken dat het wel degelijk erg random is volgens mij:

Als de server-tijd gesynced is met NTP heb je ongeveer een miljoen mogelijke waardes, dat is 19-bit. Dat is een stuk minder dan de 95-bit die mijn functie zou genereren als mt_rand wel random was. De vraag is nu of 19-bit wel of niet via brute force te kraken is.

[Olaf van der Spek]

Infinitive schreef op 18 October 2003 @ 09:50:
Als MD5 een perfect hash algoritme zou zijn dan is de kans op dubbelen erg klein: bij benadering: n / 2^256 (gegeven n gegenereerde passwords en het kiezen van een nummer onafhankelijk). Als je enorm veel pech hebt dan werkt het dus niet

256? Is MD5 niet 128 bit? En de kans dat je een dubbele hebt is veel en veel groter dan dat. Ooit gehoord van de birthday-paradox?

[ACM]

OlafvdSpek schreef op 18 oktober 2003 @ 11:29:
Als de server-tijd gesynced is met NTP heb je ongeveer een miljoen mogelijke waardes, dat is 19-bit. Dat is een stuk minder dan de 95-bit die mijn functie zou genereren als mt_rand wel random was. De vraag is nu of 19-bit wel of niet via brute force te kraken is.

Had je het nou al es geprobeerd met mt_srand van te voren roepen?

En idd, de tijdsgebaseerde functies zijn in principe te voorspellen, maar wel vrij lastig.
Je moet je natuurlijk afvragen of men ook al die moeite _wil_ doen... Want ben jij werkelijk zo belangrijk dat men alle mogelijke moeite zal doen om de boel te kraken?
Dan hoop ik dat je nog wel wat meer beveiliging hebt dan domweg een random string ter authenticatie

OlafvdSpek schreef op 18 October 2003 @ 11:31:
256? Is MD5 niet 128 bit? En de kans dat je een dubbele hebt is veel en veel groter dan dat. Ooit gehoord van de birthday-paradox?

128 idd.

Er zijn twee zwakheden idd:
- Je kan in theorie door 64 (willekeurige) posities in een tekst om te klappen (dus met "64 bits" afwijking) de boel al met een heel grote kans kraken (dus dat uit een (nauwelijks, bijvoorbeeld wat herschreven zinnen) andere tekst dezelfde hash rolt). Uiteraard is 2^64 combinaties proberen nog redelijk kostbaar

- Hoe meer entries, hoe meer kans op een duplicaat (de birthday paradox idd), aangezien je te maken hebt met een groeiende kans dat de nieuw gegenereerde waarde gelijk is aan een van de al aanwezige.
Te berekenen met: 1 - (364/365 * 363/365 * ...) voor verjaardagen oftewel 1 - (N - 1 / N * N - 2 / N * ... * N - (n-1) / N) in het algemene geval.

De kans dat er bij 1.000.000 random gekozen md5-strings tussen een of meer duplicaten zijn is, als het goed is (ongeveer)
0.0000000000000000000000000014693664691599208571015357095276180984797551546566503282918486524703584894

Maar dat is dus niet de kans dat iemand een specifieke string kan kraken ofzo, dat is dat er in een lijst van 1000000 entries een dubbele zit.

[ Voor 47% gewijzigd door ACM op 18-10-2003 12:31 ]

[Olaf van der Spek]

ACM schreef op 18 oktober 2003 @ 11:41:
Had je het nou al es geprobeerd met mt_srand van te voren roepen?

Nee, ik heb pas maandag weer de mogelijkheid om eraan te sleutelen. Dat betekent niet dat het niet leuk is om even door te discussieren.

En idd, de tijdsgebaseerde functies zijn in principe te voorspellen, maar wel vrij lastig.
Je moet je natuurlijk afvragen of men ook al die moeite _wil_ doen... Want ben jij werkelijk zo belangrijk dat men alle mogelijke moeite zal doen om de boel te kraken?
Dan hoop ik dat je nog wel wat meer beveiliging hebt dan domweg een random string ter authenticatie

Het systeem wordt gebruikt door mensen die passwords als 00000000 hebben. Echt veilig hoeft het niet te zijn dus. Maar om dan gelijk maar een methode met known weaknesses in te zetten is weer iets anders, terwijl een methode zonder die weaknesses bijna even eenvoudig is.

Eenmalig een random code genereren en dan md5(code + serienummer) is volgens mij al veiliger dan mijn random methode met timebased seed.

[ACM]

Ik denk dat jouw randommethode goed is, maar dat ie geen unieke seed genereerd door een bug oid.

Want bij mij werkt ie dus best aardig, ik wil nog wel testen of ie bij meerdere "invocaties" ook nog zo goed random is.

[T-Blizzard]

Ik gebruik al een hele tijd deze generator, stukkie korter

PHP:

<?php

function randPassword($lengte)

{
    $pass = '';
    $lchar = 0;
    $char = 0;

    for($i = 0; $i < $lengte; $i++)

    {
        while($char == $lchar)

        {
            $char = rand(48, 109);
            if($char > 57) $char += 7;
            if($char > 90) $char += 6;
        }
        $pass .= chr($char);
        $lchar = $char;
    }
    return $pass;
}

$i = randPassword(10);

print("$i");

?>

[ACM]

Net even getest met:
rand_pass_in.php:

PHP:

<?

set_time_limit(0);

$passes = array();
for($j = 0; $j < 10000000; $j++)
{
        $keys = explode(',', `f:\\software\\applications\\programming\\php-4.3.3-Win32\\php rand_pass_sim.php`);
        foreach($keys as $key)
        {
                if(isset($passes[$key]))
                {
                        echo "duplicate: ", $key, " ", $passes[$key], "\n";
                        $passes[$key]++;
                }
                else
                {
                        $passes[$key] = 1;
                }
        }

        if($j % 100 == 0)
        {
                echo "Keys: {$j}0\n";
        }

}

echo "Done\n";
?>

rand_pass_sim.php

PHP:

<?
function new_security_code()
{
    $v = "";
    $s =
"0123456789ABCDEFGHIJKLMNOPQRSTUVXWXYZabcdefghijklmnopqrstuvxwxyz";
    for ($i = 0; $i < 16; $i++)
        $v .= $s[mt_rand(0, strlen($s) - 1)];
    return $v;
}

$passes = array();
for($j = 0; $j < 10; $j++)
{
        echo ($j > 0 ? ',' : ''), new_security_code();
}
?>

En na 2700 invokaties duurde dat me te lang, maar dat betekende dus wel al 27000 random unieke passes met 2700 keer een nieuwe salt die dus blijkbaar best goed was, op windows was ik het na 1000 (10000 passes) al zat

[Olaf van der Spek]

T-Blizzard schreef op 18 oktober 2003 @ 14:51:
Ik gebruik al een hele tijd deze generator, stukkie korter

Korten dan wat?
Mijn functie body is vijf lines.

[Olaf van der Spek]

ACM schreef op 18 oktober 2003 @ 15:02:
En na 2700 invokaties duurde dat me te lang, maar dat betekende dus wel al 27000 random unieke passes met 2700 keer een nieuwe salt die dus blijkbaar best goed was, op windows was ik het na 1000 (10000 passes) al zat

Maar wanneer seed je precies? Bij elke invokatie?
Salt en seed zijn trouwens twee verschillende dingen.

[ Voor 7% gewijzigd door Olaf van der Spek op 18-10-2003 15:56 ]

[ACM]

OlafvdSpek schreef op 18 October 2003 @ 15:23:
Maar wanneer seed je precies? Bij elke invokatie?
Salt en seed zijn trouwens twee verschillende dingen.

't Bovenste script roept 't onderste script X keer aan en stopt de 10 geretourneerde passes dan in zijn array.

Dus er worden 10 * X passes gegenereerd en X keer opnieuw geseed.

[Grijze Vos]

De vraag is overigens, hoe erg is het als 2 mensen dezelfde random pass aangeboden krijgen? Als dit 1 op de 1000x voorkomt, zou iemand dezelfde pass hebben als een van de andere duizend. Denk je echt dat iemand denkt bij een string als "498djdfjkskj3ui38787dkj" van "HEY! Es kijken of de andere duizend diezelfde string hebben gekregen!".

[_Squatt_]

Grijze Vos schreef op 19 oktober 2003 @ 18:59:
De vraag is overigens, hoe erg is het als 2 mensen dezelfde random pass aangeboden krijgen? Als dit 1 op de 1000x voorkomt, zou iemand dezelfde pass hebben als een van de andere duizend. Denk je echt dat iemand denkt bij een string als "498djdfjkskj3ui38787dkj" van "HEY! Es kijken of de andere duizend diezelfde string hebben gekregen!".

Er wordt ingelogd met alleen een wachtwoord, als je het zelfde wachtwoord hebt als een ander, ben je eigenlijk dezelfde persoon.

[Roa]

hmm...idee: gebruik timestamp + een random nr

de kans dat op hetzelfde timestamp hetzelfde random nr gegenereerd wordt is echt super, super klein.... Zeker als je er nog iets bij doet dat iig uniek is, bijvoorbeeld het aantal users + 1, zoiets als:

timestamp + user_id + random_nr

en dan dat weer door de md5 halen. Zullen wij wedden dat niemand dat password namaakt

[Grijze Vos]

Squatt, dan zou ik dat snel veranderen. Alleen een password gebruiken om in te loggen is niet bijster intelligent. Een user/pass combo is veel handiger, en stukken veiliger..

[curry684]

Grijze Vos schreef op 19 oktober 2003 @ 20:45:
Squatt, dan zou ik dat snel veranderen. Alleen een password gebruiken om in te loggen is niet bijster intelligent. Een user/pass combo is veel handiger, en stukken veiliger..

_{Pssst niet meteen kijken hoor, maar lees de openingspost van Olafvdspek eens}

[Grijze Vos]

curry684 schreef op 19 October 2003 @ 21:10:
[...]

_{Pssst niet meteen kijken hoor, maar lees de openingspost van Olafvdspek eens}

Hij vindt dat zelfs met usernames het onveilig is, op deze manier, en daar ben ik het niet mee eens. Maar inderdaad, als hij per se dit zonder usernames wil doen, dan moet ie een oplossing ervoor vinden. Lijkt mij het makkelijkste wat al gezegd is hier, check na het genereren gewoon ff of ie al in de database zit, dat password.

[Verwijderd]

Met random, een goede seed + een uniek gegeven is het goed mogelijk om vrijwel unieke passwords te maken.
Als dit onder bepaalde omstandigheden niet lukt dan mag je er vanuit gaan dat er iets mis is met een van de onderdelen, dus ofwel je random-functie, je seed- of je uniek gegeven is niet in orde en kan inderdaad, zoals eerder aangegeven, wellicht een Bug bevatten.

Optie is dus om je PHP te re-installen of om je functie te herschrijven.

[Wolfboy]

Verwijderd schreef op 20 October 2003 @ 08:39:
Met random, een goede seed + een uniek gegeven is het goed mogelijk om vrijwel unieke passwords te maken.
Als dit onder bepaalde omstandigheden niet lukt dan mag je er vanuit gaan dat er iets mis is met een van de onderdelen, dus ofwel je random-functie, je seed- of je uniek gegeven is niet in orde en kan inderdaad, zoals eerder aangegeven, wellicht een Bug bevatten.

Optie is dus om je PHP te re-installen of om je functie te herschrijven.

php re-installen kan je doen ja maar als je dan is het script gebruikt bij een server die de bug nog wel heeft dan zit je nogsteeds met slechte wachtwoorden dus imho geen goede oplossing

[Olaf van der Spek]

Verwijderd schreef op 20 October 2003 @ 08:39:
Optie is dus om je PHP te re-installen of om je functie te herschrijven.

Ik heb de nieuwste PHP stable al. Ik zal een check toevoegen die kijkt of het pass al bestaat. Ik had eigenlijk die column als unique moeten definen, dan waren dubbele passes in ieder geval uitgesloten.

[ Voor 24% gewijzigd door Olaf van der Spek op 20-10-2003 12:27 ]