Codegate 2014: "Chrono" 300 pts [Hexcellents CTF Wiki]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
= 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:

<code>
$ ./chrono 


He said : 
	import zlib
	zlib.compress(space)
                                              
                                              
                                              
 o                                            
|+|                                           
 !                                           *
[ ]  #########################################
                                              
                                              
                                              
                                              

</code>
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:
<code>
$ ./chrono  <<< "test"

He said : 
	import zlib
	zlib.compress(space)
                                              
                                              
                                              
 o                                            
|+|      #######             ######          *
 !    ###       ###      ####      ###       #
[ ]  #             ######             ####### 
                                              
                                              
                                              
                                              
$ ./chrono  <<< "test"

He said : 
	import zlib
	zlib.compress(space)
                                              
                                              
                                              
 o                                           *
|+|  # # #        # # # # # # #      # # # # #
 !         #######             ######         
[ ]   # # #        # # # # # #        # # # # 
                                              
                                              
                                              
                                              

</code>
It even seems to be non-deterministic. Let's check the code:
{{ :writeups:chrono_1.png?direct&1200 |}} 
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:
{{ :writeups:chrono_2.png?direct&600 |}}
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.
<code python>
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")
</code>

<code>
 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)

</code>

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:
<code>
$ 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)
</code>
Not much activity, if we see it finer grained:
<code>
$ 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)

</code>
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:
<code c>
/*
 * 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.
 ....
 */

</code>

Hmm, STICKY_TIMEOUTS seems promising. Let's check:
<code bash>
 $ 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

</code>
Perfect. Now to run the exploit remotely and get the flag:
<code bash>
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

</code>