Subject: [Cfrg] 1024 bit RSA

From: "Erik Andersen" <[email-masked]>
Date: Fri, 4 Nov 2016 16:29:54 +0100

I participate in IT smart grid standardization within IEC TC57 WG15. A
couple of standards under development still allow 1024 bit RSA keys for
so-called backward compatibility. I have so far not been able to change
that. My question is now. Is there any information available for how long
time or how much effort it takes to break  a 1024 bit RSA key?

Erik

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Fri, 4 Nov 2016 11:50:58 -0400

I think the informal position would be that it is still beyond the
capabilities of parties using public resources and methods but nobody would
be in the least surprised if the big SIGINT agencies like NSA and GCHQ were
breaking them.

The longest RSA challenge factored was RSA 768 in 2009:

https://en.wikipedia.org/wiki/RSA_Factoring_Challenge

RSA 704 was broken this year which shows people are still active. That
effort looks like the type of thing you would do before a challenge on
RSA896 which I expect to fall before 2020.

So expect RSA 1024 to certainly fall by 2030 and probably by 2025.

On Fri, Nov 4, 2016 at 11:29 AM, Erik Andersen <[email-masked]> wrote:

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

---

From: Derek Atkins <[email-masked]>
Date: Fri, 04 Nov 2016 12:33:46 -0400

"Erik Andersen" <[email-masked]> writes:

> I participate in IT smart grid standardization within IEC TC57 WG15. A couple
> of standards under development still allow 1024 bit RSA keys for so-called
> backward compatibility. I have so far not been able to change that. My
> question is now. Is there any information available for how long time or how
> much effort it takes to break  a 1024 bit RSA key?

Just remember that RSA1024 provides approximately 80 bits of security.
As Phill mentioned that's currently out of the range of public
resources, but probably not SIGINT.

What symmetric ciphers are they using?  If they're using AES-128, then I
would ask why they would support a key agreement/signature that's less
secure?  Getting 128-bit public key security is rather straightforward
these days, even in pretty small systems.

> Erik

-derek
-- 
       Derek Atkins                 617-623-3745
       [email-masked]             www.ihtfp.com
       Computer and Internet Security Consultant

---

From: Paul Grubbs <[email-masked]>
Date: Fri, 4 Nov 2016 15:37:06 -0400

Recall also that any cryptanalytic advances that improve the asymptotic
complexity of factoring could cause 1024-bit keys to fall much sooner than
2025.

On Fri, Nov 4, 2016 at 12:33 PM, Derek Atkins <[email-masked]> wrote:

> couple

---

From: Hanno Böck <[email-masked]>
Date: Sat, 5 Nov 2016 14:17:54 +0100

On Fri, 4 Nov 2016 16:29:54 +0100
"Erik Andersen" <[email-masked]> wrote:

> couple of standards under development still allow 1024 bit RSA keys
> for so-called backward compatibility. I have so far not been able to
> change that. My question is now. Is there any information available
> for how long time or how much effort it takes to break  a 1024 bit
> RSA key?

Dan Bernstein has made some estimates about the costs of breaking 1024
bit a while ago in a talk:
https://www.youtube.com/watch?v=IuSnY_O8DqQ
He thinks that large botnets may be capable of doing it.

Also to be considered for the attack scenario is that one can break
multiple keys at once (batch-nfs by bernstein/lange), which changes the
economics of an attack quite a bit:
https://eprint.iacr.org/2014/921

One can probably conclude that attacking 1024 bit rsa is still a very
expensive attack. However one should also ask the other question: What
is the cost of using a stronger algorithm? I usually tend to have the
opinion that we know how to get the basic algorithms right in a way
that it's completely infeasible to break them. So let's just use secure
algorithms and then use our energy bother about all the other things
that can go wrong (next thing up the stack would be "don't use PKCS #1
1.5" and "don't use e=3").

So rather than asking "is rsa 1024 bit secure enough?" I'd ask "is
there any significant cost in using rsa 2048?". The performance impact
for most applications is almost irrelevant these days.
You cite "backwards compatibility" as a reason, but that's not very
specific. Is there a large deployment of devices that only support
1024 bit rsa? If yes then why is that? Are they really old (pre 2003)?
The major warnings against rsa 1024 came in 2003, so if the devices
are newer than 2003 and only support rsa 1024 then they have been
shipped with substandard crypto (which is quite common, but still bad).
If that's the case then I'd conclude that there is an underlying problem
and the call for rsa 1024 is just a symptom of that (and I'd also
assume that these devices are probably using other crypto constructions
that are scarier than rsa 1024).

-- 
Hanno Böck
https://hboeck.de/

mail/jabber: [email-masked]
GPG: FE73757FA60E4E21B937579FA5880072BBB51E42

---

From: "Erik Andersen" <[email-masked]>
Date: Sat, 5 Nov 2016 14:35:07 +0100

My best guess is that some vendor with a major voice in the standard organizations have products that due to a bad design cannot be easily upgraded to a stronger algorithm.

This proves to me that it wrong to leave the IT standardization to vendors.

Erik

-----Oprindelig meddelelse-----
Fra: Cfrg [mailto:[email-masked]] På vegne af Hanno Böck
Sendt: 05 November 2016 14:18
Til: [email-masked]
Emne: Re: [Cfrg] 1024 bit RSA

On Fri, 4 Nov 2016 16:29:54 +0100
"Erik Andersen" <[email-masked]> wrote:

> for how long time or how much effort it takes to break  a 1024 bit RSA 
> key?

Dan Bernstein has made some estimates about the costs of breaking 1024 bit a while ago in a talk:
https://www.youtube.com/watch?v=IuSnY_O8DqQ
He thinks that large botnets may be capable of doing it.

Also to be considered for the attack scenario is that one can break multiple keys at once (batch-nfs by bernstein/lange), which changes the economics of an attack quite a bit:
https://eprint.iacr.org/2014/921

One can probably conclude that attacking 1024 bit rsa is still a very expensive attack. However one should also ask the other question: What is the cost of using a stronger algorithm? I usually tend to have the opinion that we know how to get the basic algorithms right in a way that it's completely infeasible to break them. So let's just use secure algorithms and then use our energy bother about all the other things that can go wrong (next thing up the stack would be "don't use PKCS #1 1.5" and "don't use e=3").

So rather than asking "is rsa 1024 bit secure enough?" I'd ask "is there any significant cost in using rsa 2048?". The performance impact for most applications is almost irrelevant these days.
You cite "backwards compatibility" as a reason, but that's not very specific. Is there a large deployment of devices that only support
1024 bit rsa? If yes then why is that? Are they really old (pre 2003)?
The major warnings against rsa 1024 came in 2003, so if the devices are newer than 2003 and only support rsa 1024 then they have been shipped with substandard crypto (which is quite common, but still bad).
If that's the case then I'd conclude that there is an underlying problem and the call for rsa 1024 is just a symptom of that (and I'd also assume that these devices are probably using other crypto constructions that are scarier than rsa 1024).

--
Hanno Böck
https://hboeck.de/

---

From: Peter Gutmann <[email-masked]>
Date: Sat, 5 Nov 2016 14:43:15 +0000

Hanno Böck <[email-masked]> writes:

>expensive attack. However one should also ask the other question: What is the
>cost of using a stronger algorithm?

Yup, and in combination with that, what's being protected/what's your threat
model?  The example I've used on a number of occasions is a 512-bit key being
used with a system that turns a ventilator on and off (details fudged slightly
to make the actual item non-recognisable to the company running it :-).  The
system is old (meaning it's a current product but the hardware was designed
in... not sure, late 90s I think, or maybe earlier), it can't handle keys
larger than 512-bit (heck, it struggles with 512-bit keys), and even using a
512-bit key is complete overkill, AFAICT the motivation for it is some sort of
checklist-compliance for the auditors, "yes we use crypto", rather than a need
to protect it from anything (the crypto was a later addition, some time
post-2000).

It's easy enough for people operating in splendid isolation from real life to
say "we should all be using [insert chosen numerology here]-sized keys for
everything all the time", but in practice it depends on a whole pile of
factors, of which "what theoretical strength in bits do we need" is several
steps down the list behind "how much will it cost", "what can the hardware
cope with", "what are we protecting", "what's the risk", and several others.

Peter.

---

From: Peter Gutmann <[email-masked]>
Date: Sat, 5 Nov 2016 14:50:13 +0000

>This proves to me that it wrong to leave the IT standardization to vendors.

I could say the same thing about cryptographers.  Both are in fact true,
because you don't want to leave standardisation to just one single group, you
need input based on both strong theoretical analysis and real-world experience
and considerations.

Unfortunately this very rarely happens, so you get the unfortunate situation
where the theory guys look over at the vendors and say "look at the mess
they're making of our fine design" and the vendors look at the theory guys and
say "this stuff doesn't do what we need, we'll have to come up with our own
way of doing it".

There's an IEC standard in the works that's a prime illustration of the latter
point...

Peter.

---

From: Hanno Böck <[email-masked]>
Date: Sat, 5 Nov 2016 16:02:52 +0100

On Sat, 5 Nov 2016 14:35:07 +0100
"Erik Andersen" <[email-masked]> wrote:

> My best guess is that some vendor with a major voice in the standard
> organizations have products that due to a bad design cannot be easily
> upgraded to a stronger algorithm.

My guess as well. Something very similar happened in the TLS working
group. Some anonymous vendor let us know that we shouldn't enforce
RSA-PSS because they have a large deployment of devices not capable of
doing that. The working group fortunately didn't follow that request.

The very first thing I'd ask for here is transparency: What device,
which vendor, why was it shipped with substandard crypto?

> This proves to me that it wrong to leave the IT standardization to

Well, they should certainly take part in the discussion. But it's
important to communicate to them that:
a) if they ship substandard crypto it's their fault.
b) they should fix their development process to avoid that in the
future.

-- 
Hanno Böck
https://hboeck.de/