Cryptography-Digest Digest #349, Volume #14 Sun, 13 May 01 19:13:00 EDT
Contents:
Re: DES Crypto Myth?? (David Wagner)
Re: Comparison of Diff. Cryptanalysis countermeasures (David Wagner)
Re: Comparison of Diff. Cryptanalysis countermeasures ("Tom St Denis")
Re: DES Crypto Myth?? ("Roger Schlafly")
Re: Secure 'talk'? (Mark Wooding)
Re: wide-trail (Mark Wooding)
Re: Secure 'talk'? ("Tom St Denis")
Re: wide-trail ("Tom St Denis")
How to break a NoeKeon variant ("Tom St Denis")
Re: DES Crypto Myth?? (Bill Unruh)
Re: Secure 'talk'? ("Harris Georgiou")
Re: DES Crypto Myth?? (SCOTT19U.ZIP_GUY)
Finding similar modulus to N^x Mod M? (Ichinin)
Re: ON-topic - UK crime statistics (was Re: Best, Strongest Algorithm) (Jim D)
Re: Micali-Schnorr pseudorandom bit generator ("Dobs")
Re: Key escrow based on BBS (Bryan Olson)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: DES Crypto Myth??
Date: 13 May 2001 17:19:43 GMT
>So why do you think the NSA changed the S-boxes, given that the IBM team
>had already optimized (s-boxes/cipher - take your pick) against
>differential cryptanalysis?
It's not clear that it happened this way.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Comparison of Diff. Cryptanalysis countermeasures
Date: 13 May 2001 17:20:45 GMT
>Are the key-dependent S-boxes generally constrained (to try to eliminate
>weak boxes)?
No.
>What is your opinion on the OP ? Would you tend to go with carefully
>optimized S-boxes or key-dependent boxes?
I don't know what OP is, but I'm a co-designer of Twofish, where
we used key-dependent S-boxes. Our philosophy on this is explained
in the AES submission.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Comparison of Diff. Cryptanalysis countermeasures
Date: Sun, 13 May 2001 17:28:41 GMT
"David Wagner" <[EMAIL PROTECTED]> wrote in message
news:9dmfpd$ebe$[EMAIL PROTECTED]...
> >Are the key-dependent S-boxes generally constrained (to try to eliminate
> >weak boxes)?
>
> No.
>
> >What is your opinion on the OP ? Would you tend to go with carefully
> >optimized S-boxes or key-dependent boxes?
>
> I don't know what OP is, but I'm a co-designer of Twofish, where
> we used key-dependent S-boxes. Our philosophy on this is explained
> in the AES submission.
OP is original poster. There are simpler ways to make key dependent sboxes
than those of Twofish.... :-)
Tom
------------------------------
From: "Roger Schlafly" <[EMAIL PROTECTED]>
Subject: Re: DES Crypto Myth??
Date: Sun, 13 May 2001 16:07:18 GMT
"Sam Simpson" <[EMAIL PROTECTED]> wrote
> Don's right: According to Levy's book Crypto (best account of DES
> development that I've seen), the IBM researchers developed an attack
against
> some SBoxes called the "T attack" (rediscovered as the Differential
Attack)
> so they then proposed SBoxes that were resistant to this attack.
> This is one of the reasons that IBM were prevented from disclosing the
> design principles of DES: the NSA didn't want details of the T Attack
(which
> they had discovered previously!) to be published.
> I think it's interesting to note that the differential attack was
discovered
> and published publicly in 1994, was found by IBM 20 years previously and
was
> known to the NSA prior to that.
Perhaps Levy just repeated the myth. The attack published in 1994
was an attack on the full 16-round DES. AFAIK, the DES team
has never claimed that they knew of any such attack. Supposedly,
some of them even urged that DES be only 8 rounds, because they
thought that 8 rounds would be sufficiently secure.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Secure 'talk'?
Date: 13 May 2001 16:50:12 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
> "mutable" technically means "able to be silenced".
No. It means `able to be changed', from the Latin muto, -are, -avi,
-atum, meaning `I change'.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: wide-trail
Date: 13 May 2001 17:15:00 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
> What does it mean? I have heard it said before. Does it mean something
> like a SPN where the diffusion is maximized?
More or less.
I believe it was first introduced in Joan Daemen's thesis `Cipher and
Hash Design', in chapter 5, `Propagation and Correlation'. In his
words:
: An S-box of a specific ruond is said to be /active/ with respect to a
: linear trail if its output selection vector is nonzero for that linear
: trail. It is said to be active with respect to a differential trail
: if its input difference vector is nonzero for that differential
: trail. Now, for both linear and differential trails it can be seen
: that the weight of a trail is the sum o the active S-boxes.
:
: This suggests two possible mechanisms of eliminating low-weight
: trails:
:
: * Choose S-boxes with difference propagations that have high
: restriction weight and with input-output correlations that have
: high correlation weight.
:
: * Design the round transformation in such a way that only trails with
: many S-boxes occur.
:
: The wide trail strategy emphasizes the second mechanism.
-- [mdw]
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Secure 'talk'?
Date: Sun, 13 May 2001 18:00:34 GMT
"Mark Wooding" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> > "mutable" technically means "able to be silenced".
>
> No. It means `able to be changed', from the Latin muto, -are, -avi,
> -atum, meaning `I change'.
I was kidding... :-)
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: wide-trail
Date: Sun, 13 May 2001 18:04:31 GMT
"Mark Wooding" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Tom St Denis <[EMAIL PROTECTED]> wrote:
>
> > What does it mean? I have heard it said before. Does it mean something
> > like a SPN where the diffusion is maximized?
>
> More or less.
>
> I believe it was first introduced in Joan Daemen's thesis `Cipher and
> Hash Design', in chapter 5, `Propagation and Correlation'. In his
> words:
>
> : An S-box of a specific ruond is said to be /active/ with respect to a
> : linear trail if its output selection vector is nonzero for that linear
> : trail. It is said to be active with respect to a differential trail
> : if its input difference vector is nonzero for that differential
> : trail. Now, for both linear and differential trails it can be seen
> : that the weight of a trail is the sum o the active S-boxes.
> :
> : This suggests two possible mechanisms of eliminating low-weight
> : trails:
> :
> : * Choose S-boxes with difference propagations that have high
> : restriction weight and with input-output correlations that have
> : high correlation weight.
> :
> : * Design the round transformation in such a way that only trails with
> : many S-boxes occur.
> :
> : The wide trail strategy emphasizes the second mechanism.
Thanks alot for this info.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: How to break a NoeKeon variant
Date: Sun, 13 May 2001 18:17:02 GMT
I realised my original attack doesn't make sense. The differences must
remain on the same words (i.e element of A[0..3]). So here is the attack.
Let's suppose a new sbox is used with a DP and LP max (same as the original)
of 4/16, however a new entry in the xor-pair table is found... namely
Pr[1=>1] = Pr[4=>4] = 4/16
Where the # means a bit # ... so.. a diff in bit one leads to a single diff
in bit one with a prob of 4/16...
This is how the attack goes.
You pick a pair of texts such that both a[0] and a[2] differ in the same bit
position (i.e let's say the lsb)
PI1 will move the bits around but since the diff remains with the same word
we don't care. Also since the rotates are diff the two single bit diffs are
not in the same sbox.
PI2 will line up the diffs again.
Theta will have a zero diff with prob 1 since the diffs line up. [is this
correct? I dunno off hand...]
Shazam. The prob per round is (4/16)^2 thus for 16 rounds this requires
2*(4/16)^-32 or 2^65 texts.
Could someone verify this is correct? This doesn't break Noekeon since
there are not any good Pr[x=>x] in the xor-pair table (save for one...)
--
Tom St Denis
---
http://tomstdenis.home.dhs.org
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: DES Crypto Myth??
Date: 13 May 2001 18:56:53 GMT
In <ocsL6.883$[EMAIL PROTECTED]> "Sam Simpson"
<[EMAIL PROTECTED]> writes:
...
>I think it's interesting to note that the differential attack was discovered
>and published publicly in 1994, was found by IBM 20 years previously and was
>known to the NSA prior to that.
>Is the public crypto community generally 20 years behind the NSA's
>abilities? Who can tell..........
Remember at the time the public crypto community was tiny. What was the
prupose in working on public crypto? There was no call for it. The
situation is very different now. A large public crypto community has
grown up, and the public interest is probably as high as the secret
community interest. Furthermore, the realisation that crypto needs to be
public and widely known and analysed is a very recent phenomenon. One
getas a huge boost from many people looking at a problem, and talking to
each other. NSA on the other hand is a highly secret organisation even
amongst themselves. Remember that the indication are that RSA was only 1
or 2 years behind the secret community, and equivalent crypto may well
now be ahead of the secret establishment.
------------------------------
From: "Harris Georgiou" <[EMAIL PROTECTED]>
Subject: Re: Secure 'talk'?
Date: Sun, 13 May 2001 23:10:41 +0300
The term "mutable", I think fits the description: the keys are not picked up
by the user on each round, they rather "mutate" in a random way as the
session continues.
The reason I took a second look in this program comes in part from what I
've read in the "Best, Strongest Algorithm" thread regarding polymorphic
encryption techniques. As for the program itself, I know for a fact that
it's secrecy level is low in any case, but (as always) it does not mean that
it cannot be useful for simple applications - after all, the artillery still
uses 3-letter permutation encryption on voice comms for pinpointing the
target's location just before the shot (no one can do anything by hand in a
few seconds...).
--
Harris
- 'Malo e lelei ki he pongipongi!'
Ï Tom St Denis <[EMAIL PROTECTED]> Ýãñáøå óôï ìÞíõìá óõæÞôçóçò:
W3uL6.83489$[EMAIL PROTECTED]
>
> "Harris Georgiou" <[EMAIL PROTECTED]> wrote in message
> news:9dll62$26vb$[EMAIL PROTECTED]...
> >
> > Ï Paul Rubin <[EMAIL PROTECTED]> Ýãñáøå óôï ìÞíõìá óõæÞôçóçò:
> > [EMAIL PROTECTED]
> > > "Harris Georgiou" <[EMAIL PROTECTED]> writes:
> > > > Given the key size (64-bit) and the mutable keys/functions, the
> question
> > is
> > > > how easy it is for someone to tap into the session and recover all
> > plaintext
> > > > message traffic (after some trials)?...
> > > >
> > > > PS: Random function is of standard form: X(n+1)=[a*X(n)+c]mod[m] and
> > > > en/decryption functions are all binary (combinations of 64-bit ROLs,
> > XORs,
> > >
> > > It sounds like this encryption scheme is no good and I wouldn't trust
> > > its security for anything except very casual attackers. Replace it
> > > with good cryptography and you'll have something. But why not use an
> > > existing program, like ytalk?
> >
> > Never mind that, I'm just thinking how "casual" this attacker would be
and
> > how "trivial" should any successful attack be. After all, why not use a
> > trully secure networking layer like VPN (PGP) or SSL? I cannot think of
an
> > easy way to discover the initial key from just a few ciphertexts, not
> while
> > the key is 64-bit and mutable. Any ideas?
>
> That's not entirely scientific. "mutable" technically means "able to be
> silenced".
>
> Just randomly inventing your own algorithm is a "bad idea (tm)".
>
> Tom
>
>
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: DES Crypto Myth??
Date: 13 May 2001 19:36:39 GMT
[EMAIL PROTECTED] (Sam Simpson) wrote in
<ocsL6.883$[EMAIL PROTECTED]>:
>Don's right: According to Levy's book Crypto (best account of DES
>development that I've seen), the IBM researchers developed an attack
>against some SBoxes called the "T attack" (rediscovered as the
>Differential Attack) so they then proposed SBoxes that were resistant to
>this attack.
>
>This is one of the reasons that IBM were prevented from disclosing the
>design principles of DES: the NSA didn't want details of the T Attack
>(which they had discovered previously!) to be published.
>
>I think it's interesting to note that the differential attack was
>discovered and published publicly in 1994, was found by IBM 20 years
>previously and was known to the NSA prior to that.
>
>Is the public crypto community generally 20 years behind the NSA's
>abilities? Who can tell..........
>
>--
I think the crypto comunity is generally 20 ears ahead of anything
in the public. But a thought has occured to me. Look at the FBI
when my mom was in it. It was an honorable honest arm of the
govenment. Know the FBI is a joke. I am not sure how many even
belive the continuing changing story on Waco. I also saw the
navy going down the tubes. I'm sure many people wondered if Bill
was working for America or the Red Chinese. It quite possible
Bill screwed up the NSA as bad as any other agency invovled with
defense. It may be that only politically correct back stabing
kiss asses are all that is left in the NSA so maybe the future
of breaking codes will be more in trying to force people to follow
laws when they outlaw crypto.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged or
something..
No I'm not paranoid. You all think I'm paranoid, don't you!
------------------------------
From: Ichinin <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Crossposted-To: sci.math
Subject: Finding similar modulus to N^x Mod M?
Date: Sat, 12 May 2001 23:20:46 +0200
Hi.
is there a paper somewhere regarding finding 2
or more similar exponents to:
Secret = N^x Modulo M
say;
S1 = N^48617237613265 Modulo M
S2 = N^87162387168695117851 Modulo M
S3 = N^17812834782376187214313 Modulo M
so that
S1 == S2 == S3
_OR_
Q: is it possible to automatically deduce the a similar
modulus by calculating it from the given values, hence
getting the frequency of how often a similarly modulus
occur?
An example:
x = 2^1766 Mod 1999
x is 1657.
Other exponents that also share 1657 are:
101, 434, 767, 1100, 1433, 1766
2099, 2432, 2765, 3098, 3431 (...)
We take a quick peak and we deduce the frequency
(333) by subtraction:
434-101=333
767-434=333
1100-767=333
...
So for the Exponent (2) and the Modulus (1999);
the frequency is 333. So when we find the first
similar modulus (101) i know that we can step up
by 333, and not miss anything (hence reducing the
workload by 8,3(+) bits for ANY exponent used with
these values).
Another example:
N = 2
M = 81726137
secret Exponent = 815312
Exponent Modulo M = 69536232
----------------------------
Frequency = 1316460 =20(+) bits
I've also noticed that this frequency seem to
increase for larger modulus (not always though.)
TIA,
Ichinin
------------------------------
From: [EMAIL PROTECTED] (Jim D)
Subject: Re: ON-topic - UK crime statistics (was Re: Best, Strongest Algorithm)
Date: Sun, 13 May 2001 20:59:06 GMT
Reply-To: Jim D
On 12 May 2001 19:48:12 GMT, [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
wrote:
>Jim D (Jim D) wrote in <[EMAIL PROTECTED]>:
>
>>On 11 May 2001 17:37:34 GMT, [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
>>wrote:
>>> Hell when I was a kid
>>>I took a gun to school. My NRA safety class required you to bring
>>>your own 22. Now adays people shit in there pants when a kid takes
>>>a gun to school. The view is different because the liberals have
>>>fucked it up and destroyed values.
>>
>>Isn't America a wonderful place? ! Rather you than me, pal!
>>
>
> Well it still can be a wonderful place is long is the liberals
>don't force communsium on us.
A little bit of communism would be the best thing that ever
happened to Yankee-Doodle land.
>At least we still have part of our
>freedoms in place. But they are slipping away. I hope that if
>you like the current UK government so much.
I don't!
>Maybe when Clinton
>gets knighted you folks can elect him to run your country.
>And then maybe what he has done to us he can do to you.
Well, at least we elect our leaders. A country which allows a
moron like George Dubya Bush to sieze power deserves all it gets.
Looks like you could use something else - Use of the English
Language lessons, perhaps....
--
______________________________________________
Posted by Jim D.
Nole me vocari, ego te vocabo.
jim @sideband.fsnet.co.uk
dynastic @cwcom.net
______________________________________________
------------------------------
From: "Dobs" <[EMAIL PROTECTED]>
Subject: Re: Micali-Schnorr pseudorandom bit generator
Date: Sun, 13 May 2001 23:34:01 +0200
U¿ytkownik Tom St Denis <[EMAIL PROTECTED]> w wiadomo¶ci do grup
dyskusyjnych napisa³:8jaL6.73187$[EMAIL PROTECTED]
>
> "Dobs" <[EMAIL PROTECTED]> wrote in message news:9djb5s$ohr$[EMAIL PROTECTED]...
> > >
> > > If your modulus is n bits long, then you should be outputing at most
> > > log2(n) of the least significant bits of Yi. For a 1024 bit modulus,
> > > you should not be outputing more than log2(1024) or 10 bits at a time.
> > >
> > > Where did you get the idea that you could use 341 bits?
> >
> > I took this algorithm from the 'Handbook of Applied Cryptography' by
> Menezes
> > In this algorithm (5.37) it is written that the output will be
> concatenation
> > of Z1||z2||...||zl
> > and Zi is the k least significant bits of Yi and k is always rather
> big
> > depending ofcourse on bithlength of n
> >
>
> I read it too. It must be wrong because I can't see anyone giving out
that
> many bits of the internal state and not getting zapped. Also it requires
> your base to be rather large so I can't see it being faster than say BBS.
>
> Tom
So if it is wrong algorithm for Micali-Schnorr generator can somebody write
for me the correct one?
Thanks
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Key escrow based on BBS
Date: Sun, 13 May 2001 15:59:19 -0700
Tom St Denis wrote:
>
> I was wondering after all the Key Escrow debackle in the mid 90s has anyone
> suggested this trivial solution?
There is the more trivial yet more general solution of
encrypting each message or session key under the public key
of the escrow authority.
A good (from a technical point of view) scheme for mandatory
key escrow will have other important properties that these
trivial schemes lack. In particular, one should be able to
tell from the message and public information (and assuming
no other channels) that the escrow authority can recover the
same message as the recipient.
--Bryan
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
