Challenge: RSA logfile

The following encrypted messages have been intercepted from the network:

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

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

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")
    

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.