Using Pollard's lambda in a key-recovery attack on DH

Question

I've become interested in writing an exploit for the OpenSSL vulnerability here (CVE-2016-0701). Running through the bullets describing the attack, I can follow up to the last bullet point.

Reviewing the referenced paper, Key Recovery Attack on DH Small subgroups, I find myself in a similar position.

The Chinese Remainder Theorem, according to Wikipedia, will return me an 'x'. If I have read the reference paper correctly, this will either be the whole of the secret 'x' if x is short enough, or it will be 'bits of x'.

Both the blog and paper seem to hand wave through "and then you can use Pollard's Lambda to recover the rest". The Wikipedia for Pollards Lambda describes it as finding the x in g^x = y, with a given g and y.

I've eventually researched this down to a further paper, as per page 338 of "On Diffie Hellman Key Agreement with Short Exponents", image below:

I can somewhat see the 'g' value required based on this, but it simply tells a user to "calculate y*", a calculation which itself appears to require several unknown values.

This could well be an issue of how I'm reading things, as I'm much better notation seen in code than in maths.

If someone could assist with what values are meant to come out of CRT and be be fed into the Pollard's Lambda function (of which there are several implementations floating around), it would be appreciated.

Answer 1

it simply tells a user to "calculate $y^*$", a calculation which itself appears to require several unknown values

Nope, it has $y^* = y / g^V$, where at this point, you know $y$, $g$ and $V$.

The original discrete log problem was given as $y = g^x$, and so you were given $y$ and $g$

In addition, $V = x \bmod z$, where $z$ is a smooth factor of $n$ (the group order, which the algorithm assumes you know). You can find the value of $V$ by taking the group order $n$, doing a partial factorization to obtain $z$ (even if it is infeasible to complete factor $n$, it's easy to find the small factors of $n$), and then by solving the Discrete Log problem $y' = g'^V$, where $g' = g^{n/z}$ and $y' = y^{n/z}$. This particular Discrete Log problem can easily be solved by the Pohlig-Hellman algorithm, as $g'$ is in a subgroup of order $z$, which is smooth.