Does chaos theory have any practical application in computer security?

Question

Having learned about chaos theory at university some years ago, I've been curious ever since to know whether it has found any practical use in computing.

Let me explain where I imagine it could be used...

Chaos, in the mathematical sense, is stochastic ("random") behaviour in a deterministic ("non-random") system. Chaotic systems have three key properties:

• they are bounded
• they are non-repeating
• they are sensitive to initial conditions

For example, take the chaotic iterative map function f(x) = 2x² - 1. For inputs between -1 and +1 (excluding -1, -0.5, 0, 0.5 and 1), iterating this function yields chaotic results. For example:

    x     |    f(x)
----------+-----------
0.700000  | -0.020000
-0.020000 | -0.999200
-0.999200 | 0.996801
0.996801  | 0.987226
0.987226  | 0.949229
0.949229  | 0.802070
0.802070  | 0.286633
0.286633  | -0.835683
-0.835683 | 0.396731

The results are bounded (output is always greater than -1.0, less than 1.0) and non-repeating (try iterating over it a few thousand times – you won't see any emerging pattern). If you vary the first value of x by even a tiny amount (e.g. use 0.700001) you'll start to see the results diverging considerably from those above after just a few iterations. In other words, this function is also sensitive to initial conditions.

I could imagine this having a number of applications in computing as a predictable pseudo-random number generator. For example, you could use something like the above function as the basis for one of those secure key fobs used for "something you have with you" authentication. Imagine using f(x) = 2x² - 1 in such a device. Provided the device and the server were seeded with exactly the same initial input, they'll continue to remain in sync forever (allowing for timing issues), since the function is completely deterministic. Let's say you used the first six digits after the decimal point as the key displayed to the user and validated by the server. If someone looked over your shoulder, saw the current value and fed it into the same function, they still couldn't predict future values of the device thanks to the function's sensitivity to initial conditions: only having the input to six decimal places is worthless.

So, is my intuition correct? Has chaos found such a use in computer security?

Answer 1

Chaos is not sufficient. A cryptographically secure PRNG must produce unpredictable output: it should not be sufficient, for someone observing a long stream of values produced by the PRNG, but not knowing its internal state, to predict the next bit with a success probability substantially distinct from 0.5 (i.e. predictions should not work better than luck). In the case of f(x) = 2x² - 1, it suffices to observe one output value to compute the internal state (if f(x) = y then x = ±sqrt((y+1)/2) and thus predict future behaviour of the generator. This would make for an extremely weak PRNG.

A secure PRNG produces output which is indistinguishable from randomness; as such, it looks chaotic. Being chaotic is necessary for a secure PRNG, but nowhere near sufficient, as the example above shows.

Chaos theory fascinates some people because it deals with chaotic behaviour emerging out of "normal" physical functions, which is surprising because "mundane" physics have accustomed us to expect tame, linear behaviour of physical quantities (thermodynamics being the prime example of that). However, computer security works on computer which already live in a discrete, thus non-linear world (it is all zeros and ones). In computers, chaotic behaviour is the norm; for cryptography, we must go much beyond that.

Chaos theory would be relevant if you had to build a PRNG without using a computer, but instead relying on a few tools from macroscopic physics. In that case, chaos would be all you would have to work with. Chaos theory is the right tool to explain why a lottery machine is a good RNG. But this does not apply to computers in which complete accuracy is the norm: you cannot measure a physical quantity with more than a dozen digits or precision, and the value you get is always approximate to some degree, as if the World kept the extra precision up its metaphorical sleeve; but you can get a thousand bits exactly, and there is nothing more in a computer.

Answer 2

You're basically describing HMAC and TOTP algorithms.