Cryptography-Digest Digest #700, Volume #9 Sat, 12 Jun 99 06:13:04 EDT
Contents:
Re: DES lifetime (was: being burnt by the NSA) ("Douglas A. Gwyn")
Re: KRYPTOS ("Douglas A. Gwyn")
Re: KRYPTOS ("Douglas A. Gwyn")
Question from a neophyte (Donald Clark)
Re: DES lifetime (was: being burnt by the NSA) (SCOTT19U.ZIP_GUY)
Re: KRYPTOS (Jim Gillogly)
Re: DES lifetime (was: being burnt by the NSA) (Jerry Coffin)
Re: cant have your cake and eat it too (Jerry Coffin)
Re: Cracking DES (Jerry Coffin)
Re: Random numbers on a sphere ([EMAIL PROTECTED])
Re: One Time Pad ([EMAIL PROTECTED])
Re: Question from a neophyte ([EMAIL PROTECTED])
Re: Cracking DES (David Wagner)
Re: cant have your cake and eat it too ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: DES lifetime (was: being burnt by the NSA)
Date: Sat, 12 Jun 1999 02:41:04 GMT
John Savard wrote:
> When DES was first accepted as a standard, it was recommended for
> certain uses, among them "sensitive but unclassified" government data.
> And, as you point out, that includes census data, and it is correct
> that census data from the year DES was adopted is still confidential
> today, and it is correct that DES is breakable today.
If *any* cryptosystem, rather than physical security, was used as the
sole means to protect the census data, then it was unconscionable.
Even the military cryptosystems have a design lifetime of only 50
years, partly because extrapolating cryptanalytic technology farther
than that becomes pure guesswork.
> Of course, I don't think it's reasonable to say that DES resulted from
> the combined efforts of IBM, NBS, and the NSA: that implies that all
> three were pulling in the same direction. IBM certainly was not
> incapable of considering a 128-bit key, as LUCIFER proved.
I guess you aren't familiar with the actual history of the development
of DES. Certainly, it was the result of a collaborative effort among
those three organizations, even more than has been published.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: KRYPTOS
Date: Sat, 12 Jun 1999 03:25:11 GMT
Jim Gillogly wrote:
> I solved the transposition section last night.
Drat! Inspired to action by Jim's previous successes, I was just
about to try a quick attack on that section, on the assumption that
it was double transposition and that the keys were KRYPTOS/KRYPTOS,
VIRTUALLY/INVISIBLE, SHADOW/FORCES, or LUCID/MEMORY.
> There're still those last few lines waiting to be decrypted.
In case anyone wants to make a stab at it:
OBKR
UOXOGHULBSOLIFBBWFLRVQQPRNGKSSO
TWTQSJQSSEKZZWATJKLUDIAWINFBNYP
VTTMZFPKWGDKZXTJCDIGKUHUAUEKCAR
This might be intractable, if the CIA Public Affairs office's help
note is right in classifying it as a true one-time-pad system.
However, if they misclassified any of the other sections (something
that Jim is now in a position to assess), it would cast doubt on
their ability to make a correct diagnosis. Their classifications:
(1) Digraphic substitution.
(2) (3) (4) Polyalphabetic, 4 or 8 alphabets.
(5) Transposition, width 11 or 13.
(6) One-time, or perhaps Vigenere based on KRYPTOS tableau.
Jim deserves high praise for almost (so far) totally cracking
KRYPTOS in just a few days. I guess we need to find another
unsolved puzzle. How about Zodiac #2?
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: KRYPTOS
Date: Sat, 12 Jun 1999 03:28:57 GMT
Medical Electronics Lab wrote:
>...you'll get a whole lot more people interested now in looking at it.
I think motivation is important. So long as people were thinking that
Kryptos was intractable, they didn't put in the work that it actually
takes to crack the systems. I'm happy to have played some role in
spurring Jim to tackle it.
------------------------------
Subject: Question from a neophyte
From: Donald Clark <[EMAIL PROTECTED]>
Date: Sat, 12 Jun 1999 04:25:54 GMT
Anyone,
First of all i would like to conradulate
this <ng> on it's mutual respect for it's
members. Very refreshing!
I have been a lurker here for several months now.
I landed here as a direct result of another
<ng> that i belong to going PGP. I know very
little about *crypto*; save a couple of simple
decrypts in last semesters phyics class.
I have, or rather am developing a keen
interest in the discipline. However, I need
some direction. I would greatly appreciate
anyones opinions as to what books would be
appropriate for the novice.
Please feel free to e-mail.
Thank You
Don Clark
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: DES lifetime (was: being burnt by the NSA)
Date: Sat, 12 Jun 1999 05:08:23 GMT
In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
>John Savard wrote:
>> When DES was first accepted as a standard, it was recommended for
>> certain uses, among them "sensitive but unclassified" government data.
>> And, as you point out, that includes census data, and it is correct
>> that census data from the year DES was adopted is still confidential
>> today, and it is correct that DES is breakable today.
>
>If *any* cryptosystem, rather than physical security, was used as the
>sole means to protect the census data, then it was unconscionable.
>Even the military cryptosystems have a design lifetime of only 50
>years, partly because extrapolating cryptanalytic technology farther
>than that becomes pure guesswork.
>
>> Of course, I don't think it's reasonable to say that DES resulted from
>> the combined efforts of IBM, NBS, and the NSA: that implies that all
>> three were pulling in the same direction. IBM certainly was not
>> incapable of considering a 128-bit key, as LUCIFER proved.
>
>I guess you aren't familiar with the actual history of the development
>of DES. Certainly, it was the result of a collaborative effort among
>those three organizations, even more than has been published.
Actaully he may be more familiar with history than you since he has
been around longer. You may have been more exposed to the NSA's
version of history.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: KRYPTOS
Date: Fri, 11 Jun 1999 23:32:46 -0700
Douglas A. Gwyn wrote:
> In case anyone wants to make a stab at it:
>
> OBKR
> UOXOGHULBSOLIFBBWFLRVQQPRNGKSSO
> TWTQSJQSSEKZZWATJKLUDIAWINFBNYP
> VTTMZFPKWGDKZXTJCDIGKUHUAUEKCAR
>
> This might be intractable, if the CIA Public Affairs office's help
> note is right in classifying it as a true one-time-pad system.
> However, if they misclassified any of the other sections (something
> that Jim is now in a position to assess), it would cast doubt on
> their ability to make a correct diagnosis. Their classifications:
> (1) Digraphic substitution.
> (2) (3) (4) Polyalphabetic, 4 or 8 alphabets.
> (5) Transposition, width 11 or 13.
> (6) One-time, or perhaps Vigenere based on KRYPTOS tableau.
There is polyalphabeticity going on, but no digraphic substitution.
Their transposition periods are a clear miss. Their main wrong
guess is that question marks separate the sections; in fact, each
question mark is textual. The fact that much of it was mis-diagnosed
leads me to be hopeful about the last bit. I don't see any
regularities other than a probably-spurious Phillips-like distribution,
if you ignore the presence of both I and J. This could mean a number
of things other than a OTP: perhaps running key with a coherent
keytext and perhaps mixed alphabet, or an autokey, or perhaps a
combination polyalphabetic and transposition. Lots of challenging
possibilities.
I'll work on the last section for a little longer before I expose
the rest -- I'd like to dump the whole bag at once if possible.
--
Jim Gillogly
Hevensday, 22 Forelithe S.R. 1999, 06:18
12.19.6.4.17, 1 Caban 5 Zotz, Seventh Lord of Night
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: DES lifetime (was: being burnt by the NSA)
Date: Sat, 12 Jun 1999 00:44:50 -0600
In article <7jqubp$e0g$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
[ ... ]
> As I understand it "sensitive but not classified" information
> would include raw data from the decennial census, and the law
> states such data shall be sealed for 72 years.
DES was specified as being suitable for sensitive but not classified
information. NOWHERE in the specification was it said to be suitable
for ALL sensitive information as long as it wasn't classified.
> A cipher to protect sensitive but not classified data, to be used
> from 1976 to 1986, must be sufficiently secure to protect data
> collected for the 1980 census. Thus the cipher must remain unbroken
> until at least 2052.
>
> DES has failed. It was never adequate - not even for its
> initial purpose and intended lifetime.
Please point to a part of the statement of its initial purpose that
says it will be used as the sole protection for census data at any
time during its operation.
The statement that a cipher may be used for sensitive but not
classified data is NOT the same as saying that it is suitable for ALL
POSSIBLE sensitive data as long as it is not classified.
For that matter, the census data is specified to be _sealed_ for 72
years. That means it is not released. It does NOT mean that it is
released in encrypted form, using an encryption believed to be secure
for at least 72 years.
Your argument is 100% fallacious. It's about equivalent to my saying
that I've seen a dog get wet. I'm sure at some time in your life,
you've been wet. Therefore, you are a dog.
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: cant have your cake and eat it too
Date: Sat, 12 Jun 1999 00:44:55 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
> hey, wait a minute, I was asking why not use a different
> key for every stage of DES, and the response was
> 1) its only nominally better and
> 2) the size of the key is too big to generate from a pass phrase.
>
> but, given a secure algorithm, the weakest link becomes
> the size of the key. which says to me, current cracking
> capabilities require keys bigger than you can generate
> with a "human-memorizable-pass-phrase".
That's simply false. IIRC, you had previously mentioned the use of
independent keys for each round of DES. That involves a 768-bit key,
and memorizing a long enough pass-phrase to generate a 768-bit key
certainly IS unreasonable.
It is NOT, however, necessary to use a 768-bit key to ensure security
against a brute-force attack for a reasonable period of time. Being
extremely conservative, we can estimate that a 128-bit key will be
immune to a brute-force attack for at least the next 50 years.
(Actually, if Moore's law holds true, it should be over 100 years, but
as I said, I'll be extremely conservative).
A 45 character pass-phrase is easily adequate to generate a 128-bit
key. I think it's well within most people's capabilities to memorize
45 characters, but not 200 or so.
> so you cant have small keys and secure data too.
Below a certain level, that's true. However, there's some middle
ground where it appears to me that a pass phrase is fairly easy to
memorize, is currently secure, and will remain so for a reasonable
period of time.
> it seems whats needed is a new approach to how keys
> are entered into an encryption system.
Other methods are already in use in quite a few systems. I don't
think they're really necessary yet in most cases, but they can also
simplify some things. Just for example, quite a few networks now use
small, hand-held devices for user authentication. The authenticating
computer sends out a challenge, which you key into the hand-held
device. It then generates a response that you send back to the
authenticator.
The beauty of this is that _everything_ that goes over the network is
encrypted. You typically use the clock in generating the challenge,
and require a response to that challenge within a relatively short
period of time. By keeping the time period short, you make a useful
attack MUCH more expensive. If you used DES and limited the time to
15 seconds, an attack using present technology would almost certainly
cost at least several billion dollars. If you increase the key to 80
bits and limit the response time to 10 seconds, I don't think anybody
can really contemplate technology to carry out an attack.
> why is it that people carry keys to a car worth as
> little as a thousand bucks, but we dont carry
> a physical key (dongle) for encrypting computer/voice/etc
> data, which can be worth much, much more?
BECAUSE it's worth so much more. It's all too easy for physical keys
to be lost or stolen. When people encrypt valuable data, they
typically expect that it'll stand up to somebody really trying to
break in, who may have thousands or millions of dollars worth of
equipment at their disposal.
By contrast, an experienced thief can break into an average car in
less than a minute, using equipment that costs less than you probably
spent on lunch today. Interestingly enough, when they try to make
cars more secure, it's typically by adding an electronic security
system that involves memorizing a combination and punching it into a
keypad on the door. Likewise, most electronic banking is done using a
combination of a physical key AND some password you're expected to
memorize.
To summarize, possession of a physical key is NOT a route to
particularly high security as a rule.
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: Cracking DES
Date: Sat, 12 Jun 1999 00:44:53 -0600
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
>
>
> Patrick Juola wrote:
> >
> > Well, first, to the best of my knowledge, there have never been any
> > published claims that single DES would require 'more time to crack
> > than the universe is old'.
>
> The director of the FBI said this last year at a press conference or
> something (preaching to the unwashed masses).
Yes and no -- if you look carefully, you'll notice that the statement
was made with very careful qualifications that make it seem like it
means more than it really does. The statement made was that a brute-
force attack with a general purpose computer (I believe a fairly
recent Cray was mentioned) would take an extremely long time, though I
think the actual number given was a few centuries rather than longer
than the age of the universe.
The problem, of course, is that a single CPU, general-purpose computer
is EXTREMELY poorly suited to a brute-force attack on DES. Special
purpose hardware can carry out an attack MUCH more quickly and
economically.
In short, what he said was almost certainly true but basically
meaningless. It was probably quite impressive sounding to his
audience though. In most areas, things like this would be quite
obvious because people would realize that nonsense was being spewed.
For example, I could show that attempting to replace an elevator with
an airplane wouldn't work very well (or vice versa). It wouldn't
really mean that either elevators or airplanes are useless, but if you
didn't know the basic characteristics of each, such an argument might
sound reasonable nonetheless.
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: sci.math.num-analysis,comp.sys.cbm
Subject: Re: Random numbers on a sphere
Date: 12 Jun 1999 06:37:03 GMT
Reply-To: [EMAIL PROTECTED] (Matthew Montchalin)
Dave Seaman wrote:
|>| The idea was to produce points that are uniformly distributed with
|>| respect to the area of a sphere. See my earlier post in this thread
|>| (the long one) for an explanation. I prepared that summary precisely
|>| because this topic has come up several times before and has generated
|>| some extremely heated arguments.
Matthew Montchalin perked up:
|>This is EXTREMELY interesting!
|
|>For a series of pseudo-random numbers, 1 * * * n, would not the choice of
|>algorithms used produce different patterns on any given sphere that these
|>numbers are plotted on?
Dave Seaman wrote:
|Different patterns, yes. In the same way that if you generate uniform
|deviates on [0,1] and then subtract each value from 1, you will get a
|different pattern. Nevertheless, the patterns have the same probability
|distribution.
I think the part that interests me the most, is comparing the "random
walk" (if you draw lines from point to point over the curved surface) that
is produced by the various pseudo-random numeral generators. I'm curious
if I can see (or better yet, recognize, or distinguish) the patterns that
are produced by the various generators that I wish to try out...
I keep coming up with new random number generators, and I need to figure
out where their weaknesses are... There are all /kinds/ of ways of doing
random number analysis, and this sounds like a very interesting one to try
out.
--
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: One Time Pad
Date: Fri, 11 Jun 1999 20:40:08 GMT
On Thu, 10 Jun 1999 10:41:40 +0200, "Ruppert"
<[EMAIL PROTECTED]> wrote:
Yeah sort of...
Basicialy (sp) a OTP is a length of text P of length n, and a _random_
key K of length n. A normal OTP is either
C=(P+K)mod 10 (ie chinese addition, ie don't carry -- 6+6 =2, 7+3 =1,
1+1 =2)
P=(C-K)mod 10
By hand (classic spies tool)
or
C=P XOR K
P=C XOR K
in Binary on computers.
Eg1(first method)
1234 = P 8489=K (<------ NOT random)
1234 <------Plaintext
+8489 <------Key
=9613 <------Ciphertext
9613 <----- C
--8489 <------K
=1234
ta-da!
note: 3-9 = 4 in "chinese aritmetic"
Eg2 (second)
P=1111111111
K=0101011011
C=1010100100
C XOR K =
1010100100
XOR 0101011011
= 1111111111
Ta da!
Clear?
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Question from a neophyte
Date: Sat, 12 Jun 1999 09:20:50 GMT
On Sat, 12 Jun 1999 04:25:54 GMT, Donald Clark <[EMAIL PROTECTED]> wrote:
>Anyone,
Hmmmm.... that's me, i guess..
> I would greatly appreciate
>anyones opinions as to what books would be
>appropriate for the novice.
The obvious, Bruce Schneier , Applied Cryptogragraphy; this is
excellent for the novice.
http://fermat.ma.rhbnc.ac.uk/~fauzan/papers/index.html has a good
intro to cryptanalysis
<lifted from Tomstdenis>
Terry Ritter
Jon Savard
;Both have good sites
http://people.goplay.com/tomstdenis/index.html papers; look at
- TEA
- RC5
- Blowfish
</lifted>
Just ask around, get some URLs (i am new too, really, the only way is
to read everything you understand. Once you know the basics, post any
q. you have here (just look at some of my dumb posts!))
[EMAIL PROTECTED]
[formerly Jim_101_202]
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Cracking DES
Date: 11 Jun 1999 12:54:31 -0700
Note that experienced cryptanalysts seem able to make a pretty decent guess
at which ciphers are most likely to break far before they can actually produce
the full attack which confirms their guess.
Therefore, if I have n ciphers to analyze and I just want to break one of
them (it doesn't matter which one), I won't devote equal amounts of time to
all of them -- instead, I'll focus my attention on the few which look most
likely to break under deep study.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: cant have your cake and eat it too
Date: Fri, 11 Jun 1999 20:22:06 GMT
On 11 Jun 1999 13:00:28 -0700, [EMAIL PROTECTED]
(David Wagner) wrote:
<snip>
>Note that such an existence proof seems likely to imply that P != NP.
>Thus, as a heuristic, such an existence proof is probably hard to find.
<snip>
"P!=/=NP" hmmmm....... Lots of people talk about this one but what is
it.... ?
[EMAIL PROTECTED]
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
