Created
February 23, 2016 13:51
-
-
Save natmchugh/ff29cb3eda9e8b6baa83 to your computer and use it in GitHub Desktop.
Brute forcing the seeding of PHP's lcg
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?php | |
class Lcg | |
{ | |
private $s1 = 0; | |
private $s2 = 0; | |
public function __construct($s1, $s2) | |
{ | |
$this->s1 = $s1; | |
$this->s2 = $s2; | |
} | |
private function modmult($a, $b, $c, $m, $s) | |
{ | |
$q = intval($s/$a); | |
$s=$b*($s-$a*$q)-$c*$q; | |
if($s<0) { | |
$s+=$m; | |
} | |
return $s; | |
} | |
public function combined_lcg() | |
{ | |
$this->s1 = $this->modmult(53668, 40014, 12211, 2147483563, $this->s1); | |
$this->s2 = $this->modmult(52774, 40692, 3791, 2147483399, $this->s2); | |
$z = $this->s1 - $this->s2; | |
if ($z < 1) { | |
$z += 2147483562; | |
} | |
return $z * 4.656613e-10; | |
} | |
} | |
$time = time(0); | |
$pid = getmypid(); | |
echo 'time is: ',$time,' (just the unix timestamp so very guessable)',PHP_EOL; | |
echo 'pid is: ',$pid, ' (process id of current PHP process usually in 1000s )',PHP_EOL; | |
$lcgValue = lcg_value(); | |
echo 'Output of 1st call to uninitialized to lcg_value is: '.$lcgValue,PHP_EOL; | |
echo 'Output of 2nd call to uninitialized to lcg_value is: '.lcg_value(),PHP_EOL; | |
echo 'Output of 3rd call to uninitialized to lcg_value is: '.lcg_value(),PHP_EOL; | |
for ($delta = 0; $delta < 10; $delta++) { | |
for ($i = 0; $i < 1000000; $i++) { | |
$s1 = $time ^ ($i << 11); | |
$s2 = $pid ^ (($i+$delta) << 11); | |
$lcg = new Lcg($s1, $s2); | |
if ($lcgValue == $lcg->combined_lcg()) { | |
printf('seeds were : s1:%d and s2:%d'.PHP_EOL,$s1, $s2); | |
printf('delta was %d'.PHP_EOL, $delta); | |
$lcg = new Lcg($s1, $s2); | |
echo 'LCG value 1 is: ',$lcg->combined_lcg(),PHP_EOL; | |
echo 'LCG value 2 is: ',$lcg->combined_lcg(),PHP_EOL; | |
echo 'LCG value 3 is: ',$lcg->combined_lcg(),PHP_EOL; | |
break 2; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment