sed programming
There’s a big sed script that consists of a list of regular expressions (actually just simple string replacements) that are tried in order. When one is successful, it loops back and starts over. There’s two stop-states (replacements exits the loop).
It looks like this:
#!/bin/sed -f
# Check flag format
# Some characters are used internally
/^SECCON{[02-9A-HJ-Z_a-km-z]*}/!{
cINVALID FORMAT
b
}
:t
s/1Illl11IlIl1/1IlIl11Illl1/;tt
s/1Illl11III1/1III11Illl1/;tt
s/1Ill11IlIl1/1IlIl11Ill1/;tt
s/1Illl11l1/1l11Illl1/;tt
s/1Ill11IIII1/1IIII11Ill1/;tt
s/1Ill11III1/1III11Ill1/;tt
s/1Ill11IIll1/1IIll11Ill1/;tt
s/1Illl11IIll1/1IIll11Illl1/;tt
s/1Illl11IIII1/1IIII11Illl1/;tt
s/1Ill11l1/1l11Ill1/;tt
s/G1II1/GR1II1/;tt
s/1II11IIll11IIll11IIll11IIll11IlIl11IlIl11IlIl11II11IIll1/1II11IIll11IIll11IIll11IIll11IlIl11IlIl11IIll11II1/;tt
s/1II11IIll11IlIl11IlIl11IIll11IlIl11II11IlIl1/1IIIl1/;tt
s/1II11IIll11IIll11IIll11IlIl11IIll11IlIl11IIll11II11IlIl1/1IIIl1/;tt
s/1II11IIll11IlIl11IlIl11IlIl11IlIl11IlIl11IIll11II11IIll1/1II11IIll11IlIl11IlIl11IlIl11IlIl11IIll11IlIl11II1/;tt
s/1II11IIll11IlIl11IIll11IIll11IlIl11IlIl11IlIl11IlIl11II11IlIl1/1II11IIll11IlIl11IIll11IIll11IlIl11IlIl11IlIl11IIll11II1/;tt
s/1II11IIll11IlIl11IIll11IlIl11IlIl11II11IIll1/1II11IIll11IlIl11IIll11IlIl11IIll11II1/;tt
s/1II11IIll11IlIl11IlIl11IlIl11IIll11IIll11IIll11IIll11II11IIll1/1IIIl1/;tt
# ... + tons more ...
Like in qchecker I did this one also naively and manually, even though it clearly invites the construction of state machines that can be more easily manipulated. There’s been a number of similar CTF tasks before, too, and I’ve written bits and pieces, but it’s a messy ad-hoc mess that there’s little hope of salvaging anything. It would probably take me as much time to collect it as it would if I just “brute forced” it like it was a puzzle. Besides, it’s fun to work “with my hands” as it were.
First thing is of course to clean it up so we have something to look at. I’m
simply replacing string-chunks with my best guess for its role in the underlying
state machine. For example it looks like 1 is a separator of some kind,
repeating at a regular interval in many strings. From the stop-states I found a
string that likely represents an error-state, and there’s tons of places where
two symbol-blocks seem to go hand-in-hand like they are binary…
|Illl|:0: /:0:|Illl|
|Illl||III| /|III||Illl|
|Ill|:0: /:0:|Ill|
|Illl||l| /|l||Illl|
|Ill||IIII| /|IIII||Ill|
|Ill||III| /|III||Ill|
|Ill|:1: /:1:|Ill|
|Illl|:1: /:1:|Illl|
|Illl||IIII| /|IIII||Illl|
|Ill||l| /|l||Ill|
G+ / GR+
+:1::1::1::1::0::0::0:+:1: / +:1::1::1::1::0::0::1:+
+:1::0::0::1::0:+:0: / <NO>
+:1::1::1::0::1::0::1:+:0: / <NO>
+:1::0::0::0::0::0::1:+:1: / +:1::0::0::0::0::1::0:+
+:1::0::1::1::0::0::0::0:+:0:/ +:1::0::1::1::0::0::0::1:+
+:1::0::1::0::0:+:1: / +:1::0::1::0::1:+
+:1::0::0::0::1::1::1::1:+:1:/ <NO>
+:1::0::1::1::1::1::1::1:+:0:/ <NO>
+:1::0::1::1::1::1::0:+:0: / <NO>
+:1::0::0::1::1:+:1: / <NO>
+:1::0::1::1::1::0::0:+:0: / <NO>
W<NO> /WR<NO>
+:1::0::0::1::1::1::1:+:1: / +:1::0::1::0::0::0::0:+
+:1::1::0::0::1::0::0:+:1: / <NO>
+:1::0::1::1::0::0::1::0:+:0:/ <NO>
+:1::0::1::0::0::0::1::1:+:0:/ <NO>
+:1::1::0::1::0::1::0:+:1: / <NO>
+:1::0::1::1::0::0::1:+:0: / <NO>
+:1::1::1::1::1::0:+:1: / <NO>
+:1::0::0::1::0::1::0::0:+:0:/ <NO>
+:1::0::0::1::1::0::0::1:+:1:/ <NO>
+:1::1::1::0::1:+:1: / +:1::1::1::1::0:+
+:1::0::1::0::0::0::0:+:0: / <NO>
+:1::1::0::1::1::0:+:0: / +:1::1::0::1::1::1:+
+:1::0::1:+:0: / <NO>
+:1::0::1::1::0::1::1::1:+:0:/ +:1::0::1::1::1::0::0::0:+
+:1::0::1::1::0::1::0::0:+:1:/ <NO>
+:1::1::0::1::1::1:+:1: / +:1::1::1::0::0::0:+
+:1::0::1::1::1::0:+:0: / +:1::0::1::1::1::1:+
+:1::1::1::0::0::0::0:+:1: / +:1::1::1::0::0::0::1:+
+:1::1::1::1:+:1: / <NO>
+:1::0::0::1::1::1:+:1: / <NO>
# ...<snip>...
...
This (the start of the script) seems to be some count-and-check logic. I.e. it counts the binary characters while breaking off with an error if it encounters a given binary digit at a given position. Basically it compares some binary string to a solution?
Further down there’s also two other set of blocks that looked to me like binary digits, though here with just transfer-logic between them.
I wrote a quick Python script to simply dump the state while replacing certain blocks with symbols to watch what was happening visually.
First, apparently is translated to a binary, e.g. 45678 eventually ends up as
its binary string with some initial state:
step 37: §§∅§:I::IIlI::IllI:∅∅§∅∅∅∅∅§∅§∅∅∅∅§∅∅§∅∅∅∅§§∅§∅∅∅§∅∅:l:
Then the “main loop” seems to start. Each iteration seems to transfer the
starting string bit by bit to the other side of the :l: separator symbol, but
manipulated in some way, and now rendered in new symbols:
step 372: §§∅∅:IIlI::IllI:§∅∅∅∅§∅∅§∅∅∅∅§§∅§∅:Illl:∅∅§∅∅:l:¶¶¶°°°¶¶°
step 373: §§∅∅:IIlI::IllI:§∅∅∅∅§∅∅§∅∅∅∅§§∅§∅∅:Illl:∅§∅∅:l:¶¶¶°°°¶¶°
step 374: §§∅∅:IIlI::IllI:§∅∅∅∅§∅∅§∅∅∅∅§§∅§∅∅∅:Illl:§∅∅:l:¶¶¶°°°¶¶°
step 375: §§∅∅:IIlI::IllI:§∅∅∅∅§∅∅§∅∅∅∅§§∅§∅∅∅§:Illl:∅∅:l:¶¶¶°°°¶¶°
step 376: §§∅∅:IIlI::IllI:§∅∅∅∅§∅∅§∅∅∅∅§§∅§∅∅∅§∅:Illl:∅:l:¶¶¶°°°¶¶°
step 377: §§∅∅:IIlI::IllI:§∅∅∅∅§∅∅§∅∅∅∅§§∅§∅∅∅§∅∅:Illl::l:¶¶¶°°°¶¶°
step 378: §§∅∅:IIlI::IllI:§∅∅∅∅§∅∅§∅∅∅∅§§∅§∅∅∅§∅∅:l::Illl:¶¶¶°°°¶¶°
step 379: §§∅∅:IIlI::IllI:§∅∅∅∅§∅∅§∅∅∅∅§§∅§∅∅∅§∅∅:l:¶:Illl:¶¶°°°¶¶°
step 380: §§∅∅:IIlI::IllI:§∅∅∅∅§∅∅§∅∅∅∅§§∅§∅∅∅§∅∅:l:¶¶:Illl:¶°°°¶¶°
step 381: §§∅∅:IIlI::IllI:§∅∅∅∅§∅∅§∅∅∅∅§§∅§∅∅∅§∅∅:l:¶¶¶:Illl:°°°¶¶°
step 382: §§∅∅:IIlI::IllI:§∅∅∅∅§∅∅§∅∅∅∅§§∅§∅∅∅§∅∅:l:¶¶¶°:Illl:°°¶¶°
step 383: §§∅∅:IIlI::IllI:§∅∅∅∅§∅∅§∅∅∅∅§§∅§∅∅∅§∅∅:l:¶¶¶°°:Illl:°¶¶°
step 384: §§∅∅:IIlI::IllI:§∅∅∅∅§∅∅§∅∅∅∅§§∅§∅∅∅§∅∅:l:¶¶¶°°°:Illl:¶¶°
step 385: §§∅∅:IIlI::IllI:§∅∅∅∅§∅∅§∅∅∅∅§§∅§∅∅∅§∅∅:l:¶¶¶°°°¶:Illl:¶°
step 386: §§∅∅:IIlI::IllI:§∅∅∅∅§∅∅§∅∅∅∅§§∅§∅∅∅§∅∅:l:¶¶¶°°°¶¶:Illl:°
step 387: §§∅∅:IIlI::IllI:§∅∅∅∅§∅∅§∅∅∅∅§§∅§∅∅∅§∅∅:l:¶¶¶°°°¶¶°:Illl:
step 388: §§∅∅:IIlI::IllI:§∅∅∅∅§∅∅§∅∅∅∅§§∅§∅∅∅§∅∅:l:¶¶¶°°°¶¶°¶
step 389: §§∅∅:IIlI::IllI::Illl:∅∅∅∅§∅∅§∅∅∅∅§§∅§∅∅∅§∅∅:l:¶¶¶°°°¶¶°¶
step 390: §§∅∅:IIlI::IllI:∅:Illl:∅∅∅§∅∅§∅∅∅∅§§∅§∅∅∅§∅∅:l:¶¶¶°°°¶¶°¶
step 391: §§∅∅:IIlI::IllI:∅∅:Illl:∅∅§∅∅§∅∅∅∅§§∅§∅∅∅§∅∅:l:¶¶¶°°°¶¶°¶
step 392: §§∅∅:IIlI::IllI:∅∅∅:Illl:∅§∅∅§∅∅∅∅§§∅§∅∅∅§∅∅:l:¶¶¶°°°¶¶°¶
(Notice also that the counter on the far left has decreased by 1 now, it does this every full cycle of the “main loop,” but its symbols change to something weird in the end. The original count is accurate though, of 13 iterations.) Once the original binary string is gone, it translates the new binary string into the alphabet of the old one:
step 1157: §§∅∅:IIlI::IlI:¶¶¶°°°¶¶°¶¶°°¶¶¶¶¶¶°°¶°°°¶¶°¶¶¶°
step 1158: §§∅∅:IIlI:§:IlI:¶¶°°°¶¶°¶¶°°¶¶¶¶¶¶°°¶°°°¶¶°¶¶¶°
step 1159: §§∅∅:IIlI:§§:IlI:¶°°°¶¶°¶¶°°¶¶¶¶¶¶°°¶°°°¶¶°¶¶¶°
step 1160: §§∅∅:IIlI:§§§:IlI:°°°¶¶°¶¶°°¶¶¶¶¶¶°°¶°°°¶¶°¶¶¶°
step 1161: §§∅∅:IIlI:§§§∅:IlI:°°¶¶°¶¶°°¶¶¶¶¶¶°°¶°°°¶¶°¶¶¶°
step 1162: §§∅∅:IIlI:§§§∅∅:IlI:°¶¶°¶¶°°¶¶¶¶¶¶°°¶°°°¶¶°¶¶¶°
step 1163: §§∅∅:IIlI:§§§∅∅∅:IlI:¶¶°¶¶°°¶¶¶¶¶¶°°¶°°°¶¶°¶¶¶°
step 1164: §§∅∅:IIlI:§§§∅∅∅§:IlI:¶°¶¶°°¶¶¶¶¶¶°°¶°°°¶¶°¶¶¶°
step 1165: §§∅∅:IIlI:§§§∅∅∅§§:IlI:°¶¶°°¶¶¶¶¶¶°°¶°°°¶¶°¶¶¶°
step 1166: §§∅∅:IIlI:§§§∅∅∅§§∅:IlI:¶¶°°¶¶¶¶¶¶°°¶°°°¶¶°¶¶¶°
step 1167: §§∅∅:IIlI:§§§∅∅∅§§∅§:IlI:¶°°¶¶¶¶¶¶°°¶°°°¶¶°¶¶¶°
step 1168: §§∅∅:IIlI:§§§∅∅∅§§∅§§:IlI:°°¶¶¶¶¶¶°°¶°°°¶¶°¶¶¶°
step 1169: §§∅∅:IIlI:§§§∅∅∅§§∅§§∅:IlI:°¶¶¶¶¶¶°°¶°°°¶¶°¶¶¶°
step 1170: §§∅∅:IIlI:§§§∅∅∅§§∅§§∅∅:IlI:¶¶¶¶¶¶°°¶°°°¶¶°¶¶¶°
step 1171: §§∅∅:IIlI:§§§∅∅∅§§∅§§∅∅§:IlI:¶¶¶¶¶°°¶°°°¶¶°¶¶¶°
Then the loop repeats, doing the same sort of translation. The final string after these iterations is the binary string that is compared in the “error checker” we saw in the beginning.
I also save and print out the values of the binary strings after each “pass” over the strings:
1094861636: 0 :: 41424344: 0 :: b'ABCD':b'' []
1094861636: 0 :: 41424344: 0 :: b'ABCD':b'' []
1094861636: 0 :: 41424344: 0 :: b'ABCD':b'' [12]
1094861636: 0 :: 41424344: 0 :: b'ABCD':b'' [12]
21119812: 0 :: 1424344: 0 :: b'\x01BCD':b'' [12]
...
4: 29983161 :: 4: 1c981b9 :: b'\x04':b'\x01\xc9\x81\xb9' [12]
4: 59966322 :: 4: 3930372 :: b'\x04':b'\x03\x93\x03r' [12]
4: 119932644 :: 4: 72606e4 :: b'\x04':b'\x07&\x06\xe4' [12]
0: 239865288 :: 0: e4c0dc8 :: b'':b'\x0eL\r\xc8' [12]
3815236718: 0 :: e367e46e: 0 :: b'\xe3g\xe4n':b'' []
3815236718: 1 :: e367e46e: 1 :: b'\xe3g\xe4n':b'\x01' [12]
1667753070: 2 :: 6367e46e: 2 :: b'cg\xe4n':b'\x02' [12]
1667753070: 2 :: 6367e46e: 2 :: b'cg\xe4n':b'\x02' [6, 1]
...
Knowing the values must have a pretty simple relation, I just stare at them
really hard until some unknown neurons finally gets it and inform me the loop
does x[i+1] = (x[i] << 1 ^ x[i] ^ x[i] >> 1) % 256**L. This repeats 13 times,
then the result is checked by the count-and-check thing I described above, so,
reversing, we get SECCON{mARkOV_4Lg0Ri7hM}, which, looking it up, is the name
for this kind of construction I guess?