12 Mar
2024
12 Mar
'24
8:37 p.m.
The author of this routine has been writing
random-number generators for many years and has
never been known to write one that worked.
It sounds like Ken to me. Although everybody had his
own favorite congruential random number generator,
some worse than others, I believe it was Ken who put
one in the math library.
The very fact that rand existed, regardless of its quality,
enabled a lovely exploit. When Ken pioneered password
cracking by trying every word in word lists at hand, one
of the password files he found plenty of hits in came from
Berkeley. He told them and they responded by assigning
random passwords to everybody. 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.
Doug
12 Mar
12 Mar
10:23 p.m.
On 3/12/24, Douglas McIlroy <douglas.mcilroy(a)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?
One problem with random password generation is to avoid generating
passwords that are or contain naughty words. VAX/VMS version 4.0
added an option for random password generation. They had a very
extensive list of naughty words in many different languages to filter
the random passwords. During beta test they got a bug report from a
high school. The naughty words text file was world-readable and
students were amusing themselves by reading it. At release the file
was protected so that only privileged users could read it.
-Paul W.
10:47 p.m.
New subject: NSFW passwords
Ron Harden’s insult generator solved the NSFW passphrase problem. It is available at
https://cheswick <https://cheswick/>.com/insults
On Mar 12, 2024, at 12:23 PM, Paul Winalski
<paul.winalski(a)gmail.com> wrote:
One problem with random password generation is to avoid generating
passwords that are or contain naughty words. VAX/VMS version 4.0
added an option for random password generation. They had a very
extensive list of naughty words in many different languages to filter
the random passwords. During beta test they got a bug report from a
high school. The naughty words text file was world-readable and
students were amusing themselves by reading it. At release the file
was protected so that only privileged users could read it.
13 Mar
13 Mar
7:22 a.m.
On Tue, Mar 12, 2024 at 12:23 PM Paul Winalski <paul.winalski(a)gmail.com>
wrote:
On 3/12/24, Douglas McIlroy
<douglas.mcilroy(a)dartmouth.edu> wrote:
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
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? 
12 Mar
12 Mar
10:32 p.m.
i wrote the generator.
dmr or rhm wrote the comment.
it came about after one of the first
drafts of a graphical pool game.
the balls were points and the test
was the bouncing off the edge of
the pool table. the balls were placed
at "random" places on the table,
they were started with "random"
directions and "random" velocities.
frictionless it ran forever.
after many minutes, from a mess
of dots, they form a line, later a couple
lines, later several points, and finally
after a large fraction of an hour, all the
balls would converge on a single dot.
that version of the program was saved
with the name "wierd" (spelling on purpose).
i have no idea if it exists now.
On Tue, Mar 12, 2024 at 7:38 AM Douglas McIlroy <
douglas.mcilroy(a)dartmouth.edu> wrote:
The author of
this routine has been writing
random-number generators for many years and has
never been known to write one that worked.
It sounds like Ken to me. Although everybody had his
own favorite congruential random number generator,
some worse than others, I believe it was Ken who put
one in the math library.
The very fact that rand existed, regardless of its quality,
enabled a lovely exploit. When Ken pioneered password
cracking by trying every word in word lists at hand, one
of the password files he found plenty of hits in came from
Berkeley. He told them and they responded by assigning
random passwords to everybody. 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.
Doug
284
days inactive
285
days old
4 comments
5 participants
participants (5)
-
Douglas McIlroy -
Ken Thompson -
Paul Winalski -
Russ Cox -
William Cheswick