Subject: [openpgp] RSA-PSS and RSA-OAEP for v5

From: "brian m. carlson" <[email-masked]>
Date: Sat, 27 Feb 2021 23:53:13 +0000

One of the persistent pieces of feedback about OpenPGP I've received
from folks involved in the security and cryptography fields is that the
PKCS v1.5 algorithms are obsolete.  It is well known that many
cryptographic libraries have suffered (and will likely continue, despite
their best efforts, to suffer) from padding vulnerabilities.  TLS has
recently added support for RSA-PSS and it's widely preferred over
PKCS1-v1.5.

I'm interested in seeing if we can require v5 SKESK packets with RSA use
RSA-OAEP with SHA-256 and MGF1-SHA-256 and require that v5 signatures
with RSA use RSA-PSS, with the MGF using the same digest as the
signature.

Hard-coding SHA-256 as the algorithm for RSA-OAEP means we don't need to
specify it as a parameter, and since it's the must-implement algorithm,
there's no reason an implementation won't support it.  Folks that wish
to provide a better than 128-bit security level will use ECDH instead,
since RSA at the 192-bit level (7680 bit keys) is much slower and such
keys are not practically used.

I realize this requires implementers to add additional code, but I think
the increase in security is worth it given the number of CVEs we've seen
for padding vulnerabilities.  We can tell implementers to avoid this
vulnerability until we're blue in the face, but considering that both
OpenSSL and NSS had this problem, that doesn't seem prudent.
-- 
brian m. carlson (he/him or they/them)
Houston, Texas, US

---

From: Peter Gutmann <[email-masked]>
Date: Sun, 28 Feb 2021 03:49:45 +0000

brian m. carlson <[email-masked]> writes:

>I'm interested in seeing if we can require v5 SKESK packets with RSA use RSA-
>OAEP with SHA-256 and MGF1-SHA-256 and require that v5 signatures with RSA
>use RSA-PSS, with the MGF using the same digest as the signature.

Apart from adding a huge amount of complexity and potential interop problems,
you're not really gaining anything by this that isn't already addressed by
"MUST use encode-them-memcmp() for signatures".  PKCS #1 signing is perfectly
secure if you do that, and PKCS #1 encryption doesn't matter much because PGP
isn't likely to be used in situations where it acts as an online million-
message oracle.

See also my post to the cryptography list last year about all the games an
attacker can play with OAEP because the parameters aren't authenticated and
therefore attacker-controlled.

Peter.

---

From: "brian m. carlson" <[email-masked]>
Date: Sun, 28 Feb 2021 17:58:45 +0000

> isn't likely to be used in situations where it acts as an online million-

I've already outlined that people definitely do use OpenPGP in online
situations in <[email-masked]>.  IIRC, we've
seen people report online usages to the list, and I provided examples
where users do indeed sign online.  And despite the fact that we clearly
issue CVEs against people who people who create Bleichenbacher oracles,
people still write them.  These attacks have been known for years and
previously fixed and yet in 2018, we had another round of them in TLS.

PKCS #1 is very hard to get right.  We've seen many implementations have
problems with it, some multiple times.  The fact that people continue to
get it wrong means that it's easy to misuse.  We specifically use
techniques such as AEADs because they are _harder_ to misuse than
techniques which are equally secure in the theoretic sense, such as
encrypt-then-MAC with CTR and HMAC.  Using RSA-PSS and RSA-OAEP doesn't
mean that implementers don't have to be careful and prudent, but it does
mean that if they make a mistake that the consequences are less
terrible.

I agree that this requires additional code and adds additional
complexity, but we're also adding support for entirely new cipher modes
and other security improvements which do as well.  Most cryptographic
libraries already support RSA-PSS and RSA-OAEP, so there's little code
to add.  OpenSSL, libgcrypt, RustCrypto, and Go's standard library all
already support this.  It's pretty much a matter of substituting a
handful of lines of code based on a branch on the version number.

> therefore attacker-controlled.

I was unable to find anything that looked like a relevant thread in the
archives for 2020.  Could you provide a citation?
-- 
brian m. carlson (he/him or they/them)
Houston, Texas, US

---

From: Hanno Böck <[email-masked]>
Date: Sun, 28 Feb 2021 19:44:40 +0100

On Sun, 28 Feb 2021 03:49:45 +0000
Peter Gutmann <[email-masked]> wrote:

> See also my post to the cryptography list last year about all the
> games an attacker can play with OAEP because the parameters aren't
> authenticated and therefore attacker-controlled.

This is a valid concern, but it can be completely eliminated by fixing
all parameters in the standard.

-- 
Hanno Böck
https://hboeck.de/

---

From: Werner Koch <[email-masked]>
Date: Sun, 28 Feb 2021 19:43:19 +0100

> RSA-OAEP with SHA-256 and MGF1-SHA-256 and require that v5 signatures

That would add a lot of additional complexity for no good reason because
RSA will over short or long anyway be replaces by 25519 and 448.

> for padding vulnerabilities.  We can tell implementers to avoid this

and replace them with bugs in the way more complext PSS and OAEP.

I see no reason for it and doubt that this can be viewed as part of the
WG's old and new charter.

Shalom-Salam,

   Werner

-- 
Die Gedanken sind frei.  Ausnahmen regelt ein Bundesgesetz.

---

From: "brian m. carlson" <[email-masked]>
Date: Sun, 28 Feb 2021 19:26:32 +0000

> RSA will over short or long anyway be replaces by 25519 and 448.

I believe that the current plan was to make RSA must-implement, but
maybe I'm misremembering.  If we instead made EdDSA, ECDH, and
Curve25519 must-implement and RSA optional, then this becomes clearly
less important.

If we continue to suggest in any way that people use RSA keys, then we
need to consider this.  If we make RSA keys completely optional, then
it's probably fine to just omit this.

> and replace them with bugs in the way more complext PSS and OAEP.

I'm not sure how these wouldn't be a problem anyway given crypto
libraries already implement them.  Presumably such bugs would have
already surfaced in their existing usage and interoperability.  For
example, any crypto library used by TLS 1.3 almost certainly implements
RSA-PSS correctly because otherwise it wouldn't interoperate, since all
RSA signatures in CertificateVerify use PSS.  S/MIME already supports
RSA-OAEP, so presumably that's already correctly implemented as well.

Are you suggesting that existing implementations have other latent
interoperability bugs that aren't exercised by TLS and S/MIME?  Or that
there's something special about OpenPGP that makes it more likely to be
a problem here?  Or that implementers are likely to avoid using
well-known existing cryptographic implementations in favor of their own?

> WG's old and new charter.

The charter specifies this:

- Revision of mandatory-to-implement algorithm selection and deprecation
of weak algorithms

I think it's very clear, based on a history of CVEs, that as practically
implemented, PKCS #1 padding is weak compared to PSS and OAEP.  We
should specify padding algorithms that are not weak as part of MUST and
SHOULD algorithms.
-- 
brian m. carlson (he/him or they/them)
Houston, Texas, US

---

From: Stephen Farrell <[email-masked]>
Date: Sun, 28 Feb 2021 19:47:15 +0000

Hiya,

On 28/02/2021 19:26, brian m. carlson wrote:
> implemented, PKCS #1 padding is weak compared to PSS and OAEP.

FWIW, my impression is that that is not clear. Quite a few
people do have that position for sure, but equally, the views
expressed by e.g. Werner and Peter Gutmann also seem fairly
commonly held afaics.

(As chair) would it be worthwhile pushing this question off
for a while? It may become easier to handle later on - or
even if it's no easier later, it still might be better to
postpone the bun fight for a bit:-)

If pushing this to later made sense, I guess creating an
issue in gitlab would be the thing to do so's we don't lose
track of it. (Apologies if someone did that already, I didn't
go check just now.)

S.

---

From: "brian m. carlson" <[email-masked]>
Date: Sun, 28 Feb 2021 20:05:39 +0000

> postpone the bun fight for a bit:-)

Sure, I'm happy to defer this for the moment.  We don't need to make a
decision immediately, and considering that I just proposed this
yesterday, we can definitely let folks think about it for a while before
coming back to it.

> track of it. (Apologies if someone did that already, I didn't

I've created one so we don't lose track of it:

https://gitlab.com/openpgp-wg/rfc4880bis/-/issues/22
-- 
brian m. carlson (he/him or they/them)
Houston, Texas, US

---

From: Stephen Farrell <[email-masked]>
Date: Sun, 28 Feb 2021 20:10:15 +0000

Hiya,

> yesterday, we can definitely let folks think about it for a while before

Great, thanks. Sometimes these things do get easier based
on earlier decisions, we'll see.

> https://gitlab.com/openpgp-wg/rfc4880bis/-/issues/22

Thanks again,
S.

---

From: Santiago Torres-Arias <[email-masked]>
Date: Sun, 28 Feb 2021 20:38:44 -0500

> OpenSSL and NSS had this problem, that doesn't seem prudent.

To add to the conversation, I wanted to share some related
bibliography[1]:

    "On the Security of the PKCS#1 v1.5 Signature Scheme"

    Tibor Jager, Paderborn Uninversity, Paderborn, Germany
    Saqib A Kakvi, Paderborn University, Paderborn, Germany
    Alexander May, Ruhr-University Bochum, Bochum, Germany

    The RSA PKCS#1 v1.5 signature algorithm is the most widely used digital
    signature scheme in practice. Its two main strengths are its extreme
    simplicity, which makes it very easy to implement, and that verification
    of signatures is significantly faster than for DSA or ECDSA. Despite the
    huge practical importance of RSA PKCS#1 v1.5 signatures, providing
    formal evidence for their security based on plausible cryptographic
    hardness assumptions has turned out to be very difficult. Therefore the
    most recent version of PKCS#1 (RFC 8017) even recommends a replacement
    the more complex and less efficient scheme RSA-PSS, as it is provably
    secure and therefore considered more robust. The main obstacle is that
    RSA PKCS#1 v1.5 signatures use a deterministic padding scheme, which
    makes standard proof techniques not applicable. We introduce a new
    technique that enables the first security proof for RSA-PKCS#1 v1.5
    signatures. We prove full existential unforgeability against adaptive
    chosen-message attacks (EUF-CMA) under the standard RSA assumption.
    Furthermore, we give a tight proof under the Phi-Hiding assumption.
    These proofs are in the random oracle model and the parameters deviate
    slightly from the standard use, because we require a larger output
    length of the hash function. However, we also show how RSA-PKCS#1 v1.5
    signatures can be instantiated in practice such that our security proofs
    apply. In order to draw a more complete picture of the precise security
    of RSA PKCS#1 v1.5 signatures, we also give security proofs in the
    standard model, but with respect to weaker attacker models (key-only
    attacks) and based on known complexity assumptions. The main conclusion
    of our work is that from a provable security perspective RSA PKCS#1 v1.5
    can be safely used, if the output length of the hash function is chosen
    appropriately.

    Publication: CCS '18: Proceedings of the 2018 ACM SIGSAC Conference
    on Computer and Communications Security, October 2018, Pages 1195–1208

Although I *personally think* that PSS is a better padding algorithm,
I'm also rather cautious not to be as definitive when making calls. This
paper shows two things:

1. It may take many decades to have a formal security proof (even if
    within the random oracle model) of a padding algorithm of this
    nature.
2. The argument that PSS is somewhat superior because of its
    "mathematically provable security" (i.e., the motivating point for
    PSS on RFC 4096) may not hold that strongly anymore.

I agree that Bleichenbacher's Oracle is an issue within certain uses of
PGP (being such a versatile tool almost always means that you will
always find a use that raises security concerns :P), yet I also wonder
if PKCSv1.5 also ended up having a series of CVE's because it has seen
more field-usage throughout these decades.

Not sure if I personally have a strong stance in any direction, just
wanted to share my perspective...

Cheers!
-Santiago

P.S. I'm also not entirely comfortable with hardcoding a hash algorithm
for OAEP, but that's a different conversation and I may be missing
context.

[1] https://dl.acm.org/doi/10.1145/3243734.3243798

> _______________________________________________
> openpgp mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/openpgp