From: "Arthur J. O'Dwyer"
Subject: Re: the FBI and 1 time pads
Date: Wed, 27 Aug 2003 16:12:40 -0400 (EDT)
Organization: Carnegie Mellon, Pittsburgh, PA
References: <email@example.com> <3F4C55C1.114C@despam.autobahn.mb.ca>
NNTP-Posting-Date: 27 Aug 2003 20:12:40 GMT
On Wed, 27 Aug 2003, Alex Flanagan wrote:
> > Quality of the keys may also a problem - they must be _truly_
> > random. You've heard of nice programs which produce "random"
> > numbers? Randomness is a lot more difficult subject than one
> > might think.
> The short story is: computers cannot produce random numbers. One time pads
> require (OTPs) complete randomness in order to be as strong as they can be,
> and because computers can't give us perfect randomness, encryption done by
> them won't be as strong as a good OTP.
> The long story follows:
> Computers fake random numbers by doing things like measuring the time
> between keystrokes and the time between when packets of information reach
> your computer from the internet and then applying statistics to these
> numbers to make sure they are used in a random-looking way. This isn't just
> a splitting hairs, patterns in pseudorandom numbers (as they are called) are
> detectable. These patterns (call them "trails") can then be "followed back"
> to the plaintext (assuming you used a computer to generate your OTP).
> True OTPs are (as far as I know) the strongest kind of encryption.
Yep. A one-time pad, properly applied, is completely unbreakable, from
the mathematical point of view. Reason: suppose I have the crypto-text
Using the one-time-pad key LFNPDDV, we get the plaintext
-- but if the key was really BYAQOZC, then the plaintext becomes
Since we (the "enemy") don't have any idea what the key is, there's
no way for us to know which of these messages was meant -- or which
of the other eight billion possible alphabetic strings it might have
> There is
> no pattern to the randomness (no "trail" to follow back to the plain text of
> your message). And yes, with the security come usability problems. If you
> use a pad twice it is compromized. A good codebreaker given two messages
> encoded with the same pad will be able to find the contents of both messages
> and the pad (the Soviets made this mistake a few times).
> Organizations using OTPs deal with this is by having lots of pads. In World
> War II, for example, they apparently had rooms full of clerks drawing
> numbers from hats, from bingo machines, from any source of random numbers
> that had no pattern (or, to be precise, a pattern so complex that no one
> could predict it) and writing those numbers down to make one time pads.
Neal Stephenson's _Cryptonomicon_ contains a brief anecdote somewhere
about how the Allies ended up having to change around their codes sometime
in the middle of WWII just because some little old lady got lazy picking
her bingo numbers. See, the Bletchley Park people had hired a lot of
women to pick letters out of bingo tumblers for their one-time pads,
and this woman eventually, subconsciously, realized that the letters she
was drawing "weren't random enough" -- you know, sometimes she'd get two
E's in a row, or three T's, and we all know that really *random* letter
arrangements won't repeat that often, and will contain a lot of Q's and
X's (because it's not just plain English; it's random!). So she must
have started putting a ball or two back into the machine every so often,
and of course that didn't make the pads more random -- it made them *less*
random. The Germans eventually managed to exploit this irregularity, and
broke one of the British pads. And then some other stuff happened.
Anyway, moral of the story was: Don't mess with randomness.