Appropriate role for lists of algorithms and key sizes

[Gervase Markham]

A discussion inspired by
https://github.com/mozilla/pkipolicy/issues/5

Should Mozilla's root store policy contain any list of approved and/or
disapproved algorithms/key sizes, or not? Possible positions include at
least:

0) No; what algorithms and/or key sizes are supported by Firefox and/or
NSS is a decision for the hackers on those projects. There's no need for
a separate policy about it.

1) No; the Baseline Requirements, section 6.1.5, specify a set of
algorithms and key sizes:
https://cabforum.org/wp-content/uploads/CA-Browser-Forum-BR-1.4.2.pdf .
If Mozilla's list is the same, there is no point; if it's different, you
just end up with the intersection.

2) Yes; we should have a list of banned algorithms and/or key sizes
which are weak and therefore dangerous for the web PKI, so we can use
the power of the policy to force them out of the system. But if an
algorithm or key size is not actively dangerous, anything else should be
permitted.

3) Yes; there are advantages such as interoperability (what else?) to
Mozilla using the power of the policy to define what algorithms and/or
key sizes are acceptable in the Web PKI; as long as we keep the list
under review, this is a good thing.

Thoughts?

Gerv

[Richard Barnes]

My gut reaction is 0+1, maybe 2.

- The CAB Forum should specify the overall envelope of what is acceptable
in the Web PKI
- Firefox will enforce restrictions that are mores strict than the BRs
requirements

If we do (2), then this will just be a three level hierarchy, with BRs <
Mozilla Policy < Firefox.

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

[Rob Stradling]

On 24/01/17 16:26, Richard Barnes wrote:
> My gut reaction is 0+1, maybe 2.
>
> - The CAB Forum should specify the overall envelope of what is acceptable
> in the Web PKI
> - Firefox will enforce restrictions that are mores strict than the BRs
> requirements

The BRs say that SHA-1 has been unacceptable in the Web PKI since Jan
1st 2017. Firefox did not enforce that deadline, but instead set a
later deadline. I'd call that *less* strict than the BRs. Wouldn't you?

EdDSA certificate signatures will be with us soon. Is it conceivable
that Mozilla might want to ship and enable EdDSA certificate signature
code before the BRs have been updated to declare that EdDSA is
acceptable in the Web PKI? If so, then that would also be *less* strict
than the BRs.

--
Rob Stradling
Senior Research & Development Scientist
COMODO - Creating Trust Online
Office Tel: +44.(0)1274.730505
Office Fax: +44.(0)1274.730909
www.comodo.com

COMODO CA Limited, Registered in England No. 04058690
Registered Office:
3rd Floor, 26 Office Village, Exchange Quay,
Trafford Road, Salford, Manchester M5 3EQ

This e-mail and any files transmitted with it are confidential and
intended solely for the use of the individual or entity to whom they are
addressed. If you have received this email in error please notify the
sender by replying to the e-mail containing this attachment. Replies to
this email may be monitored by COMODO for operational or business
reasons. Whilst every endeavour is taken to ensure that e-mails are free
from viruses, no liability can be accepted and the recipient is
requested to use their own virus checking software.

[Ryan Sleevi]

I mostly agree with Richard's sentiments - that is, the BRs are likely to
be more liberal than what Mozilla may want - but not sure how 0/1 falls out
from that.

I think 2/3 are implemented the same, just different expressions of 'why' -
and I think both reasons are valid. That is, Mozilla may want to discourage
some keys because they're weak - OR because they cause interoperability
issues.

I'm not sure that it's a three-level hierarchy - that is, I don't think
you'd want to have a situation where Mozilla Policy != Firefox, if
anything, because of interoperability concerns.

This means, as a practical matter, I strongly agree with Brian Smith's
suggestion of having an explicit, enumerated list of algorithms (and
parameters) in the Mozilla policy, with the caveat/expectation that Mozilla
policy will be able to be updated in a timely fashion w/r/t this section if
need be.

On Tue, Jan 24, 2017 at 8:26 AM, Richard Barnes <rba...@mozilla.com> wrote:

> My gut reaction is 0+1, maybe 2.
>
> - The CAB Forum should specify the overall envelope of what is acceptable
> in the Web PKI
> - Firefox will enforce restrictions that are mores strict than the BRs
> requirements
>

[Jeremy Rowley]

Why not just make the changes at the CAB Forum? That's the purpose of the
CAB Forum afterall - to discuss these policies. Seems like it would be
better to add restrictions there first before creating a separate policy.

[Gervase Markham]

On 24/01/17 17:12, Ryan Sleevi wrote:
> This means, as a practical matter, I strongly agree with Brian Smith's
> suggestion of having an explicit, enumerated list of algorithms (and
> parameters) in the Mozilla policy, with the caveat/expectation that Mozilla
> policy will be able to be updated in a timely fashion w/r/t this section if
> need be.

You believe that such a scheme would definitely be better than a "delta"
scheme where the Mozilla policy said: "We allow what's in the BRs, but
with the removal of option X and the addition of option Y"?

Gerv

[Ryan Sleevi]

On Wed, Jan 25, 2017 at 3:21 AM, Gervase Markham <ge...@mozilla.org> wrote:

> On 24/01/17 17:12, Ryan Sleevi wrote:

> > This means, as a practical matter, I strongly agree with Brian Smith's
> > suggestion of having an explicit, enumerated list of algorithms (and
> > parameters) in the Mozilla policy, with the caveat/expectation that
> Mozilla
> > policy will be able to be updated in a timely fashion w/r/t this section
> if
> > need be.
>

> You believe that such a scheme would definitely be better than a "delta"
> scheme where the Mozilla policy said: "We allow what's in the BRs, but
> with the removal of option X and the addition of option Y"?
>

Yes, I think it results in a clearer communication that is otherwise
identical, and ensures that there is community consensus on policy changes
:)

[Gervase Markham]

On 25/01/17 17:55, Ryan Sleevi wrote:
> Yes, I think it results in a clearer communication that is otherwise
> identical, and ensures that there is community consensus on policy changes
> :)

Draft of new Maintenance Policy section, bullet 8:

We consider the following algorithms and key sizes to be acceptable in
root certificates in our root program, and in any certificate which
chains up to them:

* RSA keys with a minimum modulus size of 2048 bits
* ECDSA keys using one of the named curves: P‐256, P‐384, or P‐521
* Digest algorithms: SHA-256, SHA-384, or SHA-512

(This would then be a good place to put the final text of our SHA-1
policy, which is being hashed out in another thread and which permits
SHA-1 under certain specific non-server-auth circumstances.)


Open questions:

1) Do we support P-521? Our current policy says we do, although it's
mis-identified as P-512, but the previous discussion of this suggested
that we don't.

2) Brian has also suggested we mandate a matching of ECDSA curves with
digest algorithms. Do we want to do that?

3) Do we want to add Ed25519?

4) Do we want to do the spec using AlgorithmIdentifiers instead of free
text? Aren't AlgorithmIdentifiers used for something a bit different?

Gerv

[Jakob Bohm]

On 27/01/2017 12:47, Gervase Markham wrote:
> On 25/01/17 17:55, Ryan Sleevi wrote:
>> Yes, I think it results in a clearer communication that is otherwise
>> identical, and ensures that there is community consensus on policy changes
>> :)
>
> Draft of new Maintenance Policy section, bullet 8:
>
> We consider the following algorithms and key sizes to be acceptable in
> root certificates in our root program, and in any certificate which
> chains up to them:
>
> * RSA keys with a minimum modulus size of 2048 bits
> * ECDSA keys using one of the named curves: P‐256, P‐384, or P‐521
> * Digest algorithms: SHA-256, SHA-384, or SHA-512
>
> (This would then be a good place to put the final text of our SHA-1
> policy, which is being hashed out in another thread and which permits
> SHA-1 under certain specific non-server-auth circumstances.)
>
>
> Open questions:
>
> 1) Do we support P-521? Our current policy says we do, although it's
> mis-identified as P-512, but the previous discussion of this suggested
> that we don't.
>
> 2) Brian has also suggested we mandate a matching of ECDSA curves with
> digest algorithms. Do we want to do that?
>

DSA and ECDSA signatures are only secure if the hash algorithm is
specified in the certificate, presumably as part of the
AlgorithmIdentifier in the SubjectPublicKeyInfo. This is because
signatures made using DSA/ECDSA do not incorporate the identity/name of
the hash algorithm in the signature in a way which prevents a signature
on e.g. "SHA-256=0123456" from being accepted as a signature on e.g.
"MD2=0123456".

> 3) Do we want to add Ed25519?
>
> 4) Do we want to do the spec using AlgorithmIdentifiers instead of free
> text? Aren't AlgorithmIdentifiers used for something a bit different?

AlgorithmIdentifiers are the precise OID-based way in which
certificates refer to signing algorithms (among others). Historically
there were multiple competing AlgorithmIdentifiers assigned to some of
the popular algorithms (such as RSA signing with SHA1).

Thus for interoperability, it is usueful to state which identifiers may
be used to refer to each of the permitted algorithm pairs (such as "RSA
PKCS#1 v1.5 signatures with SHA-256").

For some algorithms (including, again, RSA) there are usually two
different identifiers: One that refers to the public key type alone
("RSA") and one which referes to the full type of a signature ("RSA
PKCS#1 v1.5 with SHA-256"). This is typically done where there is no
security downside to using the same certificate and public key with
different hash algorithms, padding schemes etc.




Enjoy

Jakob
--
Jakob Bohm, CIO, Partner, WiseMo A/S. https://www.wisemo.com
Transformervej 29, 2860 Søborg, Denmark. Direct +45 31 13 16 10
This public discussion message is non-binding and may contain errors.
WiseMo - Remote Service Management for PCs, Phones and Embedded

[Ryan Sleevi]

On Fri, Jan 27, 2017 at 3:47 AM, Gervase Markham <ge...@mozilla.org> wrote:
>
> * RSA keys with a minimum modulus size of 2048 bits
>

Nits and niggles: Perhaps 2048, 3072, 4096?

- 8K RSA keys cause Web PKI interop problems
- RSA keys that aren't modulo 8 create interop problems

> 2) Brian has also suggested we mandate a matching of ECDSA curves with
> digest algorithms. Do we want to do that?
>

Yes, ideally. Jakob's reply confused the issue, but it's not ideal to see
P-521 with SHA-256, for example.

> 3) Do we want to add Ed25519?
>

No. This was discussed at the CA/Browser Forum meeting in Seattle. Although
you have RFC 8032, you're still missing the appropriate assignments
relative to PKIX (which a separate draft was working on). You also have the
issue that the BRs currently require that the CA's private key be stored in
an appropriately protected HSM, but the specifications for the HSMs (FIPS
140-2 level 3 or CC EAL equivalent) don't allow the use of Ed25519.

> 4) Do we want to do the spec using AlgorithmIdentifiers instead of free
> text? Aren't AlgorithmIdentifiers used for something a bit different?
>

There's the AlgorithmIdentifier of the key, and the AlgorithmIdentifier of
the signature produced with that key. For the key, you can allow something
like P-256, but for the signature, you want to restrict it to P-256 with
SHA-256.

This is similar to identifying the key as rsaEncryption, but the signature
as sha1withRSAEncryption.

Which aspect were you thinking of?

[Peter Gutmann]

Jakob Bohm <jb-mo...@wisemo.com> writes:

>DSA and ECDSA signatures are only secure if the hash algorithm is specified
>in the certificate, presumably as part of the AlgorithmIdentifier in the
>SubjectPublicKeyInfo.

It's in the (badly-named) signature field of the cert, if it was in the
signatureAlgorithm it wouldn't be covered by the sig. Having said that, I
don't know how many implementations actually check whether what's in the
signature corresponds to the signatureAlgorithm, I tried it many years ago
(md5With... vs sha1With...) and nothing much seemed to notice, as long as the
signatureAlgorithm was the one that was correct for the signature.

Peter.

[Kurt Roeckx]

At least OpenSSL changed this, CVE-2014-8275.


Kurt

[Gervase Markham]

On 27/01/17 18:53, Ryan Sleevi wrote:
> There's the AlgorithmIdentifier of the key, and the AlgorithmIdentifier of
> the signature produced with that key. For the key, you can allow something
> like P-256, but for the signature, you want to restrict it to P-256 with
> SHA-256.
>
> This is similar to identifying the key as rsaEncryption, but the signature
> as sha1withRSAEncryption.

If we want to use AlgorithmIdentifiers, can someone point me at a list
of them, and ideally give me a subset which matches what the current
text says in English?

Gerv

[Jakob Bohm]

Actually, it is more fundamental than that. Using a compromised hash
(such as MD2) over a data item that contains the identifier "MD2", does
not require the signature made on the MD2 value to actually indicate
that it is a signature on an MD2 value.

An (EC)DSA signature signs a "hash value" disembodied from the identity
of that hash algorithm. Thus a signature on an SHA-3-256 value M is an
equally valid signatue on a CRAP-256 value M, and thus on anything that
can (through the insecurity of the hypothetical CRAP algorithm) be made
to have that hash value, including messages saying that this signature
is supposed to be made with the CRAP algorithm.

Therefore, an (EC)DSA public key must specify both the group parameters
(such as P-521) AND the hash algorithm in order to be fully specified.

In contrast the PKCS#1 RSA signature formats do include the hash
algorithm identifier separately from the hash value, thus allowing safe
use of a SHA-512 certified RSA key to sign an SHA-256 hash value as
part of a protocol exchange.

Surprised you didn't know that, considering who you are.

[Peter Gutmann]

Jakob Bohm <jb-mo...@wisemo.com> writes:

>Surprised you didn't know that, considering who you are.

Uhh, I did know that, that's why I checked it about 15-odd years ago to see if
anything would notice if it was done wrong (I can't remember the exact date,
it was when I was still updating the X.509 Style Guide so around 1999 or
2000). At the time, it was OK with DLP sigs as well since the only thing that
was allowed was DSA + SHA-1, and obviously PKCS #1 was fine too, it was 9796-2
certs that had problems, but then they were barely used by anyone except some
European banks.

Now, we have ECDSA, which not only has this problem in spades but even has a
requirement (X9.62) to truncate the hash to fit the group order. So you can
swap in any hash you want (that's specified for use with ECDSA) and standards-
compliant code will helpfully adjust it for you to make sure the attack works.
Certs protect against this (assuming the code checks the signature vs.
signatureAlgorithm), but generalised signing doesn't, e.g. with both PGP and
CMS / S/MIME the hash function identifier isn't an authenticated attribute.
This is why CMS authenticated-enveloped-data MACs the
EncryptedContentInfo.ContentEncryptionAlgorithmIdentifier, so you can't
manipulate the algorithm parameters:

The EncryptedContentInfo.ContentEncryptionAlgorithmIdentifier must be
protected alongside the encrypted content; otherwise, an attacker
could manipulate the encrypted data indirectly by manipulating the
encryption algorithm parameters, which wouldn't be detected through
MACing the encrypted content alone. For example, by changing the
encryption IV, it's possible to modify the results of the decryption
after the encrypted data has been verified via a MAC check.

The test vectors then say:

For the triple DES-encrypted data, corrupting a byte at positions
192-208 can be used to check that payload-data corruption is
detected, and corrupting a byte at positions 168-174 can be used to
check that metadata corruption is detected.

to make sure that the code to check for problems is working as required.

Peter.

[Jakob Bohm]

On 30/01/2017 14:24, Peter Gutmann wrote:
> Jakob Bohm <jb-mo...@wisemo.com> writes:
>
>> Surprised you didn't know that, considering who you are.
>
> Uhh, I did know that, that's why I checked it about 15-odd years ago to see if
> anything would notice if it was done wrong (I can't remember the exact date,
> it was when I was still updating the X.509 Style Guide so around 1999 or
> 2000). At the time, it was OK with DLP sigs as well since the only thing that
> was allowed was DSA + SHA-1, and obviously PKCS #1 was fine too, it was 9796-2
> certs that had problems, but then they were barely used by anyone except some
> European banks.

This changed the moment SHA-2 came out, though one could interpret that
the length of the signature elements would uniquely indicate the SHA
variant. With SHA-256/160 and SHA-3, that is completely gone as there
are now two SHA hash algorithms for each length. Plus any non-FIPS
hash used outside FIPS-restricted contexts.

>
> Now, we have ECDSA, which not only has this problem in spades but even has a
> requirement (X9.62) to truncate the hash to fit the group order. So you can
> swap in any hash you want (that's specified for use with ECDSA) and standards-
> compliant code will helpfully adjust it for you to make sure the attack works.
> Certs protect against this (assuming the code checks the signature vs.
> signatureAlgorithm),

Doesn't help if the wrong hash algorithm is insecure enough to produce
a "second" preimage that includes the name of that wrong hash algorithm.

[Peter Gutmann]

Jakob Bohm <jb-mo...@wisemo.com> writes:

>This changed the moment SHA-2 came out, though one could interpret that the
>length of the signature elements would uniquely indicate the SHA variant.
>With SHA-256/160 and SHA-3, that is completely gone as there are now two SHA
>hash algorithms for each length. Plus any non-FIPS hash used outside FIPS-
>restricted contexts.

Thus the obvious lesson, "don't implement weirdo hash algorithms" (or more
than the minimum you need), although as I pointed out, even though no-one
should be using crazy stuff like SHA-256/160, X9.62 gives you that whether you
actually implement it or not. Even if you only support the universal-standard
SHA-1 and SHA-256 (and nothing else), you're still vulnerable.

Mind you I wonder how serious it really is, since you're signing with e.g. the
full 256 bits from SHA-256 but verifying with only 160 bits from SHA-1 it's a
lot more work than just finding a collision, you'd have to find a situation
where SHA-1( m ) x c mod n == SHA-256( m ) x c mod n, not just where SHA-1 ==
trunc160( SHA-256 ).

Peter.

[Hubert Kario]

On Saturday, 28 January 2017 06:51:10 CET Peter Gutmann wrote:
> Jakob Bohm <jb-mo...@wisemo.com> writes:

> >DSA and ECDSA signatures are only secure if the hash algorithm is specified
> >in the certificate, presumably as part of the AlgorithmIdentifier in the
> >SubjectPublicKeyInfo.
>
> It's in the (badly-named) signature field of the cert, if it was in the
> signatureAlgorithm it wouldn't be covered by the sig. Having said that, I
> don't know how many implementations actually check whether what's in the
> signature corresponds to the signatureAlgorithm, I tried it many years ago
> (md5With... vs sha1With...) and nothing much seemed to notice, as long as
> the signatureAlgorithm was the one that was correct for the signature.

I've tested it for TLS signatures[1], and OpenSSL, NSS and GnuTLS do match the
sig alg with the hash info structure in the actual signature.

1 - https://github.com/tomato42/tlsfuzzer/blob/master/scripts/test-certificate-verify-malformed-sig.py
--
Regards,
Hubert Kario
Senior Quality Engineer, QE BaseOS Security team
Web: www.cz.redhat.com
Red Hat Czech s.r.o., Purkyňova 99/71, 612 45, Brno, Czech Republic

[Hubert Kario]

[Patrick Figel]

On 27/01/2017 19:53, Ryan Sleevi wrote:
> On Fri, Jan 27, 2017 at 3:47 AM, Gervase Markham <ge...@mozilla.org> wrote:
>>
>> * RSA keys with a minimum modulus size of 2048 bits
>>
>
> Nits and niggles: Perhaps 2048, 3072, 4096?
>
> - 8K RSA keys cause Web PKI interop problems
> - RSA keys that aren't modulo 8 create interop problems

It looks like a number of CAs currently accept RSA keys with modulus
sizes != (2048, 3072, 4096). Censys currently finds 21,150 EE certs[1].
Does it make more sense to explicitly add the mod 8 requirement to the
policy in this case, while allowing anything >= 2048 <= 4096?

[1]:
https://censys.io/certificates?q=current_valid_nss%3A+true+and+parsed.subject_key_info.key_algorithm.name%3A+RSA+not+parsed.subject_key_info.rsa_public_key.length%3A+%282048+or+3092+or+4096%29&page=1

[Tom]

Why the 4096 limit?

https://rsa8192.badssl.com/ work well, and if somebody wish a
certificate with that size of key (or even bigger), why refusing it?

ECC certificates are allowed but cause a lot of PKI interop problems
too. That's not a reason for refusing it.

[Patrick Figel]

On 07/02/2017 08:11, Tom wrote:
> Le 07/02/2017 à 05:01, Patrick Figel a écrit :

> Why the 4096 limit?
>
> https://rsa8192.badssl.com/ work well, and if somebody wish a
> certificate with that size of key (or even bigger), why refusing it?
>
> ECC certificates are allowed but cause a lot of PKI interop problems
> too. That's not a reason for refusing it.

It's not quite the same thing - web servers can detect ECC support
through the signature_algorithms TLS client hello extension and fall
back to a RSA cert if needed. Clients don't announce the maximum key
size they support that way, so that wouldn't be possible (some fancy
client hello fingerprinting to detect the client/UA might work, but that
would be rather complex).

There are about 2k RSA certs with a key size > 4096 out there (and < 100
with > 8192). I don't personally see the need for > 4096, but don't feel
very strongly about that, so if most of the ecosystem does indeed
support 8192, I'd be fine with that limit too.

[Gervase Markham]

On 24/01/17 21:34, Jeremy Rowley wrote:
> Why not just make the changes at the CAB Forum? That's the purpose of the
> CAB Forum afterall - to discuss these policies. Seems like it would be
> better to add restrictions there first before creating a separate policy.

Mozilla's policy is wider in scope than e.g. the BRs - for example, it
covers email certs.

Please comment in the new thread if you think the current draft is
overly-restrictive, and why.

Gerv

[Gervase Markham]

On 27/01/17 18:53, Ryan Sleevi wrote:

> Nits and niggles: Perhaps 2048, 3072, 4096?
>
> - 8K RSA keys cause Web PKI interop problems
> - RSA keys that aren't modulo 8 create interop problems

This raises the question if, should our approach to interop problems be:

a) We ban anything which Firefox doesn't and won't ever support
b) We ban anything we think enough clients don't support that there'll
be problems
c) We let CAs and the market decide what works

Requiring them to be modulo 8 seems to be hardly a significant
restriction, but making them max 4096 seems like a bigger one. As
Firefox supports 8192, I don't see a reason to ban it. So I guess I'm in
favour of a).

>> 4) Do we want to do the spec using AlgorithmIdentifiers instead of free
>> text?

If someone wants it phrased this way, I need draft text. Otherwise it'll
be staying the way it is :-)

I've posted a proposal as a new thread.

Gerv

[Ryan Sleevi]

On Tue, Feb 7, 2017 at 9:45 AM, Gervase Markham <ge...@mozilla.org> wrote:

> >> 4) Do we want to do the spec using AlgorithmIdentifiers instead of free
> >> text?
>

> If someone wants it phrased this way, I need draft text. Otherwise it'll
> be staying the way it is :-)
>

For something technical, would you prefer an onlist wording suggestion or
as an on-github submission/pull request?

[Gervase Markham]

On 07/02/17 18:23, Ryan Sleevi wrote:
> For something technical, would you prefer an onlist wording suggestion or
> as an on-github submission/pull request?

Happy with either, as long as the PR includes any relevant additional
text from my recently-posted proposal here.

Gerv