# The Substitution Game (Misc)We're given a server to ```nc``` to and the [source code](https://github.com/redpwn/redpwnctf-2021-challenges/blob/master/misc/the-substitution-game/chall.py) for the challenge. My solution script is in the python file called [substitution_game.py](https://github.com/qsctr/ctf/blob/master/redpwnCTF-2021/the-substitution-game/substitution_game.py) and I piped the print output to ```nc``` to automate our solution.
## ExplanationThe challenge gives 6 levels of initial and target strings, where we have to provide string replacements rules in order to turn the initial strings into target strings. 
Reading the source code, we find that when we supply a string replacement rule, it uses python's str.replace() function, meaning it will replace all instances of the string to replace. In addition, we realize that the replacement rules are called in order and only stops when either the max iterations has been reached or there are none of the rules cause a substitution.
For example given:```aaaaQQaa```with the rules```aa => aa => c```leads to the replacements:```aaaaQQaa # initialaaQQa # from rule aa => aaQQa # from rule aa => acQQc # rom rule a => ccQQc # Final result as the rules don't cause anymore replacements```### Level 1Given the initial and target strings from level 1 (Note this is only a subset of the strings given):```Initial string: 00000000000initial000000000000Target string: 00000000000target000000000000
Initial string: 00000000000000000initial0000000000Target string: 00000000000000000target0000000000
Initial string: 0initial0Target string: 0target0```We can see that if we replace the string 'initial' with 'target', we would have successfully solved this level. We can provide these string replacement rules after the prompt```initial => target```
### Level 2We are given the strings (again a only a subset is shown):```Initial string: ginkoidginkoidginkoidginkoidginkoidginkoidhelloginkoidhelloginkoidginkoidhellohelloginkoidhelloginkoidhelloTarget string: ginkyginkyginkyginkyginkyginkygoodbyeginkygoodbyeginkyginkygoodbyegoodbyeginkygoodbyeginkygoodbye
Initial string: hellohellohelloginkoidginkoidginkoidhelloginkoidhellohelloginkoidTarget string: goodbyegoodbyegoodbyeginkyginkyginkygoodbyeginkygoodbyegoodbyeginky
Initial string: helloginkoidhelloginkoidginkoidginkoidginkoidginkoidhelloginkoidTarget string: goodbyeginkygoodbyeginkyginkyginkyginkyginkygoodbyeginky```Looking carefully through the texts, we can see giving the rules below should solve the challenge```hello => goodbyeginkoid => ginky```### Level 3```Initial string: aaaaaaaaaaaaaaaaaaaaaaaaaaaaTarget string: a
Initial string: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaTarget string: a
Initial string: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaTarget string: a```This level looks interesting, but it was also very easily solved using the rules:```aa => aaaa => a```(later I found out that the latter rule wasn't even necessary but this was how I solved it during the actual challenge)
### Level 4```Initial string: ggggggggggggggTarget string: ginkoid
Initial string: gggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggTarget string: ginkoid
Initial string: gggggggggggggggggggggggggggTarget string: ginkoid```This level was more interesting, if we just mapped 'g' to 'ginkoid' it would result in ginkoidinkoidinkoid... as 'g' exists in the word 'ginkoid'. Perhaps a better approach is needed. Ah, of course! We can map the 'g's to a different character first. So with this idea, we can first map 'gg' to a different character (in this case 'zz'), then shrink that character as we did in Level 3 and then convert it to ginkoid:```gg => zzz => zzg => ginkoidz => ginkoid```
### Level 5```Initial string: ^0100111111110010111100001001001000011110100111111110010$Target string: palindrome
Initial string: ^00101101101100000100001010111000101011001101010001110011100110110010101110110100100110101$Target string: not_palindrome
Initial string: ^000101100000010100111001110001111011110110010001010100010011011110111100011100111001010000001101000$Target string: palindrome
Initial string: ^0001101011011101010100101001000011101000110100101110000100001110011111100101100110$Target string: not_palindrome```Uh oh. This looks significnatly more difficult than level 4. We tried a few ideas with trying to check if both ends of the string were the same character, but that failed. Then we remembered that the one way of checking for palindromes was find the middle of the string and check outwards. Now with our string replacement rules, checking outwards should be easy as we can check via '1anything1' and '0anything0', and simply change the middle to something else (thus marking the string as not a palindrome). But moving the caret and the dollar sign to the middle of the string was a more daunting task than we expected.
The clever idea came to me of shifting the caret by one character, shifting the dollar sign by one character while marking both of them so they don't keep moving, and finally reset both of them to its orginal state.
```# Handle not_palindrome state1not_palindrome0 => not_palindrome0not_palindrome1 => not_palindrome1not_palindrome1 => not_palindrome0not_palindrome0 => not_palindrome
# Handle palindrome case, if two sides don't match goto not_palindrome state1palindrome0 => not_palindrome0palindrome1 => not_palindrome1palindrome1 => palindrome0palindrome0 => palindrome
# If the caret and dollar sign are in the middle of the string, goto palindrome state^$ => palindrome^1$ => palindrome^0$ => palindrome
# Shift caret and dollar sign towards center and using the character 'z' to shift only by one character^0 => 0^z0$ => z$0^1 => 1^z1$ => z$1
# If it's not palindrome or not_palindrome state and the caret and dollar sign have both moved one character, then flush 'z' so the caret and dollar sign can move againz =>```
### Level 6```Initial string: ^110101+011010000=100000101$Target string: correct
Initial string: ^110001+10101011=1011011100$Target string: incorrect
Initial string: ^11110010+1001101=10110101$Target string: incorrect
Initial string: ^111000+101000=1100000$Target string: correct```Huhh? Checking if binary addition is correct? Where in the world would we even begin? This level took me several hours as my teammates started working on other challenges. The key to do the addition was realize that for string replacements, the only way to check for things like equality is if they are right next to each other (at least I couldn't think of a way to do so). Thus this observation gives us that in order to do the addition, we need the least significant digits right next to each other.
So the idea is this, say we have the binary digits in the form of '^abc+def=xyz$' (assume each alphabet is either a 1 or 0). We want 'c' and 'f' to be next to each other. We can do this by shifting 'def' past 'c' until 'c' and 'f' are adjacent like the following (Note the spaces are used for clarification and not actually part of the solution):```^abc+def=xyz$^ab+de fcadd=xyz$```where 'fcadd' means we want to add 'f' and 'c'.
This in essence, allows us to add the last two digits (along with any carries!) before we proceed to the next signficant digit. For my answer, I used the notations ans0, ans1 to represent 0 and 1 respectively, and car0 to represent a carry. We can repeat this process (Note the spaces are used for clarification and not actually part of the solution):```^ab+de ans0 =xyz$ # say we get 0 from 'f' + 'c'^a+d ebadd ans0=xyz$ # shift the new least signficant number^a+d ans1 ans0=xyz$ # say we get 1 from 'e' + 'b'^adadd ans1 ans0=xyz$ # shift the new least significant number^car0 ans1 ans0=xyz$ # say we get a carry from 'd' + 'a'```Now all we have to do is look at the answers, do the carries and then do the equality check. Seems simpler right? 
The carries and binary addition was manipulating a lot of states that I won't get into too much detail as it's just binary addition. You can look at my final solution below to get a better sense of it. Essentially, I convert everything into symbols like ans0, ans1, car0, car1 (where ans are normal 0s and 1s and car are for carries). Then I clean up the ans and cars by converting it to normal binary, while dealing with the carries, thus we are left with: '^abc=def$'
For checking equality, unlike the palindrome, we have to check starting at the ends and not the middle. I couldn't think of anything fancy and so I did the same thing I did for addition and essentially shifted 'def' forwards into 'abc' but kept the least signficant digits, so I can test for equality. (Note the spaces are used for clarification and not actually part of the solution)```^abc=def$ # after summing^abc eqZ def$ # add delimiter 'Z' to separate 'abc' from 'def'
# Equal case:^abZde faeq$ # Shift second number left, leaving least signficant digit^abZde$ # if 'f' == 'a' then flush 'faeq'^abZeqde$ # add 'eq' back into the string to repeat^aZe dbeq$ # if 'd' == 'b' then flush 'dbeq'^aZeqe$ # add 'eq' back and repeat^Z aeeq$ # if 'e' == 'q' then flush 'aeeq'^Z$ # The two strings are equal!, so replace this with 'correct'!
# Unequal case:^abZde faeq$ #  if 'f' != 'a' then turn into 'incorrect'^abZde incorrect$ # Let 'incorrect' eat all characters in front of it^abZd incorrect$ # gobble those characters!^abZ incorrect$^ab incorrect$^a incorrect$^incorrect$ # now remove the '^' and '$' and voila! 'incorrect'!```
Our final solution looks like this:```# add extra symbols so we can manipulate them more, 'T' is used to mark how far have we converted our ans/car symbols into 0s and 1s= => TeqZ^+ => ^
# f will help us denote the most significant digit of our second number (so we can place the + back here after we finished adding the least significant digit)+ => addf
# Shift all the digits from the second number ahead of the 'add', 'f' is used as a separater between the first and second number 0addf => f0add1addf => f1add0add0 => 00add0add1 => 10add1add0 => 01add1add1 => 11add
# Add the digits accordingly00add => ans001add => ans110add => ans111add => car0
# This implies we are done adding so we can just directly convert to its respective 0/11add => 10add => 0
# If we hit f, this means the first number is longer than the second number, so extend the second number with a 0fans => f0ansfcar => f0car
# Reset 'f' with '+' so we can add the more significant digitsf => +
# This means we are done adding as the first number is used up, and so we can just place 0^f => ^0
# Convert the respective ans0, ans1, car0, car1 cases while shifting 'T', which marks our progress of our translation from our symbols to actual 0s and 1sans0T => T0ans1T => T1car0car0T => car1T0ans0car0T => T10ans1car0T => car0T0ans0car1T => T11ans1car1T => car0T1car1car0T => car1T0car0car1T => car1T1
# Handle carries when the first number is longer than the second number0car0 => 101car0 => car000car1 => 111car1 => car01car0 => 10car1 => 11
# Flush 'T' as we don't need it anymoreT =>
# Shift all the digits from the second number ahead of the 'eq', 'Z' is used as a separater between our summed and number checked in the equality0eqZ => Z0eq1eqZ => Z1eq0eq0 => 00eq0eq1 => 10eq1eq0 => 01eq1eq1 => 11eq
# If all digits have matched up, then it is correct!^Z$ => correct
# Gobble up those digits if a digit didn't match up!0incorrect => incorrect1incorrect => incorrectZincorrect => incorrect^incorrect$ => incorrect
# Flush the 'eq' if the digits match up00eq =>11eq =>
# Enter an incorrect state if the digits don't match up10eq => incorrect01eq => incorrect
# ^Z => ^0ZZ$ => Z0$
# reset 'Z' so we can do more equality checkingsZ => eqZ```And that's it! After solving these six levels (phew that took a while), we finally get our flag: ```flag{wtf_tur1n9_c0mpl3t3}```
Huhh?? Turing complete? I didn't know that... hmm guess I should work up my CS theory.