Subject: [Cfrg] Quibble about XMSS draft's critique of RSA, DSA, ECDSA ...

From: Dan Brown <[email-masked]>
Date: Wed, 25 Apr 2018 18:41:03 +0000

Hi CFRG,

https://tools.ietf.org/html/draft-irtf-cfrg-xmss-hash-based-signatures-12#section-9.2

says        

“Any signature algorithm that allows

   arbitrary size messages relies on the security of a cryptographic

   hash function, either on collision resistance or on extended target

   collision resistance if randomized hashing is used for message

   compression.”

and

“In contrast, common signature schemes like

   RSA, DSA, and ECDSA additionally rely on the conjectured hardness of

   certain mathematical problems.”

This text is open to minor misunderstanding. It seems to imply all forms of XMSS security rely on fewer assumptions than any of RSA, DSA and ECDSA do.  I think this implication would be wrong.  

(Skip the next 2 paragraphs of arguments, for a suggested fix of the text.)

For example, first consider key-only (=no-message) universal (=selective) forgery, and full-domain hash RSA.  The forger F is given a message M to forge and RSA public key (N,e).  The forger must compute H(M)^(1/e) mod N.  As long as H(M) is not overly likely to be an e^th power, then there is no forgery attack that I know of, other than breaking RSA.  Reduced to absurdity, put H(M)=2 for all M, so H is a constant.  It seems hard to launch a key-only universal forgery.  I believe that XMSS key-only universal forgery might be possible such an absurd hash, since every message would end up the same signature, etc.  Of course, the limitation to a key-only forger is quite arbitrary, and kind of like of considering the security of 0-time signature (1 signature and all bets are off).  

So, instead, consider non-chosen-message, universal forgery.  But there are moderately realistic applications in which the signer have strict control of the messages they sign, not giving the adversary any say in the message.  A 2nd preimage-finder against the hash certainly helps to get an existential forgery [a well-known attack], but a 2nd preimage finder does not seem to help (very much) in achieving a universal forgery (as long as say the hash function is not too lossy, etc.) against this signer.  So, it seems like non-chosen-message, universal forgery of RSA-FDH (and I think ECDSA, too), can be resisted even with considerable weakness in the hash.  I don’t have a proof, but the best attack of this type of forgery would be solving the RSA problem - as far as I know (60% sure).  (Proof sketch: such a forger could be used to invalidate the random oracle model security proof for RSA-FDH – only 0.001% sure of this.) To reduce things to absurdity (and perhaps clarity), put H(M)=M mod n.  To review: 2nd preimage finding against H is easy, and existential forgery against RSA-FDH is easy too (e.g. if the signer signs M, the forger forges M’=M+fN), but universal forgery (the message M’ that the forger has to forge is given to the forger as an input) seems hard if the attacker cannot choose the messages that the signer signs.  By contrast, I think (80% sure)  that XMSS would resist not this type of forgery with a similarly absurd hash (e.g. H(M) = M mod 2^256).  In other words, for this type of security (UF-NCMA), XMSS relies on additional properties of the hash that RSA is not known to rely upon.  Given the realism of this threat model, I think resisting it more strongly has some merit.

Okay, my points may arguably be too pedantic, verbose, incoherent, theoretical, academic, absurd, simplistic, and even petty (or worse wrong), so to be more constructive, I would suggest a correction to the draft like this:

“In contrast, common signature schemes like

   RSA, DSA, and ECDSA additionally rely on the conjectured hardness of

   certain mathematical problems to resist some types of forgery, such as existential forgery or chosen-message forgery.”

Best regards,

Dan Brown
Office: +1 (289) 261-4157

 <http://www.blackberry.com/>

---

From: "A. Huelsing" <[email-masked]>
Date: Wed, 25 Apr 2018 23:48:29 +0200

Dear Dan,

I sign responsible for that statement and I still think it should be there as is.

The standard notion of security for signature schemes is existential
unforgability under adaptive chosen message attacks (EU-CMA). Section 9 starts
with saying:
"A signature system is considered secure if it prevents an attacker

   from forging a valid signature.  More specifically, consider a
   setting in which an attacker gets a public key and can learn
   signatures on arbitrary messages of his choice.  A signature system
   is secure if, even in this setting, the attacker can not produce a
   new message, signature pair of his choosing such that the
   verification algorithm accepts."

This is an informal definition of EU-CMA and the whole text in this section
comes with this background. Moreover, a general purpose signature scheme that
does not achieve EU-CMA would be considered insecure for general use. Hence, I
think the statement is perfectly fine. I also do not see any discrimination
against RSA, DSA, or ECDSA here. This is just the way it is. Otherwise you could
use MD5 with those to sign and i am pretty sure this is not what you want to
imply :-)

Best regards,
Andreas

Am 25-04-18 um 20:41 schrieb Dan Brown:
> This text is open to minor misunderstanding. It seems to imply all forms of
> XMSS security rely on fewer assumptions than any of RSA, DSA and ECDSA do.  I
> think this implication would be wrong.  
>
>  
>
> For example, first consider key-only (=no-message) universal (=selective)
> forgery, and full-domain hash RSA.  The forger F is given a message M to forge
> and RSA public key (N,e).  The forger must compute H(M)^(1/e) mod N.  As long
> as H(M) is not overly likely to be an e^th power, then there is no forgery
> attack that I know of, other than breaking RSA.  Reduced to absurdity, put
> H(M)=2 for all M, so H is a constant.  It seems hard to launch a key-only
> universal forgery.  I believe that XMSS key-only universal forgery might be
> possible such an absurd hash, since every message would end up the same
> signature, etc.  Of course, the limitation to a key-only forger is quite
> arbitrary, and kind of like of considering the security of 0-time signature (1
> signature and all bets are off). 
>
>  
>
> So, instead, consider non-chosen-message, universal forgery.  But there are
> moderately realistic applications in which the signer have strict control of
> the messages they sign, not giving the adversary any say in the message.  A
> 2^nd preimage-finder against the hash certainly helps to get an existential
> forgery [a well-known attack], but a 2^nd preimage finder does not seem to
> help (very much) in achieving a universal forgery (as long as say the hash
> function is not too lossy, etc.) against this signer.  So, it seems like
> non-chosen-message, universal forgery of RSA-FDH (and I think ECDSA, too), can
> be resisted even with considerable weakness in the hash.  I don’t have a
> proof, but the best attack of this type of forgery would be solving the RSA
> problem - as far as I know (60% sure).  (Proof sketch: such a forger could be
> used to invalidate the random oracle model security proof for RSA-FDH – only
> 0.001% sure of this.) To reduce things to absurdity (and perhaps clarity), put
> H(M)=M mod n.  To review: 2^nd preimage finding against H is easy, and
> existential forgery against RSA-FDH is easy too (e.g. if the signer signs M,
> the forger forges M’=M+fN), but universal forgery (the message M’ that the
> forger has to forge is given to the forger as an input) seems hard if the
> attacker cannot choose the messages that the signer signs.  By contrast, I
> think (80% sure)  that XMSS would resist not this type of forgery with a
> similarly absurd hash (e.g. H(M) = M mod 2^256).  In other words, for this
> type of security (UF-NCMA), XMSS relies on additional properties of the hash
> that RSA is not known to rely upon.  Given the realism of this threat model, I
> think resisting it more strongly has some merit.
>
>  
>
> Okay, my points may arguably be too pedantic, verbose, incoherent,
> theoretical, academic, absurd, simplistic, and even petty (or worse wrong), so
> to be more constructive, I would suggest a correction to the draft like this:
>
>    certain mathematical problems to resist some types of forgery, such as
> existential forgery or chosen-message forgery.”
>
>  
>
> Best regards,
>
> 
>
> Dan Brown
> BlackBerry <http://www.blackberry.com/>
>
>  
>
>
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg