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

[Dan Brown <[e-mail]>]

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: [phone]

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