Subject: rsa-sha2-256: Need YOUR opinion on PSS vs PKCS#1 v1.5

From: denis bider <[email-masked]>
Date: Tue, 10 Nov 2015 13:25:19 +0000

I extend thanks to Peter Gutmann for attempting to implement rsa-sha2-256.

In a recent version of the draft, I changed the padding to PSS (from PKCS#1 v1.5) for the following reasons:

(1) RFC 3447, where both formats are defined, recommends PSS:

https://tools.ietf.org/html/rfc3447#section-8
   Although no attacks are known
   against RSASSA-PKCS1-v1_5, in the interest of increased robustness,
   RSASSA-PSS is recommended for eventual adoption in new applications.
   RSASSA-PKCS1-v1_5 is included for compatibility with existing
   applications, and while still appropriate for new applications, a
   gradual transition to RSASSA-PSS is encouraged.Note that this was published in 2003. Twelve years later, it might be time to start making this transition.

(2) Hanno Boeck has argued persuasively in favor of PSS:

https://rsapss.hboeck.de/rsapss-1.0.3.pdf

He makes the following points:

- PSS has provable security in the random oracle model; PKCS#1 v1.5 does not.
- There have been successful attacks on PKCS#1 v1.5 implementations. These do not work against correct (non-parser-like) verifier implementations. However, due to its structure, PKCS#1 v1.5 is appealing to implement incorrectly.
- Fault-based attacks take more care to defend against using PKCS#1 v1.5 than using PSS.

(3) Availability of PSS is now much better than it used to be. In my case, I work with Crypto++ and Windows CNG, which both support it. Free software tends to use OpenSSL, which has also supported PSS since version 1.0.1. This has been available since 2012.

These are the arguments in favor of PSS.

The main argument against is as pointed out by Peter Gutmann. Although a number of major crypto implementations have it, there are still implementations out there that do not.

What's everyone's opinion on this?

In my opinion, we ought to migrate toward an apparent improvement, and now is the opportunity to do so.

If we specify PKCS#1 v1.5 today, we'll be stuck with it for 15 years.

We may have to define another signature algorithm that uses PSS in the future, if standards bodies start to demand PSS.

The main argument in favor of PKCS#1 v1.5 appears to be laziness. No?

---

From: Peter Gutmann <[email-masked]>
Date: Wed, 11 Nov 2015 08:14:18 +0000

denis bider <[email-masked]> writes:

>Note that this was published in 2003. Twelve years later, it might be time to
>start making this transition.

PSS is just under 20 years old (it dates from 1996, "The Exact Security of
Digital Signatures How to Sign with RSA and Rabin").  If there's been next to
zero interest in it in twenty years, why start now?  The signature mechanism
that'll be used everywhere a decade from now will almost certainly still be
PKCS #1, not PSS.

OAEP, the key-transport equivalent of PSS, has the same problem.  It dates
from 1994 ("Optimal Asymmetric Encryption"), but the only major(?)
applications I can think of at the moment are SET and Windows Vista content
protection.  In twenty years its major adopters have been a failed e-commerce
protocol and Vista DRM (and that had some pretty weird stuff in it anyway, it
looked like it was defined by geeks on a crypto algorithm shopping expedition,
I had to add a pile of bizarro stuf to my code to implement that that I've
never had to use since).

>- PSS has provable security in the random oracle model; PKCS#1 v1.5 does not.

I haven't looked at PSS too much, but OAEP is a mass of timing side-channels.
Its complex structure makes it pretty much impossible to implement without
exposing side-channels, and there are published attacks on some of them (see
e.g. James Manger's "A chosen ciphertext attack on RSA optimal asymmetric
encryption padding (OAEP)").

It's not such a big deal with PSS since you're not exposing secret data
through it, but just because something has an abstract mathematical proof (in
an equally abstract mathematical model) doesn't make it secure in the real
world.  OAEP, like PSS, is also provably secure, except that it probably isn't
(see Victor Shoup's "OAEP Reconsidered", and the more recent "Trading One-
Wayness against Chosen-Ciphertext Security in Factoring-Based Encryption",
which points out that the random-oracle model used for the proofs doesn't
provide the same level of assurance as the standard model, and vice versa in
some cases).

In any case since the proof doesn't consider side-channel attacks, it's not
actually secure despite its proof that it is.  OAEP in my code is commented
out because of this, and isn't exposed through an external API.

(Not wanting to start a long debate about security proofs, see "Another Look
at 'Provable Security'" for a starter on this, just pointing out that a
security proof is just a supporting argument for something, not an actual
proof that it's secure in practice).

>- There have been successful attacks on PKCS#1 v1.5 implementations. These do
>not work against correct (non-parser-like) verifier implementations. However,
>due to its structure, PKCS#1 v1.5 is appealing to implement incorrectly.

All you need there is a note to tell people to encode the sig and do a
memcmp(), it's extremely simple.  In addition if there were timing side-
channels, a constant-time memcmp() to deal with them is easy to implement.

>(3) Availability of PSS is now much better than it used to be. In my case, I
>work with Crypto++ and Windows CNG, which both support it. 

Oh, they finally added it in Windows?  It wasn't supported for most of the
lifetime of CryptoAPI (and presumably still won't be in older version of
Windows which don't qualify for upgrades).

>If we specify PKCS#1 v1.5 today, we'll be stuck with it for 15 years.

You've described what will happen if we move to PSS, not PKCS #1.  We'll be
stuck supporting an orphaned crypto mechanism for the next 15 years.  To
paraphrase a quote by AV researcher Vesselin Bontchev, if PSS (and OAEP) was
going to work, it would have worked by now.

>We may have to define another signature algorithm that uses PSS in the
>future, if standards bodies start to demand PSS.

They've had nearly twenty years to do so and haven't yet, why would they start
now?

>The main argument in favor of PKCS#1 v1.5 appears to be laziness. No?

That certainly contributes, although in my case I underestimated the amount of
work by 50%, I need to change two lines of code, not one.  However, the much
bigger objection is being stuck supporting an oddball orphaned crypto
mechanism that nothing else uses for the rest of eternity.

Peter.