Skip to content

Instantly share code, notes, and snippets.

@Thermi
Created January 7, 2018 01:21
Show Gist options
  • Save Thermi/05bc671436841670ac81b3b86217dd62 to your computer and use it in GitHub Desktop.
Save Thermi/05bc671436841670ac81b3b86217dd62 to your computer and use it in GitHub Desktop.
#! /bin/python3 -B
from fractions import Fraction
import pprint
class inputCase:
deltaX = 0
recursor = None
def __init__(self, deltaX, recursor):
self.deltaX = deltaX
self.recursor = recursor
def recurse(self):
self.recursor.recurse()
return self.recursor.ends
# the recursor needs access to the probability tables
class recursor:
branches = []
probabilityTables = None
ends = []
deltaX = 0
def recurse(self):
global maxNum
global sBoxes
for i,j in self.probabilityTables[1].items():
for k in range(len(sBoxes)-1):
for l in getOutputs(self.probabilityTables[1], i):
newBranch = Branch(i, self.deltaX, self.probabilityTables, self, k, l[0], l[1])
self.branches.append(newBranch)
for i in self.branches:
i.recurse()
def __init__(self, probabilityTables, deltaX):
self.probabilityTables = probabilityTables
self.deltaX = deltaX
# the branch needs access to the probability tables
class Branch:
outputDifference = 0
inputDifference = 0
subBranches = []
round = 1
maxRound = 4
probabilityTables = None
parent = None
sBoxOffset = 0
prob = 0
def recurse(self):
print("Round: {} Self.inputDifference: {}".format(self.round, self.inputDifference))
if self.round == 5:
print("%%%%%%%%%%%%%%%% IMPOSSIBLE CONDITION OCCURED!")
return
print("Table: {}".format(self.probabilityTables[self.round][self.inputDifference]))
if self.round == self.maxRound or self.round == self.maxRound:
dY,probability = findbestOutput(self.probabilityTables[self.round], self.inputDifference)
print("Best output: {}".format(dY))
self.outputDifference = dY
nextBranch = self
print("Parent round {} inputDifference {} outputDifference {}".format(nextBranch.round, nextBranch.inputDifference, nextBranch.outputDifference))
inputs = []
global paths
probability = 1
while True:
if type(nextBranch) == recursor or type(nextBranch) == recursor:
# get the probability of this event from the global table
# inputs.insert(0, nextBranch.deltaX)
print("prob: {}".format(probability))
print("Inputs: {}".format(inputs))
paths.append((probability, inputs))
return
print ("type nextBranch {}, check {}".format(type(nextBranch), type(nextBranch) == recursor))
print("------------< Recursing from {} up ".format(nextBranch.round))
print("Prob: {}".format(probability))
print("Current up round {}".format(nextBranch.round))
print("inputDifference {} outputDifference {}".format(nextBranch.inputDifference, nextBranch.outputDifference))
print("Inputs: {}".format(inputs))
# get our own probability by looking it up in the former round's output tablé
print("Previous round data: {} {} {}".format(nextBranch.round, nextBranch.inputDifference, self.probabilityTables[nextBranch.round][nextBranch.inputDifference]))
probability = probability * nextBranch.prob
inputs.insert(0, nextBranch.inputDifference)
nextBranch = nextBranch.parent
else:
possibleOutputs=getOutputs(self.probabilityTables[self.round], self.inputDifference)
print("Round {} possible outputs {}".format(self.round, possibleOutputs))
print("self.inputDifference: {}".format(self.inputDifference))
satisfied = []
for i,j in possibleOutputs:
print ("i,j: {} {}".format(i, j))
# transform the output
transformed = transformOutputToInputs(self.sBoxOffset, i)
print("Transformed to {}".format(transformed))
if transformed != 0 and transformed not in satisfied:
satisfied.append(transformed)
print("!!!!! self.round: {} (+1 {})".format(self.round, self.round + 1))
newBranch = Branch(transformed, self.round + 1, self.probabilityTables, self, self.sBoxOffset, i, j)
self.subBranches.append(newBranch)
print("------------> Recursing from {} down".format(self.round))
if self.round + 1 > self.maxRound:
print("%%%%%%%%%%%%%%%% IMPOSSIBLE CONDITION OCCURED!")
return
newBranch.recurse()
return
def __init__(self, inputDifference, round, probabilityTables, parent, sBoxOffset, outputDifference, prob):
# print("##### Init branch with {} {} {} {} {} {} {}".format(inputDifference, round, probabilityTables, parent, sBoxOffset, outputDifference, prob))
self.inputDifference = inputDifference
self.round = round
self.probabilityTables = probabilityTables
self.parent = parent
self.sBoxOffset = sBoxOffset
self.outputDifference = outputDifference
self.prob = prob
class sBox():
# The substitution table this s-box uses
table = []
def __init__(self, table):
self.table = table
def forwards(self, x):
return self.table[x]
class result:
inputs = []
probability = []
def __init__(self, inputs, probability):
self.inputs = inputs
self.probability = probability
def __repr__(self):
return "probability {} inputs {}".format(self.probability, self.inputs)
# this function calculates the inputs to the next round
def transformOutputToInputs(sBoxOffset, output):
return output & (0x8 >> sBoxOffset)
def generateTable(sBox, deltaX):
table = {}
for x in range(0, maxNum):
x_ = x^deltaX
y = sBox.forwards(x)
y_ = sBox.forwards(x_)
deltaY=y^y_
if table.get(deltaY, False):
table[deltaY] = table[deltaY] + Fraction (1,maxNum)
else:
table[deltaY] = Fraction(1, maxNum)
return table
def findBestInput(table):
bestInput=(0,0,Fraction(2,0))
for dx, dy in table.items():
for prob in dy:
if prob > bestInput[2]:
bestInput=(dx,dy,prob)
return bestInput
def findbestOutput(table, dx):
bestOutput=(0,Fraction(0,1))
for dy, prob in table[dx].items():
if prob > bestOutput[1]:
bestOutput = (dy, prob)
return bestOutput
def getOutputs(table, dx):
outputs=[]
for dy, prob in table[dx].items():
outputs.append((dy,prob))
return outputs
def getInputs(table):
inputs=[]
for dx in table.keys():
inputs.append(dx)
return inputs
maxNum=0xf
cases = []
differenceDistributionTable={}
s1=[10,0,9,14,6,3,15,5,1,13,12,7,11,4,2,8]
s2=[7,13,14,3,0,6,9,10,1,2,8,5,11,12,4,15]
s3=[2,12,4,1,7,10,11,6,8,5,3,15,13,0,14,9]
s4=[12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11]
paths = []
sBoxes = {
1: sBox(s1),
2: sBox(s2),
3: sBox(s3),
4: sBox(s4)
}
deltaXTestCases={}
for i,j in sBoxes.items():
print("Building tables for sBox {}".format(i))
differenceDistributionTable[i] = {}
# skip deltaX == 0
for k in range(1,maxNum):
print("Building table for deltaX {}".format(k))
differenceDistributionTable[i][k] = generateTable(j,k)
for i in differenceDistributionTable[1].keys():
deltaXTestCases[i] = inputCase(i, recursor(differenceDistributionTable, i))
for i in deltaXTestCases.values():
print("Recursing with dX {}".format(i.deltaX))
i.recurse()
print("Paths: {}".format(paths))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment