**tl;dr**

- Timing-based attack on the double-and-add algorithm to recover secret value
`d`

- Predict pseudo-random value using the NSA backdoor on Dual_EC_DRBG

**Challenge Points**: 964**No. of solves**: 9**Solved by**: LS

## Challenge Description

Can you help me test out this PRNG I implemented? I’m inserting a backdoor, but I’m sure you can’t find it. Oh btw, I did some optimizing, so version 2 is faster. You can still try out version 1 though. They’re the same anyway.

## Overview

Source isn’t provided for this challenge, and the only thing given to us is an nc connection.

The description tells us that the service is a PRNG implementation, that has a backdoor inserted into it.

It also tells us that there are two versions, that are essentially the same except for their speeds.

1 | Choose your version [1/2] |

After we choose either version, it starts “computing parameters”. It gives us a percentage of the progress.

With multiple trials, it’s also noted that the first version takes significantly longer than the second version, as implied by the challenge description.

After the parameter computation, we’re given a curve and two points on the curve.

We’re also given a menu following the two parameters, that looks like this:

1 | Curve: secp192r1 |

Seemingly, our goal is to predict the next random number.

If we get a random number from the service, we get a number that’s `240`

bits long.

## Approach

We have limited information about this service, but we know that it’s a PRNG, and that it uses a curve and two points on the curve in some way.

With some googling, we come across the PRNG called Dual_EC_DRBG, which is a PRNG that was standardized by NIST, and was later found to have a backdoor inserted into it by the NSA.

### How the PRNG works

The PRNG has an internal state `s`

that’s updated every time a new pseudo-random value is requested.

There are two internal parameters `P`

and `Q`

which are elliptic curve points.

The value that’s returned by the PRNG is the x-coordinate of `r`

. The computation is as follows:

Here’s the implementation that was used in the challenge:

1 | class PRNG: |

### The backdoor

The backdoor in Dual_EC_DRBG is present when the `Q`

parameter is directly related to the parameter `P`

. In a safe implementation of the PRNG, `Q`

is supposed to be a random point on the curve. However, in the backdoored implementation, `Q`

is related to `P`

in a way that allows the attacker to predict the next value.

The relation is as follows:

Where `d`

is the secret value that’s known to entity that inserted the backdoor.

Knowing this value allows for calculating the internal state of the PRNG, given any two consecutive output values.

## Solution

Since we’re told that the backdoor is inserted, we can assume that the `Q`

parameter is going to be a scalar multiple of `P`

. However, discrete log would be infeasible here. It should be noted that the “Computing parameters…” stage of the service implies the insertion of the backdoor, that is, the calculation of `P * d`

.

One of the most common methods of elliptic curve point multiplication is the Double and Add algorithm, and it’s been intentionally made vulnerable to a timing attack in this challenge.

The percentages can be timed to determine the bits of the secret `d`

.

After recovering the bits and verifying that they’re correct by multiplying `P`

with the recovered `d`

, we can predict the next value of the PRNG using the backdoor.

## Exploit

1 | from pwn import remote |

## Conclusion

I thought it was an interesting idea to make a challenge out of, but the execution may have not been the best. I hope you enjoyed the challenge regardless.