Re: lynx-dev SSL for Lynx 2.8.4

[dec0de]

Hi folks...

Just a few thoughts on the random number thing - I was doing a little
research into imlementations of rand() type functions recently and I
discovered the following:

- 'linear congruential' pseudorandom sequence generators are the most
popular implementation. It's possible to solve for the three internal
coefficients with an extremely small sample, and you can then perfectly
predict the sequence.

- a random seed does *not* imply a random sequence. Most RNGs have
sequences that if you were to graph them, lead to cycles, some of them
quite short (< 1M numbers), depending on the seed. Some seeds settle into
longer cycles than others, and the number of cycles for each RNG is not
necessarily that large.

- we're using rand() or an equivalently predictable routine in a couple of
places in the lynx 2.8.4 code - to generate temp file names, and for what
looks like a one - time key for the 'options' page.

So, I'd advocate for integrating a strong rng in the lynx distro, so that
we're secure cross - platform. Here's an example of some code that
predicts the microsoft rand() function on the basis of a sample of two
numbers:

============
// randpredict.c
// Prediction of CRT rand() function; the lame implementation assumed is
below; I'm not sure how long it's been
// around but I presume a *long* time.
// address@hidden
// 27/12/2000

/*

  int __cdecl rand (
        void
        )
{
#ifdef _MT

        _ptiddata ptd = _getptd();

        return( ((ptd->_holdrand = ptd->_holdrand * 214013L
            + 2531011L) >> 16) & 0x7fff );

#else
        return(((holdrand = holdrand * 214013L + 2531011L) >> 16) &
0x7fff);
#endif
}

*/


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



int Next( int n1 )
{
        return  ( n1 * 214013 ) + 2531011;
}


int Predict( int n1, int n2 )
{
        // n1 is the low order 15 bits of the high order word. Generate
all 128k possibilities and verify which result in n2.
        int nSecret = 0, i = 0;

        for ( i = 0; i < 0x00010000; i++ )
        {
                nSecret = (n1 << 16) + i;

                if ((((( nSecret * 214013L ) + 2531011L ) >> 16 ) &
0x7fff) == n2 )
                {
                        printf( "%x : correct\n", nSecret );
                        printf( "next:%d\n", ( Next( Next( nSecret ) ) >>
16 ) & 0x7fff );
                }

                nSecret |= 0x80000000;

                if ((((( nSecret * 214013L ) + 2531011L ) >> 16 ) &
0x7fff) == n2 )
                {
                        printf( "%x : correct\n", nSecret );
                        printf( "next:%d\n", ( Next( Next( nSecret ) ) >>
16 ) & 0x7fff );
                }
        }

        return 0;
}


int Syntax()
{
        printf( "randpredict attempts to guess the next number in a
sequence of numbers generated by the MSVCRT implementation\n" );
        printf( "of the rand() function. Works on the vcrt supplied with
MSVC 6.\n" );
        printf( "Syntax: randpredict <n1> <n2>\n" );

        return 1;
}


int main( int argc, char *argv[] )
{
        int n1, n2;

        if ( argc != 3 )
                return Syntax();

        n1 = atoi(argv[1]);
        n2 = atoi(argv[2]);

        Predict( n1, n2 );

        return 0;
}




============


ps are there any security - related code components I can help with?

        -dec0de.



On Sun, 7 Jan 2001, David Woolley wrote:

> > random state file if one is available, the time, and the PID,) then pull a
>                                              ^^^^
>
> The time, except for the milliseconds and microseconds parts, is useless
> for creating cryptographic random numbers.
>
> > random state file if one is available, the time, and the PID,) then pull a
>                                                            ^^^
> This helps a bit, assuming an attacker has no other access to it (all
> local attackers do), and even then, it means that successive numbers
> are not completely independent and that and that the machine has been
> running many days (otherwise there is a bias to low numbers).
>
> > long's worth of random bytes out of the PRNG and use it to seed the
> > system-supplied random number generator, and then pull random numbers off of
> > the system's RNG until the PRNG is happy.  I then write out some randomness
>
> This is fixing a symptom, not creating true entropy.  The output of the
> system's RNG is a deterministic function (maybe with some difficult to
> recover information about the number of cycles) of the seed.  Worse,
> one doesn't know the precise function on each platform.
>
> > to disk for next time.  It could be made better, but this is more than
> > sufficient for what we're trying to accomplish after a few runs to get the
> > stored randomness well churned.
>
> You are churning it, making it more difficult to invert the state, but
> you are not adding entropy, so a brute force forwards approach may be
> feasible (the strongest link is the cumulative stored randomness).
>
> I repeat that most failures in big name commercial crypto systems
> recently have been due to thnks like predictable random numbers and
> other operational laxness (it was procedural laxness that really made
> Enigma breakable in WW II, as well).
>
> ; To UNSUBSCRIBE: Send "unsubscribe lynx-dev" to address@hidden
>




; To UNSUBSCRIBE: Send "unsubscribe lynx-dev" to address@hidden