pset3-salsa-distinguisher.py

import salsa20
#   import the distinguisher function and B and r paramaters from my_salsa
#   B: number of 64-byte blocks to generate
#   r: number of Salsa20 rounds
from distinguish import distinguish, B, r, random_dist
import os
from struct import pack, unpack
import numpy as np
import matplotlib.pyplot as plt
import time

"""
    `distinguish` should take a list of `B` 64-byte ciphertext blocks as
    a parameter and return `0` if it determines the bytes are output of Salsa20
    or `1` if the bytes are random.
"""

labeled_salsa = False
labeled_random = False

def challenge_distinguisher():
    global labeled_salsa, labeled_random
    coin = ord(os.urandom(1)[0]) % 2
    ctxt_blocks = []
    if coin == 1:
        #   salsa bytes
        sk = os.urandom(32)
        #   initialization vector (nonce)
        iv = 0
        for i in range(B):
            salsa = salsa20.Salsa20(sk, pack("<Q", iv), r)
            ctxt = salsa.encrypt('\x00'*64)
            ctxt_blocks.append(ctxt)
            iv += 1
    else:
        #   random bytes
        for i in range(B):
            ctxt_blocks.append(os.urandom(64))

    is_salsa, chisq = distinguish(ctxt_blocks)

    if coin == 1:
        if not labeled_salsa:
            plt.axvline(chisq, color='b', label="Salsa Chi2 Samples")
            labeled_salsa = True
        else: plt.axvline(chisq, color='b')
    else:
        if not labeled_random:
            plt.axvline(chisq, color='r', label="Random Chi2 Samples")
            labeled_random = True
        else: plt.axvline(chisq, color='r')

    if is_salsa == coin:
        return True
    return False
    
if __name__ == "__main__":
    start_time = time.time()
    bins = np.linspace(150, 350, 50)
    print "Testing distinguisher for " + str(B) + " blocks of " + str(r) + "-round Salsa"
    trials = 20
    correct = 0
    for i in range(trials):
        if challenge_distinguisher():
            correct += 1
    print "Number of correct guesses: " + str(correct) + " out of " + str(trials)
    plt.hist(random_dist, bins, alpha=0.5, label='Random Chi2 Distribution', color='c')
    plt.legend(loc='upper right')
    plt.title('Chi2 Distribution of Random Samples')
    plt.suptitle(str(r) + ' Salsa Rounds; ' + str(B) + ' Blocks; ' + str(len(random_dist)) + ' Random Samples')
    plt.xlabel("Number of correct guesses: " + str(correct) + " out of " + str(trials))
    print("--- %s seconds ---" % (time.time() - start_time))
    plt.show()

pset3-salsa-z-distinguisher.py

import salsa20
import os
import math
from struct import pack
import numpy as np

B = 2048
N = 256 # number of possible bytes
r = 4
Ei = float(B)*64 / float(N)
SAMPLE_SIZE = 16384

random_dist = []
random_stddev = 0
random_mean = 0

def make_random_dist(sample_size):
    print 'Building a Random Distribution with', SAMPLE_SIZE, 'samples'

    global random_dist, random_stddev, random_mean
    for r in range(sample_size):
        if r%50==0: print r
        random_blocks = [os.urandom(64) for i in range(B)]
        char_counts = []
        for i in range(N):
            char_counts.append(sum([block.count(chr(i)) for block in random_blocks]))
        random_chisq = sum([((Ei-float(char_count))**float(2)/Ei) for char_count in char_counts])
        random_dist.append(random_chisq)
    random_stddev = np.std(np.array(random_dist))
    random_mean = np.mean(np.array(random_dist))

    print 'Random Mean:', random_mean
    print 'Random StdD:', random_stddev

def distinguish(blocks):
    if len(random_dist) < 1: make_random_dist(SAMPLE_SIZE)
    threshold = 3 * random_stddev

    chisq = 0
    for i in range(N):
        count = 0
        for j in range(len(blocks)):
            count += blocks[j].count(chr(i))
        chisq += ((Ei - count)**2) / Ei
    is_salsa = math.fabs(chisq - random_mean) >= threshold
    return (is_salsa, chisq)