Notes 20110314 CIS 6650 Computer Security - Presentations

Jump to: navigation, search

Genetic Algorithm Crtyptanalysis of a Substitution Permutation Network

Speaker: Joseph Brown

genetic algorithms applied to many ciphers
good at hard optimization problems
simple SPN encryption
example usage has a blocksize of 16-bits
key -- 32 bits
16 bit subkey -- multiple rounds
chosen plaintext attack: paired plain- and cipher- text have some known statistical properties
known plaintext attack: non-trivial version -- statistical properties are not set before hand
fitness is minimizing bitwise error
single elite holds best key
in general, GAs look for an approximate solution
- in this case, we want the best one
GA system attempts to find the best key
the goal was to characterize keys for weakness
are there also particular sizes of plain-, cipher- texts that are particularly vulnerable
results ...
- as the number of 1-bits in key increases, so too does difficulty to break
- early randomness better than later
- swaps better than flips (less destructive to the GA)
- two-point crossover more adequately resembles the key scheme
future work ...
- apply to different key schemes
- apply to different ciphers
- intelligent way to create cross-over operations should mirror block operations given by algorithm
the moral of the story is to find or create crossover operators based on the schemes

can we base the number of rounds on some of the bits of the keys?
- probably not beneficial -- a higher number of rounds is always best