Removing support for RSA keys less than 1023 bits

[Kathleen Wilson]

All,

Is there any reason why NSS should continue to support certificates with
RSA key sizes less than 1023 bits?

According to the EFF SSL Observatory data, the number of certs with key
sizes are:
<=512 4168
<1000 4208
<1023 4208
<1024 5185

Therefore, it would appear that if we were to disallow RSA 512-bit
certs, that we might as well go a step further and disallow RSA keys
less than 1023 bits.

Bugs that we would like to address:
"Disallow RSA 512 and deprecate RSA 1024"
https://bugzilla.mozilla.org/show_bug.cgi?id=360126

"warn about server RSA keys less than 1024 bits"
https://bugzilla.mozilla.org/show_bug.cgi?id=134735

I would appreciate your prompt feedback on this.

Kathleen

[Kathleen Wilson]

Correction:

> Is there any reason why NSS should continue to support certificates with
> RSA key sizes less than 1023 bits?

Should have been:

Is there any reason why Mozilla should continue to support certificates

[Kathleen Wilson]

Also, note v2.0 of Mozilla's CA Certificate Policy:

http://www.mozilla.org/projects/security/certs/policy/MaintenancePolicy.html

"8. We consider the following algorithms and key sizes to be acceptable
and supported in Mozilla products:
-- SHA-1 (until a practical collision attack against SHA-1 certificates
is imminent);
-- SHA-256, SHA-384, SHA-512;
-- Elliptic Curve Digital Signature Algorithm (using ANSI X9.62) over
SECG and NIST named curves P-256, P-384, and P-512;
-- RSA 2048 bits or higher; and
-- RSA 1024 bits (only until December 31, 2013)."

[ianG]

On 2/11/11 10:18 AM, Kathleen Wilson wrote:
> All,

>
> Is there any reason why NSS should continue to support certificates
> with RSA key sizes less than 1023 bits?

Policy should not be done in toolkits. People out there use NSS for
crypto, and RSA keys <1024 are good and useful.

Well, all the reasons why following NIST is a bad idea apply as well,
but at one level down.

> According to the EFF SSL Observatory data, the number of certs with
> key sizes are:
> <=512 4168
> <1000 4208
> <1023 4208
> <1024 5185

Does the EFF trace breaches and damages? We live in a world where the
SSL community is obsessed with the slightest theoretical weakness, yet
20% of the world's users have a password consisting of the name of their
pet.

http://research.microsoft.com/pubs/149885/*WhereDoAllTheAttacksGo*.pdf

> I would appreciate your prompt feedback on this.

-1 from me :) But that's more of a broad-brush security view than NSS
directly.



iang

[Eddy Nigg]

On 11/02/2011 10:50 AM, From ianG:

>
> Policy should not be done in toolkits. People out there use NSS for
> crypto, and RSA keys <1024 are good and useful.
>

Not! There are right now certs out there that were apparently fabricated
with 512 bit RSA keys.

--
Regards

Signer: Eddy Nigg, StartCom Ltd.
XMPP: star...@startcom.org
Blog: http://blog.startcom.org/
Twitter: http://twitter.com/eddy_nigg

[ianG]

On 2/11/11 20:47 PM, Eddy Nigg wrote:
> On 11/02/2011 10:50 AM, From ianG:
>>

>> Policy should not be done in toolkits. People out there use NSS for
>> crypto, and RSA keys <1024 are good and useful.
>>
>

> Not! There are right now certs out there that were apparently
> fabricated with 512 bit RSA keys.
>

Apparently, the world is to end soon. Google shows 196,000,000 references.



iang

[Eddy Nigg]

On 11/02/2011 11:56 AM, From ianG:

> Apparently, the world is to end soon. Google shows 196,000,000
> references.
>

Time and again your comments show to me how to relate to your
contributions here. Thanks.

[ianG]

On 2/11/11 21:09 PM, Eddy Nigg wrote:
> On 11/02/2011 11:56 AM, From ianG:

>> Apparently, the world is to end soon. Google shows 196,000,000
>> references.
>>
>

> Time and again your comments show to me how to relate to your
> contributions here. Thanks.
>

I apologise for being opaque. I shall spell it out: give us some evidence.

iang

[Paul Tiemann]

On Nov 2, 2011, at 2:50 AM, ianG wrote:

> On 2/11/11 10:18 AM, Kathleen Wilson wrote:
>> All,
>>
>> Is there any reason why NSS should continue to support certificates with RSA key sizes less than 1023 bits?
>
>
>

> Policy should not be done in toolkits. People out there use NSS for crypto, and RSA keys <1024 are good and useful.

Do you mean to say that your security policy should not be reflected in toolkits? You could always just set minimums in the default source tree if other people have some special use they think won't be attacked if they use a 512 bit key:

#define MIN_RSA_KEYSIZE 1023

http://www.google.com/search?q=512+bit+rsa+cracked

NSS should be refusing 512 and (probably also) 768 bit RSA keys as unsafe for TLS clients, servers, S/MIME and code signing. An SSL certificate with a small key size could have its private key cracked, and then the certificate could be used for whatever purposes are listed in its keyUsage and extendedKeyUsage.

Does anyone have a reasoned argument for allowing 512 or 768 bit RSA in Firefox and Thunderbird?

Sincerely,

Paul Tiemann
CTO, DigiCert Inc

[ianG]

On 3/11/11 01:39 AM, Paul Tiemann wrote:
> On Nov 2, 2011, at 2:50 AM, ianG wrote:
>
>> On 2/11/11 10:18 AM, Kathleen Wilson wrote:
>>> All,
>>>
>>> Is there any reason why NSS should continue to support certificates with RSA key sizes less than 1023 bits?
>>
>>
>> Policy should not be done in toolkits. People out there use NSS for crypto, and RSA keys<1024 are good and useful.
> Do you mean to say that your security policy should not be reflected in toolkits?

Of course not. My security policy shouldn't be reflected in NSS, nor
should USG's be reflected in my crypto toolkit.

If we did that, we'd end up with lowest common denominator, pdq.

> ....

> Does anyone have a reasoned argument for allowing 512 or 768 bit RSA in Firefox and Thunderbird?

Sure. If the network were internal, or another area where we have
substantial protections in contract and law, the purpose of the crypto
is to be a gate. It matters not how strong the gate is, but that it is
visible. Actually in this context, the fact that it is crackable is an
advantage, following Geer's hypothesis.



iang

[Rob Stradling]

On Wednesday 02 Nov 2011 14:39:53 Paul Tiemann wrote:
> On Nov 2, 2011, at 2:50 AM, ianG wrote:
> > On 2/11/11 10:18 AM, Kathleen Wilson wrote:
> >> All,
> >>
> >> Is there any reason why NSS should continue to support certificates with
> >> RSA key sizes less than 1023 bits?
> >
> > Policy should not be done in toolkits. People out there use NSS for
> > crypto, and RSA keys <1024 are good and useful.
>
> Do you mean to say that your security policy should not be reflected in

> toolkits? You could always just set minimums in the default source tree
> if other people have some special use they think won't be attacked if they
> use a 512 bit key:
>
> #define MIN_RSA_KEYSIZE 1023
>
> http://www.google.com/search?q=512+bit+rsa+cracked
>
> NSS should be refusing 512 and (probably also) 768 bit RSA keys as unsafe
> for TLS clients, servers, S/MIME and code signing. An SSL certificate
> with a small key size could have its private key cracked, and then the
> certificate could be used for whatever purposes are listed in its keyUsage
> and extendedKeyUsage.
>

> Does anyone have a reasoned argument for allowing 512 or 768 bit RSA in
> Firefox and Thunderbird?

HTTPS with a self-certified 512-bit RSA key is no less secure than unencrypted
HTTP traffic.

Perhaps it would be appropriate for Firefox to show a warning (or block the
connection) when it encounters a CA-certified 512-bit RSA key, but I think a
complete ban on 512-bit RSA would be going too far...unless we're planning to
ban unencrypted HTTP as well!

> Sincerely,
>
> Paul Tiemann
> CTO, DigiCert Inc
>

> _______________________________________________
> dev-security-policy mailing list
> dev-secur...@lists.mozilla.org
> https://lists.mozilla.org/listinfo/dev-security-policy

Rob Stradling
Senior Research & Development Scientist
COMODO - Creating Trust Online

[Kyle Hamilton]

On Tue, Nov 1, 2011 at 4:18 PM, Kathleen Wilson <kathle...@yahoo.com> wrote:
> All,
>
> Is there any reason why NSS should continue to support certificates with RSA
> key sizes less than 1023 bits?

Because there are other customers of NSS, and older phones can't support 1024 bit RSA in any reasonable time.

PSM, on the other hand, could be legitimately changed to not support less than 1024 bit RSA.

-Kyle H

[Peter Gutmann]

Paul Tiemann <pa...@digicert.com> writes:

>Does anyone have a reasoned argument for allowing 512 or 768 bit RSA in
>Firefox and Thunderbird?

Opportunistic security. 512-bit RSA everywhere would have stopped Firesheep
before it was even released.

So disallow it by all means if you want, but allow users to configure use of
shorter keys if they like.

Peter.

[Paul Tiemann]

On Nov 2, 2011, at 2:06 PM, Peter Gutmann wrote:

> Paul Tiemann <pa...@digicert.com> writes:
>
>> Does anyone have a reasoned argument for allowing 512 or 768 bit RSA in
>> Firefox and Thunderbird?
>
> Opportunistic security. 512-bit RSA everywhere would have stopped Firesheep
> before it was even released.

Putting future possibilities like opportunistic encryption aside, is it safe to say that no certificate issued by an NSS "built-in" CA should be trusted if it has a 512-bit or 768-bit key?

Firefox would just need to distinguish betweek certificate that were issued by a built-in trust anchor and reject them if they are, since none of these CAs is expected to be issuing certificates with those key sizes today (isn't that also a requirement Mozilla put on CAs, to issue 2048 bit certificates?) It would be a good belt-and-suspenders approach to protect users from both angles: 1) require CAs not to issue 512 bit certs, and 2) don't accept such certs anyhow.

> So disallow it by all means if you want, but allow users to configure use of
> shorter keys if they like.

For other purposes than trusted CA issued certs maybe -- but I don't see a use for letting users override for "built-in" CA issued certs.

Paul

[Peter Gutmann]

Paul Tiemann <pa...@digicert.com> writes:

>Firefox would just need to distinguish betweek certificate that were issued
>by a built-in trust anchor and reject them if they are, since none of these
>CAs is expected to be issuing certificates with those key sizes today (isn't
>that also a requirement Mozilla put on CAs, to issue 2048 bit certificates?)
>It would be a good belt-and-suspenders approach to protect users from both
>angles: 1) require CAs not to issue 512 bit certs, and 2) don't accept such
>certs anyhow.

That'd be a good way to handle it. So self-signed certs for opportunistic
encryption, embedded devices, and home use, would be OK for shorter keys, but
CA-issued ones would need longer keys.

Peter.

[Kyle Hamilton]

On Wed, Nov 2, 2011 at 2:58 PM, Peter Gutmann <pgu...@cs.auckland.ac.nz> wrote:
> That'd be a good way to handle it.  So self-signed certs for opportunistic
> encryption, embedded devices, and home use, would be OK for shorter keys, but
> CA-issued ones would need longer keys.

+1

-Kyle H

[Jeffrey Walton]

1024 bit moduli offer about 80 bits of security. NSA's Suite B minimum
security level is 128 bits (3072-bit moduli). NIST's current
recommendation are 112 bits (2048-bit moduli) in SP 800-57. ECRYPT
tends to follow NIST (http://www.ecrypt.eu.org/documents/D.SPA.
13.pdf). Lenstra (et al) tell us 1024 bit keys are good through 2014
with a small amount of risk (https://documents.epfl.ch/users/l/le/
lenstra/public/papers/ecdl2.pdf).

CA keys are high value and long term, and 1023 does not make me fell
comfortable - I would prefer to see 1536 or 2048.

Here's another problem I am seeing in the field: I recently purchased
two certificates with a security level of 128 bits (3072-bit modulus).
I presumed that some users might prefer AES-128, and needed a matching
security level for key transport. My certificates were signed by the
CA with SHA-1/RSA-1024, which is well below my security levels. Put
another way, my adversaries will not try to break my 3072-bit modulus;
they will go after the CA's weaker 1024-bit modulus. Its especially
appealing since the CA's key does not change often, and service a
number of certificates.

Take aways: (1) 1024 is a bit low for long term, high value keys; and
(2) CAs are not properly matching security levels, effectively
creating a security vulnerability in the resulting system.

Jeff

[Peter Gutmann]

Jeffrey Walton <nolo...@gmail.com> writes:

>Here's another problem I am seeing in the field: I recently purchased two
>certificates with a security level of 128 bits (3072-bit modulus). I presumed
>that some users might prefer AES-128, and needed a matching security level
>for key transport. My certificates were signed by the CA with SHA-1/RSA-1024,
>which is well below my security levels. Put another way, my adversaries will
>not try to break my 3072-bit modulus; they will go after the CA's weaker 1024-
>bit modulus. Its especially appealing since the CA's key does not change
>often, and service a number of certificates.

This is just another example of the security numerology that's discussed in
the article that Ian Grigg posted a reference to recently. No-one will ever
go after "the CA's weaker 1024-bit modulus". They'll go after the CA, the
bugs in the PKI software, the awful security UI, the two dozen buffer
overflows in the app you're using, the 0day in your OS, and absolutely
anything but the CA's 1024-bit modulus. Thinking about threats purely in
terms of public-key sizes is pure numerology, and until we can get away from
this fixation with numerology it's very difficult to hold a sensible
discussion about the issue.

Peter.

[Tom Lowenthal]

That said, it is much preferable to force adversaries to use
side-channel attacks rather than having both our system *and* our
cryptography vulnerable.

[ianG]

Hi Jeffrey and Peter

On 4/11/11 23:06 PM, Jeffrey Walton wrote:
> Unfortunately, I could not locate the post. I did come across "The
> Curse of Cryptographic Numerology", but I don't have an IEEE or ACM
> membership to fetch the paper.

Apologies, the post was not a post, but an offlist mail. I've since put
up a copy of the document on this page:
http://iang.org/ssl/

I'm not sure if it is permitted to post it or not; I recall authors are
allowed to post a copy on their personal pages ... if this works it will
remain there.

Peter, is that the latest version? Something about it makes me think it
is an earlier draft.

>> No-one will ever
>> go after "the CA's weaker 1024-bit modulus". They'll go after the CA, the
>> bugs in the PKI software, the awful security UI, the two dozen buffer

>> overflows in the app you're using, the 0day in your OS...
> Agreed.

>
>> Thinking about threats purely in
>> terms of public-key sizes is pure numerology, and until we can get away from
>> this fixation with numerology it's very difficult to hold a sensible
>> discussion about the issue.

> Its not so much fixation, but honoring or observing best practice. My
> chances of dying in a car accident are slim to none, but I still wear
> a seat belt.

Seat belts are informed by empirical research showing frequent events
with & without. Although controversial (there are some safety
mechanisms like bike helmets that are allegedly worse than the
alternate) there are statistics about what happens with & without, and
we can have that debate, and decide on the costs.

In PKI we don't have that. Or we ignore that 99% of traffic is
successfully completed and unchallenged over HTTP ... Or we come up with
another way to avoid informed discussion (bad marks on both sides:
http://financialcryptography.com/mt/archives/001341.html ).

> I don't want to ship a negligent implementation because other parts of
> the system are defective. That sounds a lot like "let's all jump off
> the cliff together". In fact, I often cannot because I frequently work
> in US Federal and I am governed by NIST and their Special Publications
> (et al).

Right. So, you do "their practices" a.k.a. compliance.

Calling it best practices requires you to leap of that cliff with them,
faith wise :) I am reminded of the US banking community's "best
practices" in dealing with account fraud, another superlative example of
the race to the bottom.

Another way to look at this is the concept of core business. A
corollary in core business is that you never outsource your core. So if
you are doing something whereby security is considered part of your core
.. outsourcing it to a NIST sp* isn't a smart move.

In this theory, "selling to Federal" would be considered your core
business. So it is fine, if that's what you do. So you follow NIST,
which is for US Federal. Simple.

> To play devils advocate: suppose there are no other weaknesses for an
> attacker to leverage. Would it then be appropriate to observe security
> levels?

Well, yes, absolutely. If we could organise the world of attackers to
respect our security model and attack it, and organise the world of
users and suppliers to follow our security model, and eliminate
violence, false marketing claims, and fly-by-night, and 1000 other human
behaviours ... then a classical MITM against crypto might surface to be
the only way for an attacker to take users' value.

The problem occurs when we don't eliminate those things, concentrate all
our energies in dealing with a tiny subset of possibilities, and then
declare that we have secured the user. Then, we're negligent at a
professional level, if not at a standards/compliance level (*).



iang


(*) however this is changing. BR requires risk analysis. This will
eventually find its way to the vendors.