0x00 Overview

Last weekend I played PBCTF on my own, and instead of binary challenges that I am quite good at, I tried to play some cryptography challenges. This is actually my first non-trivial Crypto challenge that I solved in CTF. Thus I think it is quite worthy to write a writeup to record. Interestingly, the intended approach to solve the challenges is by using slide attack, but I actually didn’t know this technique until I got the flag, which tells the technique I used is actually slide attack that has been a common cryptography technique.

0x01 Challenge

The encryption is a random one-to-one mapping within lowercase and `'_'` 2-letter domain (thus with size `27*27`).

``````def encrypt(message):
if len(message) % 2:
message += "_"

message = list(message)
rounds = int(2 * ceil(log(len(message), 2))) # The most secure amount of rounds

for round in range(rounds):
# Encrypt
for i in range(0, len(message), 2):
message[i:i+2] = S_box[''.join(message[i:i+2])]

# Shuffle, but not in the final round
if round < (rounds-1): # put all even indexes at front and all odd ones at end
message = [message[i] for i in range(len(message)) if i%2 == 0] + [message[i] for i in range(len(message)) if i%2 == 1]

return ''.join(message)
``````

We can also encrypt arbitrary content for at most 1500 times, and the encrypted flag is given. If we can crack the unknown key `S_box`, the flag can be figured out.

0x02 Solution

Let’s consider the case where `len(message) == 2`, in this case `rounds = 2`. The shuffle makes no effect because there is only 2 characters. Thus the overall effect of the encryption is just `S_box[S_box[message]]`, which is applying `S_box` for 2 times. Therefore, we can iterate over all `27*27` cases and get the box which represent `S_box` applied 2 times. Let’s call it `double_box`. Note that this `double_box` must also be one-to-one. Therefore, the goal is just figuring out the `S_box` given `double_box`.

The problem can be illustrated below, what we need to do is to find `??` for each 2-letter token.

``````             S_box                          S_box
aa           ----->           ??            ----->              c1 (known)
ab           ----->           ??            ----->              c2 (known)
...
__           ----->           ??            ----->              c2 (known)
``````

The idea is that we can simply guess each token at each position, for example, we can guess `ab` at the first position.

``````             S_box                          S_box
aa           ----->           ab            ----->              c1 (known)
ab           ----->           ??            ----->              c2 (known)
``````

The we can infer that `ab -> c1`:

``````             S_box                          S_box
aa           ----->           ab            ----->              c1 (known)
ab           ----->           c1            ----->              c2 (known)
``````

We then know `c1 -> c2`, so we can do this iteratively, until we reach some place that we have already visited before. This process is similar to the idea of slide attack. If there is conflict (e.i. the known cypher text does not match the previous token on that position), the initial guess should be wrong; otherwise the initial guesses are possible to be correct. We try to guess all possible tokens (e.i. `27*27`) for one particular position, since we know there must be one correct guess, we can have: if there is only one non-conflict guess among `27*27` trials, it must be the correct `S_box` mapping; if there are multiple non-conflict guesses, we are not sure which one is correct but the correct one must be one of these multiple non-conflict guesses.

Thus, we do this for all positions, we can actually recover most of the `S_box`. However there are still some unknown mappings. Therefore, my approach is record these multiple guesses (there are 32 in total in my case) and corresponding inference, and then try all of them to decrypt the cypher text. If we brute-force all possible cases, there are `32!` possibilities which is too large. My approach is to only consider valid ones by merging the inference mapping and only recording those that change the mapping and do not cause conflict. The full solution is shown below:

``````from string import ascii_lowercase
from itertools import product
from pwn import *
from math import log, ceil
context(log_level='debug')
ALPHABET = ascii_lowercase + "_"
bigrams = [''.join(bigram) for bigram in product(ALPHABET, repeat=2)]

def infer_given_map(double_box, first_map, idx):
single_box = dict()
single_box[bigrams[idx]] = first_map
mid = first_map
dst = double_box[bigrams[idx]]
while True:
if mid in single_box:
if single_box[mid] == dst: # and len(set(single_box.keys())) == 27*27:
return single_box
else:
return False
single_box[mid] = dst
old_mid = mid
mid = dst
dst = double_box[old_mid]

def merge_dict(dst, src):
for k in src:
if k in dst and src[k] != dst[k]:
return False
else:
dst[k] = src[k]
return True

def crack_double_map(double_box):
certain_box = dict()
possible_box = []
for i in range(0, 27*27):
guesses = []
for first_map in bigrams:
res = infer_given_map(double_box, first_map, i)
if res:
guesses.append(res)
if len(guesses) == 1:
r = merge_dict(certain_box, guesses[0])
assert r
else:
possible_box.append(guesses)
return certain_box, possible_box

def dump_data():
# sh = process("nc -x 127.0.0.1:1080 -X 5 queensarah2.chal.perfect.blue 1".split(' '))
sh = remote("queensarah2.chal.perfect.blue", 1)
sh.recvuntil("{'")
c_flag = sh.recvuntil("'}")[:-2]
assert len(c_flag) == 58
sh.recvuntil("> ")
double_box = {}
for x in bigrams:
sh.sendline(x)
sh.recvuntil("this:\n")
res = sh.recvuntil('\n')[:-1]
if len(res) != 2:
sh.interactive()
double_box[x] = res
sh.recvuntil("> ")
return double_box, c_flag

def shuffle_back(message):
assert len(message) % 2 == 0
ret = [None] * len(message)
half_len = len(message)//2
for i in range(0, half_len):
ret[i*2] = message[i]
ret[i*2+1] = message[half_len+i]
return ret

def map_with_default(box, key):
if key in box:
return box[key]
else:
return "??"

def decrypt(message, box):
assert len(message) % 2 == 0
message = list(message)
rounds = int(2 * ceil(log(len(message), 2)))

inv_box = {}
for k in box:
inv_box[box[k]] = k
# assert len(set(inv_box.keys())) == 27*27

for r in range(0, rounds):
if r != 0:
message = shuffle_back(message)
for i in range(0, len(message), 2):
message[i:i+2] = map_with_default(inv_box, ''.join(message[i:i+2]))

return ''.join(message)

def try_inc_boxes(certain_box, boxes):
ret = []
for box in boxes:
inc_certain_box = dict(certain_box)
r = merge_dict(inc_certain_box, box)
if r and len(inc_certain_box.keys()) != len(certain_box.keys()):
ret.append(inc_certain_box)
return ret

def find_all(certain_box, possible_box):
past_boxes = [certain_box]
for boxes in possible_box:
new_boxes = []
for past_box in past_boxes:
new_boxes += try_inc_boxes(past_box, boxes)
past_boxes += new_boxes
print(len(new_boxes))
return [box for box in past_boxes if len(box.keys()) == 27*27]

# print(dump_data())
double_box, c_flag = ({'gw': 'sv', 'gv': 'gy', 'gu': 'tf', 'gt': 'gc', 'gs': 'nr', 'gr': 'wq', 'gq': 'mq', 'gp': 'qe', 'gz': '_k', 'gy': 'cf', 'gx': 'at', 'gg': 'cn', 'gf': 'og', 'ge': 'vj', 'gd': 'md', 'gc': 'fa', 'gb': 'uj', 'ga': 'ds', 'go': 'fe', 'gn': 'xk', 'gm': 'bz', 'gl': 'wg', 'gk': 'cx', 'gj': 'c_', 'gi': 'fw', 'gh': 'aw', 'tz': 'to', 'tx': 'da', 'ty': 'xj', 'g_': 'bs', 'tw': 'tt', 'tt': 'en', 'tu': 'fr', 'tr': 'pu', 'rf': 'gb', 'tp': 'lw', 'tq': 'lb', 'tn': 'iw', 'to': 'bd', 'tl': 'io', 'tm': 'jr', 'tj': 'nt', 'tk': 'fh', 'th': 'ce', 'ti': 'ab', 'tf': 'eg', 'tg': 'qh', 'td': 'ba', 'te': 'mc', 'tb': 'wi', 'tc': 'wk', 'ta': 'zt', 'vu': 'zm', 'zl': 'ou', 'zm': 'im', 'zn': 'fz', 'zo': 'qt', 'zh': 'cz', 'zi': 'xl', 'zj': 'zi', 'zk': 'hu', 'zd': 'lv', 'ze': '_c', 'zf': 'xy', 'zg': 'dz', 'za': 'ka', 'zb': 'pd', 'zc': 'rw', 'zx': 'vi', 'zy': 'tw', 'zz': 'bi', 'zt': 'ac', 'zu': 'jl', 'zv': 'ec', 'zw': 'ub', 'zp': 'hh', 'zq': 'wf', 'zr': 'rg', 'zs': 'de', 't_': 'bg', 'z_': 'sa', 'o_': 'jm', 'tv': 'jp', 'wl': 'zu', 'va': 'mn', 'ts': 'om', 'vc': 'pl', 'wk': 'b_', 'vh': 'oz', 'wj': 'kl', 'vi': 'ii', 'vj': 'j_', 'vk': 'bj', 'vl': 'mi', 'vm': 'bw', 'wi': 'vl', 'vn': 'zf', 'm_': 'yc', 'vo': 'ew', 'me': 'tj', 'md': 'qn', 'mg': 'ho', 'mf': '_p', 'ma': 'kh', 'mc': 'qa', 'mb': 'kf', 'mm': 'ix', 'ml': 'zz', 'mo': 'ij', 'mn': 'ye', 'mi': 'ap', 'mh': 'xb', 'mk': 'oo', 'mj': 'be', 'mu': 'ms', 'mt': 'yl', 'mw': 'pq', 'mv': 'es', 'mq': 'xr', 'mp': 'dr', 'ms': 'px', 'mr': 'lk', 'vt': 'mk', 'my': 'xp', 'mx': 'vu', 'mz': 'bu', 'vv': 'xz', 'vw': 'gj', 'vx': 'sb', 'vz': 'jv', 'fp': 'bn', 'fq': 'vh', 'fr': 'fq', 'fs': 'pm', 'ft': 'je', 'fu': 'hn', 'fv': 'le', 'fw': 'vr', 'fx': 'ut', 'fy': 'ma', 'fz': 'za', 'fa': 'fg', 'fb': 'uv', 'fc': 'bh', 'fd': 'k_', 'fe': 'jc', 'ff': 'oe', 'fg': 'is', 'fh': 'ic', 'fi': '_i', 'fj': 'ag', 'fk': 'dd', 'fl': 'gx', 'fm': 'oj', 'fn': 'li', 'fo': 'mt', 'sz': '_g', 'sy': 'dy', 'ot': 'ls', 'ss': 'nq', 'sr': 'kz', 'sq': 're', 'sp': 'zk', 'sw': 'xc', 'sv': 'nb', 'su': 'vv', 'f_': 'ok', 'sk': 'tg', 'sj': 'xt', 'si': 'd_', 'sh': 'jy', 'so': 'ck', 'sn': 'du', 'sm': 'ct', 'sl': 'ax', 'sc': 'oc', 'sb': 'ob', 'sa': 'ip', 'sg': 'eb', 'sf': 's_', 'se': 'iq', 'sd': 'pj', '__': 'yh', 'l_': 'ua', 'lf': 'jb', 'lg': 'cd', 'ld': 'ws', 'le': 'l_', 'lb': 'uh', 'lc': 'dk', '_y': 'bf', 'la': 'qr', 'ln': 'ez', 'lo': 'vy', 'll': 'ph', 'lm': 'si', 'lj': 'os', 'lk': 'qs', 'lh': 'ne', 'li': 'jq', 'lv': 'xu', 'lw': 'st', 'lt': 'ti', 'lu': 'qx', 'lr': 'qm', 'ls': 'kj', 'lp': 'xf', 'lq': 'vq', '_g': 'nh', '_f': 'eu', '_e': 'cg', '_d': 'sx', 'lz': 'an', '_b': 'au', 'lx': 'np', 'ly': 'ux', 'wq': 'wv', 'yh': 'ai', 'yk': 'ug', 'yj': 'qj', 'ym': 'co', 'yl': 'ay', 'yo': 'sj', 'yn': 'hs', 'ya': 'zh', 'yc': 'pr', 'yb': 'mr', 'ye': 'pc', 'yd': 'pn', 'yg': 'vm', 'yf': 'ad', 'yy': 'ro', 'yx': '_h', 'yz': 'mw', 'yq': 'lx', 'yp': 'xw', 'ys': 'i_', 'yr': 'ny', 'yu': 'hp', 'yt': 'mb', 'yw': 'xv', 'yv': 'dv', 'y_': 'kq', 'em': 'tu', 'el': 'vd', 'eo': 'ft', 'en': 'ga', 'ei': 'no', 'eh': 'ig', 'ek': '_y', 'ej': 'ie', 'ee': 'ej', 'ed': '_d', 'eg': 'um', 'ef': 'by', 'ea': 'bb', 'ec': 'te', 'eb': 'jf', 'ey': 'yw', 'ex': 'il', 'ez': 'jx', 'eu': 'jd', 'et': 'gt', 'ew': 'pp', 'ev': 'rv', 'eq': 'rr', 'ep': 'fs', 'es': 'yn', 'er': 'oa', 'rt': 'rc', 'ru': 'sn', 'rv': 'ff', 'rw': 'hl', 'rp': 'ek', 'rq': 'ei', 'rr': 'zd', 'rs': 'nf', 'rx': '_e', 'ry': 'qc', 'rz': 'of', 'rd': 'ha', 're': 'lt', 'e_': 'lz', 'rg': 'fy', 'ra': 'sr', 'rb': 'me', 'rc': 'lm', 'rl': 'jg', 'rm': 'cb', 'rn': 'gl', 'ro': 'ex', 'rh': 'hw', 'ri': 'ib', 'rj': 'km', 'rk': 'gn', '_t': 'fv', 'n_': 'ur', 'xj': 'oy', 'xk': 'xm', 'xh': 'tm', 'xi': 'q_', 'xn': 'ey', 'xo': 'ss', 'xl': 'bc', 'xm': 'yf', 'xb': 'ym', 'xc': 'pt', 'xa': 'az', 'xf': 'cs', 'xg': 'vs', 'xd': 'hm', 'xe': 'uu', 'xz': 'qq', 'xx': 'zo', 'xy': 'yu', 'xr': 'ps', 'xs': 'cw', 'xp': 'rh', 'xq': 'dl', 'xv': 'h_', 'xw': 'x_', 'xt': 'ol', 'xu': '_q', 'wy': 'ww', 'x_': 'th', 'wh': 'my', 'wx': 'tc', 'sx': 'ed', '_s': 'tb', 'u_': 'ov', 'st': 'df', 'k_': 'xe', 'kc': 'dg', 'kb': 'uk', 'ka': 'yx', 'kg': 'dw', 'kf': 'tr', 'ke': 'bt', 'kd': 'zy', 'kk': 'qg', 'kj': 'bk', 'ki': 'ze', 'kh': 'pa', 'ko': 'pv', 'kn': 'gz', 'km': 'ql', 'kl': 'eq', 'ks': 'fp', 'kr': 'jo', 'kq': 'uo', 'kp': 'zj', 'kw': 'mh', 'kv': 'dp', 'ku': 'wa', 'kt': 'jn', 'kz': 'mg', 'ky': 'wl', 'kx': 'kd', 'dn': 'fc', 'do': 'uc', 'dl': 'tn', 'dm': 'pw', 'dj': 'wu', 'dk': 'va', 'dh': 'di', 'di': 'nn', 'df': 'cr', 'dg': 'ra', 'dd': 'ui', 'de': 'v_', 'db': 'ev', 'dc': 'kx', 'q_': 'sy', 'da': 'kn', 'dz': 'ts', 'dx': 'fo', 'dy': 'lr', 'dv': 'ku', 'dw': 'xg', 'dt': 'ht', 'du': '_t', 'dr': 'pe', 'ds': 'dn', 'dp': 'gg', 'dq': 'up', 'qq': '_w', 'qp': 'nv', 'qs': 'lc', 'qr': 'nd', 'qu': 'xq', 'qt': 'hj', 'qw': 'fu', 'qv': 'jw', 'qy': '__', 'qx': 'p_', 'qz': 'kv', '_z': 'fm', 'qa': 'yi', 'd_': 'la', 'qc': 'mx', 'qb': 'ot', 'qe': 'ue', 'qd': 'dq', 'qg': 'y_', 'qf': 'kk', 'qi': 'xh', 'qh': '_l', 'qk': 'rz', 'qj': 'ud', 'qm': 'ju', 'ql': 'ta', 'qo': 'zg', 'qn': 'qp', 'wc': 'f_', 'wb': 'ky', 'wa': 'wh', 'wo': 'vb', 'wn': 'ih', 'wm': '_s', 'wg': 'jk', 'wf': 'z_', 'we': 'nc', 'wd': 'wr', 'jx': 'ki', 'jy': 'py', 'jz': 'vk', 'jt': 'sc', 'ju': 'wy', 'jv': 'nx', 'jw': 'hi', 'jp': 'nm', 'jq': 'qk', 'jr': 'tl', 'js': 'bp', 'jl': 'in', 'jm': 'rs', 'jn': 'mm', 'jo': 'or', 'jh': 'xa', 'ji': 'pb', 'jj': '_n', 'jk': 'sp', 'jd': 'wx', 'je': 'bv', 'jf': 'dj', 'jg': 'hx', 'ja': 'db', 'jb': 'lg', 'jc': '_u', 'ww': 'gs', 'j_': 'yk', 'wv': 'yg', '_x': 'qf', 'wu': 'fj', '_w': 'eo', 'wt': '_r', '_v': 'qo', 'w_': 'na', 'ws': 'gh', '_u': 'zw', 'wr': 'sm', 'ck': 'yv', 'cj': 'cy', 'ci': 'tk', 'ch': 'xi', 'co': '_j', 'cn': '_o', 'cm': 'gr', 'cl': 'cp', 'cc': 'gu', 'cb': 'po', 'ca': 'lo', 'wp': 'n_', 'cg': 'zn', 'cf': 'qd', 'ce': 'kg', 'cd': 'un', 'cz': 'wd', 'cy': 'hz', 'cx': 'qi', '_q': 'tz', 'cs': 'vg', 'cr': 'nu', 'cq': 'iu', 'cp': 'ji', 'cw': 'wp', 'cv': 'ry', 'cu': 'tq', 'ct': 'wn', 'pr': 'yo', 'ps': 'gp', 'pp': 'he', 'pq': 'td', 'pv': '_v', 'pw': 'xn', 'pt': '_x', 'pu': 'vw', 'pz': 'ea', 'px': 'jz', 'py': 'lj', '_m': 'pf', 'wz': 'e_', 'pb': 'cj', 'pc': 'cu', 'pa': 'el', 'c_': 'et', 'pg': 'mj', 'pd': 'vf', 'pe': 'qv', 'pj': 'm_', 'pk': 've', 'ph': 'gf', 'pi': 'vc', 'pn': 'ly', 'po': 'nk', 'pl': 'rp', 'pm': 'jh', '_i': 'aq', '_h': 'hy', 's_': 'sd', '_r': 'op', '_c': 'kc', '_a': 'rd', 'iy': 'mp', 'ix': 'pz', 'vb': 'qu', 'iz': 'dx', 'vd': 'zc', 've': 'uz', 'vf': 'ng', 'vg': 'sw', 'iq': 'uf', 'ip': 'eh', 'is': 't_', 'ir': 'ks', 'iu': 'fn', 'it': 'rj', 'iw': 'dc', 'iv': 'kp', 'ii': 'we', 'ih': 'gd', 'ik': 'lu', 'ij': 'oq', 'im': 'js', 'il': 'ko', 'io': 'yt', 'in': 'wb', 'ia': 'ah', 'vy': 'af', 'ic': 'cq', 'ib': 'xo', 'ie': 'ge', 'id': '_m', 'ig': 'rf', 'if': 'pk', 'i_': 'kw', 'r_': 'ja', '_o': 'it', 'v_': 'ia', 'yi': 'fl', '_n': 'dh', 'vr': 'ox', '_l': 'zq', '_k': 'gq', '_j': 'cm', 'p_': 'ys', 'nv': 'us', 'ux': 'w_', 'vs': 'aj', 'bd': 'a_', 'be': 'cl', 'bf': 'hv', 'bg': 'nw', 'ba': 'vx', 'bb': 'o_', 'bc': 'sf', 'bl': 'gv', 'bm': 'vp', 'bn': 'jj', 'bo': 'rt', 'bh': 'kb', 'bi': 'ln', 'bj': 'gm', 'bk': 'yy', 'bt': '_f', 'bu': 'go', 'bv': 'pg', 'bw': 'aa', 'bp': 'jt', 'bq': 'mf', 'br': 'as', 'bs': 'ul', 'bx': 'sk', 'by': 'ar', 'bz': 'od', 'oo': 'id', 'on': 'ru', 'om': 'bq', 'ol': 'cc', 'ok': 'bx', 'oj': 'gi', 'oi': 'rl', 'oh': 'ca', 'og': 'zl', 'of': 'fd', 'oe': 'dm', 'od': 'wt', 'oc': 'ty', 'ob': 'yq', 'oa': 'br', 'oz': 'ao', 'oy': 'xx', 'ox': 'bm', 'ow': 'qz', 'ov': 'so', 'ou': 'vo', 'b_': 'rm', 'os': 'hk', 'or': 'ae', 'oq': 'qb', 'op': 'av', 'pf': 'iy', 'hz': 'sq', 'hx': 'tv', 'hy': 'ak', 'hr': 'zx', 'hs': 'dt', 'hp': 'mz', 'hq': 'g_', 'hv': 'rq', 'hw': 'yz', 'ht': 'vn', 'hu': 'ir', 'hj': 'zp', 'hk': '_b', 'hh': 'wj', 'hi': 'sh', 'hn': 'wz', 'ho': 'mu', 'hl': 'yd', 'hm': 'xs', 'hb': 'gk', 'hc': 'kt', 'ha': 'ni', 'hf': 'lp', 'hg': 'xd', 'hd': 'nz', 'he': 'll', '_p': 'yj', 'uy': 'zs', 'h_': 'fx', 'uz': 'hb', 'uu': 'hc', 'ut': 'qy', 'uw': 'am', 'uv': 'tx', 'uq': 'uw', 'up': 'zr', 'us': 'zv', 'ur': 'ml', 'um': 'gw', 'ul': 'mv', 'uo': 'ya', 'un': 'hf', 'ui': 'hr', 'uh': 'tp', 'uk': 'ef', 'uj': 'hg', 'ue': 'qw', 'ud': 'em', 'ug': 'ci', 'uf': 'sg', 'ua': 'zb', 'uc': 'rb', 'ub': 'yr', 'aa': 'ri', 'ac': 'wc', 'ab': 'yp', 'ae': 'fb', 'ad': 'nj', 'ag': 'fk', 'af': 'pi', 'ai': 'if', 'ah': 'r_', 'ak': 'vt', 'aj': 'ee', 'am': 'rk', 'al': 'mo', 'ao': 'u_', 'an': 'ik', 'aq': 'ke', 'ap': 'wo', 'as': 'uy', 'ar': 'lq', 'au': 'hd', 'at': 'bl', 'aw': 'iz', 'av': 'fi', 'ay': 'su', 'ax': 'on', 'az': 'oh', 'nh': 'vz', 'ni': 'ch', 'nj': 'uq', 'nk': 'ep', 'nl': 'hq', 'nm': 'rx', 'nn': 'se', 'no': '_z', 'na': 'ow', 'nb': 'wm', 'nc': 'nl', 'nd': 'al', 'ne': 'kr', 'nf': '_a', 'ng': 'ld', 'nx': 'lf', 'ny': 'rn', 'nz': 'yb', 'np': 'er', 'nq': 'bo', 'nr': 'lh', 'ns': 'sz', 'nt': 'do', 'nu': 'iv', 'a_': 'cv', 'nw': 'ns', 'vp': 'sl', 'vq': 'oi'}, 'aeq_tywjfkhowelwbmzsfufvhykieccelbszgsfha_xhkdksaqcmfjd_qh')
certain_box, possible_box = crack_double_map(double_box)

boxes = find_all(certain_box, possible_box)
print(len(boxes))
for certain_box in boxes:
print(decrypt(c_flag, certain_box))
``````

By browsing the output for a while, we can find the flag:

`slide_attack_still_relevant_for_home_rolled_crypto_systems`