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

[Santiago Torres-Arias <[e-mail]>]

On Sat, Feb 27, 2021 at 11:53:13PM +0000, brian m. carlson wrote:
> 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.


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


> -- 
> brian m. carlson (he/him or they/them)
> Houston, Texas, US



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