NSUCRYPTO 2018 - Problem 4 - TwinPeaks2 - Slide attack

TwinPeaks2_slide_attack.py

"""
Slide attack on the TwinPeaks2 cipher from NSUCRYPTO.

Disclaimer: this is not an optimal solution, just a proof-of-concept!

An actual solution is to note that Reverse(Encrypt(Reverse(x)) = Decrypt(x), where Reverse(a,b,c,d) = (d,c,b,a).
"""

from random import shuffle, randint

def xor(c1, c2):
    return [a ^ b for a, b in zip(c1, c2)]

def unpack(s):
    return [int(s[i:i+8], 16) for i in xrange(0, 32, 8)]

def pack(m):
    return "".join("%08X" % x for x in m)

def oracle(x):
    x = E(x)
    return x

def S(x):
    for i in xrange(3):
        x = (x * 0xdeadbeef) % 2**N
        x ^= (x >> (N/2))
        x += 0xaaaaaaaa
        x %= 2**N
    return x

def F(b, c, d):
    m = S(b) ^ S(d) ^ S( ((b ^ d) & (c ^ MASK)) ^ c)
    return S(m)

def E(x):
    a, b, c, d = x
    for i in xrange(48):
        a, b, c, d = (
            b, c, d,
            a ^ F(b, c, d)
        )
    return a, b, c, d

if 1:
    N = 20
    H = N/2
    MASK = 2**N-1

    pt = [1, 2, 4, 8]
    ct = oracle(pt)

    target = pack(ct)

def oracle_F(b, c, d):
    pts1 = []
    pts2 = []
    for v in xrange(2**H):
        pt = v,b,c,d
        pts1.append(pt)
        pt = b,c,d,v<<H
        pts2.append(pt)

    cts1 = map(oracle, pts1)
    cts2 = map(oracle, pts2)

    table = {}
    for i, ct in enumerate(cts1):
        key = tuple(ct[1:])
        assert key not in table
        table[key] = i

    for j, ct in enumerate(cts2):
        key = tuple(ct[:3])
        if key in table:
            i = table[key]
            # print i, j, ":", cts1[i], cts2[j]
            a,b,c,d = cts1[i]
            b,c,d,af = cts2[j]

            assert F(b,c,d) == a ^ af
            # print "BCD", b, c, d, ":", a^af
            a,b,c,d = pts1[i]
            b,c,d,af = pts2[j]

            assert F(b,c,d) == a ^ af
            # print "BCD", b, c, d, ":", a^af
            return a ^ af

a, b, c, d = unpack(target)
for i in xrange(48):
    print i
    a, b, c, d = (
        d ^ oracle_F(a, b, c),
        a, b, c
    )

print a, b, c, d