Prev: Australian Crypto Regulations
Next: Are online password managers safe to use?
From: Nomen Nescio on 18 Apr 2010 15:30
http://www.keylength.com/en/4/

I noticed that the NIST recommends an asymmetric key length strength of
15360 bits for the timeframe after 2030 (the exact timeframe isn't made
clear but my guess is 2100).

Now, given that it recently took 4 years of nonstop computation to
crack a *single* 768 bits RSA key and that it will probably take at
least a decade before we can crack a 1024-bit RSA key (probably using
many years of computations), I'm wondering what their drift is. Are
they anticipating Quantum computers in these calculations? Surely such
a large keylength can't be explained by pure increases in computational
strength alone, can it?

From: Jens Stuckelberger on 18 Apr 2010 18:59
On Sun, 18 Apr 2010 21:30:09 +0200, Nomen Nescio wrote:

> http://www.keylength.com/en/4/
>
> I noticed that the NIST recommends an asymmetric key length strength of
> 15360 bits for the timeframe after 2030 (the exact timeframe isn't made
> clear but my guess is 2100).
>
> Now, given that it recently took 4 years of nonstop computation to crack
> a *single* 768 bits RSA key and that it will probably take at least a
> decade before we can crack a 1024-bit RSA key (probably using many years
> of computations), I'm wondering what their drift is. Are they
> anticipating Quantum computers in these calculations? Surely such a
> large keylength can't be explained by pure increases in computational
> strength alone, can it?

They are just being anal and/or they are feeding their ego/self-
importance. If the bad guys want to get your data there are far cheaper
and more efficient approaches to do so than attempting to brute force
your 1024-bit RSA keys.


From: Scott Contini on 18 Apr 2010 20:33
On Apr 19, 5:30 am, Nomen Nescio <nob...(a)dizum.com> wrote:
> http://www.keylength.com/en/4/
>
> I noticed that the NIST recommends an asymmetric key length strength of
> 15360 bits for the timeframe after 2030 (the exact timeframe isn't made
> clear but my guess is 2100).
>
> Now, given that it recently took 4 years of nonstop computation to
> crack a *single* 768 bits RSA key and that it will probably take at
> least a decade before we can crack a 1024-bit RSA key (probably using
> many years of computations), I'm wondering what their drift is. Are
> they anticipating Quantum computers in these calculations? Surely such
> a large keylength can't be explained by pure increases in computational
> strength alone, can it?

I disagree with the "4 years of nonstop computation" claim. Yes, some
polynomial selection started in 2005, but I'm pretty sure it was not
nonstop computation from then on. The bulk of the work didn't get
underway until 2007.

It is reasonable to expect that researchers can factor 1024-bit
numbers
by 2020. Large, well funded organizations might be able to do so
sooner.

I think part of your problem is not understanding the running time of
the number field sieve. I suggest that rather than looking at the
asymmetric column of the table, you instead look at the symmetric
column. Do you find it reasonable to believe that by 2030, high-end
security applications should have 256-bit symmetric keys? If you
answered yes, then the time to factor 15360-bit RSA keys with the
number field sieve is very very roughly equivalent to the time to
brute for a 256-bit symmetric key. I say "very very roughly" because
there are two caveats to this claim: (i) It is impossible to
approximate
this very closely because the known running time of NFS does not allow
us to extrapolate that far out for future predictions, and (ii) This
calculation is completely ignoring the memory obstacles which several
researchers are unhappy with (the model is over-simplified).
Regardless
of these caveats, I think most researchers agree that the future of
RSA
and discrete log based systems does not look promising. Time to start
thinking about switching to elliptic curves or some other realistic
alternative.

Scott

From: Scott Contini on 18 Apr 2010 20:38
On Apr 19, 5:30 am, Nomen Nescio <nob...(a)dizum.com> wrote:
> http://www.keylength.com/en/4/
>
> I noticed that the NIST recommends an asymmetric key length strength of
> 15360 bits for the timeframe after 2030 (the exact timeframe isn't made
> clear but my guess is 2100).
>
> Now, given that it recently took 4 years of nonstop computation to
> crack a *single* 768 bits RSA key and that it will probably take at
> least a decade before we can crack a 1024-bit RSA key (probably using
> many years of computations), I'm wondering what their drift is. Are
> they anticipating Quantum computers in these calculations? Surely such
> a large keylength can't be explained by pure increases in computational
> strength alone, can it?

I disagree with the "4 years of nonstop computation" claim. Yes, some
polynomial selection started in 2005, but I'm pretty sure it was not
nonstop computation from then on. The bulk of the work didn't get
underway until 2007.

It is reasonable to expect that researchers can factor 1024-bit
numbers
by 2020. Large, well funded organizations might be able to do so
sooner.

It also does not say changing to keys this length in 2030 but
instead ">>> 2030", i.e. much later than 2030. But putting that
aside, let's address your concern.

I think part of your problem is not understanding the running time of
the number field sieve. I suggest that rather than looking at the
asymmetric column of the table, you instead look at the symmetric
column. Do you find it reasonable to believe that by ">>> 2030", high-
end
security applications should have 256-bit symmetric keys? If you
answered yes, then the time to factor 15360-bit RSA keys with the
number field sieve is very very roughly equivalent to the time to
brute for a 256-bit symmetric key. I say "very very roughly" because
there are two caveats to this claim: (i) It is impossible to
approximate
this very closely because the known running time of NFS does not allow
us to extrapolate that far out for future predictions, and (ii) This
calculation is completely ignoring the memory obstacles which several
researchers are unhappy with (the model is over-simplified).
Regardless
of these caveats, I think most researchers agree that the future of
RSA
and discrete log based systems does not look promising. Time to start
thinking about switching to elliptic curves or some other realistic
alternative.

Scott

From: Scott Contini on 18 Apr 2010 20:54
On Apr 19, 5:30 am, Nomen Nescio <nob...(a)dizum.com> wrote:
> http://www.keylength.com/en/4/
>
> I noticed that the NIST recommends an asymmetric key length strength of
> 15360 bits for the timeframe after 2030 (the exact timeframe isn't made
> clear but my guess is 2100).
>
> Now, given that it recently took 4 years of nonstop computation to
> crack a *single* 768 bits RSA key and that it will probably take at
> least a decade before we can crack a 1024-bit RSA key (probably using
> many years of computations), I'm wondering what their drift is. Are
> they anticipating Quantum computers in these calculations? Surely such
> a large keylength can't be explained by pure increases in computational
> strength alone, can it?

I disagree with the "4 years of nonstop computation" claim. Yes, some
polynomial selection started in 2005, but I'm pretty sure it was not
nonstop computation from then on. The bulk of the work didn't get
underway until 2007.

It is reasonable to expect that researchers can factor 1024-bit
numbers by 2020. Large, well funded organizations might be able
to do so sooner.

It also does not say changing to keys this length in 2030 but
instead ">>> 2030", i.e. much later than 2030. But putting that
aside, let's address your concern.

I agree that it is indeed looking very far in the future, and
making such predictions now is a bit of a leap. But putting
that aside, it is important to understand the running time of
the number field sieve (NFS). I suggest that rather than looking
at the asymmetric column of the table, you instead look at the
symmetric column. Do you find it reasonable to believe that by
">>> 2030" (i.e. some unspecified time far into the future), high-end
security applications should have 256-bit symmetric keys? If you
answered yes, then the time to factor 15360-bit RSA keys with the
number field sieve is very very roughly equivalent to the time to
brute for a 256-bit symmetric key. I say "very very roughly" because
there are two caveats to this claim: (i) It is impossible to
approximate this very closely because the known running time of NFS
does not allow us to extrapolate that far out for future predictions,
and (ii) This calculation is completely ignoring the memory obstacles
which several researchers are unhappy with (the model is
over-simplified). Regardless of these caveats, I think most
researchers
agree that the long-term future of RSA and discrete log based systems
does not look promising.

Scott
 |  Next  |  Last
Pages: 1 2 3
Prev: Australian Crypto Regulations
Next: Are online password managers safe to use?