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

[denis bider <ietf-ssh3%denisbider.com@localhost>]

Peter:


> in my case I underestimated the amount of work by 50%,
> I need to change two lines of code, not one.

So, it turns out that there isn't an availability problem... :-)


> just pointing out that a security proof is just a supporting
> argument for something, not an actual proof that it's
> secure in practice

Oh, absolutely. Fully agreed.

I am not aware of these practical flaws in PSS, though.


> If there's been next to zero interest in it in twenty years,
> why start now?

It's not true that there has been zero interest. It is present in major crypto implementations, and has been added to them recently (OpenSSL).

I do believe it was added with hope that it will be supported widely enough that protocols like SSH will begin to specify it.

The obstacle to widespread PSS adoption is exactly at the point we're now: standardization in common protocols.

In other words, the fact that you make this argument seems to be the main reason PSS is not (yet?) widely adopted. This causes a circular cause and effect.


> All you need there is a note to tell people to encode
> the sig and do a memcmp(), it's extremely simple.

With a different algorithm, you have recently supported the opposite side of this argument. I argued that DSA is secure if you do X (use deterministic K); others (whom you've supported) argued that people won't do that, and will just use crypto libraries that generate K randomly.

Both arguments are of the form "algorithm X is secure if you do Z". Why does this argument hold water when it comes to PKCS#1 v1.5, but not when it comes to DSA?


> supporting an oddball orphaned crypto mechanism
> that nothing else uses for the rest of eternity.

Except that SSH is a major protocol, and RSA is a major algorithm. If we use PSS, it's no longer oddball. Maybe we're not TLS, but SSH is not bush league.

The libraries implementing PSS appear to be numerous enough that we should no longer be stopped by availability. We should consider what's technically best. That's why we're specifying a new signature algorithm.


denis

 
----- Original Message -----
From: Peter Gutmann
Sent: Wednesday, November 11, 2015 02:14
To: denis bider ; ietf-ssh%netbsd.org@localhost
Cc: djm%mindrot.org@localhost
Subject: RE: rsa-sha2-256: Need YOUR opinion on PSS vs PKCS#1 v1.5
 
denis bider <ietf-ssh3%denisbider.com@localhost> 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).
 
>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.
 
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.