Subject: [Cfrg] Hash substitution in PSS

From: "Igoe, Kevin M." <[email-masked]>
Date: Thu, 11 Apr 2013 17:41:58 +0000

On 4 August Jim Schaad pointed out that the choice of hash algorithm in PSS is not authenticated and asked if this was a security problem.

The good news is that if all of the hash algorithms in use are "secure", the only risk is the "birthday problem", and the aVailability of more than one hash does not a priori result in a cheaper attack.

The bad news is that if one of the hashes is broken, so broken that an adversary has a non-trivial chance of finding an "evil" message that has the same hash value as a benign message formed with a hash that is "secure", they can substitute the evil message under the weak hash for the benign message under the strong hash. Preventing this requires either that (1) the have a policy to reject all messages with the weak hash or (2) the choice of hash algorithm be authenticated. Personally I trust a cryptographic authentication over policy.

---

From: Dan Brown <[email-masked]>
Date: Thu, 11 Apr 2013 18:28:04 +0000

Doesn't the signer need to have a policy to avoid signing with a weak hash?

Otherwise, if Alice the signer does not have such a policy, then she could sign with a weak hash.  Then Eve the adversary, under your scenario (*), could take the hash value from any message that Alice signed, and find an evil message with the same hash, and fool Bob the verifier.  What am I missing?

It seems impossible to avoid having a good policy for the signer.  I agree that it would be fantastic to avoid such a policy on algorithms, via some algorithm. 

Surely, the verifier would be able to use the same policy as the signer.  Maybe this violates the principle of being "generous in what you receive", but how appropriate is that particular principle when verifying a signature?

Why not embed the signer's policy into the signer's certificate?  That would somewhat ease the burden on the verifier, and place responsibility for the policy upon the signer, where the burden probably belongs.

Best regards,

Dan

(*) Your scenario sounds like this to me: the hash is "weak" in the sense that evil pre-images of any hash can be found.  That is what I am assume above.  (Or, you can take second preimages ...)

A more elaborate scenario would be that the "weak" hash is still strong in the sense that it 1st and 2nd preimage resistant, but it is not 2nd preimage resistant given a 1st preimage under the strong hash.  In other words, it fails to be second cross-preimage resistant.  This scenario is theoretically possible, but seems unlikely for most conventional hash functions.  The policy-necessity argument I make above does not apply to this scenario. 

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> Igoe, Kevin M.
> Sent: Thursday, April 11, 2013 1:42 PM
> To: [email-masked]'
> Subject: [Cfrg] Hash substitution in PSS
> 
> On 4 August Jim Schaad pointed out that the choice of hash algorithm in
> PSS is not authenticated and asked if this was a security problem.
> 
> The good news is that if all of the hash algorithms in use are
> "secure", the only risk is the "birthday problem", and the aVailability
> of more than one hash does not a priori result in a cheaper attack.
> 
> The bad news is that if one of the hashes is broken, so broken that an
> adversary has a non-trivial chance of finding an "evil" message that
> has the same hash value as a benign message formed with a hash that is
> "secure", they can substitute the evil message under the weak hash for
> the benign message under the strong hash. Preventing this requires
> either that (1) the have a policy to reject all messages with the weak
> hash or (2) the choice of hash algorithm be authenticated. Personally I
> trust a cryptographic authentication over policy.
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---------------------------------------------------------------------
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: "Igoe, Kevin M." <[email-masked]>
Date: Fri, 12 Apr 2013 00:38:47 +0000

I believe we are in agreement. Any policy put in place by the signer to require use of the strong hash when signing is useless unless the verifier also has a policy to not accept messages signed using the weak hash. Like CRLs and patches, it takes a worrisomly long time for such changes to propogate to every verifier. During the chage over period the signer is vulnerable  to having one of their benign messages "hijacked" and an evil version fed to an "unpatched" verifier.

Having the policy be part of the cert sounds like a prudent precaution, but doesn't that implicitly require the policy to be authenticated to stop Eve from meddling with it?  I suppose the bottom line is that if a commonly used hash fails disasterously then even people who have not been using that hash are vulnerable. 

This seems to say designing a protocol that allows for the use of several different hashes actually increase everyones vulnerability. That certainly is counter intuitive. Of course the discussion above assumes a truly disasterous flaw. If the flaw more mundane, supporting more than one hash helps in recovering from the discovery of this flaw.

----- Original Message -----
From: Dan Brown [mailto:[email-masked]]
Sent: Thursday, April 11, 2013 02:28 PM Eastern Standard Time
To: Igoe, Kevin M.; [email-masked]' <[email-masked]>
Subject: RE: Hash substitution in PSS

Best regards,

Dan

---

From: Dan Brown <[email-masked]>
Date: Fri, 12 Apr 2013 18:37:17 +0000

> From: Igoe, Kevin M. [mailto:[email-masked]]
> I believe we are in agreement. 

[DB] I am sure that we agree on many points, but I think we disagree on some specific points. I will try to be clearer.  I am open to correction.

I think a hash identifier in PSS does not help.  Do you agree?  

I stand by my argument for that position: which, recall, is that if hash substitution is a problem there will also be much bigger problem, except under very unrealistic scenarios.

> Any policy put in place by the signer to
> require use of the strong hash when signing is useless unless the
> verifier also has a policy to not accept messages signed using the weak
> hash. Like CRLs and patches, it takes a worrisomly long time for such
> changes to propogate to every verifier. 

[DB] Which is why I propose placing the policy in the certificate, so it is available as soon as the verifier needs it.

> During the chage over period
> the signer is vulnerable  to having one of their benign messages
> "hijacked" and an evil version fed to an "unpatched" verifier.

[DB] Your last sentence is why I think we still disagree. 

The "bigger problem" (that I alluded to above, and tried to express in a previous email) is that the attacker will not need to "hijack" any benign messages to feed evil messages to that "unpatched" verifier.  Instead, if the hash is weak, the attacker can feed evil messages to the verifier, without relying any benign messages.

> 
> Having the policy be part of the cert sounds like a prudent precaution,
> but doesn't that implicitly require the policy to be authenticated to
> stop Eve from meddling with it?  

[DB] Yes.  

E.g. if SHA-1 gets totally broken, then any relying party Bob who continues to use SHA-1, will accept malicious certs from Eve, etc.

So, it mainly helps if the issuer uses a stronger algorithm in the cert than the subject uses to the sign message, or if the cert is authenticated out of band, i.e. pre-trusted.

I realize that I failed to explain the benefit of using the signer's cert, instead of the signer's signature, to convey the signer's policy on the alg.  If the signature security is compromised, then it cannot be presumed to safely convey the signer's policy.  The cert still has a chance to convey the signer's policy (either by stronger algorithm, or by being pre-trusted, as mentioned above).

I also failed to clarify that my reason for conveying the signer's policy is not to thwart "hijacking" attacks, but rather that weak hashes must be avoided, and that the signer should be responsible for avoiding weak hashes.  (My failure to clarify this point may have cause to you think that I agree with the "hijacking" concern.)

More technically, the signer needs to ensure the hash resists second-preimage attacks, while the verifier only must ensure that the hash resists first-preimage attacks.

> I suppose the bottom line is that if a
> commonly used hash fails disasterously then even people who have not
> been using that hash are vulnerable.

[DB] Yes.

> 
> This seems to say designing a protocol that allows for the use of
> several different hashes actually increase everyones vulnerability.
> That certainly is counter intuitive. 

[DB] Why is it counter intuitive?  If Bob accepts any of 5 hashes (or algs), then his security is only as good as the weakest hash (or alg).  If Bob insisted that a message was signed by all 5 algs, then his security could be as a good as the strongest. 

> Of course the discussion above
> assumes a truly disasterous flaw. If the flaw more mundane, supporting
> more than one hash helps in recovering from the discovery of this flaw.

[DB] To recover from a total disaster, only distributing a policy to stop all signing and verifying with the weak hash seems to work. 

I have yet to be persuaded that there is a realistic milder flaw in the hash that hash ids in PSS would thwart.

I agree that there is benefit to having signature schemes reduce their reliance on the hash for security.  For example, randomized hashing reduces the reliance on collision resistance of the hash, which, I am persuaded, addresses a realistic concern.  (It also reduces the reliance on other security properties of the hash, such as second-preimage and first-preimage resistance, and instead relies on milder versions thereof.)

I agree that it is prudent to take steps to address unforeseen attacks, e.g. the provable security analyses of PSS [but unfortunately the current research mostly ignores hash attacks because it mostly assumes a random oracle hash].

I disagree that a good way to thwart unforeseen attacks is to speculate about unrealistic possible attacks, e.g. second cross-preimage attacks (but no first preimage attacks), and to speculate about countermeasures.  

I think it is important to have a clear statement of what protection a crypto scheme provides, to help ensure users do not rely on the crypto scheme in the wrong way.

---

From: Dan Brown <[email-masked]>
Date: Mon, 15 Apr 2013 20:33:40 +0000

Hi Kevin,

Somehow, I missed Kaliski's paper from CT-RSA 2002 [even though it is a reference in PKCS #1 ver. 2.1!]: you may wish to consider Kaliski's argument why RSA-PSS does not need a hash firewall, and his general recommendations about algorithm authentication (via the infrastructure, not the message).  I think the Kaliski paper shows that the issue was considered carefully, and not just something that was forgotten and fell through the cracks.

Best regards,

Dan

PS  My view on the issue has not changed much.  Overall, it is somewhat different from Kaliski's, although our conclusions for PSS are similar.

---

From: "Jim Schaad" <[email-masked]>
Date: Mon, 15 Apr 2013 21:28:45 -0700

Dan,

I will note that almost none of the recommendations in this paper would
appear to have made it into practice and in fact are actively suppressed

There is no requirement in any standard that I have seen that says that the
hash function for the mask generation and that hash function for the body
compression match. 

There is no requirement that the set of hash algorithms for a PSS RSA key be
included in a certificate (in fact it is currently actively precluded from
happening).

While interesting in theory, I find the argument made for the creation of a
new weak hash function id to be one that would be difficult to get the
real-world to accept.  And note that without this extension of the attack
there is a strong defense imposed by RSA v1.5 signatures by having the
firewall present.

Finally, I know of no research that says that the birthday attack cannot be
improved by allowing multiple hash functions to be used in the RSA-PSS, DSA
or ECDSA cases where there is no hash firewall even in the presence of
accepting only strong hash functions.  I am far less interested in the case
of accepting known weak hash functions.  (Although there is still the
problem of accepting weak hash functions which are thought to be strong.)

Jim

Dan
> Brown
> Sent: Monday, April 15, 2013 1:34 PM
> To: 'Igoe, Kevin M.'; [email-masked]'
> Subject: Re: [Cfrg] Hash substitution in PSS
> 
> Hi Kevin,
> 
> Somehow, I missed Kaliski's paper from CT-RSA 2002 [even though it is a
> reference in PKCS #1 ver. 2.1!]: you may wish to consider Kaliski's
argument
> why RSA-PSS does not need a hash firewall, and his general recommendations
> about algorithm authentication (via the infrastructure, not the message).
I
> think the Kaliski paper shows that the issue was considered carefully, and
not
> just something that was forgotten and fell through the cracks.
> 
> Best regards,
> 
> Dan
> 
> PS  My view on the issue has not changed much.  Overall, it is somewhat
> different from Kaliski's, although our conclusions for PSS are similar.
> 
> > From: [email-masked] [mailto:[email-masked]] On Behalf
> > Of Igoe, Kevin M.
> > On 4 August Jim Schaad pointed out that the choice of hash algorithm
> > in PSS is not authenticated and asked if this was a security problem.
> >
> > "secure", the only risk is the "birthday problem", and the
> > aVailability of more than one hash does not a priori result in a cheaper
> attack.
> >
> > hash or (2) the choice of hash algorithm be authenticated. Personally
> > I trust a cryptographic authentication over policy.
> 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: "Igoe, Kevin M." <[email-masked]>
Date: Mon, 29 Apr 2013 17:58:54 +0000

Under the assumption that the two hash functions behave as independent random
functions, the birthday problem isn't affected if more than one hash functions is
allowed.  This falls apart if the two hash functions are related, say the same 
compression function used in each, but with different initial fills.

> From: Jim Schaad [mailto:[email-masked]]
> Sent: Tuesday, April 16, 2013 12:29 AM
> To: 'Dan Brown'; Igoe, Kevin M.; [email-masked]
> Subject: RE: [Cfrg] Hash substitution in PSS
> 
> Dan,
> 
> Of

---

From: Dan Brown <[email-masked]>
Date: Mon, 29 Apr 2013 19:27:41 +0000

> included in a certificate (in fact it is currently actively precluded
[DB] RFC 5756 says "When the id-RSASSA-PSS object identifier
   appears in the TBSCertificate subjectPublicKeyInfo algorithm field of
   EE certificates, then the parameters field MAY include the RSASSA-
   PSS-params structure." 

RFC 4055 says "RSASSA-PSS-params  ::=  SEQUENCE  {
         hashAlgorithm      [0] HashAlgorithm DEFAULT
                                   sha1Identifier,
         maskGenAlgorithm   [1] MaskGenAlgorithm DEFAULT
                                   mgf1SHA1Identifier,
         saltLength         [2] INTEGER DEFAULT 20,
         trailerField       [3] INTEGER DEFAULT 1  }"

So, I agree with you that there is no requirement to identify RSA-PSS hash algs, but I disagree that it is precluded: because the way I read 5756 says that it is optional, not precluded.  What am I missing?

For ECDSA: I agree that 5480 precludes placing hash restriction for ECDSA in a certificate.  I, as a 5480 co-author, only reluctantly agreed to this preclusion (based on some survey comments and interoperability issues).  Meanwhile, SEC1 offers an optional ASN.1 syntax that does allow hash-restriction, for the signers and verifiers who, rather nervously, want to retain assurance, for the long-term, against a hypothetical flaw in a hash, such as SHA1.