Cryptography-Digest Digest #699, Volume #9 Fri, 11 Jun 99 22:13:03 EDT
Contents:
Re: cant have your cake and eat it too (John Myre)
Re: Slide Attack on Scott19u.zip (SCOTT19U.ZIP_GUY)
Re: MD5 test data (James Pate Williams, Jr.)
Re: cant have your cake and eat it too (SCOTT19U.ZIP_GUY)
Re: cant have your cake and eat it too (wtshaw)
Re: huffman code length (Antaeus Feldspar)
IA-64 instruction set to include population count (John Savard)
Re: Cracking DES (wtshaw)
Re: DES (Paul Koning)
Re: DES lifetime (was: being burnt by the NSA) (Paul Koning)
Re: DES (Jerry Coffin)
Re: DNA cryptology (from the NYT) (wtshaw)
Re: MD5 test data (millipede)
Re: differential cryptanalysis (Fauzan Mirza)
----------------------------------------------------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: cant have your cake and eat it too
Date: Fri, 11 Jun 1999 13:16:53 -0600
John Savard wrote:
<snip>
> If a 128-bit key is enough to be secure against a brute-force attack,
> then it is *possible* to construct a secure cipher with a 128-bit key,
> since only a brute-force attack is applicable to _all_ ciphers with a
> 128-bit key or any other particular key length.
>
> John Savard ( teneerf<- )
> http://members.xoom.com/quadibloc/crypto.htm
Has anyone every done an "existence proof" of a secure cipher
design? (That is, in mathematics it is sometimes possible to
prove that some object with certain properties must exist,
without actually showing an example (usually because we don't
actually have an example). So is there a result that says
there must exist, for example, a cipher with a 128 bit key
for which brute force *really is* the best possible attack?)
I presume no one has done a non-existence proof - that it
is *impossible* to create a secure cipher.
J. Savard asserts that it is possible to construct a secure
cipher. Others have asserted that a proof of security is
impossible. Logically, both of these could be true at the
same time - we might know that secure ciphers exist but
never know which ones they are. AFAIK, neither statement
can be regarded as proved (or disproved) - it really is
a matter of opinion (so far).
John M.
------------------------------
From: SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]>
Subject: Re: Slide Attack on Scott19u.zip
Date: Fri, 11 Jun 1999 18:00:48 GMT
In article <[EMAIL PROTECTED]>,
Horst Ossifrage <[EMAIL PROTECTED]> wrote:
> 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.
>
This is interesting in that you seem to need 2^37 entries
but ther are exactly 2^38 possible combinations. If one could
mode the code to use 38 bits then just store the 2^38 pair
combinations and if the enemy uses a moded program that only
has 38 bits allowed this would allow all future messages with
the same exact key to be broken. However the program does not
work at all for less then 64 bits.
> 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
>
Keep me posted and does any one now where to get a free
post script reader since the papers is writtien in that format.
Or is there an ascii version of the paper so poor people can
read it?
--
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
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (James Pate Williams, Jr.)
Crossposted-To: comp.security.misc
Subject: Re: MD5 test data
Date: Fri, 11 Jun 1999 21:09:00 GMT
On 11 Jun 1999 19:28:15 +0100, Tony Lezard <[EMAIL PROTECTED]
SPAM PLEASE> wrote:
>I need to test the output of an MD5 implementation. Could someone with
>a known correct version of MD5 hash some strings and post/email them?
>From _Handbook of Applied Cryptography_ by Alfred J. Menezes et al.
Table 9.6 "Test vectors for selected hash functions" page 345:
"abc"
900150983cd24fb0d6963f7d28e17f72
"abcdefghijklmnopqrstuvwxyz"
c3fcd3d76192e4007dfb496cca67e13b
==Pate Williamms==
[EMAIL PROTECTED]
http://www.mindspring.com/~pate
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: cant have your cake and eat it too
Date: Fri, 11 Jun 1999 22:14:26 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(John Savard) wrote:
>[EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote, in part:
>
>> 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.
>
>Yes, but all that means is that you can't prove that *a particular
>cipher* with a 128-bit key is secure.
>
>If a 128-bit key is enough to be secure against a brute-force attack,
>then it is *possible* to construct a secure cipher with a 128-bit key,
>since only a brute-force attack is applicable to _all_ ciphers with a
>128-bit key or any other particular key length.
>
The problem is yes it is possible in thery to consturct a cipher
of 128 bits key that is do secure only a brute force search is possible
however how does one go about proving it is that secure. Far better to
use a simler cipher with a longer key.
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: [EMAIL PROTECTED] (wtshaw)
Subject: Re: cant have your cake and eat it too
Date: Fri, 11 Jun 1999 16:13:31 -0600
In article <[EMAIL PROTECTED]>, Greg Bartels <[EMAIL PROTECTED]> wrote:
>..... 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.
>
> it seems whats needed is a new approach to how keys
> are entered into an encryption system.
> rather than having a human type a phrase which
> gets hashed into a key.
>
....
>
> 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?
>
It all boils down to this, if you are lazy, you are not likely to keep
good security, or even find it in the first place;. surely, what is first
offered to the average person is rather poor. PT Barnum lives.
There is no reason that quite long passages cannot be remembered: In fact
most of us have learned such things in the past, and there are
organizations that demonstrate the ability of average people to learn
rather lots of material as a part of their entrance protocols.
Perhaps you already know something extensive which could be slightly
modified for such purposes. Consider the trite: Now is the time for all
good men to come to the aid of their country. Change two or three words
in unexpected directions and you suddenly have something which might be
most difficult to guess. Remember that each person has the ability to
create on the fly a sentence of ten words that has likely never been even
uttered before in the history of the world.
--
Weathermen prosphesize and insurance companies predict, while both pretend to be doing
the other to get an audience.
------------------------------
From: [EMAIL PROTECTED] (Antaeus Feldspar)
Crossposted-To: comp.compression,alt.comp.compression,sci.math
Subject: Re: huffman code length
Date: Fri, 11 Jun 1999 18:08:28 -0400
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> Mr. X wrote:
> >
> >
> > Some possible symbol sets for code set [0,1]
> > [.1,.9] [.5,.5] [.9,.1]
> >
> > Some possible symbol sets for code set [0,10,11]
> > [.33,.33,.33] [.34,.33,.32] [.8,.1,.1]
>
> Maybe I misunderstood you, but what I think is preferable is a method
> to compute, given a Huffman tree, the extreme frequency distributions
> within whose range any valid distribution must lie.
>
> M. K. Shen
You mean something like: "Ah, symbols A, B, and C have codes 0,
10, and 11 respectively; therefore, if the tree was created by the
Huffman algorithm, the lowest frequency A could have is *just* above
..33..., and the highest frequency for both of B and C is .33..."?
-jc
--
* -jc IS *NOW* [EMAIL PROTECTED]
* Home page: http://members.tripod.com/~afeldspar/index.html
* The home of >>Failed Pilots Playhouse<<
* "Better you hold me close than understand..." Thomas Dolby
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: IA-64 instruction set to include population count
Date: Fri, 11 Jun 1999 22:04:54 GMT
A population count instruction, and an instruction for finding the
first zero byte, are included in the instruction set of the new IA-64
processors to come from Intel.
Although I could not find a "bit matrix multiply" instruction, there
are Mix and Unpack instructions that may help in moving bits around,
as well as an instruction to copy a field of consecutive bits in or
out of one register from or to the least significant bits in another.
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Cracking DES
Date: Fri, 11 Jun 1999 15:58:52 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Terry Ritter) wrote:
> The next time you want to read a 200-page book, rip it apart and
> reconstruct the writing from any random 10 pages. So now "reading a
> book" takes only 5% of the time it did. That should be a boon for
> busy executives everywhere!
I'm tempted to do this with Cryptonomicon, since it is partially shuffled
chronologically.
>
> If we consider the essence of a book to be the main plot, you might
> get lucky, although even that seems dicy. But if the essence of the
> book is the experience of immersion in a different situation, you can
> not get that from 10 pages. End of story.
>
One wonders whether 900+ pages is verging on too much immersion, but I
normally prefer sprinkling anyway.
Concerning the importance of comprehensive knowledge to be gained through
decrypted material, surely there is going to be some redundance. If
messages are too repeatitive about subjects that need to be highly
protected, the error is in talking, or writing, too much. One valid goal
in secure communications is to keep content high and ciphertexts to a
minimum, so anything not decrypted is going to be important in its own
right.
--
Weathermen prosphesize and insurance companies predict, while both pretend to be doing
the other to get an audience.
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: DES
Date: Fri, 11 Jun 1999 12:57:59 -0400
Thomas Pornin wrote:
>
> According to Paul Koning <[EMAIL PROTECTED]>:
> [initial and final permutations in DES]
> > Fortunately, there are ways to do it in software that aren't all that
> > expensive.
>
> Bitslice comes to mind. Since this is only routing of data, it is free.
> However, bitslicing is really efficient for DES only when enciphering a
> big block of data in ECB mode, or when programming a password-cracker.
Good point. I wasn't thinking of that one, but rather of the neat
shuffle by masking and rotating you'll find in Eric Young's code.
Check it out. (Bring aspirin. :-) )
Also, bitslice also works for CBC when decrypting.
paul
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: DES lifetime (was: being burnt by the NSA)
Date: Fri, 11 Jun 1999 17:26:35 -0400
[EMAIL PROTECTED] wrote:
>
> Which is the requirement: A cipher must remain unbroken for,
> A) its operational life,
> or
> B) the intelligence life of any data it protects?
B, of course, that's elementary.
> I think that's a pretty basic question. Could the the NSA
> have come up with the wrong answer?
No, but some people may be using DES to protect data that needs
protection beyond what DES can provide (hours to a year or so
depending on the value of the data).
> 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. 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.
Right, so it would be a mistake to apply DES to that job.
(That was true from the start, since DES never claimed a
service life of 72 year.)
> DES has failed. It was never adequate - not even for its
> initial purpose and intended lifetime.
Only if you assume that protecting census data was part of
the requirement. I don't know if anyone else made that
assumption (since it is rather obviously wrong). But there
has been, and still is, data of low enough value and short
enough life that DES protects it adequately.
paul
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: DES
Date: Fri, 11 Jun 1999 17:36:42 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
[ ... ]
> > Many software implementations skip it.
>
> Not if they are DES they don't.
By definition, a software implementation is not DES, and cannot be
DES, even if it can encrypt things so a DES implementation can decrypt
it and vice versa. I.e. the standard says that to qualify as DES, the
implementation MUST be done in hardware.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: DNA cryptology (from the NYT)
Date: Fri, 11 Jun 1999 15:43:25 -0600
In article <[EMAIL PROTECTED]>, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
> Mark wrote:
> >
>
> > bases. The scientists built a DNA strand in which different combinations of
> > bases represented the letters of their message.
> > At either end of the strand they put sequences of bases that would serve as
> > the key to finding the strand. The strand was one three-thousandths the
> > width of a human hair in length.
> > The scientists then chopped the entire DNA of a human cell into pieces of
> > about the same length, and mixed them with the message strand.
> > They soaked the mixture into paper with a period printed on it, cut out the
> > period and pasted it onto a letter. They mailed the letter to themselves to
> > prove that the DNA could survive the rigors of the U.S. mail.
>
> I can't help wondering why one takes such great troubles to achieve
> information hiding tasks. The more common way nowadays of hiding
> bits in pixels of graphical files is also of too much effort (unless
> what one wants is watermarking to protect against fraud of multimedia
> products.)
>
It is comforting to note that DNA is not a binary system, put I once said
that nature writes the best crypto; such a structure seems a natural for
adaptation if not in a purely biological sense, an electronic one.
Surely cryptological means are to be ones that will be closely used in
unscrambling human genetics.
--
Weathermen prosphesize and insurance companies predict, while both pretend to be doing
the other to get an audience.
------------------------------
From: millipede <[EMAIL PROTECTED]>
Crossposted-To: comp.security.misc
Subject: Re: MD5 test data
Date: 12 Jun 1999 00:41:27 GMT
Reply-To: millipede <[EMAIL PROTECTED]>
Tony Lezard <[EMAIL PROTECTED] SPAM PLEASE> wrote:
> I need to test the output of an MD5 implementation. Could someone with
> a known correct version of MD5 hash some strings and post/email them?
vampire$ md5 -s "Once upon a time"
MD5 ("Once upon a time") = cb3901f2f743528962715d9d85a5e112
vampire$ md5 -s "there was this dude"
MD5 ("there was this dude") = c4c861d8f43cd4f5805088b364ca5426
vampire$ md5 -s "(we'll call him Tony)"
MD5 ("(we'll call him Tony)") = 3e6a083ec5c3f4bc387a23f660336e2d
vampire$ md5 -s "who wanted to test"
MD5 ("who wanted to test") = 06beb57eb077ea9a7db109392fe126d2
vampire$ md5 -s "his implementation of md5"
MD5 ("his implementation of md5") = 3904f55518184885cef939271c5520b9
vampire$ md5 -s "."
MD5 (".") = 5058f1af8388633f609cadb75a75dc9d
vampire$ md5 -s " "
MD5 (" ") = 23b58def11b45727d3351702515f86af
vampire$ md5 -s "And they lived happily"
MD5 ("And they lived happily") = edca6122b1c565dc11baee7330bf34d2
vampire$ md5 -s "ever after."
MD5 ("ever after.") = 2e8cc2bdc5d3988cc0a32685b3132c0a
vampire$ md5 -s "The End."
MD5 ("The End.") = aaad2dbb73e5a48d4f0d207c56b7dc6f
vampire$
------------------------------
From: Fauzan Mirza <[EMAIL PROTECTED]>
Subject: Re: differential cryptanalysis
Date: 12 Jun 1999 01:06:53 GMT
Reply-To: [EMAIL PROTECTED] (Fauzan Mirza)
[EMAIL PROTECTED] wrote:
> In an earlier thread (DES) Tomstdenis said that in diff analysis you
> take A (=P-P') and B (=C-C') and find a difference which is more
> prominent than it should be. Cool, but I'm something of a simpleton
> -- how exactly is such a thing done? I assume you take lots and lots
> of known p + c, and look for a trend in A and B .... but how
> precisely?
It works the other way round: the cryptanalyst looks for differentials
that hold with high probability by examination of the encryption
algorithm; then the attacker looks for ciphertext pairs that satisfy
those differentials.
You might be interested in reading my introduction to "Block Ciphers
and Cryptanalysis" which is available from:
http://fermat.ma.rhbnc.ac.uk/~fauzan/papers/index.html
It provides a gentle introduction to differential and linear
cryptanalysis.
Fauzan
==================================================================
Fauzan Mirza Department of Mathematics
Research Postgraduate Royal Holloway, University of London
==================================================================
------------------------------
** 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
******************************
