Challenge - Wiener waltz
During their yearly season opening party our super-smart elves developed an improved usage of the well known RSA crypto algorithm. Under the “Green IT” initiative they decided to save computing horsepower (or rather reindeer power?) on their side. To achieve this they chose a pretty large private exponent, around 1/4 of the length of the modulus – impossible to guess. The reduction of 75% should save a lot of computing effort while still being safe. Shouldn’t it?
Mission: Your SIGINT team captured some communication containing key exchange and encrypted data. Can you recover the original message?
b7307460-be03-45be-bd9f-b404b48e62c9.zip
Hints: Don’t waste time with the attempt to brute-force the private key
Solution
First we look in the pcap file for the key exchange and the sent data. It quickly becomes clear that it is not a normal TLS handshake, but that the transmission takes place unencrypted and the raw data is then encrypted in itself.
We make out the following packets with json payload, annotated by us:
Encryption setup
A->B
{
"pubkey":
{
"n": "dbn25TSjDhUge4L68AYooIqwo0HC2mIYxK/ICnc+8/0fZi1CHo/QwiPCcHM94jYdfj3PIQFTri9j/za3oO+3gVK39bj2O9OekGPG2M1GtN0Sp+ltellLl1oV+TBpgGyDt8vcCAR1B6shOJbjPAFqL8iTaW1C4KyGDVQhQrfkXtAdYv3ZaHcV8tC4ztgA4euP9o1q+kZux0fTv31kJSE7K1iJDpGfy1HiJ5gOX5T9fEyzSR0kA3sk3a35qTuUU1OWkH5MqysLVKZXiGcStNErlaggvJb6oKkx1dr9nYbqFxaQHev0EFX4EVfPqQzEzesa9ZAZTtxbwgcV9ZmTp25MZg==",
"e": "S/0OzzzDRdsps+I85tNi4d1i3d0Eu8pimcP5SBaqTeBzcADturDYHk1QuoqdTtwX9XY1Wii6AnySpEQ9eUEETYQkTRpq9rBggIkmuFnLygujFT+SI3Z+HLDfMWlBxaPW3Exo5Yqqrzdx4Zze1dqFNC5jJRVEJByd7c6+wqiTnS4dR77mnFaPHt/9IuMhigVisptxPLJ+g9QX4ZJX8ucU6GPSVzzTmwlDIjaenh7L0bC1Uq/euTDUJjzNWnMpHLHnSz2vgxLg4Ztwi91dOpO7KjvdZQ7++nlHRE6zlMHTsnPFSwLwG1ZxnGVdFnuMjEbPA3dcTe54LxOSb2cvZKDZqA==",
"format": ["mpz_export", -1, 4, 1, 0]
},
"sessionId": "RmERqOnbsA/oua67sID4Eg=="
}Block 0
A->B
{
"sessionId": "RmERqOnbsA/oua67sID4Eg==",
"blockId": 0,
"data": "fJdSIoC9qz27pWVpkXTIdJPuR9Fidfkq1IJPRQdnTM2XmhrcZToycoEoqJy91BxikRXQtioFKbS7Eun7oVS0yw==",
"format": "plain"
}
B->A
{
"sessionId": "RmERqOnbsA/oua67sID4Eg==",
"blockId": 0,
"msg": "ack"
}Block 2
A->B
{
"sessionId": "RmERqOnbsA/oua67sID4Eg==",
"blockId": 2,
"data": "fRYUyYEINA5i/hCsEtKkaCn2HsCp98+ksi/8lw1HNTP+KFyjwh2gZH+nkzLwI+fdJFbCN5iwFFXo+OzgcEMFqw==",
"format": "plain"
}
B->A
{
"sessionId": "RmERqOnbsA/oua67sID4Eg==",
"blockId": 2,
"msg": "ack"
}Block 3
A->B
{
"sessionId": "RmERqOnbsA/oua67sID4Eg==",
"blockId": 3,
"data": "+y2fMsE0u2F6bp2VP27EaLN68uj2CXm9J1WVFyLgqeQryh5jMyryLwuJNo/pz4tXzRqV4a8gM0JGdjvF84mf+w==",
"format": "plain"
}
B->A
{
"sessionId": "RmERqOnbsA/oua67sID4Eg==",
"blockId": 3,
"msg": "ack"
}Block 1
A->B
{
"sessionId": "RmERqOnbsA/oua67sID4Eg==",
"blockId": 1,
"data": "vzwheJ3akhr1LJTFzmFxdhBgViykRpUldFyU6qTu5cjxd1fOM3xkn49GYEM+2cUVk22Tu5IsYDbzJ4/zSDfzKA==",
"format": "plain"
}
B->A
{
"sessionId": "RmERqOnbsA/oua67sID4Eg==",
"blockId": 1,
"msg": "ack"
}Instruction
A->B
{
"sessionID": "RmERqOnbsA/oua67sID4Eg==",
"msg": "decrypt"
}
B->A
{
"sessionID": "RmERqOnbsA/oua67sID4Eg==",
"msg": "kthxbye"
}So we have the public key, 4 packets with data and a farewell. The data blocks have IDs and have not been sent in the right order, presumably they need to be put in the right order.
To decrypt the data, we need the private key. Fortunately, the elves want to save reindeer power and have specified that the private exponent of the RSA key should be about a quarter of the modulus to generate the keys.
While refreshing our knowledge about RSA, we stumble upon the “Wieners Attack“, which aims exactly at this.
Fortunately, there are already some implementations for this attack on the Internet (we are going to use this one), but unfortunately not in one of our preferred languages, but in Python instead. But first we have to be able to import the public key. “format": ["mpz_export",-1,4,1,0]” is a strong hint towards GMPLib, luckily there is a C# wrapper for the GMPLib:
mpz_t rop2 = new mpz_t();
gmp_lib.mpz_init(rop2);
var eBytes = Convert.FromBase64String(
"S/0OzzzDRdsps+I85tNi4d1i3d0Eu8pimcP5SBaqTeBzcADturDYHk1QuoqdTtwX9XY1Wii6AnySpEQ9eUEETYQkTRpq9rBggIkmuFnLygujFT+SI3Z+HLDfMWlBxaPW3Exo5Yqqrzdx4Zze1dqFNC5jJRVEJByd7c6+wqiTnS4dR77mnFaPHt/9IuMhigVisptxPLJ+g9QX4ZJX8ucU6GPSVzzTmwlDIjaenh7L0bC1Uq/euTDUJjzNWnMpHLHnSz2vgxLg4Ztwi91dOpO7KjvdZQ7++nlHRE6zlMHTsnPFSwLwG1ZxnGVdFnuMjEbPA3dcTe54LxOSb2cvZKDZqA==");
var nBytes = Convert.FromBase64String(
"dbn25TSjDhUge4L68AYooIqwo0HC2mIYxK/ICnc+8/0fZi1CHo/QwiPCcHM94jYdfj3PIQFTri9j/za3oO+3gVK39bj2O9OekGPG2M1GtN0Sp+ltellLl1oV+TBpgGyDt8vcCAR1B6shOJbjPAFqL8iTaW1C4KyGDVQhQrfkXtAdYv3ZaHcV8tC4ztgA4euP9o1q+kZux0fTv31kJSE7K1iJDpGfy1HiJ5gOX5T9fEyzSR0kA3sk3a35qTuUU1OWkH5MqysLVKZXiGcStNErlaggvJb6oKkx1dr9nYbqFxaQHev0EFX4EVfPqQzEzesa9ZAZTtxbwgcV9ZmTp25MZg==");
void_ptr data2 = gmp_lib.allocate(new size_t(Convert.ToUInt64(eBytes.Length)));
Marshal.Copy(eBytes, 0, data2.ToIntPtr(), eBytes.Length);
gmp_lib.mpz_import(rop2, new size_t(Convert.ToUInt64(eBytes.Length / 4)), -1, 4, 1, 0, data2);
char_ptr value2 = gmp_lib.mpz_get_str(char_ptr.Zero, 16, rop2);
Console.WriteLine("e in hex:");
Console.WriteLine(value2.ToString());
Console.WriteLine("");
mpz_t rop3 = new mpz_t();
gmp_lib.mpz_init(rop3);
void_ptr data3 = gmp_lib.allocate(new size_t(Convert.ToUInt64(nBytes.Length)));
Marshal.Copy(nBytes, 0, data3.ToIntPtr(), nBytes.Length);
gmp_lib.mpz_import(rop3, new size_t(Convert.ToUInt64(nBytes.Length / 4)), -1, 4, 1, 0, data3);
char_ptr value3 = gmp_lib.mpz_get_str(char_ptr.Zero, 16, rop3);
Console.WriteLine("n in hex:");
Console.WriteLine(value3.ToString());
Console.WriteLine("");
After we have successfully imported the public key, we write a Python script to use the Python implementation of the Wieners attack:
import owiener
import base64
e = int("64a0d9a8926f672fee782f1303775c4d8c8c46cf655d167b1b56719cc54b02f0c1d3b273444eb394fefa79473bdd650e3a93bb2a708bdd5d12e0e19b4b3daf83291cb1e73ccd5a73b930d426b552afde1ecbd1b022369e9ed39b094363d2573cf2e714e817e19257b27e83d4b29b713c218a0562dffd22e39c568f1e1d47bee6a8939d2eedcebec244241c9d2e632515d5da853471e19cde8aaaaf37dc4c68e541c5a3d6b0df316923767e1ca3153f9259cbca0b808926b86af6b06084244d1a7941044d92a4443d28ba027cf576355a9d4edc174d50ba8abab0d81e737000ed16aa4de099c3f94804bbca62dd62dddde6d362e129b3e23c3cc345db4bfd0ecf", 16)
n = int("a76e4c6615f59993dc5bc207f590194ec4cdeb1a57cfa90c1055f811901debf486ea1716d5dafd9dfaa0a931a820bc96b4d12b95578867122b0b54a6907e4cab94535396adf9a93b037b24ddb3491d2494fd7c4c27980e5f9fcb51e258890e9125213b2bd3bf7d64466ec747f68d6afa00e1eb8fd0b8ced8687715f21d62fdd9b7e45ed00d54214242e0ac86c893696d3c016a2f213896e3047507abb7cbdc0869806c835a15f9307a594b9712a7e96dcd46b4dd9063c6d8f63bd39e52b7f5b8a0efb78163ff36b70153ae2f7e3dcf213de2361d23c270731e8fd0c21f662d42773ef3fdc4afc80ac2da62188ab0a341f00628a0207b82fa34a30e1575b9f6e5", 16)
d = owiener.attack(e, n)
if d is None:
print("Failed")
else:
print("Hacked d={}".format(d))
After we have successfully calculated the private key, we switch back to C#. With the private key it is easy to decrypt the encrypted message:
var hackedD = "7b752b93e230ce0d24f04e3229f9f05e7cd83c49e49d4a174f2c82f2b58349b7034378325bd187bb41f4965813036c8f8d313f4c32aed77935cef33800e1a22f";
var tmpData = new List<byte>();
tmpData.AddRange(Convert.FromBase64String(
"fJdSIoC9qz27pWVpkXTIdJPuR9Fidfkq1IJPRQdnTM2XmhrcZToycoEoqJy91BxikRXQtioFKbS7Eun7oVS0yw=="));
tmpData.AddRange(Convert.FromBase64String(
"vzwheJ3akhr1LJTFzmFxdhBgViykRpUldFyU6qTu5cjxd1fOM3xkn49GYEM+2cUVk22Tu5IsYDbzJ4/zSDfzKA=="));
tmpData.AddRange(Convert.FromBase64String(
"fRYUyYEINA5i/hCsEtKkaCn2HsCp98+ksi/8lw1HNTP+KFyjwh2gZH+nkzLwI+fdJFbCN5iwFFXo+OzgcEMFqw=="));
tmpData.AddRange(Convert.FromBase64String(
"+y2fMsE0u2F6bp2VP27EaLN68uj2CXm9J1WVFyLgqeQryh5jMyryLwuJNo/pz4tXzRqV4a8gM0JGdjvF84mf+w=="));
var data = tmpData.ToArray();
var dataBigInt = new BigInteger(data, true, true);
var hackedDBigInt = new BigInteger(Convert.FromHexString(hackedD), true, true); //BigInteger.Parse(hackedD, );
var modulus = new BigInteger(Convert.FromHexString(value3.ToString()), true, true);
var decryptedBytes = BigInteger.ModPow(dataBigInt, hackedDBigInt, modulus).ToByteArray(true, true);
var s = Encoding.ASCII.GetString(decryptedBytes);
Console.WriteLine(s);
Console.ReadLine();
Wait what? No flag? Wait a minute!
In the debugger we look at the value of variable s and lo and behold! The first line is simply by a carriage return (\r). The entire content of the message is:
"\u0001\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\rYou made it! Here is your flag: HV20{5hor7_Priv3xp_a1n7_n0_5mar7}\r\rGood luck for Hackvent, merry X-mas and all the best for 2021, greetz SmartSmurf\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"