Cryptography-Digest Digest #697, Volume #9 Fri, 11 Jun 99 15:13:03 EDT
Contents:
Re: ATTN: Bruce Schneier - Street Performer Protocol (Bruce Schneier)
Re: cant have your cake and eat it too (SCOTT19U.ZIP_GUY)
Re: KRYPTOS (Jim Gillogly)
Slide Attack on Scott19u.zip (Horst Ossifrage)
Re: DES lifetime (was: being burnt by the NSA) (SCOTT19U.ZIP_GUY)
Re: being burnt by the NSA (Paul Koning)
Re: ATTN: Bruce Schneier - Street Performer Protocol (Patrick Juola)
Re: Fw: The Mathematics of Public-Key Cryptography, June 12 - June 17, 1999 (Medical
Electronics Lab)
Re: ATTN: Bruce Schneier - Street Performer Protocol (John Savard)
Re: Random numbers on a sphere (John Savard)
Re: KRYPTOS (Medical Electronics Lab)
Re: Cracking DES (Terry Ritter)
Re: DES lifetime (was: being burnt by the NSA) (John Savard)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Bruce Schneier)
Subject: Re: ATTN: Bruce Schneier - Street Performer Protocol
Date: Fri, 11 Jun 1999 14:13:45 GMT
On Fri, 11 Jun 1999 01:22:15 GMT, [EMAIL PROTECTED] (Inky O.
Lamer) wrote:
>[EMAIL PROTECTED] (Bruce Schneier) wrote:
>
>>This newsgroup has never been particularly scientific.
>
>Ouch! You're attacking the entire sci.crypt newsgroup?
I don't think so. Calling something non-scientific is not an attack.
Most everything I hold dear in life isn't particuarly scientific. As
far as I know, sci.crypt is a discussion list. Even
sci.crypt.research, which we created to have more mathematical content
than sci.crypt, isn't particularly scientific. There's nothing wrong
with that; I skim both lists regularly.
Bruce
**********************************************************************
Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: cant have your cake and eat it too
Date: Fri, 11 Jun 1999 16:31:15 GMT
In article <7jr3r5$hef$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Patrick Juola)
wrote:
>In article <[EMAIL PROTECTED]>, Greg Bartels <[EMAIL PROTECTED]> wrote:
>>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".
>>
>>so you cant have small keys and secure data too.
>
>Sure you can. A 128-bit key is 'small' by the standards we're discussing,
>but is still secure against brute force.
>
>If 128-bits gives you all the security you need, why go with 2000?
>
> -kitten
Because you can't prove that 128 bits is secure. Oh yes maybe it is
secure against a blind no intelligent brute force attack. But a blind dumb
brute fore attack is not everything. Maybe you think it is. Buy those
standards Enigma as used by the german navy would still be safe.
Since a brute force attack on it is larger than 128bits. What you fail to
see is that there are other forms of attack so one should not force the
use of an arbitrary small key unless one does not care if the code can
be broken.
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 09:01:07 -0700
"Douglas A. Gwyn" wrote:
> One section of Kryptos is clearly a transposition cipher, which means
> that it is solvable with enough trial and error by someone who knows
> the general methodology.
Doug was right about this -- I solved the transposition section last
night. I now have solutions to all but the last few lines of the
sculpture. Perhaps I should use Kelsey & Schneier's "Street Performer
Protocol" to publish the solutions... so far my plan is to submit it
to The Cryptogram, the publication of the American Cryptogram Association.
> (I haven't had the time to work on it; my
> main contribution so far was to post an accurate transcription several
> years ago, which one sometimes finds floating around the Internet with
> attribution and other notes removed.)
Doug's careful transcription (complete with attribution) was critical
to solving it. I can confidently say that a missing character in the
transposition section would have made it very much more difficult, and
probably impossible for me.
> I suppose if you get desperate, you could burgle the DCI's vault. ;-\
There're still those last few lines waiting to be decrypted. I'll
review the Mission Impossible movie for tips on getting into the
vault, if all else fails.
--
Jim Gillogly
Trewesday, 21 Forelithe S.R. 1999, 15:52
12.19.6.4.16, 13 Cib 4 Zotz, Sixth Lord of Night
------------------------------
From: Horst Ossifrage <[EMAIL PROTECTED]>
Subject: Slide Attack on Scott19u.zip
Date: Fri, 11 Jun 1999 08:14:05 -1000
Attempted Slide Attack on Scott19u.zip
During the next 3 days, a Slide Attack will be discussed
against the Scott19u.zip cryptographic algorism. The
attack was introduced at the FSE-6 Conference in March,
1999, Rome. The authors were Alex Biryukov and David
Wagner at the Fast Software Encryption Workshop #6. You
can read a Postscript version of the paper here:
http://www.cs.berkeley.edu/~daw/papers/
The Slide Attack is done
using known plaintexts and known ciphertexts. Below, two
encryptions are put side by side, with a one round offset.
F is the round function:
P0
F
P1 P0'
F F
P2 P1'
F F
P3 P2'
F F
P4 P3'
F F
C P4'
F
C'
Pj is a plaintext in round j, C is a ciphertext.
The analyst does not have access to the inner workings
of hardware with the key nor software with the key.
The analyst has, for an m bit key, more than 2^m/2
matching plaintexts and ciphertexts. The cryptanalyst
can check whether it is possible that F(P0)=P0'. This
checking requires that a round is "weak" so that
logic will rule out many candidate P, C pairs. The check is
made feasible by knowing that F(P0)=P0' AND F(C)=C'
simultaneously for the same key.
The documentation for the Scott19u.zip algorithm is at:
http://members.xoom.com/ecil/page2.htm#Dec
The encryption and decryption use the following
round function:
Encryption: Cn = S{(Cn-1 XOR Pn) + Pn+1}
decryption: Pn = Cn-1 XOR (SI{Cn} - Pn+1)
Here, n is the word number in a variable block size, S
is the S-Box and SI is the inverse S-Box.
Keep in mind the overlaying offset shown next:
Plain0 Plain1 Plain2 Plain3
Cifer0 Cifer1 Cifer2 Cif
er3
That describes the 19 bit words kept in memory, with the
result of the encryption equation being written back to
the memory, but offset a few bits. On the next round, the
offset word boundaries are ignored and the first boundaries
are used on the bits in memory. Since the cipher uses a
variable block size, we can choose any number of bits or
words in a block. It is temping to use a 2 bit plaintext
block, but for today, a 2 word block is used (38 bits).
Next, we need to find a "slid pair" from chosen plaintexts
and ciphertexts. A slid pair is 4 blocks. A block can be
any size for Scott19u.zip so we will use a 2 word block of
38 bits. The goal is to find the key made 19*2^19 bits,
usually, but for Scott19u.zip we only need to find the
S-Box, since the key is only used to create an S-Box.
Because of the Birthday Paradox, randomly chosen plaintexts
will create a "first round ciphertext"
that has the same value as another
plaintext after 2^19 guesses. Similarly for the chosen
ciphertext, after 2^19 guesses, we may find a ciphertext that
has the same value as an intermediate value one round before
the end.
The round function is a "weak function" as described the the FSE
paper. In other words, once a plaintext and a matching first round
result are found, some key bits can be determined. The key discovery
is validated by showing that the same key bits are consistent with
the ciphertext pair and plaintext pair (which together constitute
a Slid Pair). Instead of key bits, we used S-Box bits.
By making the block as small as 38 bits as we have done, it makes
the Birthday Paradox become advantageous, but it increases the
number of Slid Pairs needed to reveal the whole S-Box. If one
Slid Pair reveals 2 S-Box words, then 2^18 Slid Pairs are needed
to get the whole S-Box. So about 2^37 calculations are needed,
(2^18 * 2^19). Each calculation may be lengthy. Please feel
free to recalculate this yourself and correct it.
But a complication occurs because the S-Box entries usually are
not the same for the first round pair and the last round pair.
This, apparently, is why the Slide Attack fails for Scott19u.zip.
The cryptanalyst knows that there will be no key bits shared
by the first round pair and the last round pair which together
would have formed a Slid Pair. The only Slid Pairs using the
same 2 S-Box entries for the first round and last round are pairs
which have the same values: That Only Happens If The Final
Ciphertext Is Equal To The First Round Result!
This concludes today's installment. In the FSE 6 paper, round
key bits were in common between the first round and the last round.
That is how consistency is shown. Scott19u.zip does not have
predetermined round keys, causing the Slid Attack to become more
difficult, perhaps squaring the amount of work needed to succeed.
2^74 calculations may be needed. We can try a smaller block size
tomorrow, after you post your comments.
Horst Ossifrage
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: DES lifetime (was: being burnt by the NSA)
Date: Fri, 11 Jun 1999 16:37:26 GMT
In article <7jr4bn$hfr$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Patrick Juola)
wrote:
>In article <7jqubp$e0g$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
>>Douglas A. Gwyn wrote:
>>
>>> DES and Skipjack both admirably met their design goals.
>>> DES has just recently *barely* been broken in a published attack,
>>> so it held up far longer than its design lifetime of ten years.
>>
>>Which is the requirement: A cipher must remain unbroken for,
>> A) its operational life,
>> or
>> B) the intelligence life of any data it protects?
>>
>>I think that's a pretty basic question. Could the the NSA
>>have come up with the wrong answer?
>
>These are two different requirements. You have to consider
>whether the intelligence life of the data protected is within
>the capacity of the operational life of the cypher.
>
>If I decide that I need to get from Pittsburgh to LA in a day, and
>therefore go out and buy a bicycle, did the Schwinn company ''come
>up with the wrong answer''? No -- I did in deciding that the
>bicycle was suitable for my needs.
>
> -kitten
IF DES was a successful cipher it was becasue the NSA could break
it the day they made it public. They may have thought low level data was
safe from dunb foreigners who lack the knowledge base of the great NSA
but its real value was that many blindly used DES so that the NSA could
read what secrets they where foolish enough to encrypt with DES.
The new AES winner we however meet these requirements in the near
future.
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: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: being burnt by the NSA
Date: Thu, 10 Jun 1999 12:11:41 -0400
Greg Bartels wrote:
>
> Patrick Juola wrote:
> >
> > In article <[EMAIL PROTECTED]>, Greg Bartels <[EMAIL PROTECTED]> wrote:
> > >I bought a book, a couple months ago, its title was
> > >"Breaking DES",
> ...
> AM I THE ONLY PERSON WHO"S HEARD OF THIS BOOK?
> or is the book a load of bull?
I bought it the moment it came out. Looks solid to me.
It got plenty of publicity at the time.
> 3) I think it might have mentioned that further improvements
> would make the system both cheaper and faster.
> they gave specifics, but I cant remember what they were.
> I seem to remember the book saying recovery time could
> be a couple days.
Easily. The design shown is a simple and low budget
solution that doesn't come anywhere near pushing the
state of the art. Its goal was to make a dramatic
demonstration. If you wanted to spend some money building
a *fast* cracker, you shouldn't have any trouble at all
getting at least a factor 10 speedup.
paul
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: ATTN: Bruce Schneier - Street Performer Protocol
Date: 11 Jun 1999 10:25:08 -0400
In article <[EMAIL PROTECTED]>,
Inky O. Lamer <[EMAIL PROTECTED]> wrote:
>[EMAIL PROTECTED] (Bruce Schneier) wrote:
>
>>This newsgroup has never been particularly scientific.
>
>Ouch! You're attacking the entire sci.crypt newsgroup?
Is that an attack?
I note a definite informality of dialogue, an almost complete lack
of formal citation, lots of theorizing but very little experimental
demonstration,... sounds "unscientific" to me.
-kitten
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: Fw: The Mathematics of Public-Key Cryptography, June 12 - June 17, 1999
Date: Fri, 11 Jun 1999 12:19:27 -0500
Mike Murray wrote:
>
> Hey all...
>
> Hadn't seen any info on this posted on the newsgroup, but anyone
> within driving distance of Toronto and with a few days off (thank God
> I'm a student) might enjoy this conference... I know I'm going to.
>
> Mike
> [...]
> Conference on
>
> The Mathematics of Public Key Cryptography
>
> The Fields Institute for
> Research in the Mathematical Sciences
> Toronto, Ontario
>
> June 12 - 17, 1999
I can't go, but I'd appreciate a report on
what you heard if you get a chance to post here!
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: ATTN: Bruce Schneier - Street Performer Protocol
Date: Fri, 11 Jun 1999 15:17:28 GMT
Anonymous <[EMAIL PROTECTED]> wrote, in part:
>The proposal on the website
>I just saw is INCREDIBLY NAIVE on your part.
>Are you aware of the battle going on over MP3s in the music business today?
*Yawn*. Bruce proposes a method whereby people can donate money
electronically to people designing works that will, if enough money
comes in, be put into the public domain (or made available under the
GNU licensing agreement).
This is in no way a declaration of open war on those who choose to
make their works available in a more controlled way. It is not a
denunciation of the concept of copyright.
Yes, Hollywood and the music industry have sometimes gone to excess in
the defence of their lucrative businesses. However, I don't recall
that Richard Stallman has mysteriously disappeared recently.
I do not know what has prompted these fantasies...
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: sci.math.num-analysis
Subject: Re: Random numbers on a sphere
Date: Fri, 11 Jun 1999 15:22:21 GMT
[EMAIL PROTECTED] (Matthew Montchalin) wrote, in part:
>Ed McBride wrote:
>>>What am I missing? I would use spherical coordinates, select theta
>>>randomly between 0,2pi then phi randomly between 0,pi set radius =1
>>>and I'm done.
>Pierre Asselin wrote:
>>Too many points near the poles. Try it and see.
>Doesn't this ultimately boil down to tiling a series of finite curved
>plane with imperfectly curved segments, tolerating some arbitrary error by
>saying 'good enough,' and then going with that?
Actually, there's no need to tolerate error.
One can use the cylindrical equal-area projection to map the sphere to
a rectangle, and generate random points on a sphere (with the
exception of two points - the poles - unless special effort is made)
without distortion or the need to discard some points.
So you choose phi randomly between 0 and 2 pi, and choose sin(theta)
randomly between -1 and 1.
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/crypto.htm
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: KRYPTOS
Date: Fri, 11 Jun 1999 12:31:59 -0500
Jim Gillogly wrote:
> Doug was right about this -- I solved the transposition section last
> night. I now have solutions to all but the last few lines of the
> sculpture. Perhaps I should use Kelsey & Schneier's "Street Performer
> Protocol" to publish the solutions... so far my plan is to submit it
> to The Cryptogram, the publication of the American Cryptogram Association.
Congratulations Jim!
> Doug's careful transcription (complete with attribution) was critical
> to solving it. I can confidently say that a missing character in the
> transposition section would have made it very much more difficult, and
> probably impossible for me.
Congratulations Doug!
> There're still those last few lines waiting to be decrypted. I'll
> review the Mission Impossible movie for tips on getting into the
> vault, if all else fails.
:-) I doubt it's necessary, you'll get a whole lot more people
interested now in looking at it.
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Cracking DES
Date: Fri, 11 Jun 1999 18:31:19 GMT
On 11 Jun 1999 09:49:35 -0400, in <7jr45f$hf5$[EMAIL PROTECTED]>,
in sci.crypt [EMAIL PROTECTED] (Patrick Juola) wrote:
>>[...]
>>There are several different effects to having multiple ciphers: One
>>effect is that each cipher must be detected, acquired, attacked, and
>>broken for future use (if possible). So the more ciphers there are,
>>the more effort which must be expended, and this is linear.
>>
>>Another effect of multiple ciphers is that the universe of information
>>is partitioned into multiple channels, which means that the reward for
>>breaking any cipher is proportionately less. The more ciphers there
>>are, the less information any one of them can expose, and this is also
>>linear.
>
>That isn't 'another effect', that's the same effect in disguise.
>
>Think of it this way. I hire one group of cryptanalysts to analyze
>one algorithm and break everything. That costs me $X -- and I have
>access to everything in the universe of a single cypher.
>
>I now hire N groups to analyze one algorithm and break everything.
>This costs me <= N*$X, and I still have access to
>everything in the universe.
The problem with that logic, of course, is the assumption that the
cryptanalysts can break everything. That is unwarranted and
unrealistic. Under more reasonable assumptions, effort must be spent
on every cipher, but only some ciphers will return a reward.
If we have one cipher, we attack one cipher; if we break it, we get
the universe.
If we have n ciphers, we attack n ciphers; if we break one, we get 1/n
of the universe.
If we have n cipher, we attack n ciphers; if we break m, we get m/n of
the universe.
So, if m is low (ciphers are generally strong) we approach 1/n**2, and
if m is high (ciphers are generally weak) we approach 1/n linearity.
Obviously, we want strong ciphers. I hope all our academic
cryptanalysts can now see their duty and will do it.
>>So for n ciphers, we have n times the attack effort, and 1/n reward
>>for any success,
>
>No, for N times the attack effort, you get complete success. For
>a single attack effort, you get 1/N reward.
No. I assume that some ciphers are strong (at any particular attack
level).
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: DES lifetime (was: being burnt by the NSA)
Date: Fri, 11 Jun 1999 18:18:38 GMT
[EMAIL PROTECTED] wrote, in part:
>DES has failed. It was never adequate - not even for its
>initial purpose and intended lifetime. The cipher resulting
>from the combined efforts of IBM, NBS (now NIST) and NSA, falls
>to an attack that the most naive crypto-newbie ciphers are
>routinely able to resist.
That is correct, although it seems harsh.
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.
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.
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/crypto.htm
------------------------------
** 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
******************************
