randy@uw-june.UUCP (02/11/88)
I'd like to know what a one time pad is. Having read my share of
spy novels and this news group, I've heard of the method many times,
but I don't really know the mechanics or theory behind it.
All I really know is that you this some sort of ordering on the
pad to encrypt your message. Could someone fill me in?
Thanks,
Randy Day.
Internet (ARPA): randy@cs.washington.edu
CSNET: randy%washington@relay.cs.net
UUCP: {decvax|ihnp4}!uw-beaver!uw-june!randygwyn@brl-smoke.ARPA (Doug Gwyn ) (02/12/88)
In article <4209@june.cs.washington.edu> randy@june.cs.washington.edu (William Randy Day) writes: >I'd like to know what a one time pad is. This is described in David Kahn's "The Codebreakers", which is "must" reading (find the hardback, which was a best seller, rather than the abridged paperback, which omitted a lot of interesting technical stuff, presumably on the theory that the American reading public is stupid). The general idea is that encryption is performed using a truly random key stream, which both parties have a copy of, and as the key stream is used, it is destroyed (as opposed to eventually being re-used). There are several variations on this theme, but this is the essence. The "one-time pad" method gets its name from the small pads containing keys that spies (particularly Soviet agents) would use. As a sheet was used, it was torn off and destroyed (presumably by burning).
henry@utzoo.uucp (Henry Spencer) (02/15/88)
"One-time pad" is the generic term for cryptosystems in which the encryption
key is the same length as the message, consists of random bits, and is not
generated in any systematic way or re-used later. The pencil-and-paper
version uses a pad of paper preprinted with random numbers; when you have
used all of the numbers on the top sheet, you tear it off and destroy it.
Hence the name.
The advantage is that it is inherently unbreakable: there is (provably) not
enough information in the transmitted message to permit cryptanalysis. The
disadvantage is that you need a volume of key text equal in size to the
volume of message text -- any attempt at re-use, systematic generation of
key text from smaller keys, derivation of keys from non-random sources (e.g.
the text of a book), etc., destroys the inherent unbreakability.
(One can view cryptosystem design as the art of devising algorithms that
generate masses of very-random-looking key text from small input keys, and
cryptanalysis as the art of finding and exploiting the subtle non-random
patterns that the algorithms leave.)
One-time systems are routinely used for diplomatic communications, where
diplomatic pouches can be used to ship key-text tapes around. Use for
other purposes usually runs into practical difficulties. As I recall, the
Soviets are fond of using one-time pads for spy communications, although
this is a double-edged sword: the messages cannot be decrypted but the
substantial pads of random numbers pose concealment problems.
--
Those who do not understand Unix are | Henry Spencer @ U of Toronto Zoology
condemned to reinvent it, poorly. | {allegra,ihnp4,decvax,utai}!utzoo!henrygwyn@brl-smoke.ARPA (Doug Gwyn ) (02/18/88)
In article <1988Feb15.151522.5094@utzoo.uucp> henry@utzoo.uucp (Henry Spencer) writes: >this is a double-edged sword: the messages cannot be decrypted but the >substantial pads of random numbers pose concealment problems. Yes, possession of such a pad would be considered evidence of ill intent. Keys that can be carried in one's head (or looked up in commonly available books) have a practical advantage here, although they are not absolutely secure.
henry@utzoo.uucp (Henry Spencer) (02/19/88)
> Keys that can be carried in one's head (or looked up in commonly available > books) have a practical advantage here, although they are not absolutely > secure. A tip for the aspiring spies :-) in the audience: Using the text of a book as the key isn't very secure, because a key which is English text shows strong patterns (although using a book written in some obscure language might help...). An easy way to make life much harder for the cryptanalysts is to use a book of *numbers*, say trade statistics or something like that. Those numbers will show patterns, but they'll be obscure and they won't be the ones the cryptanalysts are looking for. -- Those who do not understand Unix are | Henry Spencer @ U of Toronto Zoology condemned to reinvent it, poorly. | {allegra,ihnp4,decvax,utai}!utzoo!henry
al@gtx.com (0732) (02/20/88)
It seems to me that potential one-time pads are broadcast every day in
the form of newspapers, magazines, sports scores, lottery numbers,
etc. All you need to do is agree on some algorithm for using them.
You can either xor strings from these sources with your message, or
reseed a random number generator based on the broadcast data and
generate your pad from that. All you need is a source of bits (more
random the better) commonly observable by sender and recipient. Is
broadcast data of this kind often used to help with key distribution?
I don't often hear about this technique, but it seems obvious,
certainly better than toting actual physical pads around.
----------------------------------------------------------------------
| Alan Filipski, GTX Corp, 2501 W. Dunlap, Phoenix, Arizona 85021, USA |
| {ihnp4,cbosgd,decvax,hplabs,amdahl}!sun!sunburn!gtx!al (602)870-1696 |
----------------------------------------------------------------------gnu@hoptoad.uucp (John Gilmore) (02/22/88)
henry@utzoo.uucp (Henry Spencer) writes: > substantial pads of random numbers pose concealment problems. gwyn@brl-smoke.ARPA (Doug Gwyn) wrote: > Yes, possession of such a pad would be considered evidence of ill intent. Why am I not surprised that a government employee would consider possession of pads of random numbers as "evidence of ill intent"? "Circumstancial evidence, your Honor. He clearly wanted privacy, therefore he must be guilty of something." Bah. -- {pyramid,ptsfa,amdahl,sun,ihnp4}!hoptoad!gnu gnu@toad.com "Watch me change my world..." -- Liquid Theatre
gwyn@brl-smoke.ARPA (Doug Gwyn ) (02/22/88)
In article <4104@hoptoad.uucp> gnu@hoptoad.uucp (John Gilmore) writes: >henry@utzoo.uucp (Henry Spencer) writes: >> substantial pads of random numbers pose concealment problems. >gwyn@brl-smoke.ARPA (Doug Gwyn) wrote: >> Yes, possession of such a pad would be considered evidence of ill intent. >Why am I not surprised that a government employee would consider possession of >pads of random numbers as "evidence of ill intent"? We were talking about suspected spies. Yes, it would be circumstantial evidence, but combined with other evidence it might be decisive. I don't know why you think I'm a "government toady" -- do you have evidence of that?
jojo@astroatc.UUCP (Jon Wesener) (02/23/88)
How about using the message itself, in some form or another,
as the pad. For example:
ABCDEFGHIJ klmnopqrst
?ABCDEFGHI ?ABCDEFGHI
---------- ----------
klmnopqrst ABCDEFGHIJ
The 1st lines the message, the second line is your pad. You give the
pads 1st character as the key. To decrypt it, you provide the first
character and then use what you've decrypted as the rest of the pad.
This is just an example, I'm sure some better way to do it could be
found.
comments?
--j
--
jon wesener
... {seismo | harvard | ihnp4} ! {uwvax | cs.wisc.edu} ! astroatc!jojo
"Watch who you're calling space garbage meteor mouth..."henry@utzoo.uucp (Henry Spencer) (02/24/88)
> It seems to me that potential one-time pads are broadcast every day in > the form of newspapers, magazines, sports scores, lottery numbers, > etc. All you need to do is agree on some algorithm for using them. > You can either xor strings from these sources with your message, or > reseed a random number generator based on the broadcast data... The trouble is that the bit stream you get from these sources is not *random*, and a random-number generator seeded from them isn't either. You don't get the unbreakability of the one-time pad unless your key stream is completely random, with no pattern whatsoever. Making it English text, from whatever source, is about as useful as just sending your message "in clear"; methods for cryptanalyzing that sort of thing are old hat. Seeding a garden-variety "random"-number generator is just as bad. -- Those who do not understand Unix are | Henry Spencer @ U of Toronto Zoology condemned to reinvent it, poorly. | {allegra,ihnp4,decvax,utai}!utzoo!henry
jk3k+@andrew.cmu.edu (Joseph G. Keane) (02/24/88)
> How about using the message itself, in some form or another, > as the pad. > comments? Not very secure: all you have to do is guess the first character! Even if you have a reasonably large key (offset), a known-plaintext attack will get some information, and it propagates forward and backward. --Joe
gwyn@brl-smoke.ARPA (Doug Gwyn ) (02/24/88)
In article <858@astroatc.UUCP> jojo@astroatc.UUCP (Jon Wesener) writes: >How about using the message itself, in some form or another, as the pad. ... You've made the entire message security depend on just one key character; trial and error will discover this in almost no time.
ecp@mitre-bedford.ARPA (Eric C. Pivnik) (02/24/88)
In article <858@astroatc.UUCP> jojo@astroatc.UUCP (Jon Wesener) writes: > > How about using the message itself, in some form or another, >as the pad. For example: > > ABCDEFGHIJ klmnopqrst > ?ABCDEFGHI ?ABCDEFGHI > ---------- ---------- > klmnopqrst ABCDEFGHIJ > >The 1st lines the message, the second line is your pad. You give the >pads 1st character as the key. To decrypt it, you provide the first >character and then use what you've decrypted as the rest of the pad. ... >jon wesener The definition and the entire security of the one-time pad is that the KEY is random. Having the key be obscure, statistically random, pseudorandom, or random enough, is not a one-time pad. What you have described is close to a running key cypher known as auto-key. In an auto-key, the nth element of the key is formed from the encryption of the (n-1)th plaintext and (n-1)th key element. There would be a preagreed upon initial key element. Running key cyphers do not provide much security by themselves even if you do not compare them to a one-time pad. See David Kahn's _The Codebreakers_ for historical information. See Friedman's _Riverbank Publication #16_ (published in 1918) for general solutions of running key cyphers. ecp@mitre-bedford Eric C. Pivnik
frank@zen.UUCP (Frank Wales) (02/25/88)
In article <1988Feb19.150017.454@utzoo.uucp> henry@utzoo.uucp (Henry Spencer) writes: >A tip for the aspiring spies :-) in the audience: > >Using the text of a book as the key isn't very secure, because a key which >is English text shows strong patterns (although using a book written in >some obscure language might help...). Try a phone book; I haven't found one I could understand the story in yet. :-) Frank Wales, [frank@zen.uucp<->mcvax!zen.co.uk!frank] Zengrange Ltd., Greenfield Rd., Leeds, ENGLAND, LS9 8DB. (+44) 532 489048 x220
amlovell@phoenix.Princeton.EDU (Anthony M Lovell) (02/27/88)
In article <cW8SR0y00XoCREk38I@andrew.cmu.edu>, jk3k+@andrew.cmu.edu (Joseph G. Keane) writes: > > > How about using the message itself, in some form or another, > > as the pad. > > comments? > > Not very secure: all you have to do is guess the first character! Even if you > have a reasonably large key (offset), a known-plaintext attack will get some > information, and it propagates forward and backward. > > --Joe As long as your method of devising a key from the plaintext is arbitrary (and remains unknown to the cracker) , he will not get his foot in the door. What if the n+5th message is the key (again adulterated in some form) for the nth message? Any scheme like this will be impregnable until guessed, and its patterns are certainly unlike those typically searched for. The arbitrary system can be changed in encrypted transmissions (with the acknowledged risk that it will not help IF the cipher is already compromised). This denies the "enemy" a large body of ciphertext to examine for these weak patterns. Not by any means the most secure or practical system (more secure than practical in my mind), but I would put my money on the cleartext remaining undiscovered for a LONG LONG time. -- amlovell@phoenix.princeton.edu
mlm@NL.CS.CMU.EDU (Michael Mauldin) (02/27/88)
In article <1857@phoenix.Princeton.EDU>, amlovell@phoenix.Princeton.EDU (Anthony M Lovell) writes: > What if the n+5th message is the key (again adulterated in some > form) for the nth message? Any scheme like this will be impregnable > until guessed, and its patterns are certainly unlike those typically > searched for. When using English text as the "key" in a stream cipher, the patterns in English show through into the ciphertext. For example, when the word 'the' is encrypted against the word 'the', you get repeated occurrences of a three letter word. Denning82 (Cryptography and Data Security) discuesses ways to crack these kinds of systems. "Impregnable until guessed" reminds me of a quote from my old DiffyQ text in college: "Bacteria are virtually indestructable unless killed" Aren't we all. Michael L. Mauldin (Fuzzy) Department of Computer Science ARPA: Michael.Mauldin@NL.CS.CMU.EDU Carnegie-Mellon University Phone: (412) 268-3065 Pittsburgh, PA 15213-3890
travis@madonna (Travis Lee Winfrey) (02/27/88)
In article <1988Feb23.165949.4602@utzoo.uucp> henry@utzoo.uucp (Henry Spencer) writes: >>[lost this reference]: >> It seems to me that potential one-time pads are broadcast every day in >> the form of newspapers, magazines, sports scores, lottery numbers, >> etc. > >The trouble is that the bit stream you get from these sources is not >*random*, and a random-number generator seeded from them isn't either. >You don't get the unbreakability of the one-time pad unless your key >stream is completely random, with no pattern whatsoever. Making it >English text, from whatever source, is about as useful as just sending >your message "in clear"; methods for cryptanalyzing that sort of thing >are old hat. Seeding a garden-variety "random"-number generator is just >as bad. Well, you're talking only about English sources. That's obvious; what about the rest of his suggestions? If the algorithm for computing lottery numbers is not random, then some of us are missing out on making a lot of money, no? The S book had a cute series of examples analyzing some lottery numbers. The tables are pretty short, though. Sports scores show patterns, obviously, but what about subsets of the statistics or league positions? Do phone numbers show patterns, ignoring the three digit prefix? t Arpa: travis@cunixc.columbia.edu Bitnet: travis@cu20b Usenet: rutgers!columbia!travis USMail: 483 Mudd, Columbia Univ., NYC 10025 Phone: 212-280-8091
henry@utzoo.uucp (Henry Spencer) (02/28/88)
> ... What if the n+5th message is the key (again adulterated in some > form) for the nth message? ... Chaining schemes like this require perfect transmission. Real cryptosystems have to be robust in the presence of garbles in messages or even missing messages; such things do happen. All such "autokey" systems have a major weakness for serious use: even a hint as to what's going on destroys security. The standard rule of thumb for cryptosystem design is that it simply isn't possible to keep an enemy totally ignorant of the general nature of the cryptosystem. (In fact, the standard rule is stronger than that: one should assume that the enemy knows *everything* about your cryptosystem that isn't changed frequently, i.e. he knows everything except what today's encryption key is.) -- Those who do not understand Unix are | Henry Spencer @ U of Toronto Zoology condemned to reinvent it, poorly. | {allegra,ihnp4,decvax,utai}!utzoo!henry
leonard@bucket.UUCP (Leonard Erickson) (02/28/88)
In article <575@gtx.com> al@gtx.UUCP (Al Filipski) writes:
<It seems to me that potential one-time pads are broadcast every day in
<the form of newspapers, magazines, sports scores, lottery numbers,
<.... All you need to do is agree on some algorithm for using them.
<generate your pad from that. All you need is a source of bits (more
<random the better) commonly observable by sender and recipient. Is
<broadcast data of this kind often used to help with key distribution?
One major pitfall here is that different areas receive different editions
of newspapers and magazines.
What has just occurred to *me* is to wonder what would happen if you decided
to use the infamous "numbers stations" on SW as the key?
--
Leonard Erickson ...!tektronix!reed!percival!bucket!leonard
CIS: [70465,203]
"I used to be a hacker. Now I'm a 'microcomputer specialist'.
You know... I'd rather be a hacker."todd@uop.edu (Dr. Nethack) (03/03/88)
In article <790@bucket.UUCP>, leonard@bucket.UUCP (Leonard Erickson) writes: > One major pitfall here is that different areas receive different editions > of newspapers and magazines. > > to use the infamous "numbers stations" on SW as the key? Er.. which one?? :-)
al@gtx.com (0732) (03/03/88)
In article <1988Feb23.165949.4602@utzoo.uucp> henry@utzoo.uucp (Henry Spencer) writes: >> It seems to me that potential one-time pads are broadcast every day in >> the form of newspapers, magazines, sports scores, lottery numbers, >> etc. > >The trouble is that the bit stream you get from these sources is not >*random*, and a random-number generator seeded from them isn't either. >You don't get the unbreakability of the one-time pad unless your key >stream is completely random, with no pattern whatsoever. Making it >English text, from whatever source, is about as useful as just sending >your message "in clear"; methods for cryptanalyzing that sort of thing >are old hat. Seeding a garden-variety "random"-number generator is just >as bad. It seems that the "randomness" in English text could be "extracted" by a suitable compression. I think Shannon estimated that there is about 1 bit of information in each character of typical English text (i.e. with full knowledge of context, you could guess the next character correctly about 50% of the time). Although English text makes a very poor random stream, a compression of this text based on some high-order statistics of English should be much better. Besides ordinary invertible compression, there should be other ways to increase the randomness of a stream at the expense of length, via hash-code-like transformations. Any specific ideas as to how to do this? (Discussions like this would be a lot more meaningful if there were a simple, agreed-upon definition for the "Randomness" of a finite sequence.) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ( Alan Filipski, GTX Corp, 8836 N. 23rd Avenue, Phoenix, Arizona 85021, USA ) ( {ihnp4,cbosgd,decvax,hplabs,amdahl,nsc}!sun!sunburn!gtx!al (602)870-1696 ) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
martin@entropy.ms.washington.edu (Don Martin) (03/04/88)
There has been some discussion of the nonrandom nature of
english text in the context of one time pads. Two remarks:
1. A Beale cipher takes advantage of the key and the message
having similar frequency distributions. This cipher appears
to be quite safe if the key is as long or longer than the
message.
2. I did some expermentation with cryptographic hash functions
a while back. As a test, I hashed the unix spelling dictionary
which is about 26000 words into 3 decimal digit numbers and used
a chi-square test on the resulting frequencies. I did not test
for serial correlation type structures. It took more tinkering
with the hash function than I expected to get a good frequency
distribution. However, I was convinced that a hash function that
looked random to the usual statistical tests was possible and
that the function could be designed so that it was difficult to
find a partial inverse.
This type of hash function is handy both as a hash function
for the usual cryptographic uses, such as signatures, and as a
good way of seeding random number generators. However, you must
use many more input characters than the function puts out to avoid
hidden redundencies.
Don Martin