感谢0CTF，上交大这次举办了一个挺有深度的CTF竞赛。
这次竞赛有一道web题，标题很简略，大致如下：
include('config.php');
session_start();
if($_SESSION['time'] && time() - $_SESSION['time'] > 60) {
    session_destroy();
    die('timeout');
} else {
    $_SESSION['time'] = time();
}
echo rand();
if (isset($_GET['go'])) {
    $_SESSION['rand'] = array();
    $i = 5;
    $d = '';
    while($i--){
        $r = (string)rand();
        $_SESSION['rand'][] = $r;
        $d .= $r;
    }
    echo md5($d);
} else if (isset($_GET['check'])) {
    if ($_GET['check'] === $_SESSION['rand']) {
        echo $flag;
    } else {
        echo 'die';
        session_destroy();
    }
} else {
    show_source(__FILE__);
}
彻底没有其他考点，便是让你猜测rand()的输出。看起来确实十分简略，名为rand()的函数实践上是伪随机函数生成器，是可以进行猜测的。并且标题不约束提交次数，约束两次提交的时刻距离，连敌手进犯模型都固定了：不该该用暴力拆解（可是我用了），而是经过若干次恳求之后可以搜集数据猜测之后的rand()函数输出。
国内查了许多材料都没找到关于rand()函数的完结细节。自己也拙，没有直接去找源码，而是相信某篇文章，进行爆炸。成果命运欠好，只能gg。
现在看完国外的博文之后才知道正确解法。原文具体论述了glibc中rand函数的用法，英文好的可以直接读原文 http://www.mscs.dal.ca/~selinger/random/ 。为了日后便利我将大致内容翻译收拾如下：
 rand()由一个种子（singned int seed）进行初始化，生成的进程对错线性的。可是linux中man有些小误导，在初始化完结之后，随机数的生成便是线性的，实践上是以个线性移位反应寄存器。给没学过暗码学的安利一下最简略的状况，线性移位反应寄存器实践便是把之前某几个特定位的输出取出来，进行一个操作（八成异或），然后作为现在的输出。常见于一些流暗码的生成进程。这东西咱们可以类比斐波那契序列进行了解。
如此，rand()可破，拿到满足的旧输出就行。那么rand()是怎么作业的呢？rand()种子规模是0~2147483647（2**31-1），初始化对前34个内部向量r0~r33，操作如下：
(1) r0 = s
(2) ri = (16807 * (signed int) r(i-1)) mod 2147483647 (for i = 1...30)
(3) ri = r(i-31) (for i = 31...33)
留意到乘16807这一步是在满足大的signed Int中进行的，所以在模运算之前不会发作溢出。并且在乘法之前，ri-1 也被转化为了 signed 32-bit int 。可是这个值仅有或许的负值出现在i=1的时分，即当s>=2**31时。由上能看出模运算便是0~2147483646之间的一个值，即使前一个数是负的。
所以，r34便是按如下的反应循环进行的：
(4) ri = (ri-3 + ri-31) mod 4294967296 (for i ≥ 34)
r0…r343 会被丢掉，第一个输出Oi实践上是：
(5) oi = r(i+344) >> 1
留意这个右移一位操作，丢掉了最终一bit，实践有用比特数为31位。
线性性质剖析：
虽然最终一位被丢掉了，可是影响并不大，咱们仍然可以得到线性性质很好的输出序列。结合(4)、(5)式可得：
(6.1) oi = o(i-31) + o(i-3) mod 2**31, for all i ≥ 31
or 
(6.2) oi = o(i-31) + o(i-3) + 1 mod 2**31, for all i ≥ 31
原文也给出一个C言语完结的简略版别random函数，附之于下：
#include
#define MAX 1000
#define seed 1
main() {
  int r[MAX];
  int i;
  r[0] = seed;
  for (i=1; i31; i++) {
    r[i] = (16807LL * r[i-1]) % 2147483647;
    if (r[i] 0) {
      r[i] += 2147483647;
    }
  }
  for (i=31; i34; i++) {
    r[i] = r[i-31];
  }
  for (i=34; i344; i++) {
    r[i] = r[i-31] + r[i-3];
  }
  for (i=344; i-31] + r[i-3];
    printf("%dn", ((unsigned int)r[i]) >> 1);
  }
}