Marcan's tis101 crackme

Here are my findings in the challenge by marcan codenamed ‘crackme.tis101’

Setup

The challenge is available at the following URLs:

  • nc marcan.st 10847 preferred
  • telnet marcan.st 10847

If you telnet the following url and port, we are greeted with the follwing prompt (does not vary):

================================================================================
           WELCOME TO THE TIS-101 DEVELOPMENT AND TEST ENVIRONMENT
================================================================================
Enter object code followed by NEWLINE:

We need object code to be sent after this. Marcan provides such an object code at the following URLs:

Here are the contents of the file:

004003004734300300002818008958186959880019200595710000020099849751140000000231801656988001920059001800700004278072781017810878108781117803378010759003500700705116419104448070480974810548108480334801090039459004400200500616417100300502818008958186959880019200595710050070258698811491018180017189064007001042480804810848101480974811548101480324590035002004024169859301297984930229771003002028180089581869598800192005957100500202586988145910181800171880170000040025400100404115988128940278141780019000081882564178000002003015164151978800171000007002740060010081686845100600200816868451001003041159881289402781417800190000818825641780000070020374810148110481164810148114480324590030001002041159881289402781417800190000818825641780000030010281800895818695988001920059571007003032481214811148117481144803245900250040010047343005004025869882399101818001718901400600600816868451003007028180089581869598800192005957100000100614515100000600254001007041169881289402781417800190000818825641780000010010411598812894027814178001900008188256417800000300602818008958186959880019200595710040050047343006004008168684510030040281800895818695988001920059571007004027481124809748115481154590020005003025869880639101818001718905100200702514988001979869102318001710050010258698824991018180017188180003003028180089581869598800192005957100700604915920424807148114481014809748116480334801045900420060070081686847100200100616417100100002815988128940237800190000780000040000045675000003019149401290017882565100200202516985910207800090000780010050000258698800691018180017189177000005002540050060258698816091018180017188128004004004567500100504115988128940278141780019000081882564178000006005008168684510020000171698591015180017100600300816868451005005025869881879101818001718905800700503748119481114811448100480584803245900300060000061686510010060411598812894027814178001900008188256417800000400600456750020060141698800197517100400200456750040070047343

After sending the file as text with an additional \n, we obtain the following:

Bootstrapping system...................... Done.

Statistics:
  Units: 64
  Peak memory usage: 51

ENVIRONMENT MODE: SECURE
Lanching application...

Hello!
Please enter your password:

We can guess the goal of this challenge is to try to guess the password, or be able to upload another valid binary, or both. As a bonus challenge, it may be desirable to understand what is this ‘object code’.

Methodology

For this challenge, we’ll try to gather as much information as we can in order to ‘understand’ the underlying principle.

First remarks

The fact that the problem is named tis-101 (probably related to the game tis-100) and the general form of the object code make us think this is some sort of bytecode. Also, it seems there is ‘code’ and ‘data store’. There is also a ‘SECURE’ and ‘INSECURE’ mode, there is probably some checks (maybe done outside the program it self, as the ‘Launching application’) is happening after.

Upon trying to fuzz the input, the VM crashed, we didn’t include it in this analysis (and it has been patched since).

Analysis

Let’s find some statistics:

>>> d = open('crackme.tis','rb').read()                                                 
>>> len(d)
1923
>>> sorted({ chr(x): d.count(x) for x in b'0123456789' }.items())
[('0', 618), ('1', 288), ('2', 99), ('3', 49), ('4', 147), ('5', 125), ('6', 82), ('7', 105), ('8', 278), ('9', 132)]

We can rule out first that the encoding is two characters long, since 1923 is odd (however it may contain a odd header, we’ll revisit later). But a 3 character encoding maybe possible, since 1923/3==641. However there is a 33% chance that this is happening randomly. So the size is not really helpful yet.

Next, we can confirm that there is an awful lots of 0: more than both 2nd and 3rd combined! It seems that these 0 could be used for padding. Or they may be there to confuse us (and have no real information in it, they would be ignored).

Glancing at the text, we can’t see obvious encoding. However some patterns are repeating. For example, the pattern 47343 is repeating 4 times, it may be exiting code.

The total information of the file is around ~3.3bit per symbol times 1923. So we have around a 6KBits or 798 bytes file. A lots of things are possible with such a length! It all depends on the underlying VM (it may have very ‘complicated’ operands, such as ‘output a string of X length’).

Modifying the binary one byte at a time

The nice thing is we don’t have to send the binary as is to the server: we can manipulate it. If we send anything other than ‘0123456789’, it seems to refuse our binary with a simple Invalid data. answer. We can use this property for later source file annotation by removing all characters that are not in the ‘0123456789’ range (disclaimer: this was suggested by marcan himself).

First step is try to remove or add a few bytes to the ‘binary’ (we call it binary for lack of better name). No dice, we get the dreaded Invalid data answer.

However we if modify a random byte, let’s say 0x100 to 0, then we get a different answer! Time to write a python script that will do the following (abbreviated):

indices=range(len(binary))
answers=['' for i in indices]
for i in indices:
    hello=readall() #ignore prompt
    test_binary = binary[:]
    test_binary[i] = 0x30
    write(bytes(test_binary)+b'\n')
    answers[i]  = readall().decode('ascii')

This will yield an enourmous file containing all the anwsers for each modified byte. You can download it at https://bitbucket.org/slurdge/crackme.tis101/raw/master/outputs/answers.txt

Upon reading the answer files, we can see two things:

  • Some bytes are corrupting a single byte of output, for example byte #1768.
  • Some bytes are corrupting sequences of bytes, for example byte #1147.
  • Some bytes are corrupting the output logic, for example #150. If we relate to the fact that the problem is named tis-101, we can infer some ‘cells’ may interact in a weird way when we corrupt this byte.
  • Some bytes are outputting a very large answer and the VM stops at 5000 cycles. For example, byte #145. We probably hit a infinite loop.
  • Two bytes are making the program output ‘Great’ and exiting: #1322 and #161. They may be related to checking code and data.

Interactive analysis

At that point, we take a break from analysing the file and will try to confirm what happens to the above locations. We create another program that takes a file, send it and print the answers, then repeat. In that way, we can modify the binary and have interactive results. The loop has the following format:

while True:
    data = open('crackme.iter.tis','rb').read()
    data = [x for x in data if x in b'0123456789']
    r = try_data(data)
    try:
        print(r.decode('ascii'))
    except:
        print(r)
    c = input('Another run ([Y]/N) ?')
    if c=='n' or c=='N':
        break

We find with this method our first data.

Strings

Until now, we don’t know yet the encoding. It may be variable length encoding. However we discover for sure many strings in the binary. They are of the following form:

78
072 H
78
101 e
78
108 l
78 
108 l
78
111 o
78
033 !
78
010 \n
75

or

48
071 G
48
114 r
48
101 e
48
097 a
48
116 t
48
033 !
48
010 \n
45

However it is not clear how the 4, 7 are related. If we change the 8 by a 9, then we obtain 256-X where X is the following 3 chars interpreted as a byte. So we can do things like 48108 and 49148 that correspond to the same letter ‘l’ in the output.

Blocks

As per tis-100, we suspect there is some kind of ‘block’ concept. This could explain the differences between 78 and 48: they don’t output the data to the same direction. Also, if we tingle with the 90XXX block after the strings, the following string is interleaved with the current one: this supports the idea that it takes the data from another block. In pseudo-code, it would have the following structure (line numbers courtesy of GW-BASIC):

10 output P
20 output l
30 output e
40 output a
50 output s
60 output e
70 output ' '
80 output right_block
90 goto 80

If we change the offset of the goto, then we will repeat more characters from current string. However offset manipulation doesn’t yield a clear rule. 9002 is equivalent to 9006. Maybe the offset is encoded later.

Number of cycles

Let’s try something different. The prompt invites us to write a password, we can do so. Of course, it will fail. However we do have a bit of information given: the number of cycles used by the machine: 553. This number is quite low, but remember that tis-like machine are massively parrallel. Maybe the number of cycles used is not the same if one character is valid ? Let’s try.

We first discover we have to enter at least 16 bytes of data to the program.

import string
all = string.ascii_uppercase+string.ascii_lowercase+string.digits
cycles = {}
for c in range(256):
    test = bytes([c])+b'000000000000000000\n'
    ans =  try_char(test)
    numcycles = ans.decode('ascii').split(': ')[1].strip()
    numcycles = int(numcycles)
    cycles[c] = numcycles
open('cycles.txt','w').write(str(cycles))
>>> set(cycles.values())
{552,553,551}

So, it does vary. Not a lot but a little. If we take a further look, we discover that only the 4 upper bits of input are changing the value. More over, only the following values are yielding results:

ByteNumCycle4 bit upper
241-2565521111
192-2405511100->1111
177-1915521011
128-1765531000->1011
113-1275520111
64-1125510100->0111
49- 635520011
0- 485530000->0011

We can see the patterns repeats if we ignore the upper bit, so maybe values are treated as signed and truncated to 7bit (& 0x7f). Strange values are 48 and 176, which do not fall ‘properly’ within the bit ranges. So there may be a comparison.

Back to block analysis

Not getting very hot with this cycle analisys, we go back to the blocks. One thing we note is that sometimes, the systems anwsers: Units: 63 Hmm, could it be we deactivated one unit? 64 units looks lot like a 8x8 matrix.

>>> fullnums = []
>>> for answer, nums in answers.items():
>>>     if "Units: 63" in  answer:
>>>         fullnums.extend(nums)
>>> fullnums = sorted(fullnums)
>>> print(fullnums, len(fullnums))

[2, 5, 15, 55, 102, 153, 156, 213, 216, 228, 231, 265, 268, 299, 302, 350, 353, 383, 386, 420, 423, 457, 465, 468, 515, 518, 542, 550, 553, 567, 570, 584, 587, 634, 637, 680, 683, 730, 733, 767, 770, 808, 811, 821, 824, 855, 858, 872, 875, 912, 927, 935, 938, 985, 988, 1035, 1038, 1072, 1075, 1085, 1088, 1102, 1105, 1139, 1142, 1175, 1178, 1209, 1212, 1243, 1246, 1277, 1280, 1314, 1317, 1372, 1375, 1389, 1392, 1404, 1441, 1457, 1482, 1485, 1516, 1553, 1561, 1564, 1595, 1598, 1608, 1611, 1658, 1661, 1675, 1701, 1704, 1718, 1721, 1752, 1755, 1798, 1813, 1816, 1863, 1866, 1876, 1879, 1899, 1902, 1912, 1915] 112

112 doesn’t seems quite like a number we recognize, but we can observe two things: often, there a a 3 gap between numbers, and 112 is close to 128 (64x2).

>>> condensed = []
>>> for i in fullnums:
>>>     if i+3 in fullnums:
>>>         condensed.append("{}->{}".format(i, i+3))
>>>     elif i-3 not in fullnums:
>>>         condensed.append(str(i))
>>> print(condensed, len(condensed))

['2->5', '15', '55', '102', '153->156', '213->216', '228->231', '265->268', '299->302', '350->353', '383->386', '420->423', '457', '465->468', '515->518', '542', '550->553', '567->570', '584->587', '634->637', '680->683', '730->733', '767->770', '808->811', '821->824', '855->858', '872->875', '912', '927', '935->938', '985->988', '1035->1038', '1072->1075', '1085->1088', '1102->1105', '1139->1142', '1175->1178', '1209->1212', '1243->1246', '1277->1280', '1314->1317', '1372->1375', '1389->1392', '1404', '1441', '1457', '1482->1485', '1516', '1553', '1561->1564', '1595->1598', '1608->1611', '1658->1661', '1675', '1701->1704', '1718->1721', '1752->1755', '1798', '1813->1816', '1863->1866', '1876->1879', '1899->1902', '1912->1915'] 63

63 is pretty close to 64, so we’ll continue that route.

Getting the blocks!

So, we have around 64 markers for possible places inside the file. Upon inspection, we see it’s of the form X00Y00 or 00X00Y. This could explain the ‘+3’ rule: if two blocks are already defined at 004000 and 000003 for example, then the block 004003 would overlap in both +2 and +5. We check quickly if our hypothesis can be valid:

>>> d=open("crackme.tis","r").read()
>>> for i in range(8):
        for j in range(8):
                print(i,j,"{}00{}00".format(i,j) in d)

We see that some of them are not found. So the format X00Y00 is either wrong, or there is something more. But by testing 00X00Y we find all occurences! With some manual work, we get the following formatted file:

004003 0047343
003000 0281800895818695988001920059571
000002 009984975114
000000 02318016569880019200590018
007000 042780727810178108781087811178033780107590035
007007 051164191044480704809748105481084803348010900394590044
002005 006164171
003005 0281800895818695988001920059571
005007 0258698811491018180017189064
007001 042480804810848101480974811548101480324590035
002004 024169859301297984930229771
003002 0281800895818695988001920059571
005002 0258698814591018180017188017
000004 00254
001004 04115988128940278141780019000081882564178000
002003 015164151978800171
000007 00274
006001 00816868451
006002 00816868451
001003 04115988128940278141780019000081882564178000
007002 0374810148110481164810148114480324590030
001002 04115988128940278141780019000081882564178000
003001 0281800895818695988001920059571
007003 03248121481114811748114480324590025
004001 0047343
005004 0258698823991018180017189014
006006 00816868451
003007 0281800895818695988001920059571
000001 006145151
000006 00254
001007 04116988128940278141780019000081882564178000
001001 04115988128940278141780019000081882564178000
003006 0281800895818695988001920059571
004005 0047343
006004 00816868451
003004 0281800895818695988001920059571
007004 027481124809748115481154590020
005003 0258698806391018180017189051
002007 0251498800197986910231800171
005001 0258698824991018180017188180
003003 0281800895818695988001920059571
007006 0491592042480714811448101480974811648033480104590042
006007 00816868471
002001 006164171
001000 0281598812894023780019000078000
004000 0045675
000003 0191494012900178825651
002002 0251698591020780009000078001
005000 0258698800691018180017189177
000005 00254
005006 0258698816091018180017188128004
004004 5675
001005 04115988128940278141780019000081882564178000
006005 00816868451
002000 01716985910151800171
006003 00816868451
005005 0258698818791018180017189058
007005 0374811948111481144810048058480324590030
006000 006168651
001006 04115988128940278141780019000081882564178000
004006 0045675
002006 01416988001975171
004002 0045675
004007 0047343

which has exactly one element for each (i,j) pair. Moreover, we can see some patterns!

Sort all the things!

Before doing a proper grid display, we can ask our favorite editor to sort the lines for us. It gives us the following:

000000 02318016569880019200590018
000001 006145151
000002 009984975114
000003 0191494012900178825651
000004 00254
000005 00254
000006 00254
000007 00274
001000 0281598812894023780019000078000
001001 04115988128940278141780019000081882564178000
001002 04115988128940278141780019000081882564178000
001003 04115988128940278141780019000081882564178000
001004 04115988128940278141780019000081882564178000
001005 04115988128940278141780019000081882564178000
001006 04115988128940278141780019000081882564178000
001007 04116988128940278141780019000081882564178000
002000 01716985910151800171
002001 006164171
002002 0251698591020780009000078001
002003 015164151978800171
002004 024169859301297984930229771
002005 006164171
002006 01416988001975171
002007 0251498800197986910231800171
003000 0281800895818695988001920059571
003001 0281800895818695988001920059571
003002 0281800895818695988001920059571
003003 0281800895818695988001920059571
003004 0281800895818695988001920059571
003005 0281800895818695988001920059571
003006 0281800895818695988001920059571
003007 0281800895818695988001920059571
004000 0045675
004001 0047343
004002 0045675
004003 0047343
004004 5675
004005 0047343
004006 0045675
004007 0047343
005000 0258698800691018180017189177
005001 0258698824991018180017188180
005002 0258698814591018180017188017
005003 0258698806391018180017189051
005004 0258698823991018180017189014
005005 0258698818791018180017189058
005006 0258698816091018180017188128004
005007 0258698811491018180017189064
006000 006168651
006001 00816868451
006002 00816868451
006003 00816868451
006004 00816868451
006005 00816868451
006006 00816868451
006007 00816868471
007000 042780727810178108781087811178033780107590035 #Hello\n
007001 042480804810848101480974811548101480324590035 #Please
007002 0374810148110481164810148114480324590030 #enter_
007003 03248121481114811748114480324590025 #your_
007004 027481124809748115481154590020 #pass
007005 0374811948111481144810048058480324590030 #word:_
007006 0491592042480714811448101480974811648033480104590042  #Fail!
007007 051164191044480704809748105481084803348010900394590044 #Great

That’s better! We can see a proper structure here. Note that all the strings are at the end.

More analysis

Now that we have proper blocks, we can first guess the structure of the program:

B(0,0)B(0,1)B(0,2)B(0,7)
B(1,0)B(1,1)B(1,2)B(1,7)
B(7,0)B(7,1)B(7,2)B(7,7)

In that notation, the B(7,7) is the following:

007007 051164191044480704809748105481084803348010900394590044 #Great

Now that we understand basic blocks and how they relate to each other, we can try some tests:

001001 005 78080

Will display a series of P on the screen. This that, we start reverse engineering the opcodes.

The opcodes

It’s pretty easy to see that 78 put something on the screen. However, it does so unless there is something below. It seems that the interpreter of tis-101 is creating the cell up until the maximum cell (which would make sense). So, if we create a cell in 099099, the 100x100=10000 cells would be created. It also means that the maximum number of cells is one million.

The first opcode are quite easy to guess:

90XXX JMP XXX #XXX is the number of bytes relative to start of cell
78YYY MOV YYY, DOWN #we suppose for now that '7' is down
79YYY MOV 256-YYY, DOWN
48XXX MOV YYY, LEFT #we suppose for now that '4' is left
48YYY MOV 256-YYY, LEFT
91XXX CONDJMP
92XXX CONDJMP
93XXX CONDJMP
94XXX CONDJMP

Try all the opcodes (again)!

This time, we have better knowledge. We will try a simple program in the following format:

000 000 002 II

Where II goes from 00 to 99.

With that method, we find another way to crash the interpreter. That being fixed, we have a list of interresting answers. 75 and 73 prints:

###### SECURE DATA UNAVAILABLE IN INSECURE MODE ######

Application quiesced.
Elapsed clock cycles: 111

Where 111 is very close to 56x2. 56 is the number of characters in the string displayed. We will also note that 03,05,13,15 are taking 56 cycles so they are probably related to reading from this location.

For now, we will consider that the tis-101 reacts this way: If it reads from a location that is a border, then it reads for STDIN. If it outputs to a location that is border, then it writes to STDOUT.

This may be not completely true, however it will serves its purposes.

More separation

It’s time to try to separate the sorted program. Here we are so far:

000000 023 18016 56 98 80 01 92005 90018
000001 006 14 51 51
000002 009 98497 51 14
000003 019 14 94012 90017 88256 51
000004 002 54
000005 002 54
000006 002 54
000007 002 74
001000 028 15 98 81 28 94023 78001 90000 78000
001001 041 15 98 81 28 94027 81 41 78001 90000 81 88256 41 78000
001002 041 15 98 81 28 94027 81 41 78001 90000 81 88256 41 78000
001003 041 15 98 81 28 94027 81 41 78001 90000 81 88256 41 78000
001004 041 15 98 81 28 94027 81 41 78001 90000 81 88256 41 78000
001005 041 15 98 81 28 94027 81 41 78001 90000 81 88256 41 78000
001006 041 15 98 81 28 94027 81 41 78001 90000 81 88256 41 78000
001007 041 16 98 81 28 94027 81 41 78001 90000 81 88256 41 78000
002000 017 16985 91015 18001 71
002001 006 16 41 71
002002 025 16985 91020 78000 90000 78001
002003 015 16 41 51 97 88001 71
002004 024 16985 93012 97 98 49 30 22 97 71
002005 006 16 41 71
002006 014 1698800197 51 71
002007 025 14 98 80 01 97 98 69 10 23 18001 71
003000 028 18008 95 81 86 95 98 80 01 92005 95 71
003001 028 18008 95 81 86 95 98 80 01 92005 95 71
003002 028 18008 95 81 86 95 98 80 01 92005 95 71
003003 028 18008 95 81 86 95 98 80 01 92005 95 71
003004 028 18008 95 81 86 95 98 80 01 92005 95 71
003005 028 18008 95 81 86 95 98 80 01 92005 95 71
003006 028 18008 95 81 86 95 98 80 01 92005 95 71
003007 028 18008 95 81 86 95 98 80 01 92005 95 71
004000 004 56 75
004001 004 73 43
004002 004 56 75
004003 004 73 43
004004 004 56 75
004005 004 73 43
004006 004 56 75
004007 004 73 43
005000 025 86 98 80 06 91018 18001 71 89177
005001 025 86 98 82 49 91018 18001 71 88180
005002 025 86 98 81 45 91018 18001 71 88017
005003 025 86 98 80 63 91018 18001 71 89051
005004 025 86 98 82 39 91018 18001 71 89014
005005 025 86 98 81 87 91018 18001 71 89058
005006 025 86 98 81 60 91018 18001 71 88128
005007 025 86 98 81 14 91018 18001 71 89064
006000 006 16 86 51
006001 008 16 86 84 51
006002 008 16 86 84 51
006003 008 16 86 84 51
006004 008 16 86 84 51
006005 008 16 86 84 51
006006 008 16 86 84 51
006007 008 16 86 84 71
007000 042 78072 78101 78108 78108 78111 78033 78010 75 90035
007001 042 48080 48108 48101 48097 48115 48101 48032 45 90035
007002 037 48101 48110 48116 48101 48114 48032 45 90030
007003 032 48121 48111 48117 48114 48032 45 90025
007004 027 48112 48097 48115 48115 45 90020
007005 037 48119 48111 48114 48100 48058 48032 45 90030
007006 049 15 92042 48071 48114 48101 48097 48116 48033 48010 45 90042
007007 051 16 41 91044 48070 48097 48105 48108 48033 48010 90039 45 90044

From this, we think that 71 is moving stuff down and 16 taking it from up. If we try the following program:

000000 009 167178080

Then that programs outputs the byte we give it in input followed by P. From that, we conclude that 1 may be related to some ACC register.

Disassembler

From that point, it becomes tiresome to disassemble by hand. We will write a small disassembler that format things nicely for us.

Writing the dissasembler is very straightforward. Take some opcodes, disassemble them. Then see what is the structure of the program, what holes are left, rince&repeat.

Two main difficulties were encountered:

  • Only the bottom left cell is outputting things and only the top left cell is taking input;
  • The opcode 98XXX is very special

98 from hell

Up to this point, we considered the program to be made of variable length encoding of opcodes, with two variants. One of them is two bytes opcode, and one of them is five bytes opcode. However, the cell (0,2) is resisting to this analysis.

000002 009 98497 51 14

If 98 is two byte opcode, then the next is 49751 which whould be MOV LEFT, 256-751 which doesn’t make sense. After many trials, we conclude that this opcode is special. In the form of 98Y with Y between 1 and 7, then it’s SUB ACC, ZZZ where ZZZ is normal encoding. However, in the form of 98(8|9) it is then SUB ACC, (-)IMM. So the opcode takes either 3 bytes or 6 bytes.

With that out of the window, we can disassemble the whole program.

Full disassembly

After a some effort, a full disassembly can be obtained.

A copy can be seen at the following location: https://bitbucket.org/slurdge/crackme.tis101/raw/master/outputs/disassembly.txt

Warning: if you look at the disassembly, you will be spoiled of most of the challenge.

An excerpt of bit mangling is as follow:

+-----------------+-----------------+-----------------+
|MOV ACC, UP      |MOV ACC, UP      |MOV ACC, UP      |
|SUBI ACC, RIGHT  |MOV LEFT, ACC    |SUBI ACC, 001    |
|JGZ m            |MOV DOWN, ACC    |NEG              |
|NEG              |                 |MOV RIGHT, ACC   |
|m:SUBI ACC, LEFT |                 |MOV DOWN, ACC    |
|JGZ w            |                 |                 |
|NEG              |                 |                 |
|w:MOV DOWN, ACC  |                 |                 |
+-----------------+-----------------+-----------------+

Upon looking at the disassembly, we can infer the following behaviour. Take 8 bytes of input -> Substract them from previous one -> Explode into 8 bits -> Mangle the bits -> Reassemble 8 bytes from each bit colums.

Reversing

We now know what is the goal: find 16 values, that, when input, will trigger the code path that will read from secure location. In order to reverse the algorithm, we create the following helper block:

006000 026 16 78048 78032 71 78032 75 90019
006001 026 16 48049 48032 41 48032 45 90019
006002 026 16 48050 48032 41 48032 45 90019
006003 026 16 48051 48032 41 48032 45 90019
006004 026 16 48052 48032 41 48032 45 90019
006005 026 16 48053 48032 41 48032 45 90019
006006 026 16 48054 48032 41 48032 45 90019
006007 026 16 48055 48032 41 48032 45 90019

This blocks basically consumes what comes from top and then output it to the console. That way, we can verify that each step we are reversing correctly. We know that the first 8 values we should obtain are: [6, 249, 145, 63, 239, 187, 160, 114]

We write the following code to reverse:

def getbits(b):
    bits=[]
    for i in range(8):
        bits.append(b&1)
        b=b>>1
    return list(reversed(bits))

def makebyte(bits):
    b=0
    for i in range(8):
        b=(b<<1)|bits[i]
    return b

def reverse(bits):
    r=[0]*8
    bits=list(reversed(bits))
    r[1]=bits[1]
    r[3]=(~bits[3])&1
    r[5]=bits[5]
    r[6]=(~bits[6])&1
    r[0]=bits[0]^r[1]
    r[2]=((~bits[2])&1)^r[3]
    r[4]=r[5]^bits[4]^r[3]
    r[7]=bits[7]^r[6]
    return list(reversed(r))

def transpose(lb):
    t=[]
    for i in range(8):
        ti=[0]*8
        for j in range(8):
            ti[j] = lb[j][i]
        t.append(ti)
    return t

def forward(b):
    r=[0]*8
    b=list(reversed(b))
    r[0]=b[0]^b[1]
    r[1]=b[1]
    r[2]=(~(b[2]^b[3]))&1
    r[3]=(~b[3])&1
    r[4]=b[3]^b[4]^b[5]
    r[5]=b[5]
    r[6]=(~b[6])&1
    r[7]=b[6]^b[7]
    return list(reversed(r))

def swap(l):
    l[2],l[3]=l[3],l[2]
    l[6],l[7]=l[7],l[6]

in0=[6, 249, 145, 63, 239, 187, 160, 114]
in1=[177, -180, -17, 51, 14, 58, -128, 64]
in2=[in0[i]+in1[i] for i in range(8)]

solution=[0]
for _in in (in0, in2):
    _in=_in[:]
    swap(_in)
    lb=[getbits(x) for x in list(reversed(_in))]
    a=[]
    for l in transpose(lb):
        a.append(makebyte(reverse(l)))
    for i in range(8):
        solution.append((solution[-1]+a[i])%256)
    
solution=solution[1:]
print(solution)
print(''.join([chr(x) for x in solution]))

Then it’s just a matter of fixing the swaps, and doing a rolling add on obtained values.

Solution

We get the following valid input:

[103, 114, 49, 100, 99, 48, 109, 80] + [117, 116, 49, 110, 54, 48, 77, 71]

Which translate to ‘gr1dc0mPut1n60MG’. Success!! We also get confirmation that this is a correct password.

Your flag is: D3naryCPUs4r3ALLth3r4g3theseD4ys
Fun fact: You should look up GreenArrays chips, they are real and have a
very similar concept!

Now go play some TIS-100 ;-).

Bonus points

We tried to make an enormous program to see if that if the cells were all operating in parrallel, thus overriding the 5000 cycles limit at least for the first step. However the system is protected against size for the binary and the cells numbers.

Source

https://bitbucket.org/slurdge/crackme.tis101/