ASIS CTF Quals 2017 - Almost leet

almost_leet.py

from sage.all import *

from itertools import product

def frombin(v):
    return int("".join(map(str, v)), 2 )

def l33tize(s, eight=False):
    ms = GL(8 if eight else 6, GF(2))
    while 1:
        # Wrap in random linear layers,
        # preserves APNness.
        # Wait when constraints satisfied
        l1 = ms.random_element().matrix()
        l2 = ms.random_element().matrix() if eight else (~l1)
        # matrix multiplication layers
        l1 = [frombin(l1 * vector(GF(2), x)) for x in product(range(2), repeat=l1.ncols())]
        l2 = [frombin(l2 * vector(GF(2), x)) for x in product(range(2), repeat=l2.ncols())]
        # wrap
        t = [l2[s[l1[x]]] for x in xrange(len(s))]
        # check
        if eight:
            t = [y ^ 0x90 for y in t]
            if " 13, 37, " in str(t):
                print "half-success"
                if min(t) == 0 and max(t) == 255:
                    print "full-success"
                    return t
        elif " 13, 37, " in str(t):
            print "success"
            return t

# 8-bit APN: x^3 is good, though not permutation
F = GF(2**8)
s = [(F.fetch_int(x)**3).integer_representation() for x in xrange(2**8)]

print "8bit:"
s = l33tize(s, eight=True)
print " ".join(map(str, s))
print

# 6-bit Butterfly APN involution 
# from https://eprint.iacr.org/2016/887.pdf
F = GF(2**3, name='a')

s = []
a = F.fetch_int(2)
for x, y in product(range(2**3), repeat=2):
    x = F.fetch_int(x)
    y = F.fetch_int(y)
    x += y**3
    x = x**5  # 5=1/3 (mod 7)
    x += a*y
    x, y = y, x
    x += a*y
    x = x**3
    x += y**3
    x = x.integer_representation()
    y = y.integer_representation()
    s.append((x << 3) | y)

print "6bit:"
s = l33tize(s)
print " ".join(map(str, s))

'''
$ time sage solve_simple.py
8bit:
half-success
half-success
half-success
full-success
144 16 148 7 224 113 127 253 124 125 174 188 100 116 45 46 59 113 20 77 113 42 197 141 47 228 214 14 13 215 111 166 243 118 124 234 158 10 138 13 37 33 124 107 32 53 226 228 140 195 40 116 219 133 228 169 162 108 208 13 157 66 116 184 0 5 107 125 39 51 215 208 192 68 125 234 143 26 169 47 36 235 100 184 57 231 226 47 28 82 138 215 105 54 100 40 16 16 240 227 42 59 81 83 234 107 220 78 184 40 21 150 224 42 43 242 224 59 176 120 226 169 255 167 138 208 12 69 105 157 36 195 37 192 243 5 176 197 43 77 148 240 148 227 108 82 10 39 26 53 231 219 77 242 253 81 83 253 120 197 255 14 57 219 174 78 243 0 28 108 12 111 37 68 174 220 46 21 195 235 69 111 51 10 53 143 14 167 54 157 150 46 167 214 133 231 188 220 5 118 82 162 166 69 33 192 78 188 45 150 36 140 12 166 158 39 32 26 255 214 105 66 45 21 66 54 235 140 68 33 118 0 141 120 242 20 227 7 7 240 28 162 158 51 32 143 57 133 43 20 127 83 127 81 176 141

6bit:
success
0 22 2 34 52 58 6 48 18 35 56 11 49 36 46 55 17 16 8 63 60 27 1 29 38 25 43 21 62 23 30 59 54 50 3 9 13 37 24 51 53 57 47 26 61 45 14 42 7 12 33 39 4 40 32 15 10 41 5 31 20 44 28 19

real    0m22.887s
user    0m22.592s
sys 0m0.340s

$ nc 66.172.33.77 13373
----------------------------------------
| Welcome to the private collection of |
|    Almost L33t Permutations (ALP)    |
----------------------------------------
Submit your permutation and get fame:
144 16 148 7 224 113 127 253 124 125 174 188 100 116 45 46 59 113 20 77 113 42 197 141 47 228 214 14 13 215 111 166 243 118 124 234 158 10 138 13 37 33 124 107 32 53 226 228 140 195 40 116 219 133 228 169 162 108 208 13 157 66 116 184 0 5 107 125 39 51 215 208 192 68 125 234 143 26 169 47 36 235 100 184 57 231 226 47 28 82 138 215 105 54 100 40 16 16 240 227 42 59 81 83 234 107 220 78 184 40 21 150 224 42 43 242 224 59 176 120 226 169 255 167 138 208 12 69 105 157 36 195 37 192 243 5 176 197 43 77 148 240 148 227 108 82 10 39 26 53 231 219 77 242 253 81 83 253 120 197 255 14 57 219 174 78 243 0 28 108 12 111 37 68 174 220 46 21 195 235 69 111 51 10 53 143 14 167 54 157 150 46 167 214 133 231 188 220 5 118 82 162 166 69 33 192 78 188 45 150 36 140 12 166 158 39 32 26 255 214 105 66 45 21 66 54 235 140 68 33 118 0 141 120 242 20 227 7 7 240 28 162 158 51 32 143 57 133 43 20 127 83 127 81 176 141
Huh! This is your first flag: ASIS{31GH7817_4PN_HA}

$ nc 66.172.33.77 13373
----------------------------------------
| Welcome to the private collection of |
|    Almost L33t Permutations (ALP)    |
----------------------------------------
Submit your permutation and get fame:
0 22 2 34 52 58 6 48 18 35 56 11 49 36 46 55 17 16 8 63 60 27 1 29 38 25 43 21 62 23 30 59 54 50 3 9 13 37 24 51 53 57 47 26 61 45 14 42 7 12 33 39 4 40 32 15 10 41 5 31 20 44 28 19
Somewhat good! This is your first part of flag: ASIS{4PN_P3RRMU74710N_D1M3N510N_S!X
Awesome! This is your second part of flag: _and_4PN_1NV0LUT10N?!@}
'''