Hi!
first let me state, that I had some private conversation about this
issue with Vadim, before and after he posted this message.
Unfortunately nobody else jumped onto the train, so I will add my $0.02
at this point to stimulate discussion :-)
On Fri, Aug 04, 2000 at 02:28:42PM +0300, Vadim Fedukovich wrote:
> I'd like to warn developers using Openssl's PRNG to make sure by-pass
> "startup" problem as described in Peter Gutmann's paper
> http://www.cs.auckland.ac.nz/~pgut001/pubs/random2.pdf
I also read the paper and thought about his remarks with respect to the
OpenSSL-PRNG.
[Background: I am writing my own "prngd" based on the OpenSSL-PRNG as
a drop-in replacement (or to support it) so that it will not be drained,
which is necessary for me to support daemons started from inetd.
Interested parties can access it from
http://www.aet.tu-cottbus.de/personen/jaenicke/postfix_tls/prngd.html
but I writing this to advertise it here :-)]
> In short, "state" is long enough, 1023 bytes, and is filled zeros on
> startup. Well, on some OSes. Yes, PRNG output results in mixing the
> "state" and will eventually provide for higher-quality randomness.
> Before that happens, namely until there are still zeros in state,
> the only one hash is used to provide for randomness.
>
> Another one problem exists: the very first run of PRNG use only half
> of that hash that cuts the search space half. That is, even properly
> seed PRNG(several hundreds of bytes) will output first
> MD_DIGEST_LENGTH/2 bytes subject to search-it-all attack with search
> space MD_DIGEST_LENGTH/2 bytes.
>
> Solution is simple: output and forget first N*1023 bytes from PRNG.
P. Guttman uses N=10 mix cycles for his own PRNG, but that number seems
to be pretty arbitrary.
For PRNG I have decided to rather read (1024+n)bytes with n being determined
as a random number from 4*(0-255) before actually retrieving the bytes
requested, but I do so for every retrieval, so that an attacker who might
be able to suck bytes at will faces the problem that he doesn't know which
bytes where retrieved during the (1024+n) retrieval (they are thrown away)
and he doesn't know at which position the pointer actually is.
(I also stir in some (not much) random bits from tv_usec etc that point and
the 1024+n retrieval forces one complete round of mixing.)
Hence, my proposal would be to not (or at least not only) mix by retrieving
N*1023 bytes before the first retrieval but perform a complete mix at each
retrieval.
This should be advantageous when it comes to another "weak point" mentioned
by Peter Guttman. The PRNG is not only used to generate the secret keys,
but also session-IDs... So the amount of bits sucked from the PRNG (and
that could be used to guess the internal state) is rather low.
Mixing the pool whenever bytes are retrieved could make this system a bit
stronger.
> After half of initial hash was learned, this attack can be escalated to
> use next 10 bytes of PRNG for search the other half of initial hash.
>
> Besides, an interactive guessing attack can be mounted after learning
> initial hash before mixing the "state" provided low-entropy seeds.
>
> Please dont worry too much: half-of-SHA1 is still huge enough to search
> easy and several more bits come from hashing PID on some OSes.
I want to add another point. When calculating the premaster secret,
48bytes (-2?) are retrieved in the client. In the server, the session_id
and other items are retrieved.
[I must admit that i have only partially investigated the source, so I
am a bit careful to add "hard" numbers here.]
The minimum number of entropy-bits is 128 (=16bytes), which is also retrieved
from /dev/urandom, if no other seeding was done.
Compared to a key-size of 128bits (RC4-MD5) or even 168bits (3DES) and
considering that bytes from the random pool may be used for other items,
I would recommend to increase the mininum amount of seed to either 32 bytes.
or even 48bytes with respect to the size of the premaster secret
(#define SSL3_MASTER_SECRET_SIZE 48).
I hope that I have stimulated this discussion a bit more.
Best regards,
Lutz
PS. Even though time is a limited item also for me, I don't want to only
"ask for changes", I would also consider contributing changes if/once
agreement about what should be done is reached.
--
Lutz Jaenicke [EMAIL PROTECTED]
BTU Cottbus http://www.aet.TU-Cottbus.DE/personen/jaenicke/
Lehrstuhl Allgemeine Elektrotechnik Tel. +49 355 69-4129
Universitaetsplatz 3-4, D-03044 Cottbus Fax. +49 355 69-4153
______________________________________________________________________
OpenSSL Project http://www.openssl.org
User Support Mailing List [EMAIL PROTECTED]
Automated List Manager [EMAIL PROTECTED]
