Enhancing an Attack to DSA Schemes

Abstract

In this paper, we improve the theoretical background of the attacks on the DSA schemes of a previous paper, and we present some new more practical attacks.

MSC 2010:  94A60 , 11T71 , 11Y16

1 Introduction

In August 1991, the U.S. government’s National Institute of Standards and Technology (NIST) proposed the Digital Signature Algorithm (DSA) for digital signatures [13, 15]. This algorithm has become a standard [6] and was called Digital Signature Standard (DSS). In 1998, an elliptic curve analogue called Elliptic Curve Digital Signature Algorithm (ECDSA) was proposed and standardized, see [10]. In the first subsection we recall the outlines of DSA and ECDSA.

1.1 The DSA and ECDSA Schemes

First, let us summarize DSA. The signer chooses a prime p of size between 1024 and 3072 bits with increments of 1024, as recommended in FIPS 186-3 [6, p. 15]. Also, he chooses a prime q of size 160, 224 or 256 bits, with $q|p-1$ and a generator g of the unique order q subgroup G of the multiplicative group $\mathbb {F}_p^*$ of the prime finite field $\mathbb {F}_p$. Furthermore, he selects a randomly $a \in \{1,\ldots ,q-1\}$ and computes $R = g^a \, \bmod \, p$. The public key of the signer is (p, q, g, R) and his private key a. He also publishes a hash function $h : \{0,1\}^* \rightarrow \{0,\ldots ,q-1\}$. To sign a message $m\in \{0,1\}^*$, he selects randomly $k \in \{1,\ldots ,q-1\}$ which is the ephemeral key, and computes $r = (g^k \ \bmod \ p) \ \bmod \ q$ and $s = k^{-1}(h(m)+ar) \, \bmod \, q$. The signature of m is the pair (r, s). The signature is valid if and only if we have:

$$r = ((g^{s^{-1}h(m)\mathrm{mod}q}R^{s^{-1}r \bmod \, q})\, \bmod \, p) \, \bmod \, q.$$

For the ECDSA the signer selects an elliptic curve E over $\mathbb {F}_p$, a point $P\in E(\mathbb {F}_p)$ with order a prime q of size at least 160 bits. According to FIPS 186-3, the prime p must be in the set $\{160,224,256,512\}.$ Further, he selects randomly $a \in \{1,\ldots ,q-1\}$ and computes $Q = aP$. The public key of the signer is (E, p, q, P, Q) and his private key a. He also publishes a hash function $h : \{0,1\}^* \rightarrow \{0,\ldots ,q-1\}$. To sign a message m, he selects randomly $k \in \{1,\ldots ,q-1\}$ which is the ephemeral key and computes $kP = (x,y)$ (where x and y are regarded as integers between 0 and $p-1$). Next, he computes $r = x \ \mathrm{mod} \ q$ and $s = k^{-1}(h(m)+ar) \ \mathrm{mod} \ q$. The signature of m is (r, s). For its verification one computes

$$u_1 = s^{-1}h(m) \ \mathrm{mod} \ q, \ \ u_2 = s^{-1}r \ \mathrm{mod} \ q, \ \ u_1P+u_2Q = (x_0,y_0).$$

He accepts the signature if and only if $r = x_0 \, \bmod \, q$.

The security of the two systems is relied on the assumption that the only way to forge the signature is to recover either the secret key a, or the ephemeral key k (in this case is very easy to compute a). Thus, the parameters of these systems were chosen in such a way that the computation of discrete logarithms is computationally infeasible.

1.2 Our Contribution

Except the attacks in discrete logarithm problem, we have attacks based on the equality $s= k^{-1}(h(m)+ar) \ \mathrm{mod} \ q$ which use lattice reduction techniques [1,2,3,4,5, 11, 12, 16,17,18,19]. In this paper, we also use this equality and following the ideas of [19], we improve the efficiency of attacks on the DSA schemes described in it.

The attack described in [19] is based on a system of linear congruences of a particular form which has at most a unique solution below a certain bound, which can be computed efficiently. Thus, in case where the length of a vector, having as coordinates the secret and the ephemeral keys of some signed message is quite small, the secret key can be computed. More precisely in this work, we also consider the system of linear congruences of [19] and we improve the upper bound under which it has at most one solution. This extension provides an improvement of the attack [19], which also remains deterministic. Thus, when some signed messages are available, we can construct a such system whose solution has among its coordinates the secret key, and so it is possible to find it in practical time.

Furthermore, an heuristic improvement based on our attack is given. We update experimental results on (EC)DSA based on known bits of the ephemeral keys. In fact we prove that if we know 1 bit of a suitable multiple of the ephemeral keys for 206 signatures, we can find the secret key with success rate $62\%.$ The previous best result was of Liu and Nguyen [12], where they provided a probabilistic attack based on enumeration techniques, where managed to find the secret key if they know 2 bits of 100 ephemeral keys. The attack provided in [12] first reduces the problem of finding the secret key, to the hidden number problem (HNP) and then reduces HNP to a variant of CVP (called Bounded Decoded Distance problem : BDD).

The Structure of the Paper. The paper is organized as follows. In Sect. 2, we recall some basic results about lattices, and the Babai’s Nearest Plane Algorithm. In Sect. 3, we prove some result which we need for the presentation of our attacks. Our attacks are presented in Sects. 4. Some experimental results are given in Sect. 5. Finally, Sect. 6 concludes the paper.

2 Background on Lattices

In this section, we collect several well-known facts about lattices which form the background to our algorithms.

Let ${\mathbf{{b}}_1,\mathbf{{b}}_2,\ldots ,\mathbf{{b}}_n}$ linearly independent vectors of ${\mathbb {R}}^{m}$. The set

$$\mathcal {L} = \left\{ \sum _{j=1}^{n}\alpha _j\mathbf{{b}}_j : \alpha _j\in \mathbb {Z}, 1\le j\le n\right\} $$

is called a lattice and the set $\mathcal {B} = \{\mathbf{{b}}_1,\ldots ,\mathbf{{b}}_n\}$ a basis of $\mathcal {L}$. All the bases of $\mathcal {L}$ have the same number of elements n which is called dimension or rank of $\mathcal {L}$. If $n=m$, then the lattice $\mathcal {L}$ is said to have full rank. We denote by M the $n\times m$-matrix having as rows the vectors $\mathbf{{b}}_1,\ldots ,\mathbf{{b}}_n$. If $\mathcal {L}$ has full rank, then the volume of the lattice $\mathcal {L}$ is defined to be the positive number $|\det {M}|$ which is independent from the basis $\mathcal {B}$. It is denoted by $vol(\mathcal {L})$ or $\det {\mathcal {L}}$ (see also [7]). If $\mathbf{v}\in \mathbb {R}^m$, then $\Vert \mathbf{v}\Vert$ denotes, as usually, the Euclidean norm of $\mathbf{v}$. We denote by LLL(M), the application of well-known LLL-algorithm on the rows of M. Finally, we denote by $\lambda _1(\mathcal {L})$ the smaller of the lengths of vectors of $\mathcal {L}$.

We define the approximate Closest Vector Problem $(CVP_{\gamma _{n}}(L))$ as follows: Given a lattice $\mathcal {L}\subset {\mathbb {Z}}^m$ of rank n and a vector $\mathbf{t}\in {\mathbb {R}}^m,$ find a vector $\mathbf{u}\in \mathcal {L}$ such that, for every $\mathbf{u}'\in \mathcal {L}$ we have:

$$\Vert \mathbf{u}-\mathbf{t}\Vert \le \gamma _n \Vert \mathbf{u}'-\mathbf{t}\Vert \ \ (\text {for some}\ \gamma _n\ge 1).$$

We say that we have a CVP oracle, if we have an efficient probabilistic algorithm that solves $\mathrm{CVP}_{\gamma _n}$ for $\gamma _n=1.$ To solve $\mathrm{{CVP}}_{\gamma _n}$, we usually use Babai’s algorithm [7, Chapter 18] (which has polynomial running time). In fact, combining this algorithm with LLL algorithm, we solve $\mathrm{{CVP}}_{\gamma }(\mathcal {L})$ for some lattice $\mathcal {L}\subset {\mathbb {Z}}^m,$ for $\gamma _n = 2^{n/2}$ and $n=rank(\mathcal {L})$ in polynomial time.

Note that there is a variant of CVP, called BDD, where we search for vectors $\mathbf{u}$ such that $\Vert \mathbf{u}-\mathbf{t}\Vert \le \lambda _1(L)/2.$ Further, there are enumeration algorithms that compute all the lattice vectors within distance R from the target vector, see [8, 9]. These algorithms are not of polynomial time with respect to the rank of the lattice.

3 Auxiliary Results

In this section we prove some results that we need for the description of our attack.

Proposition 1

Let n, q and $A_j$ be positive integers satisfying

$$\begin{aligned} \frac{q^{\frac{j}{n+1}+f_q(n)}}{2}< A_j <\frac{q^{\frac{j}{n+1}+f_q(n)}}{1.5} \ \ \ (j=1,\ldots ,n), \end{aligned}$$

(1)

where $f_q(n)$ is a positive real number such that

$$\begin{aligned} f_q(n)+\frac{n}{n+1}<1 \end{aligned}$$

(2)

and

$$\begin{aligned} \frac{q^{1+2f_q(n)}}{1.5}<q - \frac{1}{2}\, q^{\frac{n}{n+1}+f_q(n)} \end{aligned}$$

(3)

Let $\mathcal {L}$ be the lattice generated by the vectors

$$\mathbf{b}_0 = (-1,A_1,\ldots ,A_n), \mathbf{b}_1 = (0,q,0,\ldots ,0),\ldots ,\mathbf{b}_n = (0,\ldots ,0,q).$$

Then, for all non-zero $\mathbf{v}\in \mathcal {L}$, we have:

$$\Vert \mathbf{v}\Vert >\frac{1}{2}\, q^{\frac{n}{n+1}+f_q(n)}.$$

Proof

Suppose that there is a vector $\mathbf{v}\in L\setminus \{\mathbf{0}\}$ such that

$$\begin{aligned} \Vert \mathbf{v}\Vert \le \frac{1}{2}\, q^{\frac{n}{n+1}+f_q(n)}. \end{aligned}$$

(4)

Then, the inequality (2) yields:

$$\begin{aligned} \Vert \mathbf{v}\Vert< \frac{q}{2} < q. \end{aligned}$$

(5)

Since $\mathbf{v}\in L$, there are integers $x_0,x_1,\ldots ,x_n$ such that

$$\mathbf{v} = x_0\mathbf{b}_0+\cdots +x_{n}{} \mathbf{b}_n = (-x_0,x_0A_1+x_1q,\dots ,x_0A_n+x_nq).$$

Thus, we deduce:

$$ |x_0|,|x_0A_j+x_jq|\le \frac{1}{2}q^{\frac{n}{n+1}+f_q(n)}. $$

If $x_0=0$, then we get the vector $\mathbf{v}=(0,x_1q,\ldots ,x_nq)$ with length $>q.$ On the other hand, (5) implies $\Vert \mathbf{v}\Vert < q$. Thus, we have a contradiction, and so we deduce that $x_0\not =0$.

Since $1\le |x_0| \le \frac{1}{2}q^{n/(n+1)+f_q(n)}$, we distinguish the following two cases:

• (i) There is $k\in \{1,2,\ldots ,n-1\}$ such that

  $$ q^{\frac{k-1}{n+1}}< |x_0|< q^{\frac{k}{n+1}}.$$

By (1), we obtain:

$$ \frac{1}{2}\, q^{\frac{n+1-k}{n+1}+f_q(n)}\le A_{n+1-k} \le \frac{1}{1.5}\, q^{\frac{n+1-k}{n+1}+f_q(n)}. $$

Multiplying the two previous inequalities, we get:

$$\frac{1}{2}\, q^{\frac{n}{n+1}+f_q(n)}<|x_0|A_{n+1-k}< \frac{1}{1.5}\, q^{1+f_q(n)}.$$

By (3), we have:

$$\frac{q^{1+f_q(n)}}{1.5}<\frac{q^{1+2f_q(n)}}{1.5}< q-\frac{1}{2}q^{\frac{n}{n+1}+f_q(n)}.$$

It follows:

$$\begin{aligned} \frac{1}{2}\, q^{\frac{n}{n+1}+f_q(n)}<|x_0|A_{n+1-k}< q-\frac{1}{2}\, q^{\frac{n}{n+1}+f_q(n)} \end{aligned}$$

(6)

If $x_0A_{n+1-k} + qx_{n+1-k}=0$, then $|x_0| A_{n+1-k} = q|x_{n+1-k}|>q$, which contradicts the above inequality. Thus, we have $x_0A_{n+1-k} + qx_{n+1-k} \ne 0$.

Since $\Vert \mathbf{v}\Vert \ge |x_0A_{n+1-k} + qx_{n+1-k}|$, we get:

$$\begin{aligned} \Vert \mathbf{v}\Vert \ge \left| |x_0|A_{n+1-k} - q|x_{n+1-k}|\right| \ge q|x_{n+1-k}| - |x_0|A_{n+1-k}. \end{aligned}$$

(7)

Assume that $x_{n+1-k}\not =0$. It follows: $\Vert \mathbf{v}\Vert \ge q-|x_0|A_{n+1-k}.$ Then, using the right part of inequality (6), we get:

$$\Vert \mathbf{v}\Vert > \frac{1}{2}\, q^{\frac{n}{n+1}+f_q(n)},$$

which contradicts (4). Hence, we have $x_{n+1-k}=0$. By (7), we have: $\Vert \mathbf{v}\Vert \ge |x_0|A_{n+1-k}.$ Using the left part of inequality (6) we obtain:

$$\Vert \mathbf{v}\Vert >\frac{1}{2}\, q^{\frac{n}{n+1}+f_q(n)},$$

which is a contradiction.

• (ii) We have:

  $$ q^{\frac{n-1}{n+1}}< |x_0|< q^{\frac{n}{n+1}+f_q(n)}.$$

Further, (1) gives:

$$\frac{1}{2}\, q^{\frac{1}{n+1}+f_q(n)}\le A_1 \le \frac{1}{1.5}\, q^{\frac{1}{n+1}+f_q(n)}.$$

Multiplying the two inequalities we obtain:

$$\frac{1}{2}\, q^{\frac{n}{n+1}+f_q(n)}< |x_0|A_1 < \frac{1}{1.5}\, q^{1+2f_q(n)}.$$

By (3), we have:

$$\frac{1}{1.5}\, q^{1+2f_q(n)}< q-\frac{1}{2}\, q^{\frac{n}{n+1}+f_q(n)}.$$

Combining the two above inequalities, we deduce:

$$\frac{1}{2}\, q^{\frac{n}{n+1}+f_q(n)}<|x_0| A_1 < q-\frac{1}{2}\,q^{\frac{n}{n+1}+f_q(n)},$$

which is relation (6) with $k=n$. Proceeding, as previously, we obtain a contradiction. Thus, the result follows.

Remark 1

Proposition 1 is an improvement of [19, Lemma 1], since the obtained lower bound is better than the lower bound $\Vert \mathbf{v}\Vert >\frac{q^{n/(n+1)}}{8},$ obtained in [19, Lemma 1]. Furthermore, the number of signed messages in [19, Lemma 1], for q 160-bits, are less than $\ln {\ln {q}}\approx 4.$ In the previous proposition the number of messages can be much larger. Note that a largest lower bound will allow us, as we shall see, to attack larger DSA keys (for fixed n and q).

Using the terminology of Proposition 1, we prove the following.

Proposition 2

Let q and $A_i,B_i$ $(i=1,\ldots ,n)$ be positive integers with $A_i$ as in Proposition 1. Then, the system of congruences

$$y_i+A_ix+B_i \equiv 0 \, (\bmod \, q) \ \ \ (i=1,\ldots ,n)$$

has at most one solution $\mathbf{v}=(x,y_1,\ldots ,y_n)$ such that

$$\Vert \mathbf{v}\Vert <\frac{1}{4}\, q^{\frac{n}{n+1}+f_q(n)}.$$

If such $\mathbf{v}$ exists, then $\mathbf{v}=\mathbf{w}-\mathbf{b}$, where $\mathbf{b} = (0,B_1,\ldots ,B_n)$, and $\mathbf{w}$ is a vector obtained by using a CVP oracle for the lattice $\mathcal {L}$ of Proposition 1 and $\mathbf{b}$.

Proof

Let $\mathbf{v}=(x,y_1,\ldots ,y_n)$ be a solution of the system with

$$\Vert \mathbf{v}\Vert <\frac{1}{4}\, q^{\frac{n}{n+1}+f_q(n)}.$$

We denote by $\mathcal {L}$ the lattice spanned by the rows of the $(n+1)\times (n+1)$ matrix

$$\begin{aligned} \begin{bmatrix} -1&A_{1}&A_{2}&\dots&A_{n} \\ 0&q&0&\dots&0 \\ 0&0&q&\dots&0 \\ \vdots&\vdots&\vdots&\ddots&\vdots \\ 0&0&0&\dots&q \end{bmatrix} \end{aligned}$$

(8)

and set $\mathbf{b}=(0,B_1,\ldots ,B_n)$. Since $y_i+A_ix+B_i \equiv 0 \, (\bmod \, q)$ there is $z_i \in {\mathbb {Z}}$, such that $y_i+B_i=-A_ix+z_iq$. Set $\mathbf{u}=\mathbf{v}+\mathbf{b}=(x,y_1+B_1,\dots ,y_n+B_n).$ Then $\mathbf{u}=(x,-A_1x+z_1q,\ldots ,-A_nx+z_nq)$ belongs to $\mathcal {L}$ and we have

$$\Vert \mathbf{u}-\mathbf{b}\Vert =\Vert \mathbf{v}\Vert <\frac{1}{4}\, q^{\frac{n}{n+1}+f_q(n)}.$$

On the other hand, using the CVP-oracle, we compute $\mathbf{w}\in \mathcal {L}$ such that

$$\Vert \mathbf{w}-\mathbf{b}\Vert \le \Vert \mathbf{u}-\mathbf{b}\Vert < \frac{1}{4}\, q^{\frac{n}{n+1}+f_q(n)}.$$

Thus, we get: $\Vert \mathbf{w}-\mathbf{u}\Vert \le \Vert \mathbf{w}-\mathbf{b}\Vert +\Vert \mathbf{b}-\mathbf{u}\Vert <\frac{1}{2}\, q^{\frac{n}{n+1}+f_q(n)}.$ Since $\mathbf{w}-\mathbf{u} \in \mathcal {L}$, Proposition 1 implies $\mathbf{w}=\mathbf{u}.$ So, the CVP oracle outputs the vector $\mathbf{u}$ and so we can compute $\mathbf{v}=\mathbf{u}-\mathbf{b}.$

To get an idea how to choose the sequence $f_q(n)$ we use the following well known result.

Lemma 1

(Hermite). For every full rank lattice $\mathcal {L} \subset {\mathbb {R}}^n$ we have:

$$\lambda _1(\mathcal {L})\le \sqrt{n}\, (\det {\mathcal {L}})^{1/n}.$$

In our case we get $\lambda _1(L) \le \sqrt{n+1}\, q^{\frac{n}{n+1}}.$ The lower bound of Proposition 1 is of the form $\frac{1}{2}q^{x}.$ So, we get:

$$\frac{1}{2}q^{x} \le \lambda _1(L) \le \sqrt{n+1}\, q^{\frac{n}{n+1}}.$$

Solving with respect to x, we obtain:

$$x \le \frac{\ln {2}+\frac{1}{2}\ln {(n+1)}}{\ln {q}}+\frac{n}{n+1} = \frac{\ln {(4(n+1))}}{2\ln {q}}+\frac{n}{n+1}.$$

Thus, we get an upper bound for x. For instance we may select

$$f_q(n)=\frac{\ln {2}+\ln {(n+1)}}{2n\ln {q}}.$$

In general, we can choose

$$\begin{aligned} f_q(n)=g_{q,b,c,d}(n)=\frac{c\ln {(n+1)}}{bn^{d}\ln {q}}, \end{aligned}$$

(9)

where b, c, d are chosen such that $0<g_{q,b,c,d}(n)< \frac{\ln {(4(n+1))}}{2\ln {q}}.$

4 The Attack

In this section we describe our attack. Let $m_i$ $(i=1,\ldots ,n)$ be messages signed with (EC)DSA system and $(r_i,s_i)$ their signatures. Then, there are $k_i \in \{1,\ldots ,q-1\}$ such that $r_i = (g^{k_i}\,\bmod \, p) \, \bmod \, q$ (resp. $r_i = x_i \,\bmod \,q$ and $k_i P = (x_i,y_i)$) and $s_i = k_i^{-1}(h(m_i)+ar_i) \ \mathrm{mod} \ q$. It follows that

$$k_i+C_ia +D_i \equiv 0\ (\bmod \ q) \ \ \ (i=1,\ldots ,n),$$

where $C_i = -r_i s_i^{-1} \,\bmod \, q$ and $D_i = -s_i^{-1} h(m_i) \,\bmod \, q$. Multiplying both sides by $C_i^{-1}\, \bmod \, q$, we get: $C_i^{-1}k_i+a+C_i^{-1}D_i \equiv 0 \, (\bmod \, q).$

Now, we pick integers $A_i$ satisfying

$$\frac{q^{\frac{i}{n+1}+f_q(n)}}{2}< A_i <\frac{q^{\frac{i}{n+1}+f_q(n)}}{1.5} $$

and we multiply by $A_i$ both sides of the above congruence. So, we get:

$$A_iC_i^{-1}k_i+A_ia+A_iC_i^{-1}D_{i}\equiv 0\, (\bmod \, q).$$

Set $B_i=A_iC_i^{-1}D_i\, \bmod \, q$ $(i=1,\ldots ,n)$. Then, the vector

$$\mathbf{s}=(a, A_1C_1^{-1}k_1\, \bmod q,\ldots ,A_nC_n^{-1}k_n\, \bmod \, q)$$

satisfies the system

$$\begin{aligned} y_i+A_ix+B_i\equiv 0\, (\bmod \, q)\ \ \ (i=1,\ldots ,n). \end{aligned}$$

(10)

We set $\mathbf{b}=(0,B_1,\ldots ,B_n)$ and $M_{n,q}=\frac{1}{4}\, q^{\frac{n}{n+1}+f_q(n)},$ for some sequence $f_q(n)$ satisfying the hypotheses of Proposition 1. The vectors

$$\mathbf{b}_0 = (-1,A_1,\ldots ,A_n), \ \ \mathbf{b}_1 = (0,q,0,\ldots ,0),\ldots ,\mathbf{b}_n = (0,\ldots ,0,q),$$

form a basis of ${\mathbb {R}}^{n+1}$. We denote by $\mathcal {L}$ the lattice spanned by $\mathbf{b}_0,\mathbf{b}_1,\ldots ,\mathbf{b}_n$. If $\Vert \mathbf{s}\Vert < M_{n,q}$, then Proposition 2 implies that $\mathbf{s}=\mathbf{w}-\mathbf{b}$, where $\mathbf{w}$ is a vector obtained by using a CVP oracle for $\mathcal {L}$ and $\mathbf{b}$. Thus, we can compute the secret key a which is the first coordinate of $\mathbf{s}.$

An Improvement of the Attack. The previous attack, which is deterministic, needs quite short solution vector (and so small secret key) in order to succeed. Now, we remark that if $\mathbf{u} \in \mathcal {L}$, then $\mathbf{u}-\mathbf{b}$ is a solution of the system (10). Indeed, since $\mathbf{u}\in \mathcal {L}$, there are integers $l_0,\ldots ,l_n$ such that $\mathbf{u}=l_0\mathbf{b_0}+\cdots +l_n\mathbf{b_n}$, and so we get:

$$\mathbf{u}-\mathbf{b}=(-l_0,l_0A_1+l_1q-B_1,\ldots ,l_0A_n+l_nq-B_n)= (x,y_1,\ldots ,y_n).$$

Thus, we obtain that $y_i+A_ix+B_i=l_iq \equiv 0 \pmod {q}.$ So, the vectors of the form $\mathbf{x}-\mathbf{b},$ where $\mathbf{x}$ is in the set

$${\mathcal {A}}_{\gamma _n}(\mathbf{b})=\{ \mathbf{u}\in L: ||\mathbf{u}-\mathbf{b}||<\gamma _nM_{n,q}\},$$

are solutions of the system (10), for some positive number $\gamma _n.$

The parameters we usually use in a (EC)DSA system, provides a solution $\mathbf{s}=(x,y_1,\ldots ,y_n)$, where all the entries are 160-bits integers and smaller than q. In this case, we compute experimentally that the value of $\gamma _n = \frac{\Vert \mathbf{s}\Vert }{M_{n,q}}$ is on average approximately equal to 38. For larger values of $\gamma _n,$ Babai’s algorithm (or some other approximation algorithm) may succeed in finding in polynomial time such a vector. Indeed, we checked (see Sect. 5) that Babai’s algorithm managed to find a solution for $\gamma _n\in [44,52].$ We get such values of $\gamma _n$ in the case where we have smaller keys. We provide the details of these experiments in Sect. 5.

This attack is non deterministic, since $\gamma _n>1$ and so Proposition 2 does not hold. If $\gamma _n=1$, then Proposition 2 holds, and the attack is deterministic. Below we present our attack.

The attacker, say Eve, has to make the choice of n and $f_q.$ The choice of n is not random. A minimal condition is to choose it, in such a way that the interval $I_i$ contains at least one integer. Then, she can construct a system of the form $y_i+A_ix+B_i \equiv 0\pmod {q},$ $1\le i \le n,$ and $A_i\in I_i.$ So, in practice the difficult part for Eve, is to find n signed messages. So Eve must be an active attacker and uses the DSA system as a signing oracle.

Remark 2

• (i) Proposition 2 may not be satisfied, but the attack may return the secret key. This is because the hypotheses of Proposition 2 are only necessary and not sufficient.

• (ii) The attack may fail in the sense that will not compute the secret key. The probability of success depends on the choices of $A_i.$

• (iii) In the 7th step we can use BKZ algorithm with a suitable blocksize instead of LLL. This is something common in case we want a more reduced basis.

5 Experimental Results

For the following experiments we used the computer algebra system Sagemath [20]¹. We generated 100 DSA-systems of the form (10), $y_i+A_ix+B_i\equiv 0 \pmod {q},$ $1\le i\le n,$ having a solution $\mathbf{s} = (x,y_1,\ldots ,y_n)$ where x is the secret key. Once q is fixed to a 160 bit prime, we choose a natural number $n=n_0$ such that the intervals $I_i$ contain at least one integer and a sequence $f_q(n),$ such that the value $f_q(n_0)$ satisfies the inequalities (2) and (3) of Proposition 1. Then, we choose the secret key x and $y_i$ (we call $y_i$’s derivative ephemeral keys), such that Proposition 2 is satisfied. In fact we pick the solution vector $\mathbf{s}$ such that

$$\frac{q^{n/(n+1)}}{16}<\Vert \mathbf{s}\Vert <\frac{q^{n/(n+1)+f_q(n)}}{4}.$$

The attack in [19], it may fail for the previous experiments, since the norm of solution we are looking for, is larger than $\frac{q^{n/(n+1)}}{16}$ and $n\gg \ln (\ln (q)).$ But our attack will succeed since Proposition 2 is satisfied. The attack is deterministic. A choice that satisfies the previous is q :  a 160-bit prime, $n_0=14,$ $f_q(n) = \frac{\ln {(n+1)}}{n\ln {q}}.$ We generated 100 DSA systems with the previous parameters and secret key 147 bits and derivative ephemeral keys 145 bits. As a CVP oracle, we used Babai algorithm. In all the instances we found the secret key, as our attack suggests. We tested our improvement (Babai’s attack), which is no longer deterministic. We summarize the results in Table 1.

Table 1. We set $n=206$ and $f_q(n) = \frac{170\ln {(n+1)}}{n\ln {q}}.$ We generated 100 random DSA systems for each row. The pair $(\alpha ,\beta )$ at the first column, means that we pick the secret key uniformly from $[2^{\alpha -1},2^{\alpha }-1]$ and the derivative ephemeral keys from $[2^{\beta -1},2^{\beta }-1]$ (and fixed 160 bit prime q). For preprocessing we used BKZ with blocksize 70. The second column is the average value of $\gamma _n.$ The last column contains the percentage that Babai’s attack succeeds in finding the solution i.e. the secret key.

Remark 3

In the Example studied in [19] some typographic errors occurred in the values of the quantities $A_1$, $h(m_2)$, $h(m_3)$, $s_2$ and $s_3$. The correct values are $A_1 = 32 D_1$ (and so, we have $l_1 = a^{-1} k_1 32\ \bmod \, q < 2^{96})$, and

$$\begin{aligned} h(m_2)= & {} 432847687632257989627045945667165545993050789339,\\ h(m_3)= & {} 102247883422181353858596598828981363231626289233,\\ s_2= & {} 1286644068312084224467989193436769265471767284571,\\ s_3= & {} 1357235540051781293143720232752751840677247754090. \end{aligned}$$

A Further Heuristic Improvement. We can further improve the previous results. The idea is to use another target vector instead of $\mathbf{b}=(0,B_1,\ldots ,B_n).$ We consider the following vector

$$\mathbf{b}=(\varepsilon ,\varepsilon + B_1,\ldots ,\varepsilon + B_n),$$

where $\varepsilon = 2^{159}-2^{157}.$ That is the new target vector is equal with the previous plus the vector $(\varepsilon ,\ldots ,\varepsilon ).$ The reason for picking such a target vector, is because the entries of the solution vector are balanced, i.e. of the same bit lengths. We test the previous idea, by choosing the solution vectors

$$\mathbf{s}\in \{2^{159},\ldots ,2^{160}-1\}\times \{2^{158},\ldots ,2^{159}-1\}^{n}.$$

That is the secret key has $160-$bits and the derivative ephemeral keys $159-$bits. We considered 100 DSA such systems with $n=206$ and $f_q(n)$ as in Table 1, preprocessing BKZ-85, and our algorithm found the secret keys in 62 instances. The time execution per example was on average 2 min in an I3 Intel CPU. So, having one least (or most) significant bit for 206 derivative ephemeral keys, we can find the secret key. This result improves, in some sense, the result [12, Sect. 4.4], where with 100 signatures and knowing 2 least significant bits of the ephemeral keys, they computed the secret key with success rate $23\%$ and in 4185 s on average per instance.

6 Conclusion

Following the ideas of [19], we have presented new attacks on DSA schemes. First, we have improved the bound for the lengths of the secret and ephemeral keys and we replaced the use of Micciancio-Voulgaris algorithm [14], by the polynomial complexity Babai’s algorithm. This allowed us to find larger keys than in [19]. Our attack remained deterministic. Furthermore, we presented an heuristic extension of our attack for finding even larger secret keys. Finally, we improved the state of the art attack in (EC)DSA presented in [12]. Several experiments were described.