Skip to content

Instantly share code, notes, and snippets.

@jahabrewer

jahabrewer/scantegrity.py

Created December 12, 2016 17:28
Show Gist options
  • Save jahabrewer/f3662cb5a884a0983e8c655e9df2d86e to your computer and use it in GitHub Desktop.
Save jahabrewer/f3662cb5a884a0983e8c655e9df2d86e to your computer and use it in GitHub Desktop.
Download ZIP
(poor, bad, not crypto safe, DO NOT USE) Scantegrity II prototype
Raw
scantegrity.py
import random
import csv
import sys
import hashlib
from Crypto.Hash import SHA256, HMAC
import binascii
salt = '2hiy2EMaM693EEpwGXqZssSd2yCOABYWCB'
pbkdf_rounds = 100000
def subkey(base_key, key_id):
concat_key = base_key + '|' + key_id
derived_key = hashlib.pbkdf2_hmac('sha256', concat_key, salt, pbkdf_rounds)
return derived_key
def commit(key, message):
if not isinstance(message, basestring):
message = str(message)
hmac = HMAC.new(key, message, SHA256)
return hmac.hexdigest()
# parameters
num_ballots = 4
num_candidates = 2
candidates = ['YES','NO']
code_alphabet = 'ABCDEFGHJKLMNPQRSTUVWXYZ0123456789'
code_length = 3
master_key = '73a86bc4ef510c4e15b4abcf0f3d131fa389272060ee19706ccc7b3aaa95db43'
num_backends = 2
table_q = []
table_r = []
table_s = []
# not crypto safe, but python's csprng doesn't take a seed
random.seed(master_key)
samples = random.sample(range(1000,10000), 2*num_ballots*num_candidates)
for i_ballot in range(num_ballots):
alpha = i_ballot
beta = samples[i_ballot*2]
gamma = samples[i_ballot*2 + 1]
for i_candidate in range(num_candidates):
code = [random.choice(code_alphabet) for j in range(code_length)]
code = ''.join(code)
table_q.append( [alpha, beta, gamma, code] )
table_r.append([0])
table_s.append([candidates[i_candidate]])
csv_writer = csv.writer(sys.stdout)
print 'Q'
for row in table_q:
csv_writer.writerow(row)
print 'R'
for row in table_r:
csv_writer.writerow(row)
print 'S'
for row in table_s:
csv_writer.writerow(row)
# generate permutations
pi = []
for i_backend in range(num_backends):
for i in range(3):
derived_key = subkey(master_key, str(i) + '|' + str(i_backend))
random.seed(derived_key)
perm = range(num_ballots*num_candidates)
random.shuffle(perm)
pi.append(perm)
print 'perms'
for row in pi:
csv_writer.writerow(row)
# shuffle Q and S
for i_backend in range(num_backends):
table_q_shuf = []
table_s_shuf = []
pi_index = i_backend * 3
a = pi[pi_index]
b = pi[pi_index + 1]
c = pi[pi_index + 2]
for i_shuf in a:
table_q_shuf.append(table_q[i_shuf])
# compose the three shufs
s_shuf_vector = [c[b[a[i]]] for i in range(len(a))]
for i_shuf in s_shuf_vector:
table_s_shuf.append(table_s[i_shuf])
print 'Q\' - backend ' + str(i_backend)
for row in table_q_shuf:
csv_writer.writerow(row)
print 'S\'\'\' - backend ' + str(i_backend)
for row in table_s_shuf:
csv_writer.writerow(row)
# commit to Q' and S'''
q_shuf_bar = []
s_shuf_bar = []
pi_bar = []
for j in range(num_ballots*num_candidates):
alpha_subkey = subkey(master_key, "alpha"+str(i_backend)+str(j))
alpha_bar = commit(alpha_subkey, table_q_shuf[j][0])
beta_subkey = subkey(master_key, "beta"+str(i_backend)+str(j))
beta_bar = commit(beta_subkey, table_q_shuf[j][1])
gamma_subkey = subkey(master_key, "gamma"+str(i_backend)+str(j))
gamma_bar = commit(gamma_subkey, table_q_shuf[j][2])
code_subkey = subkey(master_key, "q"+str(i_backend)+str(j))
code_bar = commit(code_subkey, table_q_shuf[j][3])
s_subkey = subkey(master_key, "s"+str(i_backend)+str(j))
s_bar = commit(s_subkey, table_s_shuf[j])
q_shuf_bar.append([alpha_bar, beta_bar, gamma_bar, code_bar])
s_shuf_bar.append([s_bar])
pi_bar_row = []
for h in range(3):
pi_subkey = subkey(master_key,"pi"+str(h)+str(i_backend)+str(j))
pi_bar_row.append(commit(pi_subkey, pi[pi_index + h][j]))
pi_bar.append(pi_bar_row)
# commitments
print 'Q-bar\''
for row in q_shuf_bar:
csv_writer.writerow(row)
print 'S-bar\'\'\''
for row in s_shuf_bar:
csv_writer.writerow(row)
print 'pi-bar'
for row in pi_bar:
csv_writer.writerow(row)
# ask user for updated R
marks = []
while len(marks) != num_candidates * num_ballots:
raw_marks = raw_input('Marks (e.g., "0,0,0,0,1,0,0,1"): ')
marks = raw_marks.split(',')
# show R''
for i_backend in range(num_backends):
pi_index = i_backend * 3
a = pi[pi_index]
b = pi[pi_index + 1]
r_shuf_vector = [b[a[i]] for i in range(len(a))]
r_shuf = [marks[i] for i in r_shuf_vector]
print 'R\'\' - backend ' + str(i_backend)
for row in r_shuf:
csv_writer.writerow(row)
# audit
for i_backend in range(num_backends):
pi_index = i_backend*3
coin_toss = i_backend % 2
if coin_toss == 0:
print 'pi2 for backend', i_backend
csv_writer.writerow(pi[pi_index+1])
print 'backend', i_backend, 'will audit Q\' -> R\'\''
print 'commitment subkeys'
print 'alpha,beta,gamma,q,pi2'
for j in range(num_candidates*num_ballots):
alpha_subkey = subkey(master_key, "alpha"+str(i_backend)+str(j))
beta_subkey = subkey(master_key, "beta"+str(i_backend)+str(j))
gamma_subkey = subkey(master_key, "gamma"+str(i_backend)+str(j))
code_subkey = subkey(master_key, "q"+str(i_backend)+str(j))
# only regen subkey for 2nd permutation, which has index 1
pi_subkey = subkey(master_key,"pi"+str(1)+str(i_backend)+str(j))
csv_writer.writerow([binascii.hexlify(x) for x in [alpha_subkey,beta_subkey,gamma_subkey,code_subkey,pi_subkey]])
elif coin_toss == 1:
print 'pi3 for backend', i_backend
csv_writer.writerow(pi[pi_index+2])
print 'backend', i_backend, 'will audit R\'\' -> S\'\'\''
print 'commitment subkeys'
print 's,pi3'
for j in range(num_candidates*num_ballots):
s_subkey = subkey(master_key, "s"+str(i_backend)+str(j))
# only regen subkey for 3rd permutation, which has index 2
pi_subkey = subkey(master_key,"pi"+str(2)+str(i_backend)+str(j))
csv_writer.writerow([binascii.hexlify(x) for x in [s_subkey,pi_subkey]])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment