Defcon Quals 2019: ASRybaB

Introduction

For Defcon Quals 2019, I wrote a challenge called ASRybaB.

You can find the challenge, its solution, and other scripts here.

• challenge.py contains what given during the competition. Some of the code is obfuscated.
• secret.py contains the secret used to compute the HMAC, and it was, obviously, not released.
• compile.py was used to generate challenge.py starting from originalchallenge.py.
• originalchallenge.py contains the non-obfuscated challenge code.
• solve_d.sage contains my solution, which uses sage.

The challenge sends you 3 RSA “challenges” in the form of n, e, v. The goal is to provide a “signed” value of v, which requires finding the secret exponent d, corresponding to the provided public key (n, e).

To get the flag, it is necessary to provide the 3 signed messages in about 15 minutes. To ensure this time constraint, I used an HMAC, “authenticating” the sent n, e, v values and the timestamp of when they were generated. I chose this solution to avoid requiring a long-term connection or saving some state on the challenge’s server.

Obfuscation

The public key (n, e) is computed so that the corresponding private exponent has special properties. This function computing the key (create_key) is obfuscated (see the compile.py file) by:

• serializing it using Python marshal,
• modifying its bytecode to make decompilers fail.

Specifically, I inserted a STOP_CODE bytecode instruction in some dead code. It was still possible to reverse engineer the create_key function by using the dis module, however that required reading Python bytecode instead of Python code. Another possibility was to add a .pyc header to the marshaled code, manually remove the STOP_CODE bytecode, and then use a Python decompiler (e.g., uncompyle6).

Properties of the private exponent

The non-obfuscated code of the create_key function is the following:

def create_key():
    if False: #used by obfuscation
        x = 7/0
        x = 7/0

    Nsize = NSIZE
    pqsize = Nsize/2
    N = 0 
    while(N.bit_length()!=Nsize):
        while True:
            p = number.getStrongPrime(pqsize)
            q = number.getStrongPrime(pqsize)
            if abs(p-q).bit_length() > (Nsize*0.496):
                break
        N = p*q
    phi = (p-1)*(q-1)

    limit1 = 0.261
    limit2 = 0.293
    while True:
        d = number.getRandomRange(pow(2,int(Nsize*limit1)),pow(2,int(Nsize*limit1)+1))
        while d.bit_length()<Nsize*limit2:
            ppp = 0
            while not number.isPrime(ppp):
                ppp = number.getRandomRange(pow(2,45),pow(2,45)+pow(2,12))
            d *= ppp
        if number.GCD(d, phi)!=1:
            continue
        e = number.inverse(d, phi)
        if number.GCD(e, phi)!=1:
            continue
        break

    zzz = 3

    return (N, e)

The key is generated so that the private exponent d is slightly larger of the 0.292 limit, so that the Boneh-Durfee attack cannot be applied directly.

However, given how the key is computed:

• it is guaranteed to contain a prime ppp (within a set of 125 values),
• d/ppp < N^0.292

My solution

My solution reuses the Boneh-Durfee attack implemented by David Wong and available on GitHub, with 2 major modifications.

Exploiting the known prime

Let’s assume for now that we know the value ppp of the prime composing d. We can then rewrite the equations at page 14 of the paper mentioned above in the following way:

e*d = 1 (mod phi(N))
e*d = k * phi(N) + 1
(e*ppp)*(d/ppp) = k * phi(N) + 1
k*phi(N) + 1 = 0 (mod e*ppp)

Consequently, if we know ppp we can just apply the “standard” Boneh-Durfee attack using ppp * e as the modulo of our equation, instead of e. In my code this is implemented by the line:

modulus *= ppp

Bruteforcing the known prime

As mentioned above ppp can only have 125 values. Since we need to solve 3 challenges, at most, we need to run the Boneh-Durfee 125*3 = 375 times. My code uses a Python multiprocessing Queue to parallelize this process. On a modern 64 cores machine, this takes, at most, about 15 minutes.

Some considerations

Bruteforcing

I wanted to write a challenge requiring writing parallel code. At the same time, I wanted to avoid a solution that could only be implemented by spending a lot of money or using special hardware. For this reason, while implementing the challenge I intentionally tuned things so that it was solvable using less than $1 of cloud computing. On Amazon EC2 a 64 vCPU machine (m4.16xlarge) costs $3.20 per hour, which is only about $0.80 for the required 15 minutes of computation.

The 0.292 limit

I did quite a lot of testing and, at least with the code I used, it was basically impossible to find a solution for d above N ^ 0.28. For this reason, I think that the 0.292 is more a theoretical limit than a real one.

p and q

This paper explains that if p-q is “small” a variation of the Boneh-Durfee could be possible even if d > N ^ 0.292. To avoid this issue, my code rejects p and q values if their difference is not large enough. However, this check increased the computation time needed to generate the keys and made me concerned about the service using too much CPU, slowing down our infrastructure. For this reason, to access this challenge, it was first needed to generate a Proof-of-Work.