Created
January 13, 2020 22:24
-
-
Save aeyakovenko/b9dc730391ac2361b53a607a5317e41f to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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)])) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment