11
$\begingroup$

In (EC)DSA as per FIPS 186-4, the message to sign is first hashed. Imagine that we skip this hashing stage, instead put the message where the hash was, and constrain the size of message $h$ to the original hash's output width $N$ bits. The resulting scheme is vulnerable to (at least) these existential forgeries ($q$ is the multiplicative group order):

  • any signature for message $0\le h<2^N-q$ is also valid for message $h+q$;
  • a valid signature for messages $h=0$ and $h=q$ is easy to obtain: in DSA, $(r,s)$ with $r=s=y\bmod q$ does the trick, where $y$ is the public key; there's an analog with ECDSA, which $r=s=x_A\bmod q$, where $x_A$ is the $x$ coordinate of the public key, and $q=n$.

Are other attacks possible? In particular, does temporary access to a signing oracle allow a total break (key extraction or other mean to sign any message)?


The question is of direct interest when one wants to lower the communication overhead between a signing device and a host using it to (EC)DSA-sign large messages: can we fully offload the hash computation to the host? I believe that holds (and as noted in comments, that seems to be practice), but can we demonstrate that? If not, how can we safely offload most of that computation, without breaking standard conformance?

$\endgroup$
  • 1
    $\begingroup$ From what I can tell, off-loading the hashing to middleware on the host is already (commonly?) done in practice. $\endgroup$ – SEJPM Mar 19 '17 at 16:09
  • $\begingroup$ @SEJPM: I know examples of hash offloading (and even padding offloading) in RSA signature, where that is quite convincingly safe. If you have a public reference to an example of hash offloading for (EC)DSA, I'd like to know. $\endgroup$ – fgrieu Mar 19 '17 at 16:25
  • 2
    $\begingroup$ My Smartcard-HSM supports that using the OpenSC middle-ware (ie it claims plain ECDSA support and ECDSA-SHA1 support), if I find more I'll link it. $\endgroup$ – SEJPM Mar 19 '17 at 16:38
  • 1
    $\begingroup$ @fgrieu What I meant is: at the time of standardisation it was known that there are close variants of DSA (e.g., DSA-II or the Pointcheval-Stern signature) that were provably secure. These basically involve a minor modification, that of computing $h=H(m,r)$ instead of just $h=H(m)$. But these were ignored. $\endgroup$ – Occams_Trimmer Jul 9 '17 at 12:36
  • 1
    $\begingroup$ @Occams Trimmer: this DSA-II signature scheme is standardized as the Pointcheval/Vaudenay algorithm at least since ISO/IEC 14888-3:2006 (It is not to be confused with the Pintsov-Vanstone Elliptic Curcve signature scheme with message recovery, aka ECPVS, PVSSR, ECSSR-PV of ISO/IEC 9796-3:2006). Too bad that's not in FIPS 186-4. $\endgroup$ – fgrieu Jul 10 '17 at 8:27
6
$\begingroup$

Let's focus on DSA. The signing on a message $m\in \mathbb{Z}_q$ for the suggested "no-hash" protocol is done as follows:

  1. Pick $k\in_R \mathbb{Z}_q$, compute $r=f(g^k)$, where $f(\cdot):=(\cdot \bmod p) \bmod q$.
  2. Compute $s=k^{-1}(m+xr)\bmod q$
  3. Return $(r,s)$ if the signature is not degenerate.

The verification algorithm, on input $(m,s,r)$, checks if $f((g^m\cdot y^r)^{(1/s)})=r$.

The following consists of a forgery on a random message under the key-only attack.

  1. Let $K=g^a\cdot y^b$, where $a,b\in_R\mathbb{Z}_q$
  2. Compute $r=f(K)$, and set $s=r/b$
  3. Return $(r,s)$ as a forgery on $m=(a\cdot r)/b$

(I'll add the references in due course.)

$\endgroup$
  • 1
    $\begingroup$ This indeed is a working existential forgery. The verifier computes $f((g^m\cdot y^r)^{(1/s)})$, that is $f((g^{a\,r/b}\cdot y^r)^{(b/r)})$, that is $f(g^a\cdot y^b)$, and that matches $r$. The signature $(y,y)$ for message $0$ of the question is a special case with $a=0$ and $b=1$. However, as is, the message $m$ signed is uncontrolled; and temporary access to a signing oracle does not yield a total break. $\endgroup$ – fgrieu Jul 8 '17 at 20:47
  • $\begingroup$ @However, as is, the message m signed is uncontrolled; and temporary access to a signing oracle does not yield a total break. That's correct. Let's see if the attack can be extended. $\endgroup$ – Occams_Trimmer Jul 9 '17 at 12:27
  • $\begingroup$ Does this show that DSA is not secure when there is no hash protocol? $\endgroup$ – Username Unknown Nov 28 '17 at 19:44
  • $\begingroup$ @UsernameUnknown In some sense, yes. $\endgroup$ – Occams_Trimmer Dec 7 '17 at 10:22

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.