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$.

These are easily solved by further restricting the message space to $[1,q)$.

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?

  • 2
    $\begingroup$ From what I can tell, off-loading the hashing to middleware on the host is already (commonly?) done in practice. $\endgroup$
    – SEJPM
    Commented Mar 19, 2017 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
    Commented Mar 19, 2017 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
    Commented Mar 19, 2017 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$
    – ckamath
    Commented Jul 9, 2017 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
    Commented Jul 10, 2017 at 8:27

1 Answer 1


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$

This attack is implicit in [FKP], which studies the security of EC(DSA) (in a restricted model).

[FKP]: Fersch, Kiltz and Poettering, On the One-Per-Message Unforgeability of (EC)DSA and its Variants, TCC 2017

  • 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
    Commented Jul 8, 2017 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$
    – ckamath
    Commented Jul 9, 2017 at 12:27
  • $\begingroup$ Does this show that DSA is not secure when there is no hash protocol? $\endgroup$ Commented Nov 28, 2017 at 19:44
  • $\begingroup$ @UsernameUnknown In some sense, yes. $\endgroup$
    – ckamath
    Commented Dec 7, 2017 at 10:22

Your Answer

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

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