Twitter: @s4tan
Writeup GitHub project: https://github.com/enkomio/Misc/tree/master/Hm0x14Writeup
I'm not used to participate in CTF competition but in this case I personally know the author of this challenge and I consider
her to be very smart, so I decided to give it a try. As I hope to show in this writeup, the challenge is very interesting and not the typical reverse engineering challenge.
Introduction
The challenge file is:
hm0x14.exe
SHA-256:
7cad36c64df33e30673d98e24be4d60c38ba433aa72f8d2bec14f69db4dbf173
It is a C++ application. As first step I run the application to see what it looks like. I have to admit that the author put a lot of effort in making the challenge appealing from a UI point of view. Below an image of the run of the challenge:
Analysis
Before I continue, I have to say that this challenge remained unsolved since its creation. For this reason the author decided to have a talk on
how to solve it. This write up is not based on her presentation.
When you open the file in IDA you can immediately see that the main function is quite big. Taking a look at the decompiled source code we can see that the program initializes a DES provider and then read the resource
Segreto from
4DES which content is displayed in the image below:
Proceeding with the debugging, it is clear that most of the code is in charge for the UI animation. After stepping a bit with the debugger, it will block on the function that reads the input password. After this function, it is easy to trace the program and see which is the function that accepts as first parameter the input password (which is, in this case, the string "1234567890").
00402E97 | 8D8D 50FEFFFF | lea ecx,dword ptr ss:[ebp-1B0] |
00402E9D | 50 | push eax | eax:&L"1234567890"
00402E9E | E8 08F2FFFF | call hm0x14.4020AB |
00402EA3 | 59 | pop ecx | ecx:L"xe"
00402EA4 | 33C0 | xor eax,eax | eax:&L"1234567890"
By decompiling the code we can see that the main goal of this function is to invoke another function that I called
hash_chars and then generates 4 symmetric keys. Since in the video there is a
4DES banner I suspect that this function creates 4 keys that will be used in this new crypto algorithm :)
memset(&v25, 0, 0x20u);
if ( v7 )
v8 = password;
else
v8 = *password;
hash_chars(v8, &v25, v6); ; generate 4DES key buffer (8 byte = 64 bit, a typical DES key length)
if ( *(password + 20) < 8u )
v9 = password;
else
v9 = *password;
hash_chars(v9 + 2 * v6, &v26, v6); ; generate 4DES key buffer (8 byte = 64 bit, a typical DES key length)
if ( *(password + 20) < 8u )
v10 = password;
else
v10 = *password;
hash_chars(v10 + 4 * v6, &v27, v6); ; generate 4DES key buffer (8 byte = 64 bit, a typical DES key length)
if ( *(password + 20) >= 8u )
v3 = *password;
hash_chars(v3 + 6 * v6, &v28, hKey); ; generate 4DES key buffer (8 byte = 64 bit, a typical DES key length)
v11 = v19;
v12 = bcrypt_generate_symmetric_key(v19, &hKey, &v25);
v13 = bcrypt_generate_symmetric_key(v11, &v22, &v26);
v14 = bcrypt_generate_symmetric_key(v11, &v23, &v27);
v15 = bcrypt_generate_symmetric_key(v19, &v21, &v27); ; <----- ?!? (1)
At this point we are not in good luck, since breaking this algorithm seems to be not so easy (just consider that 3DES is still considered a strong algorithm). Let's take a look at the function in charge for creating the key from our password, in the image below I have highlighted the main points:
The loop is executed a number of times that depends on the password length. The meaning of the various circles is:
*
blue circle: read the
ith character of the input password
*
orange circle: this is the main code. It just multiplies the current key value for
0x1F and save only the low DWORD result value (remember this fact).
*
green circle: the value of the blue circle is added to the result
*
read circle: before to return the result in the ESI register, the value is shifted left by 5 (other point to remember)
The code to generate the key from a password can be represented by the following F# code:
let hashChunk(password: String, offset: Int32, rounds: Int32) =
let mutable result = 1UL
for i=0 to rounds-1 do
result <- (result * 0x1FUL) + uint64 password.[i + offset]
(result <<< 5) &&& 0x00000000FFFFFFFFUL
let generateKey(password: String) =
let keys = [
let size = password.Length >>> 2
for i=0 to 3 do
let value = hashChunk(password, i * size, size)
yield BitConverter.GetBytes(value)
]
(keys.[1], keys.[0]) // I'll exaplin later why I only return these two keys
Finally, the decryption of the resource content is done by executing the following code:
Which can be summarized as:
P = D(E(D(E(C, k1), k2), k3), k4)
If during the decryption the application identify an error, the image of the skull is displayed (if you are wondering which skull, watch the first video till the end ^^).
Implementation Errors
Let's take a break to do a recap of the info that we have. Despite the fact that each key is 8 bytes long, only the first 4 bytes are used, so here we have the first error. However, breaking such a keyspace is still not feasible with my laptop.
One of the most important aspect that will help us is pointed out in the decompiled code above with reference (1). I'll rewrite the code below for easy reference:
v12 = bcrypt_generate_symmetric_key(v19, &hKey, &v25);
v13 = bcrypt_generate_symmetric_key(v11, &v22, &v26);
v14 = bcrypt_generate_symmetric_key(v11, &v23, &v27);
v15 = bcrypt_generate_symmetric_key(v19, &v21, &v27);
Do you see it? The last two operations reference the same exact value! By debugging the application we can notice this fact since the first two operations use the same key, invalidating the result. So the effective decryption process is:
P = D(E(D(E(C, k1), k1), k2), k3) = D(E(C, k2), k3)
So we downgraded the algorithm to a 2DES and if you have ever followed a cryptographic course, you know that there is a reason if we jumped from
DES to
3DES by skipping
2DES.
Meet In the Middle
The reason why
2DES is considered not secure is for this specific attack. By quoting wikipedia:
When trying to improve the security of a block cipher, a tempting idea is to encrypt the data several times using multiple keys. One might think this doubles or even n-tuples the security of the multiple-encryption scheme, depending on the number of times the data is encrypted, because an exhaustive search on all possible combination of keys (simple brute-force) would take 2^(n-k) attempts if the data is encrypted with k-bit keys n times.
The MITM is a generic attack which weakens the security benefits of using multiple encryptions by storing intermediate values from the encryptions or decryptions and using those to improve the time required to brute force the decryption keys. This makes a Meet-in-the-Middle attack (MITM) a generic space–time tradeoff cryptographic attack.
The MITM attack attempts to find the keys by using both the range (ciphertext) and domain (plaintext) of the composition of several functions (or block ciphers) such that the forward mapping through the first functions is the same as the backward mapping (inverse image) through the last functions, quite literally meeting in the middle of the composed function. For example, although Double DES encrypts the data with two different 56-bit keys, Double DES can be broken with 2^57 encryption and decryption operations.
Since we know that our key is 32 bit long we can break this encryption with 2^37 operations. Nice... in theory. I don't know about you, but my laptop is still not so powerful to break such a keyspace. There must be some other way to downsize the key.
Indeed, there is! If you take another look at the function that generates the key from a password you will notice that the final result is left shifted 5 times, this means that the least 5 important bits are always zero! With this information we can downgrade the key from 32 bit to 27 bit!
At this point I started to implement the algorithm, but 27 bit are still too much for my laptop. I have to confess that I was stuck at this point. Talking with the author, she told me that there is still a way to downgrade the key size from 27 to 24 bits.
I struggled a bit on this part, until I realized, the parity bit! It is pretty know that
DES uses a key of 64 bits but the effective size is 56 bits. This is due to the fact that the last bit is used as parity bit and it is not consider in the encryption process. Since we have 3 full bytes (the last one is shifted by 5 so doesn't count), by removing 1 bit from each byte we reach the final size of 24 bits.
Finding the plaintext
At this point we have in place the theory and the feasibility of the attack but we miss one last piece, the plaintext to encrypt. Unfortunately the program doesn't seem to give any hints on the format of the plaintext, so I decided to take another look at the program. As every experienced reverse engineering in the world would do, I run the most sophisticated analysis, I run
strings on the binary. I discovered some interesting strings like:
"Scrivi il messaggio e premi INVIO, control Z, INVIO... "
"Inserisci la password SEGRETA e premi INVIO!! "
"Stai per creare un messaggio segreto con"
those strings were effectively referenced in the binary. By taking a look at the referencing code I discovered that if the binary doesn't found the encrypted resource, it enters in another state and allows to create a secret message. So I removed the resource and started the program again. The image below show how to create a secret message.
Since I created a new protected message I'm finally able to see which is the screen displayed to the user when a message is correctly decrypted. From this screen I can see that the first 8 bytes are always the same and their value is: "
Oggetto:". Finally we have all the missing pieces of our puzzle.
Break the rule!
We reached the end of the writeup, let's do a quick recap of the attack:
P = D(E(C, k2), k3) => E(P, k3) = E(C, k4) =>
E("Oggetto:", k3) = E("\xA8\xEC\xE8\x6E\x9D\xB5\xE1\xB7", k4)
I have to compute the two parts for each k3 and k4 until I found two keys that generates the same value.
So, the implementation of the Meet In The Middle attack is composed of two steps, in the first part I encrypt the plaintex with all keys from the 24 bit keyspace and save the result and the key. Then I proceed to encrypt the ciphertext with each possible key and try to find a match with the first step. If a match is found I broke the encryption.
On my laptop it took a while to complete. In the following result you can see the execution of the first step of the attack:
-=[ Start encrypt plaintext: 6/6/2019 2:54:27 PM ]=-
Start iteration 0 of 7 at 6/6/2019 2:54:27 PM
Start iteration 1 of 7 at 6/6/2019 3:07:01 PM
Start iteration 2 of 7 at 6/6/2019 3:18:45 PM
Start iteration 3 of 7 at 6/6/2019 3:32:16 PM
Start iteration 4 of 7 at 6/6/2019 3:45:15 PM
Start iteration 5 of 7 at 6/6/2019 3:58:26 PM
Start iteration 6 of 7 at 6/6/2019 4:10:37 PM
Start iteration 7 of 7 at 6/6/2019 4:22:27 PM
-=[ End encrypt plaintext: 6/6/2019 4:34:14 PM ]=-
And here is the second part of the attack where you can see that the password was successfully bruteforced:
-=[ Populate storage from pre-built table: 6/6/2019 5:56:37 PM ]=-
-=[ Start identify key: 6/6/2019 5:58:03 PM ]=-
Start iteration 0 of 7 at 6/6/2019 5:58:03 PM
Start iteration 1 of 7 at 6/6/2019 6:01:58 PM
Encrypt Password found: 20-8A-34-40-00-00-00-00
Decrypt Password found: 80-A0-DE-1C-00-00-00-00
-=[ End identify key: 6/6/2019 6:08:43 PM ]=-
-=[ Secret message: 6/6/2019 6:08:47 PM ]=-
Oggetto: Finché la barca va.
Quell'augel d'ebano, allora, così tronfio e pettoruto
tentò fino ad un sorriso il mio spirito abbattuto:
«Sebben spiumato e torvo, - dissi, - un vile non sei tu
certo, o vecchio spettral corvo della tenebra di Pluto?
Quale nome a te gli araldi dànno a corte di Re Pluto?»
Disse il corvo allor: «HM{2005d05af414ac92a3ffc5beecbd94f4}!».
PS: questo «4DES» non mi sembra molto sicuro. ho dei seri dubbi sull'algo-
ritmo di hashing della password, e comunque quando si implementa un algorit-
mo non standard si rischia sempre di fare degli erroi grossolani. anche ba-
nali errori di copia-incolla possono essere fatali per la sicurezza. E poi
il logo è così lento a disegnarsi! Troviamo un'alternativa?
Once that I retrieve the keys I'm able to decrypt the text and visualize the FLAG (which is HM{2005d05af414ac92a3ffc5beecbd94f4}), as can be seen from the following video:
Conclusion
This challenge was very entertaining, not because of the reversing part (that was pretty easy to be honest) but because was built with the idea to show how difficult is to implement a new cryptographic algorithm by demonstrating how a real world attack works.
Side Note
The challenge is full of funny comments having joke of hackers. The author told me that she created this challenge by considering a middle-aged developer.
The final message is an excerpt from the poem "The Raven" where the quote "Nevermore" was replaced with the MD5 of "Barbra Streisand" (the actual CTF flag value). This is a tribute to a meme that was popular at that time (actually I didn't realize this thing, it was the author that told me to search for that MD5).
Source Code
The full source code is on my
Github account, I report here just the most important parts to break the encryption (for an updated version please visit the Github website).
namespace Hm0x14Writeup
open System
open System.Text
open System.IO
open System.Collections.Generic
open System.Reflection
module Program =
let mangleKey(k0: Int32, k1: Int32, k2: Int32, k3: Int32) = [|
byte k0 <<< 5
byte k1 <<< 1
byte k2 <<< 1
byte k3 <<< 1
0uy
0uy
0uy
0uy
|]
let getKeys() = seq {
for i0=0 to 0x7 do
Console.WriteLine("Start iteration {0} of 7 at {1} ", i0, DateTime.Now)
for i1=0 to 0x7F do
for i2=0 to 0x7F do
for i3=0 to 0x7F do
yield (mangleKey(i0, i1, i2, i3))
}
let buildEncryptedTextTable(plainText: Byte array, storage: Dictionary<String, Byte array>) =
Console.WriteLine("-=[ Start encrypt plaintext: {0} ]=-", DateTime.Now)
Utility.getKeys()
|> Seq.iter(fun key ->
try
let encryptedBuffer = Encryption.encrypt(plainText, key)
storage.[BitConverter.ToString(encryptedBuffer)] <- key
with _ -> ()
)
Console.WriteLine()
Console.WriteLine("-=[ End encrypt plaintext: {0} ]=-", DateTime.Now)
Console.WriteLine()
let populateStorage(storage: Dictionary<String, Byte array>) =
if not <| Storage.storageExists() then
let plainText = Encoding.UTF8.GetBytes("Oggetto:")
buildEncryptedTextTable(plainText, storage)
Storage.saveEncryptedText(storage)
Storage.loadEncryptedText(storage)
let findKey(encryptedText: Byte array, storage: Dictionary<String, Byte array>) =
Console.WriteLine("-=[ Start identify key: {0} ]=-", DateTime.Now)
let mutable (encKey, decKey) = (Array.empty<Byte>, Array.empty<Byte>)
Utility.getKeys()
|> Seq.iter(fun key ->
try
let encryptedBuffer = Encryption.encrypt(encryptedText, key) |> BitConverter.ToString
if storage.ContainsKey(encryptedBuffer) then
encKey <- storage.[encryptedBuffer]
decKey <- key
Console.WriteLine("Encrypt Password found: " + BitConverter.ToString(storage.[encryptedBuffer]))
Console.WriteLine("Decrypt Password found: " + BitConverter.ToString(key))
Console.ReadLine() |> ignore
with _ -> ()
)
Console.WriteLine()
Console.WriteLine("-=[ End identify key: {0} ]=-", DateTime.Now)
Console.WriteLine()
(encKey, decKey)
let getCipherText() =
let curDir = Path.GetDirectoryName(Assembly.GetEntryAssembly().Location)
File.ReadAllBytes(Path.Combine(curDir, "4DES_SEGRETO"))
[<EntryPoint>]
let main argv =
let storage = new Dictionary<String, Byte array>()
populateStorage(storage)
// decrypt the cipher text
let ciphertext = getCipherText()
let (encKey, decKey) = findKey(ciphertext.[0..7], storage)
// print the cipherText
let secretMessage = Encryption.twoDesDecrypt(encKey, decKey, ciphertext)
Console.WriteLine(secretMessage)
0
