Cryptography-Digest Digest #511, Volume #12 Wed, 23 Aug 00 02:13:01 EDT
Contents:
Collomb .. not again! Re: Kryptos and Gillogly (Sundial Services)
Re: How many bits of strength does the ZIP encryption have? (Sundial Services)
Re: 320-bit Block Cipher (Mack)
Re: SHA-2 name rumors (Mack)
Re: Re-using CD-R discs (Mack)
Re: SHA-1 program (cool!) (Mack)
Re: Very Fast Decorrelated Cipher (Mack)
Chat Group ([EMAIL PROTECTED])
Re: 320-bit Block Cipher ([EMAIL PROTECTED])
Re: The DeCSS ruling and the big shots (Mack)
Re: SHA-2 name rumors (S. T. L.)
Re: Crypto Coprocessor on Javacard (Mack)
Re: New algorithm for the cipher contest ([EMAIL PROTECTED])
Re: The DeCSS ruling (Anthony Stephen Szopa)
Re: New algorithm for the cipher contest ([EMAIL PROTECTED])
Re: Very Fast Decorrelated Cipher ([EMAIL PROTECTED])
Re: Comment from Hardware Experts Please (Guy Macon)
Re: Re-using CD-R discs (Guy Macon)
----------------------------------------------------------------------------
Date: Tue, 22 Aug 2000 20:43:39 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Collomb .. not again! Re: Kryptos and Gillogly
Collomb, you have -had- your fifteen minutes of fame. Don't come
begging for more. The solution to a cryptogram is not an issue of
metaphysics.
>collomb wrote:
>
> Achilles
> Did you read my website concerning KRYPTOS ? I give an original
> and complete solution :
> http://calvaweb.calvacom.fr/collomb/
> Do not judge it too quickly.
> I am waiting for your comments
> [EMAIL PROTECTED]
------------------------------
Date: Tue, 22 Aug 2000 20:58:00 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: How many bits of strength does the ZIP encryption have?
Actually, Tim, about a year and a half ago I investigated the
possibilities of cracking PKZip's cipher -without- knowing plaintext and
actually succeeded in doing so from time to time, using a variation of
the published known-plaintext attack.
The essential observation that I made and was pursuing off-and-on is
that the frequency characteristics (and a metric I called "bit density")
in a compressed file are very, very predictable. You can readily tell
if the data is compressed-anything or if random noise (a la
cryptography) has been injected into it. And you can modify, relax,
loosen the tests made by the published algorithm -- so that they are not
looking for "exact" bytes in each of the 12 positions (say), but only
"probable" ones.
It helps considerably that most Zip files are -archives- containing
dozens or even hundreds of members, all of which are likely to have
similar frequency characteristics and sometimes even blocks of very
similar data, especially in the first few hundred bytes.
>Tim Tyler wrote:
>
> Christian Ghisler <chris@ghisler=remove.com> wrote:
>
> : I'm not talking about known plain text attacks here, just cryptographic
> : strength with no known plaintext.
>
> You've got to know /something/ about the plaintext in order to be able to
> distinguish a successful decrypt.
>
> The idea that cryptographic strength remains meaningful if you disallow
> the concept of known plaintext seems dubious.
------------------------------
From: [EMAIL PROTECTED] (Mack)
Date: 23 Aug 2000 04:32:37 GMT
Subject: Re: 320-bit Block Cipher
>For fun I made a 320-bit block cipher that uses SHA as the round
>function. I did the inputs to SHA as the first 160 bits as one half of
>the block and 352 bits of key material so it's really
>
>L = L xor SHA(R||K1)
>R = R xor SHA(L||K2)
>L = L xor SHA(R||K3)
>
>It runs at about 2.2mbyte/sec on my K6-2 (with the ref source code) and
>only requires 132 bytes of ram. It's sorta like what they talked about
>in the BEAR/LION paper except no stream cipher is involved.
>
>http://www.geocities.com/tomstdenis/tc7.c
>
>Tom
>
>
>Sent via Deja.com http://www.deja.com/
>Before you buy.
>
>
>
The key setup is a bit awkward. A better method is
L2= L1 xor SHA(R1||K1||C1)
R2=R1 xor SHA(L2||K1||C2)
L3=L2 xor SHA(R2||K1||C3)
where C1,C2, and C3 are constants. maybe strings of
digits from PI.
It is the basic Luby-Rackoff design.
This is reinventing the wheel but it is a sound design.
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: [EMAIL PROTECTED] (Mack)
Date: 23 Aug 2000 04:34:31 GMT
Subject: Re: SHA-2 name rumors
>Got a rumor that the new longer hashes will be named SHA-256, SHA-384, and
>SHA-512. Also, SHA-384 is supposed to be a truncation of SHA-512.
>Don Johnson
>
Any info on the structures?
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: [EMAIL PROTECTED] (Mack)
Date: 23 Aug 2000 04:37:11 GMT
Subject: Re: Re-using CD-R discs
>I don't think this will work, but they do taste great with a little soy
>sauce.
>
ack I am allergic to SOY!!!!
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: [EMAIL PROTECTED] (Mack)
Date: 23 Aug 2000 04:42:56 GMT
Subject: Re: SHA-1 program (cool!)
>STL wrote:
>> I've
>> gone over the algorithm as it's implemented a few times in my head, and I
>would
>> have thought that I could confidently say that after twenty revisions to
>> version 0.01 (the first "finished" version that gave a hash, albeit a very
>> corrupted one), the implementation is logically perfect and should cope
>with
>> all possible inputs under 4GB. Sadly, I just found that one exists,
>although I
>> have NO idea where it's coming from as it hasn't shown up either in the
>1M-"a"
>> vector or your 2MB file. I took the largest darn file I had on my hard
>drive,
>> a hulking behemoth called "pak0.pak" in the \valve\ directory of the game
>> Half-Life (weighing in at a crushing 302,907,835 bytes), and the reference
>I
>> use (HASHcipher demonstration by Bokler.com) output a different hash than
>my
>> SHA-1 program. Something is afoot, and I'm not sure exactly what it could
>be.
>
>It seems to me that you really pushed things to the limit by testing a 300
>MB file. If there is some way of showing that your program is good for files
>below a certain size, it would still be very useful for my purposes. So do
>we prove that, to a statistically acceptable level of certainty? Would you
>need to somehow run your program and a "gold standard" program with N random
>files and, if no differences are seen, compute the chances of there being a
>problem in your program with the Poisson distribution? Or is the code simple
>enough to inspect and attribute the 300 MB file "error" to something other
>than your code?
>
>NIST has some test vectors (beyond those in FIPS-180) that may be useful,
>though they like kind of hard to use:
>http://csrc.nist.gov/cryptval/shs/sha1-vectors.zip
>
>Ed Suominen
>Registered Patent Agent
>Web Site: http://eepatents.com
>PGP Public Key: http://eepatents.com/key
>
>
I would suggest trying it on a different compiler and/or library. May be a
problem with the library handling certain size files.
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: [EMAIL PROTECTED] (Mack)
Date: 23 Aug 2000 04:51:12 GMT
Subject: Re: Very Fast Decorrelated Cipher
>In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (Mack) wrote:
>> >Can someone help I think this is how the attack on five rounds goes..
>> >
>> >For any input diff (0,a) you use pairs of inputs such as (L,Ri) where
>> >Ri varies and L remains the same. Then the output is something like
>> >(b,a).
>>
>> yes ...
>>
>> given that you can construct a characteristic
>>
>> input r1 b,a
>> f 0,a
>> swap a,0
>> input r2 a,0
>> f a,0
>> swap 0,a
>> input r3 0,a
>> f b,a
>> swap a,b
>>
>> note that the probability of the three round characteristic is
>> p^2 where p is the probability of the one round characteristic.
>
>Well differential cryptanalysis is impossible against this cipher. I
>thought the impossible differential holds with a prob of 1?
>
Never say impossible. I haven't looked at it but even with 'perfect'
theory there may be a way of attacking it with differentials.
>> >
>> >With 2^32 possible inputs of the form (L,Ri) you can get about 2^31
>> >right pairs which would remove 2^31 keys right?
>>
>> That depends on the characteristic and the cipher.
>>
>> >
>> >Then you need todo this 2^32 more times before the key becomes
>apparent?
>>
>> no then you do a brute force search on the remaining keys. Or if the
>number of
>> keys is still too high you repeat using the same texts with a
>different
>> characteristic.
>
>Still you need about 2^32 plaintexts to reduce the keyspace by not even
>one bit, I think the six-round version is still ok.
>
If the attack only eliminates 2^32 keys. Differential attack is probabilistic
by nature. Without looking at the cipher in detail I can't really say.
>> >
>> >That means you need 2^63 chosen texts?
>> >
>>
>> for a 64 bit block cipher it is hoped that you need more than 2^64
>chosen
>> texts. ie. it can't be done.
>
>Tom
>
>
>Sent via Deja.com http://www.deja.com/
>Before you buy.
>
>
>
>
>
>
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: [EMAIL PROTECTED]
Subject: Chat Group
Date: Wed, 23 Aug 2000 04:50:02 GMT
Open anytime on EFnet room is "scicrypt".
I realize that people are on at diff times, so please just drop in
whenever.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: 320-bit Block Cipher
Date: Wed, 23 Aug 2000 05:14:56 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Mack) wrote:
> >For fun I made a 320-bit block cipher that uses SHA as the round
> >function. I did the inputs to SHA as the first 160 bits as one half
of
> >the block and 352 bits of key material so it's really
> >
> >L = L xor SHA(R||K1)
> >R = R xor SHA(L||K2)
> >L = L xor SHA(R||K3)
> >
> >It runs at about 2.2mbyte/sec on my K6-2 (with the ref source code)
and
> >only requires 132 bytes of ram. It's sorta like what they talked
about
> >in the BEAR/LION paper except no stream cipher is involved.
> >
> >http://www.geocities.com/tomstdenis/tc7.c
> >
> >Tom
> >
> >
> >Sent via Deja.com http://www.deja.com/
> >Before you buy.
> >
> >
> >
>
> The key setup is a bit awkward. A better method is
> L2= L1 xor SHA(R1||K1||C1)
> R2=R1 xor SHA(L2||K1||C2)
> L3=L2 xor SHA(R2||K1||C3)
>
> where C1,C2, and C3 are constants. maybe strings of
> digits from PI.
>
> It is the basic Luby-Rackoff design.
>
> This is reinventing the wheel but it is a sound design.
Good idea I could do that.
Normally I see something like that uses SHA to key a stream cipher...
this is slightly more like a MDC cipher.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Mack)
Date: 23 Aug 2000 05:29:08 GMT
Subject: Re: The DeCSS ruling and the big shots
A list of DeCSS mirrors is
available at
http://www.vexed.net/CSS/mirrors.html
Deja.com also has the
list tucked away in its files.
Of course I am probably breaking
the law by posting that link.
It is interesting to note that
CSS is totally insecure since
it includes the key with the
encrypted data.
Didn't someone criticize me
for suggesting that a OTP
was breakable if used twice
by saying that using it twice
was like posting the key with
the data?
Go figure.
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: [EMAIL PROTECTED] (S. T. L.)
Subject: Re: SHA-2 name rumors
Date: 23 Aug 2000 05:32:41 GMT
SHA-1 provides 160 bits; isn't that enough? Seems like it will be good for
decades to come.
-*---*-------
S.T.L. My Quotes Page * http://quote.cjb.net * leads to my NEW site.
My upgraded Book Reviews Page: * http://sciencebook.cjb.net *
Optimized pngcrush executable now on my Download page!
Long live pngcrush! :->
------------------------------
From: [EMAIL PROTECTED] (Mack)
Date: 23 Aug 2000 05:35:56 GMT
Subject: Re: Crypto Coprocessor on Javacard
>In article <[EMAIL PROTECTED]>,
>Shawn Willden <[EMAIL PROTECTED]> wrote:
>>[EMAIL PROTECTED] writes:
>>> I am interested to know if anyone has benchmarked Crypto Functions on a
>>> Javacard with and without a crypto processor on the card...
>>
>>> 3DES encryption
>>> 1024 RSA Key generation
>>> etc
>>
>>> What type of speed improvement factors does one get , with the crypto
>>> coprocessor.
>>
>>I don't know of any smart cards that have crypto coprocessors for DES
>>operations, just RSA, so that part of your question is unanswerable.
>
>GemPlus GPK4000 has DES and at least one mode of 3DES (2 keys, not three).
>And RSA up to 1024 bits. It's been around for at least three years.
>I don't remember the DES speed, other than "pretty slow".
>
>
>>Similarly, RSA is only done on cards with coprocessors, so there isn't
>>anything to compare. Most smart cards wouldn't even have enough RAM
>>to hold the numbers, requiring that intermediate results be written to
>>EEPROM (ugh!) if you tried to do RSA in software. Also, the
>>processors are just too slow even if they had enough RAM.
>>
>>FYI, key generation times on smart cards are measured in minutes, even
>>for 512-bit keys. Most smart card applications generate the keys
>>off-card and inject them.
>
>Also, most smartcards that have key generation have lousy RNGs.
>There's a pretty tight limit on the power consumption specd
>in 7816 (a common smartcard interface spec) and good RNGs
>take a lot of power compared to memory cells.
>
>> Private key operations (decryption and
>>signing) generally take on the order of 10 seconds, public key
>>operations (encryption and signature verification) take a second or
>>so.
>
>The GPK400 takes 1.4 seconds for verifying a 1024 bit RSA signature.
>
The assymetry in the times suggests that the GPK400 has not been corrected
for some of the more recent attacks on small public keys.
>--
> Eric Murray http://www.lne.com/ericm ericm at lne.com PGP keyid:E03F65E5
>Security consulting: secure protocols, security reviews, standards,
>smartcards.
>
>
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: New algorithm for the cipher contest
Date: Wed, 23 Aug 2000 05:28:25 GMT
In article <8nvddl$nrf$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (David A. Wagner) wrote:
> Fascinating. The round function is
> X_{i+1} := (X xor K_{i,0}) * K_{i,1} mod 2^64,
> and there are four rounds. That's it. Now that's simplicity.
>
> If the middle xor is changed to addition, then I _think_ there is a
> boomerang attack (unverified). But the xor destroys the boomerang.
>
> If you consider a three-round variant, I _think_ there is a similar
> boomerang (unverified). But four rounds seems to kill the attack.
>
> It's an appealingly-simple cipher. But can it really be secure?
> Very interesting...
>
I have concerns about the cipher security too.
I reduced the number of rounds based on statistical tests only. Risky
maybe.
Another risk is the multiplication (mod 2^64) that stagnates the result
lower bits. The bit-reversal function (Mirror) eliminate this effect in
two rounds only. Maybe this can be exploited, as pointed by Tom St
Denis.
The hole integer output start to be random at the 3rd round.
Interesting: you devised a last attack just at this round. Coincidence
only ?
I considered an algebraic solution but the bit-reversal troubled me,
since I couldn't find any simple algebraic equivalent for it.
I considered also a numerical (aproximate) solution using, for example,
Newton method on an equation system. Didn't try this yet, but I think
the iterations will hardly converge.
Thank you.
Alexis
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Anthony Stephen Szopa <[EMAIL PROTECTED]>
Subject: Re: The DeCSS ruling
Date: Tue, 22 Aug 2000 22:44:29 -0700
Jim Steuert wrote:
>
> I am horrified to learn about the DeCSS
> case. The judge has
> ruled in favor of the MPAA (Motion Picture
> Arts Association) and
> enjoined 2600 magazine from publishing the
> DeCSS code on it's web
> site.
>
> The judge apparently ruled that publishing
> keys to a bank
> vault, even if the publisher never intended
> to rob the bank,
> would force the bank to re-program it's
> vault. And that
> constitues illegal intent.
>
> Where I think the judge is mistaken is his
> lack of distinction
> between publishing the specific keys to a
> specific bank vault, versus
> reverse-engineering a publicly visible vault
> mechanism (software).
>
> Isn't what is discussed on this newsgroup
> equivalent to
> "vault mechanisms?". And if so, isn't
> publishing an attack on
> a commericially used encryption algorithm
> (DES certainly)
> illegal?
>
> Is anyone in this newgroup concerned about
> this ruling?
>
> -Jim Steuert
Who cares?
Well, I think the issue is: did you get your copy of DeCSS?
Let's see. Did I or didn't I?
I just can't remember.
Maybe you should get your copy.
I hear it shows up on the internet at random.
Is it true that the DeCSS program is exactly 58,376 bytes?
Oh, well. I don't really know.
What do I know?
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: New algorithm for the cipher contest
Date: Wed, 23 Aug 2000 05:39:36 GMT
In article <8nvndc$f11$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> In article <8nvddl$nrf$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (David A. Wagner) wrote:
> > Fascinating. The round function is
> > X_{i+1} := (X xor K_{i,0}) * K_{i,1} mod 2^64,
> > and there are four rounds. That's it. Now that's simplicity.
> >
> > If the middle xor is changed to addition, then I _think_ there is a
> > boomerang attack (unverified). But the xor destroys the boomerang.
> >
> > If you consider a three-round variant, I _think_ there is a similar
> > boomerang (unverified). But four rounds seems to kill the attack.
> >
> > It's an appealingly-simple cipher. But can it really be secure?
> > Very interesting...
> >
>
> I have concerns about the cipher security too.
Good.
> I reduced the number of rounds based on statistical tests only. Risky
> maybe.
>
> Another risk is the multiplication (mod 2^64) that stagnates the
result
> lower bits. The bit-reversal function (Mirror) eliminate this effect
in
> two rounds only. Maybe this can be exploited, as pointed by Tom St
> Denis.
>
> The hole integer output start to be random at the 3rd round.
> Interesting: you devised a last attack just at this round. Coincidence
> only ?
>
> I considered an algebraic solution but the bit-reversal troubled me,
> since I couldn't find any simple algebraic equivalent for it.
>
> I considered also a numerical (aproximate) solution using, for
example,
> Newton method on an equation system. Didn't try this yet, but I think
> the iterations will hardly converge.
Your bit reversal is an entirely linear process. Multiplication in Zn
is linear for the most part (minus the upper bits). I am sorry I can't
connect the two... I really don't have the cogniative ability (need
more brain power!).
Seems like a simple cipher, and after all simple is good.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Very Fast Decorrelated Cipher
Date: Wed, 23 Aug 2000 05:41:58 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Mack) wrote:
> >In article <[EMAIL PROTECTED]>,
> > [EMAIL PROTECTED] (Mack) wrote:
> >> >Can someone help I think this is how the attack on five rounds
goes..
> >> >
> >> >For any input diff (0,a) you use pairs of inputs such as (L,Ri)
where
> >> >Ri varies and L remains the same. Then the output is something
like
> >> >(b,a).
> >>
> >> yes ...
> >>
> >> given that you can construct a characteristic
> >>
> >> input r1 b,a
> >> f 0,a
> >> swap a,0
> >> input r2 a,0
> >> f a,0
> >> swap 0,a
> >> input r3 0,a
> >> f b,a
> >> swap a,b
> >>
> >> note that the probability of the three round characteristic is
> >> p^2 where p is the probability of the one round characteristic.
> >
> >Well differential cryptanalysis is impossible against this cipher. I
> >thought the impossible differential holds with a prob of 1?
> >
>
> Never say impossible. I haven't looked at it but even with 'perfect'
> theory there may be a way of attacking it with differentials.
It would be very hard because no specific difference will hold with a
given probability. Only a set of random differences which hold with a
prob of 1.
> >> >
> >> >With 2^32 possible inputs of the form (L,Ri) you can get about
2^31
> >> >right pairs which would remove 2^31 keys right?
> >>
> >> That depends on the characteristic and the cipher.
> >>
> >> >
> >> >Then you need todo this 2^32 more times before the key becomes
> >apparent?
> >>
> >> no then you do a brute force search on the remaining keys. Or if
the
> >number of
> >> keys is still too high you repeat using the same texts with a
> >different
> >> characteristic.
> >
> >Still you need about 2^32 plaintexts to reduce the keyspace by not
even
> >one bit, I think the six-round version is still ok.
> >
>
> If the attack only eliminates 2^32 keys. Differential attack is
probabilistic
> by nature. Without looking at the cipher in detail I can't really
say.
Well please comment when you have time.
Thanks,
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Comment from Hardware Experts Please
Date: 23 Aug 2000 05:54:06 GMT
[EMAIL PROTECTED] wrote:
>
>
>My question is about performming a hardware multiplication in GF(2^n)
>modulo an appropriate primitive polynomial. Sorry if my questions
>seems vague, I am not a hardware expert.
>
>Generally I have two questions:
>
>1. Can it be done with relatively low amounts of hardware. I.e
>cheaper unit. Low power as well.
>
>2. Can it be done with a relatively high output rate. Relative to
>what I am not sure, i.e can it be done quickly? Say something close to
>nlog n steps?
>
>I want to design a 128-bit block cipher using decorrelation in eight
>rounds, this requires a 64-bit GF multiply which is very costly in
>software. In hardware this cipher would require 1024 bits of SRAM but
>this could be fed into the unit any way (i.e fed into latches in the
>execution pipeline), and if the GF multiply is efficient in hardware
>then the cipher could be practical for real usage.
My first order estimation is that a good commercial DSP board would
give you something on the order of a 10X increase in speed. It will
cost a lot of money and use a lot of power, and would require a large
software development effort. It would likely be much cheaper to try
to get your program working on a Buewolf cluster.
I am very concerned aboout your "something close to nlog n steps"
comment. It shows a deep lack of knowledge of hardware/software
tradeoffs that I believe will not allow you to implement a hardware
solution. Going to hardware can only give you a fixed percenage
speedup. It takes an algorithm change to change 2^n to nlog n.
Hardware just does the same old thing faster.
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Re-using CD-R discs
Date: 23 Aug 2000 05:59:39 GMT
Sark <[EMAIL PROTECTED]> writes:
> I have heard some rumours about being able to erase CD-R discs by
> baking them in the oven. Someone said it was 220 degrees for 10 min. I
> tried it, but it didn't work. Any suggestions?
You are making a common error. You are trying to erase the CD-R
witbout rewinding it first. by doing this, the flat spots on the
photons don't line up, causing an optical logjam and spilling the
valiance electrons all over the floor.
I hope this helps.
------------------------------
** 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
******************************
