4
$\begingroup$

I'm working with a C++ library and I’m currently investigating the changes needed to accommodate Deterministic DSA and ECDSA Signatures (RFC 6979). While the RFC 6979 changes are specific, I'm trying to understand more about the breadth of the potential changes to some of C++ classes involved in the implementation.

Is it possible to pair a “Discrete Log/ElGamal”-alike signature scheme (like – for example – DSA/ECDSA), adorn it with determinism (the deterministic $k$), and then pair it with an encoding method which uses randomness (maybe like something found in a PSS, perhaps with a salt)?

I realize RSA-PSS is a different class of signature schemes. I'm less clear or some of the unique or unusual pairings that may be experienced in the field with lesser known schemes.

This question on pairing primitives is about extensibility planning in software. It leaves open the mathematical questions of correctness and proofs. We often have to ask a theoretical crypto question here to ensure the cryptography is well represented, even though it could be off-topic.

Here's a question that touches on similar: Why use randomness in digital signature algorithms?

De-randomization can be used to turn a randomized signature scheme (such as RSASSA-PSS of PKCS#1v2 parameterized with significant random salt) into a deterministic one ...

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

First, some clarifications.

A randomised signature scheme is a signature scheme that produces randomised signatures, that is, if you sign the same message twice, you are not likely to get the same signature twice.

We can "derandomise" a signature scheme by replacing the randomness with pseudo-randomness generated as a function of the messaget to be signed and a secret key. The result is a deterministic signature scheme, where if you sign the same message twice, you will get the same pseudo-randomness and therefore the same signature. If the randomised scheme was secure and the derandomising was done correctly, the deterministic scheme will also be secure.

A padding scheme is a way to encode messages in one "format" as messages of a different "format", typically arbitrary bit strings as bit strings of length divisible by some number, or short bit strings as long numbers, or ... Usually, these schemes are in some sense injective, in that if you encode two distinct messages, you never get the same padded message.

A randomised padding scheme is a padding scheme that if you encode the same message twice, you are not likely to get the same padded message twice. Such schemes can sometimes be used to turn certain somewhat insecure signature schemes into secure signature schemes, typically by turning the message to be signed into a random-looking message that can be safely signed by the insecure scheme.

Now, the answer: Given the way we define "secure signature scheme", composing a secure signature scheme with any padding scheme cannot result in an insecure scheme (just a pointless scheme). So:

  • Derandomising DSA results in a deterministic signature scheme.
  • Since we believe DSA is secure, derandomised DSA should also be secure.
  • Since we believe derandomised DSA is secure, derandomised DSA composed with a padding scheme like PSS should also be secure (but pointless).

So the answer to your question appears to be yes.

However, one caveat. DSA involves a hash function: you hash the message and then the hash is included in some number-theoretic computations that results in a signature. The hash is an integral part of DSA. If you replace the hash with (say) PSS, you have not composed a secure signature scheme with a padding scheme, but modified a secure scheme. And when you modify schemes, the composition result I mentioned does not apply, and you may end up with something insecure.

Improve this answer
$\endgroup$
1
$\begingroup$

Let's look at the DSA algorithm and assume for simplicity we have two messages with $k_1$ and $k_2$ known to the attacker and all checks for "if this is 0, pick a new k" work out fine. This represents an approach like: We can easily guess $k$, because it is chosen in some deterministic way, possibly depending on the message.

Let's denote $m_i$ for message $m$ with the choice of $k_i$. So we got a $m_1$ with signature $r_1,s_1$ and $k_1$, and $m_2$ with signature $r_2,s_2$ and $k_2$(for simplicity, I will omit the moduli):

$$ r_1 = g^{k_1}, r_2 = g^{k_2}\\ s_1 = {k_1}^{-1}(H(m_1) + x r_1) = {k_1}^{-1} H(m_3) + {k_1}^{-1}g^{k_1}x\\ s_2 = {k_2}^{-1}(H(m_2) + x r_2) = {k_2}^{-1} H(m_2) + {k_2}^{-1} g^{k_2}x $$

Now we can calculate: $$s_2 - s_1 = {k_2}^{-1} H(m_2) - {k_1}^{-1} H(m_3) + ({k_2}^{-1} g^{k_2} - {k_1}^{-1} g^{{k_1}})x\\ x = \frac{s_2 - s_1 - {k_2}^{-1} H(m_2) + {k_1}^{-1} H(m_3)}{{k_2}^{-1} g^{k_2} - {k_1}^{-1} g^{{k_1}}}$$

We know all the variables, if we know the two signatures and their according values for $k$, even if they are different. This means, it is not enough if every $k$ is unique but possibly known (or guessable) to the attacker, due to the deterministic stragety.

So no, it is vital for the signature algorithm, that the attacker can not guess $k$. It is not enough to have a nonce there, it has to be chosen at random.

Improve this answer
$\endgroup$
3
  • $\begingroup$ What does this have to do with the question, which specifically mentions RFC 6979? Are you claiming that RFC6979 makes it possible for someone who doesn't know the private key to recover $k$? $\endgroup$
    – poncho
    Aug 31, 2016 at 19:09
  • $\begingroup$ Also, if you do know the value $k$ that was used to sign message $m$, we have $x = r^{-1}(sk - H(m))$, so you don't need two different messages... $\endgroup$
    – poncho
    Aug 31, 2016 at 19:36
  • $\begingroup$ @tylo: $k$ is indeed chosen in a deterministic way but its computation requires some secret; for example, for a message $m$, suppose that $k$ is defined as $k = H(K,m)$ where $K$ is a secret key only known to the signer. $\endgroup$
    – user94293
    Nov 30, 2016 at 6:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.