Improving digital security with natural selection

How scientists from the Czech Republic trialed new cryptanalysis methods with inspiration from the theory of evolution and the help of High-Throughput Compute

Hiding private data is a major concern in today’s digital world. We need to protect information from prying eyes and one way of doing that is by encryption with algorithms that scramble the data when it’s sent and reassemble it after a safe arrival.

Good encryption algorithms make the processed information look as much as possible like random data, with few flaws so-called ‘distinguishers’. Finding such flaws in algorithm design is essential for security. Yet cryptanalysis computer programs can only look for as much as they are programmed to do. Human cryptanalysts are the best choice, but this is labour-intensive work. So how could a cryptanalysis program be made more like a human?

One tactic would be to give a programme the power to evolve.

Vashek Matyas and colleagues colleagues Petr Svenda and Martin Ukrop from Masaryk University have now trialled a form of cryptanalysis that uses genetic programming and the HTC resources provided by Metacentrum, the Czech National Grid Initiative.

The ‘genetic programming’ approach borrows concepts from evolutionary theory and turns ‘survival of the fittest’ into a method to test algorithms.

The method uses programmed, hardware-like circuits as tests. These circuits take the encrypted information as input and test it. If a circuit succeeds in identifying a possible distinguisher, the circuit is selected and used again in the next round of testing. In between rounds, the evolutionary algorithms managing the process come in and tweak the circuits and their connections to form slightly different programmes.

And over many rounds the end result is a collection of ‘surviving’ circuits that is very efficient at finding distinguishers. In effect, their system keeps rewriting itself.

The team tested their approach on seven ciphers from the ESTREAM competition, organised by ECRYPT, and compared results to a standard cryptanalysis computer program, the NIST statistical testing suite. Overall they used 1,000 cores and consumed 30,000 CPU hours through the HTC services provided by Metacentrum.

The system was able to find distinguishers in the ciphers, and performed almost as well as the NIST suite. The evolutionary algorithm was more efficient, once the learning evolution phase is over. Once a successful system is made, the algorithm is able to work on extremely short sequences, only 16 bytes long. This is a huge advantage over traditional statistical cryptanalysis programmes which need at least several megabytes of data.

And what was the benefit of HTC  for this work? “HTC allows us to execute experiment significantly faster, which in turn allows us to stop non-perspective runs, change controlling parameters of genetic programming and run it again,” said Vashek.

References

Svenda, P.; Ukrop, M.; Matyas V.: Determining Cryptographic Distinguishers for eStream and SHA-3 Candidate Functions with Evolutionary Circuits, In ICETE 2013, CCIS 456, Springer, 2014, DOI: 10.1007/978-3-662-44788-8 17

More information

Metacentrum