lauren@vortex.UUCP (Lauren Weinstein) (01/30/84)
In cases of very important military or diplomatic communications, I believe that the coding technique of choice is still the time-honored "one-time" code. This technique involves pre-sending to your destination (by trusted means, such as inside a diplomatic pouch) a long "sequence" of data to be used for encryption and/or decryption purposes. Essentially, the concept is simple. For each byte you wish to encode/decode, you perform some function based on that byte and the NEXT byte in the coding "sequence". You never use the same sequence data byte twice, and the coding sequence itself (magnetic tape, ROM, or whatever) is also never used again. The coding sequence itself would normally be as random as possible (for example, based on the "noise" generated by the decay of a radioactive particle). In the old days, the coding sequence was sent on paper, thusly the term "one-time pad." Today, such data would usually be sent on magnetic tape, on ROMs within calculator-like encoding/decoding devices, or by similar means. Of course, old-style pads are still a possibility in some cases. One-time codes are generally considered to be essentially impossible to crack, since there is no "key" nor pattern to uncover. They are generally reserved for important communications, since they involve considerable logistic problems, including maintaining the sync between the encoding/decoding sides of the communication using the sequence data, and the hassles of delivering the sequence data to the destination party in the first place. --Lauren--
chongo@nsc.UUCP (Landon Noll) (02/09/84)
one time pads are a good idea. but the the reasons below, they are not the answer to all needs. just for the record, i will point out the problems with such pads: 1) they are not public-key. one time pads are only as secure as the distribution of the pads. when you have to broadcast a message to many sites, the problem gets worse. anyone who gets one of the one-time pads (which becomes even more likely when you have a large distribution) will ruin the security for that pad. people who defect to the "other side" (whatever that means) can carry off such pads... 2) one time pads are very unforgiving on missing data the loss of a section of encrypted data will result in you getting off sync on your pad. just think of would happen if you had to use such a system over uucp? :-) you can use sync marks to help reduce loss of information, but such sync marks are "give-away information" for code crackers too. 3) when you need a large one-time pad, you almost have to resort to a generation system of some kind. say you want a 1,000,000 unit pad. how do you generate such data? if you use random number generators of some kind, and the method of generation or even the style of generation gets known the pad security is greatly reduced. you can overcome this problem by using static noise, or cosmic ray counts, but that is still not totally secure. 4) when you need to transmit a large amount of data, you must use a large one-time key pad, distribute many pads, or reuse the same pad. one time pads are best if they are short length, and short lived. the longer used, or worse more often used, the less secure they become. one time pads are useful, but not everywhere. to put it another way, if one time pads were the answer to everything and 100% secure, then why are there people spending time, energy, and money in the field of cryptosystems? chongo <0110 1010 1001 0001> /\00/\
fair@dual.UUCP (Erik E. Fair) (02/09/84)
With regard to one-time encryption systems: The logistical problems
Lauren cited are no longer relevant. I am writing this as a founding
member of Cryptex, a new company in the cryptosystems business.
We are soon to release a system called CS-3, which is basically
a one-time cipher. CS-3 solves most of the problems previously associated
with one-time ciphers. The only remaining issue concerns key distribution;
CS-3 still requires that key material be distributed via a known-secure
channel such as hand courier. However, you will find this problem exists
with every other system except public key systems and those just became
obsolete anyway. The Merkle-Hellman trapdoor knapsack was defeated
by Rivest et. al., and their system (RSA) was defeated by a new advance
in mathematics by a Mr. Arnold in England, who discovered a new way to
factor huge prime numbers extremely rapidly. Systems other than public
key require key information to be pre-distributed, usually in the form
of "codebooks" containing key seed numbers. So nothing really changed after
all.
In any case, persons interested in finding out more about CS-3, or in
talking about topics of general interest in cryptology, are invited to
contact us. Cryptex, 1442-A Walnut St., #151,; Berkeley, CA, 94709.
George Gleason
c/o
Erik E. Fair
dual!fair@BERKELEY.ARPA
{ucbvax,ihnp4,cbosgd,amd70,zehntel,fortune,unisoft,onyx,its}!dual!fair
Dual Systems Corporation, Berkeley, California
[I will forward Email replies to this article to George - EEF]andrew@orca.UUCP (Andrew Klossner) (02/11/84)
I'm not a cryptologist, but some recent comments as to why a one-time
pad are bad left me less than convinced.
"1) they are not public-key.
one time pads are only as secure as the distribution of the
pads. when you have to broadcast a message to many sites, the
problem gets worse. anyone who gets one of the one-time pads
(which becomes even more likely when you have a large
distribution) will ruin the security for that pad. people who
defect to the "other side" (whatever that means) can carry off
such pads..."
With public key you "broadcast" by sending the message serially, once
for each recipient's key. You can do the same with one-time pad, once
for each recipient's pad.
"2) one time pads are very unforgiving on missing data
the loss of a section of encrypted data will result in you
getting off sync on your pad. just think of would happen if
you had to use such a system over uucp? :-) you can use sync
marks to help reduce loss of information, but such sync marks
are "give-away information" for code crackers too."
So you precede each word of encrypted information with its ordinal
number. A cracker who receives the entire broadcast gains no
additional information, unless (s)he's unfamiliar with the set of
natural numbers :-)
"3) when you need a large one-time pad, you almost have to
resort to a generation system of some kind.
say you want a 1,000,000 unit pad. how do you generate such
data? if you use random number generators of some kind, and
the method of generation or even the style of generation gets
known the pad security is greatly reduced. you can overcome
this problem by using static noise, or cosmic ray counts, but
that is still not totally secure."
Agreed that you can't use a deterministic (programmable) random number
generator. But what's wrong with a static noise count? Why is it
"still not totally secure?" Herein would lie the crux of the argument.
"4) when you need to transmit a large amount of data, you must
use a large one-time key pad, distribute many pads, or
reuse the same pad.
one time pads are best if they are short length, and short
lived. the longer used, or worse more often used, the less
secure they become."
Agreed that you don't use the pad more than once, and that trusted
delivery of many one time pads is a problem, but what's the problem
with a big pad? Noise doesn't become more intelligible in greater
quantity.
Would someone tell me what's *really* wrong with this scheme? I can't
get comfortable with public-key; "uncomputable" doesn't mean anything
if the cracker has enough time and resources.
-- Andrew Klossner (decvax!tektronix!orca!andrew) [UUCP]
(orca!andrew.tektronix@rand-relay) [ARPA]zzz@mit-eddie.UUCP (Mike Konopik) (02/12/84)
What's this nonsense about public key systems being obsolete? I heard about that group in New Mexico that used this Cray to factor some 70 or so digit number in less than a day. So? It seems I also heard that they were lucky and that one of the factors was much smaller than would be expected. Even so, "fast" factoring of numbers this size hardly endangers the 150-200 digit PAIRS of primes used to generate keys that Rivest suggests for security. These would produce 300-400 digit keys that are still a long way from being threatened by existing factoring schemes. Black is White War is Peace RSA is Obsolete P = NP . . . -- -Mike genrad!mit-eddie!zzz (UUCP) ZZZ%MIT-OZ@MIT-MC (ARPA)
outer@utcsrgv.UUCP (Richard Outerbridge) (02/14/84)
What is wrong with one-time pads? Two things, expense and applicability. The
one-time system requires as much key as message; and the key must be
distributed with perfect security. The one-time system is a 'stream' cipher,
which restricts its usefulness for protecting static data.
If you have a network of N stations, all of which may talk to each other, you
require (N-1)**2 one-time pads (or one pad split into that many sections, or a
protocol that takes care of 'crossing off' used sections). Each pad has to be
big enough to handle all the data transmitted on that link. Anyway, it will be
seen that this is only a practical objection; mass storage is becoming cheaper,
and networking sophistication greater.
On the other hand, consider the protection of on-line data rather than data
transmission. To use a one-time scheme doubles the storage requirements.
You can't do partial updates without reenciphering with a new one-time key.
Random access becomes harder because you have to match key with cipher text.
Of course, you have to protect the on-line "one-time" key from inspection.
Then there are problems of undetected data modification (because of known
plaintext). Still, it may be that these too are only practical problems.
The use of one-time systems is becoming more and more feasible, if no less
problematic, but the allure of other cryptosystems is still economic: if you
need 1 unit of key for every unit of plaintext, you end up transmitting (or
"distributing") as much information over discrete ("outside") channels as you
do over the insecure channels. Obviously the timeliness of the insecure
communication provides the economic justification for the scheme, but you can
see that taken to an extreme perfect security is at best ludicrous. Hence
the interest in "practically" or computationally secure cryptography. In
effect this means schemes that have a lifespan of as few as ten years. Whether
this makes much more sense is an open question. The hope is to find one (for
example, RSA) whose useful life is likely to be several decades.
Richard Outerbridge outer@utcsrgv UofToronto CSRG