Msg: 7181 *Conference*

05-30-97 21:11:50

From: COMET _

To : JAMES KENNEY

Subj: REPLY TO MSG #7167 (CFRJMK 2.0)

I am interest in cryptography and cryptanalysis.  I have my copy of "Applied
Cryptography, 2nd ed." right here.  :-)
 
Your statement that commercial programs cannot produce "absolutely unbreakable"
ciphertext, but that yours can, is logically inconsistent.
 
As you are doubtless aware, the only "absolutely unbreakable" means of 
encryption is the use of a "one-time pad".  Basically, if the sender and the
recipient have the same list of RANDOMLY-GENERATED bits, then the encoding and
decoding process is trivial--simply use the exclusive OR (XOR) operation on
plaintext and corresponding encryption key (the random bits), and voila!  The
result of XORing the plaintext will be a set of bits that could represent -any-
message of that length, and with equal probability (since the
randomly-generated bits have a uniform distribution and no correlation,
pairwise or otherwise).
 
Since the algorithm is simple, the difficulty, then, is with the acquisition
and distribution of the large amount of randomly-generated bits, which must be
as large as the plaintext.
 
Let's say I looked up a table of random bits, and then wanted to use this for a
commercial encryption program.  Since everybody I sold the program to would
have access to the same table of random bits, this would make the resulting
messages readible by anybody who had a copy of the program.  Hmmm....  I
consider this a bit of a flaw, as I would like to have a message that only
myself and my intended recipient would be able to read.  (Of course, I would
still have the problem of transporting the encryption key through a different
secure channel than the encyrpted message.)
 
So let's say that the encryption program is distributed WITHOUT the random key.
Fine.  Then the problem of getting a random key is up to the user.  This is a
larger problem then one might think, at first blush.  The reason is that the
average user has not a clue as to where to get a large stream of random bits.
In fact, I'd say that the average user would trust his computer's random number
generator, but this would NOT lead to an "absolutely unbreakable" encryption.
 
The reason for this, is because most computers generate random numbers by
software alone.  Shocking, isn't it?  "Seminumerical Algorithms", by Donald
Knuth, goes into the design of these algorithms, which actually  generate
PSEUDOrandom number sequences.  The problem is, of course, that given the same
initial values, the algorithm will always generate the same sequence of
numbers....  Hardly "random"--in fact, mathematically it's absolutely
predictable.  Of course the fact that the sequences are reproducible and random
for several statistical measures is a useful feature, and indeed these types of
sequences are used in several commercially available encryption packages.
 
So where is one to get RANDOM numbers, random for truly unbreakable encryption?
Well, some slightly clever people may try to randomize the initial condition,
using variables such as the quickly changing bits in the built-in real-time
clock, sampling it at intervals dictated by user's keystrokes as time between
two key presses.  The problem here is that even with this amount of true
randomness, you CANNOT extrapolate this to make EVERY BIT of the resulting
generated sequence a random one....  You may think this doesn't matter, but
then, Netscape Navigator's security was broken just because they didn't
introduce enough randomness....  (Since that time they have added significantly
many more inputs, and so the resultant sets of bits produced by their algorithm
is much more widely distributed, but it's still not a uniform random
distribution.)
 
Using the conscious mental powers of the user (please enter a 900 digit
number--this will be used to encrypt your message) may make many users feel
secure, but the inability of humans to generate uniform random sequences has
been well demonstrated by psychologists and stage magicians.
 
So how CAN one get a truly random sequence of bits?  Without it, absolutely
unbreakable encryption is impossible.  Well...  there are hardware devices that
are quantumly uncertain that one can sample to get a random bit.  For example,
let's say that you have a geiger counter and a sample of uranium...  the exact
timing of each bit of decay is not predictable, and this source of randomness
can be used to generate a set of bits that is uniformly distributed.  There ARE
commercial devices that are available that are used for this very purpose.
 
Still, the fact that you have this set of random bits the size of your message
and that you cannot compress this set of bits or lose it once  you've encrypted
your message (for if you did, you would not be able to recover the plaintext)
can cause problems.  This is why the one-time pad is not in wide usage.
 
Still, as the only mathematically unbreakable encryption, it is used for
extremely high security systems, such as the "red phone" between the Oval
Office and Moscow.  [The set of random bits is transported by trusted courier
in advance of the phone call--during the phone call, conversations are
encrypted with the bits, and after the phone call the bits are NEVER re-used.]