Skip to content

Instantly share code, notes, and snippets.

@natmchugh
Created February 23, 2016 13:51
Show Gist options
  • Save natmchugh/ff29cb3eda9e8b6baa83 to your computer and use it in GitHub Desktop.
Save natmchugh/ff29cb3eda9e8b6baa83 to your computer and use it in GitHub Desktop.
Brute forcing the seeding of PHP's lcg
<?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