HackYou CTF - Crypto 300 - UDP Hardcore Writeup

In this challenge we need to guess the secret key used by an encryption service running over UDP.

We get the source of the server-side.

The encryption algorithm uses a Sbox that is initialized with sequential numbers from 1 to 128:

SALTED_SBOX = list(range(128))

Then the secret key is mixed in the Sbox using element permutations:

add_key(SALTED_SBOX, KEY)

def add_key(sbox, k):
for i, c in enumerate(k):
sbox[i], sbox[ord(c)] = sbox[ord(c)], sbox[i]
for i in xrange(len(sbox)):
sbox[i] = (sbox[i] + 1) % 128
return

The packet format for this service is then one UDP packet per request as this:

[[C1][C2]..[Cn]] where n < 64

Command block is divided in 2 equals parts:

mid = len(data) >> 1
k = data[:mid].rstrip("\x00")
m = data[mid:].rstrip("\x00")

c = encrypt(SALTED_SBOX, k, m)
f.sendto(c.encode("hex"), addr)

One part, k, is used to mix more data in the Sbox part and the other part, m, is used for encryption

def encrypt(sbox, k, m):
sbox = sbox[::]
add_key(sbox, k)

c = ""
for ch in m:
c += chr(sbox[ord(ch)])
sbox = combine(sbox, sbox)
return c

The combine function is full of evil remix so we need to avoid it if we want to keep track of the state of the Sbox:

def combine(a, b):
ret = [-1] * len(b)
for i in range(len(b)):
ret[i] = a[b[i]]
return tuple(ret)

As the Sbox is copied over anew for each request (sbox = sbox[::]), if we send a single m part, we will avoid the combine.

So our strategy:
– Send 127 2-bytes packets with an empty k part (NUL character) and just one m part request to dump the Sbox from the server
– The dump will miss offset 0 of the Sbox so we use one add additionnal packet to swap offset 0 and 1 in the Sbox and request offset 1 again to fill in our local Sbox offset 0
– Revert the mixing algorithm using the dumped Sbox to recover the key

Source code:

#!/usr/bin/env python

import os, sys
import socket

host = sys.argv[1]

addr = (host, 7777)

s=socket.socket(socket.AF_INET,socket.SOCK_DGRAM)

sbox = list(range(128))

for i in xrange(1,128):

msg = chr(0) + chr(i)
s.sendto(msg,addr)
reply, addr = s.recvfrom(1024)
sbox[i] = ord(reply.decode("hex"))

msg = chr(1) + chr(1)
s.sendto(msg,addr)
reply, addr = s.recvfrom(1024)
sbox[0] = ord(reply.decode("hex")) - 1

print "Dumped Sbox=", repr(sbox)

local_sbox = list(range(128))

key_length = sbox[127]

print "Key length=", key_length + 1

for k in xrange(0,128):
sbox[k] = (sbox[k] - key_length - 1) % 128

flag = ''

i = 0
while i < key_length+1:
a = sbox[i]
if a:
c = local_sbox.index(a)
print "Position=", i, "Remote Sbox=", a, "Local Sbox offset=", c, "Char=", repr(chr(c))
flag = flag + chr(c)
local_sbox[i], local_sbox[c] = local_sbox[c], local_sbox[i]
for z in xrange(len(local_sbox)):
local_sbox[z] = (local_sbox[z] + 1) % 128
sbox[z] = (sbox[z] + 1) % 128
i = i + 1

print "flag=", flag

Run it:

Dumped Sbox= [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]
Key length= 26
Position= 0 Remote Sbox= 60 Local Sbox offset= 60 Char= '<'
Position= 1 Remote Sbox= 106 Local Sbox offset= 105 Char= 'i'
Position= 2 Remote Sbox= 117 Local Sbox offset= 115 Char= 's'
Position= 3 Remote Sbox= 99 Local Sbox offset= 96 Char= '`'
Position= 4 Remote Sbox= 120 Local Sbox offset= 116 Char= 't'
Position= 5 Remote Sbox= 109 Local Sbox offset= 104 Char= 'h'
Position= 6 Remote Sbox= 55 Local Sbox offset= 49 Char= '1'
Position= 7 Remote Sbox= 9 Local Sbox offset= 115 Char= 's'
Position= 8 Remote Sbox= 11 Local Sbox offset= 96 Char= '`'
Position= 9 Remote Sbox= 116 Local Sbox offset= 107 Char= 'k'
Position= 10 Remote Sbox= 61 Local Sbox offset= 51 Char= '3'
Position= 11 Remote Sbox= 4 Local Sbox offset= 121 Char= 'y'
Position= 12 Remote Sbox= 20 Local Sbox offset= 96 Char= '`'
Position= 13 Remote Sbox= 121 Local Sbox offset= 108 Char= 'l'
Position= 14 Remote Sbox= 62 Local Sbox offset= 48 Char= '0'
Position= 15 Remote Sbox= 125 Local Sbox offset= 110 Char= 'n'
Position= 16 Remote Sbox= 73 Local Sbox offset= 57 Char= '9'
Position= 17 Remote Sbox= 29 Local Sbox offset= 96 Char= '`'
Position= 18 Remote Sbox= 119 Local Sbox offset= 101 Char= 'e'
Position= 19 Remote Sbox= 34 Local Sbox offset= 110 Char= 'n'
Position= 20 Remote Sbox= 34 Local Sbox offset= 48 Char= '0'
Position= 21 Remote Sbox= 10 Local Sbox offset= 117 Char= 'u'
Position= 22 Remote Sbox= 125 Local Sbox offset= 103 Char= 'g'
Position= 23 Remote Sbox= 28 Local Sbox offset= 104 Char= 'h'
Position= 24 Remote Sbox= 87 Local Sbox offset= 63 Char= '?'
Position= 25 Remote Sbox= 87 Local Sbox offset= 62 Char= '>'
flag= <is`th1s`k3y`l0n9`en0ugh?>