# Halfpike

**REV 500**

**28 Solves**

**Challenge 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!

[This might come in handy](https://archive.org/details/bitsavers_intelMCS4MProgrammingManualDec73_5215098)

Author: Josh Hofing (@hyperosonic, @trailofbits)

---

The intended solution is to reverse engineer the `chal.rom` which can be disassembled by radare2, but as I am not familiar with the CPU and didn't want to spend too much time reading the manual, I decided to address this problem using a different method..

### Brute force
We could just brute force the flag, but without some tricks this would take way too long, as the execution time increases with the input size and can take several seconds. But we have the code for the emulator. And from the disassembly I know that there are some instructions like:
```
0x0000000f sub r11
0x00000010 jcn 4 0x25
```
And if I would do some input testing I would load the input and the relevant part of the flag in two registers or memory locations and then subtract them. Depending on whether the result is zero, in this case they are equal, I would jump to different code sections. Therefore I just patched the emulator to write the result of each `sub` instruction to stdout.
```
{Opcode::SUB,
[decode_pc](Machine_State &state) {
const auto reg_num = state.rom.at(decode_pc.get()) & 0xf;
// we do the subtract in full-width by adding complements of the
// reg and state, then grab the bits we want from the result
auto result_full = state.acc.get() +
~state.registers[reg_num].get() +
(~state.carry_bit.get() & 0b1);
state.carry_bit = (result_full & 0x10) >> 4;
state.acc = result_full & 0xf;
if (decode_pc.get() == 0xf || decode_pc.get() == 0x83){
printf("%x\n",(state.acc.get()));
}
}},
```
Now I just have to count the number of times `0` is written to stdout when running a test for the next character. The *best* test (the test with the highest amount of `0`) should contain the most similar string. By automating this with a simple and stupid python script we should get the flag!

### Don't give up early
At least in theory and my first attempt was already quite promising..
```
import subprocess
ch = "_{}abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
def fn():
k = ""
for x in range(1,10):
t = k
best = 0
best_c = ''
for j in range(0,len(ch)):
c = t+ch[j]
print("testing: %s" %(c))
cmd = """echo "%s" | ./emu_patched chal.rom""" %(c)
try:
a = subprocess.Popen(['sh','-c',cmd], stdout=subprocess.PIPE)
n = str(a.communicate()[0])
g = n.split('\\n').count('0')
print("score: %d" %(g))
if g > best:
best = g
best_c = ch[j]
except KeyboardInterrupt:
return
except Exception as e:
return
k=k+best_c
fn()
```

I patched the emulator to terminate as soon as `(` is printed to stdout:

```
{Opcode::WRR,
[decode_pc](Machine_State &state) {
// this is technically not *quite* what this instruction is
// supposed to do, but y'know, gotta get io and this does io.
if (state.write_hold.has_value()) {
char c = (state.write_hold->get() << 4) | state.acc.get();
putchar(c);
if(c=='('){
exit(0);
}
state.write_hold = std::nullopt;
} else {
state.write_hold = state.acc;
}
}},
```

And got this after some time:
```
...
score: 101
testing: flag{intl_cpu{_{
score: 102
testing: flag{intl_cpu{_}
score: 102
testing: flag{intl_cpu{_a
score: 101
testing: flag{intl_cpu{_b
score: 101
testing: flag{intl_cpu{_c
score: 102
testing: flag{intl_cpu{_d
score: 101
testing: flag{intl_cpu{_e
score: 101
testing: flag{intl_cpu{_f
```

The idea seems to work, but also seems to break after `cpu` what happened?!

```
...
score: 101
testing: flag{intl_cpu{_{
score: 102
testing: flag{intl_cpu{_}
score: 102
testing: flag{intl_cpu{_a
score: 101
testing: flag{intl_cpu{_b
score: 101
testing: flag{intl_cpu{_c
score: 102
testing: flag{intl_cpu{_d
score: 101
testing: flag{intl_cpu{_e
score: 101
testing: flag{intl_cpu{_f
```

```
testing: flag{intl_cpu_
score: 98
testing: flag{intl_cpu{
score: 99
testing: flag{intl_cpu}
score: 98
testing: flag{intl_cpua
score: 98
testing: flag{intl_cpub
score: 98
testing: flag{intl_cpuc
score: 99
testing: flag{intl_cpud
score: 98
testing: flag{intl_cpue
score: 99
testing: flag{intl_cpuf
score: 98
testing: flag{intl_cpug
score: 99
testing: flag{intl_cpuh
score: 98
testing: flag{intl_cpui
score: 99
testing: flag{intl_cpuj
score: 98
testing: flag{intl_cpuk
score: 99
...
testing: flag{intl_cpus
score: 99
testing: flag{intl_cput
score: 98
testing: flag{intl_cpuu
score: 99
testing: flag{intl_cpuv
score: 98
testing: flag{intl_cpuw
score: 99
testing: flag{intl_cpux
score: 98
testing: flag{intl_cpuy
score: 99
testing: flag{intl_cpuz
score: 98
...
```
There are multiple tests with the score `99` and no test was able to get higher, therefore the first was selected. I tried to debug this problem for some time and tried to understand the disassembly maybe the first part of the flag is checked differently than the last part?! I don't know.

Another team member tried to do a similar thing and counted the instructions and got stuck at the same point. One team member mentioned that the char could be a `s` but I just missed the message and was too frustrated to continue and went on to work on some rwctf challenges.

The day after the submission was closed I got back to finish my work. And let the script run in the background after I removed the upper-case letters and the digits, just to get motivated. After some time I wanted to see how it was doing and saw something like this.

```
testing: flag{intl_cpu{_scare_j
score: 124
testing: flag{intl_cpu{_scare_k
score: 124
testing: flag{intl_cpu{_scare_l
score: 124
testing: flag{intl_cpu{_scare_m
score: 125
testing: flag{intl_cpu{_scare_n
score: 124
testing: flag{intl_cpu{_scare_o
score: 124
```

This was a very frustrating moment. If I would just have waited a bit longer before killing the process, I would have got the flag..
```
testing: flag{intl_cpu{_scare_me}_
score: 129
testing: flag{intl_cpu{_scare_me}{
score: 129
testing: flag{intl_cpu{_scare_me}}
score: 129
testing: flag{intl_cpu{_scare_me}a
score: 129
testing: flag{intl_cpu{_scare_me}b
score: 129
testing: flag{intl_cpu{_scare_me}c
score: 129
testing: flag{intl_cpu{_scare_me}d
score: 129
testing: flag{intl_cpu{_scare_me}e
score: 129
testing: flag{intl_cpu{_scare_me}f
score: 129
testing: flag{intl_cpu{_scare_me}g
score: 129
testing: flag{intl_cpu{_scare_me}h
score: 129
testing: flag{intl_cpu{_scare_me}i
score: 129
testing: flag{intl_cpu{_scare_me}j
score: 129
testing: flag{intl_cpu{_scare_me}k
score: 129
testing: flag{intl_cpu{_scare_me}l
score: 129
testing: flag{intl_cpu{_scare_me}m
score: 129
testing: flag{intl_cpu{_scare_me}n
```

At this point the score won't differ as only 24 characters are checked as far as I know.

Now we can guess the invalid character to get this flag:

`flag{intl_cpus_scare_me}`

**Next time I will be more patient!**