Prev: Australian Crypto Regulations
Next: Are online password managers safe to use?
From: Joseph Ashwood on 18 Apr 2010 20:01
"Nomen Nescio" <nobody(a)dizum.com> wrote in message
news:6e198f1243bbf6401bc331b8662f07ce(a)dizum.com...
> 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?

Actually it is explained exclusively by computational complexity, more
specifically they disregard computational storage requirements. The opposing
standard is generally pushed most by RSA Security
(http://www.rsa.com/rsalabs/node.asp?id=2088) and includes computational
storage requirements as well. In the computation complexity model performing
the NFS algorithm on an input of about 15360 bits will take about 2^128
work, in the RSA model the inclusion of memory cost bring the number down,
to 1620 bits.

Opinions on this are divided. Certainly the computational complexity process
gives a good baseline, but for such a large computation space there is
something to be said for considering the storage requirements.

In general, I prefer a model like the RSA model, but I think the RSA model
needs a major recomputation. Advancing SSD technology is exposing some
differences between the future and the present used for the RSA model.
Basically, the technology exists right now to start producing multi-TB SSDs
that operate at 100s of GB/sec, this doesn't eliminate the value of a
cost-based model, but does require a recomputation of it.

If you want the most conservative number, the computational complexity
models give great numbers, they're big, they're scary, they have great
doomsday promise, but if you want accuracy it does have to be a cost based
model like the RSA Model, just be aware that accuracy very often becomes
very inaccurate over time.
Joe

From: Non scrivetemi on 19 Apr 2010 09:45
Nomen Nescio <nobody(a)dizum.com> wrote:

> 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)

RSA keys can be factored considerably cheaper than that, and there is very
good reason to believe 1024 bit keys are already well within range.

You don't need imaginary "quantum" computers to get this done, but you do
need to understand what technology is available and has been available for
quite a long time, that's considerably more powerful than the hottest PC
and available to big companies and governments.

From: unruh on 19 Apr 2010 13:05
On 2010-04-19, Carsten Krueger <cakruege(a)gmail.com> wrote:
> Am Mon, 19 Apr 2010 08:28:03 -0700 (PDT) schrieb Tom St Denis:
>
>> I thought it was generally understood that the memory requirements of
>> the NFS are what prevent it from really tackling any larger keys...
>
> Do u have assumptions how much memory is needed?
>
> Big companies (like Google) and some nations have computer power of hundred
> thounds to millions of PCs.

Usually does not help, because they are on different machines. The
memory must be accessed in parallel ( matrix inversion) and the
intermachine communication gets slow.


>
> greetings
> Carsten
From: Nomen Nescio on 19 Apr 2010 18:05
"Scott Contini" <the_great_contini(a)yahoo.com> wrote in message
news:1b7f35b5-2c15-4715-9234-9332e52682df(a)e7g2000yqf.googlegroups.com...
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


========================================================================

Agreed, it depends on how you benchmark, but it took them either 2 or 4
years of computation to crack the 768 bit RSA key. IIRC they did two
years of pre-calculations (almost non-stop) and two years of non-stop
computation to crack the actual key. So take your pick.

I doubt anyone will be able to break 1024-bit keys in 2020 and the NSA
won't even attempt it unless your name is Osama Bin Laden. Google may
have the computational power in 2020 but they need it for their day to
day business (Internet search) so they can only do it on paper. And
even so, it would take them years.

IIRC most cryptologists agree that a 256-bit AES key cannot be broken
for HUNDREDS of years. When Captain Kirk and Mr. Spock are a reality
they still will not be able to break AES-256 encrypted messages. That
would imply that a 15360 bit RSA key will be pretty much secure for as
long as anyone of us will be around. In fact, even taken in account
computational increases a 256-bit AES key cannot be broken before the
UNIVERSE ceases to exist!

From: Bryan on 19 Apr 2010 18:32
Scott Contini wrote:
> It also does not say changing to keys this length in 2030 but
> instead ">>> 2030", i.e. much later than 2030.
[...]
> I agree that it is indeed looking very far in the future, and
> making such predictions now is a bit of a leap.
[...]
> look at the symmetric column.
[...]
> 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 think Scott nailed it. NIST is answering a demand for guidance with
a best-effort attempt based on what little we now know. Consistency,
though a poor second, is the next best thing to truth.
First  |  Prev  |  Next  |  Last
Pages: 1 2 3
Prev: Australian Crypto Regulations
Next: Are online password managers safe to use?