Subject: Re: [pkix] redundant AlgorithmIdentifier in X.509 certificates

From: Peter Gutmann <[email-masked]>
Date: Wed, 14 Nov 2012 22:42:29 +0000

Dan Brown <[email-masked]> writes:

>Burt Kaliski prepared some slides explain the security motivation, and the
>inefficacy, of "hash firewalls":
>
>http://www.rsa.com/rsalabs/staff/bios/bkaliski/publications/hash-firewalls/kaliski-hash-firewalls-ct-rsa-2002.ppt

None of those applied to PKCS #1, or any newer replacements like PSS.  They
only worked for 9796 (which is insecure enough anyway without this extra
problem), DSA if you allow something other than SHA-1 (or DSA-2 and SHA-2),
and some other signature scheme that no-one ever uses.  So while it can be an
issue, the simple solution is "don't do that, then".  Or, for current
implementations, "don't change what you're currently doing".

Peter.

---

From: Dan Brown <[email-masked]>
Date: Thu, 15 Nov 2012 17:42:34 +0000

Peter Gutmann [mailto:[email-masked]] writes:
> >Burt Kaliski prepared some slides:
> >
> None of those applied to PKCS #1, or any newer replacements like PSS.

Slides 24--29 address PKCS #1 version 1.5, which uses a hash OID as a "hash firewall".  Slide 27 describes an attack that involves "registering" a malicious OID for a strong hash.  (Aside: this is similar in nature to Vaudenay's domain parameter attack on DSA, in that some parameters of the signature algorithm are malicious.)  It seems that X.509/PKIX additional "signature firewall" would prevent the strong hash attack on Slide 27, but not the weak hash attack on Slide 26.  Regarding Slide 26, I'm not sure if "weak hash attack" is a sensible phrase.  Replacing "weak" by "attackable" makes it sound like a tautology.

> issue, the simple solution is "don't do that, then".  Or, for current

Don't do what?  Use "some other signatures schemes"?  Bother with checking the signed signature algorithm?

> implementations, "don't change what you're currently doing".

It was a fair question to ask if any attacks are prevented by signing the signature algorithm.  If yes, then the verifier/RP really should ensure that signature algorithm used for verification is the signed algorithm identifier.  If no, then it is harmless for the verifier to ignore the inner signature algorithm, because it is safely tucked inside some signed data (assuming the signature verifies).  

RFC 5280 in Section 4.1.2.3 seems to specify a MUST that the RP checks inner==outer. The question about redundancy of the OIDs can be rephrased as follows.  Is it possible for an attacker to forge a certificate that is valid except that inner and outer signature algorithm identifiers do not match.  To be precise, it would be valid in the sense that the signature verifies under the algorithm specified by the outer identifier.  

The way I see it, such a mismatch-forgery would mean the outer-identified signature algorithm is "forgeable", under any reasonable definition of forgeable.  As long the verifier uses a secure signature algorithm, then she can rely on the outer signature alone.  Therefore, the inner identifier is redundant.   

The Slide 27 attack can create this type of mismatching forged certificate.  Even so, the conclusion above about the insecurity of the outer signature still holds, because the outer signature would be PKCS #1 v. 1.5 with a padding that includes a long malicious OID and it would be unreasonable to deem such a malicious signature algorithm as secure.

Best regards,

Dan 

---------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.

---

From: "Kemp, David P." <[email-masked]>
Date: Thu, 15 Nov 2012 20:24:03 +0000

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Dan Brown

> The way I see it, such a mismatch-forgery would mean the outer-identified
> signature algorithm is "forgeable", under any reasonable definition of
> forgeable.  As long the verifier uses a secure signature algorithm, then
> she can rely on the outer signature alone.  Therefore, the inner identifier is redundant.   

Does there exist a signature algorithm (e.g., MD4withRSA) that is known or suspected to be forgeable (using Dobbertin or other attacks)?

If so, does PKIX maintain a whitelist of unforgeable signature algorithms such that if verifiers support only whitelisted algorithms, the inner identifier is redundant?

If there is a nonempty set of forgeable algorithms supported by any verifier application claiming to be X.509 or PKIX conformant, then either the algorithm whitelist must exist and be included in X.509 conformance, or the inner/outer MUST requirement is justified.

---

From: Dan Brown <[email-masked]>
Date: Thu, 15 Nov 2012 21:41:25 +0000

> From: Kemp, David P.
> Sent: Thursday, November 15, 2012 3:24 PM
> 
> Does there exist a signature algorithm (e.g., MD4withRSA) that is known
> or suspected to be forgeable (using Dobbertin or other attacks)?
> 
> If so, does PKIX maintain a whitelist of unforgeable signature
> algorithms such that if verifiers support only whitelisted algorithms,
> the inner identifier is redundant?

Well, I now see that RFC 5280 does not require "any particular cryptographic algorithms", so it technically allows forgeable algorithm (although I think most would read it as tacitly disallowing known-to-be-insecure algorithms).  Despite this general and open wording, I think most implementers would actually construe RFCs 3279, 4055, 4491, 5480, and 5758 as a de facto list of acceptable signature algorithms.  

Taking the more open position raises the question of what qualifies as a "signature algorithm" or "cryptographic algorithm"?  Presumably, the commonly-used empty-string-digital-signature-algorithm does not qualify, because nobody claims it is secure.  Some algorithms are so rarely-used (e.g. NTRUSign, GQ signatures, raw RSA or raw ElGamal) that they may be irrelevant to PKIX.

Or, am I misinterpreting the point of PKIX?  Does PKIX only really specify a format only, leaving security totally to the implementers?

Aside: do you say "unforgeable" ironically in the sense that nobody, not even PKIX, can make such a promise of unforgeability?   Well, even if you didn't mean that, I'd have to respond and say that the best any crypto standard can do is to specify the state of art, implying not-yet-known-to-be-too-broken algorithms, but even still crypto implementations have to watch out for new developments which the standards cannot anticipate.

> 
> If there is a nonempty set of forgeable algorithms supported by any
> verifier application claiming to be X.509 or PKIX conformant, then
> either the algorithm whitelist must exist and be included in X.509
> conformance, or the inner/outer MUST requirement is justified.

Yes, if security is a PKIX goal.  More generally, would it be justified to allow such a verifier application to claim to be PKIX conformant even if it enforced outer==inner?  If it uses sufficiently insecure signature verification algorithm, then a forger could send it forged certificates.  In other words, you said "either A or B [or both]", and I'm saying "A".

> _______________________________________________
> pkix mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/pkix