Add RSA-PSS signing

[DemiMarie]

If ring is going to support RSA-PKCS#1.5 signing it should support RSA-PSS signing.

[briansmith]

This should require just simple modifications to whatever is done in #208.

[burdges]

It's maybe worth noting that RSA usage is declining in classical cryptographic applications and increasingly for situations needing homomorphic properties, like Paillier, voting, accumulators, etc., which means lower level access. Yey foot guns!

In Taler (not in Rust) for example, we use RSA blind signatures because Schnorr blind signatures would require an extra round trip and BLS blind signatures employ a Weil pairing. PSS is useless in that setting. Instead, one needs a full domain hash and an entirely different proof of security from different underlying assumption.

[briansmith]

See https://github.com/briansmith/ring/issues/115#issuecomment-227272106 for the details of how to support the various PSS parameters.

It's probably a good idea to implement PSS verification first.

[briansmith]

Regarding how the salts work, the main question is whether we can safely implement a deterministic RSA-PSS scheme that interops with other implementations, particularly implementations that are designed according to TLS 1.3's requirements. For now, I suggest that we always generate a fixed salt that has the same length as the digest's output length, e.g. 32 bytes of zeros for SHA-256 and 48 bytes of zeros for SHA-384. This way, our signatures will be completely deterministic.

Internally, in order to pass the NIST test suite, we'll have to support salts with other values.

References in support of doing this:

• Optimal Security Proofs for Full Domain Hash, Revisited: "However, since PSS (with random salt of arbitrary length) is at least as secure as FDH, we obtain as a corollary from Section 3 a tight security proof from lossiness to the security of PSS, with random salt of arbitrary (possibly zero) length."
• Efficiency Improvements for Signature Schemes with Tight Security Reductions: "We show a variant of PSS which avoids the random salt altogether yet has an equally-tight security reduction."
• Another Look at “Provable Security”, section "A Variant of PSS".
• Another Look at “Provable Security” II: Section "The implausible magic of one bit"
• http://www5.rz.rub.de:8032/mam/foc/content/publ/rsa-fdh_fullversion.pdf
• https://eprint.iacr.org/2015/517.pdf - Section 4.2
• http://crypto.stackexchange.com/questions/1217/rsa-pss-salt-size.

[briansmith]

References in support of a randomized salt being useful:

• How Risky is the Random Oracle Model?: “While RSA-KW has a much better security reduction than RSA-FDH, there are essentially the same attacks on both RSA-KW and RSA-FDH as soon as there are defects in the full-domain hash. On the other hand, RSA-PSS with a large salt seems more robust than all other paddings, especially if one uses h(r||m) instead of h(m||r). This differs from the conclusion of [38], where it was argued that RSA-FDH was the best method known to sign with RSA.”

[briansmith]

More support of randomized signatures: Making RSA-PSS Provably Secure Against Non-Random Faults, which also cites other work on the benefits of PSS-style randomization regarding fault attacks. However, it isn't clear that PSS benefits us much regarding fault attacks given that we already verify the result of the modular exponentiation x = n^d (mod n) by verifying x^e (mod n).

[DemiMarie]

One thought might be to do what deterministic DSA and ECDSA implementations (which leak the private key if the ephemeral key is not. random) do and generate the salt from the private key and message. We know that the private key has enough entropy, so we just need to assume a PDF that is good.

On Aug 9, 2016 5:57 PM, "Brian Smith" notifications@github.com wrote:

More support of randomized signatures: Making RSA-PSS Provably Secure Against Non-Random Faults https://eprint.iacr.org/2014/252, which also cites other work on the benefits of PSS-style randomization regarding fault attacks. However, it isn't clear that PSS benefits us much regarding fault attacks given that we already verify the result of the modular exponentiation x = nd (mod n) by verifying xe (mod n).

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/briansmith/ring/issues/213#issuecomment-238704994, or mute the thread https://github.com/notifications/unsubscribe-auth/AGGWB9frAoZ96BkbdmCu-XRZx2fMDAFIks5qePfZgaJpZM4Iyb6p .

[briansmith]

The deterministic RSA-PSS scheme I suggested (just a fixed zero-valued salt) seems too controversial to add just yet. @samscott89 already wrote the randomized-salt version. Let's move the discussion of how to do deterministic RSA-PSS and/or FDH safely to #264.

[briansmith]

The implementation of this landed in master in #262; see https://github.com/briansmith/ring/pull/262#issuecomment-260765364.

The main thing that's missing at this point is the tests for signatures with public key moduli that are {2048, 4096, 8192} ± 1 bit. Unlike for verification, we don't have any tests for that at the padding layer, and like for verification, we don't have tests for that that cover that for the entire signing operation. More generally we should have test vectors for all the checks in the code; in particular, let's look at the code coverage report and verify that every return Err(error::Unspecified); line is either covered or has a note about why it is impossible.

[briansmith]

Again, @samscott89 did an amazing job adding the tests, in addition to doing the implementation work! Thanks!