(poor, bad, not crypto safe, DO NOT USE) Scantegrity II prototype

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]])