xor_attack.py

import random

LEN = 200
NUM = LEN + LEN // 10

def one_hot(i):
    return [1 if i == x else 0 for x in range(NUM)]

def rand_vec(l):
    return [random.randint(0, 1) for _ in range(l)]

def xor(a, b):
    return [(a_i + b_i) % 2 for (a_i, b_i) in zip(a, b)]

def filter_xor(bitmask, bs):
    ret = [0 for _ in range(len(bs[0]))]
    for (bit, b) in zip(bitmask, bs):
        if bit == 1:
            ret = xor(ret, b)
    return ret

def break_xor(a, bs):
    desired = list(a)
    print("Desired vector: %s" % a)
    print("Given vectors:")
    for (i, b) in enumerate(bs):
        print("    %s: %s" % (i, b))

    ans = [0 for _ in range(LEN)]
    ans_mask = [0 for _ in range(NUM)]

    bs = [(one_hot(i), x) for (i, x) in enumerate (bs)]
    attack_set = []
    for i, v in enumerate(a):
        print("Solving for bit %s" % i)
        for b in bs:
            if b[1][i] == a[i]:
                ans = xor(ans, b[1])
                ans_mask = xor(ans_mask, b[0])
                a = xor(a, b[1])
                attack_set.append(b[1])
                break
        else:
            assert False

        new_bs = []
        while len(new_bs) < len(bs):
            bitmask = rand_vec(len(bs))
            b = filter_xor(bitmask, [x[1] for x in bs])
            if b[i] == 0:
                new_bs.append((filter_xor(bitmask, [x[0] for x in bs]), b))
        bs = new_bs

    assert desired == ans, "attack vector doesn't match"
    attack_result = [0 for _ in range(LEN)]
    for v in attack_set: 
        attack_result = xor(attack_result, v)
    assert desired == attack_result, "attack vector doesn't match"
    return (ans_mask, ans)

print(break_xor(rand_vec(LEN), [rand_vec(LEN) for i in range(NUM)]))