Lattices vs Cranks

A while ago, I was bored and wrote a Twitter post on how to find an integer if you only know the fractional part of its square root. My Twitter is private these days, and lies unused, but I still get questions about this topic from time to time, so I decided to put it into a blog post on here.

Why would one care about reconstructing an integer from the fractional part of its square root you might ask? It turns out there is some crank out there who claims that this can serve as the basis for his brilliant crypto system, so showing that this reconstruction is possible is the same as a key recovery attack.

Computing Square Roots

As usual with crank cryptography, the official documents are very light on actual description of the algorithm, so we will have to nail down the definitions first before we can actually attack the cryptosystem.

From what can be inferred from the documents, we first select a secret $n$ -bit integer $a$ that is not a perfect square (if $a$ is a perfect square the attack won’t work, but the algorithm will only produce zeroes, so it is trivially distinguishable). We then produce a “random” bitstream by looking at the digits of $\sqrt{a} - \lfloor\sqrt{a}\rfloor$ , i.e. the primitive we are studying is a DRBG.

Before we look at the security of this algorithm, lets first take a quick glance at how it otherwise works for a DRBG. The best algorithm to compute a square root is using Newton’s method to first compute the inverse square root, and then recover the square root via multiplication with the number itself. In other words, apply Newton’s method to the function $f(x) = \frac{1}{x^2} - a$ . This function clearly has a zero at $\frac{1}{\sqrt{a}}$ , which Newton’s method should find with quadratic convergence, assuming we started somewhere halfway decent.

For Newton’s method we need to first compute the derivative of our function, which is just $f'(x) = -2\frac{1}{x^3}$ .

Newton’s iteration then gives us:

$x_{i+1} = x_i - \frac{f(x_i)}{f'(x_i)}=x_i-\frac{\frac{1}{x^2} - a}{-2\frac{1}{x_i^3}}=\frac{1}{2}x_i(3-ax_i^2)$

Now we can see why we prefer to compute the inverse square root with the iteration: The formula happens to only ever divide by 2, so it is far cheaper then having to divide by $x_i$ , which we would otherwise have to do if things didn’t cancel out this neatly.

Quadratic convergence means we roughly double the number of correct digits each iteration step, but looking at our iteration step, we need to multiply several $n$ -bit precision numbers, so the total time complexity of this algorithm should be $\mathcal{O}(n^\frac{3}{2}\log n)$ with $\mathcal{O}(n)$ bits of space complexity.

This is abysmal. A DRBG should have linear time complexity and constant space complexity, i.e. the cost of producing an extra bit of randomness should not depend on how much randomness was previously created. It seems like even our crank caught wind of that, because he used this generator just to seed a Blum-Blum-Shub generator, which, while one of the slowest DRBGs we have, has linear time complexity and constant space complexity. You can also add a backdoor to it, which I guess is a property you can have in a DRBG, if you like it.

Lattices enter Stage left

With the ranting about how badly this DRBG performs aside, to the main piece of this article, how to break it. We will use a well-known technique to tackle Diophantine equations with some lattice math for this.

For this, let’s get some $m$ -bit stream of $\alpha = \sqrt{a}-\lfloor\sqrt{a}\rfloor\in[0, 1]$ of our $n$ -bit integer $a$ . In other words $a = (k+\alpha)^2=k^2+2k\alpha+\alpha^2$ , for some unknown integer $k$ . Let’s set $l = a - k^2$ . With that we have $2k\alpha - l = \alpha^2$ , with both $k$ and $l$ being unknown integers. This isn’t looking very promising, one equation with two unknown variables, but then you realize that $\alpha$ is known to a precision high enough to contain more than enough information about both of these integers, if we can just tickle it out of it. It’s a linear equation (and in fact one of the goals of the substitution was to make it linear), and if you paid attention in one of my previous posts, a linear equation when the coefficients are integers is what lattices live for. We still need to manipulate it a bit further before we get to the actual lattice, though. First, we need a large number, let’s call take some $p=2^{n+4}$ . The main thing that matters here is not so much the value of $p$ itself, just that it is large enough for what comes next. And what comes next is a lattice, generated by the vectors

$\begin{pmatrix}2p\alpha\\1\\0\end{pmatrix},\begin{pmatrix}-p\\0\\1\end{pmatrix}$

In other words, the elements of our lattice are the vectors of $\mathbb{R}^3$ of the form $\begin{pmatrix}p\cdot(2\alpha x-y)\\x\\y\end{pmatrix}$ , with $x, y$ integers. In particular, the vector $\begin{pmatrix}p\alpha^2\\k\\l\end{pmatrix}$ is a vector in our lattice, according to our previous calculations. Since $p$ is so large, this vector is fairly close to $\begin{pmatrix}p\alpha^2\\0\\0\end{pmatrix}$ , given that both $k$ and $l$ are roughly $\sqrt a$ , i.e. only $\frac{n}2$ bit integers. If we vary $x$ or $y$ though, we either have to make them very large, or we will never get as close in the first coordinate, as we carefully balanced things so that our linear equation works out.

In other words, if we find the lattice vector closest to $\begin{pmatrix}\alpha^2\\0\\0\end{pmatrix}$ , we have found our integers $k, l$ and with them $a$ .

But wait, I hear you say, isn’t that the Closest Vector Problem (CVP), known for being hard to compute. Well indeed it is. And it is hard to compute. For higher dimensional lattices. For a rank 2 lattice embedded in three dimensions, it’s not. You simply reduce the lattice basis above, express $\begin{pmatrix}\alpha^2\\0\\0\end{pmatrix}$ in this basis, round the coefficients to integers, and, as by magic, the coefficients will be the unknown integers. I’ve implemented this algorithm here, and here is a sample output:

Lattice reduction for two dimensional lattices is incredibly fast, resulting in an algorithm that is nearly as fast to break as it is to compute in the first place. The author of the algorithm suggested a hardening technique of varying the offset used, i.e. discarding some of the keystream. This of course doesn’t do anything, as the attack is fast enough, and the computation of the keystream is slow enough, that you can simply bruteforce all possible starting points, changing $a$ by a power of 2 as necessary to account for the discarded bits.

While this algorithm is obviously bogus for cryptographic purposes, the general technique for solving Diophantine equations with lattices is a useful tool to understand and study, similar techniques are for example used in Coppersmith’s attack on RSA with small exponents and are valuable to understand for anyone with an interest in discrete mathematics.

Computing Square Roots

Lattices enter Stage left

Share this:

Leave a ReplyCancel reply

Discover more from Key Material