CRC’sly was a challenge at Defcon’s Car Hack Village about having a known CRC value and finding something to collide with it. Unfortunately due to the way the challenge was presented on day 1, it was unsolvable. This was due to two issues, first issue: the search space of the flag was too large, 3080 * 3080 * 3080 * 3080 = 89991784960000, which I don’t believe to be able to be brute forced. Second issue: since the CRC was only 16 bits, the amount of collisions was so high, as to not single out any one solution. I spent a long time on day one coming to this conclusion. So on day two, the challenge description was updated with the first three words (in no particular order) of input to the CRC calculation, making the search space reasonable, and eliminating all collisions. Here’s the description:
This is a reverse engineering problem, in TriCore! Can you figure out what is going on under the hood? You might need a unicorn or a multi-headed serpent to help you out. You just have to figure out 4 things!
# Files provided
We are given a file defcon_dump_crc.zip, unzipping it we are greeted with many files.
start_0x10000000_0x10017FFF start_0x50000000_0x50017FFF start_0x80000000_0x802FFFFF start_0xA0300000_0xA05FFFFF
start_0x10018000_0x1001BFFF start_0x50018000_0x5001BFFF start_0x80300000_0x805FFFFF start_0xA0600000_0xA08FFFFF
start_0x100C0000_0x100C17FF start_0x500C0000_0x500C17FF start_0x80600000_0x808FFFFF start_0xAFFF0000_0xAFFFFFFF
start_0x10100000_0x1010FFFF start_0x50100000_0x5010FFFF start_0x80900000_0x80BFFFFF start_0xB0000000_0xB000FFFF
start_0x10110000_0x10117FFF start_0x50110000_0x50117FFF start_0x80C00000_0x80EFFFFF start_0xB0010000_0xB001FFFF
start_0x101C0000_0x101C2FFF start_0x501C0000_0x501C2FFF start_0x8FFF0000_0x8FFFFFFF start_0xB0020000_0xB002FFFF
start_0x30000000_0x30017FFF start_0x60000000_0x6003BFFF start_0x90000000_0x9000FFFF start_0xB0030000_0xB003FFFF
start_0x30018000_0x3001BFFF start_0x6003C000_0x6003FFFF start_0x90010000_0x9001FFFF start_0xB0040000_0xB007FFFF
start_0x300C0000_0x300C17FF start_0x600C0000_0x600C17FF start_0x90020000_0x9002FFFF start_0xB0080000_0xB00BFFFF
start_0x30100000_0x3010FFFF start_0x60100000_0x6010FFFF start_0x90030000_0x9003FFFF start_0xB00C0000_0xB00FFFFF
start_0x30110000_0x30117FFF start_0x60110000_0x60117FFF start_0x90040000_0x9007FFFF start_0xB0100000_0xB010FFFF
start_0x301C0000_0x301C2FFF start_0x601C0000_0x601C2FFF start_0x90080000_0x900BFFFF start_0xB0110000_0xB011FFFF
start_0x40000000_0x40017FFF start_0x70000000_0x7003BFFF start_0x900C0000_0x900FFFFF start_0xB0400000_0xB040FFFF
start_0x40018000_0x4001BFFF start_0x7003C000_0x7003FFFF start_0x90100000_0x9010FFFF start_0xB0410000_0xB041FFFF
start_0x400C0000_0x400C17FF start_0x700C0000_0x700C17FF start_0x90110000_0x9011FFFF start_0xC0000000_0xC00C0000
start_0x40100000_0x4010FFFF start_0x70100000_0x7010FFFF start_0x90400000_0x9040FFFF start_0xD0000000_0xD00C0000
start_0x40110000_0x40117FFF start_0x70110000_0x70117FFF start_0x90410000_0x9041FFFF start_regs.txt
start_0x401C0000_0x401C2FFF start_0x701C0000_0x701C2FFF start_0xA0000000_0xA02FFFFF
This is a lot, and we are provided with a start_regs.txt file. This line is of note
{name: "PC", unit: "CPU", value: 0x80006564, core: 0}
Upon double checking the TriCore reference manual, we can see that the PC register is the program counter, which is where execution will start.
# Ghidra
We can load the start_0x80000000_0x802FFFFF file into Ghidra, specifying the base of 0x80000000 and architecture to tricore | default | 32 | little | default.
We can now navigate to 0x80006564 in Ghidra and define this location as a function. The decompilation view is this:
void FUN_80006564(void)
{
bool bVar1;
undefined4 uVar2;
char *pcVar3;
int iVar4;
char *pcVar5;
char flag_buf [32];
undefined *local_8;
uVar2 = _DAT_70004004;
local_8 = &DAT_80000028;
pcVar3 = flag_buf;
iVar4 = 0x1f;
pcVar5 = s_AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA_8000002c;
do {
*pcVar3 = *pcVar5;
bVar1 = iVar4 != 0;
pcVar3 = pcVar3 + 1;
iVar4 = iVar4 + -1;
pcVar5 = pcVar5 + 1;
} while (bVar1);
flag_buf[0] = '\0';
FUN_800000c4(flag_buf,s_FLAG{_80000020);
FUN_800000c4(flag_buf,uVar2);
FUN_800000c4(flag_buf,uVar2);
FUN_800000c4(flag_buf,uVar2);
FUN_800000c4(flag_buf,uVar2);
FUN_800000c4(flag_buf,local_8);
FUN_800064c6(flag_buf,0x1f);
return;
}
We see a reference to DAT_70004004 so lets load that region into Ghidra as well. Loading the start_0x70000000_0x7003BFFF the same way as before. This is accomplished by File -> Add to program.
DAT_70004004 Is now cleared up after re-running Ghidra’s analysis. We see this is a pointer table to a long list of 3080 different strings. So uVar2 contains this value.
The function FUN_800000c4 is called 6 times, so it’s important to figure out what its doing. I have cleaned up and commented the code.
void FUN_800000c4(char *buffer,char *j)
{
int i;
char *buf_cpy;
buf_cpy = buffer;
/* find the null terminated end of buffer 1 */
for (i = 0; buffer[i] != '\0'; i = i + 1) {
buf_cpy = buffer + i + 1;
}
/* copy bytes from buffer 2 to end of buffer 1 */
for (; *j != '\0'; j = j + 1) {
*buf_cpy = *j;
buf_cpy = buf_cpy + 1;
}
/* cap with a null */
*buf_cpy = '\0';
return;
}
We can see this is strcat. So we are concatenating 6 different values to the flag_buf. This results in the string FLAG{rainyrainyrainyrainy}\x00\x41\x41\x41\x41, note the hex characters at the end. This is caused by the do { ... } while(...) loop in the main function. The buffer of 31 A’s is copied to flag_buf from pcVar5 and the \x41 are caused by not writing enough characters to this buffer. Apparently this was also unintentional, after talking to the challenge creator.
The last function to check is FUN_800064c6(flag_buf, 0x1f) so lets pull it up.
void FUN_800064c6(int param_1,uint param_2)
{
uint uVar1;
if (DAT_70004000 == '\0') {
FUN_80006516();
}
if (param_1 != 0) {
for (uVar1 = 0; uVar1 < param_2; uVar1 = uVar1 + 1) {
}
}
return;
}
Unfortunately, Ghidra fails to produce valid pseudo code for this function, and the function at FUN_80006516 seems to be setting up some kind of table, its not very important to understand this.
void FUN_80006516(void)
{
uint uVar1;
uint uVar2;
uint uVar3;
uint uVar4;
uint uVar5;
for (uVar2 = 0; uVar2 < 0x100; uVar2 = uVar2 + 1) {
uVar1 = 0;
uVar3 = uVar2;
for (uVar4 = 0; uVar4 < 8; uVar4 = uVar4 + 1) {
uVar5 = uVar1 ^ uVar3;
uVar1 = (int)uVar1 >> 1;
if ((uVar5 & 1) != 0) {
uVar1 = uVar1 ^ 0xa001;
}
uVar3 = (int)uVar3 >> 1;
}
(&DAT_70007e80)[uVar2] = (short)uVar1;
}
DAT_70004000 = 1;
return;
}
Of note however, is the 0xa001 constant, after a quick search, we find this link, giving us a CRC name of CRC16_ARC. Lets assume that the function at FUN_800064c6 is this CRC calculation.
Looking back at the main function disassembled view, directly after the call to our CRC function, there is a check made on the return value.
80006606 bb e0 6b mov.u d15,#0xd6be
fd
8000660a 7e 22 jne d15,d2,LAB_8000660e
So we want some value FLAG{val1 + val2 + val3 + val4} + \x00\x41\x41\x41\x41.
At this point, we headed back to the hotel and kept working. The challenge description was later updated to give the hint that the first three words are spoon, scary, asked in no particular order. So we need the flag to contain those words, and equal 0xd6be.
# Solving
First, we need to extract all the strings from the file. The string table is located at 0x80000484 and we can simply copy and paste it out of there to a file words.txt.
We can then quickly code up a python brute force to try all possible combinations. That code follows:
import fastcrc
from itertools import permutations
with open('words.txt','rb') as fd:
dat = [x.strip() for x in fd.readlines()]
base = b'FLAG{'
lst = [b'spoon',b'scary',b'asked']
perms = permutations(lst, 3)
start = time.time()
for words in perms:
for word1 in dat:
attempt = base + words[0] + words[1] + words[2] + word1 + b'}' + b'\x00\x41\x41\x41\x41'
h = fastcrc.crc16.arc(attempt)
if h == 0xd6be:
print(attempt)
Running this file quickly gets us FLAG{scaryspoonaskedquite}\x00AAAA, and there is our flag.