I was playing justCTF 2020 with the new CTFers in Yakitori (Firebird). Oracles is a fun cryptography challenge that I solved during the game, and I thought this is worth compiling the write-up.

Challenge Summary⌗

We are given a chance to ask the agencies for oracles. The challenge author have prepared some questions for us:

  • Is Goldbach's conjecture true?
  • What is the answer to everything?

On top of them, the challenge author tried to tell the agency the flag. Well, the agencies are so indifferent and they will not be responding anyway. By the way, the questions (or the flag) are encrypted with RSA-OAEP. It is not possible to read the flag solely from the ciphertext.

Solution⌗

Note. This is likely to be an unintentional solution. The challenge author said that this should be solvable within ten minutes. Turns out it is! I was using the correct approach though, and unfortunately my algorithm isn’t efficient.

Part I: Recovering the public keys⌗

Why? When the challenge is released, the entire key file is redacted and the public key is not given.

Although the agencies seemed indifferent to our questions, they are curious and actually would decrypt the questions.

const oracle = new asmCrypto.RSA_OAEP(
    privkey,
    new asmCrypto.Sha256(),
    fs.readFileSync('./oracles_stuff/' + oracleName)
);

var response = 'I won\'t answer.';
try {
    const result = oracle.decrypt(question);
    asmCrypto.bytes_to_string(result);
} catch(err) {}

res.render('index', {response: response});

We can easily identify the LFI vulnerability as we are the ones who can manipulate oracleName, and it isn't being checked. However it does not seem useful since the hash of the content is computed and being used. Having this, we are not able to recover the content even we are able to obtain its hash.

However, would it be possible that the functions inside the try block to overwrite the response? In this case, it will actually return something other than I won't answer? Well, response isn't even used as a variable in the asmCrypto.js, not to mention if it is being misused. This is not the way.

This part did not struggle me a lot. I linked this challenge with Obvious Transfer (a challenge that I made) at an early time because there are some common factors. When I look at the source code for asmCrypto.js, I am able to found the place that I could recover $n$. Let's read the code together!

// Excerpted from https://github.com/asmcrypto/asmcrypto.js/blob/v2.3.2/src/rsa/pkcs1.ts

export class RSA_OAEP {
    
    // omitted

    decrypt(data: Uint8Array): Uint8Array {
        if (!this.rsa.key) throw new IllegalStateError('no key is associated with the instance');

        const key_size = Math.ceil(this.rsa.key[0].bitLength / 8);
        const hash_size = this.hash.HASH_SIZE;
        const data_length = data.byteLength || data.length || 0;

        if (data_length !== key_size) throw new IllegalArgumentError('bad data');

        // [!] Calls the `decrypt` method in the `RSA` class excerpted below
        this.rsa.decrypt(new BigNumber(data));

        // omitted
    }
    // omitted
}
// Excerpted from https://github.com/asmcrypto/asmcrypto.js/blob/v2.3.2/src/rsa/rsa.ts

export class RSA {
    public readonly key: key;
    public result!: Uint8Array;
    
    // omitted
    
    decrypt(msg: BigNumber): this {
        if (this.key[0].compare(msg) <= 0) throw new RangeError('data too large');

        // omitted

        return this;
    }
    // omitted
}

The decrypt method in the RSA class checks whether $m < n$! If $m \geq n$, an error is thrown and the remaining operations are not performed. It is obvious that they should be responding faster... But how can we detect it?

The response times when $m < n$.
The response times when $m \geq n$.

It seems that the latency has highly fluctuated, which makes the results unreliable. Luckily the response-time package is used, adding a X-Response-Time header to the responses showing the time the server has processed the request. When $m < n$, it is around 10 - 15ms. Otherwise it can be done within 5ms. Knowing this, we can recover $n$ with binary search! For $e$, I suppose that would be 65537 as always...

Part II: Back to square one⌗

Uh oh. Our progress is ruined.

While I am struggling on how to recover $m$ from a given ciphertext, the organizers made the above announcement... and now the public key $(n, e)$ are given. Although this may be a sad news for us, we knew that the public keys are unchanged for all sandboxes. With that said, if we have partial results in ten minutes, we can create another sandbox and continue our work over there.

Part III: Slower... and even slower...⌗

I cannot stop myself from thinking this to be vulnerable to timing attack, and keep reading the source code of asmCrypto.js. Some RSA-OAEP implementations are known vulnerable to Manger's padding oracle attack by checking if the first byte is a null byte ($m < 2^{1016}$ in our case). This package checks and raise an exception too... but how can I detect that?

// Excerpted from https://github.com/asmcrypto/asmcrypto.js/blob/v2.3.2/src/rsa/pkcs1.ts

export class RSA_OAEP {
    
    // omitted

    decrypt(data: Uint8Array): Uint8Array {
        
        // omitted

        this.rsa.decrypt(new BigNumber(data));

        const z = this.rsa.result[0];
        const seed = this.rsa.result.subarray(1, hash_size + 1);
        const data_block = this.rsa.result.subarray(hash_size + 1);

        // [!] How can I detect this?
        if (z !== 0) throw new SecurityError('decryption failed');

        const seed_mask = this.RSA_MGF1_generate(data_block, seed.length);
        for (let i = 0; i < seed.length; i++) seed[i] ^= seed_mask[i];

        const data_block_mask = this.RSA_MGF1_generate(seed, data_block.length);
        for (let i = 0; i < data_block.length; i++) data_block[i] ^= data_block_mask[i];

        const lhash = this.hash
            .reset()
            .process(this.label || new Uint8Array(0))
            .finish().result as Uint8Array;
        for (let i = 0; i < hash_size; i++) {
            if (lhash[i] !== data_block[i]) throw new SecurityError('decryption failed');
        }

        // omitted
    }
    // omitted
}

In particular, the operations do not seemed expensive between two security errors. The server takes a similar amount of time for both valid and invalid OAEP-padded messages. The majority of time is used to compute $m = c^d\ \text{mod}\ n$... Or is it? We can see that hash(label) is computed after $m$ is computed. We are able to use other labels... can we find a label that is slow enough for us to detect whether $m < 2^{2016}$? Yes - From the source code, apart from the three agencies, we can make use with the LFI vulnerability to include any of the files inside the container. We can use a long file and it will be more expensive to compute its hash. One file I found inside the container is /usr/lib/x86_64-linux-gnu/libicui18n.a, which is around 35MB.

$ ls -al /usr/lib/x86_64-linux-gnu/libicui18n.a
# -rw-r--r-- 1 root root 34867974 Mar 14  2020 /usr/lib/x86_64-linux-gnu/libicui18n.a

We can set the oracle name to be ../../../../usr/lib/x86_64-linux-gnu/libicui18n.a. Given a ciphertext $c$, it takes around 300ms to respond if $m < 2^{1016}$, while it takes only 30ms otherwise. This is pretty reliable! After all, we can use this to check if a given message falls in $m < 2^{1016}$. By implementing the Manger's attack, I am able to recover the OAEP-padded $m$. Eventually, the flag pops out after 100 minutes with around 20K calls - justCTF{60c173b4c6554af11e43a8c95190dcde749443}. First blood! 🎉

Addendum. I am awared from @josep68_'s writeup that 1.1K oracle calls should be sufficient to recover the padded message. It is my implementation to Manger's attack that made it super inefficient...