The Heuristic Evolution of Security and Insecurity

by John Clark and Jeremy Jacob

Researchers of the University of York in England aim to show that heuristic search techniques are powerful tools for modern day cryptology.

Heuristic search techniques such as simulated annealing and genetic algorithms are a major success story of computer science. Their use in cryptology, however, has remained very low key. Most work has been concerned with breaking simple classical ciphers and there has been little application to modern-day cryptological problems. Modern day crypto-algorithms do not lend themselves to cryptanalysis via heuristic search in the way that classical ciphers often do. This may well have led to heuristic search being discounted as a serious tool for cryptologists. We aim to show that its cryptological power is greatly underestimated and outline below some successes so far. The work ranges from the design of fundamental components, through cryptanalysis of identification schemes, to the automated synthesis of provably correct security protocols.

The Design of Cryptographic Building Blocks
Boolean functions (mappings of vectors of Boolean inputs to vectors of Boolean outputs) are at the heart of modern digital cryptography. Block ciphers such as the Data Encryption Standard and Advanced Encryption Standard, for example, can be regarded as (rather complex) Boolean functions (mapping plaintext input to ciphertext output in a manner determined by a secret key). Modern algorithms use simpler Boolean functions as components. These are carefully constructed to resist modern cryptanalytic attacks. Various resilience properties have been proposed as desirable but the field is subtle and engineering functions with excellent properties is surprisingly difficult. Mathematical construction remains the primary derivation technique but for the small single-output case our search approaches, based around simulated annealing, have been able to produce functions with more extreme values of properties than hitherto known. Counter-examples to several conjectures in the literature concerning achievable bounds have been demonstrated (often within a few seconds or less). When functions satisfying many criteria are sought our approaches have equalled, and in many cases bettered, the best results theoretical construction has provided to date. A feature of optimisation-based approaches is that they extend naturally to cater for additional desirable criteria (the cost functions used are appropriately amended). What counts as desirable, however, depends on who you are. Though the focus of our work is the attainment of functions with excellent profiles of positive properties, we have evidence to show that trapdoor properties may easily be incorporated too. Understanding how, why and when the techniques work effectively remains a major challenge.

Exploiting the Computational Dynamics of Search Techniques
Work over the past decade has shown that timing and power consumption characteristics of a cryptosystem can be exploited to reveal the secret keys used. The injection of hardware faults (even transient ones) into a cryptosystem can be similarly exploited. But it is not realised that search techniques such as simulated annealing also have computational dynamics that can be exploited in a cryptological context (using such characteristics we have successfully attacked instances of NP-complete problems underpinning certain identification protocols). The important point here is that annealing is a form of guided search. The way in which the solution moves from a random start point to its eventual destination may provide substantial information about the underlying solution to the problem instance under attack. The order in which solution elements attain their final values (ie the order in which those elements get stuck at that final values during a search) may be related to the actual sought solution. This may be regarded as a form of timing channel. On a different tack, we have obtained excellent results by warping the problem instance under attack in many different ways (in analogy with fault injection) and have used the sets of final solutions obtained by the searches to locate the solution to the original problem.

Profiling is a crucial component of such attacks and cryptosystems lend themselves to such approaches. Every secret key for example may define a representative instance. We can generate many representative instances, apply heuristic search based techniques aimed at finding the underlying secrets, and investigate how the actual secrets sought are related to the final solutions of various search runs and to the trajectories taken to such final solutions. This knowledge can then be applied to instances where the secret key is not known. This has already been demonstrated in the context of some identification schemes (as indicated above) and we now seek to attack block ciphers and public key algorithms.

Evolving Secure Protocols
A protocol is a series of message exchanges, each message designed to achieve some goal, typically making subsequent messages possible or meaningful. The notion of progress towards goals seems inherent to the concept of a protocol. We have sought to exploit this and have created a prototype framework for the automated synthesis of security protocols (eg key distribution protocols) based around the belief logic of Burrows, Abadi and Needham. We carry out a guided search over the space of feasible protocols. Each protocol achieves something. The closer that something is to what we want, the fitter that protocol is deemed to be. The guided search approach (using simulated annealing or genetic algorithms) allows increasingly fit protocols to be evolved, eventually leading to one (or more) that meets all the intended goals. The formal nature of the belief logic used allows the evolution of protocols whose abstract executions are in fact proofs of their own correctness. Heuristic search is a powerful tool for professional modern day cryptology. Its power has barely been tapped.

Please contact:
John A Clark and Jeremy L Jacob,
University of York, UK
Tel: +44 1904 433379
E-mail: {jac,jeremy}@cs.york.ac.uk