Linux随机数分析

May I Suggest ?

#leanote #leanote blog #code #hello world

Mutepig's Blog

Linux随机数分析

无 260 0 0

mut3p1g

这里分析的是最一般的随机数过程，即`srand`=>`rand`的过程，主要是想看能否根据获得的随机数逆向出种子。

## 0x01 unsafe_state
`randtbl`应该是`random_table`，数据如下：
```
146	static int32_t randtbl[DEG_3 + 1] =
147	  {
148	    TYPE_3,
149	
150	    -1726662223, 379960547, 1735697613, 1040273694, 1313901226,
151	    1627687941, -179304937, -2073333483, 1780058412, -1989503057,
152	    -615974602, 344556628, 939512070, -1249116260, 1507946756,
153	    -812545463, 154635395, 1388815473, -1926676823, 525320961,
154	    -1009028674, 968117788, -123449607, 1284210865, 435012392,
155	    -2017506339, -911064859, -370259173, 1132637927, 1398500161,
156	    -205601318,
157	  };
```
然后就是`unsafe_state`，记录了随机化过程的基本数据：
```
160	static struct random_data unsafe_state =
161	  {
162	/* FPTR and RPTR are two pointers into the state info, a front and a rear
163	   pointer.  These two pointers are always rand_sep places apart, as they
164	   cycle through the state information.  (Yes, this does mean we could get
165	   away with just one pointer, but the code for random is more efficient
166	   this way).  The pointers are left positioned as they would be from the call:
167	        initstate(1, randtbl, 128);
168	   (The position of the rear pointer, rptr, is really 0 (as explained above
169	   in the initialization of randtbl) because the state table pointer is set
170	   to point to randtbl[1] (as explained below).)  */
171	
172	    .fptr = &randtbl[SEP_3 + 1], // 前指针
173	    .rptr = &randtbl[1], // 后指针
174	
175	/* The following things are the pointer to the state information table,
176	   the type of the current generator, the degree of the current polynomial
177	   being used, and the separation between the two pointers.
178	   Note that for efficiency of random, we remember the first location of
179	   the state information, not the zeroth.  Hence it is valid to access
180	   state[-1], which is used to store the type of the R.N.G.
181	   Also, we remember the last location, since this is more efficient than
182	   indexing every time to find the address of the last element to see if
183	   the front and rear pointers have wrapped.  */
184	
185	    .state = &randtbl[1], // randtbl为基础的表，state会在srand设置种子后对这个表进行转换，并将生成的随机数循环存在这里
186	
187	    .rand_type = TYPE_3, // 3
188	    .rand_deg = DEG_3, // state的大小为31，因为state是从randtbl[1]开始算起，randtbl[0]始终为TYPE_3
189	    .rand_sep = SEP_3, // 3
190	
191	    .end_ptr = &randtbl[sizeof (randtbl) / sizeof (randtbl[0])] // randtbl终结的位置
192	};
```

## 0x02 srand
`srand`的具体实现就是`__srandom_r`，其中参数 `seed`为种子，`buf`就是上面的`unsafe_state`。
这里主要是以`seed`为基础，记为`state[0]`，实现`state[i] = (16807 * state[i - 1]) % 2147483647`。
```
161	__srandom_r (unsigned int seed, struct random_data *buf) 
162	{
163	  int type;
164	  int32_t *state;
165	  long int i;
166	  int32_t word;
167	  int32_t *dst;
168	  int kc;
169	
170	  if (buf == NULL)
171	    goto fail;
172	  type = buf->rand_type; // type默认为3
173	  if ((unsigned int) type >= MAX_TYPES)
174	    goto fail;
175	
176	  state = buf->state; // state默认从randtbl[1]开始
177	  /* We must make sure the seed is not 0.  Take arbitrarily 1 in this case.  */
178	  if (seed == 0) // seed为0也改为1
179	    seed = 1;
180	  state[0] = seed; // state[0]设置为seed，默认是TYPE_3
181	  if (type == TYPE_0)
182	    goto done;
183	  // 从state[1]开始，实现state[i] = (16807 * state[i - 1]) % 2147483647
184	  dst = state;  // dst表示state[i]
185	  word = seed; // word表示state[i-1]
186	  kc = buf->rand_deg; // kc=31，表示table的大小
187	  for (i = 1; i < kc; ++i) //一共30个
188	    {
189	      /* This does:
190	           state[i] = (16807 * state[i - 1]) % 2147483647;
191	         but avoids overflowing 31 bits.  */
192	      long int hi = word / 127773;
193	      long int lo = word % 127773;
194	      word = 16807 * lo - 2836 * hi;
195	      if (word < 0)
196	        word += 2147483647;
197	      *++dst = word;
198	    }
199	
200	  buf->fptr = &state[buf->rand_sep]; // fptr从state[3]开始
201	  buf->rptr = &state[0]; // rptr从state[0]开始
202	  kc *= 10; // 310
203	  while (--kc >= 0) // 通过__random_r生成310个随机数
204	    {
205	      int32_t discard;
206	      (void) __random_r (buf, &discard);
207	    }
208	
209	 done:
210	  return 0;
211	
212	 fail:
213	  return -1;
214	}
```

## 0x03 rand
`rand`的具体实现就是`__random_r`，参数`buf`依然是上面的`unsafe_state`，`result`就是我们返回的随机数。
```
352	int
353	__random_r (struct random_data *buf, int32_t *result)
354	{
355	  int32_t *state;
356	
357	  if (buf == NULL || result == NULL)
358	    goto fail;
359	
360	  state = buf->state;
361	
362	  if (buf->rand_type == TYPE_0)
363	    {
364	      int32_t val = state[0];
365	      val = ((state[0] * 1103515245) + 12345) & 0x7fffffff;
366	      state[0] = val;
367	      *result = val;
368	    }
369	  else // 一般type=3，所以走下面这一段
370	    {
371	      int32_t *fptr = buf->fptr; 
372	      int32_t *rptr = buf->rptr;
373	      int32_t *end_ptr = buf->end_ptr;
374	      int32_t val;
375	
376	      val = *fptr += *rptr;
377	      /* Chucking least random bit.  */
378	      *result = (val >> 1) & 0x7fffffff;
379	      ++fptr;
380	      if (fptr >= end_ptr)
381	        {
382	          fptr = state;
383	          ++rptr;
384	        }
385	      else
386	        {
387	          ++rptr;
388	          if (rptr >= end_ptr)
389	            rptr = state;
390	        }
391	      buf->fptr = fptr;
392	      buf->rptr = rptr;
393	    }
394	  return 0;
395	
396	 fail:
397	  __set_errno (EINVAL);
398	  return -1;
399	}
```

## 0x04 伪代码
通过上面的分析，已经可以根据跟定的`seed`获得随机数，以及对应的`state`了：
```
#include <stdio.h>
#define MAX 1000
#define seed 1
int main() {
    int r[MAX],i,j;
    int state[31];
    state[0] = seed;
    for (i=1; i<31; i++){
            state[i] = (16807LL * state[i-1]) % 2147483647;
            if (state[i] < 0) {
                state[i] += 2147483647;
            }
        }
    for (i=31; i<341;i++){
        state[(i+3)%31] = (state[(i+3)%31]+state[i%31]);
    }
    for (i=341;i<MAX;i++){
        state[(i+3)%31] = (state[(i+3)%31]+state[i%31]);
        r[i-340] = (state[(i+3)%31]>>1)&0x7fffffff;
        printf("%d : %x\n",i-340,r[i-340]);
    }
    return 0;
}
```
代码简化一点就是这样了：
```
#include <stdio.h>
#define MAX 1000
#define seed 1
int main() {
    int r[MAX],i;
    r[0] = seed;
    for (i=1; i<31; i++){
            r[i] = (16807LL * r[i-1])%0x7fffffff;
            if (r[i] < 0) {
                r[i] += 0x7fffffff;
            }
        }
    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<350;i++){
        r[i] = r[i-31] + r[i-3];
        printf("%d %#x\n", i-343, (r[i]>>1)&0x7fffffff);
    }
    return 0;
}
```

## 0x05 预测
可以看到上面存在`&0x7fffffff`，并且还存在除以2，所以要能成功预测的情况是`r[i-31]`和`r[i-3]`都没有`&0x7fffffff`，这样就是
```
r[i] = ((r[i-31]<<1)+(r[i-3]<<1))
对应的随机数还是(r[i]>>1)&0x7fffffff)
```
但是实际上还能更简单，由于我们获得的是随机数，那么就是这样的：
```
rand[i] = (r[i]>>1)&0x7fffffff
r[i] = ((r[i-31]<<1)+(r[i-3]<<1))
rand[i-3] = (r[i-3]>>1)&0x7fffffff
rand[i-31] = (r[i-31]>>1)&0x7fffffff
那么综上可以得到
rand[i] = (((r[i-31]<<1)+(r[i-3]<<1))>>1)&0x7fffffff=>
rand[i] = (rand[i-3]+rand[i-31])&0x7fffffff
```
但是由于存在除以2的原因，所以可能会存在1的误差，所以看运气就好啦~

觉得不错，点个赞？

文章目录