# 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 forceWe 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     r110x00000010      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 earlyAt least in theory and my first attempt was already quite promising..```import subprocessch = "_{}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_cfn()```
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: 101testing: flag{intl_cpu{_{score: 102testing: flag{intl_cpu{_}score: 102testing: flag{intl_cpu{_ascore: 101testing: flag{intl_cpu{_bscore: 101testing: flag{intl_cpu{_cscore: 102testing: flag{intl_cpu{_dscore: 101testing: flag{intl_cpu{_escore: 101testing: flag{intl_cpu{_f```
The idea seems to work, but also seems to break after `cpu` what happened?!
```...score: 101testing: flag{intl_cpu{_{score: 102testing: flag{intl_cpu{_}score: 102testing: flag{intl_cpu{_ascore: 101testing: flag{intl_cpu{_bscore: 101testing: flag{intl_cpu{_cscore: 102testing: flag{intl_cpu{_dscore: 101testing: flag{intl_cpu{_escore: 101testing: flag{intl_cpu{_f```
```testing: flag{intl_cpu_score: 98testing: flag{intl_cpu{score: 99testing: flag{intl_cpu}score: 98testing: flag{intl_cpuascore: 98testing: flag{intl_cpubscore: 98testing: flag{intl_cpucscore: 99testing: flag{intl_cpudscore: 98testing: flag{intl_cpuescore: 99testing: flag{intl_cpufscore: 98testing: flag{intl_cpugscore: 99testing: flag{intl_cpuhscore: 98testing: flag{intl_cpuiscore: 99testing: flag{intl_cpujscore: 98testing: flag{intl_cpukscore: 99...testing: flag{intl_cpusscore: 99testing: flag{intl_cputscore: 98testing: flag{intl_cpuuscore: 99testing: flag{intl_cpuvscore: 98testing: flag{intl_cpuwscore: 99testing: flag{intl_cpuxscore: 98testing: flag{intl_cpuyscore: 99testing: flag{intl_cpuzscore: 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_jscore: 124testing: flag{intl_cpu{_scare_kscore: 124testing: flag{intl_cpu{_scare_lscore: 124testing: flag{intl_cpu{_scare_mscore: 125testing: flag{intl_cpu{_scare_nscore: 124testing: flag{intl_cpu{_scare_oscore: 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: 129testing: flag{intl_cpu{_scare_me}{score: 129testing: flag{intl_cpu{_scare_me}}score: 129testing: flag{intl_cpu{_scare_me}ascore: 129testing: flag{intl_cpu{_scare_me}bscore: 129testing: flag{intl_cpu{_scare_me}cscore: 129testing: flag{intl_cpu{_scare_me}dscore: 129testing: flag{intl_cpu{_scare_me}escore: 129testing: flag{intl_cpu{_scare_me}fscore: 129testing: flag{intl_cpu{_scare_me}gscore: 129testing: flag{intl_cpu{_scare_me}hscore: 129testing: flag{intl_cpu{_scare_me}iscore: 129testing: flag{intl_cpu{_scare_me}jscore: 129testing: flag{intl_cpu{_scare_me}kscore: 129testing: flag{intl_cpu{_scare_me}lscore: 129testing: flag{intl_cpu{_scare_me}mscore: 129testing: 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!**