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

From: denis bider <[email-masked]>
Date: Wed, 11 Nov 2015 10:41:22 +0000

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 ; [email-masked]
Cc: [email-masked]
Subject: RE: rsa-sha2-256: Need YOUR opinion on PSS vs PKCS#1 v1.5
 
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).
 
>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.

---

From: Peter Gutmann <[email-masked]>
Date: Thu, 12 Nov 2015 02:37:30 +0000

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

Uhh, just in case there's any confusion over this, that's for PKCS #1.  For
PSS I would have had to implement a completely new signature mechanism from
scratch, thus my earlier email requesting use of PKCS #1.

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

Not yet.  However, PSS has seen so little interest from both the crypto
community and implementers that we can't really say much about it.  For
example for some years the NIST test vectors for RSA-PSS were completely wrong
(every single test except the SHA-224 ones failed), and no-one noticed.

I'll just let that sink in for a second.  The published test vectors from a
major, effectively global in reach, standards body for RSA-PSS were wrong, and
no-one noticed.  How much attention do you think that indicates PSS has got in
practice?

>It is present in major crypto implementations, and has been added to them
>recently (OpenSSL).

Well, OpenSSL is kinda of the petri dish that everything gets hacked into, so
I'm not sure if that's a good indicator.  For example it has a convenient
remote-debug facility that allows attackers to read out your server's memory
in 64kB blocks, but I won't be adding that to my code any time soon.  It also
implements X9.31 RSA, and there was a patch for some of the ISO 9796 RSA
schemes floating around as well.  How often have you run into those in
practice?

In any case with the "close to zero interest" I was referring to
standardisation and support in major crypto-using protocols, PGP, S/MIME,
X.509, IPsec, TLS, and SSH.

>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.

It can actually work both ways: We need to make a start somewhere in order to
get it adopted, or conversely if we adopt it and no-one else does we'll be
stuck supporting an orphan protocol like the lucky adopters of OAEP are.
Given that there's been close to twenty years of no interest, I'd say it's far
more likely to be the latter.

It's actually more than just passive disinterest, it was actively rejected by
the TLS WG (as OAEP for RSA key transport) in 2001 when an attempt was made to
piggyback it on top of AES adoption (in other words "if you want AES you have
to use RSA-OAEP with it", it couldn't even stand on its own merits).  I've
attached one vendor's reasoning for this at the end of this message, it talks
about AES which was the big deal at the time, substitute SHA-2 for AES to
update it to the current discussion.  RSA-KEM, yet another newer padding
scheme, was rejected by the S/MIME WG in 2002, as was OAEP.  There's another
scheme, Simple-RSA, which was proposed when the flaws in the OAEP proof were
discovered, that's also failed to see an adoption, as has SAEP and OAEP+.

>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.

Uhh, I never made any comment about deterministic DSA.  If I did, I would also
have argued against ECDSA, which has the same problem.  My point with DSA was
that continuing support for an algorithm that was more or less dead wasn't a
good idea.

>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.

It's no longer oddball, but it'll leave SSH stuck with something that no-one
else (meaning no other mainstream protocol) uses.  Redde Caesari quae sunt
Caesaris: The stated goal of this draft is to allow use of SHA-2 instead of
SHA-1, so that's what it should do.  If there's interest in introducing a new
signature scheme that's incompatible with the one that every version of SSH
for the last 20 years has been using then it should stand or fall on its own,
not piggybacked onto an update of hash algorithms.

I would be perfectly happy with a separate draft for RSA-PSS.  My sole
objection to it is having to implement a completely new signature mechanism
just to be allowed to use SHA-2.

Peter.

-- Snip --

1. Deploying AES-based ciphersuites is the primary goal

The AES block cipher provides a step up in security  from 3DES including
true 128 bit (and larger) keys, and a larger block size.  At the same
time, it provides increased performance across a wide set of platforms.

The definitions of the AES ciphersuites should introduce only the new
block cipher, not additional protocol or cryptographic mechanisms that
would complicate or delay deployment of AES.  If OAEP has benefits for
TLS it should be introduced as a separate ciphersuite using an existing
and established encryption mechanism such as 3DES.

2. RSA-OAEP is not required for security

In message to this list on 31 May, David Hopwood said:

"Using OAEP with TLS makes effectively no difference to the provable security
properties of the RSA ciphersuites, assuming that the method described in
section 7.4.7.1 of RFC 2246 is followed (i.e. the premaster secret is replaced
with a random value whenever the PKCS #1 v1.5 block is invalid).

The effect of that method is to prevent chosen ciphertext attacks in much
the same way as the "Simple RSA" scheme described in [Shoup01], which has
a tighter reduction from the RSA problem than OAEP does. To get the same
tightness of reduction when using OAEP in TLS, you would still have to
require that no information is leaked about whether the decryption of the
premaster secret succeeds or not."

So it seems that OAEP adds no benefit for TLS, since the suggested
method from RFC 2246 must be used in any case.

3. Adding RSA-OAEP adds complexity

Requiring RSA-OAEP for the AES ciphersuites means that implementations
will need to provide both RSA padding schemes.  In some situations the
extra code space and complexity won't be a problem, but some memory or
performance contrained devices would be better off without both
implemenations.  It is unlikely that AES-only deployments will be
possible in the near term, so devices will need to implement both old
and new methods for interoperability reasons.

4. Adding RSA-OAEP delays implementation

This requirement will delay the availability of the new ciphersuites for
two reasons. First, the time to implement the OAEP padding will delay
the availability of products with this capability.  Second, testing
independantly developed products will take longer since the
interoperability of both OAEP and the AES cipher will need to be tested.

5. Adding RSA-OAEP delays adoption of AES in hardware devices

Many services that use TLS rely on hardware devices to improve the
performance of TLS or to provide additional security.  These hardware
devices will need to be updated to provide both the AES cipher, and the
new RSA-OAEP encryption mechanism.  Hardware updates are typically less
frequent than updates for software packages, and

[6 = not-relevant TLS-specific issue]

---

From: Terra Frost <[email-masked]>
Date: Wed, 11 Nov 2015 21:38:21 -0600

Just because an RFC exists that provides for the use of RSA PSS doesn't
mean implementations are going to use it. And if new versions of OpenSSL do
start implementing it it's still probably years away and even then it's of
little consequence without clients implementing it, as well, and
prioritizing RSA PSS over other algorithms.

Defining it in the RFC is the first of many steps that need to occur for it
to become widely utilized and it can become stillborn at each of those
steps.

If it becomes more widely utilized it'll become more scrutinized and the
lessons that that increased scrutiny will bring will lead to even better
algorithms, in the future..

Long story short, I'm in support of implementing RSA PSS.