Challenge: RSA logfile

The following encrypted messages have been intercepted from the network:

39677f67eb9de589b63e511ee840d9efeb0fee812542c4f2035f64a1704e127164e632fbf4293f08648ee879
0f00ddcb841526a8718afcfb62ac3c5115c6eb2905df5d66877722b517b69a6dc53fa30bfb2ddc525ca92a5b
542563d217b7b785c677830d7411ecc233a8cc8e950004ec8349c714edf9a14452c101853e1e1ee8

c7c2c40aff92de473fed6a62e8379401f49c50c575d3b8d73fc27d754a802b753000781478e9c3f6653f96b0
53c4da210b08da743726e2edb40f6e8b47de08e652d75b7bb17954456983f39c8fb7092e7a8300ca3f743aad
660cf349a7a8980fcdf414801b856a76ea597825a33ef68a9c5d448a4f7149a74ecb6345bd660c67

Both messages are believed to be the same plain message containing a secret password, encrypted under the following public key

-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDheypWVeEBnoWqmqV8CZcYkh7k
m4/bNtHcATfdqp6yqimB83fOxJ/bsbdbfr9qvibxYZYHq7yr519aNPGdI6T9lDLV
4uc1TOwT/B1U45OaMCOTcD0GAb6bQ7BuKZ2OxOx6GlRMs7Rl9IqJ1Y2Nd/dVhDn1
0vt73CYiwLugMcmxcwIDAQAB
-----END PUBLIC KEY-----

It has also been leaked a logfile of the keypair generation process:

[myRSAkeygen] 1024 bits key generation starts
[myRSAkeygen] Using the default public exponent
[myRSAkeygen] Generating the primes .............++++++ .......++++++
[ExtenEuclid] Called with 0x10001 0xe17b2a5655e1019e85aa9aa57c099718921ee49b8fdb36d1dc01
37ddaa9eb2aa2981f377cec49fdbb1b75b7ebf6abe26f1619607abbcabe75f5a34f19d23a4fbb3ae474bae21
8834d34e8d383a0a834b2e993bc283d10490c1083de8ec241e401463a609cbf44cc0588e898890bb73b118f4
e5da155a8db4c10fc99cff160530
[myRSAkeygen] Generation successful
[myRSAkeygen] Saving the key-pair into file 'key.pem'

Can you write a program that recovers the secret password contained in the plain messages?

7 thoughts on “Challenge: RSA logfile”

  1. Hi everybody!!

    I’ve done it!! 🙂
    I’ve found the way to recover the secret password and I wrote some PHP functions (used in a webpage) that displays the private key and the decrypted message!

    Should I post everything here as a comment or there is another more suitable place?

    Thank you!

  2. Well done Alessio, sure you can publish here so that other can see your solution and comment or propose more …

    I see you like a lot PHP (I guess you use it for your job). May I anyway suggest that you experiment with other languages? PHP is fine but it’s specialized for WEB applications, so maybe it’s not the simplest way to go.

    For this exercises python is a great choice as it’s intuitive, fast and with extremely easy-to-use data structures. It is also very well documented: https://www.python.org/doc/

    Give it a try!

    btw if there’s enough interest we might organize a hands-on lab on basic python just to give the basic notions.

    @all as usual feel free of posting more solutions. Even if you are not the fist one any more you might get bonus if your solution is elegant/original/different …

  3. Here I am!

    First of all: how I solved it! Basically I saw that in the leaked log file there is a [ExtenEuclid] string followed by the default public exponent and then a large hex number which is different from the modulus (that can obviously be computed from the PEM formatted key). The first few bytes, however, are the same! So I guessed that the hex number in the log file is actually (p-1)(q-1). So I tried to compute the private exponent and then decrypt the two messages. It worked and the two messages contain the same plaintext with a header of non relevant bytes (this part is not the same in the two messages). The plaintext we’re interested in is: “The secret password is l33t2011”.

    The following are all the PHP functions I implemented in order to decrypt the messages. I have to admit that it has been rather challenging because PHP does not easily manage 1024 bit numbers… I had to use some special functions (in the BCMath library). I also used the OpenSSL library embedded in PHP to compute the modulus (and the public exponent) from the PEM.

    <?php

/* This function converts a hexadecimal value into a decimal value
 * with arbitrary precision
 */
function LargeHex2Dec($number) {
    $toRet = "0";
    $exp = "0";
    while($number != "") {
        $lsd = substr($number,strlen($number)-1);
        if (!is_numeric($lsd)) {
            $lsd = "" . ord($lsd) - ord("a") + 10;
        }
        $toRet = bcadd($toRet, bcmul($lsd,bcpow("16",$exp)));
        $exp = bcadd($exp,"1");
        $number = substr($number,0,strlen($number) - 1);
    }
    return $toRet;
}

/* This function converts a decimal value into a hexadecimal value
 * with arbitrary precision
 */
function LargeDec2Hex($number) {
    $toRet = array();
    $digits = 0;
    
    while ($number != "0") {
        $toRet[$digits++] = bcmod($number, "16");
        $number = bcdiv($number, "16", 0);
    }
    
    if (!isset($toRet[0])) {
        $toRet[0] = "0";
    }
    
    $final_conv = "";
    foreach ($toRet as $value) {
        if (intval($value) > 9) {
            $value = chr(ord('a') + ($value - 10));
        }
        
        $final_conv = $value . $final_conv;
    }
    
    return $final_conv;
}

/* This function converts a hexadecimal value into a binary value
 * with arbitrary precision
 */
function LargeHex2Bin($number) {
    $conversion_table = array("0" => "0000",
                              "1" => "0001",
                              "2" => "0010",
                              "3" => "0011",
                              "4" => "0100",
                              "5" => "0101",
                              "6" => "0110",
                              "7" => "0111",
                              "8" => "1000",
                              "9" => "1001",
                              "a" => "1010",
                              "b" => "1011",
                              "c" => "1100",
                              "d" => "1101",
                              "e" => "1110",
                              "f" => "1111"
                             );
    
    $toRet = "";
    while ($number != "") {
        $toRet .= $conversion_table[substr($number,0,1)];
        $number = substr($number,1);
    }
    
    while (substr($toRet,0,1) != "1") {
        $toRet = substr($toRet,1);
    }
    
    return $toRet;
}

/* This function is used to compute the modulus and public exponent from a
 * public key written using the PEM standard
 * It uses the openssl function embedded in the PHP language
 */
function getExponentModulus($key,&$e,&$n) {
    if (($res = openssl_pkey_get_public($key)) === FALSE) {
        return FALSE;
    }
    
    if (($det = openssl_pkey_get_details($res)) === FALSE) {
        return FALSE;
    }
    
    $e = bin2hex($det["rsa"]["e"]);
    $n = bin2hex($det["rsa"]["n"]);
    
    return TRUE;
}

/* This function computes the inverse mod $d of $c */
function EuclidExtended($c,$d) {
    $c = LargeHex2Dec($c);
    $d = LargeHex2Dec($d);
    $d0 = $d;
    $e = "1";
    $f = "0";
 
    while ($d != "0") {
        $q = bcdiv($c, $d,0);
        $tmp = bcsub($c, bcmul($q, $d));
        $c = $d;
        $d = $tmp;
        $tmp = bcsub($e, bcmul($q, $f));
        $e = $f;
        $f = $tmp;        
    }
 
    if ($c == "1") {
        return LargeDec2Hex(bcmod($e, $d0));
    }
}

/* This function decrypts a ciphertext using a certain pair (key,mod).
 * It is based on the SquareAndMultiply algorithm but it computes the mod
 * operation at each step. This is done because the PHP language has troubles
 * in computing multiplications with too many digits.
 */
function decrypt($cipher,$key,$modulus) {
    $x = LargeHex2Dec($cipher);
    $e = LargeHex2Bin($key);
    $m = LargeHex2Dec($modulus);
    $r = "1";
    while ($e != "") {
        $r = bcpowmod($r,"2",$m);
        if (substr($e,0,1) == "1") {
            $r = bcmod(bcmul($r,$x),$m);
        }
        $e = substr($e,1);
    }
    
    return LargeDec2Hex($r);
}

/* This function converts a large hexadecimal value into a string */
function getResultString($hex) {
    $toRet = "";
    while ($hex != "") {
        $char = substr($hex,strlen($hex) - 2,2);
        $ascii = LargeHex2Dec($char);
        $toRet = chr($ascii) . $toRet;
        $hex = substr($hex,0,strlen($hex) - 2);
    }
    
    return $toRet;
}
?>

    And then there is the code used to call these functions, embedded in a webpage:

    <?php
require_once("./rsa_decrypter.php");

$RSA = (isset($_POST["RSA"])) ? $_POST["RSA"] : "";
$leak = (isset($_POST["leak"])) ? strtolower(str_replace("\r\n", "", $_POST["leak"])) : "";
$message = (isset($_POST["message"])) ? strtolower(str_replace("\r\n", "", $_POST["message"])) : "";

/* OMITTED HTML CODE */

if ($RSA != "" && $leak != "" && $message != "") {
    if (getExponentModulus($RSA, $exponent, $modulus)) {
        $private_key = EuclidExtended($exponent, $leak);
        echo "<strong>The computed private key is</strong>:" . $private_key . "<br><br><br>";
        $decrypted = decrypt($message, $private_key, $modulus);
        echo "<strong>The decrypted message is</strong>:" . getResultString($decrypted);
    }
}
?>

    If you want to see this code in action, just click on my name and use the webpage (I published it on my webspace 🙂 )

    I use PHP a lot because is a language that I deeply know and I find it more natural for me to write code in that language! But it’s definitely not the best choice to implement cryptographic things since it does not manage large numbers properly… So I take Prof. Riccardo’s suggestion into account and I’ll try to use Python in the future for sure!!! 😉

    I wish everybody a nice evening! 😉

  4. Nice!
    what you call “header” is in fact a (PKCS#1) random padding that is useful to randomize the ciphertext and to make it as long as the block. It should have a 0x00 byte to separate for the actual message (you can automatically remove it).
    Good idea to use openssl, you could use it also for decryption. And yes, it would be nice to see you trying some python 😉

  5. Yes, I call it a “header” but I actually meant a random padding! But, honestly, I thought it was completely random and I didn’t consider PKCS#1 and the 0x00 byte! So I didn’t check for the 0x00 byte in order to clean up the decrypted message! I have modified the getResultString function, so now it removes all the padding and it leaves only the plaintext!
    Here’s the updated source code:

    function getResultString($hex) {
    $toRet = "";
    while ($hex != "") {
        $char = substr($hex,strlen($hex) - 2,2);
        
        if ($char == "00") { // If the PKCS#1 delimiter is found
            break; // stop the loop!!
        }
        
        $ascii = LargeHex2Dec($char);
        $toRet = chr($ascii) . $toRet;
        $hex = substr($hex,0,strlen($hex) - 2);
        
    }
    
    return $toRet;
}

    I didn’t use OpenSSL for decryption because I wanted to try to implement the algorithm myself! 🙂

    About the Hands-on lab: I love the idea! It would be great! If it is possible I’d ask to arrange lab lectures on thursday because on monday I can’t attend due to my job!

    Thank you so much! 🙂

  6. Hi all!
    This is a solution that uses the RSA module of the PyCripto API. With these classes I read the modulo of the public key, then I built a private key according to the values that we can extract from the log file. Finally, I used the private key to decrypt the two ciphertexts and discover the plaintexts. In the PyCripto documentation I saw there are two different standard types of padding, so I try both, the first padding is the right one.

    from Crypto.PublicKey import RSA # used to build a private key
# two standard types of padding
from Crypto.Cipher import PKCS1_v1_5
from Crypto.Cipher import PKCS1_OAEP
# usefull doc: https://www.dlitz.net/software/pycrypto/api/2.6/

# Given two coprime numbers c and d, return a number x such that (x * c) % d = 1
def EuclidExt(c,d):
    d0 = d
    e = 1
    f = 0
    while d != 0:
        q = c/d		# integer division
        tmp = c - q*d	# this is c % d
        c = d
        d = tmp
        tmp = e - q*f	# new computation for the inverse
        e = f
        f = tmp
    if c == 1:
	return e % d0	# if gcd is 1 we have that e is the inverse

# from the public key get the modulo and the public exponent (the public exponent is written also in the log file)
public_key_pem = "-----BEGIN PUBLIC KEY-----\nMIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDheypWVeEBnoWqmqV8CZcYkh7k\nm4/bNtHcATfdqp6yqimB83fOxJ/bsbdbfr9qvibxYZYHq7yr519aNPGdI6T9lDLV\n4uc1TOwT/B1U45OaMCOTcD0GAb6bQ7BuKZ2OxOx6GlRMs7Rl9IqJ1Y2Nd/dVhDn1\n0vt73CYiwLugMcmxcwIDAQAB\n-----END PUBLIC KEY-----"
public_key = RSA.importKey(public_key_pem)

n = getattr(public_key.key, 'n')
e = getattr(public_key.key, 'e')

# from the log file get phi n (we can guess that it is phi n because is different from n)
phi_n = int("0xe17b2a5655e1019e85aa9aa57c099718921ee49b8fdb36d1dc0137ddaa9eb2aa2981f377cec49fdbb1b75b7ebf6abe26f1619607abbcabe75f5a34f19d23a4fbb3ae474bae218834d34e8d383a0a834b2e993bc283d10490c1083de8ec241e401463a609cbf44cc0588e898890bb73b118f4e5da155a8db4c10fc99cff160530", 0)

# compute the private exponent with the Euclide Extended algorithm
d = EuclidExt(e, phi_n)

print("Modulo:\n%d\nPubblic exponent:\n%d\np * q:\n%d\nPrivate exponent:\n%d" % (n, e, phi_n, d) )

# build a private rsa key
private_key = RSA.construct([long(n),long(e), long(d)])

cipher_text_1 = "39677f67eb9de589b63e511ee840d9efeb0fee812542c4f2035f64a1704e127164e632fbf4293f08648ee8790f00ddcb841526a8718afcfb62ac3c5115c6eb2905df5d66877722b517b69a6dc53fa30bfb2ddc525ca92a5b542563d217b7b785c677830d7411ecc233a8cc8e950004ec8349c714edf9a14452c101853e1e1ee8"
cipher_text_2 = "c7c2c40aff92de473fed6a62e8379401f49c50c575d3b8d73fc27d754a802b753000781478e9c3f6653f96b053c4da210b08da743726e2edb40f6e8b47de08e652d75b7bb17954456983f39c8fb7092e7a8300ca3f743aad660cf349a7a8980fcdf414801b856a76ea597825a33ef68a9c5d448a4f7149a74ecb6345bd660c67"

# try to decrypt the texts with two different standard paddings
# the two plaintexts are hexadecimal string, we must decode them
try:
	cipher_obj = PKCS1_v1_5.new(private_key)
	print(cipher_obj.decrypt(cipher_text_1.decode('hex'), 0))
	print(cipher_obj.decrypt(cipher_text_2.decode('hex'), 0))
except ValueError:
	print("The text is not encrypted with PKCS1_v1_5")

try:
	cipher_obj = PKCS1_OAEP.new(private_key)
	print(cipher_obj.decrypt(cipher_text_1.decode('hex')))
	print(cipher_obj.decrypt(cipher_text_2.decode('hex')))
except ValueError:
	print("The text is not encrypted with PKCS1_OAEP")

Comments are closed.