DARPA Shredder Challenge 2011

December 09, 2011 at 12:35 PM | categories: aktenvernichtung

In diesem Jahr veranstaltete die Defense Advanced Research Projects Agency (DARPA) ein Puzzeln der besonderen Art. Teilnehmer sollten geschredderte Dokumente wieder zusammensetzen. Nicht verwunderlich ist der Hintergrund:

"Today's troops often confiscate the remnants of destroyed documents in war zones, but reconstructing them is a daunting task. [...]The goal was to identify and assess potential capabilities that could be used by our warfighters operating in war zones, but might also create vulnerabilities to sensitive information that is protected through our own shredding practices throughout the U.S. national security community."

Die Formulierung klingt so, als wäre dieses Thema erst jetzt für die Sicherheitscommunity von Interesse. Dem ist natürlich nicht so, denn es gab Anlass genug, über geeignete Aktenvernichtung nachzudenken und Methoden zur automatischen Rekonstruktionzu entwickeln. Unabhänig davon ist es eine interessante Herausforderung aus den Bereichen Informationssicherheit, Bildverarbeitung und Methoden der Künstlichen Intelligenz.

Beispielschnipsel der Darpa Shredder Challenge 2011

Der Wettbewerb bestand aus fünf Runden mit teilweise mehreren Dokumentenseiten, Grafiken, z.T. liniertem und kariertem Papier und rundenverschiedenen Handschriften. Die Seiten wurden einzeln mit einem Cross-Cut-Shredder zerstört und mit 400 dpi eingescannt. In den ersten zwei Runden waren die Papierschnipsel größer und entsprechen etwa der Sicherheitsstufe 3 (nach DIN-Norm) für vertrauliches Schriftgut. Bei den letzten Runden waren die Schnipsel kleiner und entsprechen vom Flächeninhalt grob der Sicherheitsstufe 4 für geheimes Schriftgut.

Einige Teilnehmer haben ihre Ansätze dokumentiert und teilweise auch Programmcode veröffentlicht:

Update: Das Team "All Your Shreds Are Belong to U.S." machte sich bei einem der schwierigen Puzzels kleine gelbe Punkte zunutze, die von vielen Farblaserdruckern auf das Papier gebracht werden. Diese Punkte dienen dem Nachvollziehen von Fälschungen. Hier ermöglichten diese Punkte das Zusammensetzen der Schnipsel zu einem Dokument. Siehe auch Investigating Machine Identification Code Technology in Color Laser Printers.

Radare and the GCHQ's brainteaser

December 02, 2011 at 10:15 PM | categories: reverse engineering, tools

Recently I discovered the tool suite radare, which is a handy tool for analyzing snippets of binary code. You can just open the file containing shell code and disassemble it. Radare works with PE files and ELF binaries. Further, the software supports several machine types like ARM and Intel and allows analyzing code for Dalvik and Java virtual machines.

When I stumbled upon the GCHQs reverse engineering challenge, I noticed the 0x42424242, the 0x41414141 and the not that obvious “deadbeef”. I supposed that it is not a byte wise XOR with a “secret” key, at least not on the full message. The most specific hint for me to inspect the code with radare is the message’s first byte, which is a 0xeb. This is also the first byte on my hard disk and there it represents a jump to the boot loader.

The secret message is given as:

char bytes[] = {
0xeb, 0x04, 0xaf, 0xc2, 0xbf, 0xa3, 0x81, 0xec,
0x00, 0x01, 0x00, 0x00, 0x31, 0xc9, 0x88, 0x0c,
0x0c, 0xfe, 0xc1, 0x75, 0xf9, 0x31, 0xc0, 0xba,
0xef, 0xbe, 0xad, 0xde, 0x02, 0x04, 0x0c, 0x00,
0xd0, 0xc1, 0xca, 0x08, 0x8a, 0x1c, 0x0c, 0x8a,
0x3c, 0x04, 0x88, 0x1c, 0x04, 0x88, 0x3c, 0x0c,
0xfe, 0xc1, 0x75, 0xe8, 0xe9, 0x5c, 0x00, 0x00,
0x00, 0x89, 0xe3, 0x81, 0xc3, 0x04, 0x00, 0x00,
0x00, 0x5c, 0x58, 0x3d, 0x41, 0x41, 0x41, 0x41,
0x75, 0x43, 0x58, 0x3d, 0x42, 0x42, 0x42, 0x42,
0x75, 0x3b, 0x5a, 0x89, 0xd1, 0x89, 0xe6, 0x89,
0xdf, 0x29, 0xcf, 0xf3, 0xa4, 0x89, 0xde, 0x89,
0xd1, 0x89, 0xdf, 0x29, 0xcf, 0x31, 0xc0, 0x31,
0xdb, 0x31, 0xd2, 0xfe, 0xc0, 0x02, 0x1c, 0x06,
0x8a, 0x14, 0x06, 0x8a, 0x34, 0x1e, 0x88, 0x34,
0x06, 0x88, 0x14, 0x1e, 0x00, 0xf2, 0x30, 0xf6,
0x8a, 0x1c, 0x16, 0x8a, 0x17, 0x30, 0xda, 0x88,
0x17, 0x47, 0x49, 0x75, 0xde, 0x31, 0xdb, 0x89,
0xd8, 0xfe, 0xc0, 0xcd, 0x80, 0x90, 0x90, 0xe8,
0x9d, 0xff, 0xff, 0xff, 0x41, 0x41, 0x41, 0x41
};

I just tried to decode it with radare and here it is:

[0x00000000]> eval asm.arch=intel32                                                                                                                                                    
[0x00000000]> pd
.=< 0x00000000, 0 cursor: eb04 jmp 0x6 ; 1 = 0x00000006
| 0x00000002 0 af scasd
| 0x00000003 0 c2bfa3 ret 0xa3bf
| 0x00000003 0 ; ------------------------------------
`-> 0x00000006 256_ 81ec00010000 sub esp, 0x100
0x0000000c, 256 31c9 xor ecx, ecx
.--> 0x0000000e 256 880c0c mov [esp+ecx], cl
| 0x00000011 256 fec1 inc cl
`==< 0x00000013 256 75f9 jnz 0xe ; 2 = 0x0000000e
0x00000015 256 31c0 xor eax, eax
0x00000017 256 baefbeadde mov edx, 0xdeadbeef ; (0xffffffffdeadbeef)
.---> 0x0000001c, 256 02040c add al, [esp+ecx]
| 0x0000001f 256 00d0 add al, dl
| 0x00000021 256 c1ca08 ror edx, 0x8
| 0x00000024, 256 8a1c0c mov bl, [esp+ecx]
| 0x00000027 256 8a3c04 mov bh, [esp+eax]
| 0x0000002a 256 881c04 mov [esp+eax], bl
| 0x0000002d 256 883c0c mov [esp+ecx], bh
| 0x00000030, 256 fec1 inc cl
`===< 0x00000032 256 75e8 jnz 0x1c ; 3 = 0x0000001c
.====< 0x00000034, 256 e95c000000 jmp 0x95 ; 4 = 0x00000095
| 0x00000039 256 89e3 mov ebx, esp
| 0x0000003b 256 81c304000000 add ebx, 0x4
| 0x00000041 248_ 5c pop esp
| 0x00000042 256_ 58 pop eax ; cursor+0x8
| 0x00000043 256 3d41414141 cmp eax, 0x41414141
.=====< 0x00000048, 256 7543 jnz 0x8d ; 5 = 0x0000008d
|| 0x0000004a 264_ 58 pop eax ; cursor+0x8
|| 0x0000004b 264 3d42424242 cmp eax, 0x42424242
.======< 0x00000050, 264 753b jnz 0x8d ; 6 = 0x0000008d
||| 0x00000052 256_ 5a pop edx
||| 0x00000053 256 89d1 mov ecx, edx
||| 0x00000055 256 89e6 mov esi, esp
||| 0x00000057 256 89df mov edi, ebx
||| 0x00000059 256 29cf sub edi, ecx
||| 0x0000005b 256 f3a4 rep movsb
||| 0x0000005d 256 89de mov esi, ebx
||| 0x0000005f 256 89d1 mov ecx, edx
||| 0x00000061 256 89df mov edi, ebx
||| 0x00000063 256 29cf sub edi, ecx
||| 0x00000065 256 31c0 xor eax, eax
||| 0x00000067 256 31db xor ebx, ebx
||| 0x00000069 256 31d2 xor edx, edx
.-------> 0x0000006b 256 fec0 inc al
|||| 0x0000006d 256 021c06 add bl, [esi+eax]
|||| 0x00000070, 256 8a1406 mov dl, [esi+eax]
|||| 0x00000073 256 8a341e mov dh, [esi+ebx]
|||| 0x00000076 256 883406 mov [esi+eax], dh
|||| 0x00000079 256 88141e mov [esi+ebx], dl
|||| 0x0000007c, 256 00f2 add dl, dh
|||| 0x0000007e 256 30f6 xor dh, dh
|||| 0x00000080, 256 8a1c16 mov bl, [esi+edx]
|||| 0x00000083 256 8a17 mov dl, [edi]
|||| 0x00000085 256 30da xor dl, bl
|||| 0x00000087 256 8817 mov [edi], dl
|||| 0x00000089 256 47 inc edi
|||| 0x0000008a 256 49 dec ecx
`=======< 0x0000008b 256 75de jnz 0x6b ; 7 = 0x0000006b
``-----> 0x0000008d 256 31db xor ebx, ebx
| 0x0000008f 256 89d8 mov eax, ebx
| 0x00000091 256 fec0 inc al
| 0x00000093 256 cd80 int 0x80
`----> 0x00000095 256 90 nop
0x00000096 256 90 nop
0x00000097 256 e89dffffff call 0x39 ; 8 = 0x00000039
0x0000009c, 256 41 inc ecx
0x0000009d 256 41 inc ecx
0x0000009e 256 41 inc ecx
0x0000009f 256 41 inc ecx
[0x00000000]>

Update: Heise has details on solving the whole puzzle.

Hello World

December 02, 2011 at 03:25 PM | categories: general

Welcome to my new blog. I will use this blog for IT security related postings, but it is not limited to. Please do not expect frequent updates.

« Previous Page