Oldschool Adventures - Apple II

Challenge description:

We’ve found an Acorn Computers machine from the 80’s, with 32K of RAM. It is working and running BBC Basic, a fantastic programming language. ButcherCorp We found this Rhiza’s Government Server, and we need to access it! It runs an Apple II emulator and accepts codes in Applesoft BASIC. If the result of your code generates a valid QR Code standard (not micro QR), it will be read and the content will be executed as a shell command on the Linux system. A very interesting way to interact with a server, don’t you think?

Follow the directives below:

Maximum size of the payload: 268 chars (it will be truncated at this point)
Send the entire payload in one line (only printable chars), replacing line-break with the symbol § (only 1 allowed)
Only QR Codes are accepted (not micro QR)
Your code can take up to 50 seconds to be drawn, before the QR Code verification occurs
If you have any questions, take a look at the source code of the server inside the container

Writeup

Basically we were tasked with creating a tiny Apple Basic program that wrote a QR code. For the sake of learning, this writeup will include some of our failed attempts at this, and some attemps that were downright stupid (you will know when you see it).

Initial steps:

We started off by trying to find an online emulator that could run apple basic, as it would be easier to run tests that way, but we also managed to get a copy of the compiler, that the actual challenge used, up and running.

Solved in first try.

First attempt was the solve. We basically just used crazy characters and printed them with the program ** ez pz**… not. Turns out, apple basic is not happy about printing crazy characters in the terminal… also the length of this alone was 262 bytes, way too much if we still wanted it to get output to the terminal.

 ▄▄▄▄▄▄▄   ▄▄▄ ▄▄▄▄▄▄▄ 
 █ ▄▄▄ █ ▀▀█▄█ █ ▄▄▄ █ 
 █ ███ █ ▀█  █ █ ███ █ 
 █▄▄▄▄▄█ █ ▄▀▄ █▄▄▄▄▄█ 
 ▄▄▄▄▄ ▄▄▄▀ ▄ ▄ ▄ ▄ ▄  
   ▄▄█▀▄▄▀▀▄▀█▄ ▀▀▄█▄▀ 
 █  ▄▀▀▄██▄▀▀█▀▄▀▄█▀▀▀ 
 ▄▄▄▄▄▄▄ █▀▀▄▀█▄▀▀▀█▄▀ 
 █ ▄▄▄ █ ▄██▄   ▀▀ ▀▀▄ 
 █ ███ █ █ ▄▀█▀█▀▀ █   
 █▄▄▄▄▄█ █ ▀▀█▀▀ █ ▀▄ 

### Attempt number 2

Second attempt had a little more promise in the beginning. We realised that the READ function only needed one DATA to read from, and that we could read 3 values at a time, so HLIN seemed like the solution. Initial test were done with a tiny script:

 1 GR: COLOR=15: DATA 1,2,3,4,5,6,7,8,9: FOR I = 1 TO 3: READ x,y,z: HLIN x,y AT z: NEXT I

This script proved to us that we could just make a huge list with “vectors” that we wanted to draw as horizontal lines.

line = f"1GR:COLOR=15:DATA "
line_started = False
triplets = 0

for y in range(0, len(matrix[0])):
        for x in range(0, len(matrix)):
            # getpix == 1 -> black
            if matrix[y][x] == False and not line_started:
                line += f"{x}"
                line_started = True
            elif matrix[y][x] == True and line_started:
                line += f",{x-1},{y},"
                line_started = False
                triplets += 1
            
            if x == len(matrix[0])-1 and line_started:
                line += f",{x},{y},"
                line_started = False
                triplets += 1

line = line[:-1]
line += f": FOR I = 1 TO {triplets}: READ x,y,z: HLIN x,y AT z: NEXT I"
return line

The above snippet of a script read a matrix of a QR code, and converted it to a command that we could use to draw the QR code in graphics mode as horizontal lines.
The idea was that this would save a ton of space, as the program could use just 3 bytes to draw an entire line!

The only problem was, that we forgot to account for all the times where the program only had to draw a single pixel, it was using a total of 5 bytes to do so, oh and 5 bytes because somehow we forgot to count the fact that the commas are stilly bytes in the program…

The first attempts with this script was very successfull in making a QR code, only issue was that it was above 1000 bytes! (9001 would have been funnier, but also much more sad.)

Third Attempt

This is where it gets WAAAAY worse before it gets better. I take full responsibility for this, and I wanna appologise to my team for making them look at this atrocity:

big_ugly_qr

This was my attempt at making the qr have less gaps between the white lines, as the amount of bytes needed could directly be correlated to how many gaps there were. Don’t ask me how to plot this, cause idfk… SCIENCE!

2²th attempt pt. 1

Finally we had a big breakthrough, when one of our teammates (thank you TCP) found a twitter post made by @deater78. Dieter was found responding to a bot on twitter that accepted Apple Basic Programs, and would then run them, showing the output.

tweeeeeeet

The VERY cryptic program from deater printed a QR code, and only in 275 bytes! This was a big breakthrough, as all that was needed to be done, was reverse engineering some small-ass program, in a language that none of us had seen before. FUN!

Solving the challenge

From here, we had the ground work done, and now we just needed to figure out what was going on.

The program was built in a very fascinating way. It was constructed of a line with a long comment, a couple of loops, and some odd PEEK function as well as a POKE.

1REM________!L%P__??M]]__7T>1___%U6T__?17%]__W74?___!4%P____7____'$JJ___5?=W___")(^__7_Q1___7(1^____E#]__'0PF___]]XU__?11R\__74WY___%UP___??=+___'0!M_______________
2FORY=0TO159:Z=PEEK(2054+Y)-32:FORI=0TO5:Q%=Z/2:POKE50,(Q%*2-Z)*192+255:Z=Q%:IFY+I-164THEN?" ";
4NEXT I,Y:GETA

The thing that caught our eyes, and probably yours too, is the comment on line 1. This comment is insanely log, and seems constructed in a very special way. Looking at the screenshot of twitter above, you can see the output that the program creates. And it seems like the underscores might be directly corresponding to white spots.
This theory was further cooperated when we tried swapping out the first _ with a !.

big change this might be another character, but it is clearly not just white in the top left corner anymore!

This gave us the idea that the characters are directly corresponding to black and white values, but it only seemed like they were responsible for 6 pixels each.

Looking through the code, we realised that the PEEK(2054+Y)-32 (where Y could be 0-159) probably was the memory position of the comment, since the comment is 160 characters long. This means that it grabs the value of each character, and does something with that.

The first something it does, is subtract 32 from the PEEK statement. This basically meant to us, that if it just extracts the charcode from memory and subtracts 32. Looking at the value in binary it is effectively moving the 7th bit to the 6th bit’s place:

01011111 - 00100000 = 00111111 SCIENCE! (or math, idk)

this is for an underscore, so how does it look like for another character?

the char value of " is 34 or in binary 00100010. Doing more SCIENCE! shows that the subtracting 32 from 34 is 2 (00000010).

This is apparently the character used in the above picture, but it is flipped the wrong way, so using some magic (stripping down to only using 6 bits, and flipping it by swapping the endianness) gives 010000

numberthings

This was now just the home stretch. We had figured out how the program worked, and now just had to implement our own version of this with custom QR codes.

Doing this in python proved to be the simplest way.

import qrcode
import pyqrcode
from PIL import Image

def imagetomatrix(image):
    img = Image.open(image)
    matrix_out = []
    for i in range(39):
        matrix_out.append(1)
    for y in range(img.size[1]):
        for i in range(10):
            matrix_out.append(1)
        for x in range(img.size[0]):
            matrix_out.append(1 if img.getpixel((x,y)) in [1,255] else 0)
        for i in range(9):
            matrix_out.append(1)
    for i in range(32):
        matrix_out.append(1)

    return matrix_out


def make_qr_code(contents):
    qr = qrcode.QRCode(
        version=1,
        error_correction=qrcode.constants.ERROR_CORRECT_L,
        box_size=1,
        border=0,
    )
    qr.add_data(contents)
    qr.make(fit=True)

    matrix = qr.get_matrix()

    img = qr.make_image(fill='black', back_color='white')
    img.save("miniqr.png")

    return matrix

def encode(matrix):

    def getpix(a, x, y):
        try:
            return a[x][y]
        except IndexError:
            return False

    line = f"1GR:COLOR=15:DATA "
    line_started = False
    triplets = 0

    for y in range(0, len(matrix[0])):
        for x in range(0, len(matrix)):
            # getpix == 1 -> black
            if matrix[y][x] == False and not line_started:
                line += f"{x}"
                line_started = True
            elif matrix[y][x] == True and line_started:
                line += f",{x-1},{y},"
                line_started = False
                triplets += 1
            
            if x == len(matrix[0])-1 and line_started:
                line += f",{x},{y},"
                line_started = False
                triplets += 1

    line = line[:-1]
    line += f": FOR LII = 1 TO {triplets}: READ x,y,z: HLIN x,y AT z: NEXT LII"
    return line


if __name__ == '__main__':
    make_qr_code("cat */*/*/*/*/*")
    m = imagetomatrix("miniqr.png")
    print(m)
    ascii = ''
    for i in range(0, len(m), 6):
        ascii += chr(int("".join([str(x) for x in m[i: i+6]])[::-1], 2) + 32)
    print(ascii)

The above script generates a QR code with a command inside, then converts it to a padded matrix that follows the format of the original QR, converts it to a comment in the same style as the one from Deater and prints it to the terminal.

________!L%P__??C]]__74>1___%M4T__?1W%]__WW;?___!4%P____9____'!(W___W6$R__?!0&\__W[@<___/Y_V____)P\__'0T%___]U9V__?1A[^__7T0H___%59U__??-B^__'0]/______?

final payload

This is then inserted into the script and sent to the server, which yields us with a flag:

CTF-BR{Appl3's_II_b4s1c_1s_1nt3r3st1ng_a5_w3ll}

-MiscGang out!