sstic2020_step6_invert.py

#!/usr/bin/env python2
import gmpy


# MODULAR QUADRATIC EQUATION SOLVER ############################################
def compute_next_sqrt(prev_sqrt, x, N):
    if x % (2**N) == (prev_sqrt * prev_sqrt) % (2**N):
        return prev_sqrt
    elif (2**(N - 1) + x) % (2**N) == (prev_sqrt * prev_sqrt) % (2**N):
        return 2**(N-2) - prev_sqrt
    else:
        print('oops')
        exit(1)

def modsqrt(x, N):
    val = 1
    for i in range(4, N + 1):
        val = compute_next_sqrt(val, x, i)
    return val

def solve_modquadratic(c):
    a = 0x854e9fb4699ed8f22fd89ebe3f17f7f6
    b = 0xd677105721b51a080288a52f7aa48517

    DELTA = b * b - 4 * a * c
    alpha = a / 2
    N = 128+3

    alpha_inv = int(gmpy.invert(alpha, 2**N))
    delta = modsqrt(DELTA, N)
    x1 = ((-b + delta)*alpha_inv/(2**2)) % (2**64)
    x2 = ((-b - delta)*alpha_inv/(2**2)) % (2**64)
    x3 = ((-b +  (2**(128-1) + delta)   )*alpha_inv/(2**2)) % (2**64)
    x4 = ((-b +  (2**(128-1) - delta)   )*alpha_inv/(2**2)) % (2**64)

    return (x1, x2)


# UPDATEVAL ####################################################################
def do_updateval(updateval):
    reroot = 0x5245205230305421

    for i in range(64):
        var1 = updateval & reroot
        var2 = var1
        for j in range(1, 64):
            var2 = var2 ^ ((var1 >> j) & 0xffffffffffffffff)
        updateval = (updateval >> 1) | ((var2 << 0x3f) & 0xffffffffffffffff)

    return updateval


def gen_updatevals(start_updateval):
    updatevals = [do_updateval(start_updateval)]
    for i in range(1, 32):
        updatevals.append(do_updateval(updatevals[i - 1]))

    return updatevals


# UTILS ########################################################################
def print_if_printable(string):
    for char in string:
        if ord(char) < 0x20 or ord(char) > 0x7f:
            return
    print(string)


# MAIN #########################################################################
#start_updateval = 0x7D49AEF29911BCAF
start_updateval = 0xB42CC50912EA7786
end_updateval = 0x099EB8BB96FF8580A
updatevals = gen_updatevals(start_updateval)
assert(end_updateval == updatevals[-1])

challenge_memory_values = [ 0xBD77247EFD5026120EC466DC0BF48F78, 0x42D91B8FD115E27863C53462655BCA4B, 0x2D4B53BD572BC0E509147E49720F2DBB, 0x9B0656AF78A7CCC5FA58ECE282AFB5BC, 0x9A58B3845230BCCDA2D68691B0F85CD3, 0x7AACC07CC54BE008851A06A6882974D4, 0x10D4DBA09B5D1C148B11EFF397A19205, 0x3D66028DE2A301537EB6A37E0A7D9578, 0xEB0BA52C2D94D5E994A0FD02953CA525, 0xBFF717B395416071B54CD1E19274B4D8, 0x09BD86249E977C79655D20569DCD3571, 0x858E2D7034EA8DBDA7097DDF36428E2A, 0x90650EDF445FD692FAEC1AE30936F9C4, 0xD6F457E826D92CD3B122417D728927B3, 0x75863546676FC6615A15F2C6C09F4933, 0xAC530B4036B0AFCD3E21EA92B858F6A9, 0x9189E739289CEA74276B13D26DBE09B4, 0x5BDDAAE22D5F3DA9B536582CB9A17298, 0xBCE46085EA23920E095E54F51316397F, 0xD7D98A01C0DFE62BB863FD73F98EBE62, 0x45884FAA578E3CA131CBEF423EA3F68C, 0xBB8476D9103C116AF663106A9E2DB2F4, 0x8B656CF9792301C29A786BAD639C3919, 0x3BD1AF68A64ADFA69329E9995FFE9C37, 0x348912D16CDFF19B53632544E24155CC, 0xC1E6D58E626E0B544310B623021C4E9F, 0x0DF3FD6B4949300E52D624E02E1DCEB0, 0x38095B8DCA7F3080760F2E79D4DEAD87, 0x50B94C75C93671A2CE180634059D9800, 0x5790098E78097C66F47F1833A8329758, 0x98F6D5A0E9039AF0B549FBED480C324C, 0x39426851D22DDF6C6D3DD9627DE11F8C ]

memory_values = challenge_memory_values


# these values are derived from initial randomval in the binary
xor_values = [ 0xc9c5032724e9488a, 0xdf5e047488d9b088, 0x573d11fbd9edccb8, 0xf0df4f17f6b9a0f2, 0xe72c7a5d270e8d9e, 0xdb35ef5c16d97f14, 0x46f788162474e74d, 0xd1a4f97c583b681a, 0xdd89f3fbab633d07, 0xbbf44beb08a09f3d, 0x8510019582d0238d, 0x12e0aac60d84eab2, 0xea9cd675a7bd39b5, 0x8ade103b3ad91825, 0x87ae0734f03c1b16, 0x70b177b255029440, 0xda9d7ba675914fb0, 0xfbf4344a28020d3d, 0xf0a3f936583a27c4, 0x90bd50e3f8795ff4, 0x5def899da5ecb6db, 0x9180628960520b84, 0x194abcd56426e72c, 0x4ab2805d0cf267eb, 0xb2b7f3627b203384, 0x90506d9e8256e5fa, 0xaa9fba88519fa0ce, 0x454356ba804c583e, 0x98241768c093d034, 0x8607259ac40eca39, 0xd891c496729af0d6, 0x97bbd6588154582e ]


# message parts are not sent in order, but since they're all independant we can juste invert all tables using the predefined order, which was based on the initial randomval
inversion_table = [ 16, 5, 10, 14, 23, 11, 25, 29, 2, 13, 22, 17, 1, 21, 19, 18, 7, 27, 26, 30, 28, 24, 15, 3, 6, 31, 9, 12, 0, 8, 20, 4 ]
updatevals2 = updatevals[:]
for i in range(len(inversion_table)):
    updatevals2[i] = updatevals[inversion_table[i]]
updatevals = updatevals2

memory_values2 = memory_values[:]
for i in range(len(inversion_table)):
    memory_values2[i] = memory_values[inversion_table[i]]
memory_values = memory_values2

xor_values2 = xor_values[:]
for i in range(len(inversion_table)):
    xor_values2[i] = xor_values[inversion_table[i]]
xor_values = xor_values2


add_table = [0x0, 0x80, 0x8000, 0x8080, 0x800000, 0x800080, 0x808000, 0x808080, 0x80000000, 0x80000080, 0x80008000, 0x80008080, 0x80800000, 0x80800080, 0x80808000, 0x80808080, 0x8000000000, 0x8000000080, 0x8000008000, 0x8000008080, 0x8000800000, 0x8000800080, 0x8000808000, 0x8000808080, 0x8080000000, 0x8080000080, 0x8080008000, 0x8080008080, 0x8080800000, 0x8080800080, 0x8080808000, 0x8080808080]


for msg_nb in range(len(memory_values)):
    xs = solve_modquadratic(-memory_values[msg_nb])

    for x in xs:
        for xorval in range(256):
            val = x ^ updatevals[msg_nb]
            for i in range(8):
                val = val ^ (xorval << (i*8))
                xorval = ((xorval << 1) & 0xfe) | (xorval >> 7)
            candidate = val ^ xor_values[msg_nb]

            out = ""
            for bla in range(8):
                out += chr( (((candidate >> 8 * bla) & 0xff) + ((add_table[msg_nb] >> bla * 8) & 0xff)) & 0xff )
            print_if_printable(out)