Subject: Re: [Cfrg] 1024 bit RSA

From: Hal Murray <[email-masked]>
Date: Fri, 04 Nov 2016 14:03:13 -0700

[email-masked] said:
> So expect RSA 1024 to certainly fall by 2030 and probably by 2025. 

What are the right units for that discussion?

I think it has to include cost and time-to-solve.  For compute-intensive 
approaches that parallize, the time part drops out.  There are probably 2 
paths, one using COTS gear and another using ASICs.

Is there something like Moore's Law for breaking crypto?

-- 
These are my opinions.  I hate spam.

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 4 Nov 2016 23:23:48 +0200

> Is there something like Moore's Law for breaking crypto?

(Warning: Pretty pure guessing ahead.)

I think it depends on what you are talking about: Using CPUs vs. ASICs.

For CPUs, I think the improvements of Moore's law mostly go to very
modest performance improvements (and to reducing power usage).

Of course, Moore's law might have slowed down by now... And will
probably halt soon (I don't imagine transition off Si being that
smooth... There have been enormous amounts of infrastructure
invested on Si).

For ASICs, those improvments probably could mostly go to improving
performance. The main limit is heat dissipiation.

And when it comes to cost of building ASICs, the costs are mostly
upfront (design, masks, etc... are very expensive). Manufacturing
ASICs (at least if using ordinary digital-only processes) is quite
cheap.

So once one has design and masks for ASIC, one can cheaply get
massive number of copies. And ASICs can be quite specialized.

One fortunate aspect with RSA is that the final step of
factoring involves quite a lot of memory use. But it takes relatively
little time (most of the work is in sieving).

In summary, I would guess that factoring RSA 1024 keys would be within
reach of groups who could do ASIC design and then ordering custom
chips off fabs. Of course, that's still many millions, so one would
need the financial case of spending that much money (it is going to
be millions of dollars at the very least).

-Ilari

---

From: Peter Gutmann <[email-masked]>
Date: Sat, 5 Nov 2016 03:51:16 +0000

Ilari Liusvaara <[email-masked]> writes:

>In summary, I would guess that factoring RSA 1024 keys would be within reach
>of groups who could do ASIC design and then ordering custom chips off fabs.
>Of course, that's still many millions, so one would need the financial case
>of spending that much money (it is going to be millions of dollars at the
>very least).

And that's the key point, would anyone bother?  There's always the
hypothetical government-level attacker with magical access to infinite
resources lurking in the shadows, but as Snowden has shown, they don't need to
spend that much to get in, or build crypto-breakers to do it.  If I was an NSA
program manager and someone came to me and said "we need $100M to build an
ASIC-based RSA cracker, which we should have tested, debugged, and operational
in two years", I'd reply "here's a full *one hundredth* of that amount, you've
got a week to get in by backdooring or subverting or bribing or whatever"
(with an optional side-order of "yer lazy bastard" in an Ernest Borgnine
accent).

Even if there was absolutely no other way in, I can't see how you could
justify building something like that unless you were using it to attack
something of extraordinarily high value like the single RSA-1024 key that the
Kremlin uses to communicate with all its local offices.  DH group 2 (group 1
in SSH terminology), sure (although an RSA-breaker can't do anything with
those anyway), but some random RSA key somewhere?

Peter.

---

From: "Erik Andersen" <[email-masked]>
Date: Sat, 5 Nov 2016 10:05:13 +0100

All the comments have been quite useful. Let me express my concern.

There is a cyber war out there and it is been use politically.

When it comes to smart grid, it will be very depending on a complex IT
infrastructure (primarily using SCADA protocols). Our electricity networks
are very critical infrastructures. The Ukraine black-out is a warning about
what we might expect. My country (Denmark) and our allies are not always
acting as other great powers may want. The threat to bring down a critical
infrastructure could affect the policy making. We should not leave too many
soft spots in our defence wall. My question was actually. Is a 1024 RSA key
such a soft spot? From what I hear, the answer might be yes.

Erik

-----Oprindelig meddelelse-----
Fra: Cfrg [mailto:[email-masked]] På vegne af Peter Gutmann
Sendt: 05 November 2016 04:51
Til: Ilari Liusvaara <[email-masked]>; Hal Murray
<[email-masked]>
Cc: Cfrg <[email-masked]>
Emne: Re: [Cfrg] 1024 bit RSA

Ilari Liusvaara <[email-masked]> writes:

>reach of groups who could do ASIC design and then ordering custom chips off
fabs.
>Of course, that's still many millions, so one would need the financial 
>case of spending that much money (it is going to be millions of dollars 
>at the very least).

And that's the key point, would anyone bother?  There's always the
hypothetical government-level attacker with magical access to infinite
resources lurking in the shadows, but as Snowden has shown, they don't need
to spend that much to get in, or build crypto-breakers to do it.  If I was
an NSA program manager and someone came to me and said "we need $100M to
build an ASIC-based RSA cracker, which we should have tested, debugged, and
operational in two years", I'd reply "here's a full *one hundredth* of that
amount, you've got a week to get in by backdooring or subverting or bribing
or whatever"
(with an optional side-order of "yer lazy bastard" in an Ernest Borgnine
accent).

Even if there was absolutely no other way in, I can't see how you could
justify building something like that unless you were using it to attack
something of extraordinarily high value like the single RSA-1024 key that
the Kremlin uses to communicate with all its local offices.  DH group 2
(group 1 in SSH terminology), sure (although an RSA-breaker can't do
anything with those anyway), but some random RSA key somewhere?

Peter.
_______________________________________________
Cfrg mailing list
[email-masked]
https://www.irtf.org/mailman/listinfo/cfrg

---

From: John Mattsson <[email-masked]>
Date: Sat, 5 Nov 2016 09:20:51 +0000

According to the formula in Section 6 of the ECRYPT report [1] on key
lengths, which I think is the state-of-the-art, RSA-1024 offers 73 bit of
security, not 80 bit.

NIST has quite reasonable recommendation [2], and they requirements where
to stop using RSA-1024 no later than 2009.

Section 4 of [3] contains a good analysis on the related problem of
breaking DH-1024. They show that breaking generic DH-1024 in under a year
is plausibly for SIGINTs on the order of hundreds of millions of dollars
(using publicly known cryptanalysis).

Even if RSA-1024 is not currently a super soft spot, it likely to quickly
become one.

[1] http://www.ecrypt.eu.org/ecrypt2/documents/D.SPA.20.pdf

[2] https://www.keylength.com/en/4/

[3] https://weakdh.org/imperfect-forward-secrecy-ccs15.pdf

Cheers,
John