Re: [Full-disclosure] Random number prediction

From: Aaron Horst (anthrax101_at_gmail.com)
Date: 06/30/05

  • Next message: `Zidane Tribal: "Re: [Full-disclosure] Jack Szeszycki" 
    Date: Thu, 30 Jun 2005 11:05:15 -0400
To: Gabriele Avosani <avosani.gabriele@libero.it>

    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/
  • Next message: `Zidane Tribal: "Re: [Full-disclosure] Jack Szeszycki"