Is it possible to make RSA-PSS signing deterministic without loss of security?
Specifically, I would use Blake2b of the key and message to generate the salt.
6
$\begingroup$
$\endgroup$
-
2$\begingroup$ There's a discussion about that in PKCS#1v2, end of section 8.1. I'm in for a real answer to the question, with preferably quantitative proof, and no secret involved in preparing the salt (that's cheating; and impractical, for the verifier is assumed to hold no secret, and then can't ascertain that there is no side channel in the salt). $\endgroup$ – fgrieu Apr 14 '16 at 16:33
-
$\begingroup$ I think this paper could help towards a (not fully positive) answer: J.S. Coron, Optimal security proofs for PSS and other signature schemes, in proceedings of Eurocrypt 2002. $\endgroup$ – fgrieu Apr 15 '16 at 6:36
-
$\begingroup$ Beware that using any operation on the private key other than RSA will not be compatible with most hardware tokens. The encoding of the private key must be deterministic as well (possibly over multiple implementations) or your end result won't be deterministic either. Finally note that PKCS#1 v1.5 padding for signature generation isn't broken so PSS isn't really required to generate a signature that's most likely - but not provably - secure. Good question regardless. $\endgroup$ – Maarten - reinstate Monica♦ Apr 15 '16 at 8:55
7
$\begingroup$
$\endgroup$
Any probabilistic signature scheme can be made deterministic without any loss of security. The generic transformation is as follows:
- Let $(pk,sk)$ be the key-pair of the original signature scheme
- Choose a random key $k$ for a pseudorandom function $F$ (you can use HMAC or CMAC), where the output of $F$ is enough randomness used to sign. This key is part of the secret key.
- In order to sign on a message $m$: First compute $r=F_k(m)$. Then, sign on message $m$ using randomness $r$.
It is not difficult to prove that the scheme is secure, as long as the probabilistic scheme is secure and $F$ is a PRF. (The bounds of the probabilistic scheme stay the same as well; the only difference is that you add the probability of breaking the PRF, which is insignificant.) In practice, this can be very efficient, by using HMAC or CMAC and then stretching the output to the required length using the result as a key to AES-CTR, or using HKDF or something of the sort.
In fact, it is very unfortunate that this is not the standard way of deploying dSA and ECDSA, since that would resolve the major weakness which is that if the same randomness is used for different messages, then the secret key is revealed.
answered Apr 15 '16 at 9:20
-
$\begingroup$ With regards to making this the standard way: you could still make this non-deterministic by including a salt, right? Not all protocols work equally well with deterministic signatures (I assume). $\endgroup$ – Maarten - reinstate Monica♦ Apr 15 '16 at 10:15
-
$\begingroup$ An issue with this method is that the verifier (not knowing $k$) can not be convinced that the signature does not convey a subliminal channel. $\endgroup$ – fgrieu Apr 15 '16 at 18:01
-
1$\begingroup$ @fgrieu The aim of this solution is not prevent a subliminal channel; for that you should use a truly deterministic scheme with a single possible signature for every message. $\endgroup$ – Yehuda Lindell Apr 17 '16 at 6:16
-
$\begingroup$ @MaartenBodewes I'm not sure that I can really answer the question as it seems very generic. I don't know of a protocol that needs a probabilistic signature scheme. If you need something to prevent replay then you do this via the message (have a random challenge etc.). But, maybe there is a protocol that specifically requires a probabilistic signature; don't know.... $\endgroup$ – Yehuda Lindell Apr 17 '16 at 6:18
-
$\begingroup$ Does using a secure hash of the private key as your $k$ still work? I would imagine that it does work (in the random oracle model). $\endgroup$ – Demi Oct 7 '16 at 19:08
