Blinds for Thermodynamic Cipher Attacks

Abstract

Recent advances in breaking Diffie Hellman and RSA public key ciphers have focused on the time required to perform the cipher function. Since the time required by a cipher function is heavily dependent on the cipher keys, it bounds the possible keys to a limited set thereby reducing the computational requirements to break a cipher. In 1995 Paul Kocher wrote an algorithm which takes advantage of this weakness. This is one attack of a class: thermodynamic cipher attacks. As a result of Kocher's efforts a secure cipher, henceforth, requires a thermodynamic blind; that is a screening of the actual cipher's thermodynamic output behind an excess output. This paper analyzes the thermodynamics of blinds to find both the correct context for discovering the minimum requirements of any thermodynamic blind and a first order estimate of the lowest sufficient thermodynamic output required as a blind. The attack can be foiled by performing two cipher functions selected such that the thermodynamic output is set equal to twice the average output for any pair of a large set of cipher functions.

Other Proposed Blinds Are Insufficient

Several insufficient blinds have been proposed which, when reviewed, guide us to a general blinding tactic. If the time to complete a cipher of a particular set of keys is extended by a random amount, several sample times may be collected, allowing an attacker to compute mean and standard deviations to remove the introduced "random" noise. A better blind forces the cipher to complete work in equal times regardless of the complexity involved. The improvement obtains because the cipher times are indistinguishable. Indistinguishability makes the probability that at any one time the cipher function is working with any particular set of keys equally likely. However, not all avenues of attack are

cut off. The attacker may still have access to CPU utilization, electromagnetic radiation, or a host of other processes which make the cipher functions distinguishable. Hence the probabilities that a cipher function is in a particular state are unequal and the most probable keys laid bare to attack. Because there are difficulties inherent in creating a software algorithm that matches all architecture's physical characteristics to a single standard, we are motivated to discover a better method of producing indistinguishable functions. The thermodynamics of cipher functions operating on large sets of keys "simultaneously" renders them indistinguishable.

Thermodynamic Context

The link between thermodynamics and statistics

The function Q(N,E,V;t) counts the number of states available to physical system, where N is the number of particles ( here it is the number of concurrent ciphers on a set of keys ), V the volume under consideration ( here it is the physical package where the cipher function resides, e.g. the CPU), E is the energy, and t is the time. The function Q is related to the entropy S -- the same S as in Shannon's paper on information theory -- by the relation

S = k ln Q.

This equation is the link between statistical mechanics and thermodynamics. Since we seek a relationship between the statistics, or more correctly, the probability distribution, of a cipher function combination and the thermodynamic properties of the processes carrying out the cipher functions, this relation must be the link.

The sufficiency of the extensive variables E,N, and V

Given that we want a blind to prevent an attacker from gaining insight into the probable keys under all circumstances, we must assure ourselves that no information can leak out through an unconsidered variable. If, in the process, an efficient blind is found, so much the better. Therefore I assert, but do not prove here, (the proof may be looked up in any thermodynamic textbook) that the fundamental relation provides that the entropy of a system is equal to the sum of the entropies of its component subsystems, and that the entropy of any subsystem is a function of its extensive parameters E,N and V which may implicitly depend on time t

Generally we look at systems in equilibrium so that the parameters are not a function of time t. In the case of time based attacks we can show that time is an inverted energy function

Timeis only one way of measuring the energy of the system, others are radiation, heat, power consumption, etc., and only energy is important for constant N and V. The entropy relation guarantees that we have access to all the observables of a physical system by the standard thermodynamic transformations. For example, one observable, temperature, is given by

Similar relations hold for all other variables we might be interested in , Pressure, Heat Capacity etc

Assuming that the cipher algorithm and a physical implementation of it are available to an attacker she can measure, or calculate, S = S(E). If E, the energy of the entire system, is directly proportional to e, the energy generated by one cipher function, only the remaining parameters N and V are available as blinds. It is reasonable to assume that V is fixed and it's value available to an attacker, because CPU's are massed produced. Therefore, only N , the number of cipher functions, remains available for creating a blind. Because S is a function of just E, N, and V, where only E is used for the attack, and only N is available as a blind, our search for an efficient blind reduces to finding a suitable relationship between E and N that maximizes the cipher space searched in an attack.

Anticipating the solution

Now the simple approach to blinding would let N go to infinity so that the entire cipher space must be searched and, in consequence defeating any advantage a thermodynamic attack had over a brute force attack in which all possible solutions are tried one after another. But we can do better, we can show, after some analysis, that

are the number of cipher, , and blinding, functions chosen so that

To illustrate this consider a cipher function operating on one key, nc then it must choose another key nb to serve as a blind. We reqire that this second key be chosen such that the total energy required to operate on the two keys is equal to twice the energy required to operate on two average keys. When an attacker gathers thermodynamic information on the system, she will discover only that the cipher function is probably working on two equal and average keys. However our analysis does not not restricted the cipher function and its blind to just two keys. The cipher function may work on any set {} of keys with this same property. In fact the cipher function need not use keys at all, there might, instead, be a large set of different ciphers functions all of which might work on the same key. All we require for the blind is that any set of cipher functions { } be selected in such a way that probable most distribution of energy among the cipher functions is equal.

Contact between thermodynamics and cipher functions

Having secured a motivation for a thermodynamic blind and guessed at the form of it, we need to set the thermodydnamic stage and outfit the cipher function problem with the garments of the Grand Cannonical formalism of statistical mecahnics. Every so often we will want to ground our analysis and check our answers by simplifying the discussion and pretending that we have only one cipher algorithm operating on a standard platform which changes energy as a function of the keys involved. A generalized analysis requires that we consider other cases where the cipher functions might have an energy equal an integral number m times , the base energy of the cipher function. An example is a DNA based computer, where many different cells are working on the same problem at any given time. The reader is challenged to invent other models and check the following analysis. Procedeing with both models in mind, the analysis requires that we divide up the energy spectrum into a series of i compartments of width de and each compartment de would contain ni keys whose cipher energies were in the range + de, where such that the total energy of the system is given by

Assume now that a cipher function is in contact with a reservoir of an infinite key space, or equivalently a thermal bath, with which it continuously exchanges keys and energies defined by so that a state of equilibrium prevails. This reservoir will be the set of all keys and energies available to the cipher function and will become our the basis for our blind.

Setting up the cipher function ensemble

How can we achieve this equilibrium state in a computer? We do so by introducing an input and an output queue which the cipher function processes -- in no particular order, singly or in groups -- so as to keep itself busy at all times. The thermal bath consists of an infinite number of other physical implementations of cipher functions (computers) processing the same queues, also in no particular order. We don't have to have an infinite number of actual computers; they are "mental constructs" that allow us to consider the problem with the ensemble theory of statistical mechanics. This infinite set of computers represents, at any given instant, all the possible microstates available to any one computer over time consistent with the given macrostate defined by N,E, and V. The energy for a particular key k is denoted by and the number of keys with that energy, or really within the range + de, is given by . and are the total number of keys and energy of the ensemble and are the constants in our earlier sums, and given by:

The thermodynamic cipher attack, and hence or blinding strategy, then hinges on assigning the correct probability that at some particular time t the cipher function is working with a particular set of keys {}. In the usual way, we demand that the probabilities are independent, so we can write:

Obviously P must be an exponential function since exp(a+b) = exp(a)exp(b) and that is the form of the above equation. Remembering that the bath and cipher function are in equilibrium, and letting ensemble theory guide us, we know that the probability Pik that our cipher is in a particular state, at a particular time, is proportional to the number of microstates available to our bath (blind) . That is we know that , and is an exponential funcion so we can work with ln . Because we are concerned with

and we can approximate ln Qb function by an expansion since , we write:

where we have taken the derivative at . Let us also agree to drop the superscripts because, henceforth, they have no meaning. We could stop here and show that , where k = k Boltzman and is the chemical potential, and check our work by recovering the fundamental relation of thermodynamics. Instead we return to our expression for the probability which we can now write as:

With this equation in hand we move to assigning the probabilities and energies we want in order to repulse the attacker.

All roads lead to Rome.

Just as an empire that dominated the world required the Romans to construct a set of roads wich led back to a single, fortified, source, a cipher blind that thwarts thermodynamic attacks must construct a blind in which all avenues of attack lead to a single, and hence meaningless, answer. A blinding function requires that all thermodynamic measurements of a cipher process return the same answer. Equivalently, it demands that the most probable keys be identical across all cipher functions. Given a space of all possible ciphers the most naturally identified single point in that space is the central point. This amounts to the requirement that the central point lies in the middle of a shpere who's radius we define by setting all state probabilities equal. Of course, this requires that we discover just where is the center.

Three of the most prominent definitions of the center spring to mind: the , average,the most probable N*,E*, and the mean, or expectation value <N>,<E>. To calculate these we step back to our mental model and visualize an ensemble of identical systems (which are labeled 1,2,3,..., ) mutually sharing a total number of cipher functions and a total energy . If is the number of cipher systems that have cipher functions and cipher functions energy (i,k = 0,1,2,...), at any time t, then we must have,

Any set of {} of the numbers , which satisfy the restrictive conditions above represents one of the possible modes of distribution of cipher functions and energy among the members of our ensemble. How do we count the number of different ways any particular mode might find itself in? We have ! permutations reduced by the number of indistinguishable permutations (!), thus we write W{} as:

To maximize this expression we look for the {} which maximizes W, i.e. . Having maximized this expression, using the method of Lagrangian multipliers, we get the most probable mode of distribution {}. Skipping the math and writing down the answer we have

or we can start with the expectation value given by,

which can be given in an asymptotic form,

In all circumstances Navg,Eavg are given by

which is also given by,

For completeness we note that

To relate this result back to S we note.

We have now shown that, in the limit as N goes to infinity, the most probable N * is equal to <N> is equal to Navg and the same holds true for E* = <E> = Eavg. Having calculated <N> ,<E> we can assign a blinding key which complements our cipher key in such a way a constant relation between cipher functions and the values <N> and <E> is maintained.

A Practical First Order Solution

As a practical matter neither N nor E runs from zero to infinity, but is bounded instead on the lower side by a keyspace N that is sufficiently large that all known attacks require more time (energy) than is, or will be, available in the near future, using known resources, and is bounded on the upper side by performance issues dependent on E. Both upper and lower bounds are calculable, and assuming that for a given system they have been calculated, we assign them to the constants

The average values, assuming perfectly a random distribution of keys, are given by

By setting our subscript max = i and min = j we can rewrite this as a requirement for arbitrary i and j:

which yields a formula for choosing a blinding cipher key

Therefore we will select a specific set of blinding keys

Now any nb which satisfies the average constraints above will generate equal entropies S and therefore equal probabilities, and hence force an attacker to search the entire keyspace.

Remaining Problems

There might also be second order corrections that would allow more efficient blinds.

Home  Next

Last updated by John Ryan john@cybertrace.com on Fri Mar 29, 1996