Score:2

What can chaos provide to cryptography?

us flag

Chaos-based cryptography is facing a lot of criticism, however, some people argue that it can provide many cryptographic primitives, such as stream ciphers, block ciphers, hash functions, public-key ciphers.

Leaving aside all the defects of the application chaos in cryptography, is not chaos at most is a pseudo-random generator which could be used for stream ciphers (if this even possible)?

Note: I am wandering why some people think it is suitable for many cryptographical primitives.

[Edit] in other words: Is it feasible to build a whole branch of cryptography on a family of pseudo-random sources Such as LFSR?

Or

For example, for the block ciphers is not the chaos just may be used for generation of random sequence which is separated for our construction of the cipher which we built to be stream or block cipher?

Or

Some author says that chaos is suitable for prng, but it failed to provide a approved cryptographic primitives. Is not chaos role in the proposed cipher merely a prng?

poncho avatar
my flag
'Leaving aside [the cryptographical issues, why] is not chaos at most [used as] a pseudo-random generator' - are you asking why it's not used as a noncryptographical rng?
user2357 avatar
us flag
@poncho I am wandering why some people think it is suitable for many cryptographical primitives.
Score:2
ng flag

Is it feasible to build a whole branch of cryptography on a family of pseudo-random sources?

In theory, yes. If there was an efficient and Cryptographically Secure Pseudo Random Number Generator built from a chaotic system, then that could serve as the foundation of reasonably practical symmetric cryptography, and even signature.

Problem is we know no such thing. PRNGs built from a chaotic system, and having an even mildly convincing security argument¹, pale in efficiency compared to a modern CSPRNG² (unless we extend the definition of "chaotic system" well beyond the usual iterated continuous functions over $\mathbb R$, or discrete approximations thereof).


A (Cryptographically Secure) Pseudo Random Number Generator, in it's modern definition, is a powerful-enough tool to build all the other symmetric cryptography functionalities: CPA and CCA(2)-secure cipher, block cipher, Message Authentication Code, authenticated encryption, hash… Some examples:

  • A cipher can be constructed from a (CS)PRNG by using the key and a truly random random IV to seed the PRNG, and constructing the ciphertext by XOR of the PRNG's output with the plaintext³. The security directly follows from that of the PRNG, and that's such a good and common way to construct a cipher that it has a name: stream cipher.
  • A block cipher can be constructed from a PRNG as a Feistel cipher, by using the PRNG to construct the round functions. The key, round number, and right half of the block seed the PRNG, which output is the value to XOR with the left half.

These constructions are demonstrably cryptographically secure if the PRNG is. But with the exception of stream ciphers, they are not used in practice, primarily for efficiency reasons. Common CSPRNG are constructed from block ciphers or/and hashes, rather than the other way around.


Is it feasible to build public key crypto primitives from PRNG?

Yes for signature. We can build secure hash from secure PRNG, then secure signature from hash, by various approaches, including SPHINCS. By this route, any efficient PRNG leads to a plausible signature scheme.

For encryption and key exchange, I doubt that a method with a security proof or even a convincing argument is known. I stand unconvinced by attempts to build asymmetric encryption from continuous chaotics systems by more direct routes⁴.


¹ We can't ask for a proof in the mathematical sense, since we have no such proof of security for any CPRNG. But we do not want to accept as security argument the fact of passing a predefined randomness test, such as NIST SP800-22rev1a or dieharder. An experimental test should be at least: impossibility for skilled human cryptographers knowing the design of the PRNG, assisted by classical computers, to distinguish from true randomness the output of the PRNG seeded with true randomness. And we'd want to extend that to such impossibility starting with a minimum value of some parameter(s) of the PRNG, like state size or/and number of rounds, with the actually used parameter(s) set comfortably larger.

² Such as the one derived from ChaCha by considering the key and IV to be the seed, and all-zero plaintext.

³ Decryption is similar with plaintext and ciphertext exchanged, except that encryption draws the IV and makes it a preamble of the ciphertext, while decryption extracts the IV from the preamble.

⁴ One such attempt (paywalled) uses Chebyshev polynomials $T_r$ of large degree $r$. A private key is $r$, the matching public key is $T_r(x)$ for some public fixed randomly-chosen real $x\in[-1,1]$. For any integer $s>0$ it holds $T_r(T_s(x))=T_s(T_r(x))$ and (ignoring issues of how that's computed) that allows an analog of Diffie-Hellman key exchange, and from that ElGamal encryption. When I first read it, I stood unconvinced by the argumentation-free assertion of security, as well as by some aspects of feasibility (e.g. that with 2048 bits of precision for real values, the integers $r$ and $s$ can be chosen as random 910-bit integers, rather than as product of primes at most 133 as in the article).
Update: The cryptosystem was found to be insecure, see this article (paywalled). It's still presented in this chapter on Public-Key Cryptography (paywalled) in a much later book on Chaos-Based Cryptography (paywalled), with acknowledgement of insecurity. I find it telling of the state of that whole academic field. And that's at it's best: most claims of security, made with comparably weak arguments, are never seriously investigated and proven wrong.

user2357 avatar
us flag
Thank you… What do you mean by: unless we extend the definition of "chaotic system" well beyond the usual iterated functions over R (or discrete approximations thereof)?
fgrieu avatar
ng flag
@user2357 : My now slightly revised _"(unless we extend the definition of "chaotic system" well beyond the usual iterated continuous functions over $\mathbb R$, or discrete approximations thereof)"_ is because we could redefine as "chaotic system" the iteration of a function over the set of bitstrings of a certain size, with the function defined using bitwise rotation, bitwise XOR, and binary addition with the last carry lost, which would cover Chacha. But Chacha's iterated function is _not_ on $\mathbb R$, nor built as a discrete approximation of a continuous function on $\mathbb R$.
user2357 avatar
us flag
You said "PRNGs built from a chaotic system with an even mildly convincing security argument". Do you have example of this on the ones defined in $\mathbb R$?
fgrieu avatar
ng flag
@user2357 : ChaCha is not a PRNGs built from a chaotic system for the definition I intend of "chaotic system". \[update: the [logistic map](https://en.wikipedia.org/wiki/Logistic_map) $x\mapsto r\,x(1-x)$ is a continuous function on $\mathbb R$ which, when iterated, leads to a chaotic system for appropriate choice of $r$. More often than not, it's restriction to a finite set by discrete approximation is far from similarly chaotic. There is no similar natural construction of the iterated function used in Chacha.\]
user2357 avatar
us flag
Got you. Do you mean by "mildly" to be good and accepted?
fgrieu avatar
ng flag
@user2357 : "even mildly" is there to emphasize that what follows needs not be strict. I could have written: _PRNGs built from a chaotic system, and having a security argument, pale in efficiency compared to a modern CSPRNG. That's even if we do not require very convincing security arguments_.
Score:2
my flag

I am wondering why some people think it is suitable for many cryptographical primitives

Well, I'm not one of those 'some people', however I will give you my perspective.

One of the good properties we like in our cryptosystems in 'avalanche'; that is, a small change somewhere ripples throughout the system. I expect that 'some people' take notice of this and say "hey, that's exactly what chaos is".

At first glance, this has some plausibility; however:

  • Chaos is not the only way to achieve this. This 'avalanche' affect is a deliberately designed property of (most) symmetric cryptosystems. For example, with AES, a one-bit change anywhere in the state will modify all 16 bytes two rounds later.

  • It's also unclear whether the chaos property of 'small changes usually avalanche everywhere' is actually sufficient. For one, we need to ensure that all such changes have this avalanche property; we would need to show that there are no nooks anywhere where changes don't propagate as fast as well expect, and that changes that would be considered large by the chaos infrastructure (e.g. changes to the msbits of the state) are also propagated.

  • Chaos is usually defined in terms of real numbers; when we do cryptography, we deal with values with finite precision. It is unclear (at least to me) whether translating from reals to some finite realm necessarily preserves the properties we were hoping for.

Finally, it all comes down to performance. Actually, it is not that difficult to design a secure symmetric cipher (as Ron Rivest pointed out, a thousand rounds of just about anything (nontrivial [1]) is usually secure); we also need to perform reasonably well. The obvious final objection would be 'do these chaos-based ciphers perform competitively compared to more traditional ciphers, while maintaining security?'


[1]: Ron didn't specify nontrivial in his observation, obviously, there are round functions that are perfectly linear or with no right-ward propagation; I've seen amateur cipher designs with these properties, and obviously 1000 rounds won't help you in those cases...

user2357 avatar
us flag
thank you.......
user2357 avatar
us flag
You said "For one, we need to ensure that all such changes have this avalanche property". My question is: how can we be sure about this in mainstream ciphers, AES for example?
user2357 avatar
us flag
"It is unclear (at least to me) whether translating from reals to some finite realm necessarily preserves the properties we were hoping for." There is numerical degradation which is considered one of the most problem in the implementation of these systems. Some serious researcher indicated this at the beginning of the century and did some work on it, however, the chaos cryptography community ignores this most of the time.
poncho avatar
my flag
@user2357: AES is a good example; we have a proof that (for example) a one byte change in one byte of an intermediate state will always change all 16 bytes in the state two rounds later. This happens no matter what the change in that one byte is, and similar statements can be made for changes to 2 or 3 bytes of an intermediate state. Are Chaos-based cryptosytems able to make similar statements?
Score:1
si flag

Apparently chaotic behavior is necessary but insufficient for cryptography. It's a result of cryptographic security, not a cause. Some people invert causation, and think that anything displaying chaotic behavior is suitable for cryptography. I don't know why some people make this mistake, and it's not unique to cryptography.

Lorenz's definition of chaos: "When the present determines the future, but the approximate present does not approximately determine the future".

For computer cryptographic systems operating entirely on bits, we don't have the issue of imprecise measurements that lead to the limit to only have the "approximate present" that physical chaotic systems have.

Practical encryption systems do display chaotic behavior, but they also have other properties. Shannon's concepts of Confusion and Diffusion create the sensitive dependence on initial conditions for the ciphertext from both the plaintext and the key. They also ensure the transformation isn't invertible, which a simple chaotic system may not do.

The one place chaotic oscillators get used a lot is in hardware random number generators. These are often composed of several ring oscillators sampled at different independent clock frequencies, which leads to jitter in the sample values. That jitter means the measurements of the oscillators are only an approximation of their complete state, so it's effectively impossible to determine the future state from a present measurement. Likewise some use avalanche diode noise, which is a quantum-mechanical effect at its core. Since we can't ever know the complete state of a quantum system (if it even exists) these also exhibit the "approximate present" property.

poncho avatar
my flag
Hmmmm, the formal analysis of ring-oscillator entropy sources I've seen base the entropy source not on chaotic behavior, but instead on thermal noise that subtlety changes the transition times (which directly alter the precise RO timing). Have you seen a formal analysis based on chaotic behavior?
SAI Peregrinus avatar
si flag
Thermal noise *is* chaotic behavior. At a small enough scale, the heat transfer is a dynamical system displaying sensitive dependence on initial conditions. It's not usually useful to model it as such, it's much easier to treat it as some sort of "true" random source, but it's an unpredictable deterministic system.
user2357 avatar
us flag
@SAIPeregrinus thank you.
Score:-3
cn flag

What can chaos provide to cryptography?

It can provide good entropy. And with entropy, we have truly random numbers. Useful in cryptography.

There is a mathematical concept called deterministic chaos. That's a blend of chaos that is a 'bit' predictable. The classic examples are Strange Attractors like:-

attractor

You can see that it is both predictable in that the curve orbits two loci, yet the particular orbits are impossible to predict in detail. Entropy (typically Kolmogorov—Sinai [a bit beyond me]) is generated when you measure relative differences in phase space. A good reference is Noise, chaos, and $(\epsilon, \tau)$-entropy per unit time.

Another classic example is the haveged entropy daemon. It utilises CPU flutter to generate it's entropy. Thus you have the entropy sources for true random number generators.

Of course this only applies to hardware implementations like Chua's circuit and real CPUs. Any mathematical model will be entirely deterministic.

user2357 avatar
us flag
Thank you. My internet is in Chaos equations which is deterministic. Aside from that, if what it provides is the entropy, so is not this makes at most is a pseudo-random generator which could be used for stream ciphers (if this even possible)? For example, for the block ciphers is not the chaos just may be used for generation of random sequence which is separated for our construction of the cipher which we built to be stream or block cipher? Is it feasible to build a whole branch of crypto on a family of prng, e.g. LFSR?
user2357 avatar
us flag
I have another question: if our goal is true random sequence, is not this is one time pad, which is not practical?
Paul Uszak avatar
cn flag
@user2357 1) Well, a PRNG only has the entropy of the seed value, say 128 bits. That's it, no matter the length of the output sequence. A chaos based TRNG has infinite entropy output.
Paul Uszak avatar
cn flag
@user2357 2) A truly random sequences are used for key generation, and seeding PRNGs. Otherwise where does the initial entropy come from? And OTPs are practical as they've been used for a century; see http://users.telenet.be/d.rijmenants/en/onetimepad.htm for a really good review. The reason we are drawn to OPTs (and so are governments, banks & NATO) is that they are guaranteed unbreakable for all time, which is not true for common cryptographic primitives.
user2357 avatar
us flag
thank you......
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.