Cryptography-Digest Digest #850, Volume #11 Wed, 24 May 00 07:13:01 EDT
Contents:
Re: pentium timings (Greg)
Re: NSA hardware evaluation of AES finalists (Tim Tyler)
Re: Observation of Matsui's Sboxes (tomstd)
Re: safer style sboxes (tomstd)
Re: pentium timings (tomstd)
Re: OAP-L3 for T Huuskonen (tomstd)
Veryfying CRLs - how practically to do that? (Alex Garter)
Re: Observation of Matsui's Sboxes (Mark Wooding)
Re: safer style sboxes (tomstd)
Re: safer style sboxes (Mark Wooding)
Re: Observation of Matsui's Sboxes (tomstd)
Re: safer style sboxes (tomstd)
ideal safer style sboxes (tomstd)
Re: ideal safer style sboxes (tomstd)
----------------------------------------------------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: Re: pentium timings
Date: Wed, 24 May 2000 10:01:20 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>
> "Gisle S�lensminde" wrote:
>
> > I haven't tried Tom's code, but most operation systems runs each
thread
> > for slices of 10-100 ms at a time. On a 100 MHz computer with 10 ms
time
> > slices, that is 1_000_000 cycles, which means that the probability
of a context
> > swich in the middle is small if you measure ciphers, which in most
cases runs
> > on less than 1000 cycles.
Forget the context switching. What about the plain ol interrupt
service routine cutting in? What about DMA activity interfering
with the bus cycles? etc.
>
> A supplementary question: If a run takes such a small time, wouldn't
> the initialization time of the thread make out a substantial portion
of
> the total time measured? Thanks.
The only way you can ever know how much time a specific set of bytes
take to execute would be to record the bus traffic going to the CPU
and measuring the timings of those cycles. With the advent of on
board caches, this becomes far more expensive than in days gone by.
And with the complexities of the latest CPU technologies, one has
to ask more than the simple question, how long does XYZ take to
execute? One needs to ask, "... under this condition, and under
that condition, and under these other conditions here, and..."
You see what I mean?
Measuring the bus timing for a Pentium is nearly impossible compared
to that of a Z80 or even an 8088. With the 80c88, you could clock
the chip with a toggle switch to find out how many cycles some code
took to execute and then determine the time based upon the clock
speed you fed it.
--
There is only one gun law on the books- the second amendment.
The only vote that you waste is the one you never wanted to make.
RICO- we were told it was a necessary surrender of our civil liberties.
Asset Forfeiture- the latest inevitable result of RICO.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: NSA hardware evaluation of AES finalists
Reply-To: [EMAIL PROTECTED]
Date: Wed, 24 May 2000 09:58:31 GMT
David A. Wagner <[EMAIL PROTECTED]> wrote:
: Ken Lamquist <[EMAIL PROTECTED]> wrote:
:> time area transistors
:> Rijndael 288.8 46.36 1029,046
:> Serpent 632.6 23.27 345,483
: Is this the right metric? If you have extra area, won't you typically
: be able to add extra encryption units? [...]
I.e. can you parallelise? Isn't the answer to this something a bit like:
"yes - if using ECB mode - or if decrypting, while not using OFB mode"?
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Goodbye cool world.
------------------------------
Subject: Re: Observation of Matsui's Sboxes
From: tomstd <[EMAIL PROTECTED]>
Date: Wed, 24 May 2000 03:15:24 -0700
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(Mark Wooding) wrote:
>tomstd <[EMAIL PROTECTED]> wrote:
>
>> Algebraically the sboxes are explained as:
>>
>> S(x) = x^-1 mod p
>>
>> The first immediate observation is that
>>
>> S(0) = 0, S(1) = 1, for all p
>
>Note that Rijndael uses a function similar to this. However,
the
>inversion is followed by an affine transformation over GF(2).
Have you
>analysed this construction?
You mean keying the sbox? Like
x' = S(x xor K1) xor K2
Will still have the same avalanche problem. My point is the
sbox is fundementally flawed. It doesn't follow SAC.
I would bet with the appropriate linear mixing steps after the
usage of the sbox there would be no practical problem. I dunno.
BTW Any change to the order of the inputs for example
S(x) = (x + b)^-1 mod p
Makes the sbox much more linear and bad.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
Subject: Re: safer style sboxes
From: tomstd <[EMAIL PROTECTED]>
Date: Wed, 24 May 2000 03:18:51 -0700
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(Mark Wooding) wrote:
>Tom St Denis <[EMAIL PROTECTED]> wrote:
>
>> And haven't found one that is ideally non-linear. Which
makes me ask,
>> how come ciphers like SAFER or E2 (uses x^255 right?) can get
away with
>> that?
>
>Because they have good diffusion layers.
>
>If you can demonstrate that any n-round characteristic must
have k
>S-boxes active, and the best characteristic through the S-box
has
>probability (or bias) p_max, then your best n-round
characteristic has
>probability (or bias) p_max^k.
Wouldn't the cipher be better served with better sboxes? I can
make sboxes that have way better 'ideal' properties. Wouldn't
that make the cipher more secure?
>So, basically, if you design your diffusion layer right, then
you can
>get much better resistance to cryptanalysis than if you merely
diddled
>with the S-boxes for a while. And you can do that with
relatively
>lacklustre S-boxes.
To a point, if S() in safer were a identity permutation I bet it
wouldn't be all that strong...
>The Rijndael paper comments that, if anyone's worried about the
S-box
>(an inversion in GF(2^8) followed by an affine transformation
over
>GF(2)) having `back doors' in it, it can be replaced by
another, and it
>doesn't actually need to have wonderful properties for the
cipher to
>remain secure.
>
>Does anyone have any analysis of Rijndael which actually depends
>strongly on the S-box used?
I bet the permutation has to not be a identitity...
Anyways, still wouldn't these ciphers be more secure with ideal
sboxes?
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
Subject: Re: pentium timings
From: tomstd <[EMAIL PROTECTED]>
Date: Wed, 24 May 2000 03:21:50 -0700
In article <[EMAIL PROTECTED]>,
Jerry Coffin <[EMAIL PROTECTED]> wrote:
>In article <[EMAIL PROTECTED]>,
>[EMAIL PROTECTED] says...
>
>[ ... ]
>
>> Hmm, well I get consistant results in win98 and pure dos. So
>> magic or not it works. Also I can tell if it gets slower
simply
>> because the time increases. I don't think there is anything
>> else to effect it. Even if my code is off by three cycles, it
>> will be off for every trial.
>
>The problem is that your code may say it's slower, and you may
>believe it's slower, but in reality, it's faster...
>
>> Also I doubt much pairs with
>>
>> rdtsc
>> push eax
>> push edx
>
>"Pairing" is relevant only on the Pentium. On newer processors
you
>can out or order execution. The processor decodes instructions
into
>micro-ops. It dumps up to 40 micro-ops into the ReOrder
Buffer.
>Execution units grab instructions and execute them as soon as
all the
>resources to do so are free. If you want an in-depth look at
this,
>you might consider reading the Intel manuals, the MindShare
books on
>the Pentium Pro (or above) or, for perhaps the deepest look
easily
>availble, _The Anatomy of a High-Performance Microprocessor: A
>Systems Perspective_ by Bruce Shriver and Bennet Smith
(published by
>IEEE). This covers the AMD K6 rather than an Intel processor,
but
>the differences between the two are in the details (e.g. number
of
>decoders) not the basic methods involved.
>
>> So there won't be much clash with the code I am testing.
>
>Rather the contrary -- essentially nothing else is going to
depend on
>results from these instructions, meaning they can be executed
almost
>_anytime_ the processor finds it convenient to do so.
>
>[ ... ]
>
>> I release my code to the public for pure research purposes.
If
>> you don't like my timer.asm code, why not contribute a fix?
>
>I've offered to do so from the beginning. At least two other
people
>actually read what I said and have taken me up on the offer.
>
>> It's not like I don't give out anything else (sboxgen, rc5asm,
>> teaasm, etc...) so don't condemn my work because "he made a
>> mistake so he's a complete moron".
>
>I never said anything about your being a moron or anything like
it.
>I said that your actions were irresponsible. I've made no
personal
>attacks on anybody. I've offered to send you better code, and
you've
>completely ignored that offer, and instead attacked me. Though
this
>makes me feel somewhat less that charitable toward you at the
moment,
>the offer stands nonetheless. The code in question is public
domain,
>so you'd be perfectly welcome to use it, distribute it from
your web
>site, etc., if you wish to do so (of course the same applies to
>anybody else as well).
So please email the fixed timer.asm to me at [EMAIL PROTECTED]
Thanks,
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
Subject: Re: OAP-L3 for T Huuskonen
From: tomstd <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Date: Wed, 24 May 2000 03:23:36 -0700
In article <[EMAIL PROTECTED]>, Anthony Stephen
Szopa <[EMAIL PROTECTED]> wrote:
>T. Huuskonen says:
>"My observation shows that for a large class of keys (those
that
>involve a non-trivial amount of processing before the
generation
>of the pseudo random digit stream) there is a faster attack
against
>OAP-L3 than brute forcing the whole key. Hence, your "security
>level" calculations are wrong. Of course, an attack requiring
>10^100 tries is just as impossible in practice as one requiring
>10^1000 tries. In other words, I know that your "security
level"
>numbers are wrong, but I don't know whether the mistake has any
>practical consequences whatsoever."
>
>Your observation is not an observation. It is your fantasy.
Prove it.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: Alex Garter <[EMAIL PROTECTED]>
Subject: Veryfying CRLs - how practically to do that?
Date: 24 May 2000 10:31:53 GMT
How is it possible to verify certificate revocation lists, i.e. given a
certificate to check it for revocation without downloading all the
database, e.g. to do it from an applet.
TIA,
Alex
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Observation of Matsui's Sboxes
Date: 24 May 2000 10:32:32 GMT
tomstd <[EMAIL PROTECTED]> wrote:
> (Mark Wooding) wrote:
> >Note that Rijndael uses a function similar to this. However, the
> >inversion is followed by an affine transformation over GF(2). Have
> >you analysed this construction?
>
> You mean keying the sbox?
No, not at all.
Let I(x) be the inverse of x, viewed as an element of GF(2^8) as
represented by GF(2)[x]/p(x), where p(x) = x^8 + x^4 + x^3 + x + 1. Now
consider I(x) as a column vector of bits, and compute S(x) = A(I(x)),
where:
[ 1 0 0 0 1 1 1 1 ] [ x_0 ] [ 1 ]
[ 1 1 0 0 0 1 1 1 ] [ x_1 ] [ 1 ]
[ 1 1 1 0 0 0 1 1 ] [ x_2 ] [ 0 ]
A(x) = [ 1 1 1 1 0 0 0 1 ] [ x_3 ] + [ 0 ]
[ 1 1 1 1 1 0 0 0 ] [ x_4 ] [ 0 ]
[ 0 1 1 1 1 1 0 0 ] [ x_5 ] [ 1 ]
[ 0 0 1 1 1 1 1 0 ] [ x_6 ] [ 1 ]
[ 0 0 0 1 1 1 1 1 ] [ x_7 ] [ 0 ]
and all arithmetic is done mod 2.
This is the Rijndael S-box.
-- [mdw]
------------------------------
Subject: Re: safer style sboxes
From: tomstd <[EMAIL PROTECTED]>
Date: Wed, 24 May 2000 03:35:04 -0700
In article <8gfjlh$ib5$[EMAIL PROTECTED]>, zapzing <zapzing@my-
deja.com> wrote:
>In article <8gfc0q$d86$[EMAIL PROTECTED]>,
> Tom St Denis <[EMAIL PROTECTED]> wrote:
>> I have tested all possible sboxes in GF(257) of the form
>>
>> S(x) = x^b mod 257
>> and
>> S(x) = b^x mod 257
>>
>> (fixed 'b' value)
>>
>> And haven't found one that is ideally non-linear. Which
makes me ask,
>> how come ciphers like SAFER or E2 (uses x^255 right?) can get
away
>with
>> that?
>>
>> I use the WT to measure non-linearness and typically see -
44/44 as the
>> WT output... I would expect at least -32/32, and at best -
16/14
>> (matsui's sboxes do that well).
>>
>> Tom
>>
>> Sent via Deja.com http://www.deja.com/
>> Before you buy.
>>
>
>I just wonder why cipher desighners don't start
>using larger s-boxes. From what I understand, if
>an s-box is large enough, say 16 bits, then just
>about any randomly generated s-box will perform
>adequately. With hardware improving by leaps
>and bounds, this seems like it might be the
>way to go.
Not true, a 16x16 sbox would still have to be designed according
to CAST (or similar) to be secure. While it is possible to
make 'more' secure 16x16 sboxes then say two parallel 8x8 sboxes
you have to be careful.
>I was also wondering about this method for
>"generating" sboxes that are key dependent.
>What about
>
>s(x)=(((x+k1)^k2)+k3)^k4 ...
>where + (now) indicates addition modulo whatever
>and ^ indicates xor. One could also imagine
>using other operations in this way, such as
>the exponentiation you mentioned above.
Hmm, it's linear, it has good input-output xor pairs, has no SAC
or BIC... not a good idea.
Just because you use add/xor doesn't automatically make it non-
linear. Take the lsb for example, it's perfectly xor-linear.
So given
S(x) = (x + K1) xor K2
for example, that's the same as
S(x) = x xor K1 xor K2
For the lsb, or essentially just
S(x) = x xor K'
K' = K1 xor K2
Once I find that little bit, the next bit becomes perfectly xor-
linear, etc...
In all about 2n plaintexts are needed and about the same in time
(to find the keys). It's not a good sbox at all.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: safer style sboxes
Date: 24 May 2000 10:37:32 GMT
tomstd <[EMAIL PROTECTED]> wrote:
> Wouldn't the cipher be better served with better sboxes? I can
> make sboxes that have way better 'ideal' properties. Wouldn't
> that make the cipher more secure?
Certainly using wonderful S-boxes would be an improvement, but choosing
a random S-box is `good enough' if you get the diffusion right.
>
> >So, basically, if you design your diffusion layer right, then you can
> >get much better resistance to cryptanalysis than if you merely
> >diddled with the S-boxes for a while. And you can do that with
> >relatively lacklustre S-boxes.
[You're linewrapping quoted material very badly. Please stop it.]
> To a point, if S() in safer were a identity permutation I bet it
> wouldn't be all that strong...
You're confusing `relatively lacklustre' with `pathologically bad'.
-- [mdw]
------------------------------
Subject: Re: Observation of Matsui's Sboxes
From: tomstd <[EMAIL PROTECTED]>
Date: Wed, 24 May 2000 03:38:12 -0700
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(Mark Wooding) wrote:
>tomstd <[EMAIL PROTECTED]> wrote:
>> (Mark Wooding) wrote:
>> >Note that Rijndael uses a function similar to this.
However, the
>> >inversion is followed by an affine transformation over GF
(2). Have
>> >you analysed this construction?
>>
>> You mean keying the sbox?
>
>No, not at all.
>
>Let I(x) be the inverse of x, viewed as an element of GF(2^8) as
>represented by GF(2)[x]/p(x), where p(x) = x^8 + x^4 + x^3 + x
+ 1. Now
>consider I(x) as a column vector of bits, and compute S(x) = A(I
(x)),
>where:
>
> [ 1 0 0 0 1 1 1 1 ] [ x_0 ] [ 1 ]
> [ 1 1 0 0 0 1 1 1 ] [ x_1 ] [ 1 ]
> [ 1 1 1 0 0 0 1 1 ] [ x_2 ] [ 0 ]
> A(x) = [ 1 1 1 1 0 0 0 1 ] [ x_3 ] + [ 0 ]
> [ 1 1 1 1 1 0 0 0 ] [ x_4 ] [ 0 ]
> [ 0 1 1 1 1 1 0 0 ] [ x_5 ] [ 1 ]
> [ 0 0 1 1 1 1 1 0 ] [ x_6 ] [ 1 ]
> [ 0 0 0 1 1 1 1 1 ] [ x_7 ] [ 0 ]
>
>and all arithmetic is done mod 2.
>
>This is the Rijndael S-box.
I assume it's a bijection, but this one doesn't follow SAC
either. if I understand correctly, flipping x_1 will not effect
the last row at all.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
Subject: Re: safer style sboxes
From: tomstd <[EMAIL PROTECTED]>
Date: Wed, 24 May 2000 03:41:54 -0700
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(Mark Wooding) wrote:
>tomstd <[EMAIL PROTECTED]> wrote:
>
>> Wouldn't the cipher be better served with better sboxes? I
can
>> make sboxes that have way better 'ideal' properties. Wouldn't
>> that make the cipher more secure?
>
>Certainly using wonderful S-boxes would be an improvement, but
choosing
>a random S-box is `good enough' if you get the diffusion right.
>
>>
>> >So, basically, if you design your diffusion layer right,
then you can
>> >get much better resistance to cryptanalysis than if you
merely
>> >diddled with the S-boxes for a while. And you can do that
with
>> >relatively lacklustre S-boxes.
>
>[You're linewrapping quoted material very badly. Please stop
it.]
>
>> To a point, if S() in safer were a identity permutation I bet
it
>> wouldn't be all that strong...
>
>You're confusing `relatively lacklustre' with `pathologically
bad'.
>
>-- [mdw]
I am working on ideal 8x8 sboxes (with an inverse). I will post
later when I find one.
I can't help the bad news formatting, remarq is a bit wierd..
Also the point of the SBOX is to be a good permutation of the
input set to 'increase' security. Not just maintain it. Random
8x8 sboxes are hardly ideal (usually a little too linear, not
sac or bic).
These sboxes I am making are linearly bounded to -32/32, have a
max diff input-output xor pair prob of 8/256, are sac and are
bic (order 7). Which ideally should improve the security of a
cipher like SAFER considerably.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
Subject: ideal safer style sboxes
From: tomstd <[EMAIL PROTECTED]>
Date: Wed, 24 May 2000 03:47:43 -0700
I just finished making (with sboxgen [1]) some sboxes which have
better ideal characteristics then the standard 45^x sboxes in
safer.
They are at:
http://www.tomstdenis.com/sboxes.c
http://www.tomstdenis.com/sboxes.txt
Where the '.txt' file is the output of the WT and xor pairs
table.
The sbox (and it's inverse) are bounded linearly to -32/32, have
a max differential trait of 8/256, are SAC and follow BIC to
order 7.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
Subject: Re: ideal safer style sboxes
From: tomstd <[EMAIL PROTECTED]>
Date: Wed, 24 May 2000 03:51:34 -0700
In article <[EMAIL PROTECTED]>, tomstd
<[EMAIL PROTECTED]> wrote:
>I just finished making (with sboxgen [1]) some sboxes which have
>better ideal characteristics then the standard 45^x sboxes in
>safer.
>
>They are at:
>
>http://www.tomstdenis.com/sboxes.c
>
>http://www.tomstdenis.com/sboxes.txt
>
>Where the '.txt' file is the output of the WT and xor pairs
>table.
>
>The sbox (and it's inverse) are bounded linearly to -32/32, have
>a max differential trait of 8/256, are SAC and follow BIC to
>order 7.
>
>Tom
>
>* Sent from RemarQ http://www.remarq.com The Internet's
Discussion Network *
>The fastest and easiest way to search and participate in
Usenet - Free!
>
Ignore this, there is a bug in sboxgen, so the sboxes are
invalid.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
