#!/usr/bin/env python
#
# test cases for Michael Vielhaber's paper
# ''Breaking ONE.FIVIUM by AIDA: an Algebraic IV Differential Attack''
# http://eprint.iacr.org/2007/413
# RIPEMD160(aida_onefivium.pdf)= a64c203b980217bbe2458df45efee43dd1b1ad33
#
# Written by Ralf-Philipp Weinmann.
# This code has been released into the public domain by its author.

import random
import sys

numTests = 1

class Trivium:
    def __init__(self, key, iv, keySetupClocks = 4 * 288):
        self.key = key
        self.iv = iv

        self.R = key + [0] * (93-len(key)) + iv + [0] * (84-len(iv)) + [0] * (111 - 3) + [1,1,1] 
        for c in range(keySetupClocks):
            self.clock()

    def clock(self):
        t1 = self.R[ 65] ^ self.R[ 92]
        t2 = self.R[161] ^ self.R[176]
        t3 = self.R[242] ^ self.R[287]
        z = t1 ^ t2 ^ t3
        t1 ^= (self.R[ 90] & self.R[ 91]) ^ self.R[170]
        t2 ^= (self.R[174] & self.R[175]) ^ self.R[263]
        t3 ^= (self.R[285] & self.R[286]) ^ self.R[ 68]
        self.R = [t3] + self.R[0:92] + [t1] + self.R[93:176] + [t2] + self.R[177:287]

        return z

# table from the paper
keyBitsApproximationsAIDA = [
    [[1], 597, [4, 7, 12, 15, 2, 56]],
    [[2, 65], 580, [4, 7, 12, 15, 8, 33]],
    [[3, 66], 580, [4, 7, 12, 15, 14, 32]],
    [[4], 579, [4, 7, 12, 15, 6, 47]],
    [[5], 577, [7, 12, 15, 1, 79]],
    [[6], 611, [4, 7, 12, 15, 41, 51]],
    [[8], 589, [4, 7, 12, 15, 23, 54]],
    [[9], 589, [4, 7, 12, 15, 36, 63]],
    [[11], 595, [4, 7, 12, 15, 24, 41]],
    [[14], 604, [4, 7, 12, 15, 21, 32]],
    [[16], 578, [4, 7, 12, 15, 77, 79]],
    [[17], 588, [4, 7, 12, 15, 20, 79]],
    [[19], 587, [4, 7, 12, 15, 23, 40]],
    [[25], 580, [4, 12, 15, 23, 49]],
    [[26], 580, [4, 12, 15, 22, 49]],
    [[27], 579, [4, 7, 12, 23, 48]],
    [[36], 583, [4, 7, 12, 34, 44]],
    [[38], 580, [7, 12, 15, 49, 55]],
    [[39], 578, [7, 12, 15, 52, 79]],
    [[55], 598, [4, 7, 12, 15, 51, 58]],
    [[56], 578, [4, 7, 12, 15, 26, 50]],
    [[57, 63], 588, [4, 7, 12, 14, 24]],
    [[59, 65], 612, [4, 7, 12, 15, 10, 41]],
    [[60, 66], 589, [4, 12, 15, 38, 48]],
    [[61], 587, [4, 7, 12, 15, 40, 74]],
    [[62], 604, [4, 7, 12, 15, 23, 75]],
    [[63], 604, [4, 7, 12, 15, 23, 74]],
    [[64], 597, [4, 7, 12, 15, 3, 30]],
    [[65], 580, [4, 7, 12, 15, 2, 33]],
    [[66], 580, [4, 7, 12, 15, 16, 34]],
    [[67], 596, [4, 7, 12, 15, 40, 65]],
    [[68], 596, [4, 7, 12, 15, 40, 64]],
    [[15], 581, [4, 28, 31, 79, 3, 47]],
    [[18], 600, [4, 28, 31, 79, 1, 69]],
    [[20], 598, [4, 28, 31, 79, 3, 50]],
    [[23], 625, [4, 28, 31, 79, 8, 12]],
    [[30], 606, [4, 28, 31, 79, 12, 46]],
    [[32], 606, [4, 28, 31, 79, 1, 17]],
    [[33], 591, [28, 31, 79, 2, 37]],
    [[35], 589, [4, 28, 31, 79, 14, 51]],
    [[58], 588, [4, 28, 31, 79, 35, 38]],
    [[21], 583, [2, 7, 8, 12, 19, 45]],
    [[22], 583, [2, 7, 8, 12, 20, 56]],
    [[10], 583, [2, 8, 80, 19, 43]],
    [[12], 582, [2, 8, 12, 80, 19, 44]],
    [[58], 607, [2, 8, 12, 80, 19, 71]],
    [[69], 579, [2, 8, 12, 80, 14, 49]]
]

################################################################################

def AIDAtest(key, approximations):
    aIndex = 0

    approxCorrect = [False] * len(approximations)

    for approx in approximations:
        keyBitsGuessed = approx[0]
        clockCycle = approx[1]
        bitsToVaryInIV = approx[2]
        
        keyBitSumGuessed = 0
        for i in range(2**len(bitsToVaryInIV)):
            IV = 80 * [0]
            bit = 0
            for bitToVary in bitsToVaryInIV:
                if bitToVary != None:
                    IV[bitToVary-1] = (i >> bit) & 1
                    bit += 1
                    
                    # we need to clock (clockCycle-1) times now to grab
                    # the output after clock 'clockCycle' (which starts from 1)
                    cipherInstance = Trivium(key, IV, clockCycle-1)
                    keyBitSumGuessed ^= cipherInstance.clock()

        keyBitSum = 0
        for keyBitIndex in keyBitsGuessed:
            if keyBitIndex != None:
                keyBitSum ^= key[keyBitIndex-1]
    
        approxCorrect[aIndex] = (keyBitSumGuessed == keyBitSum)
        print >> sys.stderr, "approximation for key bits", keyBitsGuessed, "is", approxCorrect[aIndex]
        aIndex += 1
    print >> sys.stderr, "iteration complete."
    return approxCorrect

################################################################################

counters = len(keyBitsApproximationsAIDA) * [0]

for i in range(numTests):
    key = [ int(random.getrandbits(1)) for i in range(80) if True ]
    result = AIDAtest(key, keyBitsApproximationsAIDA)

    for i in range(len(counters)):
        if result[i]:
            counters[i] += 1

print >> sys.stderr, "----------"

for i in range(len(counters)):
    print "approx. for key bits", keyBitsApproximationsAIDA[i][0], \
          "was correct", counters[i], "out of", numTests, "times"