halfpike

by ice

Points: 500 (27 Solves)

Description:

Ah, the 70’s, a time of love, rock and roll, and the emergence of the microprocessor. At that time, a young upstart company by the name of Intel was doing a contracting job to keep the lights on, and they created an interesting little chip: the Intel 4004. Today, we’ve mostly forgotten that cute little CPU’s legacy, so it might be good for us all to have a little reminder about how innovative it was!

Given: challenge.zip

Solution:

TLDR

  1. Side-channel in number of executed instructions allows one to find the correct input

Attack

Description

We are given a ROM file with a program written for an Intel 4004 processor. We are not supposed to run that directly but rather with an emulator which is also given to us. Soon enough we realized that there was a pattern in the number of instructions that the emulator performed when we provided a mixture of inputs, some with correct parts of the flag and some with incorrect.

For instance, feeding flag{AAAAAAAAAAAAAAAAAA} to the emulator would execute x instructions and feeding either flag1AAAAAAAAAAAAAAAAAA} or flag2AAAAAAAAAAAAAAAAAA} would both execute y instructions. This means that we probably have a side-channel on the number of executed instructions that we can use to find the input that the program expects.

Exploit

finalFlag = flag #Initially all set to 'A's

for each c in flag
	results = {}
	for each poss in printableChars
		set c to poss in flag
		results[c] = get_number_inst(flag)
	
	poss = getSpecialPoss(results) #Explained below
	if poss is not None:
		set c to poss in finalFlag

So how do we recognize correct possibilities? That is, what does the getSpecialPoss function do?

It checks if there is one and only one possibility to be the only to execute a certain number of instructions and returns that one. Otherwise, it returns None.

To clarify, if half of the possibilities executed 10000 instructions, the other half except one executed 10100 and one of them executed 10200, then that last possibility is the correct one. If an input looks “special”, then its probably the correct one ;)

This simple script allows to find almost all characters of the flag: flag{intl_cp???scare_me}.

Its easy enough to guess the rest.

Flag: flag{intl_cpus_scare_me}

Resources:

Exploit in solve.py.