Naughty or Nice v2

We have a binary that prints a welcome message and asks for 128 bytes of input. The input is decrypted using textbook RSA with a known modulus and 0x10001 as the exponent, and if the padding is (almost) correct, marked as executable and executed.

int main()
{
    // print welcome banner

    if(fread(ciphertext,1,0x80,stdin) != 0x80) {
        puts("Your wish list is too short!");
        exit(-1);
    }

    mpz_init(N);
    mpz_import(N,0x80,1,1,0,0,pubkey,0x1013e3);
    mpz_init(C);
    mpz_import(C,0x80,1,1,0,0,ciphertext,0x101426);
    mpz_powm_ui(C,C,0x10001,N);

    mpz_export(plaintext,&len_plain,1,1,0,0,C,0x101479);

    memmove(plaintext + (0x80 - len_plain),plaintext,len_plain);
    memset(plaintext,0,0x80 - len_plain);
    plaintext[128] = 0;

    // checks that plaintext is of the form "\x00\x02" + g + "\x00" + c and returns c
    // (where g is anything with no zero-bytes)
    exec = rsa_pkcs1_unpad(plaintext);
 
    if (exec == (undefined *)0x0) {
        puts("Naughty!");
    }
    else {
        puts("Nice!");
        len = strlen(exec);
        make_executable(exec,len);
        (*(code *)exec)();
    }
    return 0;
}

If the program used 3 as the exponent, it would be vulnerable to purely crypto-based attacks, such as the one in Bleichenbacher ’06, “Forging some RSA signatures with pencil and paper”. They, however, won’t work here (the basic idea they rely on is that a message can be short enough its cube is still less than the modulus).

We will exploit two vulnerabilities:

Consider a ciphertext that looks like the following, where <shellcode> is something we want to execute (like execve("/bin/sh", 0, 0)) and <padding> is a few random bytes,

90 90 90 .. 90 <shellcode> <padding>

such that it decrypts to something like

00 02 xx xx .. xx 00 eb XX ...

After removing the padding, the program will execute eb XX, which is a near jump that can move the program counter by up to ~128 bytes in either direction (PC += sign_extend(XX)). If the XX offset is such that this lands in the NOP sled (90 90 ...), it will jump to the ciphertext and execute our shellcode.

For this to work, we need to guess three bytes (00, 02 and eb right after the first zero-byte), and we need an offset that lands in the correct place. Even if there was only one valid value of XX, this would require reasonably many (around 2^32) choices of padding, and since there are many such valid values, we can brute-force a working payload in around fifteen minutes.

Flag: AOTW{Nev3r_Ev3r_r0ll_ur_0wn_crypt0}