神刀安全网

glibc库中rand函数的实现详解与预测手法

glibc库中rand函数的实现详解与预测手法

感谢0CTF,上交大这次举办了一个挺有深度的CTF比赛。

这次比赛有一道web题,题目很简单,大致如下:

<?php 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中进行的,所以在模运算之前不会发生溢出。而且在乘法之前, r i -1 也被转化为了 signed 32-bit int 。但是这个值唯一可能的负值出现在i=1的时候,即当s>=2**31时。由上能看出模运算就是0~2147483646之间的一个值,即便前一个数是负的。

所以,r34就是按如下的反馈循环进行的:

(4) ri = (ri-3 + ri-31) mod 4294967296 (for i ≥ 34)

r 0… r 343 会被丢弃,第一个输出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 <stdio.h>  #define MAX 1000 #define seed 1  main() {   int r[MAX];   int i;    r[0] = seed;   for (i=1; i<31; i++) {     r[i] = (16807LL * r[i-1]) % 2147483647;     if (r[i] < 0) {       r[i] += 2147483647;     }   }   for (i=31; i<34; i++) {     r[i] = r[i-31];   }   for (i=34; i<344; i++) {     r[i] = r[i-31] + r[i-3];   }   for (i=344; i<MAX; i++) {     r[i] = r[i-31] + r[i-3];     printf("%d/n", ((unsigned int)r[i]) >> 1);   } }

*原文连接: mscs.dal.ca ,编译:YoungC, 转载请注明来自FreeBuf黑客与极客(FreeBuf.COM)

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » glibc库中rand函数的实现详解与预测手法

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
分享按钮