NSACodebreaker2022 - Task9
Table of Contents
Task 9
Unfortunately, looks like the ransomware site suffered some data loss, and doesn’t have the victim’s key to give back! I guess they weren’t planning on returning the victims’ files, even if they paid up.
There’s one last shred of hope: your cryptanalysis skills. We’ve given you one of the encrypted files from the victim’s system, which contains an important message. Find the encryption key, and recover the message.
Solution
Ahhh, we’ve come to the final task of this years NSA Codebreaker challenge. Unfortunately, the actual key generated by the victim has been lost. According to the website, the owners had to restore from an old backup. As such, some of the fairly newer generated keys were lost in the process. This is unfortunate for us, since we don’t get too simply use our script to reverse the key-encrypted-key to get our answer. All we have is the important_data.pdf.enc file to go off of.
The good thing is, we have LOTS of information to go off of in order to figure out how the key was generated, how the files were encrypted, and lastly - we have our computer science skills to help us save the day.
First things first, I wanted to know how the files were encrypted so we knew what complexity we were dealing with. I just so happened to remember a few tasks ago that our wireshark pcap file showed the attacker downloading their tools onto the victims machine. One of these files was called ransom.sh.
Going back and reopening our pcap file and navigating to the ransom.sh file being downloaded, we are able to see what the bash script contents were:
read -p "Enter encryption key: " key
hexkey=`echo -n $key | ./busybox xxd -p | ./busybox head -c 32`
export hexkey
./busybox find $1 -regex '.*\.\(pdf\|doc\|docx\|xls\|xlsx\|ppt\|pptx\)' -print -exec sh -c 'iv=`./openssl rand -hex 16`; echo -n $iv > $0.enc; ./openssl enc -e -aes-128-cbc -K $hexkey -iv $iv -in $0 >> $0.enc; rm $0' \{\} \; 2>/dev/null
It looks like the attacker is using the aes-128-cbc algorithm from the openssl library. Additionally, the attacker is generating a random 16 byte hex value as the aes IV, or Initialization Vector, and appending that to the beginning of our encrypted file!
If we were to open up the important_data.pdf.enc file we can see the first 16 byte hex value. Extracting that out and saving that for later already gives us the upper hand to decrypting this file.
adc3216ac29201fa484999e823a95e90
The only last piece of information we really need is the hexkey, which is arguably one of the most important parts! That being said, there is a VERY large space of which the hexkey can possibly be.
How do we break up the information we know in order to reduce are set of possible keys?
Luckily, after breaking down the lock function in task 8 we can focus primarily on the portion that generates the encryption key.
The first thing that happens come time to generate an encryption key is that the binary captures the current time. You can see this happening analyzing the binary with IDA with the following instructions:
call time_Now
lea rdi, a20060102t15040 ; "2006-01-02T15:04:05Z07:00"
mov esi, 25
nop dword_ptr[rax]
call time_Time_Format
Which can convert to being:
currentTime := time.Now()
formattedTime := currentTime.Format("2006-01-02T15:04:05Z07:00");
This value is then passed into the GetUUID() function to generate a Unique ID. The unique id is then encrypted using an AES Block Cipher encryption with the key-encryption-key we discovered earlier in Task 8.
The logic goes onto to access the database that stores their customers information, charges the customer for using their services, stores the encrypted key in the database, and then displays the “plainKey” for the user so they can go about encrypting the files of whoever they have compromised.
If you are following me thus far, you have probably also come to the same realization that, like a seed, if we are able to retrieve the timestamp for which the attacker generated the key, then we can make use of Golang’s wonderful documentation to reverse how the unique id is created to generate the exact same id used as an encryption key!
To that end, there is good news and bad news.
The good news is that from earlier tasks, we recovered the keygeneration log file that stores the timestamp of when a user requests an encryption key! We also have from Task B1 the cid number and the ransom amount!
https://zgoxzopogsqkolvv.ransommethis.net/demand?cid=88599
{... ,"amount":5.657, ...}
We also have the username of the attacker who was using the service from task 6.
JaggedGeneration
Matching all of this information in our key generation log file gives us:
2022-01-24T07:59:11-05:00 JaggedGeneration 88599 5.657
The timestamp is: 2022-01-24T07:59:11-05:00. This means the encryption key was requested on January 24th, 2022 at 7:59:11 PM. However, now there is some bad news…
with open("/opt/ransommethis/log/keygeneration.log", 'a') as logfile:
print(f"{datetime.now().replace(tzinfo=None, microsecond=0).isoformat()}\t{util.get_username()}\t{cid}\t{request.args.get('demand')}", file=logfile)
The first bit of bad news is that we are losing some precision. The function datetime.now() is being called, and the microseconds are being replaced with 0. Which is vital information that we need to generate our unique id - this is because of the way the Golang UUID generator function works; of which we will go into greater detail later.
The second bit of bad news is that the server is calling datetime.now()! Which means that the time being used in the keyMaster binary is NOT going to be the same as the timestamp that is being logged. It could be off anywhere from a few microseconds to multiple seconds!
From reverse engineering the keyMaster binary, I spotted the existence of a keyMaster.db file that stores the encrypted keys. Using the same LFI technique to extract the binary and user/victim database files, we can extract the keyMaster database file.
Now that we have a database file with other encrypted keys from other users, we can prove the timestamp difference by reversing the encrypted keys from other users and extracting the timestamp from the decrypted unique ids. We can then compare the timestamp to the timestamp that was logged for the same request.
Since we have our own script based on the keyMaster binary, it isn’t difficult to reverse the “lock” logic into an “unlock” function. This function looks like the following:
func Unlock(cipherstring string) string {
ciphertext := []byte(cipherstring)
key := Pbkdf2Cryption()
block, _ := aes.NewCipher(key)
if len(ciphertext) < aes.BlockSize {
panic("Text is too short")
}
iv := ciphertext[:aes.BlockSize]
ciphertext = ciphertext[aes.BlockSize:]
stream := cipher.NewCBCDecrypter(block, iv)
stream.CryptBlocks(ciphertext, ciphertext)
finalKey := base64.StdEncoding.EncodeToString(ciphertext[:32])
return finalKey
}
In doing this with every encrypted key present in the keyMaster database, I determined there was a range of 1 second to 11 second gap between the timestamp logged vs the timestamp the unique id was generated with!
For example, for this user the timestamps have a 10 second difference:
=== From keyMaster.db ===
CustomerId: 27184
ExpectedPayment: 1.245
HackerName: TenuousBasketball
CreationDate: 2021-07-14T02:42:33-04:00
EncryptedKey: SSNyoZWNI3Xa48s4NeK48q+uem3edL1lmGX+UA8D2BzQo700bMY5sW7jruXZnYnbVH+5526gFWMgaFZOb9gdSw==
=== Decrypted ===
DecryptedKey: aa944dcc-e46e-11eb-842a-39fe5d6c
RealTimeStamp: 2021-07-14 02:42:32.4313548 -0400 EDT
DBTimeStamp: 2021-07-14T02:42:33-04:00
TimeStampLogged: 2021-07-14T02:42:43-04:00
=== KeyGeneration Log ===
2021-07-14T02:42:43-04:00 TenuousBasketball 27184 1.245
Speaking of reversing encrypted keys from other users in the keyMaster.db file, we can analyze the UUIDs to see if we can find any patterns!
Making use of our extracted keyMaster database file and our unlock function, we can loop through all the keys! Here is some of the UUIDs we get from doing this:
...
44de1cf8-b228-11eb-842a-39fe5d6c
ef5c1d26-f27c-11eb-842a-39fe5d6c
09f28647-d13a-11eb-842a-39fe5d6c
2a845791-07a6-11ec-842a-39fe5d6c
22bf8723-cb1e-11eb-842a-39fe5d6c
36adf96e-f65f-11eb-842a-39fe5d6c
96272de6-1da5-11ec-842a-39fe5d6c
929aaf45-44aa-11ec-842a-39fe5d6c
ed1fd259-f862-11eb-842a-39fe5d6c
...
As we can see - there is quite a bit of the UUID that is consistent! Such as the 842a-39fe5d6c and the 11e(b/c) value. We could blindly accept this for how it is, however - it is better if we understand why the values are generated the way they are. Luckily Golang has some great documentation!
The following function is an edited version of the Golang source code getUUID()
func getUUID(timeString string) (uuid.UUID, error) {
t, _ := time.Parse("2006-01-02T15:04:05Z07:00", timeString)
now := uint64(t.UnixNano()/100) + g1582ns100
var id uuid.UUID
var clockSeq := 1066
seq := uint16(clockSeq&0x3fff) | 0x8000
timeLow := uint32(now & 0xffffffff)
timeMid := uint16((now >> 32) & 0xffff)
timeHi := uint16((now >> 48) & 0x0fff)
timeHi |= 0x1000 // Version 1
binary.BigEndian.PutUint32(id[0:], timeLow)
binary.BigEndian.PutUint16(id[4:], timeMid)
binary.BigEndian.PutUint16(id[6:], timeHi)
binary.BigEndian.PutUint16(id[8:], seq)
copy(id[10:], uuid.NodeID()[:])
return id, nil
}
This allows me to pass in various time stamps and analyze the respective UUID output, paying attention to the relationship that it has with each portion of the UUID.
Doing so helps me come to the conclusion that the last 4 bytes are determined by the clock sequence value and the last 8 bytes are determined by the uuid.NodeID(). This is different for every computer, which means each machine will have unique values - however those values will remain the same for every UUID generated from here on til the clock sequence or NodeID is forcefully changed. By decrypting all the generated user keys, I was able to determine that the clock sequence for the attackers machine is 1066 and that the NodeID can be set the same as the attackers machine by executing: uuid.SetNodeID([]byte{57, 254, 93, 108, 152, 118}).
Now if we generate a UUID with any timestamp - our UUID should have the same ending values as our keyMaster database examples.
...
e6df2be8-1732-11ec-842a-39fe5d6c
dbebfc0a-ca80-11eb-842a-39fe5d6c
=== My UUID ===
dde57300-80e0-11ed-842a-39fe5d6c <- timestamp used: "2022-12-20T23:38:00.218496-04:00"
The final bit of the 11e# pattern is determined by the year within the timestamp.
The year 2020 gives 11eb, the year 2021 gives 11ec and the year 2022 gives 11ed. Perfect!
Finally, the remaining values are controlled in tandem with the Month, Day, Hours, Minutes, Seconds, and Microseconds. This sounds like a lot, but since we know the Month, Day, Hour, and Minute that the key was generated - we only have to worry about the Seconds and Microseconds. Lets take a look at what our target timestamp looks like based on the timestamp given to us in the key generation log file.
=== keyGeneration log file ===
2022-01-24T07:59:11-05:00 JaggedGeneration 88599 5.657
timeString := "2022-01-24T07:59:11-05:00"
id, _ := getUUID(timeString)
fmt.Println("=== My UUID ===")
fmt.Println(id.String()[:32])
=== My UUID ===
6c83b980-7d15-11ec-842a-39fe5d6c
Great! Playing with the seconds of our time stamp, once can notice that the 7d15 value doesn’t change! Which means we are able to make the determination that a large majority of the UUID will be in the following format:
########-7d15-11ec-842a-39fe5d6c
Already, this largely reduces our search space! However, I knew I could still do so much better.
Lets see what happens when we look at the base range that we determined in our analysis earlier, anywhere from 1 seconds to 11 seconds difference.
fmt.Println("=== My UUID ===")
for i:= 0; i <= 11; i++ {
timeString := fmt.Sprintf("2022-01-24T07:59:%02d-05:00", i)
id, _ := getUUID(timeString)
fmt.Println(timeString + " -- " + id.String()[:32])
}
=== Output ===
=== My UUID ===
2022-01-24T07:59:00-05:00 -- 65f54200-7d15-11ec-842a-39fe5d6c
2022-01-24T07:59:01-05:00 -- 668dd880-7d15-11ec-842a-39fe5d6c
2022-01-24T07:59:02-05:00 -- 67266f00-7d15-11ec-842a-39fe5d6c
2022-01-24T07:59:03-05:00 -- 67bf0580-7d15-11ec-842a-39fe5d6c
2022-01-24T07:59:04-05:00 -- 68579c00-7d15-11ec-842a-39fe5d6c
2022-01-24T07:59:05-05:00 -- 68f03280-7d15-11ec-842a-39fe5d6c
2022-01-24T07:59:06-05:00 -- 6988c900-7d15-11ec-842a-39fe5d6c
2022-01-24T07:59:07-05:00 -- 6a215f80-7d15-11ec-842a-39fe5d6c
2022-01-24T07:59:08-05:00 -- 6ab9f600-7d15-11ec-842a-39fe5d6c
2022-01-24T07:59:09-05:00 -- 6b528c80-7d15-11ec-842a-39fe5d6c
2022-01-24T07:59:10-05:00 -- 6beb2300-7d15-11ec-842a-39fe5d6c
2022-01-24T07:59:11-05:00 -- 6c83b980-7d15-11ec-842a-39fe5d6c
As we can see, we have narrowed down another value! The first value will always be a 6! Now we are looking at a pattern of:
6#######-7d15-11ec-842a-39fe5d6c
Can we break this down even more? I think we can! We still haven’t looked at the microseconds yet!
To do this, I changed my approach slightly. Microseconds can be as large as 9999999, and have varying formats. However, never smaller than 5 digits with varying leading zeros.
I decided to instead generate UUIDs for every time stamp combination, store those values and extract the unique values for each remaining index. The code looks similar to this:
for uuidIdx := 1; uuidIdx <= 7; uuidIdx++ {
arr := []string{}
for seconds := 0; seconds <= 11; seconds++ {
for ms := 1000; ms <= 99999; ms++ {
timeString := fmt.Sprintf("2022-01-24T07:59:%02d.%05d-05:00", seconds, ms)
id, _ := getUUID(timeString)
arr = append(arr, string(id.String()[uuidIdx]))
}
}
keys := make(map[string]bool)
uniq := []string{}
for _, entry := range arr {
if _, value := keys[entry]; !value {
keys[entry] = true
uniq = append(uniq, entry)
}
}
fmt.Println(fmt.Sprintf("Index: %d", k))
fmt.Println(uniq)
}
I did this for every microsecond variation as well. Doing this gave me the following unique characters for each index:
1: [5 6 7 8 9 a b c d]
2: [0 1 2 3 4 5 6 7 8 9 a b c d e f]
3: [0 1 2 3 4 5 6 7 8 9 a b c d e f]
4: [0 1 2 3 4 5 6 7 8 9 a b c d e f]
5: [0 1 2 3 4 5 6 7 8 9 a b c d e f]
6: [0 1 2 3 4 5 6 7 8 9 a b c d e f]
7: [0 4 8 c] (5 digit microseconds)
7: [a e 2 6] (6 digit microseconds)
7: [1 3 5 7 9 b d f] (7 digit microseconds)
As the microseconds digits increased, so did the number of characters. However, if we generate all possible UUIDs for 5 digit microseconds - if there are no matches, then we can ignore those values for the 6 and 7 digit microseconds. So on and so forth for the 6 digit microsecond characters that overlap with the 7 digit microseconds. Additionally, we were able to eliminate 7 characters out of 16 characters total for the 1st index. Unfortunately, the 2nd to 6th index cannot be broken down any further.
At this point - I think we’ve broke up our possible keys into as low of a range as we possibly can. I decided to split the UUIDs into three files for each digit microsecond. That being 5, 6, and 7 digits.
Now comes into question - how do we go about running our decryption test without waiting for years?
One answer… multithreading.
C# has a wonderful cryptography library and is super easy to set up. I created a program that ran 20 threads in total! The script would read in one of the files, attempt to decrypt the encrypted file, and look at the contents of the result to see if it resembles a PDF file. If so, it will let us know and return!
Here is a look at my code!
using System.Threading;
using System;
using System.IO;
using System.Security.Cryptography;
using System.Text;
using System.Linq;
namespace NsaTaskNine
{
class Program
{
public static byte[] StringToByteArray(string hex) {
return Enumerable.Range(0, hex.Length)
.Where(x => x % 2 == 0)
.Select(x => Convert.ToByte(hex.Substring(x, 2), 16))
.ToArray();
}
public static byte[] DecryptAes(byte[] cipherText, byte[] IV, byte[] Key)
{
Aes aes = Aes.Create();
aes.Key = Key;
aes.IV = IV;
aes.BlockSize = 128;
aes.Mode = CipherMode.CBC;
aes.Padding = PaddingMode.None;
// decryption
using (ICryptoTransform decrypt = aes.CreateDecryptor(aes.Key, aes.IV))
{
byte[] decryptedText = decrypt.TransformFinalBlock(cipherText, 0, cipherText.Length);
return decryptedText;
}
}
static void TestMethod(int idx1, string[] keys, byte[] cipher, string arg)
{
int increment = (keys.Length / 20);
int end = increment * idx1;
int start = end - increment;
int halfWaypoint = start + ((start - end) / 2);
Console.WriteLine(arg + " -- starting at index: " + start.ToString() + " and ending at: " + end.ToString() + "\n");
byte[] IV = StringToByteArray("adc3216ac29201fa484999e823a95e90");
for (int idx = start; idx <= end; idx++) {
byte[] test = Encoding.Default.GetBytes(keys[idx]);
string test_hex = BitConverter.ToString(test);
string hexKey = test_hex.Replace("-", "").Substring(0, 32).ToLower();
byte[] key = StringToByteArray(hexKey);
byte[] output = DecryptAes(cipher, IV, key);
string outputStr = Encoding.UTF8.GetString(output);
if (outputStr.Contains("stream") && outputStr.Contains("endstream")) {
Console.WriteLine(">>> !Hack the Planet! <<<");
Console.WriteLine(keys[idx]);
Console.WriteLine(hexKey);
Console.WriteLine(idx);
string filename = "test_file_" + idx.ToString() + ".pdf";
File.WriteAllBytes(filename, output);
return;
}
if (idx == halfWaypoint) {
Console.WriteLine("Thread " + idx1.ToString() + " has reached the halfway point!\n");
}
}
}
static void Main(string[] args)
{
Console.WriteLine("This is the main application . . .");
string uuid_path = @"uuid.txt";
string[] keys = File.ReadAllLines(uuid_path);
string encoded_file = @"important_data.pdf.enc";
byte[] cipher = File.ReadAllBytes(encoded_file);
var t1 = new Thread(() => TestMethod(1, keys, cipher, "Hello from thread one"));
t1.Name = "ThreadOne";
var t2 = new Thread(() => TestMethod(2, keys, cipher, "Hello from thread two"));
t2.Name = "ThreadTwo";
var t3 = new Thread(() => TestMethod(3, keys, cipher, "Hello from thread three"));
t3.Name = "ThreadThree";
var t4 = new Thread(() => TestMethod(4, keys, cipher, "Hello from thread four"));
t4.Name = "ThreadFour";
var t5 = new Thread(() => TestMethod(5, keys, cipher, "Hello from thread five"));
t5.Name = "ThreadFive";
var t6 = new Thread(() => TestMethod(6, keys, cipher, "Hello from thread six"));
t6.Name = "ThreadSix";
var t7 = new Thread(() => TestMethod(7, keys, cipher, "Hello from thread seven"));
t7.Name = "ThreadSeven";
var t8 = new Thread(() => TestMethod(8, keys, cipher, "Hello from thread eight"));
t8.Name = "ThreadEight";
var t9 = new Thread(() => TestMethod(9, keys, cipher, "Hello from thread nine"));
t9.Name = "ThreadNine";
var t10 = new Thread(() => TestMethod(10, keys, cipher, "Hello from thread ten"));
t10.Name = "ThreadTen";
var t11 = new Thread(() => TestMethod(11, keys, cipher, "Hello from thread eleven"));
t11.Name = "ThreadEleven";
var t12 = new Thread(() => TestMethod(12, keys, cipher, "Hello from thread twelve"));
t12.Name = "ThreadTwelve";
var t13 = new Thread(() => TestMethod(13, keys, cipher, "Hello from thread thirteen"));
t13.Name = "ThreadThirteen";
var t14 = new Thread(() => TestMethod(14, keys, cipher, "Hello from thread fourteen"));
t14.Name = "ThreadFourteen";
var t15 = new Thread(() => TestMethod(15, keys, cipher, "Hello from thread fifteen"));
t15.Name = "ThreadFifteen";
var t16 = new Thread(() => TestMethod(16, keys, cipher, "Hello from thread sixteen"));
t16.Name = "ThreadSixteen";
var t17 = new Thread(() => TestMethod(17, keys, cipher, "Hello from thread seventeen"));
t17.Name = "ThreadSeventeen";
var t18 = new Thread(() => TestMethod(18, keys, cipher, "Hello from thread eighteen"));
t18.Name = "ThreadEighteen";
var t19 = new Thread(() => TestMethod(19, keys, cipher, "Hello from thread nineteen"));
t19.Name = "ThreadNineteen";
var t20 = new Thread(() => TestMethod(20, keys, cipher, "Hello from thread twenty"));
t20.Name = "ThreadTwenty";
t1.Start();
t2.Start();
t3.Start();
t4.Start();
t5.Start();
t6.Start();
t7.Start();
t8.Start();
t9.Start();
t10.Start();
t11.Start();
t12.Start();
t13.Start();
t14.Start();
t15.Start();
t16.Start();
t17.Start();
t18.Start();
t19.Start();
t20.Start();
}
}
}
The 7 digit microsecond file was the magic file, finding the output file resembling a PDF file within minutes of running! Looks like all this hard work has paid off after all!
>>> !Hack the Planet! <<<
6923530f-7d15-11ec-842a-39fe5d6c
36393233353330662s376431352s3131
34711943
Of course, opening the resulting file still will not work because the attacker used openssl to encrypt the file which makes use of additional features to encrypt. In order to retrieve all of the data after decryption, we will also need to make use of openssl!
I had made a simple bash script to help with this:
read -p "Enter encryption key: " key
openssl enc -d -aes-128-cbc -K $key -iv adc3216ac29201fa484999e823a95e90 -in important_data.pdf.enc > solve.pdf
Since we already had the hex form of the UUID from our c# script, 36393233353330662s376431352s3131, we can pass this in as input to our bash script! Opening up solve.pdf should give us:
Congratulations on completing the 2022 Codebreaker Challenge!
The answer to Task 9 is:
Zq1BibZRQqNYnlCKGGxX2RQjAHvXXq88
BOOYAH!
The correct answer:
Zq1BibZRQqNYnlCKGGxX2RQjAHvXXq88
