Pwn 随机数攻击

介绍

随机数攻击

主要阅读了 glibc rand 相关的源代码，总结一下 CTF 中常见随机数攻击手法，主要还是打伪随机数预测。

常见写法

以 C 语言的 rand() 为例，主要写法如下：

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

void gen_random_plus() {
	srand(time(0));
	printf("%d\n", rand());
	return;
}

int main() {
	int seed;
	srand(seed);
	printf("%d\n", rand());
	return 0;
}

调用 rand() 函数会返回一个 [0,RAND_MAX] 中的随机非负整数，其中 RAND_MAX 是标准库中的一个宏，在 Linux 系统下 RAND_MAX 等于 $2^{31}-1$。可以用取模来限制所生成的数的大小。

使用 rand() 需要一个随机数种子，可以使用 srand(seed) 函数来将随机种子更改为 seed，当然不初始化也是可以的。

同一程序使用相同的 seed 两次运行，在同一机器、同一编译器下，随机出的结果将会是相同的。

有一个选择是使用当前系统时间来作为随机种子：srand(time(0))。

还有用 linux 的 random 和 urandom 设备的，写法大概如下：

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>

int main() {
    int fd = open("/dev/urandom", O_RDONLY, S_IRUSR);
    int seed = 0;
    read(fd, &seed, 4);
	return 0;
}

源码分析

./stdlib/rand.c 中定义了 rand() 函数

/* Return a random integer between 0 and RAND_MAX.  */
int
rand (void)
{
  return (int) __random ();
}

跟进去看 __random():

long int
__random (void)
{
  int32_t retval;

  __libc_lock_lock (lock);

  (void) __random_r (&unsafe_state, &retval);

  __libc_lock_unlock (lock);

  return retval;
}

发现它调用了 __random_r，它的第一个参数 unsafe_state 是一个自定义的结构体：

static struct random_data unsafe_state =
  {
/* FPTR and RPTR are two pointers into the state info, a front and a rear
   pointer.  These two pointers are always rand_sep places aparts, as they
   cycle through the state information.  (Yes, this does mean we could get
   away with just one pointer, but the code for random is more efficient
   this way).  The pointers are left positioned as they would be from the call:
    initstate(1, randtbl, 128);
   (The position of the rear pointer, rptr, is really 0 (as explained above
   in the initialization of randtbl) because the state table pointer is set
   to point to randtbl[1] (as explained below).)  */

    fptr : &randtbl[SEP_3 + 1],
    rptr : &randtbl[1],

/* The following things are the pointer to the state information table,
   the type of the current generator, the degree of the current polynomial
   being used, and the separation between the two pointers.
   Note that for efficiency of random, we remember the first location of
   the state information, not the zeroth.  Hence it is valid to access
   state[-1], which is used to store the type of the R.N.G.
   Also, we remember the last location, since this is more efficient than
   indexing every time to find the address of the last element to see if
   the front and rear pointers have wrapped.  */

    state : &randtbl[1],

    rand_type : TYPE_3,
    rand_deg : DEG_3,
    rand_sep : SEP_3,

    end_ptr : &randtbl[sizeof (randtbl) / sizeof (randtbl[0])]
};

其中：

fptr 是循环队列的头指针，初始位置为4
rptr 是循环队列的尾指针，初始位置为1
endptr：指向数组末尾，以指示队列的循环

这里又涉及到一个 randtbl 数组，它的定义如下：

static int32_t randtbl[DEG_3 + 1] =
  {
    TYPE_3,

    -1726662223, 379960547, 1735697613, 1040273694, 1313901226,
    1627687941, -179304937, -2073333483, 1780058412, -1989503057,
    -615974602, 344556628, 939512070, -1249116260, 1507946756,
    -812545463, 154635395, 1388815473, -1926676823, 525320961,
    -1009028674, 968117788, -123449607, 1284210865, 435012392,
    -2017506339, -911064859, -370259173, 1132637927, 1398500161,
    -205601318,
  };

这个时候再看一下 __random_r 的算法流程：

int
__random_r (struct random_data *buf, int32_t *result)
{
  int32_t *state;

  if (buf == NULL || result == NULL)
    goto fail;

  state = buf->state;

  if (buf->rand_type == TYPE_0)
    {
      int32_t val = state[0];
      val = ((state[0] * 1103515245) + 12345) & 0x7fffffff;
      state[0] = val;
      *result = val;
    }
  else
    {
      int32_t *fptr = buf->fptr;
      int32_t *rptr = buf->rptr;
      int32_t *end_ptr = buf->end_ptr;
      int32_t val;

      val = *fptr += *rptr;
      /* Chucking least random bit.  */
      *result = (val >> 1) & 0x7fffffff;
      ++fptr;
      if (fptr >= end_ptr)
	{
	  fptr = state;
	  ++rptr;
	}
      else
	{
	  ++rptr;
	  if (rptr >= end_ptr)
	    rptr = state;
	}
      buf->fptr = fptr;
      buf->rptr = rptr;
    }
  return 0;

 fail:
  __set_errno (EINVAL);
  return -1;
}

注意到这个算法主要有两个流程：

如果 buf->rand_type == TYPE_0，那么就是一个非常白给的 LCG，可以随便逆向预测
否则，队头自加队尾值，将此值保存为结果，然后队头队尾统一后移一项，再将结果作为生成的随机数返回。

最后来看看 srand 函数，

int
__srandom_r (unsigned int seed, struct random_data *buf)
{
  int type;
  int32_t *state;
  long int i;
  int32_t word;
  int32_t *dst;
  int kc;

  if (buf == NULL)
    goto fail;
  type = buf->rand_type;
  if ((unsigned int) type >= MAX_TYPES)
    goto fail;

  state = buf->state;
  /* We must make sure the seed is not 0.  Take arbitrarily 1 in this case.  */
  if (seed == 0)
    seed = 1;
  state[0] = seed;
  if (type == TYPE_0)
    goto done;

  dst = state;
  word = seed;
  kc = buf->rand_deg;
  for (i = 1; i < kc; ++i)
    {
      /* This does:
	   state[i] = (16807 * state[i - 1]) % 2147483647;
	 but avoids overflowing 31 bits.  */
      long int hi = word / 127773;
      long int lo = word % 127773;
      word = 16807 * lo - 2836 * hi;
      if (word < 0)
	word += 2147483647;
      *++dst = word;
    }

  buf->fptr = &state[buf->rand_sep];
  buf->rptr = &state[0];
  kc *= 10;
  while (--kc >= 0)
    {
      int32_t discard;
      (void) __random_r (buf, &discard);
    }

 done:
  return 0;

 fail:
  return -1;
}

可以看出来 srand(0) 和 srand(1) 是一样的。

这个算法会根据 LCG 打乱 state 数组。

攻击手法

随机数校验逻辑漏洞

随机数本身无法预测，例如通过 /dev/urandom 设备读入 16 字节，和预测的数字对比，可能在这个对比处存在漏洞点，例如使用了 strcmp() 等可能被 \x00 截断的函数。

这是因为通过 /dev/urandom 读入的字节完全存在第一个字节就是 \x00 的可能（1/255），爆破概率是比较高的。

也有存在栈溢出，把 seed 覆盖掉的打法。

还有使用随机数只加密了部分 shellcode，可以利用 jmp 短跳转跳掉。

伪随机数预测

显然，rand() 生成的随机数都跟 seed 有强相关性，如果题目里用的 seed 是已知常数，那么可以直接做到预测随机数。

可以写一个 poc gen_random_number.c：

#include <stdio.h>
#include <stdlib.h>
int gen_rand(int seed) {
	srand(seed);
	return rand();
}

然后编译为动态链接库，然后 python 调用动态链接库。

$ gcc A.c -share -o A.so

模板如下：

from ctypes import *
poc = cdll.LoadLibrary("./B.so")
libc = cdll.LoadLibrary('/usr/lib/libc.so.6')
seed = poc.find(num)

注意，这个 .so 里的 find 函数不能是 void，如果想接受返回值的话。

在 find 函数里的 printf 输出会晚于 pwntools 的交互。

基于时间的预测

这个也可以打，因为时间是已知的（把 poc 和题目文件同时运行不就好了）

#include <stdio.h>
#include <time.h>

int gen_rand() {
	int seed = time(0);
	srand(seed);
	return rand();
}

同样的用法。

已知一个随机数

对于一个随机的 seed（例如从 /dev/random 或者 /dev/urandom 里读取的），也不是完全不能打。假如题目已经告诉了一个该种子生成的随机数，可以尝试检查 buf->rand_type == TYPE_0 是否成立，而这个要怎么设置呢？可以看 initstate 函数。

int
__initstate_r (unsigned int seed, char *arg_state, size_t n,
	       struct random_data *buf)
{
  if (buf == NULL)
    goto fail;

  int32_t *old_state = buf->state;
  if (old_state != NULL)
    {
      int old_type = buf->rand_type;
      if (old_type == TYPE_0)
	old_state[-1] = TYPE_0;
      else
	old_state[-1] = (MAX_TYPES * (buf->rptr - old_state)) + old_type;
    }

  int type;
  if (n >= BREAK_3) // break 3 是 128
    type = n < BREAK_4 ? TYPE_3 : TYPE_4;
  else if (n < BREAK_1) // break 1 是 32
    {
      if (n < BREAK_0) // break 0 是 0
	goto fail;

      type = TYPE_0;
    }
  else
    type = n < BREAK_2 ? TYPE_1 : TYPE_2;

  int degree = random_poly_info.degrees[type];
  int separation = random_poly_info.seps[type];

  buf->rand_type = type;
  buf->rand_sep = separation;
  buf->rand_deg = degree;
  int32_t *state = &((int32_t *) arg_state)[1];	/* First location.  */
  /* Must set END_PTR before srandom.  */
  buf->end_ptr = &state[degree];

  buf->state = state;

  __srandom_r (seed, buf);

  state[-1] = TYPE_0;
  if (type != TYPE_0)
    state[-1] = (buf->rptr - state) * MAX_TYPES + type;

  return 0;

 fail:
  __set_errno (EINVAL);
  return -1;
}

所以只要调用 initstate(seed, arg_state, 8) 之类的就可以设置了。

已知多个随机数

这个攻击方式的原理是，对于一个给定的种子，其后续生成的随机数序列都是唯一确定的。

在这篇文章中，详细介绍了 GLIBC 随机数生成器的 LCG 原理。基于此，可以写出一个简单的 rand 复现：

#include <stdio.h>

#define MAX 1000

void myrand(int seed) {
  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);
  }
}

由此可知，在一个确定的随机种子下的序列中，下一个随机数的生成公式为：

$randlist_l = (randlist_{l-3}+randlist_{l-31}) % 2147483648$

于是，如果题目中可以泄漏多个给定种子的随机数，那么可以预测出在某个随机数后的所有随机数。

介绍