Cryptography-Digest Digest #392, Volume #14 Sat, 19 May 01 20:13:00 EDT
Contents:
Re: TC15a cryptanalysis ("Scott Fluhrer")
Re: TC15a cryptanalysis ("Tom St Denis")
Re: TC15a cryptanalysis ("Tom St Denis")
Re: TC15a cryptanalysis ("Scott Fluhrer")
Re: TC15a cryptanalysis ("Tom St Denis")
Re: DES Encryption - salt? ("Andreas Born")
Re: PGP details (Andrew McDonald)
Re: TC15a cryptanalysis ("Scott Fluhrer")
Re: TC15a cryptanalysis ("Tom St Denis")
Re: Questionable security measures (Cloakware!) ("Henrick Hellstr�m")
Re: Questionable security measures (CIC and Cloakware!) ("Henrick Hellstr�m")
Re: TC15a cryptanalysis ("Scott Fluhrer")
Re: Questionable security measures (CIC and Cloakware!) ("John A. Malley")
Re: TC15a cryptanalysis ("Tom St Denis")
----------------------------------------------------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: TC15a cryptanalysis
Date: Sat, 19 May 2001 11:04:17 -0700
Tom St Denis <[EMAIL PROTECTED]> wrote in message
news:rEyN6.138225$[EMAIL PROTECTED]...
>
> "Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
> news:9e6cjg$mon$[EMAIL PROTECTED]...
> >
> > Tom St Denis <[EMAIL PROTECTED]> wrote in message
> > news:WlsN6.133704$[EMAIL PROTECTED]...
> > > Now that a few people have seen the TC15a source code, has anyone come
> up
> > > with a good attack method (ahem Scott Fluhrer ... you can speak up
> :-) ).
> > Well, one weakness is that it doesn't avalanche very well. In
particular,
> > after 7 rounds, these two weaknesses occur:
> >
> > - If you inject two texts with a one bit differential in bit 30 in A,
then
> > after 7 rounds, bit 0 of A will differ with probability 0.496
> >
> > - If you inject two texts with a one bit differential in bit 22 in B,
then
> > after 7 rounds, bit 0 of D will differ with probability 0.496
> >
> > The second can be used in an attack against the full cipher -- inject a
> > million plaintext pairs with a differential in bit 22 of B. Assume the
4
> > LSBits of the post-whitening key, and use that do decrypt the bit 0 of D
> > values, and look for above bias. That only gives you 4 bits of subkey,
> but
> > it isn't that difficult to do.
>
> Did you just do a SAC test? (i.e flip bit A and see often it flips bit
B)?
Yup.
> So should I check for new rotation values?
Either that, or add a few more rounds...
--
poncho
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: TC15a cryptanalysis
Date: Sat, 19 May 2001 18:26:01 GMT
"Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
news:9e6d9u$s67$[EMAIL PROTECTED]...
>
> Tom St Denis <[EMAIL PROTECTED]> wrote in message
> news:rEyN6.138225$[EMAIL PROTECTED]...
> >
> > "Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
> > news:9e6cjg$mon$[EMAIL PROTECTED]...
> > >
> > > Tom St Denis <[EMAIL PROTECTED]> wrote in message
> > > news:WlsN6.133704$[EMAIL PROTECTED]...
> > > > Now that a few people have seen the TC15a source code, has anyone
come
> > up
> > > > with a good attack method (ahem Scott Fluhrer ... you can speak up
> > :-) ).
> > > Well, one weakness is that it doesn't avalanche very well. In
> particular,
> > > after 7 rounds, these two weaknesses occur:
> > >
> > > - If you inject two texts with a one bit differential in bit 30 in A,
> then
> > > after 7 rounds, bit 0 of A will differ with probability 0.496
> > >
> > > - If you inject two texts with a one bit differential in bit 22 in B,
> then
> > > after 7 rounds, bit 0 of D will differ with probability 0.496
> > >
> > > The second can be used in an attack against the full cipher -- inject
a
> > > million plaintext pairs with a differential in bit 22 of B. Assume
the
> 4
> > > LSBits of the post-whitening key, and use that do decrypt the bit 0 of
D
> > > values, and look for above bias. That only gives you 4 bits of
subkey,
> > but
> > > it isn't that difficult to do.
> >
> > Did you just do a SAC test? (i.e flip bit A and see often it flips bit
> B)?
>
> Yup.
>
> > So should I check for new rotation values?
>
> Either that, or add a few more rounds...
Well I just wrote a SAC program and tested 7 rounds. The highest SAC biases
I got were
0 => 0, -188
0 => 2, -380
0 => 6, -462
0 => 19, 688
0 => 46, 718
1 => 58, -784
4 => 83, -836
7 => 12, 866
8 => 79, -878
26 => 90, 912
49 => 70, -1074
I note your difference 22 => 0, is not on the list. However, -1074 does
represent a bias... maybe because I only used 2^16 texts...
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: TC15a cryptanalysis
Date: Sat, 19 May 2001 18:36:32 GMT
"Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
news:9e6cjg$mon$[EMAIL PROTECTED]...
>
> Tom St Denis <[EMAIL PROTECTED]> wrote in message
> news:WlsN6.133704$[EMAIL PROTECTED]...
> > Now that a few people have seen the TC15a source code, has anyone come
up
> > with a good attack method (ahem Scott Fluhrer ... you can speak up
:-) ).
> Well, one weakness is that it doesn't avalanche very well. In particular,
> after 7 rounds, these two weaknesses occur:
>
> - If you inject two texts with a one bit differential in bit 30 in A, then
> after 7 rounds, bit 0 of A will differ with probability 0.496
>
> - If you inject two texts with a one bit differential in bit 22 in B, then
> after 7 rounds, bit 0 of D will differ with probability 0.496
I have failed to reproduce either of these over 2^20 randomly chosen
plaintexts. I did a full SAC test (well monte carlo style) and with 2^20
texts in one trial I came up with
0 => 0, -2078
0 => 7, 2166
0 => 24, 2318
0 => 41, -2400
0 => 98, -3084
4 => 3, -3828
13 => 102, -4236
58 => 0, -5134
89 => 0, -8292
89 => 3, -9386
Max bias is 0.4910488128662109375
Of course in subsequent runs with diff keys the biases appear elsewhere.
I don't think your attack is valid, sorry dude try again :-)
Tom
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: TC15a cryptanalysis
Date: Sat, 19 May 2001 11:52:44 -0700
Tom St Denis <[EMAIL PROTECTED]> wrote in message
news:ZUyN6.138384$[EMAIL PROTECTED]...
>
> "Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
> news:9e6d9u$s67$[EMAIL PROTECTED]...
> >
> > Tom St Denis <[EMAIL PROTECTED]> wrote in message
> > news:rEyN6.138225$[EMAIL PROTECTED]...
> > >
> > > "Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
> > > news:9e6cjg$mon$[EMAIL PROTECTED]...
> > > >
> > > > Tom St Denis <[EMAIL PROTECTED]> wrote in message
> > > > news:WlsN6.133704$[EMAIL PROTECTED]...
> > > > > Now that a few people have seen the TC15a source code, has anyone
> come
> > > up
> > > > > with a good attack method (ahem Scott Fluhrer ... you can speak up
> > > :-) ).
> > > > Well, one weakness is that it doesn't avalanche very well. In
> > particular,
> > > > after 7 rounds, these two weaknesses occur:
> > > >
> > > > - If you inject two texts with a one bit differential in bit 30 in
A,
> > then
> > > > after 7 rounds, bit 0 of A will differ with probability 0.496
> > > >
> > > > - If you inject two texts with a one bit differential in bit 22 in
B,
> > then
> > > > after 7 rounds, bit 0 of D will differ with probability 0.496
> > > >
> > > > The second can be used in an attack against the full cipher --
inject
> a
> > > > million plaintext pairs with a differential in bit 22 of B. Assume
> the
> > 4
> > > > LSBits of the post-whitening key, and use that do decrypt the bit 0
of
> D
> > > > values, and look for above bias. That only gives you 4 bits of
> subkey,
> > > but
> > > > it isn't that difficult to do.
> > >
> > > Did you just do a SAC test? (i.e flip bit A and see often it flips
bit
> > B)?
> >
> > Yup.
> >
> > > So should I check for new rotation values?
> >
> > Either that, or add a few more rounds...
>
> Well I just wrote a SAC program and tested 7 rounds. The highest SAC
biases
> I got were
>
> 0 => 0, -188
> 0 => 2, -380
> 0 => 6, -462
> 0 => 19, 688
> 0 => 46, 718
> 1 => 58, -784
> 4 => 83, -836
> 7 => 12, 866
> 8 => 79, -878
> 26 => 90, 912
> 49 => 70, -1074
>
> I note your difference 22 => 0, is not on the list. However, -1074 does
> represent a bias... maybe because I only used 2^16 texts...
Actually, remember, it's bit 22 of B to bit 0 of D. In any case, 2**16
texts should be on the ragged edge of detecting the bias, but random events
can be larger. Try a few more. I used 2**20.
>
> Tom
>
>
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: TC15a cryptanalysis
Date: Sat, 19 May 2001 19:31:53 GMT
"Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
news:9e6g4q$djs$[EMAIL PROTECTED]...
> > 0 => 0, -188
> > 0 => 2, -380
> > 0 => 6, -462
> > 0 => 19, 688
> > 0 => 46, 718
> > 1 => 58, -784
> > 4 => 83, -836
> > 7 => 12, 866
> > 8 => 79, -878
> > 26 => 90, 912
> > 49 => 70, -1074
> >
> > I note your difference 22 => 0, is not on the list. However, -1074 does
> > represent a bias... maybe because I only used 2^16 texts...
> Actually, remember, it's bit 22 of B to bit 0 of D. In any case, 2**16
> texts should be on the ragged edge of detecting the bias, but random
events
> can be larger. Try a few more. I used 2**20.
Either case neither of your differentials occur with the bias you say.
Tom
------------------------------
From: "Andreas Born" <[EMAIL PROTECTED]>
Subject: Re: DES Encryption - salt?
Date: Sat, 19 May 2001 22:25:43 +0200
Custerstoe <[EMAIL PROTECTED]> wrote:
> I placed a crypt3 source which should be compatible with unix here. it
> creates the key from the password and uses the salt:
> http://www.geocities.com/custerstoe.geo/crypt3.c
Thanks, it's the right thing! Helps me a lot.
Ciao,
Andreas
------------------------------
From: [EMAIL PROTECTED] (Andrew McDonald)
Subject: Re: PGP details
Date: Sat, 19 May 2001 20:22:21 GMT
On 18 May 2001 11:35:37 -0700,
Gregory G Rose <[EMAIL PROTECTED]> wrote:
>
> I'm a power PGP user and I'm unaware of a way to
> change the default cipher through any UI. The real
> question is whether that default is in the signed
> part of the packet or not, and if it is, it would
> effectively require getting all the signatures to
> be done again. I wouldn't be surprised if it *is*
> in the signed part (but I haven't checked). So, my
> guess is no, you can't do it.
It can be done (not very nicely though) with gnupg.
The preferences are in the signed part of the packet.
Basically, the first step is to edit the source (not difficult, just
a few lines in the keygen_add_std_prefs function in keygen.c) so that
the hard coded cipher preference list matches what you want. If the
default (currently - in order of preference - Rijndael, Twofish,
CAST5, Blowfish plus an implied 3DES) is ok, you can miss this step.
Then (using your newly compiled version of gnupg), go into the
edit-key menu. Change your key's expiry date, save and exit. Go back
into the edit-key menu, reset the expiry date, save and exit. (This
generates a new self-signature on the key).
A bit nasty, but not too difficult, and it works.
--
Andrew McDonald
[EMAIL PROTECTED]
http://www.mcdonald.org.uk/andrew/
OpenPGP DSA/ElG 1024/2048 3EDE 0FBC 6138 DCA0 FC8E C508 FCBB A9C8 F2DE ED36
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: TC15a cryptanalysis
Date: Sat, 19 May 2001 13:59:45 -0700
Tom St Denis <[EMAIL PROTECTED]> wrote in message
news:Q2zN6.138438$[EMAIL PROTECTED]...
>
> "Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
> news:9e6cjg$mon$[EMAIL PROTECTED]...
> >
> > Tom St Denis <[EMAIL PROTECTED]> wrote in message
> > news:WlsN6.133704$[EMAIL PROTECTED]...
> > > Now that a few people have seen the TC15a source code, has anyone come
> up
> > > with a good attack method (ahem Scott Fluhrer ... you can speak up
> :-) ).
> > Well, one weakness is that it doesn't avalanche very well. In
particular,
> > after 7 rounds, these two weaknesses occur:
> >
> > - If you inject two texts with a one bit differential in bit 30 in A,
then
> > after 7 rounds, bit 0 of A will differ with probability 0.496
> >
> > - If you inject two texts with a one bit differential in bit 22 in B,
then
> > after 7 rounds, bit 0 of D will differ with probability 0.496
>
> I have failed to reproduce either of these over 2^20 randomly chosen
> plaintexts. I did a full SAC test (well monte carlo style) and with 2^20
> texts in one trial I came up with
>
> 0 => 0, -2078
> 0 => 7, 2166
> 0 => 24, 2318
> 0 => 41, -2400
> 0 => 98, -3084
> 4 => 3, -3828
> 13 => 102, -4236
> 58 => 0, -5134
> 89 => 0, -8292
> 89 => 3, -9386
> Max bias is 0.4910488128662109375
>
> Of course in subsequent runs with diff keys the biases appear elsewhere.
>
> I don't think your attack is valid, sorry dude try again :-)
Actually, that bias is quite strong enough (and actually a bit stronger than
what my expirements showed) -- if 89 => 0 means "bit 25 of C to bit 0 of A",
then the attacker can inject a 2**16 or so pairs with a differential in bit
25 of C, and then assume that 2 lsbits of the postwhitening key, and decrypt
the last round for the bias. That'll give him 8 bits of postwhitening key,
and then he can use 89=>3 in a similar manner to pick up 12 more bits. With
20 bits of postwhitening, I suspect he can peel back enough of the last
round to start attacking the next-to-last round subkeys...
--
poncho
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: TC15a cryptanalysis
Date: Sat, 19 May 2001 21:28:51 GMT
"Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
news:9e6niv$vel$[EMAIL PROTECTED]...
>
> Tom St Denis <[EMAIL PROTECTED]> wrote in message
> news:Q2zN6.138438$[EMAIL PROTECTED]...
> >
> > "Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
> > news:9e6cjg$mon$[EMAIL PROTECTED]...
> > >
> > > Tom St Denis <[EMAIL PROTECTED]> wrote in message
> > > news:WlsN6.133704$[EMAIL PROTECTED]...
> > > > Now that a few people have seen the TC15a source code, has anyone
come
> > up
> > > > with a good attack method (ahem Scott Fluhrer ... you can speak up
> > :-) ).
> > > Well, one weakness is that it doesn't avalanche very well. In
> particular,
> > > after 7 rounds, these two weaknesses occur:
> > >
> > > - If you inject two texts with a one bit differential in bit 30 in A,
> then
> > > after 7 rounds, bit 0 of A will differ with probability 0.496
> > >
> > > - If you inject two texts with a one bit differential in bit 22 in B,
> then
> > > after 7 rounds, bit 0 of D will differ with probability 0.496
> >
> > I have failed to reproduce either of these over 2^20 randomly chosen
> > plaintexts. I did a full SAC test (well monte carlo style) and with
2^20
> > texts in one trial I came up with
> >
> > 0 => 0, -2078
> > 0 => 7, 2166
> > 0 => 24, 2318
> > 0 => 41, -2400
> > 0 => 98, -3084
> > 4 => 3, -3828
> > 13 => 102, -4236
> > 58 => 0, -5134
> > 89 => 0, -8292
> > 89 => 3, -9386
> > Max bias is 0.4910488128662109375
> >
> > Of course in subsequent runs with diff keys the biases appear elsewhere.
> >
> > I don't think your attack is valid, sorry dude try again :-)
> Actually, that bias is quite strong enough (and actually a bit stronger
than
> what my expirements showed) -- if 89 => 0 means "bit 25 of C to bit 0 of
A",
> then the attacker can inject a 2**16 or so pairs with a differential in
bit
> 25 of C, and then assume that 2 lsbits of the postwhitening key, and
decrypt
> the last round for the bias. That'll give him 8 bits of postwhitening
key,
> and then he can use 89=>3 in a similar manner to pick up 12 more bits.
With
> 20 bits of postwhitening, I suspect he can peel back enough of the last
> round to start attacking the next-to-last round subkeys...
This is true, but not useful. I could take Twofish and get the same
results. The problem is I only did 2^20 texts with a single random key.
There will be a slight bias in that since the sample space is small. Not
only that but the diff 89 => 0 doesn't hold for all keys and all pairs with
the same prob.
It's like looking at a 1cm^2 window of space from earth and saying "all
space looks like this". The window is much too small.
Unless you're observed bias exists for all keys it's not really useful.
Tom
------------------------------
From: "Henrick Hellstr�m" <[EMAIL PROTECTED]>
Subject: Re: Questionable security measures (Cloakware!)
Date: Sun, 20 May 2001 00:34:54 +0200
"John Savard" <[EMAIL PROTECTED]> skrev i meddelandet
news:[EMAIL PROTECTED]...
> Are there any Windows languages where a *text file* generates a
> program complete with dialog boxes, no graphical resource editor
> required, and which are handled by compilers made by more than one
> company (which lets out FoxPro and Clarion, that come close)? I don't
> think so, but maybe Smalltalk - or even Cobol, for all I know -
> qualifies.
I'm not sure I see the problem.
Why shouldn't you be able to do that in C? Source files are usually plain
text files, and you only need a couple of hundred calls to ComCtl32.dll to
set up a decent, basic GUI.
--
Henrick Hellstr�m [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
------------------------------
From: "Henrick Hellstr�m" <[EMAIL PROTECTED]>
Subject: Re: Questionable security measures (CIC and Cloakware!)
Date: Sun, 20 May 2001 00:47:09 +0200
"Tom St Denis" <[EMAIL PROTECTED]> skrev i meddelandet
news:HReN6.127805$[EMAIL PROTECTED]...
>
> "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > "I fought the Law, and the Law won"
> > - What song was that?
>
> I've heard of it but I can't remember the name
Some group feat. Mick Jones (The Clash), I think the title is "bank robber".
Correct me if I'm wrong.
--
Henrick Hellstr�m [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: TC15a cryptanalysis
Date: Sat, 19 May 2001 16:09:29 -0700
Tom St Denis <[EMAIL PROTECTED]> wrote in message
news:nABN6.138695$[EMAIL PROTECTED]...
>
> "Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
> news:9e6niv$vel$[EMAIL PROTECTED]...
> >
> > Tom St Denis <[EMAIL PROTECTED]> wrote in message
> > news:Q2zN6.138438$[EMAIL PROTECTED]...
> > >
> > > "Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
> > > news:9e6cjg$mon$[EMAIL PROTECTED]...
> > > >
> > > > Tom St Denis <[EMAIL PROTECTED]> wrote in message
> > > > news:WlsN6.133704$[EMAIL PROTECTED]...
> > > > > Now that a few people have seen the TC15a source code, has anyone
> come
> > > up
> > > > > with a good attack method (ahem Scott Fluhrer ... you can speak up
> > > :-) ).
> > > > Well, one weakness is that it doesn't avalanche very well. In
> > particular,
> > > > after 7 rounds, these two weaknesses occur:
> > > >
> > > > - If you inject two texts with a one bit differential in bit 30 in
A,
> > then
> > > > after 7 rounds, bit 0 of A will differ with probability 0.496
> > > >
> > > > - If you inject two texts with a one bit differential in bit 22 in
B,
> > then
> > > > after 7 rounds, bit 0 of D will differ with probability 0.496
> > >
> > > I have failed to reproduce either of these over 2^20 randomly chosen
> > > plaintexts. I did a full SAC test (well monte carlo style) and with
> 2^20
> > > texts in one trial I came up with
> > >
> > > 0 => 0, -2078
> > > 0 => 7, 2166
> > > 0 => 24, 2318
> > > 0 => 41, -2400
> > > 0 => 98, -3084
> > > 4 => 3, -3828
> > > 13 => 102, -4236
> > > 58 => 0, -5134
> > > 89 => 0, -8292
> > > 89 => 3, -9386
> > > Max bias is 0.4910488128662109375
> > >
> > > Of course in subsequent runs with diff keys the biases appear
elsewhere.
> > >
> > > I don't think your attack is valid, sorry dude try again :-)
> > Actually, that bias is quite strong enough (and actually a bit stronger
> than
> > what my expirements showed) -- if 89 => 0 means "bit 25 of C to bit 0 of
> A",
> > then the attacker can inject a 2**16 or so pairs with a differential in
> bit
> > 25 of C, and then assume that 2 lsbits of the postwhitening key, and
> decrypt
> > the last round for the bias. That'll give him 8 bits of postwhitening
> key,
> > and then he can use 89=>3 in a similar manner to pick up 12 more bits.
> With
> > 20 bits of postwhitening, I suspect he can peel back enough of the last
> > round to start attacking the next-to-last round subkeys...
>
> This is true, but not useful. I could take Twofish and get the same
> results.
Actually, such a result with Twofish would be *very* interesting (read:
publishable)
> The problem is I only did 2^20 texts with a single random key.
> There will be a slight bias in that since the sample space is small. Not
> only that but the diff 89 => 0 doesn't hold for all keys and all pairs
with
> the same prob.
Actually, the sample space is large enough that we know it's not the source
of the bias. If you submit 2^{20} pairs of texts to a random function,
you'd expect to see about (0.5 +- \epsilon) * 2^{20} agreements on an output
bit, for \epsilon around 2^{-10}. You found a bias about 10 times larger,
which will (almost) never happen "by random chance" (the probability is
somewhat less than the probability that someone guessing a random 128 bit
key right on the first attempt).
As for using a single key, well, we've established (at best) that the key is
"weak". Since you presumably picked the key arbitrarily, it brings up the
question about what percentage of keys are similarly "weak".
>
> It's like looking at a 1cm^2 window of space from earth and saying "all
> space looks like this". The window is much too small.
>
> Unless you're observed bias exists for all keys it's not really useful.
Actually, it doesn't have to exist for all keys, it only has to exist for a
nontrivial subset for it to be a serious weakness.
Actually, during my tests, I averaged over 100 different sets of random
subkeys. In addition, because of the structure of TC15A, I'd expect the
same sort of biases to exist essentially independent of the keys -- all you
do with the subkeys is xor them into the block periodically, and if we use
random starting blocks, xoring in unknown random subkeys should have little
effect, at least to a first approximation. Of course, if you've observed
that different keys do behave differently, then ignore that argument.
--
poncho
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Questionable security measures (CIC and Cloakware!)
Date: Sat, 19 May 2001 16:23:17 -0700
"Henrick Hellstr�m" wrote:
>
> "Tom St Denis" <[EMAIL PROTECTED]> skrev i meddelandet
> news:HReN6.127805$[EMAIL PROTECTED]...
> >
> > "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote in message
> > news:[EMAIL PROTECTED]...
> > > "I fought the Law, and the Law won"
> > > - What song was that?
> >
> > I've heard of it but I can't remember the name
>
> Some group feat. Mick Jones (The Clash), I think the title is "bank robber".
> Correct me if I'm wrong.
The Bobby Fuller Four released "I FOUGHT THE LAW" in 1966.
See http://www.tsimon.com/fuller.htm
Lyrics at
http://www.execpc.com/~suden/fought_law.html
The Clash released their own version in 1979 (in the US) on their album
"The Clash."
See http://londonsburning.org/alb_clash_us.html
John A. Malley
[EMAIL PROTECTED]
P.S. My favorite Clash single: THIS IS RADIO CLASH - Lyrics at
http://londonsburning.org/lyr_complete_lyrics_09.html#ThisisRadi
Second favorite: KNOW YOUR RIGHTS - (such musical satire!) Lyrics at
http://londonsburning.org/lyr_combat_rock.html#KnowYourRi
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: TC15a cryptanalysis
Date: Sat, 19 May 2001 23:30:00 GMT
"Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
news:9e6v68$tqj$[EMAIL PROTECTED]...
>
> Tom St Denis <[EMAIL PROTECTED]> wrote in message
> news:nABN6.138695$[EMAIL PROTECTED]...
> >
> > "Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
> > news:9e6niv$vel$[EMAIL PROTECTED]...
> > >
> > > Tom St Denis <[EMAIL PROTECTED]> wrote in message
> > > news:Q2zN6.138438$[EMAIL PROTECTED]...
> > > >
> > > > "Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
> > > > news:9e6cjg$mon$[EMAIL PROTECTED]...
> > > > >
> > > > > Tom St Denis <[EMAIL PROTECTED]> wrote in message
> > > > > news:WlsN6.133704$[EMAIL PROTECTED]...
> > > > > > Now that a few people have seen the TC15a source code, has
anyone
> > come
> > > > up
> > > > > > with a good attack method (ahem Scott Fluhrer ... you can speak
up
> > > > :-) ).
> > > > > Well, one weakness is that it doesn't avalanche very well. In
> > > particular,
> > > > > after 7 rounds, these two weaknesses occur:
> > > > >
> > > > > - If you inject two texts with a one bit differential in bit 30 in
> A,
> > > then
> > > > > after 7 rounds, bit 0 of A will differ with probability 0.496
> > > > >
> > > > > - If you inject two texts with a one bit differential in bit 22 in
> B,
> > > then
> > > > > after 7 rounds, bit 0 of D will differ with probability 0.496
> > > >
> > > > I have failed to reproduce either of these over 2^20 randomly chosen
> > > > plaintexts. I did a full SAC test (well monte carlo style) and with
> > 2^20
> > > > texts in one trial I came up with
> > > >
> > > > 0 => 0, -2078
> > > > 0 => 7, 2166
> > > > 0 => 24, 2318
> > > > 0 => 41, -2400
> > > > 0 => 98, -3084
> > > > 4 => 3, -3828
> > > > 13 => 102, -4236
> > > > 58 => 0, -5134
> > > > 89 => 0, -8292
> > > > 89 => 3, -9386
> > > > Max bias is 0.4910488128662109375
> > > >
> > > > Of course in subsequent runs with diff keys the biases appear
> elsewhere.
> > > >
> > > > I don't think your attack is valid, sorry dude try again :-)
> > > Actually, that bias is quite strong enough (and actually a bit
stronger
> > than
> > > what my expirements showed) -- if 89 => 0 means "bit 25 of C to bit 0
of
> > A",
> > > then the attacker can inject a 2**16 or so pairs with a differential
in
> > bit
> > > 25 of C, and then assume that 2 lsbits of the postwhitening key, and
> > decrypt
> > > the last round for the bias. That'll give him 8 bits of postwhitening
> > key,
> > > and then he can use 89=>3 in a similar manner to pick up 12 more bits.
> > With
> > > 20 bits of postwhitening, I suspect he can peel back enough of the
last
> > > round to start attacking the next-to-last round subkeys...
> >
> > This is true, but not useful. I could take Twofish and get the same
> > results.
> Actually, such a result with Twofish would be *very* interesting (read:
> publishable)
>
> > The problem is I only did 2^20 texts with a single random key.
> > There will be a slight bias in that since the sample space is small.
Not
> > only that but the diff 89 => 0 doesn't hold for all keys and all pairs
> with
> > the same prob.
> Actually, the sample space is large enough that we know it's not the
source
> of the bias. If you submit 2^{20} pairs of texts to a random function,
> you'd expect to see about (0.5 +- \epsilon) * 2^{20} agreements on an
output
> bit, for \epsilon around 2^{-10}. You found a bias about 10 times larger,
> which will (almost) never happen "by random chance" (the probability is
> somewhat less than the probability that someone guessing a random 128 bit
> key right on the first attempt).
>
> As for using a single key, well, we've established (at best) that the key
is
> "weak". Since you presumably picked the key arbitrarily, it brings up the
> question about what percentage of keys are similarly "weak".
>
> >
> > It's like looking at a 1cm^2 window of space from earth and saying "all
> > space looks like this". The window is much too small.
> >
> > Unless you're observed bias exists for all keys it's not really useful.
> Actually, it doesn't have to exist for all keys, it only has to exist for
a
> nontrivial subset for it to be a serious weakness.
True.
>
> Actually, during my tests, I averaged over 100 different sets of random
> subkeys. In addition, because of the structure of TC15A, I'd expect the
> same sort of biases to exist essentially independent of the keys -- all
you
> do with the subkeys is xor them into the block periodically, and if we use
> random starting blocks, xoring in unknown random subkeys should have
little
> effect, at least to a first approximation. Of course, if you've observed
> that different keys do behave differently, then ignore that argument.
I agree my point is that I think the window is too small to get a good idea
of a useful bias. If you could show mathematically why the bias works that
would be more useful.
Tonight I will perform a larger test of 2^24 texts and see if the bias
holds.
Tom
------------------------------
** 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
******************************
