Fall 2014
CODEBREAKER CHALLENGE 2.0
1
Challenge Scenario
“An international terrorist organization has recently
revised the operational security (OPSEC) procedures
used to communicate with their members in the field.
We have recovered a program that we believe is
being used to covertly send encrypted messages. On
the surface, the program appears to simply check the
weather forecast in a few cities, but we believe there
is more to the program than meets the eye. Your
mission is to figure out how to execute the covert
functionality, reverse-engineer the encryption
algorithm, create a decryption program, and lastly
figure out a way to decipher a message that was
captured from a high-value target.”
2
The Challenge
There are 4 different levels or "tiers" to this
challenge problem
Tier 1: Determine how to execute the hidden
functionality
Tier 2: Bypass an authentication check
Tier 3: Create a decryption program
Tier 4: Decrypt message from a high-value target
Each tier gets progressively harder and builds
off lower tiers
3
The Challenge (cont.)
The program will provide you with directions
for where to send an encrypted email after
you complete Tier 3
Please use your *.edu address so we know you are
a student
You will then be sent the encrypted message for
Tier 4
Solutions are due by the end of 2014
4
Getting Started
Review the ‘Getting Started’ tips in the
Codebreaker Challenge document
Download the IDA Demo from Hex-Rays
https://www.hex-
rays.com/products/ida/support/download_demo.h
tml
Try running the program with different
options and observe its behavior
Disassemble and start analyzing the binary
5
Reverse Engineering Tips
Examine strings in the binary using IDA
Look for clues that relate to the functionality you are trying
to find / reverse
Utilize IDA xrefs to find code that references the string(s) of
interest
Utilize symbols (e.g., function names) to help determine
what a section of code does
Try setting debugger breakpoints to help RE code
Single-step after hitting a breakpoint and see how the
values in registers/memory change
Look for the result of interesting computations. You can
sometimes get the data you need from memory
Leverage online resources, e.g.,Intel manuals, RE
lectures, etc. for help on reverse-engineering
6
Reverse Engineering Tips
Optimizing compilers sometimes generate
strange looking code for simple operations
In this challenge, you will encounter one such
optimization during Tiers 2 – 4
To save you some time/frustration, we will
walk through an example and explain the
math behind the optimization
7
What does this code do?
mov edx, 0xAC769185 // edx = 0xAC769185
mov eax, ecx // ecx = input value
imul edx // edx:eax = eax * edx
lea eax, [edx + ecx*0x1]// eax = edx + ecx
mov edx, eax // edx = eax
sar edx, 0x6 // arith right shift; edx = edx >> 0x6
mov eax, ecx // eax = ecx
sar eax, 0x1f // eax = eax >> 0x1f (31)
mov ebx, edx // ebx = edx
sub ebx, eax // ebx = ebx - eax
mov eax, ebx // eax = ebx
imul eax, eax, 0x5f // edx:eax = eax * 0x5f (95)
mov edx, ecx // edx = ecx
sub edx, eax // edx = edx – eax
// edx is the final result
8
Signed Division and Remainder
The code computes: edx = ecx % 95
Why multiply by 0xAC769185 and where did that
number come from?
Division is a time consuming operation
When the divisor is a constant, the compiler can
optimize the computation
The basic trick is to multiply by a “magic value”
(~ 232/d) and extract the leftmost 32 bits of the
product
The following site computes these numbers for
you: http://www.hackersdelight.org/magic.htm
9
Signed Division and Remainder
For wordsize W ≥ 3 and divisor d, 2 ≤ d <
2𝑊−1 , we wish to find the least integer m and
p such that:
𝑚𝑛 𝑛
= for 0 ≤ n < 2𝑊−1 (1a)
2𝑝 𝑑
𝑚𝑛 𝑛
+1= for −2𝑊−1 ≤ n ≤ −1 (1b)
2𝑝 𝑑
with 0 ≤ m < 2𝑊 and p ≥ 𝑊
10
Signed Division and Remainder
The “magic number” M used in the multiply
instruction is given by:
𝑚, 𝑖𝑓 0 ≤ 𝑚 < 2𝑊−1
𝑀=
𝑚 − 2𝑊 , 𝑖𝑓 2𝑊−1 ≤ 𝑚 < 2𝑊
Because (1b) must hold for 𝑛 = −𝑑,
−𝑚𝑑
+ 1 = −1, which implies
2𝑝
𝑚𝑑
>1 (2)
2𝑝
11
Signed Division and Remainder
Let 𝑛𝑐 be the largest value of n such that
rem(𝑛𝑐 , d) = d-1. It can be calculated from:
2𝑊−1
𝑛𝑐 = ∗d−1
𝑑
= 2𝑊−1 − 𝑟𝑒𝑚 2𝑊−1 , 𝑑 − 1 (3)
Because (1a) must hold for 𝑛 = 𝑛𝑐 :
𝑚𝑛𝑐 𝑛𝑐 𝑛𝑐 −(𝑑−1)
= = or
2𝑝 𝑑 𝑑
𝑚𝑛𝑐 𝑛𝑐 +1
< (4)
2𝑝 𝑑
12
Signed Division and Remainder
Combining (4) with (2) gives:
2𝑝 2𝑝 𝑛𝑐 +1
<𝑚< (5)
𝑑 𝑑 𝑛𝑐
Because 𝑚 is to be the least integer satisfying
2𝑝
(5), it is the next integer greater than :
𝑑
2𝑝 +𝑑−𝑟𝑒𝑚(2𝑝 ,𝑑) 2𝑝
𝑚= = +1 (6)
𝑑 𝑑
2𝑝 > 𝑛𝑐 (𝑑 − 𝑟𝑒𝑚 2𝑝 , 𝑑 ) (7)
13
Signed Division and Remainder
Algorithm to find 𝑀 and shift amount 𝑠 from 𝑑
Compute 𝑛𝑐 using (3)
Solve for 𝑝 by trying successively larger values,
starting at 𝑊, until satisfying the inequality in (7)
When the smallest 𝑝 ≥ 𝑊 satisfying (7) is found,
𝑚 is calculated from (6)
The shift amount is computed as: 𝑠 = 𝑝 − 𝑊
𝑀 is simply a reinterpretation of 𝑚 as a signed
integer
14
64-bit Data Types
Consider the following program:
int main(){
char one = 0x11; // sizeof(char) == 1
char two = 0x22;
int three = 0x33333333; // sizeof(int) == 4
int four = 0x44444444;
long long five = 0x5555555555555555; // sizeof(long long) == 8
long long six = 0x6666666666666666;
printf("8b: %hu 32b: %u 64b: %llu\n", one + two, three + four, five + six);
return 0;
}
15
64-bit Data Types – x86_64
Part 1: Move values onto the stack
mov BYTE PTR [rbp-0x2],0x11
mov BYTE PTR [rbp-0x1],0x22
mov DWORD PTR [rbp-0xc],0x33333333
mov DWORD PTR [rbp-0x8],0x44444444
mov DWORD PTR [rbp-0x20],0x55555555
mov DWORD PTR [rbp-0x1c],0x55555555
mov DWORD PTR [rbp-0x18],0x66666666
mov DWORD PTR [rbp-0x14],0x66666666
16
64-bit Data Types – x86_64
Part 2: Load into registers and compute
mov rax,QWORD PTR [rbp-0x18] // 0x6666666666666666 in rax
mov rdx,QWORD PTR [rbp-0x20] // 0x7777777777777777 in rdx
lea rcx,[rdx+rax*1] // rcx = rax + rdx*1
mov eax,DWORD PTR [rbp-0x8] // 0x44444444 in eax
mov edx,DWORD PTR [rbp-0xc] // 0x33333333 in edx
add edx,eax // edx = edx + eax
movsx esi,BYTE PTR [rbp-0x2] // 0x11 in esi
movsx eax,BYTE PTR [rbp-0x1] // 0x22 in eax
add esi,eax // esi = esi + eax
17
64-bit Data Types – x86
No 64-bit registers
long long five = 0x5555555555555555; // sizeof(long long) == 8
long long six = 0x6666666666666666;
Let’s make it work with 32-bit ones!
18
64-bit Data Types – x86
Part 1: Move values onto the stack (same as x86_64)
mov BYTE PTR [ebp-1],0x11
mov BYTE PTR [ebp-2],0x22
mov DWORD PTR [ebp-8],0x33333333
mov DWORD PTR [ebp-12],0x44444444
mov DWORD PTR [ebp-24],0x55555555
mov DWORD PTR [ebp-20],0x55555555
mov DWORD PTR [ebp-32],0x66666666
mov DWORD PTR [ebp-28],0x66666666
19
64-bit Data Types – x86
Part 2: Load into registers and compute
mov eax,DWORD PTR [ebp-32] // 0x66666666 in eax
mov edx,DWORD PTR [ebp-28] // 0x66666666 in edx
add eax,DWORD PTR [ebp-24] // eax = eax + 0x55555555
adc edx,DWORD PTR [ebp-20] // edx = edx + 0x55555555 + CF
…
mov eax,DWORD PTR [ebp-12] // 0x444444 in eax
add eax,DWORD PTR [ebp-8] // eax = eax + 0x33333333
…
movsx edx,BYTE PTR [ebp-1] // 0x11 in edx
movsx eax,BYTE PTR [ebp-2] // 0x22 in eax
lea eax,[edx+eax] // eax = edx + eax*
20
Questions
21
Technical Walkthrough
Original Codebreaker Challenge
Released during Fall 2013
Reverse-engineering / crypt challenge
Program prompted for a password
AES key is derived from SHA256 hash of password
AES-encrypted blob w/ instructions for how to submit the
solution stored in the executable
To verify the correct password was entered, the derived key is
used to compute an HMAC of the encrypted blob
If HMAC is correct, the blob is decrypted, revealing
instructions.
Weakness of the design is in the key-derivation function
Only first 2-bytes of SHA256 hash matter
Easy to brute force
22
Running the program
23
Running the program (2)
24
Disassemble
Disassemble the Codebreaker binary
If asked whether you want to use Proximity View
Click no
Use graph view
25
Disassemble (2)
26
Disassemble (3)
27
Observe Strings
Observe the strings that show up in IDA
Click Views->Open Subviews->Strings
You should see the strings that are displayed when
you run the program
Welcome to the NSA Codebreaker Challenge!
Loading……
To win the challenge, you must be the first to decrypt the code
protected by the password. You are free to use any means at your
disposal to reverse-engineer and/or modify this binary in order to discover
the encryption key. Instructions for submitting you solution will be ‘revealed’
when you are successful…good luck!
Enter Password:
28
Observe Strings (2)
29
Observe Strings (3)
30
ACCESS DENIED
Double click on the “ACCESS DENIED\n”
string
This takes you to the data section of the binary
where the string is stored
To the right of the string are cross references
to this address (show up as DATA XREF in
IDA)
Press ctrl-x to pull up a cross-references
window; you will see two different references
31
ACCESS DENIED (2)
32
ACCESS DENIED (3)
33
Double-click Reference
You should now be looking at disassembled
x86 code
We just leveraged the fact that in order to print
the ACCESS DENIED message to the screen, the
code had to reference the address in the data
section of the program where the string was
stored.
Using xrefs in IDA is a quick and easy way to
find interesting code sections
34
Double-click Reference (2)
35
Explore Code Block
Explore the code block preceding the access
denied message (note: you can double-click call statements to visit the function body)
You will see routines to:
print the initial welcome screen,
prompt the user for the password and
compute the password length
The branch for “ACCESS DENIED” is taken
when the strlen of the password is 0.
36
Explore Code Block (2)
37
Explore Code Block (3)
38
Explore Code Block (4)
39
Explore Code Block (5)
40
Explore Code Block (6)
41
Explore Code Block (7)
42
Explore Code Block (8)
43
Explore Code Block (9)
44
Explore Code Block (10)
45
Secure Hash Algorithm
Hash values can be used to verify the
integrity of the data without providing any
means to derive the original data. The
algorithm is irreversible (SHA-2 is implemented in some widely used security
applications and protocols: TLS, SSL, PGP, SSH, S/MIME, Bitcoin and IPsec)
The first call computes the SHA256 hash of
the password
You can figure out that it is a SHA256 by Googling
for some of the large constants that you will find
in the code (0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c,
0x1f83d9ab, 0x5be0cd19)
46
Secure Hash Algorithm (2)
47
Secure Hash Algorithm (3)
48
Secure Hash Algorithm (4)
49
Secure Hash Algorithm (5)
50
AES Key Derivation Routine
AES is a symmetric-key algorithm; same key
is used to encrypt and decrypt the data.
The AES key is being derived from the hash of
the password
Lets take a closer look at what is being done
to the password hash
51
AES Key Derivation Routine (2)
52
AES Key Derivation Routine (3)
53
AES Key Derivation Routine (4)
54
AES Key Derivation
The 16-byte key is derived as follows:
H0, H1, …, H31 represents the 32-bytes of the
SHA256 hash
K0, K1, …, K15 are the 16-bytes of key
R0, R1, …, R15 are the 16-bytes of fixed
random data that is in the program
(0x23,0x8e,0x60,0xe1,0xd2,0x96,0x38,0xc7,0xa5,0xc0,0x22,0x74,0x4f,0x31,0x5b,0xcd)
55
AES Key Derivation
• K0 = H1 xor R0
• K1 = H0 xor R1
• K2 = K1 xor R2
• K3 = K0 xor R3
• K4 = K3 xor R4
• K5 = K2 xor R5
• :
• K15 = K12 xor R15
• Looking at the above equations, do you notice any problems?
– How many bytes of the password hash are ultimately used in the
derivation of the key?
– Given this, how many possible AES keys could be derived from this
function?
– Is that something that you can efficiently compute and brute-force?
56
Keyed-Hash Message
Authentication Code
• Following the code you will see that the AES
key is passed to a function that computes the
Keyed-Hash Message Authentication Code
(HMAC) of the cipher text stored in the
program.
• If the computed HMAC-SHA256 matches the
expected HMAC
(0xbc,0xb0,0x78,0x41,0xaa,0xd0,0x06,0x68,0xdd,0xa4,0x74,0x06,0xd7,0x1a,0x2b,0xd2,0x9b,0x0e,0xdb,0x0d,0xf9,0xce,0xf4,
0xa7,0xf9,0x51,0x6c,0x99,0xfc,0xb6,0x95,0xf8)
Then, the AES key is used to decrypt the cipher text
Else, “ACCESS DENIED” message is displayed
57
Keyed-Hash Message
Authentication Code (2)
58
Keyed-Hash Message
Authentication Code (3)
59
Keyed-Hash Message
Authentication Code (4)
60
AES Decryption
61
Brute Force Attack
Leverage the fact that you know the
expected HMAC and you know how to derive
putative key
(0xbc,0xb0,0x78,0x41,0xaa,0xd0,0x06,0x68,0xdd,0xa4,0x74,0x06,0xd7,0x1a,0x2b,0xd2,0x9b,0x0e,0xdb,0x0d
,0xf9,0xce,0xf4,0xa7,0xf9,0x51,0x6c,0x99,0xfc,0xb6,0x95,0xf8)
Write a simple program to brute force the key
and decrypt the ciphertext
The CyaSSL library is easy to use and contains all
the functions that you need (it was used to write
the challenge problem)
62
Brute Force Code
printf("Searching for a solution...\n");
for (i=0; i < (1<<16); i++)
{
memcpy(hashGuess, (uint8_t*)&i, 2);
// Derive the AES key to decrypt secret code
retCode = deriveAESKey(hashGuess, (uint8_t*)AESKey);
// Compute HMAC of ciphertext
computeHMAC(ciphertext, sizeof(ciphertext), AESKey, AES_KEY_SIZE, HMACdigest);
// Compare computed HMAC with expected value
if (memcmp(HMACdigest, HMAC_cipher, SHA256_DIGEST_SIZE) == 0)
{
fprintf(stderr, "FOUND SOLUTION!\n");
fprintf(stderr, "SHA256 Hash of Password -> Byte 1: 0x%x\tByte 2: 0x%x\n", hashGuess[0], hashGuess[1]);
fprintf(stderr, "AES Key: ");
printHexString(AESKey, AES_KEY_SIZE);
printf("\n");
// Decrypt the challenge ciphertext
decrypt(AESKey, plain, sizeof(plain));
printf("%s\n", plain);
}
}
63
Ciphertext
uint8_t ciphertext[] = {0x34,0x3b,0x71,0x62,0xba,0x9f,0x55,0xb8,0xd9,0x88,0x71,0x98,0x24,0x41,0x3e,0x4d,
0xa4,0xbd,0x1a,0xe1,0x2c,0xae,0x2c,0xff,0x1d,0x4e,0x1a,0x9e,0x94,0x8a,0x4d,0x07,
0x71,0x5d,0xc6,0x1f,0xef,0x91,0x09,0x67,0xda,0xfa,0x37,0x96,0x11,0xe1,0x67,0xd6,
0x3e,0xa1,0x5e,0x58,0x0b,0x81,0xdd,0xb2,0xaf,0x5d,0xde,0xde,0x9d,0x82,0xb3,0x72,
0x36,0x86,0xa6,0x72,0xea,0x3e,0x5a,0xa0,0x21,0x4e,0x94,0xbf,0x51,0x12,0xbe,0xfc,
0xb6,0x07,0x3d,0x51,0x36,0xcf,0x76,0x93,0xab,0xc6,0x6c,0x7b,0x5f,0xc8,0x16,0xa2,
0x11,0xc0,0xe6,0x87,0x9e,0xab,0x40,0x56,0xa4,0xb7,0xa5,0x20,0x44,0xbf,0xb0,0xb7,
0x5b,0x43,0x4a,0x02,0x19,0x09,0x1d,0xb2,0x30,0xbb,0x15,0xce,0x1c,0x97,0xd8,0x77,
0xbc,0x42,0x87,0x14,0x93,0x85,0xd2,0x0a,0x7d,0xc4,0x44,0x0e,0x82,0x35,0x3b,0xc4,
0x40,0x78,0x7a,0x59,0xa1,0x59,0x18,0x09,0x22,0x17,0x68,0xc0,0xfc,0x7a,0x5f,0x67,
0x5b,0x2a,0xb3,0xfc,0x53,0xbc,0xe0,0x92,0xff,0x0d,0x84,0x74,0x31,0x1f,0xf5,0x16,
0x4f,0x17,0x50,0x8d,0x95,0x51,0x06,0xf7,0xbc,0xda,0x15,0x05,0x76,0xb5,0x10,0x78,
0xa4,0xa1,0xf1,0x45,0xf1,0x6e,0x78,0x2c,0x3a,0x01,0x4e,0x82,0x68,0x4f,0xe8,0x12,
0x69,0xdd,0x00,0x77,0x17,0xec,0x95,0x76,0xbc,0x8c,0x43,0xc5,0x99,0x53,0xba,0x86,
0x4c,0x6b,0x46,0x4a,0x35,0x82,0xe1,0x10,0xee,0x2a,0x73,0x4d,0x80,0x55,0xdc,0xbc};
64
Brute Force Solution
65
Plaintext
Congratulations! You have successfully
decrypted the challenge cipher.
Please send an email (use your *.edu address)
with a writeup of your solution and the string
bd461a21f932a4130a6f670d to the following
address: _________________________
66
Questions
67
