Mercredi 14/09

taktoy.py

sbox = [3, 14, 1, 10, 4, 9, 5, 6, 8, 11, 15, 2, 13, 12, 0, 7]
# sbox = [12, 5, 6, 11, 9, 0, 10, 13, 3, 14, 15, 8, 4, 7, 1, 2] # from PRESENT
xobs = [14, 2, 11, 0, 4, 6, 7, 15, 8, 5, 3, 9, 13, 12, 1, 10]


def round(msg, subkey):
    return sbox[msg ^ subkey]


def enc(msg, key):
    t0 = round(msg, key[0])
    t1 = round(t0, key[1])
    return t1


def simplified_enc(msg, key):
    t0 = round(msg, key[0])
    return t0 ^ key[1]

diff.py

from random import choice, randint
import taktoy

debug = True


def compute_differential_characteristics():
    sbox_dc = [[0 for _ in range(0, 16)] for _ in range(0, 16)]
    for a in range(0, 16):
        for b in range(0, 16):
            sbox_dc[a ^ b][taktoy.sbox[a] ^ taktoy.sbox[b]] += 1
    if debug:
        print("\n> XOR differential table:")
        print("     ", end="")
        for i in range(0, 16):
            print("%2x " % i, end="")
        print("\n   +-", end="")
        for i in range(0, 16):
            print("---", end="")
        for i in range(0, 16):
            print("\n%2x | " % i, end="")
            for j in range(0, 16):
                print("%2d " % sbox_dc[i][j], end="")
    return sbox_dc


def get_most_probable_diff_sbox_io(dc):
    mpd = 0
    for i in range(1, 16):
        for j in range(1, 16):
            mpd = max(mpd, dc[i][j])
    if debug:
        print(f"\n> Most probable diff occurs {mpd} times\n")
        print("> Most probable diff I/O:")
    io = []
    for i in range(1, 16):
        for j in range(1, 16):
            if dc[i][j] == mpd:
                io.append((i, j))
                if debug:
                    print(f"{hex(i)[2:]} --> {hex(j)[2:]}")
    return io


def get_possible_intermediate_values(diff_io):
    di, do = diff_io
    if debug:
        print(f"\n> Selected diff: di={di} --> do={do}")
    piv = []  # probable intermediate values
    for a in range(0, 16):
        b = a ^ di
        if taktoy.sbox[a] ^ taktoy.sbox[b] == do:
            piv.append(a)
            if debug:
                print(
                    f"> Possible a ^ b --> S[a] ^ S[b]: {a} ^ {b} --> {taktoy.sbox[a]} ^ {taktoy.sbox[b]}.")
    return piv


def generate_pairs(count, di, key):
    pairs_rand = []
    pairs_diff = []
    for _ in range(0, count):
        m = randint(0, 15)
        c0 = taktoy.simplified_enc(m, key)
        pairs_rand.append((m, c0))
        md = m ^ di
        cd = taktoy.simplified_enc(md, key)
        pairs_diff.append((md, cd))
    return pairs_rand, pairs_diff


def find_good_pair(pairs_r, pairs_d, do):
    print(f"> Looking for a pair with output diff = {do}...")
    for i in range(0, len(pairs_r)):
        if pairs_r[i][1] ^ pairs_d[i][1] == do:
            if debug:
                print(f"> Found {pairs_r[i]}.")
            return pairs_r[i]
    print("> Cannot find good pair...")


def test_key(key, pairs):
    for p in pairs:
        if p[1] != taktoy.simplified_enc(p[0], key):
            return False
    return True


def attack(piv, m, c, pairs_r, pairs_d):
    for i in range(0, len(piv)):
        k0 = piv[i] ^ m
        k1 = taktoy.sbox[piv[i]] ^ c
        if test_key((k0, k1), pairs_r) and test_key((k0, k1), pairs_d):
            return k0, k1
    print("> Raté")


if __name__ == "__main__":
    dc = compute_differential_characteristics()
    mpd_io = get_most_probable_diff_sbox_io(dc)
    io = choice(mpd_io)
    piv = get_possible_intermediate_values(io)

    key = (randint(0, 15), randint(0, 15))
    print(f"KEY: {key}")
    pairs_r, pairs_d = generate_pairs(8, io[0], key)
    m, c = find_good_pair(pairs_r, pairs_d, io[1])

    k = attack(piv, m, c, pairs_r, pairs_d)
    print(f"ATTACK: {k}")