Cryptography-Digest Digest #245, Volume #13 Thu, 30 Nov 00 08:13:00 EST
Contents:
Re: DES question: Has this ever been proven before? (David Wagner)
Re: keysize for equivalent security for symmetric and asymmetric keys (Bob Silverman)
Re: keysize for equivalent security for symmetric and asymmetric keys (DJohn37050)
Re: keysize for equivalent security for symmetric and asymmetric keys (DJohn37050)
Re: keysize for equivalent security for symmetric and asymmetric keys (Roger
Schlafly)
Pentium 4 and modular exponential (Paul Rubin)
Re: keysize for equivalent security for symmetric and asymmetric keys (Roger
Schlafly)
Re: Pentium 4 and modular exponential ([EMAIL PROTECTED])
Re: RC4 Questions ("CMan")
Re: Pentium 4 and modular exponential (Paul Rubin)
Re: Pentium 4 and modular exponential (Roger Schlafly)
Re: keysize for equivalent security for symmetric and asymmetric keys (Roger
Schlafly)
Re: On mutation of crypto algorithms (Mok-Kong Shen)
Re: password synchronisation (Mok-Kong Shen)
Re: RC4 Questions (Richard Heathfield)
Re: keysize for equivalent security for symmetric and asymmetric keys (Richard
Heathfield)
Re: RC4 Questions (Tom St Denis)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: DES question: Has this ever been proven before?
Date: 30 Nov 2000 03:19:11 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Francois Grieu wrote:
>Now I'll believe you on this one, but is there a simple argument
>showing that the header length is almost allways smaller than the
>cycle ?
You definitely shouldn't just believe me on it!
(_especially_ when you consider how many mistakes I have been making)
On second thought "almost always" is almost certainly :-) an exaggeration,
but I think the following argument gives the idea. If j is the smallest
index so that there exists i with 0 <= i < j and a(i) = a(j), then I believe
the distribution of i (conditioned on the above) should be uniform in the
interval 0 .. j-1. (assuming you are iterating a random function, of course)
Thus, the cycle length is larger than the header length at least half of
the time. So, a simple randomized algorithm is to optimistically assume
that the period is n; if this does not produce a collision, try again.
You can be a bit more efficient. The cycle length is of the form n/k, and
k can be found in time linear in the largest prime divisor of k and
logarithmic in k. Now, the header length is at most O(cycle length),
except for a bad event whose probability can be made arbitrarily small,
which allows you to provide a linear running time almost always.
There may be a clever way to improve on this even further. But I'm not
sure it's worth thinking about too much; Wiener and van Oorschot's parallel
collision search algorithm solves this problem and is superior in many
other valuable respects as well.
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: keysize for equivalent security for symmetric and asymmetric keys
Date: Thu, 30 Nov 2000 03:05:22 GMT
In article <[EMAIL PROTECTED]>,
Doug Kuhlman <[EMAIL PROTECTED]> wrote:
>
>
> Bob Silverman wrote:
> >
> > In article <[EMAIL PROTECTED]>,
> > [EMAIL PROTECTED] (DJohn37050) wrote:
> > >
> > > So you picks your model and makes your mapping. I personally
favor
> > the NIST
> > > numbers,
> >
> > Unstated: "Because I work for Certicom and it is in my company's
> > best interest to make RSA keys as large as possible relative to EC
> > keys. That way, EC cryptography appears to have much better
> > performance".
> >
> I just feel compelled to point out that Bob Silverman works for RSA,
so
> you have to take his arguments and numbers with a grain of salt, too.
> And don't ask me, because I'm not unbiased on this topic, either.
Except that I've been saying this stuff long before I came to RSA.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Date: 30 Nov 2000 03:23:16 GMT
Subject: Re: keysize for equivalent security for symmetric and asymmetric keys
ANSI X9 mandates that RSA modulus n or DSA field size p be at least 1024 bits
and that the ECC subgroup order n be at least 161 bits. Each is estimated to
be around 2**80 ops in complexity and so is appropriate to use with SHA-1 and
80-bit symmetric keys.
In a DSA-2 draft with longer key lengths that NIST presented to ANSI X9, they
said that for symmetric key sizes of 80, 112, 128, 192, and 256.the p and q
sizes are as given in my paper I referred to ealier (this is where I got the
numbers for DSA). The ECC numbers in my paper are from the NIST recommended
curves and also can be mapped from the DSA q value.
It is well known that GNFS to solve DL is slightly harder than GNFS to solve
RSA, so use of the DSA p values for the RSA modulus n value is about right.
Perhaps it should be some bits more, but most people do not quibble about this.
I call this the NIST TIME keysize model. I did not create it, I just assembled
it from different sources. I do see advantages in using it, (1) It has the
imprimateur of NIST (read NSA), at least for DSA and ECC. (2) It is simple and
straightforward. One can easily see how the numbers were arrived at. (3) It is
conservative. Advances in cheaper storage and/or improvements in algs to use
less storage do not affect it. (4) It gives specific guidance on keysize in a
simple table and is simple to use.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Date: 30 Nov 2000 03:32:09 GMT
Subject: Re: keysize for equivalent security for symmetric and asymmetric keys
David exactly sees what I am trying to say. Pick a model and you get a
keysize. But understand your assumptions. Hear, hear.
Don Johnson
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: keysize for equivalent security for symmetric and asymmetric keys
Date: Wed, 29 Nov 2000 20:01:18 -0800
David Wagner wrote:
> Let < represent the relation "is more conservative than".
> Consider the following three assumptions:
> A_0: There will be no advances in factoring.
> A_1: Advances in factoring might reduce its storage complexity of
> factoring faster than its time complexity.
> A_2: The time complexity of factoring might reduce faster than storage.
> Then A_1 < A_0 and A_2 < A_0 (but A_1 and A_2 need not be comparable).
>
> A_0 is a blatantly anti-conservative assumption. If you are willing to
> call an assumption A conservative whenever A < A_0, then both A_1 and
> A_2 are conservative assumptions. If not, well, my comments don't apply.
If you want A_0 to be blatantly anti-conservative, then also
assume that there will be no advances in computer technology,
no increase in criminal behavior, no increase in funds available
to criminals, etc.
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Pentium 4 and modular exponential
Date: 29 Nov 2000 20:03:31 -0800
Anyone looked into this? The P4 is getting some bad press at normal
applications, but it might be a win for modexp. Its ALU runs at 2x
the clock speed of the rest of the chip, i.e. the 1.5 ghz P4
(available now for around $1K) runs its ALU at 3 ghz. Also, it has
yet another MMX extension, this time called SSE2. This lets you use
the 128-bit SSE registers as a pair of 64-bit long long ints or IEEE
doubles. What I don't know is whether you can start a pair of
multiply-adds on every cycle (3 ghz) or what; and you can arrange
the input data to use it at full speed without overflows.
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: keysize for equivalent security for symmetric and asymmetric keys
Date: Wed, 29 Nov 2000 20:18:41 -0800
David Wagner wrote:
> It all depends on how conservative the end user is. If the end user
> wants to be conservative about improvements to storage complexity, then
> she should use the comparison method you are attributing to Don. If the
> end user wants to be less conservative about this issue, then it would
> be more rational for her to "Bob's method". Agreed?
That just seems arbitrary to me for the end user to focus on
storage. Is the end user really going to say, "I am worried
someone will figure out how to do GNFS with less memory."?
Well, maybe, but that doesn't seem any more likely than, "I
am worried someone will figure out how to do EC discrete logs
in less CPU time."
Sure, someone might have an opinion. And no one really knows,
so the instincts of the average user might be as good as the
expert's. But I just don't buy this argument that you can
pick out one issue, be "conservative" about that, and come
to a useful conclusion. It's just another hand waive, no
better than any other.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Pentium 4 and modular exponential
Date: Thu, 30 Nov 2000 05:15:14 GMT
Paul Rubin <[EMAIL PROTECTED]> wrote:
> Anyone looked into this? The P4 is getting some bad press at normal
> applications, but it might be a win for modexp. Its ALU runs at 2x
> the clock speed of the rest of the chip, i.e. the 1.5 ghz P4
> (available now for around $1K) runs its ALU at 3 ghz. Also, it has
> yet another MMX extension, this time called SSE2. This lets you use
> the 128-bit SSE registers as a pair of 64-bit long long ints or IEEE
> doubles. What I don't know is whether you can start a pair of
> multiply-adds on every cycle (3 ghz) or what; and you can arrange
> the input data to use it at full speed without overflows.
On the other hand, the FPU is slower than the P3. To be fair though,
that's countered by the faster clock. You can FADD every clock cycle,
and FMUL every other clock cycle. You cannot, however, start them on
the same cycle.
Peak throughput for SSE2 is and ADD and MUL every clock cycle. The L1
cache latency, however, is 6 clocks for SSE2 and FP instructions (vs 2
for intheger instructions.) Once you get into L2, it's 7 clocks
regardless.
This is sort of the hot topic on the mersenne mailng list this week,
as George Waltman looks at porting the FFT to the P4. If it's not in
the archives yet, I can forward you the two applicable digests, which
have alot more numbers quoted from the specs.
--
Matt Gauthier <[EMAIL PROTECTED]>
------------------------------
From: "CMan" <[EMAIL PROTECTED]>
Subject: Re: RC4 Questions
Date: Wed, 29 Nov 2000 22:22:57 -0700
>
> First off I suggest you study what an sbox is first. A 16x16 sbox
> requires 128kb of ram and would actually slow down RC4 (on a commodity
> desktop). A 32x32 is infeasible at best.
Um...
Yer math seems a bit off here. On my slide rule, I get the following:
I calculate 2048 bits required to implement a 16 bytes/row by 16 row RC4
S-box. 16 X 16 = 256 bytes. 256 bytes X 8 bits/byte = 2048 bits!
That is if I have studied what an s-box is. :--))
JK
--
CRAK Software
http://www.crak.com
Password Recovery Software
QuickBooks, Quicken, Access...More
Spam bait (credit E. Needham):
root@localhost
postmaster@localhost
admin@localhost
abuse@localhost
webmaster@localhost
[EMAIL PROTECTED]
[EMAIL PROTECTED]
[EMAIL PROTECTED]
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: Pentium 4 and modular exponential
Date: 29 Nov 2000 21:46:07 -0800
[EMAIL PROTECTED] writes:
> On the other hand, the FPU is slower than the P3. To be fair though,
> that's countered by the faster clock. You can FADD every clock cycle,
> and FMUL every other clock cycle. You cannot, however, start them on
> the same cycle.
Interesting, thanks. I'd want to use integer instructions for modexp,
of course.
> Peak throughput for SSE2 is and ADD and MUL every clock cycle. The L1
> cache latency, however, is 6 clocks for SSE2 and FP instructions (vs 2
> for intheger instructions.) Once you get into L2, it's 7 clocks
> regardless.
But the memory access sequence for these convolutions is mostly
sequential and totally predictable, so it should be ok to use the
cache prefetch instructions to overlap arithmetic that you're doing
now with loads of stuff that you're going to need later?
> This is sort of the hot topic on the mersenne mailng list this week,
> as George Waltman looks at porting the FFT to the P4. If it's not in
> the archives yet, I can forward you the two applicable digests, which
> have alot more numbers quoted from the specs.
Nah, I was just wondering what the prospects were. I have too many
other things to occupy my time. Thanks for the update.
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: Pentium 4 and modular exponential
Date: Wed, 29 Nov 2000 22:09:47 -0800
Tom's Hardware has had mixed reviews of the Pentium 4. The
chip did well on some benchmarks, but surprisingly poorly
on a lot of them. It may be that you have to have software
optimized for the Pentium 4 to get any benefit.
http://www.tomshardware.com/blurb/00q4/001128/index.html
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: keysize for equivalent security for symmetric and asymmetric keys
Date: Wed, 29 Nov 2000 22:20:50 -0800
DJohn37050 wrote:
> ANSI X9 mandates that RSA modulus n or DSA field size p be at least 1024 bits
> and that the ECC subgroup order n be at least 161 bits. Each is estimated to
> be around 2**80 ops in complexity and so is appropriate to use with SHA-1 and
> 80-bit symmetric keys.
They are bankers. Do they have infinite wisdom?
> I call this the NIST TIME keysize model. I did not create it, I just assembled
> it from different sources. I do see advantages in using it, (1) It has the
> imprimateur of NIST (read NSA), at least for DSA and ECC. (2) It is simple and
> straightforward. One can easily see how the numbers were arrived at. (3) It is
> conservative. Advances in cheaper storage and/or improvements in algs to use
> less storage do not affect it. (4) It gives specific guidance on keysize in a
> simple table and is simple to use.
I doubt the NSA had anything to do with it. Your tables are simple
to use, but there could be a more thorough analysis that is more
accurate.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On mutation of crypto algorithms
Date: Thu, 30 Nov 2000 09:59:48 +0100
Tom St Denis wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >
> > Tom St Denis wrote:
> > >
> > > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >
> > > > An interesting question is how would a scaled-down version
> > > > of Rijndael compete with DES. My feeling of the gut is that
> > > > 20 rounds would probably suffice to provide a fairly safe
> > > > bet.
> > >
> > > Irrelevant. Rijndael cannot process 64-bit blocks. The closest
> thing
> > > is a 72-bit block.
> >
> > What hinders a scaling-down to 64 bit blocks?
>
> The fact that you cannot build a square with eight elements...
I don't yet understand. Which square? Which component of
a Rijndael's round are you talking about? Can't we use
a rectangle, say?
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: password synchronisation
Date: Thu, 30 Nov 2000 10:05:22 +0100
johan cowe wrote:
> At our firm, we are looking for a password-synchronisation tool that works
[snip]
Sorry for a question of ignorance: What is password-
synchronisation? Thanks.
M. K. Shen
------------------------------
Date: Thu, 30 Nov 2000 10:45:14 +0000
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: RC4 Questions
CMan wrote:
>
> >
> > First off I suggest you study what an sbox is first. A 16x16 sbox
> > requires 128kb of ram and would actually slow down RC4 (on a commodity
> > desktop). A 32x32 is infeasible at best.
>
> Um...
> Yer math seems a bit off here. On my slide rule, I get the following:
>
> I calculate 2048 bits required to implement a 16 bytes/row by 16 row RC4
> S-box. 16 X 16 = 256 bytes. 256 bytes X 8 bits/byte = 2048 bits!
>
> That is if I have studied what an s-box is. :--))
No, 16x16 in this context means you put 16 bits in, and you get 16 bits
out.
Since there are 65536 different combinations of 16 bits, you will need
65536 different values in your S-box, so you need an array of 65536
16-bit quantities. Thus, 128KB is correct.
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html
------------------------------
Date: Thu, 30 Nov 2000 11:05:55 +0000
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: keysize for equivalent security for symmetric and asymmetric keys
[Disclaimer: Bob Silverman is an expert in cryptography, and I'm not, so
newbies should be careful not to ascribe too much weight to my article,
and oldies will probably laugh in my face anyway :-) ]
Bob Silverman wrote:
>
<snip>
>
> Using a 15K RSA key is worse than ridiculous. Using a 256 bit
> AES key is gross overkill as well. I suggest you do the arithmetic
> to see how long it will take to break a 128-bit key. You may assume
> computers 1 million times faster than existing computers. You may
> assume that you have a billion of them available.......
Moore's Law. By 2032 (or so), we'll have computers a million times
faster than today's computers. By 2066, they'll be one million million
times faster. By around 2100, one single computer will be able to do the
work of the batch of computers you describe in the above paragraph. And
what if we have a billion of /those/?
This fact doesn't, of itself, defeat your point, because 2**128 is such
a colossal number. But, if Moore's Law holds (and I recognise that it's
a big IF), the day may eventually come when 128 bits isn't enough. Of
course, we'll all be dead by then, but that's beside the point. :-)
People will insist on longer and longer keys, because key length seems
to be market-driven - the S.O. merchants are telling them "look at the
size of our keys!" and they believe it. But there is an upper
theoretical limit on how much computing can be done in the entire
observable universe for the rest of the expected life of the universe,
and so it should be possible to calculate a key length such that the key
cannot be brute forced, EVER. I think Bruce Schneier's "Applied
Cryptography" discusses this, but my copy isn't to hand at the moment.
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: RC4 Questions
Date: Thu, 30 Nov 2000 12:19:01 GMT
In article <[EMAIL PROTECTED]>,
Richard Heathfield <[EMAIL PROTECTED]> wrote:
> CMan wrote:
> >
> > >
> > > First off I suggest you study what an sbox is first. A 16x16 sbox
> > > requires 128kb of ram and would actually slow down RC4 (on a
commodity
> > > desktop). A 32x32 is infeasible at best.
> >
> > Um...
> > Yer math seems a bit off here. On my slide rule, I get the
following:
> >
> > I calculate 2048 bits required to implement a 16 bytes/row by 16
row RC4
> > S-box. 16 X 16 = 256 bytes. 256 bytes X 8 bits/byte = 2048 bits!
> >
> > That is if I have studied what an s-box is. :--))
>
> No, 16x16 in this context means you put 16 bits in, and you get 16
bits
> out.
>
> Since there are 65536 different combinations of 16 bits, you will need
> 65536 different values in your S-box, so you need an array of 65536
> 16-bit quantities. Thus, 128KB is correct.
CAN WE SAY BOOYAH? hehehe just kidding.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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
******************************
