From what I read in Wikipedia's article "Elliptic Curve DSA ~ Security", the "deterministic" generation of $k$ can help prevent certain type of attacks (such as the one happened to Sony).

However, wouldn't the deterministic property be predictable as compared with "probabilistic encryption"? To me, it seems like RSA does use padding to make it non-deterministic. From a security point of view of, wouldn't that be undesirable?


We are talking about signatures here, not encryption. The two activities are quite different. In the case of signatures, there is nothing secret except the private key, whereas in the case of encryption, both the private key and the message to encrypt should remain confidential (you encrypt the data precisely because you want to keep it confidential).

Asymmetric encryption requires some randomization because if it was deterministic, then an attacker could make an exhaustive search on the data itself. In the case of signatures, there is no confidential data on which the attacker may want to run such a brute force attack (indeed, no confidential data at all), so this specific issue does not apply.

Indeed, the "old" padding for RSA signatures (EMSA-PKCS1-v1_5, more usually known as "PKCS#1 v1.5") is deterministic, and, as yet, unbroken. The newer version (EMSA-PSS) is randomized, but, as PKCS#1 puts it:

RSASSA-PSS is different from other RSA-based signature schemes in that it is probabilistic rather than deterministic, incorporating a randomly generated salt value. The salt value enhances the security of the scheme by affording a "tighter" security proof than deterministic alternatives such as Full Domain Hashing (FDH); see [4] for discussion. However, the randomness is not critical to security. In situations where random generation is not possible, a fixed value or a sequence number could be employed instead, with the resulting provable security similar to that of FDH [12].

(Emphasis is mine.)

In the case of (EC)DSA, the $k$ value has some specific requirements which do not have a counterpart in RSA; namely, from the point of view of any attacker, $k$ should be as if it was generated randomly and uniformly in the $1..q-1$ range, where $q$ is the order of the subgroup in which the algorithm is applied, with one optimization: it is permitted to reuse the same $k$ value as a previous signature, provided that all the inputs are the same (same private key, same input message). We can see that this "optimization" is safe if we consider the following attack model:

  • The attacker is given access to a black box which computes the signature on messages that the attacker chooses, using a private key $x$ that the attacker does not know.
  • The attacker may submit $n$ signature requests to the box ($n$ messages $m_i$), thus resulting in $n$ corresponding signatures ($s_i$).
  • The attacker's goal is to make a forgery: a new message $m$, distinct from all the $m_i$, and a corresponding signature $s$.

The "optimization" is then modelled as a filter/cache on the box, which remembers past requests from the attacker; if a request is made for a message which was already seen ($m_j = m_i$ for $j \gt i$), then the filter blocks the request, and returns the previous signature instead of making the box work again (i.e. it forces $s_j = s_i$). In the model above, this is a restriction on the attacker, so this can only strengthen the algorithm, not weaken it.

This model actually explains why, in all generality, derandomization is safe for signature algorithms: any random value used in the course of the algorithm can be replaced with a deterministically generated value, provided that the generation system takes as input both the message and the private key, and acts as a random oracle. This is exactly what RFC 6979 does. (Of course, random oracles are more easily talked about than incarnated; e.g. see this. RFC 6979 uses HMAC-DRBG as a "practical random oracle".)

| improve this answer | |
  • $\begingroup$ Good to have reply straight from the source, i.e. writer of the RFC. Overall, I appreciate introducing derandomized algorithms, because security is just too important to be left on chance. I like your description of random oracle, maybe you should attempt to get it on the short list of algorithms IETF uses. $\endgroup$ – user4982 Oct 24 '13 at 15:09

No. Public key encryption has to be probabilistic (in the sense that we have generic attacks against deterministic encryption schemes), but signatures don't. RSA-FDH is one example of a fully deterministic scheme that is usefully secure.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.