I solved this challenge when I was on a long and boring bus trip... Nothing better than a CTF to keep me awake 😉 We have this python script:
def LShift(t, k):
k %= 8
return ((t << k) | (t >> (8 - k))) & 0xff
def encode(p):
ret = ""
for i in range(8):
ret = ('|' if (p >> i) & 1 else 'O') + ret
return ret
A = [85, 128, 177, 163, 7, 242, 231, 69, 185, 1, 91, 89, 80, 156, 81, 9, 102, 221, 195, 33, 31, 131, 179, 246, 15, 139, 205, 49, 107, 193, 5, 63, 117, 74, 140, 29, 135, 43, 197, 212, 0, 189, 218, 190, 112, 83, 238, 47, 194, 68, 233, 67, 122, 138, 53, 14, 35, 76, 79, 162, 145, 51, 90, 234, 50, 6, 225, 250, 215, 133, 180, 97, 141, 96, 20, 226, 3, 191, 187, 57, 168, 171, 105, 113, 196, 71, 239, 200, 254, 175, 164, 203, 61, 16, 241, 40, 176, 59, 70, 169, 146, 247, 232, 152, 165, 62, 253, 166, 167, 182, 160, 125, 78, 28, 130, 159, 255, 124, 153, 56, 58, 143, 150, 111, 207, 206, 32, 144,
75, 39, 10, 201, 204, 77, 104, 65, 219, 98, 210, 173, 249, 13, 12, 103, 101, 21, 115, 48, 157, 147, 11, 99, 227, 45, 202, 158, 213, 100, 244, 54, 17, 161, 123, 92, 181, 243, 184, 188, 84, 95, 27, 72, 106, 192, 52, 44, 55, 129, 208, 109, 26, 24, 223, 64, 114, 19, 198, 23, 82, 120, 142, 178, 214, 186, 116, 94, 222, 86, 251, 36, 4, 248, 132, 25, 211, 199, 30, 87, 60, 127, 155, 41, 224, 151, 237, 136, 245, 37, 170, 252, 8, 42, 209, 46, 108, 88, 183, 149, 110, 66, 235, 229, 134, 73, 38, 118, 236, 119, 154, 216, 217, 240, 22, 121, 174, 93, 126, 230, 228, 18, 148, 220, 172, 2, 137, 34]
B = [0, 2, 3, 7, 1, 5, 6, 4]
C = [179, 132, 74, 60, 94, 252, 166, 242, 208, 217, 117, 255, 20, 99, 225, 58, 54, 184, 243, 37, 96, 106, 64, 151, 148, 248, 44, 175, 152, 40, 171, 251, 210, 118, 56, 6, 138, 77, 45, 169, 209, 232, 68, 182, 91, 203, 9, 16, 172, 95, 154, 90, 164, 161, 231, 11, 21, 3, 97, 70, 34, 86, 124, 114, 119, 223, 123, 167, 47, 219, 197, 221, 193, 192, 126, 78, 39, 233, 4, 120, 33, 131, 145, 183, 143, 31, 76, 121, 92, 153, 85, 100, 52, 109, 159, 112, 71, 62, 8, 244, 116, 245, 240, 215, 111, 134, 199, 214, 196, 213, 180, 189, 224, 101, 202, 201, 168, 32, 250, 59, 43, 27, 198, 239, 137, 238, 50,
149, 107, 247, 7, 220, 246, 204, 127, 83, 146, 147, 48, 17, 67, 23, 93, 115, 41, 191, 2, 227, 87, 173, 108, 82, 205, 49, 1, 66, 105, 176, 22, 236, 29, 170, 110, 18, 28, 185, 235, 61, 88, 13, 165, 188, 177, 230, 130, 253, 150, 211, 42, 129, 125, 141, 19, 190, 133, 53, 84, 140, 135, 10, 241, 222, 73, 12, 155, 57, 237, 181, 36, 72, 174, 207, 98, 5, 229, 254, 156, 178, 128, 55, 14, 69, 30, 194, 122, 46, 136, 160, 206, 26, 102, 218, 103, 139, 195, 0, 144, 186, 249, 79, 81, 75, 212, 234, 158, 163, 80, 226, 65, 200, 38, 187, 113, 63, 24, 25, 142, 51, 228, 35, 157, 216, 104, 162, 15, 89]
D = [2, 4, 0, 5, 6, 7, 1, 3]
plain = bytearray("asdfghjk123456")
key = bytearray(/*Missed*/)
assert len(key) == 8
t1 = bytearray()
for i in plain:
t1.append(A[i])
t2 = bytearray()
for i in range(len(t1)):
t2.append(LShift(t1[i], B[i % 8]))
for times in range(16):
for i in range(len(t2)):
t2[i] = C[t2[i]]
for i in range(len(t2)):
t2[i] = LShift(t2[i], i ^ D[i % 8])
for i in range(len(t2)):
t2[i] ^= key[i % 8]
out = ""
for i in t2:
out += encode(i)
print out
# out>>
# OO|OO||OO|||||OO|OO||O||O|O||O|||O|OOOOOOO|O|O|O|||||OO|||O|||OO||O|OOOOOO|O|OO|OO||||OO|||OOOO|||||O||||O|OO|O|O|O||OO|O||O|OO|O||O|||O||O|OO|OOOOOO||OOO|O|O|O|||O|OO|O|O||O||O||OOOOO|||OO|O|
# flag >>
# OO||O||O|O|||OOOO||||||O|O|||OOO||O|OOOO||O|O|OO|||||OOOO||||O||OO|OO||O||O|O|O|||||OOOOOO|O|O||OOOOOOO||O|||OOOO||OO|OO|||O|OO|O|||O|O|OO|OOOO|OOO|OOO|OOOO||O|OO||||OO||||OOO|O|O||OO||||O||OOO|||O|OO|OO||OO||OOOO|O|
Our task is to find the key that produces the result out for the input "asdfghjk123456". First, I decided to write a decrypt function, since we only have a encrypt procedure and I'm going to need it to decrypt the flag. As you can see, the encrypt procedure uses two functions: encode and LShift. Therefore, the decrypt procedure will use decode and RShift. The decode function converts the binary representation (| and 0) to a number in the range 0-255:
def RShift(t, k):
k %= 8
return ((t >> k) | (t << (8 - k))) & 0xff
def decode(s):
bits = ""
for i in range(8):
if (s[i] == '|'):
bits += "1"
else:
bits += "0"
return int(bits, 2)
Now that we have these two functions, we need to write the decrypt function:
def decrypt(out, key):
t2 = []
for i in range(0, len(out), 8):
t2.append(decode(out[i:i+8]))
for times in range(16):
for i in range(len(t2)):
t2[i] ^= key[i%8]
for i in range(len(t2)):
t2[i] = RShift(t2[i], i ^ D[i % 8])
for i in range(len(t2)):
t2[i] = C.index(t2[i])
t1 = []
for i in range(len(t2)):
t1.append(RShift(t2[i], B[i % 8]))
plain = ""
for i in t1:
plain += chr(A.index(i))
return plain
Now that everything is working, we need to write a function to get the key used for a given plaintext and output. This is possible since the only operation that uses the key is t2[i] ^= key[i%8] (XOR).
def getKey(plain, out):
#use plain
t1 = bytearray()
for i in plain:
t1.append(A[i])
t2 = bytearray()
for i in range(len(t1)):
t2.append(LShift(t1[i], B[i % 8]))
#use out
dt2 = []
for i in range(0, len(out), 8):
dt2.append(decode(out[i:i+8]))
key = bytearray("00000000")
tmp = [0]*8
for i in range(8):
print("key[" + str(i) + "] ="),
for j in range(0, 255):
tmp[i] = t2[i]
key[i] = j
for times in range(16):
tmp[i] = C[tmp[i]]
tmp[i] = LShift(tmp[i], i ^ D[i % 8])
tmp[i] ^= int(key[i % 8])
if (tmp[i] == dt2[i]):
print(j),
print("")
What I am doing here is to reach the t2 list state before the for times in range(16) using the plaintext, and getting the t2 list (dt2) right after the same for loop using the encrypted output for the same plaintext. Then, this function compares t2 and dt2 after the for loop, bruteforcing the key index by index.
This function produces the following output for the plaintext "asdfghjk123456" and the given output:
key[0] = 64 94 137 key[1] = 38 78 key[2] = 35 key[3] = 113 key[4] = 68 243 key[5] = 57 84 153 163 key[6] = 51 245 key[7] = 0 4 95 157 163
Now, we have the possible key codes for each index. After a few attempts I was able to decrypt the flag, using the key:
key = bytearray(chr(94) + chr(38) + chr(35) + chr(113) + chr(68) + chr(57) + chr(51) + chr(95))
print(decrypt(flag, key))
SSCTF{1qaz9ol.nhy64rfv7ujm}