How were random numbers generated for one-time pads before the late 1940s, i.e. before radioactive decay, thermal noise, or other fundamentally random phenomena could be readily measured? Physical methods that might have been used before that era such as ‘coin flipping’, dice rolling, or other similar processes will always contain non-random traces which, at least in theory, would render any messages using them quite breakable.
This came up when I was reading about the Venona Project (an interesting thing in itself). Basically, this refers to the organized effort to break high-level Soviet messages that had been encrypted using one-time pads. The break for the decrypters came when it was realized that the Soviets had violated a fundamental tenet of one-time pad encryption by using the same random sequence to encode more than one message. The re-use of one-time pads had occurred circa 1941 as Hitler approached Moscow when, presumably due to the exigencies of war, the factory producing them couldn’t meet demand.
But, back to my question, however the Soviets generated their random numbers before 1941, they seem to have done a very job. AFAIK, only messages (or parts thereof) encrypted with the re-used pads were ever broken. Do we know how they or others of the era would have generated them?
I don’t know enough on the subject to talk further, but this is clearly untrue. Me throwing an (almost) fair die many times is for all intents exactly as unpredictable as me using cosmic radiation to get a choice of 6 possibilities. A die has no memory and the “noise” between throws is something that nobody could ever calculate.
Yes, but after many uses, an almost fair die could become significantly unfair. The die could wear such that some numbers come up more often than others.
Even unfair dice are OK as long as there is some randomness, which you can filter by processing the raw input.
Wanted to mention, the famous “A million random digits” table (1947) used a sort of electronic “roulette wheel” (pulse source). (They indeed had a lot of trouble tuning up the machine and postprocessing the data until it was sufficiently random.) Kendall (1930s) used mechanical devices (an actual rotating disc).
Here is a document from 1952 describing a U.S. device to generate 7 random characters per second. I think the Soviets during W.W.II had a much cruder system, perhaps typists told to peck randomly at their typewriters!
The main problem with using dice would be the slow speed. Precision dice are rather “fair” I think; anyway there are algorithms to convert random numbers with known bias to uniform random numbers.
How easy is it to apply the filter without computers? There’s a time factor. If it takes a long time to do this filtering, there’s a tendency to skip it in the interest of producing random numbers faster.
I can’t imagine that producing anything close to being truly random.
Some of the stuff RAND did, like transforming digits by adding them to the corresponding digits on the previous page, is not that time-consuming, but the need for literally millions of random numbers goes along with the rise of computers to run Monte Carlo simulations that consume that many numbers, so there is not really any problem.
If one merely needs a few random digits for a secret password and is manually flipping a coin or rolling dice, and the die/coin is not too badly loaded, then something like von Neumann’s procedure will increase the number of rolls or flips required by a small constant factor (like 2x or 3x), but even for a few dozen digits, who cares. That procedure also assumes the bias is not changing with time, which seems reasonable for a very small sample.
They don’t have to be truly random.
Just random enough that the enemy de-crypters, using 1940s equipment, could not decode them in time. The ‘in time’ is important – most military messages have a very short value-life, often less than 24 hours. After that, it’s too late for your troops to respond, even if they know what the message said.
I’ve seen several references to the Brits using such ball-and-basket systems circa WWII. There’d be 26 numbered balls. Rotate the cage a specified number of times, reach in and pull a ball out. Write the number down. Put the ball back. Repeat.
One huge advantage of this system over dice/coins/etc. is there is no need to work out an awkward encoding into the alphabet size. (And yes, they spelled out numbers and avoided punctuation to keep the alphabet size down. This was a big issue pre-computers.)
Even with ball-and-basket there’s a chance for mistakes to be made. A person might look in before selecting a ball. The wooden balls might not all feel the same. People tend to reject selecting the same number twice in a row despite it being more common than most people think, etc.
Neal Stephenson in Cryptonomicon puts in a fictional incident where one of the women doing the ball-and-basket thing wasn’t doing it right.
Note that one-time pads are sort of in the same mindset to some as security through obscurity (but not really). So one could take a table of random numbers (which had been published widely by that time), and apply a mix of random and Mathematical transformations to it and you have another stream of numbers that looks really random. (Of course it isn’t if you know the protocol and the additional new random numbers aren’t that many.)
Part of the reason I was impressed with the success of the Soviet’s ‘primitive’ randomization procedure was that, aside from the few percent of messages decrypted as a result of the page duplication, the huge majority (supposedly) remained uncracked even many years later when more modern electrical/electronic approaches were available to use in attempts to break it. Perhaps that is a reflection of the relatively small amount of traffic available for ‘study’ but I guess it also suggests a pretty decent approximation to random.
Early roulette wheels were made no better than they should be, and with the development of early statistical theory became statistically predictable. The gambling houses realized this at about the same time that statisticians did, and were in the process of replacing their wheels at the same time that early wheel-counters where trying to get rich.
The process for creating truly random numbers for gambling kept pace with attempts to find exploitable patterns in the random numbers created for gambling. Huge sums of money were at stake.
By ‘primitive’, are you referring to a specific procedure?
I don’t know if those intercepted messages are published, but if they are, since you do have access to electronic computers it would only take you a few moments to analyse the data statistically for randomness (make sure you strip headers and similar and are just feeding in the stream of supposedly-random digits). The SIS did.
A simple example of this:
To generate random bits, flip a coin twice. If it comes up HT, output 0. If TH, output 1. Otherwise try again.
It doesn’t matter if the coin is biased as long as it’s independent flip to flip, since P(HT)=P(H)P(T)=P(TH). The technique is ruined if you try to save time by using two coins.
You can still save time by using multiple coins, as long as you use the different coins for different bits. For instance, you could generate a penny bitstream in parallel with a nickel bitstream, a dime bitstream, and a quarter bitstream.