Cryptography
hash dsa cryptographic-hardware
Updated Fri, 20 May 2022 02:33:20 GMT

(EC)DSA signature without hashing, or with offloaded hash?


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?

Solution

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

Comments (4)

  • +1 – 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. — Jul 08, 2017 at 20:47  
  • +0 – @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. — Jul 09, 2017 at 12:27  
  • +0 – Does this show that DSA is not secure when there is no hash protocol? — Nov 28, 2017 at 19:44  
  • +0 – @UsernameUnknown In some sense, yes. — Dec 07, 2017 at 10:22  

External Links

External links referenced by this document:

References