RSA-1024 - how dead is it?

[Harold Johanssen]

Conventional wisdom has it that, in 2017, RSA-1024 should not be
used any longer for purposes of data protection encompassing more than a
few years. My question is, what is the state-of-the-art when it comes to
breaking such a scheme? What kind of progress has been made in, say, the
last five years, when it comes to factorizing a typical RSA-1204 modulus?
I mean, in the academic world. How closer are we to being able to
factorize such integers in a matter of hours, rather than months, at a
resonable cost - i.e. less than hundreds of millions of dollars?

[Pubkeybreaker]

See: https://eprint.iacr.org/2017/067.pdf

This paper discusses the very recent break of a 768-bit DL problem,
but in it they give projections (which are consistent with already
known estimates) for the difficulty of breaking 1024-bit RSA and 1024-bit DL.

Bottom line: It isn't going to happen in the next 5 years.

In May thru Dec 2015 they used 5300 core years on multiple clusters
to do the 768-bit DL.

RSA-1024 will be about 1000x as much work and ~sqrt(1000) times the
memory for the linear algebra. The 768-bit effort took 8 terabytes of
RAM for the final stage of the LA.

We therefore need about 5.3 million core years and ~250 terabytes of
memory for RSA-1024.

There are 31 million hours in a year. To do the sieving for RSA-1024 in
"a matter of hours" will require about 1.6 x 10^14 computers......
And doing the LA in "hours" is impossible with current technology.

The keysizes for RSA have been greatly raised in standards, not because of
conventional attacks, but rather from the *threat* (as yet unrealized)
of quantum computing.

Note: I predicted back in the 90's that RSA-1024 would not be broken before 2020.

[Harold Johanssen]

Thanks for the explanations and reference. So, it would be seem
that the reports on RSA-1024's impending demise have been somewhat
exaggerated.

[Pubkeybreaker]

OOPS! MEA CULPA. That should be 31 million SECONDS (not hours) in a year.
Adjust accordingly.

[Peter Fairbrother]

About 5.3 billion cores, at 1000 breaks per year or 8.8 hours per break.

>> And doing the LA in "hours" is impossible with current technology.

250 TB @ say $10,000/TB is certainly attainable by a major player. I
don't know how long it might take though.

>> The keysizes for RSA have been greatly raised in standards, not because
>> of conventional attacks, but rather from the *threat* (as yet
>> unrealized)
>> of quantum computing.

Partly that, but historically the smaller RSA keysizes became insecure
quicker than initially expected, and also people became aware of the
cost of upgrading; and so people became very conservative about new
keysizes.

>>
>> Note: I predicted back in the 90's that RSA-1024 would not be broken
>> before 2020.
>
> Thanks for the explanations and reference. So, it would be seem
> that the reports on RSA-1024's impending demise have been somewhat
> exaggerated.
>

Not entirely so - while Pubkeybreaker is essentially correct in his
facts concerning publicly-known algorithms, and I agree (but with the
second proviso below) that most likely it isn't going to happen in the
next five years, at least two other issues must still be considered.

First, how long do you want to keep a secret? If it's more than say 10
years, using 1024-bit RSA becomes dodgy at best; and using 1024-bit DH,
especially with a commonly-used prime, becomes almost irresponsible [1].

Second issue, whether there have been any hardware or theoretical
advances made by major players, eg NSA. You don't use the full power of
a major core when doing the sieving, and dedicated hardware could chop
at least one and probably two orders of magnitude off the core hardware
requirements.

As to theoretical advances, there have been hints of a theoretical
breakthrough by NSA - whether there is any truth in them I do not know.

But nowadays I recommend 1,536 bits, especially for DL/DH. The extra
cost is often lost in the noise, and seldom amounts to much.

I don't think there is much to gain in going any higher than 1,536 bits
- if Quantum computing can break 1,536 bits, it is likely only a small
step further to breaking any practicable number of bits. 2k bits is not
unreasonable to offset against unknown future developments, but any more
is most likely wasted.


[1] If you don't know, if you can do a lot of work and "break" a DH/DL
prime, then it becomes cheap to break as many messages using that prime
as you like.

As individual DH primes get reused a lot more often than RSA keys, if
you can break a few 1024-bits then the first and juiciest targets would
be the widely-used DH primes.

As far as I can see, there is no useful way to similarly "parallel"
attacks on sets of randomly generated RSA keys.

In consequence there is a good argument that DH primes should be longer
than RSA keys, even though equal lengths of RSA and DL are about as hard
to crack as each other.


-- Peter Fairbrother

[David Eather]

On Wed, 01 Mar 2017 18:50:19 +1000, David Eather <eat...@tpg.com.au> wrote:

> To put a different point of view:
>
> BULLRUN was an NSA program to compromise about 25% of all VPN servers -
> those that used the same 1024-bit DL. While it was a massive effort,
> they succeed and Snowden leaked it. RSA is supposed to be a little
> weaker for the same bit size, therefore, if your public key is of major
> importance and 1024 bits long, it is safer to assume it is broken (or at
> least that it can be broken) other keys of lesser importance and
> 1024-bit long will also become less secure but maybe OK for now - lets
> face it, most of us do not have any secrets the NSA would consider
> important enough to risk exposing their ability for regardless of how
> small that risk is .
>
> IIRC (and I am pretty sure I do) the NSA recommendation for it's suite
> of stuff was for 3072 bit RSA keys and then they only recommend they be
> used up to the classification of secret.


--
Using Opera's mail client: http://www.opera.com/mail/