One Time Pad (was: Re: [rc5] The DOS client appears at last!)
rfreeman at netaxs.com
Mon Oct 27 11:15:07 EST 1997
On Mon, 27 Oct 1997, Chris Grantham wrote:
> Hmm. Never (No.. ever) is a strong word, and one that is frequently over
> used. Maybe you could explain to the laymen (such as myself) on the
> group what OTP is, and why it is completely secure (and maybe why we
> aren't all using it for encryption ;-> ).
In short - the OTP is simply the use of an encryption key longer than the
message itself... Since the key is not repeated througout the message,
the knowledge of any portion of hte key cannot be leveraged to obtain
addional information about the message. In our brute-force strategy, we
know half of the message's plaintext ("The secret message is:" or
something like that). We simply find keys that convert that plaintext to
the known ciphertext. Then when we find that key, we use it to decrypt
the rest of the plaintest (since the key is shorter than the known portion
of the plaintext, it repeats and knowing only a portion of the plaintext
is sufficient to get enough key to decode the entire thing). The OTP is
immune to this. A proper OTP uses a totally random key (which is one weak
point - this is difficult to truly generate) - which by definition means
that knowing one part of the key gives you no information at all about the
rest of the key. Of course, many implementations are not totally random -
but we are only talking about a true implementation here. The biggest
problem is that the key ends up being at least as large as the message.
In order to decode the message you need the key. So you need a way of
getting this key to somebody else. If you are worried about your email
being read you obviously just can't email it to them. The state
department uses the OTP (from what I hear). They record the keys on
media and keep one copy in the US and distribute one copy to an embassy -
by hand. This way you hopefully know that nobody evesdropped on its
transmission. This can be done in advance at your convenience. Then when
you want to send a message, you use the key - and it cannot be broken.
The problem is that in order to keep the key secure, you can only use it
once (otherwise you are repeating the key, making a statistical attack
difficult, but no longer impossible). So, even the state department
doesn't use it for routine communications (you'd go through a lot of keys
really fast). Of course, since keys are much longer than the messages,
you can always recycle the portion of the key that wasn't used without
penalty, but there is still a limit. Key exchange is always a limit in
most types of cryptography - and the only way for it to be mathamatically
unbreakable this has to occur over a channel which is impossible to
intercept. The OTP is provably unbreakable - provided that:
1. Key is longer than message, and is only used once and not repeated.
2. Key is TRULY random (the Random Nubmer Generator in
BASIC/C++/PGP/Whatever is not).
3. Key is exchaged securely.
I think that I am not missing anything. The best attack against a OTP is
to try to figure out if the key used had patterns in it. Even if there
are patterns, this is a very difficult attack. A true OTP won't even
allow a difficult attack - it is secure in the very meaning of the word...
Even our RC5 bruteforce would be a whole different ballgame if it weren't
for the known portion of the plaintext...
Richard T. Freeman <rfreeman at netaxs.com> - finger for pgp key
3D CB AF BD FF E8 0B 10 4E 09 27 00 8D 27 E1 93
http://www.netaxs.com/~rfreeman - ftp.netaxs.com/people/rfreeman
To unsubscribe, send email to majordomo at llamas.net with 'unsubscribe rc5' in the body.
More information about the rc5