Full Disclosure: Re: Random number prediction

[Aaron Horst <anthrax101 () gmail com>]

This is an interesting method of reducing the keyspace of attack, but
rand() is still a linear congruent PRNG. It should never be used where
cryptographically secure pseudo-random numbers are needed. I would
suggest using Blum Blum Shub or some method based on an existing
cipher in counter mode.

AnthraX101

On 6/30/05, Gabriele Avosani <avosani.gabriele () libero it> wrote:
>  
> Hello there folks, 
> take a look at this source, its called sidis.c 
> /*****************************************************************************************************/
> /* Sidis                                                   
>                                         
> */
> /* CRT rand() function random number predictor                    
>                                   */
> /*                                                         
>                                         
> */
> /* works with every windows and unix random generator                    
>                            */
> /*                                                         
>                                         
> */
> /* this is a full service random number predictor                    
>                                */
> /* the function of CRT rand is the following                    
>                                     */
> /* int rand (void)                                         
>                                          */
> /* {                                                       
>                                         
> */
> /*      _ptiddata ptd = _getptd();                         
>                                          */
> /*        return( ((ptd->_holdrand = ptd->_holdrand * 214013L + 2531011L) >>
> 16) & 0x7fff );         */
> /* }                                                       
>                                         
> */
> /* As you can see the seed starts to set the variable that is returned from
> the pointer              */
> /* then we have a little mathematic and we get 15 bits                      
>                         */
> /* ......                                                  
>                                         
> */
> /* but, from what i discovered, you can read the explaination in sci.math, i
> have made a post there, */
> /* we can do this operation                                
>                                          */
> /* x1 = (seed * y + z)                                     
>                                          */
> /* x2 = (x1 * y + z)                                       
>                                          */
> /* x3 = (x2 * y + z)                                       
>                                          */
> /* the random numbers are: x1 >> 15, x2 >> 15, x3 >> 15                     
>                         */
> /* now .... if we apply a little phormula, i can assure you that:           
>                         */
> /* (x2 >> 15 - z >> 15) * y >> 15 gives us x1 >> 15                         
>                         */
> /* now we can easily brute force the remaining 17 bits                      
>                         */
> /*                                                         
>                                         
> */
> /* Zuc                                                     
>                                         
> */
> /*                                                         
>                                         
> */
> /*****************************************************************************************************/
>   
> #include <stdlib.h>
> #include <stdio.h> 
>   
> #define rand1 666
> #define rand2 32767 
>   
> unsigned long next=-1,w; 
>   
> void main(void)
> {
>  unsigned long x = (((rand2 >> 15) - (2531011 >> 15) >> 15) * 214013 >> 15)
> > > 15;
>  for(long y=0;y<2^17;y++)
>  {
>   w = y * 2^17 + x;
>   next = (w * 214013 + 2531011) >> 32;
>   if( (( next * 214013 + 2531011)>> 15 ) == rand1 )break;
>  }
>  if(next==-1)
>  {
>   printf("Sorry, number not found.\n");
>   return;
>  }
>  for(unsigned short i=0;i<10;i++)
>  {
>   printf("Next number n.%i ---
> %i\n",i,(next*214013+2531011)>>15);
>   next=next*214013+2531011;
>  }
>  printf("Sic transit gloria mundi.\n");
> } 
>   
> Zuc 
> _______________________________________________
> Full-Disclosure - We believe in it.
> Charter:
> http://lists.grok.org.uk/full-disclosure-charter.html
> Hosted and sponsored by Secunia - http://secunia.com/

-- 
AnthraX101 -- PGP Key ID# 0x4CD6D0BD
Fingerprint:
8161 D008 3DAB 86C1 2CA3  AEDE 0E21 DBDE 4CD6 D0BD
_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/