Hack You CTF - Crypto 300 [Team xbios]

We were given the python source code of the crpto service. The flag is read from a file and used as the salt for S-box. Also during encryption the S-box is once again shuffled with a part of the user input. So to grab the key we have to do the reverse process. First we find the current S-box using printables and non printables from ascii range of 0-127. Then revert back the effect in S-box due to user input. This will give the server copy of the salted S-box. From this copy we have to find the key which is our flag.
Here is the part of code which we used to grab the server copy of salted S-box. Not the best code to read but it worked for us

#!/usr/bin/python

import string
import collections
from socket import *

data_print = string.printable
data_notprint = "\x00\x01\x02\x03\x04\x05\x06\x07\x08\x0e\x0f\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19\x1a\x1b\x1c\x1d\x1e\x1f\x7f"
JUNK = "aa"
NEW_LINE = "\n"
HOST = "127.0.0.1" 
HOST = "93.191.13.142"
PORT = 7777
sbox = [0] * 128

soc = socket(AF_INET,SOCK_DGRAM)
soc.connect((HOST,PORT))

for i in data_print:
    data = JUNK + i + NEW_LINE
    soc.sendto(data, (HOST, PORT))
    f_byte = soc.recvfrom(128)[0][:2] #fetch first byte
    val = ord(f_byte.decode("hex"))
    sbox[int(ord(i))] = val
for i in data_notprint:
    data =JUNK + i + NEW_LINE
    soc.sendto(data, (HOST, PORT))
    f_byte = soc.recvfrom(128)[0][:2] #fetch first byte
    val = ord(f_byte.decode("hex"))
    sbox[int(ord(i))] = val

print "\n[*] Reconstructed LEVEL ONE SBOX"
print sbox

for j in xrange(len(sbox)):  #remove the effect in S-box due to user input
    sbox[j] = (sbox[j] - 1) % 128
sbox[ord('a')],sbox[1] = sbox[1],sbox[ord('a')]
for k in xrange(len(sbox)):
    sbox[k] = (sbox[k] - 1) % 128
sbox[ord('a')],sbox[0] = sbox[0],sbox[ord('a')]

print "\n[*] Reconstructed LEVEL TWO SBOX"
print sbox 

This is the salted S-box from the server:

[86, 3, 13, 122, 14, 2, 75, 28, 29, 5, 77, 19, 34, 6, 74, 8, 83, 38, 127, 41, 40, 15, 1, 31, 89, 88, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 46, 32, 76, 36, 78, 79, 80, 81, 82, 42, 84, 85, 26, 87, 51, 50, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 43, 123, 124, 125, 126, 44, 0, 48, 49, 27, 4, 35, 39, 7, 45, 9, 10, 11, 12, 33, 30, 47, 16, 17, 18, 37, 20, 21, 22, 23, 24, 25]

Once we got this, we have to calculate the key length being used. The server code does a mod operation over the S-box list for each character of key, this actually rotates the S-box as per key length. So from each element in list, subracting its index, we found that most elements differed by 26, which is actually our key length. A simple rotation with key length will show how it works.

[0, 48, 49, 27, 4, 35, 39, 7, 45, 9, 10, 11, 12, 33, 30, 47, 16, 17, 18, 37, 20, 21, 22, 23, 24, 25, 86, 3, 13, 122, 14, 2, 75, 28, 29, 5, 77, 19, 34, 6, 74, 8, 83, 38, 127, 41, 40, 15, 1, 31, 89, 88, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 46, 32, 76, 36, 78, 79, 80, 81, 82, 42, 84, 85, 26, 87, 51, 50, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 43, 123, 124, 125, 126, 44]

As we can see most elements are in its respective positions when the salted S-box is rotated with key length. Next task is to find the key, this is where we got stuck. We couldn't figure out the exact way to find the flag from the available data. Finally we came up with a code which found keys when they are smaller and doesn't have any repeated characters. Heres is the part of the code:

sboxes=[]
for i in range(max_len-1, -1, -1):
    for j in xrange(len(sbox)):
        sbox[j] = (sbox[j] - 1) % 128
    ret = sbox[i] - i
    print "\n[*] SBOX Stages: ",i
    print sbox  
    sboxes.append(sbox[::])   
    sbox[ret],sbox[i] = sbox[i],sbox[ret]

flag = ''
for index,sbox in enumerate(sboxes[::-1]):
    num = sbox[index]-index
    if num > 31 and num < 127:
        flag += chr(num)

The key we got from server is <i**t*1**k3**l**9*e***g*?> ('*' represents unfound characters). Also the stage 0 of reconstructed S-box gives clue of repeating characters. Characters other than repeating ones were in place

[60, 1, 2, 3, 4, 5, 6, 115, 96, 9, 10, 11, 12, 13, 14, 15, 16, 8, 18, 110, 48, 21, 22, 104, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 20, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 0, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 17, 97, 98, 99, 100, 101, 102, 103, 23, 105, 106, 107, 108, 109, 19, 111, 112, 113, 114, 7, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127]

>>> len("<i**t*1**k3**l**9*e***g*?>")
26
>>> chr(115)
's'
>>> chr(96)
'`'
>>> chr(110)
'n'
>>> chr(48)
'0'
>>> chr(104)
'h'

We have partial key and some other data to work with. Then our teammate rdy started looking into this with his Beautiful Mind eyes, hunting for combinations and sensible meanings. We soon figured out the key: <is`th1s`k3y`l0n9`en0ugh?>