ECLCG

ECLCG

• Category: Crypto
• Score: 421/500
• Solves: 3

Description

LCG is fun, ECDSA is fun too, so why not combine them together?

Overview

It signs 16 messages with ECDSA using secp256k1, with nonces $k_i$ generated by a LCG with unknown parameters $(a,b,p)$. The target is to recover the private key from the signatures.

Solution

Warning: I do not fully understand why my solver works, so the explanation here is most likely wrong.

This writeup will roughly explain how solve2.py work, which is modified from my first working solver solve.py. But what they actually do is the same, just with different implementation.

First, take any two message and signature pairs $(z_1, r_1, s_1)$ and $(z_2, r_2, s_2)$, we can derive the following equation from ECDSA signing process:

$$ s_1^{-1} z_1 - s_2^{-1} z_2 + (s_1^{-1} r_1 - s_2^{-1} r_2) d \equiv k_1 - k_2 \pmod{q} $$

where $d$ is the private key, $k_i$ are the nonces, and $q$ is the order of the curve.

So from the given $n=16$ signatures, define these $n-1$ dimensional vectors:

$$ \begin{aligned} (v_1)i &= s_i^{-1} z_i - s{i+1}^{-1} z_{i+1} \ (v_2)i &= s_i^{-1} r_i - s{i+1}^{-1} r_{i+1} \ (\Delta k)i &= k_i - k{i+1} \end{aligned} $$

It follows that:

$$ v_1 + v_2 d \equiv \Delta k \pmod{q} $$

Then apply orthogonal lattice to $v_1, v_2$, we would recover a $n-1$ dimension basis $O$, which satisfy $O \mu = \Delta k$ over integers with a small vector $\mu$.

$O$ is the ortho2.T in the solver.

From the properties of LCG, we can see that:

$$ a \cdot ((\Delta k)1, \cdots, (\Delta k){n-1}) - ((\Delta k)2, \cdots, (\Delta k){n}) \equiv 0 \pmod{p} $$

which is

$$ a \cdot \mathop{\text{Slice}}(\Delta k, 0, n-1) - \mathop{\text{Slice}}(\Delta k, 1, n) \equiv a \cdot \mathop{\text{Slice}(O \mu, 0, n-1)} - \mathop{\text{Slice}(O \mu, 1, n)} \equiv 0 \pmod{p}

$$

where $\mathop{\text{Slice}}(\cdot)$ denotes Python's slicing operation (so zero indexed).

And it can be further simplified to:

$$ \left( a \cdot \mathop{\text{Slice}(O, 0, n-1)} - \mathop{\text{Slice}(O, 1, n)} \right) \mu \equiv 0 \pmod{p} $$

Since $\mu$ is small, we can reasonably expect there would be a short vector in $a \cdot \mathop{\text{Slice}(O, 0, n-1)} - \mathop{\text{Slice}(O, 1, n)}$ modulo $p$ orthogonal to $\mu$ in $\mathbb{Z}$.

Here we assume that $p$ is known. We can see that reducing $\mathop{\text{Slice}(O, 0, n-1)}$ and $\mathop{\text{Slice}(O, 1, n)}$ modulo $p$ simultaneously, and it would result in $2 \times (n-4)$ short vectors orthogonal to $\mu$. So computing the kernel of the matrix formed by these vectors over $\mathbb{Z}$ would give $\mu$ (up to sign), which allows us to recover $\Delta k$, and hence $d$.

While this explaination sounds reasonable (to me), I find that replacing the $p$ used in the last step with any reasonably large prime $p' \neq q$ also works, and this is why I think my explanation above is wrong.

@genni first blooded this challenge, and he said his solution is based on Stern's algorithm, which only require one LLL to solve the challenge. I have no idea how it works, but I think it is worth mentioning and I might try to understand it later.

Solution by @lance_roy from Kalmarunionen

His idea is to recover a and p using a variant of Stern's attack, then it becomes a similar problem to my old challenge Easy DSA:LCG (or "Pseudo-Random" Number Generation within Cryptographic Algorithms: the DSS Case).

Lance Roy: Stern's attack is usually done when you are given the high bits of the LCG output, but it works equally well with the low bits of the LCG output, or more generally reducing the LCG output modulo a second, smaller modulus.

Lance Roy: Because I didn't get the LCG output exactly, only that the output is $k = s^{-1} * z + s^{-1} * r * d \pmod{q}$, I made it search for short vectors orthogonal $\pmod{q}$ to both $s^{-1} * z$ and $s^{-1} * r * d$, so that I'd be sure that it was orthogonal to k. When these vectors are short enough, a bound similar to the one for Stern's attack shows that the vector has to be orthogonal to the original PRG output. Interpreting the orthogonal vector as a polynomial, this means that the polynomial is a multiple of $(x - a)$ modulo $p$, so I can take a gcd of resultants of a few of these orthogonal vectors to get $p$, and then take the gcd of the polynomials $\pmod{p}$ to get $x - a$.

Solver: solve_lance_roy.sage

Actually, the idea of adapting Stern's attack is one of the few things I tried when I tried to develop this challenge, but it doesn't work for me at that time. However, after I read and understand his solution, I understand that culpit is that the short vectors $\lambda$ would have to be orthogonal to $k$ over integers, not modulo $q$. The vectors in the ortho matrix in my solver are only orthogonal in $\mathbb{Z}_q$ but not in $\mathbb{Z}$, so trying to apply Stern's attack on them would not work.

It turns out a simple find_ortho_fp(q, v1, v2) it not sufficient, but find_ortho_fp(q, v1[:-1], v2[:-1], v1[1:], v2[1:]) could result in vectors that zeros $k$ over integers. And I combined this idea and my solver, it only require one lattice reduction to solve the challenge. See solve3.py for the implementation.

The solution from genni and ConnorM are also fairly similar at the start, so I think we can conclude that the most crucial step is to find orthogonal vectors.