cascade.py 6.25 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
# Author: Brice Colombier
# Laboratoire Hubert Curien
# 42000 Saint-Etienne - France
# Contact: b.colombier@univ-st-etienne.fr
# Project: Demonstrator
# File: cascade.py
# Date : 2016-10-12

import binary_par as bi_par
import parity as par
import split as split
import flip_bits as fb
import flatten as fl
import random as rd
import swap_blocks as sb
import get_parities_from_indices as gpfi

def cascade(reference_response, error_rate, nb_passes, tclsh, board_manager, 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):
print "Passe:", passe
block_size_increased = False
if block_size < len(reference_response)/2:
block_size *= 2
block_size_increased = True
print "Block size:", block_size
reference_response_indexed = zip(indices, reference_response)
if passe > 0:
rd.shuffle(reference_response_indexed)
indices, reference_response = [list(i) for i in zip(*reference_response_indexed)]

split.split(reference_response, block_size)
split.split(indices, block_size)
parities = gpfi.get_parities_from_indices(indices, tclsh, board_manager, len(reference_response)*4)
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 par.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:
while len(blocks_to_correct[0]) > 2:
reference_response_to_correct, blocks_to_correct = bi_par.binary_par(reference_response_to_correct, blocks_to_correct, tclsh, board_manager, len(reference_response)*4)
# Final BINARY execution where single PUF bits are queried from the board
_, indices_to_flip = bi_par.binary_par(reference_response_to_correct, blocks_to_correct, tclsh, board_manager, len(reference_response)*4)
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
sb.swap_blocks(even_parity_blocks, odd_parity_blocks, index_to_flip, block_size_increased, block_size)
else:
even_parity_blocks.extend(indices)
indices = fl.flatten(indices)
reference_response = fl.flatten(reference_response)
print "Indices to flip", indices_to_flip
if blocks_to_correct:
# Error correction step
fb.flip_bits(reference_response, indices_to_flip, indices)
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] = bi_par.binary_par([reference_response_block], [block_to_correct], tclsh, board_manager)
# # Final BINARY execution where single PUF bits are queried from the board
# _, backtracked_pos = bi_par.binary_par([reference_response_block], [block_to_correct], tclsh, board_manager)
# # backtracked_pos = bi.binary(reference_response_block, block_to_correct, response_on_board)
# fb.flip_bits(reference_response, backtracked_pos, indices)
# # Move blocks from one group to the other if they contain the bit to flip
# sb.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 = 6
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

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]