## General problem description
```You won't find any assembly in this challenge, only C64 BASIC. Once you get the password, the flag is CTF{password}. P.S. The challenge has been tested on the VICE emulator.```
We got an old .prg file, which is a C64 program file.
## Parsing the file
First we tried using parsers that exist in the wild, that would parse the file for us, but that proved to be not effective, as there were not many and they didn't work very well, so we wrote our own parser. Fortunately the file format is not very difficult.Here is the parser in python:```pythonimport binasciidecode_char = [    u'\uFFFD',u'\uFFFD',u'\uFFFD',u'\uFFFD',u'\uFFFD',u'\uF100',u'\uFFFD',u'\uFFFD',u'\uF118',u'\uF119',u'\uFFFD',u'\uFFFD',u'\uFFFD',u'\u000D',u'\u000E',u'\uFFFD',    u'\uFFFD',u'\uF11C',u'\uF11A',u'\uF120',u'\u007F',u'\uFFFD',u'\uFFFD',u'\uFFFD',u'\uFFFD',u'\uFFFD',u'\uFFFD',u'\uFFFD',u'\uF101',u'\uF11D',u'\uF102',u'\uF103',    u'\u0020',u'\u0021',u'\u0022',u'\u0023',u'\u0024',u'\u0025',u'\u0026',u'\u0027',u'\u0028',u'\u0029',u'\u002A',u'\u002B',u'\u002C',u'\u002D',u'\u002E',u'\u002F',    u'\u0030',u'\u0031',u'\u0032',u'\u0033',u'\u0034',u'\u0035',u'\u0036',u'\u0037',u'\u0038',u'\u0039',u'\u003A',u'\u003B',u'\u003C',u'\u003D',u'\u003E',u'\u003F',    u'\u0040',u'\u0061',u'\u0062',u'\u0063',u'\u0064',u'\u0065',u'\u0066',u'\u0067',u'\u0068',u'\u0069',u'\u006A',u'\u006B',u'\u006C',u'\u006D',u'\u006E',u'\u006F',    u'\u0070',u'\u0071',u'\u0072',u'\u0073',u'\u0074',u'\u0075',u'\u0076',u'\u0077',u'\u0078',u'\u0079',u'\u007A',u'\u005B',u'\u00A3',u'\u005D',u'\u2191',u'\u2190',    u'\u2501',u'\u0041',u'\u0042',u'\u0043',u'\u0044',u'\u0045',u'\u0046',u'\u0047',u'\u0048',u'\u0049',u'\u004A',u'\u004B',u'\u004C',u'\u004D',u'\u004E',u'\u004F',    u'\u0050',u'\u0051',u'\u0052',u'\u0053',u'\u0054',u'\u0055',u'\u0056',u'\u0057',u'\u0058',u'\u0059',u'\u005A',u'\u253C',u'\uF12E',u'\u2502',u'\u2592',u'\uF139',    u'\uFFFD',u'\uF104',u'\uFFFD',u'\uFFFD',u'\uFFFD',u'\uF110',u'\uF112',u'\uF114',u'\uF116',u'\uF111',u'\uF113',u'\uF115',u'\uF117',u'\u000A',u'\u000F',u'\uFFFD',    u'\uF105',u'\uF11E',u'\uF11B',u'\u000C',u'\uF121',u'\uF106',u'\uF107',u'\uF108',u'\uF109',u'\uF10A',u'\uF10B',u'\uF10C',u'\uF10D',u'\uF11D',u'\uF10E',u'\uF10F',    u'\u00A0',u'\u258C',u'\u2584',u'\u2594',u'\u2581',u'\u258F',u'\u2592',u'\u2595',u'\uF12F',u'\uF13A',u'\uF130',u'\u251C',u'\uF134',u'\u2514',u'\u2510',u'\u2582',    u'\u250C',u'\u2534',u'\u252C',u'\u2524',u'\u258E',u'\u258D',u'\uF131',u'\uF132',u'\uF133',u'\u2583',u'\u2713',u'\uF135',u'\uF136',u'\u2518',u'\uF137',u'\uF138',    u'\u2501',u'\u0041',u'\u0042',u'\u0043',u'\u0044',u'\u0045',u'\u0046',u'\u0047',u'\u0048',u'\u0049',u'\u004A',u'\u004B',u'\u004C',u'\u004D',u'\u004E',u'\u004F',    u'\u0050',u'\u0051',u'\u0052',u'\u0053',u'\u0054',u'\u0055',u'\u0056',u'\u0057',u'\u0058',u'\u0059',u'\u005A',u'\u253C',u'\uF12E',u'\u2502',u'\u2592',u'\uF139',    u'\u00A0',u'\u258C',u'\u2584',u'\u2594',u'\u2581',u'\u258F',u'\u2592',u'\u2595',u'\uF12F',u'\uF13A',u'\uF130',u'\u251C',u'\uF134',u'\u2514',u'\u2510',u'\u2582',    u'\u250C',u'\u2534',u'\u252C',u'\u2524',u'\u258E',u'\u258D',u'\uF131',u'\uF132',u'\uF133',u'\u2583',u'\u2713',u'\uF135',u'\uF136',u'\u2518',u'\uF137',u'\u2592'    ]
token = ["END", "FOR", "NEXT", "DATA", "INPUT#", "INPUT", "DIM", "READ",         "LET", "GOTO", "RUN", "IF", "RESTORE", "GOSUB", "RETURN", "REM",        "STOP", "ON", "WAIT", "LOAD", "SAVE", "VERIFY", "DEF", "POKE",        "PRINT#", "PRINT", "CONT", "LIST", "CLR", "CMD", "SYS", "OPEN",        "CLOSE", "GET", "NEW", "TAB(", "TO", "FN", "SPC(", "THEN",        "NOT", "STEP", "+", "-", "*", "/", "power", "AND",        "OR", ">", "=", "<", "SGN", "INT", "ABS", "USR",        "FRE", "POS", "SQR", "RND", "LOG", "EXP", "COS", "SIN",        "TAN", "ATN", "PEEK", "LEN", "STR$", "VAL", "ASC", "CHR$",        "LEFT$", "RIGHT$", "MID$", "GO"] 
ptr = 0def parsecommand(f):    global ptr    s = ""    while True:        c = f.read(1)        ptr += 1        if len(c) == 0:            return s        byte = ord(c)        if byte >= 0x80 and byte <= 0xCB:            s = s + token[byte - 0x80]            continue        elif byte == 0x00:            return s        s = s + decode_char[byte]
with open("crackme.prg", "rb") as f:    ptr = int(binascii.hexlify(f.read(2)[::-1]), 16)    print("Mapping Offset %x" % ptr)    while True:        nextoffset = f.read(2)[::-1]        if len(nextoffset) < 2:            break        print ("%x" % ptr) + " -> " + binascii.hexlify(nextoffset)        ptr += 2        label = f.read(2)        if len(label) < 2:            break        lab = int(binascii.hexlify(label[::-1]), 16)        ptr += 2        print str(lab) + " " + parsecommand(f)```
## Patching the binaryWe looked at the code and saw that this command:```basic2001 POKE 03397, 00069 : POKE 03398, 00013```Considering that the binary is mapped at memory position 0x801, this command actually modifies the program memory.There is also a second such command:```basic2001 POKE 03397, 00069 : POKE 03398, 00013```These two do not do anything except manipulate the next-pointer of a comment.
The next few pairs of commands, that we can recognize as important are of the form:```c642004 ES = 03741 : EE = 04981 : EK = 1482005 FOR I = ES TO EE : K = ( PEEK(I) + EK ) AND 255 : POKE I, K : NEXT I```They loop over program memory and change it. We Wrote a script, that patches these memory locations, so we can parse the decoded memory.The code for this was:```pythondef patchbinary(f1, f2, fr, to, l):    with open(f1, "rb") as f:        data = f.read()    offset = data[:2]    ptr = int(binascii.hexlify(offset[::-1]), 16)    fr -= ptr    to -= ptr    data = data[2:]    pre = data[:fr]    topatch = data[fr:to]    post = data[to:]    res = ""    for c in topatch:        res = res + l(c)    with open(f2, "wb") as file2:        file2.write(offset + pre + res + post) #2001 POKE 03397, 00069 : POKE 03398, 00013patchbinary("crackme.prg", "crackme2.prg", 3397, 3398, lambda x: chr(199))patchbinary("crackme2.prg", "crackme2.prg", 3398, 3399, lambda x: chr(13))#2001 POKE 03397, 00069 : POKE 03398, 00013patchbinary("crackme2.prg", "crackme2.prg", 3397, 3398, lambda x: chr(69))patchbinary("crackme2.prg", "crackme2.prg", 3398, 3399, lambda x: chr(13))#2004 ES = 03741 : EE = 04981 : EK = 148#2005 FOR I = ES TO EE : K = ( PEEK(I) + EK ) AND 255 : POKE I, K : NEXT Ipatchbinary("crackme2.prg", "crackme2.prg", 3741, 4982, lambda x: chr((ord(x) + 148) & 0xff))#2004 ES = 05363 : EE = 06632 : EK = 152#2005 FOR I = ES TO EE : K = ( PEEK(I) + EK ) AND 255 : POKE I, K : NEXT Ipatchbinary("crackme2.prg", "crackme2.prg", 5363, 6633, lambda x: chr((ord(x) + 152) & 0xff))#2004 ES = 07014 : EE = 08219 : EK = 165#2005 FOR I = ES TO EE : K = ( PEEK(I) + EK ) AND 255 : POKE I, K : NEXT Ipatchbinary("crackme2.prg", "crackme2.prg", 7014, 8220, lambda x: chr((ord(x) + 165) & 0xff))#2004 ES = 08601 : EE = 09868 : EK = 184#2005 FOR I = ES TO EE : K = ( PEEK(I) + EK ) AND 255 : POKE I, K : NEXT Ipatchbinary("crackme2.prg", "crackme2.prg", 8601, 9869, lambda x: chr((ord(x) + 184) & 0xff))#2004 ES = 10250 : EE = 11483 : EK = 199#2005 FOR I = ES TO EE : K = ( PEEK(I) + EK ) AND 255 : POKE I, K : NEXT Ipatchbinary("crackme2.prg", "crackme2.prg", 10250, 11484, lambda x: chr((ord(x) + 199) & 0xff))#2004 ES = 11865 : EE = 13107 : EK = 240#2005 FOR I = ES TO EE : K = ( PEEK(I) + EK ) AND 255 : POKE I, K : NEXT Ipatchbinary("crackme2.prg", "crackme2.prg", 11865, 13108, lambda x: chr((ord(x) + 240) & 0xff))#2004 ES = 13489 : EE = 14760 : EK = 249#2005 FOR I = ES TO EE : K = ( PEEK(I) + EK ) AND 255 : POKE I, K : NEXT Ipatchbinary("crackme2.prg", "crackme2.prg", 13489, 14761, lambda x: chr((ord(x) + 249) & 0xff))#2004 ES = 15142 : EE = 16351 : EK = 132#2005 FOR I = ES TO EE : K = ( PEEK(I) + EK ) AND 255 : POKE I, K : NEXT Ipatchbinary("crackme2.prg", "crackme2.prg", 15142, 16352, lambda x: chr((ord(x) + 132) & 0xff))#2004 ES = 16733 : EE = 17975 : EK = 186#2005 FOR I = ES TO EE : K = ( PEEK(I) + EK ) AND 255 : POKE I, K : NEXT Ipatchbinary("crackme2.prg", "crackme2.prg", 16733, 17976, lambda x: chr((ord(x) + 186) & 0xff))#2004 ES = 18360 : EE = 19633 : EK = 214#2005 FOR I = ES TO EE : K = ( PEEK(I) + EK ) AND 255 : POKE I, K : NEXT Ipatchbinary("crackme2.prg", "crackme2.prg", 18360, 19634, lambda x: chr((ord(x) + 214) & 0xff))#2004 ES = 20020 : EE = 21265 : EK = 245#2005 FOR I = ES TO EE : K = ( PEEK(I) + EK ) AND 255 : POKE I, K : NEXT Ipatchbinary("crackme2.prg", "crackme2.prg", 20020, 21266, lambda x: chr((ord(x) + 245) & 0xff))#2004 ES = 21652 : EE = 22923 : EK = 203#2005 FOR I = ES TO EE : K = ( PEEK(I) + EK ) AND 255 : POKE I, K : NEXT Ipatchbinary("crackme2.prg", "crackme2.prg", 21652, 22924, lambda x: chr((ord(x) + 203) & 0xff))#2004 ES = 23310 : EE = 24584 : EK = 223#2005 FOR I = ES TO EE : K = ( PEEK(I) + EK ) AND 255 : POKE I, K : NEXT Ipatchbinary("crackme2.prg", "crackme2.prg", 23310, 24585, lambda x: chr((ord(x) + 223) & 0xff))#2004 ES = 24971 : EE = 26178 : EK = 237#2005 FOR I = ES TO EE : K = ( PEEK(I) + EK ) AND 255 : POKE I, K : NEXT Ipatchbinary("crackme2.prg", "crackme2.prg", 24971, 26179, lambda x: chr((ord(x) + 237) & 0xff))#2004 ES = 26565 : EE = 27837 : EK = 192#2005 FOR I = ES TO EE : K = ( PEEK(I) + EK ) AND 255 : POKE I, K : NEXT Ipatchbinary("crackme2.prg", "crackme2.prg", 26565, 27838, lambda x: chr((ord(x) + 192) & 0xff))#2004 ES = 28224 : EE = 29471 : EK = 157#2005 FOR I = ES TO EE : K = ( PEEK(I) + EK ) AND 255 : POKE I, K : NEXT Ipatchbinary("crackme2.prg", "crackme2.prg", 28224, 29472, lambda x: chr((ord(x) + 157) & 0xff))#2004 ES = 29858 : EE = 31101 : EK = 158#2005 FOR I = ES TO EE : K = ( PEEK(I) + EK ) AND 255 : POKE I, K : NEXT Ipatchbinary("crackme2.prg", "crackme2.prg", 29858, 31102, lambda x: chr((ord(x) + 158) & 0xff))#2004 ES = 31488 : EE = 32761 : EK = 235#2005 FOR I = ES TO EE : K = ( PEEK(I) + EK ) AND 255 : POKE I, K : NEXT Ipatchbinary("crackme2.prg", "crackme2.prg", 31488, 32762, lambda x: chr((ord(x) + 235) & 0xff))#2004 ES = 33148 : EE = 34367 : EK = 143#2005 FOR I = ES TO EE : K = ( PEEK(I) + EK ) AND 255 : POKE I, K : NEXT Ipatchbinary("crackme2.prg", "crackme2.prg", 33148, 34368, lambda x: chr((ord(x) + 143) & 0xff))```
All decoded sections have the form of:```basic2010 v = 0.6666666666612316235641 - 0.00000000023283064365386962890625 : g = 02020 ba = ASC( MID$(p$, 1, 1) )2021 bb = ASC( MID$(p$, 2, 1) )2025 p0 = 0:p1 = 0:p2 = 0:p3 = 0:p4 = 0:p5 = 0:p6 = 0:p7 = 0:p8 = 0:p9 = 0:pa = 0:pb = 0:pc = 02030 IF ba AND 1 THEN p0 = 0.0625000000018189894035458564758300781252031 IF ba AND 2 THEN p1 = 0.01562500000045474735088646411895751953122032 IF ba AND 4 THEN p2 = 0.00390625000011368683772161602973937988282033 IF ba AND 8 THEN p3 = 0.00097656250002842170943040400743484497072034 IF ba AND 16 THEN p4 = 0.00024414062500710542735760100185871124272035 IF ba AND 32 THEN p5 = 0.00006103515625177635683940025046467781072036 IF ba AND 64 THEN p6 = 0.00001525878906294408920985006261616945272037 IF ba AND 128 THEN p7 = 0.00000381469726573602230246251565404236322040 IF bb AND 1 THEN p8 = 0.00000095367431643400557561562891351059082031 IF bb AND 2 THEN p9 = 0.00000023841857910850139390390722837764772032 IF bb AND 4 THEN pa = 0.00000005960464477712534847597680709441192033 IF bb AND 8 THEN pb = 0.0000000149011611942813371189942017736032034 IF bb AND 16 THEN pc = 0.00000000372529029857033427974855044340072050 k = v + p0 + p1 + p2 + p3 + p4 + p5 + p6 + p7 + p8 + p9 + pa + pb + pc2060 g = 0.6715657063760172100 t0 = k = g : a = 86 : b = 102200 IF t0 = -1 THEN a = 83 : b = 52210 POKE 1024 + chkoff + 1, 90````ASC( MID$(p$, 1, 1) )` selects the first char and converts it into a number.From what we can gather the code adds values to `v` depending if certain bits are set in the converted chars of the input.
Then there is a compare with value `g`. THe problem here is, that the values can never add up to `g` no mather the combination. At first this was confusing, but computers when working with floating point may not be accurate. So what we tried to do was to be as accurate as possible and just go with that.
When working with the values we did not actually use floating point numbers, but python integers. They do not have a size limit we need to worry about, so we converted the floating point numbers to integers like this: `0.6666666666612316235641 -> int("6666666666612316235641".ljust(50, '0'))`. So we append 0s on the right side of the number until they have a length of 50. This means all our numbers are strings of length 50, which we can now transform to integers. This means we do not loose precision.
Now we need to choose the best values for `p0` - `pc` so that the sum + `v` best matches `g`. We used this algorithm to solve the problem:```pythondef solve_eq(koeff, v):    sol = []    for k in koeff:        if abs(v - k) > v:            sol.append(0)        else:            v -= k            sol.append(1)    print v    return sol```
When going through all decoded sections we can see that the only values, that diverge from the first block are `v` and `g`. We extracted all values and solved all bits of the solution:```arr = []p = [int("062500000001818989403545856475830078125".ljust(50, '0')),    int("0156250000004547473508864641189575195312".ljust(50, '0')),    int("0039062500001136868377216160297393798828".ljust(50, '0')),    int("0009765625000284217094304040074348449707".ljust(50, '0')),    int("0002441406250071054273576010018587112427".ljust(50, '0')),    int("0000610351562517763568394002504646778107".ljust(50, '0')),    int("0000152587890629440892098500626161694527".ljust(50, '0')),    int("0000038146972657360223024625156540423632".ljust(50, '0')),    int("0000009536743164340055756156289135105908".ljust(50, '0')),    int("0000002384185791085013939039072283776477".ljust(50, '0')),    int("0000000596046447771253484759768070944119".ljust(50, '0')),    int("000000014901161194281337118994201773603".ljust(50, '0')),    int("0000000037252902985703342797485504434007".ljust(50, '0'))] v = int("6666666666612316235641".ljust(50, '0')) - int("00000000023283064365386962890625".ljust(50, '0'))k = int("671565706376017".ljust(50, '0'))arr.extend(solve_eq(p, k - v))
k = int("682612358126820".ljust(50, '0'))arr.extend(solve_eq(p, k - v))
v = int("6666666666612316235641".ljust(50, '0'))k = int("682552023325146".ljust(50, '0'))arr.extend(solve_eq(p, k - v))
v = int("6666666666612316235641".ljust(50, '0')) - int("00000000023283064365386962890625".ljust(50, '0'))k = int("667647300753773".ljust(50, '0'))arr.extend(solve_eq(p, k - v))
v = int("6666666666612316235641".ljust(50, '0'))k = int("682310803327740".ljust(50, '0'))arr.extend(solve_eq(p, k - v))
...
def frombits(bits):    chars = []    for b in range(len(bits) / 8):        byte = bits[b*8:(b+1)*8]        chars.append(chr(int(''.join([str(bit) for bit in byte]), 2)))    return ''.join(chars)s = ""for i in range(0, len(arr), 8):    s = s + frombits(arr[i:i + 8][::-1])print ```Executing this program gives us `LINKED-LISTS-AND-40-BIT-FLOATS` which makes the flag `CTF{LINKED-LISTS-AND-40-BIT-FLOATS}`