Cryptography-Digest Digest #369, Volume #14 Wed, 16 May 01 20:13:01 EDT
Contents:
Re: TC15 analysis ("Tom St Denis")
Re: PRNG question from newbie (David Wagner)
Re: PRNG question from newbie ("Roger Schlafly")
Re: taking your PC in for repair? WARNING: What will they find? (Ichinin)
Re: taking your PC in for repair? WARNING: What will they find? (P.Dulles)
Re: PRNG question from newbie ("Henrick Hellström")
Re: PRNG question from newbie (David Wagner)
Re: TC15 analysis ("Scott Fluhrer")
Re: TC15 analysis ("Scott Fluhrer")
Re: taking your PC in for repair? WARNING: What will they find? ("Omnivore")
Re: taking your PC in for repair? WARNING: What will they find? ("Omnivore")
Re: TC15 analysis ("Tom St Denis")
Re: PRNG question from newbie ("Paul Pires")
Re: PRNG question from newbie ("Roger Schlafly")
Re: How can I see the symmetric enncryption keysize in SSL? ("no_carrier")
Re: taking your PC in for repair? WARNING: What will they find? (SCOTT19U.ZIP_GUY)
----------------------------------------------------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: TC15 analysis
Date: Wed, 16 May 2001 21:54:06 GMT
"Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
news:9du4hf$5e1$[EMAIL PROTECTED]...
> In any case, it turns out there was a bug in my program -- I had the sbox
in
> backwards (which brings up an obvious question -- would the cipher
actually
> be stronger if you inverted the sbox? Probably not). When I fixed that,
it
> did find a one round differential at hamming weight 7 (with probability
> 2**-15). The differential at the beginning of a round is (in binary):
> 00000000000000000000010000010001
> 00000000000000000000001000010000
> 00000000000000000000000000000000
> 00000000000000000000001000001000
>
> The linear transform turns it into:
> 00000000000000000000000000000001
> 00000000000000000000000000011000
> 00000000000000000000001000011000
> 00000000000000000000010000001001
>
> And each of the 5 active sboxes has a 2**-3 probability of turning the
bits
> within its column back into the column settings of the original
> differential.
I finished an accelerated search and I think I can conclude there are no
usefull 1R differentials.
Any clues on how to make the LT better? I see in serpent they used logical
shifts, is that to avoid this cyclic behaviour?
Tom
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: PRNG question from newbie
Date: 16 May 2001 21:59:36 GMT
John Myre wrote:
>I think that's the deep question to address. How are the
>requirements for the output of a PRNG (stream cipher) and
>a hash function different?
The two concepts are *very* different. For instance, it is possible
to have a secure stream cipher that ignores the first bit of its key,
yet this would clearly make a very bad hash function. The security
requirements of a hash function seem to be much stronger than the security
requirements for stream ciphers.
------------------------------
From: "Roger Schlafly" <[EMAIL PROTECTED]>
Subject: Re: PRNG question from newbie
Date: Wed, 16 May 2001 20:39:05 GMT
"David Wagner" <[EMAIL PROTECTED]> wrote in message
news:9dut88$qgh$[EMAIL PROTECTED]...
> John Myre wrote:
> >I think that's the deep question to address. How are the
> >requirements for the output of a PRNG (stream cipher) and
> >a hash function different?
> The two concepts are *very* different. For instance, it is possible
> to have a secure stream cipher that ignores the first bit of its key,
> yet this would clearly make a very bad hash function. The security
> requirements of a hash function seem to be much stronger than the security
> requirements for stream ciphers.
OTOH, it is possible to have a secure hash function (in the sense that
it is one-way and collision-resistant) but where one bit of every output
byte is zero. But that would give a very poor stream cipher.
------------------------------
From: Ichinin <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Crossposted-To:
alt.privacy,alt.security.pgp,alt.security.scramdisk,alt.privacy.anon-server
Subject: Re: taking your PC in for repair? WARNING: What will they find?
Date: Tue, 15 May 2001 06:46:44 +0200
P.Dulles wrote:
<SNIP>
add
12. What does EE do to twart Proxies and remote monitoring software?
------------------------------
From: P.Dulles <*@*.com>
Crossposted-To:
alt.privacy,alt.security.pgp,alt.security.scramdisk,alt.privacy.anon-server
Subject: Re: taking your PC in for repair? WARNING: What will they find?
Date: Wed, 16 May 2001 18:35:19 -0400
Reply-To: *@*.com
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
>: P.Dulles wrote:
>: <SNIP>
>:
>: add
>:
>: 12. What does EE do to twart Proxies and remote monitoring software?
>:
Excellent point. But they won't answer. I also forgot to mention that
a trojan could also be installed on your system by your boss or the
police, and they can retrieve all files that way.
--
Loki
"Joan of Arc heard voices too!"
------------------------------
From: "Henrick Hellström" <[EMAIL PROTECTED]>
Subject: Re: PRNG question from newbie
Date: Thu, 17 May 2001 00:37:28 +0200
"Paul Pires" <[EMAIL PROTECTED]> skrev i meddelandet
news:HgBM6.32288$[EMAIL PROTECTED]...
> I'll make you a deal. I'll look at yours and comment if you'll
> do the same with mine :-)
Sure. Where can I find it?
--
Henrick Hellström [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: PRNG question from newbie
Date: 16 May 2001 22:50:56 GMT
Roger Schlafly wrote:
>OTOH, it is possible to have a secure hash function (in the sense that
>it is one-way and collision-resistant) but where one bit of every output
>byte is zero. But that would give a very poor stream cipher.
Yes, but usually when people say "secure hash function", they implicitly
assume far more than just one-wayness and collision-resistance. So I take
"secure hash function" to mean that it behaves like a random oracle, with
no structure whatsoever.
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: TC15 analysis
Date: Wed, 16 May 2001 15:31:38 -0700
Tom St Denis <[EMAIL PROTECTED]> wrote in message
news:2GCM6.112202$[EMAIL PROTECTED]...
>
> "Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
> news:9du4hf$5e1$[EMAIL PROTECTED]...
> > In any case, it turns out there was a bug in my program -- I had the
sbox
> in
> > backwards (which brings up an obvious question -- would the cipher
> actually
> > be stronger if you inverted the sbox? Probably not). When I fixed
that,
> it
> > did find a one round differential at hamming weight 7 (with probability
> > 2**-15). The differential at the beginning of a round is (in binary):
> > 00000000000000000000010000010001
> > 00000000000000000000001000010000
> > 00000000000000000000000000000000
> > 00000000000000000000001000001000
> >
> > The linear transform turns it into:
> > 00000000000000000000000000000001
> > 00000000000000000000000000011000
> > 00000000000000000000001000011000
> > 00000000000000000000010000001001
> >
> > And each of the 5 active sboxes has a 2**-3 probability of turning the
> bits
> > within its column back into the column settings of the original
> > differential.
>
> I finished an accelerated search and I think I can conclude there are no
> usefull 1R differentials.
>
> Any clues on how to make the LT better? I see in serpent they used
logical
> shifts, is that to avoid this cyclic behaviour?
I don't know enough about the design criteria of Serpent to have an opinion.
However, replacing the rotates with shifts in TC15 would have two negative
effects:
- It would decrease the amount of diffusion. Right now, the rotates is the
only diffusion you have between different bits of the sboxes, and if you
replace them with shifts, then a shift of N (either direction) will defuse N
fewer bits, because N of the bits will fall off the end of the shift
register
- It would increase the number of distinct differentials you have to worry
about. Every possible location within the word is then essentially
distinct, and hence it becomes more likely that there's a high probability
one (such as one that sticks on the right side, and relies on the fact that
shifts to the right do not extend the differential).
--
poncho
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: TC15 analysis
Date: Wed, 16 May 2001 15:25:25 -0700
Tom St Denis <[EMAIL PROTECTED]> wrote in message
news:W%BM6.111072$[EMAIL PROTECTED]...
>
> "Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
> news:9du4hf$5e1$[EMAIL PROTECTED]...
> >
> > Tom St Denis <[EMAIL PROTECTED]> wrote in message
> > news:sOiM6.101727$[EMAIL PROTECTED]...
> > >
> > > "Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
> > > news:9dsd5f$97b$[EMAIL PROTECTED]...
> > > >
> > > > Tom St Denis <[EMAIL PROTECTED]> wrote in message
> > > > news:s8gM6.100647$[EMAIL PROTECTED]...
> > > > >
> > > > > "Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
> > > > > news:9drhq3$vaa$[EMAIL PROTECTED]...
> > > > > >
> > > > > > Tom St Denis <[EMAIL PROTECTED]> wrote in message
> > > > > > news:4zeL6.76746$[EMAIL PROTECTED]...
> > > > > > > I started my analysis of TC15 (more than just poking). I am
> > looking
> > > > for
> > > > > > low
> > > > > > > hamming weight differentials (i.e low active sbox count).
> > > > > > I just verified that there are no single round iterative
> > differentials
> > > > (at
> > > > > > any probability level) with hamming weight 6 or less.
> > > > >
> > > > > May I ask *how* you analyzed it. That's more meaningful then just
> the
> > > > > results.
> > > >
> > > > Ok, I considered all possible differentials into the start of a
round
> > with
> > > > Hamming weight of 6 or less (well, 7 now, as my computer completed
> > > searching
> > > > over 7 since I last posted). Since the cipher is circularly
symmetric
> > as
> > > > far as differentials are concerned (rotating all the variables by
the
> > same
> > > > amount preserves the differential behavior), that reduced the search
> > > > somewhat. For each such differential, I computed how it would flow
> > > through
> > > > the linear transform, and then see if the sbox could possibly
> transform
> > > that
> > > > differential back to the original one (possibly circularly rotated).
> > >
> > > I dunno what you mean by "rotating all the variables by the same
amount
> > > pre...". my LT doesn't do a simple rotate...Maybe I am looking at it
> > > wrong...
> > TC5 consists of three different operations:
> > - Xoring in of key material
> > - Fixed 32 bit rotates
> > - 32-bit-wide xors/and/ors
> >
> > For all these three operations, if you take a differential input, and
> apply
> > a rotate of (say) 7 bits to the right, then the output differential will
> > also be rotated 7 bits to the right. And hence, the entire cipher has
the
> > property that if you have a differential (a,b,c,d) to (x,y,z,w) with
> > probability p, then you also have a differential
(a>>>7,b>>>7,c>>>7,d>>>7)
> > to (x>>>7,y>>>7,z>>>7,w>>>7) with probability p.
>
> This is true.
>
> >
> > Question for the student: this property does not hold for direct inputs:
> if
> > (a,b,c,d) encrypts to (x,y,z,w), then (a>>>7,b>>>7,c>>>7,d>>>7) might
not
> > encrypt to (x>>>7,y>>>7,z>>>7,w>>>7). Why not?
>
> Off hand I don't know, but I would have to say it's because the
> substitutions will replace the a,b,c,d with different values then
> a<<<7,b<<<7,etc... Also the key material will be diff at diff bit
rotations.
> You would have to rotate all the keys too?
>
> Am I remotely close?
Not with the substitions (which are rotationally symmetric), but yes,
because the keys remain fixed, rotating the inputs do not rotate the
outputs. Differentials do rotate, because they ignore the subkey mixing
step.
>
> >
> > >
> > > I have a relatively fast PC, maybe you could send me the source and I
> > might
> > > be able to learn from it/use it.
> > I won't bore the rest of the newsgroup with it -- I'll email it to you.
> >
> > >
> > > > > > My next step: two round iterative differentials...
> > > > >
> > > > > Ahh keen.
> > > > It'll be a lot of work. Likely, I won't be able to do anything
> > > > exhaustive -- some pruning will be required to keep it feasible.
> > > > >
> > > > > So you found 1R differentials with 7 active sboxes? That would be
> > > > 16*7=112
> > > > > active sboxes ... way over the 64 limit.
> > > > No -- at that point, my computer completed the search to that
extent,
> > and
> > > > I'm not working with "active sboxes", but input Hamming weight. It
> > still
> > > > hasn't found *any* 1R differentials. I found several differentials
> that
> > > > almost work -- it feels like there might be some simple reason why
> such
> > a
> > > > differential can't exist, but that reason escapes me so far.
> > >
> > > Well if you OR the four words together the hamming weight over
GF(2^32)
> is
> > > the number of active sboxes. So if you have a HW of 7 that means 7
> sboxes
> > > are active does it not? Or are you assuming differences occur in
> parallel
> > > bits?
> > No, a Hamming Weight of 7 means that there are 7 one's in the input
> > differential.
> >
> > In any case, it turns out there was a bug in my program -- I had the
sbox
> in
> > backwards (which brings up an obvious question -- would the cipher
> actually
> > be stronger if you inverted the sbox? Probably not). When I fixed
that,
> it
> > did find a one round differential at hamming weight 7 (with probability
> > 2**-15). The differential at the beginning of a round is (in binary):
> > 00000000000000000000010000010001
> > 00000000000000000000001000010000
> > 00000000000000000000000000000000
> > 00000000000000000000001000001000
> >
> > The linear transform turns it into:
> > 00000000000000000000000000000001
> > 00000000000000000000000000011000
> > 00000000000000000000001000011000
> > 00000000000000000000010000001001
> >
> > And each of the 5 active sboxes has a 2**-3 probability of turning the
> bits
> > within its column back into the column settings of the original
> > differential.
> >
> > Obviously, this particular differential is not really a concern against
> the
> > full cipher. However, given a full code book, the fact that this
> > differential really is 32 different differentials (by rotational
symmetry)
> > and the fact that the cipher doesn't avalanche all that well, I suspect
> that
> > this can be used to attack 10 or 11 rounds, by having the differential
go
> > through the first 8, and the last 2-3 rounds not quite covering up the
> > evidence well enough.
>
> That is not true. Let's say you found one pair called (a,b,c,d) and
> (a',b',c',d') such that they are a correct pair, then
> (a<<<7,b<<<7,c<<<7,d<<<7), etc... is not nessesarly a correct pair.
>
> > > May I ask what you think about the cipher so far? Good/bad?
> > Well, it is certainly elegant, and has no profoundly obvious weaknesses
> > (although the differential above cuts too close into the safety margin
for
> > me to be comfortable -- a few more rounds may be warrented). A quick
> cycle
> > count implies that it has a respectable, but not outstanding, speed in
> > software. However, the program should be shortish (the expanded key
> > schedule is too large to be called really short), and assuming the key
> setup
> > isn't too obnoxious, a hardware implementation would appear to take up
> > hardly any transistors at all.
>
> Hmm well I want to improve my LT to avoid all simple 1R differentials
> involving under 6 or so sboxes. Although if the best 1R diff has 5 sboxes
> then I still win since the prob is out of bounds... :-)
But the 4 sbox differential I mentioned elsewhere is right on the ragged
edge of being useful at 16 rounds. You will need to tweak the LT (or add
more rounds)
--
poncho
------------------------------
From: "Omnivore" <[EMAIL PROTECTED]>
Crossposted-To:
alt.privacy,alt.security.pgp,alt.security.scramdisk,alt.privacy.anon-server
Subject: Re: taking your PC in for repair? WARNING: What will they find?
Date: Wed, 16 May 2001 16:16:40 -0700
They may find Evidence Eliminator and alert the authorities that one bears
keeping an eye on.
------------------------------
From: "Omnivore" <[EMAIL PROTECTED]>
Crossposted-To:
alt.privacy,alt.security.pgp,alt.security.scramdisk,alt.privacy.anon-server
Subject: Re: taking your PC in for repair? WARNING: What will they find?
Date: Wed, 16 May 2001 16:17:47 -0700
Didn't you just say the exact same thing in another post?
I suppose a good lie bears repeating?
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: TC15 analysis
Date: Wed, 16 May 2001 23:17:37 GMT
"Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
news:9duvfe$pvp$[EMAIL PROTECTED]...
> > Off hand I don't know, but I would have to say it's because the
> > substitutions will replace the a,b,c,d with different values then
> > a<<<7,b<<<7,etc... Also the key material will be diff at diff bit
> rotations.
> > You would have to rotate all the keys too?
> >
> > Am I remotely close?
> Not with the substitions (which are rotationally symmetric), but yes,
> because the keys remain fixed, rotating the inputs do not rotate the
> outputs. Differentials do rotate, because they ignore the subkey mixing
> step.
I see this now. Thanks for pointing this out.
> > Hmm well I want to improve my LT to avoid all simple 1R differentials
> > involving under 6 or so sboxes. Although if the best 1R diff has 5
sboxes
> > then I still win since the prob is out of bounds... :-)
> But the 4 sbox differential I mentioned elsewhere is right on the ragged
> edge of being useful at 16 rounds. You will need to tweak the LT (or add
> more rounds)
Well you're best is p=2^-15 and I found several good ones at p=2^-12
Prob: 12
Turns into:
00000000000000000000000000000001
00001000000000000000000000000000
00000000000000000000001000000000
00000000000000000000000000000010
Original:
00001000000000000000000000000011
00001000000000000000001000000001
00001000000000000000000000000000
00000000000000000000000000000001
In fact I have done an exhaustive search of all 1R differentials with four
sboxes and this is among the best.
At 16 rounds this has a prob of 2^-192 of occuring which is fairly low. In
fact after 10 rounds the differentials probability is too low to be used. I
think the extra five rounds are a nice padding.
This says nothing about 2R and longer differentials though.
What is a good way to search for them? Over two rounds we have to make sure
no more than 7 sboxes are used (and the prob is highest)... but I am not
sure how to efficiently seek for them.
The 1R search program is at
http://tomstdenis.home.dhs.org/tc15_fd.c
Tom
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: PRNG question from newbie
Date: Wed, 16 May 2001 16:18:47 -0700
Henrick Hellström <[EMAIL PROTECTED]> wrote in message
news:9duvhs$dur$[EMAIL PROTECTED]...
> "Paul Pires" <[EMAIL PROTECTED]> skrev i meddelandet
> news:HgBM6.32288$[EMAIL PROTECTED]...
> > I'll make you a deal. I'll look at yours and comment if you'll
> > do the same with mine :-)
>
>
> Sure. Where can I find it?
Well, the brief description is right here in Sci.crypt.
Re: Comments appreciated. (Was, Bleaming Strock cipher)
I have a more comprehensive description in PDF
form I could send if you find it of interest. I looked
at your web reference. Do you have a PDF or text
version? I prefer to do my reading on the porch.
I'm old fasioned, reading off a screen just doesn't
work best for me.
>
>
> --
> Henrick Hellström [EMAIL PROTECTED]
> StreamSec HB http://www.streamsec.com
>
>
------------------------------
From: "Roger Schlafly" <[EMAIL PROTECTED]>
Subject: Re: PRNG question from newbie
Date: Wed, 16 May 2001 21:56:31 GMT
"David Wagner" <[EMAIL PROTECTED]> wrote in message
news:9dv08g$rbp$[EMAIL PROTECTED]...
> Roger Schlafly wrote:
> >OTOH, it is possible to have a secure hash function (in the sense that
> >it is one-way and collision-resistant) but where one bit of every output
> >byte is zero. But that would give a very poor stream cipher.
> Yes, but usually when people say "secure hash function", they implicitly
> assume far more than just one-wayness and collision-resistance. So I take
> "secure hash function" to mean that it behaves like a random oracle, with
> no structure whatsoever.
Aarrgh. IMO, people should use different terminology if that is what
they mean. The obvious meaning of "secure hash function" is that of
a hash function such that usage as a hash function is secure from known
attacks. Behaving like a random oracle is a very different and nebulous
thing.
------------------------------
From: "no_carrier" <[EMAIL PROTECTED]>
Subject: Re: How can I see the symmetric enncryption keysize in SSL?
Date: Thu, 17 May 2001 00:47:52 +0200
"Nathan Sherman" <[EMAIL PROTECTED]> ha scritto nel messaggio
news:3b02adf3$[EMAIL PROTECTED]...
>
> "no_carrier" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > When I visit a SSL secure site with InternetExplorer I can see the
> security certificate and I can
> > see the RSA keysize and the Hash algorythm used.
> > However I haven't found a way to see the size of the symmetric key used
> for the session, which is
> > very important too.
> >
> When I go to amazon.com and log in, I can click on File... Properties and I
> see "Connection: SSL 3.0, RC4 with 128 bit encryption (High);
Thank you sir,
this was what I was looking for.
> RSA with 1024
> bit exchange"
>
> If I hit Certificates... at the bottom of the tab and click on the Details
> tab, I see that the thumbprint algorithm is SHA-1 and the signature
> algorithm is MD5 RSA.
>
> What else do you need to know?
>
> X
>
>
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Crossposted-To:
alt.privacy,alt.security.pgp,alt.security.scramdisk,alt.privacy.anon-server
Subject: Re: taking your PC in for repair? WARNING: What will they find?
Date: 16 May 2001 23:28:37 GMT
[EMAIL PROTECTED] (Omnivore) wrote in
<9dv1o2$gqn$[EMAIL PROTECTED]>:
>They may find Evidence Eliminator and alert the authorities that one bears
>keeping an eye on.
>
>
Actually they could do far worse. Seeing your willing to part money
for this particular class of product. May mark you as an easy target
for related forms of SPAM so they may give your email address to the
SPAMMERS that actaully belive you might wish to part with more money.
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!
------------------------------
** 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
******************************
