[TUHS] Re: early unix rand

[Russ Cox <rsc@swtch.com>]

[-- Attachment #1: Type: text/plain, Size: 1609 bytes --]

On Tue, Mar 12, 2024 at 12:23 PM Paul Winalski <paul.winalski@gmail.com>
wrote:

> On 3/12/24, Douglas McIlroy <douglas.mcilroy@dartmouth.edu> wrote:
> >
> > That was a memorable
> > error. Guessing that the passwords were generated by
> > a simple encoding of the output of rand, Ken promptly
> > broke 100% of the newly "hardened" password file.
>
> To do that wouldn't you need to know the seed value that was used?  Or
> did this version of rand() always generate the same sequence of
> pseudo-random numbers?


Any LCG-based version of rand (including, say, java.lang.Math.random)
always generates the same periodic sequence of numbers; the seed only
controls where in the sequence you start (you start where the seed appears).

Worse, any LCG-based rand truncated to k bits is itself just a periodic
sequence of the 2^k possible truncations. The trivial k=1 case of this is
that if
you look at the bottom bit of successive rand outputs on any of these
generators, it is always alternating between even and odd, no matter
what constants you pick. (Almost. If you pick bad constants you could
get all even or all odd instead.)

I don't know what the simple BSD encoding was, but those two facts
combined mean that an example of an encoding that would be easily broken
would be to pick a fixed-length sequence of letters drawn from
"abcdefghijklmnopqrstuvwxyz123456"[rand()&31].
That would just produce the same 32-character permutation
over and over again, so there would only be 32 possible passwords,
depending only on where in the sequence you start.

Best,
Russ

[-- Attachment #2: Type: text/html, Size: 2240 bytes --]