Backdoored Crypto Code

backdoored.php

<?php

/*
 * Backdooring the constant-time comparison algorithm.
 * Taylor Hornby. Feburary 28, 2015.
 *
 * THIS CODE IS INTENTIONALLY BACKDOORED. DO NOT USE IT!
 */

/* ========================================================================= */
/* VULNERABLE CODE                                                           */
/* ========================================================================= */

/*
 * Pretend this is some sort of web application that accepts authenticated
 * ciphertexts (e.g. a cookie) and tries to authenticate then decrypt them,
 * returning an error code in the case of failure (so that clueless users can
 * try to debug your app, that's always useful...)
 *
 * This is all really just an excuse to do some cool bit-trickery in the attack
 * code below.
 */

define('ERR_BAD_CIPHERTEXT_PARTS', 1);
define('ERR_OPENSSL_NOT_AVAILABLE', 2);
define('ERR_BAD_HMAC', 3);

/* (No, this isn't the backdoor, that would be too easy) */
define('SECRET_KEY',  "YOUPICKBETTERKEY");

/* Returns zero if and only if $a == $b. */
function const_time_compare($a, $b)
{
    /* THIS IS INTENTIONALLY BACKDOORED. DO NOT USE IT. */
    if (strlen($a) != strlen($b)) {
        return 1;
    }

    $zero_iff_same = 0;
    for ($i = 0; $i < strlen($a); $i++) {
        $zero_iff_same |= ord($a[$i]) ^ ord($b[$i]);
    }

    /* hmm... */
    return $zero_iff_same;
}

function decrypt($ciphertext)
{
    /* THIS IS INTENTIONALLY BACKDOORED. DO NOT USE IT. */
    $err = 0;

    /* Ugly crypto, most likely has other mistakes just ignore them... */
    $parts = explode(':', $ciphertext);
    if (count($parts) !== 3) {
        $err = ERR_BAD_CIPHERTEXT_PARTS;
        goto fail;
    }
    $iv = hex2bin($parts[0]);
    $hmac = hex2bin($parts[1]);
    $ciphertext = hex2bin($parts[2]);
    if (strlen($iv) != 16 || strlen($hmac) != 16) {
        $err = ERR_BAD_CIPHERTEXT_PARTS;
        goto fail;
    }

    if (!function_exists('openssl_encrypt')) {
        $err = ERR_OPENSSL_NOT_AVAILABLE;
    }

    $good_hmac = hash_hmac('md5', $ciphertext, SECRET_KEY, true);
    $err = const_time_compare($good_hmac, $hmac);
    if ($err !== 0) {
        $erp = ERR_BAD_HMAC;        /* ??? */
        goto fail;
    }

    /* Too tired to finish the decryption, but it's not needed for the backdoor
        idea. */

fail:
    return $err;
}

/* ========================================================================= */
/* ATTACK CODE                                                               */
/* ========================================================================= */

/* Message to forge. */
$ciphertext = "312ec803b2ce49e4a541068d495ab570";
$iv = "a677abfcc88c8126deedd719202e5092";

/* Recover each 16-bit 'column' of the MAC independently. */
/* (I really just wanted an excuse to write this code.) */
$recovery = array();
for ($bit = 0; $bit < 8; $bit++) {
    for ($v = 0; $v < 65536; $v++) {
        $hmac = '';
        for ($i = 0; $i < 16; $i++) {
            $hmac .= chr( (($v >> $i) & 1) << $bit);
        }
        $hex_hmac = bin2hex($hmac);

        $ret = decrypt($iv . ':' . $hex_hmac . ':' . $ciphertext);
        if (($ret & (1 << $bit)) == 0) {
            echo "Bits in position $bit of each byte: $v\n";
            $recovery[$bit] = $v;
            break;
        }
    }
}

/* Put it all together. */
$recovered_hmac = '';
for ($i = 0; $i < 16; $i++) {
    $byte = 0;
    for ($bit = 0; $bit < 8; $bit++) {
        $byte |= (($recovery[$bit] >> $i) & 1) << $bit;
    }
    $recovered_hmac .= chr($byte);
}

$hex_hmac = bin2hex($recovered_hmac);
echo $hex_hmac . "\n";

/* Make sure we have a forgery. */
if (decrypt($iv.':'.$hex_hmac.':'.$ciphertext) === 0) {
    echo "It worked!\n";
}

?>