Cryptography-Digest Digest #342, Volume #14 Sat, 12 May 01 13:13:00 EDT
Contents:
Comparison of Diff. Cryptanalysis countermeasures ([EMAIL PROTECTED])
Re: Comparison of Diff. Cryptanalysis countermeasures ("Tom St Denis")
Re: Is Differential Cryptanalysis practical? ([EMAIL PROTECTED])
Re: Comparison of Diff. Cryptanalysis countermeasures (SCOTT19U.ZIP_GUY)
Re: Is Differential Cryptanalysis practical? ("Tom St Denis")
Re: Comparison of Diff. Cryptanalysis countermeasures ([EMAIL PROTECTED])
Re: Comparison of Diff. Cryptanalysis countermeasures ("Tom St Denis")
Re: Is Differential Cryptanalysis practical? ("Scott Fluhrer")
Re: Comparison of Diff. Cryptanalysis countermeasures ([EMAIL PROTECTED])
Re: Comparison of Diff. Cryptanalysis countermeasures ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Comparison of Diff. Cryptanalysis countermeasures
Date: Sat, 12 May 2001 05:53:19 -0800
I've been through a couple of papers on diff. cryptanalysis and secure
S-box
generation. I've also looked at a decorrelation paper that Tom St. Denis
mentioned (although at this point I really don't understand it, but I'm
working on it).
There appear to be two commonly used methods for diff. cryptanal.
hardening
for block ciphers:
1. Carefully design the S-boxes. This seems to come down
to trying to obtain the flattest difference distribution
possible while minimizing the non-zero entries in the
first column of the diff. distribution table. I haven't
fully figured out how this is done but I understand
why this is done.
2. Use decorrelation which can offer "provable resistance"
to diff. attacks.
Another paper which I ran across decribed using a PRNG
to generate S-boxes (something like 8 x 8 boxes) by seeding from key
bits. Supposedly, the probability
of getting a bad S-box for m=8 is low and since diff. cryptanal. assumes
that
the S-box contents are known, it should be very difficult to use diff.
cryptanal.
Would someone care to compare the effectiveness of these three methods?
Are
there other methods?
My guess is that for method 1, some kind of design tradeoff is going to
take
place and the S-box design will be optimized EITHER for this or that,
but not
both. The attacker, knowing the S-box contents, would choose the most
appropriate
attack. I can't venture a guess on method 2 since I don't understand it
yet. My
worry about method 3 would be getting bad S-boxes from certain keys, but
I guess the PRNG seed could be constrained. Another problem with method
3
is that the S-boxes won't be optimized against diff. cryptanal. but I
don't
see how that matters if the analyst has to know the S-box contents in
order
to apply diff. cryptanal.
veb3
5/12/01
=====BEGIN PGP MESSAGE=====
Version: PGP 6.5.8
pCxibgtG9gGHw3oOaZIu0w6iUz27izdTRvp0EdNSrMJ8La93oiygo6+eQtU4Tw==
=IZJ2
=====END PGP MESSAGE=====
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Comparison of Diff. Cryptanalysis countermeasures
Date: Sat, 12 May 2001 15:07:13 GMT
<[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
>
>
> I've been through a couple of papers on diff. cryptanalysis and secure
> S-box
> generation. I've also looked at a decorrelation paper that Tom St. Denis
> mentioned (although at this point I really don't understand it, but I'm
> working on it).
>
> There appear to be two commonly used methods for diff. cryptanal.
> hardening
> for block ciphers:
>
> 1. Carefully design the S-boxes. This seems to come down
> to trying to obtain the flattest difference distribution
> possible while minimizing the non-zero entries in the
> first column of the diff. distribution table. I haven't
> fully figured out how this is done but I understand
> why this is done.
That's only for surjective sboxes. In bijective sboxes the first column is
always zero (ignore the prob 1 in the top corner). A flat profile does not
ensure security (see the attacks on LOKI).
> 2. Use decorrelation which can offer "provable resistance"
> to diff. attacks.
Ah it's not provable resistance it's quantifiable resistance. Depends on
how well decorrelated the function is. In the case of GF(2^W) it's perfect
but slow and can't be used as a plugin (see COCONUT98).
> Another paper which I ran across decribed using a PRNG
> to generate S-boxes (something like 8 x 8 boxes) by seeding from key
> bits. Supposedly, the probability
> of getting a bad S-box for m=8 is low and since diff. cryptanal. assumes
> that
> the S-box contents are known, it should be very difficult to use diff.
> cryptanal.
I did some analysis on this a while back. For 8x8's the average DP max was
16/256 and the LP max was 36/256. It's easy to find 8x8's with 8/256 and
32/256 respectively so random ones are not that good.
Tom
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Is Differential Cryptanalysis practical?
Date: Sat, 12 May 2001 06:36:36 -0800
Tom St Denis wrote:
>
> > Tom St Denis wrote:
>
> Yes you're right in this case it is not plausiable. A cipher is described
> as broken if
>
> "It can be detistinguished from a random permutation faster than sieving the
> entire codebook"
>
> This entails differential/linear distiniguishers that can be used to solve
> for keys or just tell it from random.
>
> For example, you can tell Blowfish from random with alot of texts but not
> what the key is. In this sense Blowfish is broken.
>
> Designers of new ciphers try to make ciphers that resist known attacks and
> are thus unbroken.
>
> Tom
I found the FEAL cryptanalysis paper you mentioned. That break appears
to be very practical.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Comparison of Diff. Cryptanalysis countermeasures
Date: 12 May 2001 15:26:04 GMT
[EMAIL PROTECTED] wrote in <[EMAIL PROTECTED]>:
>
>
>I've been through a couple of papers on diff. cryptanalysis and secure
>S-box
>generation. I've also looked at a decorrelation paper that Tom St. Denis
>mentioned (although at this point I really don't understand it, but I'm
>working on it).
>
>There appear to be two commonly used methods for diff. cryptanal.
>hardening
>for block ciphers:
>
> 1. Carefully design the S-boxes. This seems to come down
> to trying to obtain the flattest difference distribution
> possible while minimizing the non-zero entries in the
> first column of the diff. distribution table. I haven't
> fully figured out how this is done but I understand
> why this is done.
>
> 2. Use decorrelation which can offer "provable resistance"
> to diff. attacks.
>
>Another paper which I ran across decribed using a PRNG
>to generate S-boxes (something like 8 x 8 boxes) by seeding from key
>bits. Supposedly, the probability
>of getting a bad S-box for m=8 is low and since diff. cryptanal. assumes
>that
>the S-box contents are known, it should be very difficult to use diff.
>cryptanal.
>
>Would someone care to compare the effectiveness of these three methods?
>Are
>there other methods?
>
Yes there are other methods. But I feel one has to look at
how the S-box is being used before one worries a whole lot how the
S-box is created. With a single 8X8 sbox that is key dependent
you don't have a very large key space. So the problem is if you
pick S-boxes that are totally secure you have a smaller class to
pick from. And attacker need only try those in that small class.
One way the way I choose was to use a bigger S-box like 16X16
or 19X19. And then made the key selelct from a very large class
of S-boxes. I choose S-boxes so that any single cycle permutaion
would be allowed. Then tested what the output characteristics
of the simplest weakest single cycle S-boxes were used. Namely
sequential ones like a = a +1. Very simple but not very likeely
and then exaimed the ouputs of different types of files using
DIEHARD. Of course if you pick any small subset of S-boxes it would
then it would be easy to break. But in reality no matter what you
pick every key could be considered weak in the sense that an attacker
need only check for that key.
That also why you should encrypt in a totally bijective manner
so that any key tested may appear to the attacker as a possible real
key.
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: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Is Differential Cryptanalysis practical?
Date: Sat, 12 May 2001 15:41:27 GMT
<[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Tom St Denis wrote:
> >
>
> > > Tom St Denis wrote:
> >
> > Yes you're right in this case it is not plausiable. A cipher is
described
> > as broken if
> >
> > "It can be detistinguished from a random permutation faster than sieving
the
> > entire codebook"
> >
> > This entails differential/linear distiniguishers that can be used to
solve
> > for keys or just tell it from random.
> >
> > For example, you can tell Blowfish from random with alot of texts but
not
> > what the key is. In this sense Blowfish is broken.
> >
> > Designers of new ciphers try to make ciphers that resist known attacks
and
> > are thus unbroken.
> >
> > Tom
>
> I found the FEAL cryptanalysis paper you mentioned. That break appears
> to be very practical.
Yup. Personally I think the designers of FEAL were none to smart. Sure diff
analysis was not really known but "a+b" as a secure transform? Common :-)
Tom
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Comparison of Diff. Cryptanalysis countermeasures
Date: Sat, 12 May 2001 06:52:34 -0800
Tom St Denis wrote:
>
> That's only for surjective sboxes. In bijective sboxes the first column is
> always zero (ignore the prob 1 in the top corner). A flat profile does not
> ensure security (see the attacks on LOKI).
Column or row? In the few diff. distros I've seen the first row is all
zeros (expected since there is no input diff) except for the first entry
(again expected since zero input diff yields zero output diff). The
non-zero entries in the first column indicate zero output diffs for
non-zero input diffs. I haven't seen the LOKI attack yet (I'll grab
the paper on it) but I imagine that even though the diff. distro is
flat there are a lot of non-zero entries in the distro table's first
column.
>
> > 2. Use decorrelation which can offer "provable resistance"
> > to diff. attacks.
>
> Ah it's not provable resistance it's quantifiable resistance. Depends on
> how well decorrelated the function is. In the case of GF(2^W) it's perfect
> but slow and can't be used as a plugin (see COCONUT98).
>
> > Another paper which I ran across decribed using a PRNG
> > to generate S-boxes (something like 8 x 8 boxes) by seeding from key
> > bits. Supposedly, the probability
> > of getting a bad S-box for m=8 is low and since diff. cryptanal. assumes
> > that
> > the S-box contents are known, it should be very difficult to use diff.
> > cryptanal.
>
> I did some analysis on this a while back. For 8x8's the average DP max was
> 16/256 and the LP max was 36/256. It's easy to find 8x8's with 8/256 and
> 32/256 respectively so random ones are not that good.
But wouldn't this method be resistant to differential cryptanalysis even
with not-so-optimal S-boxes? The cryptanalyst would suspect that the
S-boxes were weak, but how would he exploit it without knowing the S-box
contents? How would he choose his plaintext pairs? How would he
determine
round chars? He could look at input and output diffs of the entire
cipher,
but how would that help? I think the PRNG would have to be attacked
first,
i.e. try to determine how the PRNG was seeded by looking at input and
output diffs of the entire cipher, which sounds pretty hard.
> Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Comparison of Diff. Cryptanalysis countermeasures
Date: Sat, 12 May 2001 16:07:12 GMT
<[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Tom St Denis wrote:
> >
>
> > That's only for surjective sboxes. In bijective sboxes the first column
is
> > always zero (ignore the prob 1 in the top corner). A flat profile does
not
> > ensure security (see the attacks on LOKI).
>
> Column or row? In the few diff. distros I've seen the first row is all
> zeros (expected since there is no input diff) except for the first entry
> (again expected since zero input diff yields zero output diff). The
> non-zero entries in the first column indicate zero output diffs for
> non-zero input diffs. I haven't seen the LOKI attack yet (I'll grab
> the paper on it) but I imagine that even though the diff. distro is
> flat there are a lot of non-zero entries in the distro table's first
> column.
In a typical bijective function you will have an xor pair table like
16 0 0 0 0 0 ...
0 2 4 2 0 2 ...
0 ....
0....
0....
In LOKI's case I think it was the fact that D=>0 can occur, I am not sure
off hand... I recall it had something todo with the flatness.
> > > 2. Use decorrelation which can offer "provable resistance"
> > > to diff. attacks.
> >
> > Ah it's not provable resistance it's quantifiable resistance. Depends
on
> > how well decorrelated the function is. In the case of GF(2^W) it's
perfect
> > but slow and can't be used as a plugin (see COCONUT98).
> >
> > > Another paper which I ran across decribed using a PRNG
> > > to generate S-boxes (something like 8 x 8 boxes) by seeding from key
> > > bits. Supposedly, the probability
> > > of getting a bad S-box for m=8 is low and since diff. cryptanal.
assumes
> > > that
> > > the S-box contents are known, it should be very difficult to use diff.
> > > cryptanal.
> >
> > I did some analysis on this a while back. For 8x8's the average DP max
was
> > 16/256 and the LP max was 36/256. It's easy to find 8x8's with 8/256
and
> > 32/256 respectively so random ones are not that good.
>
> But wouldn't this method be resistant to differential cryptanalysis even
> with not-so-optimal S-boxes? The cryptanalyst would suspect that the
> S-boxes were weak, but how would he exploit it without knowing the S-box
> contents? How would he choose his plaintext pairs? How would he
> determine
> round chars? He could look at input and output diffs of the entire
> cipher,
> but how would that help? I think the PRNG would have to be attacked
> first,
> i.e. try to determine how the PRNG was seeded by looking at input and
> output diffs of the entire cipher, which sounds pretty hard.
Ah perhaps. It depends on how the sboxes are used. Try proposing a new DES
using such random sboxes :-)
Tom
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Is Differential Cryptanalysis practical?
Date: Sat, 12 May 2001 08:59:59 -0700
Tom St Denis <[EMAIL PROTECTED]> wrote in message
news:HQcL6.75067$[EMAIL PROTECTED]...
>
> <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> > Tom St Denis wrote:
> > >
> >
> > > > Tom St Denis wrote:
> > >
> > > Yes you're right in this case it is not plausiable. A cipher is
> described
> > > as broken if
> > >
> > > "It can be detistinguished from a random permutation faster than
sieving
> the
> > > entire codebook"
> > >
> > > This entails differential/linear distiniguishers that can be used to
> solve
> > > for keys or just tell it from random.
> > >
> > > For example, you can tell Blowfish from random with alot of texts but
> not
> > > what the key is. In this sense Blowfish is broken.
> > >
> > > Designers of new ciphers try to make ciphers that resist known attacks
> and
> > > are thus unbroken.
> > >
> > > Tom
> >
> > I found the FEAL cryptanalysis paper you mentioned. That break appears
> > to be very practical.
>
> Yup. Personally I think the designers of FEAL were none to smart. Sure
diff
> analysis was not really known but "a+b" as a secure transform? Common :-)
Tom, now be kind to the poor designers of FEAL. Yeah, their designed turned
out to be somewhat, errr, suboptimal. However, remember how many of your
designs have been broken in the past.
--
poncho
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Comparison of Diff. Cryptanalysis countermeasures
Date: Sat, 12 May 2001 08:02:09 -0800
Tom St Denis wrote:
> > >
> > > > Another paper which I ran across decribed using a PRNG
> > > > to generate S-boxes (something like 8 x 8 boxes) by seeding from key
> > > > bits. Supposedly, the probability
>
> Ah perhaps. It depends on how the sboxes are used. Try proposing a new DES
> using such random sboxes :-)
>
> Tom
I smell booby-trap. We were talking about 8 x 8 boxes, not
6x4's remember?
Changes in the DES S-boxes greatly weaken that particular algorithm.
[Biham91]
But I think you are still assuming that you know the contents of the
S-boxes, yes?
Is diff. cryptanalysis possible on 16 rounds without knowing the
S-box contents even though the boxes are weak?
Differential analysis assumes that you know the contents of the S-boxes.
If diff. analysis _requires_ knowledge of the S-boxes, then it seems to
me that the way to harden a cipher against diff. cryptanalysis is to
deny the cryptanalyst knowledge of the boxes' contents.
=====BEGIN PGP MESSAGE=====
Version: PGP 6.5.8
pCxibgtG9gGHw3oOaZIu0w6iUz27izdTRvp0EdNSrMJ8La93oiygo6+eQtU4Tw==
=IZJ2
=====END PGP MESSAGE=====
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Comparison of Diff. Cryptanalysis countermeasures
Date: Sat, 12 May 2001 08:14:22 -0800
"SCOTT19U.ZIP_GUY" wrote:
> >
>
> Yes there are other methods. But I feel one has to look at
> how the S-box is being used before one worries a whole lot how the
> S-box is created. With a single 8X8 sbox that is key dependent
> you don't have a very large key space. So the problem is if you
> pick S-boxes that are totally secure you have a smaller class to
> pick from. And attacker need only try those in that small class.
> One way the way I choose was to use a bigger S-box like 16X16
> or 19X19. And then made the key selelct from a very large class
> of S-boxes. I choose S-boxes so that any single cycle permutaion
> would be allowed. Then tested what the output characteristics
> of the simplest weakest single cycle S-boxes were used. Namely
> sequential ones like a = a +1. Very simple but not very likeely
> and then exaimed the ouputs of different types of files using
> DIEHARD. Of course if you pick any small subset of S-boxes it would
> then it would be easy to break. But in reality no matter what you
> pick every key could be considered weak in the sense that an attacker
> need only check for that key.
> That also why you should encrypt in a totally bijective manner
> so that any key tested may appear to the attacker as a possible real
> key.
>
>
> David A. Scott
This brings up a related question that's been bothering me. I've studied
how redundancy in language allows the cryptanalyst to determine if a
randomly chosen decryption key is correct because keys that give
meaningless decryptions can be eliminated. The probability of obtaining
a meaningful message with a randomly chosen decryption key is small, so
if a meaningful message is obtained, the decryption key used is almost
certainly the right key.
I'm not sure how this applies to a digital system, esp. a block cipher.
Is there any redundancy, i.e. are there "meaningless" 64-bit values
(for a 64-bit block cipher) and if so how does the cryptanalyst
distinguish meaningless values from meaningful values? For ASCII it
should be fairly easy, but not everything is ASCII.
Redundancy pops up in several equations (unicity distance, for example)
so it's an important concept, but I'm not sure what redundancy in
a digital system really is.
How can one tell that a 64-bit block is "meaningful" or "meaningless"?
=====BEGIN PGP MESSAGE=====
Version: PGP 6.5.8
pCxibgtG9gGHw3oOaZIu0w6iUz27izdTRvp0EdNSrMJ8La93oiygo6+eQtU4Tw==
=IZJ2
=====END PGP MESSAGE=====
------------------------------
** 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
******************************
