cascade.py 6.57 KB
   1
   2
   3
   4
   5
   6
   7
   8
   9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66
  67
  68
  69
  70
  71
  72
  73
  74
  75
  76
  77
  78
  79
  80
  81
  82
  83
  84
  85
  86
  87
  88
  89
  90
  91
  92
  93
  94
  95
  96
  97
  98
  99
 100
 101
 102
 103
 104
 105
 106
 107
 108
 109
 110
 111
 112
 113
 114
 115
 116
 117
 118
 119
 120
 121
 122
 123
 124
 125
 126
 127
 128
 129
 130
 131
 132
 133
 134
 135
 136
# Author: Brice Colombier
# Laboratoire Hubert Curien
# 42000 Saint-Etienne - France
# Contact: b.colombier@univ-st-etienne.fr
# Project: CASCADE
# File: cascade.py
# Date : 2016-10-12

from binary_par import binary_par
from parity import parity
from split import split
from get_parities_from_indices import get_parities_from_indices
from flip_bits import flip_bits
from flatten import flatten
from random import shuffle
from swap_blocks import swap_blocks


def cascade(reference_response, error_rate, nb_passes, response_on_board, initial_block_size=0):
"""Implementation of the CASCADE reconciliation protocol"""

powers = [2**i for i in range(12)] # Up to 512-bit responses
if (not len(reference_response) in powers):
raise ValueError('Message length is not a power of two or is too large')

if not initial_block_size:
# Initialize the block size
block_size = 0.5/error_rate
# Round the block size to the closest lower power of 2
diff = [x - block_size for x in powers]
block_size = min(powers[diff.index(min([x for x in diff if x > 0]))], len(reference_response))
block_size = int(block_size/2)
elif initial_block_size in powers:
block_size = initial_block_size/2
else:
raise ValueError("Illegal block size")
even_parity_blocks = []
odd_parity_blocks = []
indices_to_flip = []

indices = list(range(len(reference_response)))

for passe in range(0, nb_passes):
block_size_increased = False
if block_size < len(reference_response)/2:
block_size *= 2
block_size_increased = True
print "Pass :", passe, ", block size", block_size
reference_response_indexed = zip(indices, reference_response)
if passe > 0:
shuffle(reference_response_indexed)
indices, reference_response = [list(i) for i in zip(*reference_response_indexed)]

split(reference_response, block_size)
split(indices, block_size)
parities = get_parities_from_indices(indices, response_on_board)
blocks_to_correct = []
reference_response_to_correct = []
for block_index, (reference_response_block, block_parity) in enumerate(zip(reference_response, parities)):
# Identify the blocks to correct with BINARY
# They have an odd relative parity
if parity(reference_response_block, block_parity):
if passe > 0:
odd_parity_blocks.append(indices[block_index])
reference_response_to_correct.append(reference_response_block)
blocks_to_correct.append(indices[block_index])
else:
if passe > 0:
even_parity_blocks.append(indices[block_index])
if blocks_to_correct:
# Narrow down to single bit errors
while len(blocks_to_correct[0]) > 2:
reference_response_to_correct, blocks_to_correct = binary_par(reference_response_to_correct, blocks_to_correct, response_on_board)
# Final BINARY execution where single PUF bits are queried from the board
_, indices_to_flip = binary_par(reference_response_to_correct, blocks_to_correct, response_on_board)
if passe > 0:
for index_to_flip in indices_to_flip:
# Move blocks from one group to the other if they contain the bit to flip
swap_blocks(even_parity_blocks, odd_parity_blocks, index_to_flip, block_size_increased, block_size)
else:
even_parity_blocks.extend(indices)
indices = flatten(indices)
reference_response = flatten(reference_response)
if blocks_to_correct:
# Error correction step
flip_bits(reference_response, indices_to_flip, indices)
print str(len(indices_to_flip)), "errors corrected before backtracking"
indices_to_flip = []
blocks_to_correct = []
if passe > 0:
# Backtracking process
while odd_parity_blocks:
backtracked_pos = 0
block_to_correct = min(odd_parity_blocks, key=len) # Get the smallest block
reference_response_block = [reference_response[indices.index(x)] for x in block_to_correct]
while len(block_to_correct) > 2:
[reference_response_block], [block_to_correct] = binary_par([reference_response_block], [block_to_correct], response_on_board)
# Final BINARY execution where single PUF bits are queried from the board
_, backtracked_pos = binary_par([reference_response_block], [block_to_correct], response_on_board)
# backtracked_pos = bi.binary(reference_response_block, block_to_correct, response_on_board)
flip_bits(reference_response, backtracked_pos, indices)
print "One more error corrected during backtracking"
# Move blocks from one group to the other if they contain the bit to flip
swap_blocks(even_parity_blocks, odd_parity_blocks, backtracked_pos[0])
if [x for x in even_parity_blocks if x in odd_parity_blocks]:
raise ValueError("Blocks are simultaneously in the even and odd group")
# Un-shuffle
_, reference_response = zip(*sorted(zip(indices, reference_response)))
return list(reference_response)

if __name__ == "__main__":
MSIZE = 256
ERROR_RATE = 0.02
NB_PASSES = 20
NB_ESSAIS = 1
INITIAL_BLOCK_SIZE = 4
for nb_essai in range(0, NB_ESSAIS):
response_on_board = list(reversed(128*[1, 0])) #sort LSB first
response_on_server = list(reversed(8*[0, 1]+120*[1, 0])) #sort LSB first
errors_location = [0 if a == b else 1 for (a, b) in zip(response_on_board, response_on_server)]
print "Errors at positions: ", [a for (a, b) in enumerate(errors_location) if b == 1]
response_on_server = cascade(response_on_server,
ERROR_RATE,
NB_PASSES,
response_on_board,
INITIAL_BLOCK_SIZE)

if response_on_server == response_on_board:
print("Correction successfull !\n------------------------\n")
else:
errors_location = [0 if a == b else 1 for (a, b) in zip(response_on_board, response_on_server)]
print "Errors at positions: ", [a for (a, b) in enumerate(errors_location) if b == 1]