How was early randomness generated?

Question

Many programs make use of randomness, from BASIC guess-the-number games to encryption key generators. This randomness could have been generated in many, many different ways: hardware, software, software seeded by hardware...

What techniques were used to generate randomness in early computers, and were cryptographically secure sources of randomness commonly used?

Answer 1

The one-word answer to your question is "badly".

The way to create random numbers quickly is via a Pseudorandom number generator (PRNG). That Wikipedia page gives the history of PRNGs and in particular notes that linear congruential generators are/were common, with quite a few failings including periodicity (i.e. it cycles through the same sequence of values), poor distribution, predictability, and quite a few other faults that make them poor choices for use in cryptography. That page also describes linear-feedback shift registers but I don't recall them being used in the BASICs of my youth.

The first decent PRNG is the Mersenne Twister, which was invented in 1997. It requires 2.5 KiB of RAM to store its state, and is relatively computationally intensive, so it would be ludicrous to provide it as the standard random number source of a BASIC running on a machine with only a few tens of kilobytes of RAM and a slow CPU even if the algorithm had been known at the time.

Cryptographically-secure random numbers need the aid of a hardware device that contains true randomness, such as interrupt timings from I/O devices, or even a dedicated quantum noise source. Again, older machines tended not to have much in the way of interrupt-driven I/O, commonly using a vertical blank interrupt to trigger a polling process instead.

For a concrete example, look at the source of the Sinclair ZX Spectrum's RND function. In case that link goes bad, I'll also summarise it. There is a 16 bit system variable SEED which unsurprisingly contains the current random number seed. When you call RND, it computes (SEED+1)*75 mod 65537 - 1 which it stores in SEED, and returns SEED / 65536, i.e. a value in the range [0, 1).

Because SEED is just 16 bits, it's clear that this PRNG can't have more than 65,536 possible states. Mathematical analysis of the function it uses to generate the next SEED will show that it has exactly 65,536 states, and thus will repeat and generate the same values after that many calls. It's alright for deciding where to put aliens on the screen, but I wouldn't trust my online banking to it...

Answer 2

Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin — John von Neumann

The method that RAND used to calculate their A Million Random Digits with 100,000 Normal Deviates is described in this brief paper: History of RAND's Random Digits: Summary from 1949. In summary, the gated output of a gas-filled thermionic valve (such as a 6D4 Thyratron [Sylvania, 1944], well known to produce noise when operated in a magnetic field) was used to increment a five bit counter. The noise signal was interrupted every second and the counter read through a BCD converter to produce decimal digits. As the counter would overflow more than 3000 times per second and was fed by pulses with very fast random timing, the results passed all randomness tests available at the time. A similar gas-discharge valve noise system was used in the UK's random draw generator (ERNIE) for premium bonds.

Alan Turing identified a very early need for true random numbers in computing, and his design for the never-built Automatic Computing Engine (ACE) (1945-6) was to include valve-based noise generators. These were to be used to assist in Monte Carlo simulations, as developed by Ulam for nuclear fission modelling.

(I seem to remember reading the statement about Turing and RNGs in George Dyson's book Turing's Cathedral, but I no longer have a copy to check.)

Answer 3

The Commodore 64 had a built-in audio processor, called the SID chip. This chip would generate sounds based on (among other things) a frequency (e.g. 440 Hz) and a wave shape (square, sawtooth, etc.). One of the options was to generate "white noise", which is basically a random series of volumes. Now the fun bit about this is that you could read a snapshot of the current volume from one of the SID registers, which in white noise mode, was an essentially random value from 0-255. This technique was commonly used on this platform. Even, if I recall correctly, in BASIC programs, though BASIC had a built-in random function.

Now, I'm pretty sure this randomness was generated in hardware, which probably means it was closer to true randomness than the software techniques described in the other answers. Or it may have been a variant of the circuit described in tofro's answer. In any case, there may well have been biases in the distribution or other features in the values generated that would make these values weak for cryptography.

Answer 4

Interesting question. After all, it's the main job of a computer to come up with deterministic results, which is pretty much the opposite of pure randomness.

In reality, coming up with a series of non-deterministic numbers from a digital circuit only is considered technically impossible. Modern computers use "known noise" in their peripheral devices or even dedicated noise generator circuits to seed their random number generator. Older home computers didn't really have that much periphery to choose from so used "close-to random" values as a seed like video flyback counters or "time since switched on".

Once you have a (more or less random) seed (initial value), a simple RNG (Random Number Generator) typically consists of an LFSR (linear feedback shift register) that runs the seed through a binary polynom, generating a new value from the previous one that "looks" random (picture source: Wikipedia) (Today's computers tend to use much more sophisticated RNGs)

Note what "looks like hardware" in the picture can easily be reproduced by software in a computer. A random number would then just be the current value of that 8 bit register. A new random value is being generated on every fetch by shifting the old value one bit and feeding back the "carry" and bit positions determined by the chosen polynom into the lowest bit.

In pseudocode, an RNG looks somewhat like this (implements the above picture):

carry = (x & $80) != 0 
oldx = x
x = x >> 1
x |= (carry + (oldx & $04) > 0 + (oldx & $10) > 0 + (oldx & $20) > 0) != 0

In reality, most of the RNGs did, different from the example, normally use 16-bit shift registers and the polynoms might look different.

The initial state i.e. the seed of the shift register is normally set by the RANDOMIZE (or similar) Basic keyword. This might be the most misunderstood and misused basic keyword ever - It somehow seems to imply to make the RNG "more random" but instead does the exact opposite - By seeding the RNG with a constant number, you can make different computers with the same BASIC produce the exact same sequence of random numbers. Using this technique you can easily create encryption programs that can only be decrypted by the same RNG using the initial seed as a key (i.e. cyphers produced by the Commodore C64 that can only be deciphered by a C64). I also remember a Basic program I once wrote for the Sinclair QL that calculated the value of PI by simulating rainfall (random coordinates) onto a circle in a square and determining whether the raindrop fell into the circle.

A "cryptographically secure" source of a seed for the RNG is not known to me from early computers - At least not of home computers. After all, proper encryption which is the main use for RNGs was not necessary on a non-networked computer (most of the early computers were) as long as you had a proper door in front of it. Only the development of larger networks and the internet made encryption really necessary - before that time, you could simply rely on physically securing computers.

Answer 5

On some games like "Super Mario 64", the randomness was determined by simply XORing the value whenever it's called (technical detail can be found here). This allowed it to be exploited, especially on places where it's never called naturally, like Peach's castle, but by doing moves that generate dust (which calls the RNG function itself), it can be exploited. One example of such a glitch can be seen here.

For example, here's the raw function for randomness in Super Mario 64 in C:

unsigned short rng_function(unsigned short input) {
    if (input == 0x560A) input = 0;
    unsigned short S0 = (unsigned char)input << 8;
    S0 = S0 ^ input;
    input = ((SO & 0xFF) << 8) | ((S0 & 0xFF00) >> 8);
    S0 = ((unsigned char)S0 << 1) ^ input);
    short S1 = (S0 >> 1) & 0xFF80;
    if ((S0 & 1) == 0) {
        if (S1 == 0xAA55) input = 0;
        else input = S1 * 0x1FF4;}
    else input = S1 & 0x8180;
    return (unsigned short)input;
}

Answer 6

Many early systems used the RANDU PRNG (seed = seed*65539 mod 2³¹; the initial seed must be an odd number) which happened to be not very random. If it is used to generate 3D coordinates, the resulting points are positioned on a few fixed planes. Here is another visualization of this in an implementation of BASIC on Elektronika BK-0010:

Testing for RANDU can be done by drawing a few thousands of pixels with

PSET (RND*width,RND*height),RND*numcols

and observing the diagonal stripe pattern.

Answer 7

Some games used the contents of ROM, or a subset of it, starting from a timer-fed address and looping. Because of the limited amount of space available, ROMs tended to be written to be very compact though you will sometimes get blocks of zeroes or repeating data, which is why a subset is often used. Other games on the Z80 CPU used the bottom 7 bits of the R register, which is actually there to provide a refresh signal for DRAMs, and increases by 1 every instruction fetch. This is often random enough for game purposes though there's a strong correlation between close reads. There wasn't much call for encryption-strength randomness on a computer not attached to a network. Some of the game loaders used scrambling and tricks to protect their games from being cracked or modified, but this decryption had to actually be deterministic to produce the same results every time.

Answer 8

The Apple II ROM keyboard-reading routines incremented a "random" number while waiting for keypresses:

KEYIN    INC   RNDL
         BNE   KEYIN2     ;INCR RND NUMBER
         INC   RNDH
KEYIN2   BIT   KBD        ;KEY DOWN?
         BPL   KEYIN      ;  LOOP
         STA   (BASL),Y   ;REPLACE FLASHING SCREEN
         LDA   KBD        ;GET KEYCODE
         BIT   KBDSTRB    ;CLR KEY STROBE
         RTS

Of course, that only works after you've waited for a keypress, otherwise you're relying on the (sometimes slightly unpredictable) initial values of RAM on power-up.

Answer 9

Don't forget lookup tables. Those were used long before "true" pseudo-random number generators, and usually worked well enough. The simplest is just copying, say, 256 numbers from your random number codebook (a physical book, yes) to your program, and indexing into this memory with a successively incremented index.

Now, this is obviously nothing even close to randomness required in cryptography, or anything where correctness depends on good randomness (e.g. genetic algorithms, Monte Carlo approximation, ...). But it's good enough for games. As a reasonably recent example, the original Doom used a "random" number generator exactly like this - 256 pre-defined numbers taken in a loop. This had some visible side-effects (the BFG weapon could "theoretically" inflict much more (or less) damage than it could in practice, thanks to the random generator not being random enough). This was a very common approach in games, since it's extremely cheap (just a single shared "pseudoRandomIndex++" and a memory read from something that's always in CPU cache), and true randomness is seldom required - the main sources of entropy in a typical game are from mostly random ordering of events. BFG in Doom became so heavily biased mainly because it took a lot of those pseudo-random numbers in a sequence.

Answer 10

During the 1940s, John von Neumann developed a pseudorandom number algorithm called the middle-square method while conducting Monte Carlo simulations on the ENIAC computer for the Manhattan Project.

The method was very simple - quoting from the Wikipedia article:

To generate a sequence of 4-digit pseudorandom numbers, a 4-digit starting value is created and squared, producing an 8-digit number. If the result has fewer than 8 digits, leading zeroes are added to compensate. The middle 4 digits of the result would be the next number in the sequence, and returned as the result. This process is then repeated to generate more numbers.

Compared with more modern techniques the period of the middle-square method was quite short, however it had the advantages of 1) being faster than reading random numbers off of punch cards, and 2) pseudorandom numbers that got stuck in a loop could be easily detected and discarded.

Answer 11

The UK Government has a thing called Premium Bonds. You lend the government some money. Instead of giving you interest, they enter you in a draw every month for a cash prize.

The winning bond numbers are chosen by a computer called ERNIE. The first ERNIE was created in 1957 by Tommy Flowers (who created the ultimate fully electronic retro computer, the Colossus) amongst others.

It used the signal noise generated by a neon gas diode valve as a source of randomness. Even the modern version doesn't rely on the normal means of generating randomness in computers but on thermal noise generated by transistors.

were cryptographically-secure sources of randomness commonly used?

The answer to this question is interesting because "cryptographically secure" is a moving target. It is, however, reasonable to say that no general purpose civilian computer had a cryptographically secure random number generator before the widespread adoption of the Internet. Apart from the fact that, for the most part, they were too slow to do properly secure cryptography there were no use cases.

Answer 12

Others have covered PRNGs commonly used in early machines, so I wanted to add some detail on hardware sources of randomness. Some machines do have dedicated, tested random number generators, but retro computers usually had to make do without them.

Computers with analogue inputs may be able to use those to generate random bits. Typically those inputs are somewhat noisy, due to limitations of the analogue-to-digital converters of the time and electrical noise. For example, the Atari 2600 and related machines could read analogue paddles for Pong style games, which worked by measuring the time it took to charge a capacitor. The charge rate was varied by a current limiting potentiometer in the paddle. Other machines like the BBC Micro had more advanced but still somewhat noisy analogue-to-digital converters.

Due to noise the lowest order bit of an analogue-to-digital conversion tends to be somewhat random on those systems. Sampling those bits, and using them to seed a PRNG can produce better results than just using a PRNG on its own.

Another common source of randomness was timers. Applications that were not synchronized to the screen refresh could often use registers in the graphic processor, like the current beam position, as a source of randomness. Depending on the application, it might only use the lowest order bit, for example if the current scanline is odd or even.

Measuring periods between user input was a popular technique. Times between key strokes, down to the millisecond or below level, are known to be fairly random. Mice are even better for this, although many users of early systems didn't have them.

Other more exotic sources of randomness included storage medium response times, for example how long a floppy disk took to seek during loading. Since the angle that the rotating disc started at was somewhat random, the overall time to seek to any particular track also varied.

All of these sources had their limitations, so were typically combined and used to seed a PRNG or entropy pool rather than being used directly.

Answer 13

John Von Neuman, during the Manhattan project suggested using a 4 digit number, square it, then use the center 2 digits, for the next round. I saw this in Richard Rhodes, book "the Making of the Atomic Bomb". The problem with the middle number technique, is it will cycle, also if you pick up 0's, then will repeat.

Answer 14

Here is another tidbit from early Soviet computing. A PRNG subroutine suggested for the M-series computers, the first of which was developed in 1955-1958 and performed at about 20 TIPS, had the following note:

The period of the generator is 2³³-1 = 8 589 934 591, that is, the generator has a practically infinite [emph. mine - Leo B.] period.

The subroutine was 6 instructions long; therefore, it would require about a month just to exhaust the period by running the generator in a loop without doing any useful work. The MTBF of a vacuum tube machine was likely an order of magnitude less than that.

The scan of the book is here, the routine is on page 349 of the book.

The following C program reproduces the algorithm on a 64-bit CPU (hence the need to mask 36 bits, absent in the original) and verifies the period in about 22 seconds on a 3 GHz Intel:

#include <stdio.h>
#define BITS36  0777777777777LL
#define UPPER13 0777740000000LL
#define START   0504277326410LL
unsigned long m20(unsigned long d1) {
    unsigned long c1 = (d1 << 13) & BITS36;
    unsigned long c2 = d1 ^ c1;
    c2 = c2 & UPPER13;
    c2 >>= 20;
    return c1 | c2;
}
main() {
    unsigned long loop_len = 0, s = START;
    do {
        s = m20(s);
        ++loop_len;
    } while (s != START);
    printf("Loop length = %lld\n", loop_len);
}

The original code had to do the final f. p. addition of zero to convert the result into a floating point value in the range [0;1).

Answer 15

Speaking of the 1980s, if that counts as "early":

The standard reference for this was Donald Knuth's The Art of Computer Programming, 2. ed. (1981), Volume 2, Seminumerical Algorithms, of which Chapter 3 is "Random Numbers". The 177-page chapter give a mathematical treatment, beginning with linear congruential pseudorandom generators, and how to pick the parameters, and continues through spectral and other statistical tests.

When we needed pseudorandom numbers, and didn't want a built-in poor or unknown-quality generator, that's how we made them in the 1980s.

Were they "cryptographically secure"? Not by today's standards. However, the microcomputers of that period were single user and didn't normally have any communications: business users would just lock up the accounting floppies in a drawer/safe. Multiuser minicomputers (PDP11s, VAXes etc) were unusual except in research places, but still would often have one-way hashes for passwords. The first time I saw one cracked it took a few hours of CPU circa 1985, and normally you had to have both legitimate access (to get anything to crack) and physical access to terminals as dial-up access was rare. Very few people had hours of CPU time available without leaving a lot of evidence. You'd look for motive, means and opportunity amongst a few hundred people; not like today where it might be anybody on the internet and digital banking is open to pretty much everywhere.

Answer 16

In the C89 language specification, the rand PRNG is defined. This was used by many programs compiled from C source code.

static unsigned long int next = 1;

int rand(void)   /* RAND_MAX assumed to be 32767 */
{
         next = next * 1103515245 + 12345;
         return (unsigned int)(next/65536) % 32768;
}

void srand(unsigned int seed)
{
         next = seed;
}

An explanation of the magic numbers is as follows:

The 32768 is there to ensure that rand() won't generate 32767 half the time on 16-bit machine, while the 65536 deals with the fact that the low-order bits of an LCG with a power-of-2 modulus are far less random than the high-order bits (in particular, the LSB alternates between 0 and 1). The 12345 and 1103515245 are derived from the modulus of 4294967296 to ensure the generator covers the full potential period. – Mark

Answer 17

A very primitive "random" generator is used in the 1984 Karate Champ game.

It doesn't even try to be random, it's just using a timer tick value and takes the modulus using the max value. It then returns a number between 0 and max value (not included).

; random method
; < d: seed from timer
; < e: max value (not included)
; > a: value between 0 and e (not included)
random_modulus_B0EE:
B0EE: AF          xor  a    ;  clears a
B0EF: 06 02       ld   b,$08  ; b <- $08    ; do it 8 times at least
B0F1: CB 22       sla  d    ; d *= 2
B0F3: CB 17       rl   a    ; a <- 1 if carry set else 0
B0F5: BB          cp   e    ; compare a with e
B0F6: DA F6 B0    jp   c,$B0FC  ; if e >= a skip to djnz, repeat only if a == e
B0F9: 93          sub  e    ; a <- a-e
B0FA: CB C2       set  0,d  ; d &= 1
B0FC: 10 F9       djnz $B0F1  ; repeat 8 times
B0FE: C9          ret

This "random" method is called with D = some timer counter that increases each VBLANK interrupt.

On a fighting game, the CPU doesn't have a lot of decisions to take in 1 frame when it does so the calls are enough spaced in time to yield different return values each time. In the case of the demo (CPU vs CPU) the CPU random requests aren't synchronized (but luck) else they would attack with the exact same moves.

Answer 18

Some games use a pseudo-random generator that is simpler than modern.

Gomoku Narabe has a pseudo-random generator that uses RAM space 0038~003F, and iterates once per frame. When fixed to 0000000000000000 using cheats, the opening is fixed.