Skip to content

Instantly share code, notes, and snippets.

@Lense
Last active June 29, 2016 15:55
Show Gist options
  • Save Lense/7ed1d8db57950b2de8fc to your computer and use it in GitHub Desktop.
Save Lense/7ed1d8db57950b2de8fc to your computer and use it in GitHub Desktop.
CSAW 2014 quals: weissman (RE300.2) writeup

Extract the key!

Written by RyanWithZombies

Update: The key is not "flag{ don't trust the Cheshire cat!! he works for the Queen of Hearts }". Sorry about that. It's an artifact from an easier version of this challenge. You need to extract key.jpg.

HINT:

CSAWLZ is a completely custom format! You won't find decompressing tools on the internet. We made it just for you. :)

typedef struct _hdr {
    uint8_t magic[8];
    uint32_t version;
    uint32_t num_files;
} hdr;

typedef struct _entry {
    uint32_t magic;
    uint32_t compressed_size;
    uint32_t uncompressed_size;
    uint8_t filename[32];
} entry;
#include<stdint.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct _hdr {
uint8_t magic[8];
uint32_t version;
uint32_t num_files;
} hdr;
typedef struct _entry {
uint32_t magic;
uint32_t compressed_size;
uint32_t uncompressed_size;
uint8_t filename[32];
} entry;
int main()
{
int entryNum, uncompressedLen, compressedOffset, compressedIndex, uncompressedIndex, replaceIndex, numReplaced, replaceLen;
char* compressedBuf;
char* uncompressedBuf;
hdr head;
entry entry;
FILE* fUncompressed;
FILE* f = fopen("weissman.csawlz", "rb");
fread(&head, sizeof(hdr), 1, f);
for(entryNum=0; entryNum<head.num_files; entryNum++)
{
fread(&entry, sizeof(entry), 1, f);
printf("%s\n", entry.filename);
printf("0x%x %u %u\n",
entry.magic, entry.compressed_size, entry.uncompressed_size);
compressedBuf = calloc(entry.compressed_size, sizeof (char));
fread(compressedBuf, sizeof (char), entry.compressed_size, f);
switch(entryNum)
{
case 1:
free(compressedBuf);
continue;
case 0:
fUncompressed = fopen("index.html", "rb");
break;
case 2:
fUncompressed = fopen("alice.txt", "rb");
}
fseek(fUncompressed, 0, SEEK_END);
uncompressedLen = ftell(fUncompressed)*8;
fseek(fUncompressed, 0, SEEK_SET);
uncompressedBuf = calloc(uncompressedLen, sizeof (char));
fread(uncompressedBuf, sizeof (char), uncompressedLen, fUncompressed);
compressedIndex = 0;
uncompressedIndex = 0;
compressedOffset = 0;
while(compressedIndex < entry.compressed_size)
{
if((compressedIndex-compressedOffset)%10 == 0)
{
// Weird compression thing here
uncompressedIndex--;
if(compressedBuf[compressedIndex] != 0x13)
{
printf("//{");
replaceLen = 0;
do
{
replaceLen += compressedBuf[compressedIndex] >> 1;
printf("<len:0x%02x>", compressedBuf[compressedIndex] >> 1);
printf("<0x%08x>",
((compressedBuf[compressedIndex+1]&0xff)<<8) +
(compressedBuf[compressedIndex+2]&0xff));
compressedIndex += 3;
compressedOffset += 3;
}
while(compressedBuf[compressedIndex] != 0x13);
printf("}={");
for(replaceIndex=0; replaceIndex<replaceLen; replaceIndex++)
{
uncompressedIndex++;
printf("%c", uncompressedBuf[uncompressedIndex]);
}
printf("}");
compressedIndex--;
}
printf("|");
}
else
{
// I commented this out for input into Python script to do
// some frequency analysis. It didn't help.
if(uncompressedIndex < entry.uncompressed_size)
printf("%c", compressedBuf[compressedIndex]);
}
compressedIndex++;
uncompressedIndex++;
}
// Guess whether or not these were in the code I wrote during the ctf
fclose(fUncompressed);
free(compressedBuf);
free(uncompressedBuf);
}
fclose(f);
return 0;
}
#include<stdint.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct _hdr {
uint8_t magic[8];
uint32_t version;
uint32_t num_files;
} hdr;
typedef struct _entry {
uint32_t magic;
uint32_t compressed_size;
uint32_t uncompressed_size;
uint8_t filename[32];
} entry;
int main()
{
int entryNum, compressedOffset, compressedIndex, replaceIndex, numReplaced;
int* replaceSizes = calloc(100, sizeof (int));
int* replaceHashes = calloc(100, sizeof (int));
char* compressedBuf;
char* replaceBuf = calloc(9, sizeof (char));
hdr head;
entry entry;
FILE* f = fopen("weissman.csawlz", "rb");
fread(&head, sizeof(hdr), 1, f);
for(entryNum=0; entryNum<head.num_files; entryNum++)
{
fread(&entry, sizeof(entry), 1, f);
compressedBuf = calloc(entry.compressed_size, sizeof (char));
fread(compressedBuf, sizeof (char), entry.compressed_size, f);
switch(entryNum)
{
case 1:
break;
case 0:
case 2:
free(compressedBuf);
continue;
}
compressedIndex = 0;
compressedOffset = 0;
while(compressedIndex < entry.compressed_size)
{
if((compressedIndex-compressedOffset)%10 == 0)
{
// Weird compression thing here
if(compressedBuf[compressedIndex] != 0x13)
{
memset(replaceSizes, 0, 100*sizeof (int));
memset(replaceHashes, 0, 100*sizeof (int));
numReplaced = 0;
do
{
replaceSizes[numReplaced] = compressedBuf[compressedIndex] >> 1;
replaceHashes[numReplaced] =
((compressedBuf[compressedIndex+1]&0xff)<<8) +
(compressedBuf[compressedIndex+2]&0xff);
compressedIndex += 3;
compressedOffset += 3;
numReplaced++;
}
while(compressedBuf[compressedIndex] != 0x13);
for(replaceIndex=0; replaceIndex<numReplaced; replaceIndex++)
{
switch(replaceHashes[replaceIndex])
{
case 0x4f9a:
strncpy(replaceBuf, "DDDDDDDDD", 9);
break;
case 0x4ce3:
strncpy(replaceBuf,
"\x00\x00\x00\x00\x00\x00\x00\x01\x02", 9);
break;
default:
strncpy(replaceBuf, "AAAAAAAAA", 9);
}
while(replaceSizes[replaceIndex]--)
{
printf("%c", replaceBuf[replaceIndex%9]);
}
}
compressedIndex--;
}
}
else
{
printf("%c", compressedBuf[compressedIndex]);
}
compressedIndex++;
}
// Guess whether or not these were in the code I wrote during the ctf
free(compressedBuf);
}
free(replaceSizes);
free(replaceHashes);
fclose(f);
free(replaceBuf);
return 0;
}

###First glance (I didn't look at the challenge until both updates were posted.)
The structs mention compression, and file is named weissman.csawlz, so this challenge must relate to LZ compression. It turns out LZ is the father of many major compression algorithms used today, with many varieties; I wasn't going to find one standard implementation that I could use.
A cursory inspection of a file reveals 0x13 bytes every 10 bytes, with occasional other bytes being garbled. The 0x13 bytes are markers for blocks of data, so after 9 bytes, if the next byte isn't another 0x13, then all of the bytes up until the marker are some compression reference.

###Write some code I then whipped up the bare bones of read.c. I found the html file and the right version of Alice in Wonderland (after fixing newlines and adding the easy flag as mentioned in the update) online, which let me look at what was replaced with what:

|<html>
<h|ead>
<tit|le>Hash F|unctions |and Block| Ciphers<|/title>
<|meta name|="keyword|s" conten|t="hash, |hash func|tion, has|h table l|ookup,
ch|ecksum, c|ipher, bl|ock ciphe|r, stream| cipher, |rng, prng|, random |number">
|</head>
<|body bgco|lor="#fff|fff" text|="#000000|" link="#|0000ff" 
|vlink="#0|0ff00" al|ink="#ff0|000">

<c|enter><h2|>Hash Fun|ctions an|d Block C{<0x0a><0x1e><0x20>}={ipher}||s</h2></c{<0x0c><0xc5><0x6c>}={enter>}||

<p>I ha|ve a lot |of materi|al relate|d to hash|ing.
<UL>|
<LI>Defi|nitions a|nd my off|erings:
 | <UL>
  <|LI><a hre|f="#looku|p">Hash f{<0x12><0xd6><0x73>}={unctions }||for hash |table loo|kup</a>
 | <LI><a h|ref="#cor|rection">|Error Cor{<0x0e><0x02><0x6e>}={rection}|| Codes</a|>
  <LI><|a href="#|checksum"|>Noncrypt|ographic |Checksums|</a>
  <L|I><a href|="nandhas|h.html">A| noncrypt{<0x12><0xdb><0x75>}={ographic }||hardware {<0x08><0x92><0x61><0x12><0x5e><0x0a><0x12><0x5d><0x62>}={hash</a>
  <LI><a href}||="#one-wa|y">One-wa|y functio|ns (crypt{<0x12><0xdb><0x20><0x08><0x92><0x75>}={ographic hash}||
function|s, digita|l signatu|res)</a>
|  <LI><a |href="#bl|ock">Bloc|k Ciphers{<0x12><0x5e><0x68><0x12><0x5d><0x75>}={</a>
  <LI><a href}||="#random|">Random |Number Ge|nerators<|/a>
  <LI|><a href=|"#stream"|>Stream C{<0x0a><0x1e><0x13>}={ipher}||s</a>

I replaced 0x13 markers with ascii |s, and put the compressed data and uncompressed data in {``} pairs.

###Now the hard part Interesting features:

  • Everything is replaced by text occurring at the start of a block.
  • ipher occurs twice, and is replaced by the same 6 bytes each time. This means that it the compression must not use relative references.
  • ipher, enter>, and unctions have wildly different bytes, so the compression probably doesn't use absolute references.
  • That leaves hashes. (Somewhere around this point I started working with Sliden)
  • Expanding the bytes into binary reveals that first byte or so has mostly 0s, while the rest appears evenly distributed.
  • The 8th bit is always 0
  • The first 7 bits are the length of the replaced section. At this point I wasted a significant amount of time reading the website that the html was taken from trying to find the hash that was used.

###Actually solving the challenge It turns out that there are only 23 distinct hashes used in the jpeg, but the jpeg is readable after only fixing the first two.

00000000   13 FF D8 FF  EE 00 0E 41  64 6F 13 62  65 00 64 C0  .......Ado.be.d.
00000010   00 00 00 01  13 FF DB 00  84 00 14 10  10 19 13 12  ................
00000020   19 27 17 17  27 32 26 1F  13 26 32 2E  26 26 26 26  .'..'2&..&2.&&&&
00000030   2E 3E 13 35  35 35 35 35  3E 44 41 41  13 41 41 41  .>.55555>DAA.AAA
00000040   41 44 44 44  44 44 13 44  44 44 44 44  44 44 44 44  ADDDDD.DDDDDDDDD
00000050   7B 3C 6C 65  6E 3A 30 78  30 39 3E 3C  30 78 30 30  {<len:0x09><0x00
00000060   34 66 39 61  3E 3C 6C 65  6E 3A 30 78  30 36 3E 3C  4f9a><len:0x06><
00000070   30 78 30 30  34 66 39 61  3E 7D 13 01  15 19 19 20  0x004f9a>}.....
00000080   1C 20 26 18  13 18 26 36  26 20 26 36  44 36 13 2B  . &...&6& &6D6.+
00000090   2B 36 44 44  44 42 35 42  7B 3C 6C 65  6E 3A 30 78  +6DDDB5B{<len:0x
000000A0   30 39 3E 3C  30 78 30 30  34 66 39 61  3E 3C 6C 65  09><0x004f9a><le
000000B0   6E 3A 30 78  30 39 3E 3C  30 78 30 30  34 66 39 61  n:0x09><0x004f9a
000000C0   3E 3C 6C 65  6E 3A 30 78  30 39 3E 3C  30 78 30 30  ><len:0x09><0x00
000000D0   34 66 39 61  3E 3C 6C 65  6E 3A 30 78  30 39 3E 3C  4f9a><len:0x09><
000000E0   30 78 30 30  34 66 39 61  3E 7D 13 44  44 FF C0 00  0x004f9a>}.DD...
000000F0   11 08 02 C8  13 05 00 03  01 22 00 02  11 01 13 03  ........."......
00000100   11 01 FF C4  00 A1 00 00  13 02 03 01  01 01 00 00  ................
00000110   00 00 13 00  00 00 00 00  00 00 01 02  13 03 05 04  ................
00000120   06 07 01 01  01 01 13 01  01 00 00 00  00 00 00 00  ................
00000130   7B 3C 6C 65  6E 3A 30 78  30 35 3E 3C  30 78 30 30  {<len:0x05><0x00
00000140   34 63 65 33  3E 7D 13 01  02 03 04 10  01 00 02 01  4ce3>}..........

0x4f9a is a block of 0x44 Ds, and 0x4ce3 is 0x000000000000000102, found from trying the possible blocks. Here is the image if you replace every single other compressed block with 0x41 As. write.c is what I wrote to write the file.

###Challenge source Part of the source
Hash algorithm:

unsigned int hash = 0x55aa55aa;
unsigned int i = 0;
 
for(i = 0; i < HASH_LEN; str++, i++)
{
hash ^= ((hash << 5) + (*str) + (hash >> 2));
}
 
return hash & MASK;

Nope, wouldn't have guessed that.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment