[IPsec] [Cryptography] Why RSA-PSS is much less secure than PKCS #1 v1.5 (fwd)

[Paul Wouters <[e-mail]>]

Interesting, since we basically said to do only PSS for RFC 7427 ....

Paul

---------- Forwarded message ----------
Date: Sun, 10 Nov 2019 23:34:28
From: Peter Gutmann <[e-mail]>
To: Cryptography Mailing List <[e-mail]>
Subject: [Cryptography] Why RSA-PSS is much less secure than PKCS #1 v1.5

There is a view that RSA-PSS (henceforth referred to as PSS) is more secure
than PKCS #1 v1.5 (henceforth PKCS #1), presumably because PSS has the words
"provable" and "secure" in its description (the abbreviation PSS stands for
Probabilistic Signature Scheme, it's the scheme itself which has "provable" in
it).  In practice however PSS is much less secure and vastly more brittle than
PKCS #1, despite its "provable security".  Here's why.

To understand the problem, you need to look at PKCS #1 vs. PSS.  PKCS #1 has
the following external, unauthenticated parameters:


The PKCS #1 verification operation, following the RSA operation that both PSS
and PKCS #1 require, is as follows.  Given a hash of the data being signed,
perform the following:

   fixed_sig_data[ hash_offset ] = hash;
   result = memcmp fixed_sig_data, recovered_sig_data;

In other words, copy the hash onto the end of the fixed-format PKCS #1
signature data and compare it with the recovered signature data.  The fixed-
format PKCS #1 signature data encodes the hash algorithm, parameters,
signature type, and anything else that's required to verify the signature.

PSS in contrast has the following external, unauthenticated parameters:

RSASSA-PSS-params ::= SEQUENCE {
     hashAlgorithm      [0] {
                        SEQUENCE {
          algorithm     OBJECT IDENTIFER,
          parameters    ANY DEFINED BY algorithm OPTIONAL
          },
     maskGenAlgorithm   [1] {
                        SEQUENCE {
          algorithm     OBJECT IDENTIFER DEFAULT mgf1SHA1,
          parameters    SEQUENCE {
              algorithm OBJECT IDENTIFIER,
              parameters ANY DEFINED BY algorithm OPTIONAL
              },
          }
     saltLength         [2] {
          length        INTEGER DEFAULT 20
          },
     trailerField       [3] {
          trailer       INTEGER DEFAULT trailerFieldBC
          }
     }

The PSS verification operation, again following the common RSA operation, is
as follows...

Actually I won't post it here.  No matter how much I try and condense it, I
can't get it down to less than four solid pages of pseudocode.  In addition, I
have no idea whether it's actually correct or not, meaning whether it captures
all of the boundless corner cases and conditions that it's required to handle.
Just to help with the explanation that follows, here's a diagram of what's
going on.  mHash is the hash of the message as for PKCS #1 (this diagram
requires a fixed-width font to see):

         +-----------------------------------+------+---+
    EM = |#           maskedDB               | mHash|xDB|
         +-----------------------------------+------+---+
                         |                       |
                         v                       |
                        xor <------- MGF() ------+---+
                         |                           |
                         v                           |
         +---------------------------+-------+       |
    DB = |        00 ... 00 01       | salt  |       |
         +---------------------------+-------+       |
                                         |           |
                                         |           |
                                         v           |
         +-------------------+-------+-------+       |
    M' = |      00 x 8       |  hash | salt  |---+   |
         +-------------------+-------+-------+   |   |
                                                 v   |
                                              Hash() |
                                                 |   |
                                                 v   v
                                                Compare

Now let's look at what an attacker can do with the above.  The immediately
obvious, trivial attack is a hash-substitution attack.  Unlike PKCS #1, PSS
doesn't encode the hash algorithm used anywhere in the signature.  This
encoding, known as a hash function firewall ("On Hash Function Firewalls in
Signature Schemes", CT-RSA 2002) was ironically not added to PSS because it
would have caused problems with the security proof.  By changing hashAlgorithm
to whatever you like, for example an algorithm of the same size that you know
how to break, you can forge the signature.  Change the hash from SHA-2/256 to
Streebog, Blake2, Keccak, CRC-256, XOR256, whatever you like, PSS won't detect
the change, making it only as strong as the weakest hash algorithm of the same
bit width that the victim will accept.

There's a lot more fun you can have with this.  Remember that you've got a
huge pile of external parameters, all controllable by the attacker.  For
example look at the way MGF() is applied, it's a simple stream cipher, meaning
that you can flip any bit in DB by flipping the corresponding bit in EM.  Note
that there's just a single bit in DB that tells you where the salt starts, so
if you can flip a bit in EM it'll set the corresponding bit in DB to 1.  In
theory you then run into a problem with the salt, but since the salt length is
another attacker-controlled parameter you just extend it to cover the extra
data that's been added by the bit flip.

Then there's M', which is assembled by the victim under the attacker's control
since they can set the salt length and hash algorithm to anything they want,
which PSS again won't detect.

There's quite a large pile of problems present here:

* There's no internal structure to the data so you can't see what's what, and
   in particular where one field ends and another begins.  Specifically, it
   violates Abadi and Needham's Principle #1, "Every message should say what it
   means" ("Prudent Engineering Practice for Cryptographic Protocols", Security
   and Privacy 1994).

* There's a ton of external, attacker-controlled parameters that allow an
   attacker excessive control over every step of the verification process (see
   also the previous point).

* The algorithm is ridiculously over-parameterised (why would you want to use
   a different hash algorithm for the message hash and mask generation hash, or
   a salt of a different length than the hash, or ...), all of which helps the
   attacker.

* It uses a stream cipher (XOR-mask) that allows you to make easily
   predictable changes to the data.

* The victim has to assemble the data block M' using attacker-controlled
   parameters rather than recovering it from the signature.

* The high level of complexity and special-case checks and operations make it
   pretty much impossible to implement in a side-channel-free manner.

It's almost a textbook example of what not to do when designing a signature,
or more generally crypto, mechanism.

(In its defence, PSS was very much a product of the times, with building
blocks like the hash function and MGF and parameters values subject to change,
so that parameter-combinatorial-explosion ended up being a frequent design
pattern, with the expectation being that usage profiles would address some of
the issues that arose.  Unfortunately none were ever really created beyond de
facto usage patterns, there's a suggested one at the end of this writeup.  For
a great introduction to the early history of RSA signature mechanism design,
see Burt Kaliski's talk from ZKProof 2019,
https://www.youtube.com/watch?v=sqsDKjPaJVg).

At the moment there isn't an obvious attack that takes advantage of this
beyond the obvious hash-substitution, but it gives the attacker an awful lot
of control over the internals of the PSS verification operation.  Contrast
this with PKCS #1, where there's only one fixed-format string possible for
each hash algorithm, and no ambiguity or manipulation by the attacker is
possible.

In terms of the unauthenticated parameters, in theory there is sort-of
protection against these in both X.509 and S/MIME / CMS, but in practice there
isn't.  X.509 includes the signature algorithm parameters in the certificate
in the form of the badly-named 'signature' field, which doesn't contain the
signature at all but the algorithm parameters.  Support for this is hit-and-
miss, with some implementations skipping it (which is perfectly justifiable,
since there's never been a need for it if you're not using PSS), some
implementations checking basic parameters but not the mass of optional and
situation-specific values used in PSS, and some meticulously checking every
parameter.  CMS in theory has a means of protecting the parameters by signing
them into the SignedAttributes as an RFC 6211 Algorithm Identifier Protection
Attribute, but I know of only one implementation that supports that, and in
any case if you've got a hash function that you can create collisions with you
can rewrite the CMS signature to remove the SignedAttributes.  Note that this
problem is specific to PSS, it doesn't affect PKCS #1 which encodes the
algorithm information into the signature.

So for the vanishingly small number of users of PSS, I'd recommend switching
to something more secure like PKCS #1, and disabling the PSS code before
someone attacks you through it.  If you must use PSS then hardcode in one, and
only one, signature scheme, say { hashAlgorithm = SHA-256, maskGenAlgorithm =
mgf1 with SHA-256, saltLength = 32, trailerField = trailerFieldBC } and don't
allow any substitutions.

"Beware of bugs in the above signature scheme; I have only proved it secure,
  not implemented it"
  - Apologies to Donald Knuth.

Thanks to various members of the cryptography community who commented on early
drafts of this writeup.  My opinions, not theirs.

Peter.
_______________________________________________
The cryptography mailing list
[e-mail]
https://www.metzdowd.com/mailman/listinfo/cryptography