🚀 go-pugleaf

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).

"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!henry

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.

> 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

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 |
    ----------------------------------------------------------------------

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

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?

	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..."

> 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

> 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

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.

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

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 

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

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

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

> ... 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

In article <1857@phoenix.Princeton.EDU> amlovell@phoenix.Princeton.EDU (Anthony M Lovell) writes:
>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.

First, the system originally described was indeed a simple auto-key
system that any competent cryptanalyst could quickly break.

Second, in your changed scenario, the whole system collapses if any
of the message traffic is not received.  In practice, for important
cryptosystems (as opposed to toys amateurs play with), you have to
count on the general system being "somehow" known to the opposition.
You also need to include sufficient indicators in the transmitted
text to allow the receiving station to select the right decryption
key without fumbling around.  Of course these indicators will also
be visible to the opposition's cryptanalysts.

>  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.

If there were any reason for competent cryptanalysts to concentrate
effort on your system, you'd lose your money (not to mention your
secrets).

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."

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??

:-)

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 )
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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