Codegate 2014: "Chrono" 300 pts
This was a “logical” challenge on which we wasted quite a lot of time until we got it.
We are given a 64 bit linux binary running remotely. The flag is in a key that we need to somehow access. It's not an exploit task so let's analyze what it does.
Running the given binary leads to this output:
$ ./chrono
He said :
import zlib
zlib.compress(space)
o
|+|
! *
[ ] #########################################
What? The task name is “Chrono”, the category is “logical” and then it talks about space compression. Odd!
A thing to note is that it first waits for our input. If we feed it through a pipe things change:
$ ./chrono <<< "test"
He said :
import zlib
zlib.compress(space)
o
|+| ####### ###### *
! ### ### #### ### #
[ ] # ###### #######
$ ./chrono <<< "test"
He said :
import zlib
zlib.compress(space)
o *
|+| # # # # # # # # # # # # # # #
! ####### ######
[ ] # # # # # # # # # # # # #
It even seems to be non-deterministic. Let's check the code:
A pretty bleak picture, with lots of floating point math operations that didn't fit the screenshot. Note that the program waits on our input using the select() call. If it waits more than 300 seconds it times out and “no hack” is displayed. Looking further into the binary something interesting shows up after walking the call graph and identifying some statically linked functions:
Following some comparisons, the program executes system() on our input. The comparisons are done after the algorithm is run on the number of microseconds passed since the select call returned. So let's check what the values are at the point of comparison after a fixed and controlled time interval has passed.
import gdb; import tempfile; import os; import subprocess gdb.execute("set pagination off") gdb.execute("set confirm off") gdb.execute("file chrono") gdb.execute("b *0x401261") gdb.execute("b *0x401542") seconds = 299 microseconds = 792458 initial = seconds * 1000000 + microseconds for i in range(initial, initial - 1000, -100): gdb.execute("run <<< 'ls'") gdb.execute("set $rax = %s" % i) gdb.execute("continue") gdb.execute("info reg st0 st1") gdb.execute("quit")
gdb -n -x gdb_sc.py
GNU gdb (Gentoo 7.7 vanilla) 7.7
Copyright (C) 2014 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law. Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-pc-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<http://bugs.gentoo.org/>.
Find the GDB manual and other documentation resources online at:
<http://www.gnu.org/software/gdb/documentation/>.
For help, type "help".
Type "apropos word" to search for commands related to "word".
Breakpoint 1 at 0x401261
Breakpoint 2 at 0x401542
Breakpoint 1, 0x0000000000401261 in ?? ()
He said :
import zlib
zlib.compress(space)
o
|+|
!
[ ]
Breakpoint 2, 0x0000000000401542 in ?? ()
st0 -nan(0xc000000000000000) (raw 0xffffc000000000000000)
st1 6.6260690000000002086721906380262226 (raw 0x4001d408c1db0142f800)
Breakpoint 1, 0x0000000000401261 in ?? ()
He said :
import zlib
zlib.compress(space)
o
|+| # # # # # # # # # # # # # *
! ##### ###### ####
[ ] # # # # # # # # # # # # #
Breakpoint 2, 0x0000000000401542 in ?? ()
st0 2525.3148485878577123031618612003513 (raw 0x400a9dd5099eac40a688)
st1 6.6260690000000002086721906380262226 (raw 0x4001d408c1db0142f800)
Breakpoint 1, 0x0000000000401261 in ?? ()
He said :
import zlib
zlib.compress(space)
o
|+| # # ## ## # # # ## # # #*
! # # # # # # # # # # # # # # #
[ ] # # ## # # # ## # # #
Breakpoint 2, 0x0000000000401542 in ?? ()
st0 2524.6057464700394854517639942059759 (raw 0x400a9dc9b12335e7cae4)
st1 6.6260690000000002086721906380262226 (raw 0x4001d408c1db0142f800)
Breakpoint 1, 0x0000000000401261 in ?? ()
He said :
import zlib
zlib.compress(space)
o
|+| ## ## ## ## ## ## #
! # # # # # # # # # # # # # #*
[ ] ## # ## ## ## ## ## #
Breakpoint 2, 0x0000000000401542 in ?? ()
st0 2524.3206295868166133544718832126819 (raw 0x400a9dc5214c7d581e18)
st1 6.6260690000000002086721906380262226 (raw 0x4001d408c1db0142f800)
Breakpoint 1, 0x0000000000401261 in ?? ()
He said :
import zlib
zlib.compress(space)
o
|+| # ### ## ### ### ##
! ## # # # ## # # # # ## #*
[ ] ## ### ## ### ## #
Breakpoint 2, 0x0000000000401542 in ?? ()
st0 2524.168291440625082167059645144036 (raw 0x400a9dc2b1525d9ae73c)
st1 6.6260690000000002086721906380262226 (raw 0x4001d408c1db0142f800)
Breakpoint 1, 0x0000000000401261 in ?? ()
He said :
import zlib
zlib.compress(space)
o *
|+| ### ### ### ### ####
! # # ## ## # ## ## #
[ ] #### ### ### ###
Breakpoint 2, 0x0000000000401542 in ?? ()
st0 2531.8438171687462991954475910461042 (raw 0x400a9e3d80466e791944)
st1 6.6260690000000002086721906380262226 (raw 0x4001d408c1db0142f800)
Breakpoint 1, 0x0000000000401261 in ?? ()
He said :
import zlib
zlib.compress(space)
o *
|+| ### #### #### ####
! # ## ## ## ## ## # ##
[ ] #### ### #### #
Breakpoint 2, 0x0000000000401542 in ?? ()
st0 2524.0086649873737156823949590034317 (raw 0x400a9dc0237de5d63eec)
st1 6.6260690000000002086721906380262226 (raw 0x4001d408c1db0142f800)
Breakpoint 1, 0x0000000000401261 in ?? ()
He said :
import zlib
zlib.compress(space)
o *
|+| ##### #### ####
! # ## ### ## ## ## ##
[ ] #### ##### #####
Breakpoint 2, 0x0000000000401542 in ?? ()
st0 2490.9508475500862392237877429579385 (raw 0x400a9baf36abebb1a248)
st1 6.6260690000000002086721906380262226 (raw 0x4001d408c1db0142f800)
Breakpoint 1, 0x0000000000401261 in ?? ()
He said :
import zlib
zlib.compress(space)
o *
|+| ##### ##### #####
! ## ### ## ### ## ###
[ ] ##### ##### #
Breakpoint 2, 0x0000000000401542 in ?? ()
st0 2523.9258824767876792094511984032579 (raw 0x400a9dbed06a24dbe188)
st1 6.6260690000000002086721906380262226 (raw 0x4001d408c1db0142f800)
Breakpoint 1, 0x0000000000401261 in ?? ()
He said :
import zlib
zlib.compress(space)
o *
|+| ###### ###### ####
! ### ### ### ### ###
[ ] ##### #####
Breakpoint 2, 0x0000000000401542 in ?? ()
st0 2519.1396099073715157956598886812571 (raw 0x400a9d723bd79925bb64)
st1 6.6260690000000002086721906380262226 (raw 0x4001d408c1db0142f800)
An interesing sine wave shows up, and we can see that the comparison is f(time_remaining) < 6.26 . Let's see the trend of the function at each second:
$ gdb -n -x gdb_sc.py | grep st0 st0 -nan(0xc000000000000000) (raw 0xffffc000000000000000) st0 2123.7499899880709151034352544229478 (raw 0x400a84bbfff5807178e0) st0 2135.0238844128988988657624759071041 (raw 0x400a857061d49f448f14) st0 2138.9524177867137320063761762867216 (raw 0x400a85af3d1a6ee106e4) st0 2140.9479791365036422945422600605525 (raw 0x400a85cf2aec2bc92ce8) st0 2142.155239510389747259466730611166 (raw 0x400a85e27bdc6cc2bc7c) st0 2142.9641933104970901169394892349374 (raw 0x400a85ef6d55f6f9b62c) st0 2143.544025509935241124992444383679 (raw 0x400a85f8b45417d5c90c) st0 2143.9799952218932306280407829035539 (raw 0x400a85ffae0f78444874) st0 2144.3197308556500573217817873228341 (raw 0x400a86051d9e1a08a020) st0 2144.5919270966396803501652357226703 (raw 0x400a860978888c1af044) st0 2144.8149023949987954651419386209454 (raw 0x400a860d09d717ff3afc) .... st0 2146.9727113082135421251450679847039 (raw 0x400a862f9039bb939fe8) st0 2146.9730031197693325140107845072635 (raw 0x400a862f916bb8250b48) st0 2146.9732929398356100492151199432556 (raw 0x400a862f929b9e2058a4) st0 2146.9735807887295493401325074955821 (raw 0x400a862f93c972f9b780) st0 2146.9738666864931637690006027696654 (raw 0x400a862f94f53c126eb0) st0 2146.9741506528973307155183647410013 (raw 0x400a862f961efeb92328) st0 2146.9744327074470380267712243949063 (raw 0x400a862f9746c02a3448) st0 2146.9747128693852431524646817706525 (raw 0x400a862f986c858fffc0)
Not much activity, if we see it finer grained:
$ gdb -n -x gdb_sc.py | grep st0 | cut -d'.' -f1 | sort | uniq st0 2064 st0 2072 st0 2082 st0 2094 st0 2103 st0 2109 st0 2114 st0 2118 st0 2121 st0 2123 st0 2125 st0 2127 st0 2128 st0 2130 st0 2131 st0 2132 st0 2133 st0 2134 st0 2135 st0 2136 st0 2137 st0 2138 st0 2139 st0 2140 st0 2141 st0 2142 st0 2143 st0 2144 st0 2145 st0 2146 st0 -nan(0xc000000000000000) (raw 0xffffc000000000000000)
Not too promising. Seems like the only way to pass the comparison is to make it return “nan” but this look like it's impossible. We tried feeding input through pipes, as optimised as possible but we couldn't get it lower than 1 microsecond. Then we took to the source to see if we can attack the problem from a different angle.
Since the libc select() is just a wrapper over the syscall we dive in the kernel source code at http://lxr.linux.no/#linux+v3.13.5/fs/select.c. Even before finding the actual source code of the syscall we see the following comments at the very beginning of the file:
/*
* This file contains the procedures for the handling of select and poll
*
* Created for Linux based loosely upon Mathius Lattner's minix
* patches by Peter MacDonald. Heavily edited by Linus.
*
* 4 February 1994
* COFF/ELF binary emulation. If the process has the STICKY_TIMEOUTS
* flag set in its personality we do *not* modify the given timeout
* parameter to reflect time remaining.
....
*/
Hmm, STICKY_TIMEOUTS seems promising. Let's check:
$ linux64 -h Usage: linux64 [options] [program [program arguments]] Options: -v, --verbose says what options are being switched on -R, --addr-no-randomize disables randomization of the virtual address space -F, --fdpic-funcptrs makes function pointers point to descriptors -Z, --mmap-page-zero turns on MMAP_PAGE_ZERO -L, --addr-compat-layout changes the way virtual memory is allocated -X, --read-implies-exec turns on READ_IMPLIES_EXEC -B, --32bit turns on ADDR_LIMIT_32BIT -I, --short-inode turns on SHORT_INODE -S, --whole-seconds turns on WHOLE_SECONDS -T, --sticky-timeouts turns on STICKY_TIMEOUTS -3, --3gb limits the used address space to a maximum of 3 GB --4gb ignored (for backward compatibility only) --uname-2.6 turns on UNAME26 --list list settable architectures, and exit -h, --help display this help and exit -V, --version output version information and exit For more details see setarch(8). $ linux64 -T $ ./chrono <<< "date" He said : import zlib zlib.compress(space) o |+| ! [ ] voila! Thu Mar 6 01:58:28 EET 2014
Perfect. Now to run the exploit remotely and get the flag:
guest@codegate:~$ cd /home/chrono guest@codegate:/home/chrono$ ls chrono key guest@codegate:/home/chrono$ linux64 -T bash guest@codegate:/home/chrono$ ./chrono <<< "cat key" He said : import zlib zlib.compress(space) o |+| ! [ ] voila! dIfF3rENT_L3VEL_s4me_aNsW3r