美文网首页CTF Re Mo writeup
关于Linux的伪随机数分析

关于Linux的伪随机数分析

作者: SueLyon | 来源:发表于2017-11-25 15:53 被阅读15次

rand函数

函数说明:
rand()会返回一随机数值,范围在0至RAND_MAX 间。在调用此函数产生随机数前,必须先利用srand()设好随机数种子,如果未设随机数种子,rand()在调用时会自动设随机数种子为1,关于随机数种子请参考srand()
返回值:
返回0至RAND_MAX之间的随机数值,RAND_MAX定义在stdlib.h,其值为2147483647

srand函数

函数说明:
srand()用来设置rand()产生随机数时的随机数种子。参数seed必须是个整数,通常可以利用geypid()或time(0)的返回值来当做seed。如果每次seed都设相同值,rand()所产生的随机数值每次就会一样。

Linux随机数分析

最一般的随机数过程,即srand->rand的过程,目的是根据获得的随机数逆向出种子

unsafe_state:

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   };
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 };

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 }

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 }

伪代码:

通过上面的分析,已经可以根据跟定的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;
}

预测:
可以看到上面存在&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的误差

相关文章

  • 关于Linux的伪随机数分析

    rand函数 函数说明:rand()会返回一随机数值,范围在0至RAND_MAX 间。在调用此函数产生随机数前,必...

  • 密码学基础之伪随机数

    随机数分类 真随机数 伪随机数2.1 强伪随机数2.2 弱伪随机数 真随机数:其定义为随机样本不可重现。实际上只要...

  • 多线程环境下生成随机数

    生成伪随机数据 Java里有伪随机型和安全型两种随机数生成器。伪随机生成器根据特定公式将seed转换成新的伪随机数...

  • 生成随机数

    两个C函数 rand()函数生成的随机数是伪随机数,所谓伪随机数,指的是程序每次运行,生成的随机数都是不变的,生成...

  • Python random 模块详解

    我们可以先来了解下伪随机数和真随机数的概念。 伪随机数:伪随机数是用确定性的算法计算出来自[0,1]均匀分布的随机...

  • python中random模块功能详解(python工程狮)

    random — 生成伪随机数,random模块为各种分布实现伪随机数的生成。 1.random.random()...

  • 一文带你读懂生成随机数的方式?

    计算机的随机数都是由伪随机数。例如:rand() 函数可以用来产生随机数,但是这不是真正意义上的随机数,是一个伪随...

  • Random简述

    1 Random Random用来创建伪随机数。所谓伪随机数,是指只要给定一个初始的种子,产生的随机数序列是完全一...

  • 2019-07-09

    伪随机数,是通过一些数学算法生成的随机数,并非真正的随机数。密码学上的安全伪随机数应该是不可压缩的。对应的“真随机...

  • bitcoin源码-1-获取密钥对

    关键概念 随机数我们在软件中一般使用的随机数实际上是伪随机数,具有统计学伪随机性。统计学伪随机性指的是在给定的随机...

网友评论

    本文标题:关于Linux的伪随机数分析

    本文链接:https://www.haomeiwen.com/subject/jiccbxtx.html