A chaos-based approach to the design of cryptographically secure substitutions

doi:10.1016/j.physleta.2005.05.057

Physics Letters A

Volume 343, Issues 1–3, 1 August 2005, Pages 55-60

https://doi.org/10.1016/j.physleta.2005.05.057 Get rights and content

Abstract

We show that chaotic maps may be used for designing so-called substitution boxes for ciphers resistant to linear and differential cryptanalysis, providing an alternative to the algebraic methods. Our approach is based on the approximation of mixing maps by periodic transformations. The expectation behind is, of course, that the nice chaotic properties of such maps will be inherited by their approximations, at least if the convergence rate is appropriate and the associated partitions are sufficiently fine. We show that this is indeed the case and that, in principle, substitutions with close-to-optimal immunity to linear and differential cryptanalysis can be designed along these guidelines. We provide also practical examples and numerical evidence for this approximation philosophy.

Introduction

Over the past decade, there has been a tremendous interest in studying the behavior of chaotic systems. They are characterized by sensitive dependence on initial conditions, similarity to random behavior, and continuous broad-band power spectrum. Chaos has potential applications in several functional blocks of a digital communication system: compression, encryption and modulation. The possibility for self-synchronization of chaotic oscillations [1] has sparked an avalanche of papers on the application of chaos in cryptography. An attempt only to mention all related papers on chaos and cryptography in this short presentation, would result in a prohibitively long list, thus we refer the reader to some recent work [2].

In this Letter we explore the feasibility of designing cryptographically secure substitutions via approximation of mixing maps by periodic transformations. In order to adapt the continuous dynamics of a mixing map to the block structure of a cryptosystem and, most importantly, to assure that the good statistical properties of the first are transferred to the second, we use periodic approximations of dynamical systems. Clearly, one expects that the better the mixing properties of the approximated dynamical system, the better the cryptographic properties of the discrete maps obtained in the process of approximation. The subject of the present Letter is precisely the relation between the dynamical system used for encryption and the quality of the resulting cryptosystem as quantified by its immunity to linear and differential cryptanalysis, which are currently the benchmarks for measuring the safety of the standard block ciphers.

Let $F : Z_{2}^{n} \to Z_{2}^{n}$ be a permutation of n-bit blocks (or an $n \times n$ S-box in cryptographic parlance) and, as usual, denote by ${LP}_{F}$ and ${DP}_{F}$ the linear approximation probability and differential approximation probability of F, respectively. ${LP}_{F}$ and ${DP}_{F}$ measure the immunity of the block cipher F to attacks mounted on the corresponding cryptanalysis, immunity being higher the smaller their values. We show in this Letter that if F is a cyclic periodic approximation of a mixing automorphism and some assumptions are fulfilled, then ${LP}_{F}$ and ${DP}_{F}$ get asymptotically close to their greatest lower bounds $1 / 2^{n}$ and $1 / 2^{n - 1}$ , respectively, thus obtaining an arbitrarily close-to-optimal immunity to both cryptanalyses. In his seminal paper “Communication Theory of Secrecy Systems”, Shannon suggested mixing transformations to be used for practical encryption systems. He wrote [3]:

“Good mixing transformations are often formed by repeated products of two simple noncommuting operations. Hopf has shown, for example, that pastry dough can be mixed by such a sequence of operations. The dough is first rolled out into a thin slab, then folded over, then rolled, and then folded again, etc. In a good mixing transformation of a space with natural coordinates $x_{1}, x_{2}, \dots, x_{N}$ , the point $x_{i}$ is carried by the transformation into a point $x_{i}^{'}$ , with $x_{i}^{'} = f_{i} (x_{1}, x_{2}, \dots, x_{N}), i = 1, 2, \dots, N,$ and the functions $f_{i}$ are complicated, involving all variables in a ‘sensitive’ way. A small variation of any one, $x_{3}$ , say, changes all the $x_{i}^{'}$ considerably. If $x_{3}$ passes through its range of possible variation, the point $x_{i}^{'}$ traces a long winding path around the space.”

Hence, we prove, as suggested by Shannon, that mixing (chaotic) transformations may indeed be used in encryption systems, providing an alternative to the traditional algebraic methods.

Section snippets

Theory

Given any pair of binary n-blocks $α = (α_{1}, \dots, α_{n}) \neq 0$ , $β = (β_{1}, \dots, β_{n})$ ≠0, and a permutation (or substitution) F on n-blocks $ξ = (ξ_{1}, \dots, ξ_{n})$ , the linear approximation probability of F ( ${LP}_{F}$ for short) [4] is defined as ${LP}_{F} = \max_{α, β \neq 0} {LP}_{F} (α, β),$ where ${LP}_{F} (α, β) = {(2 p - 1)}^{2}$ , $p = \frac{1}{2^{n}} # {ξ : ξ_{1} α_{1} \oplus \dots \oplus ξ_{n} α_{n} = F {(ξ)}_{1} β_{1} \oplus \dots \oplus F {(ξ)}_{n} β_{n}},$ # denotes cardinality and ⊕ addition modulo 2. Therefore, the linear approximation probability ${LP}_{F}$ is the square of the maximal imbalance of the following event: the parity of the input bits selected by the

Software implementation

Given an automorphism T in, say, an interval $X \subset R^{n}$ , it is in general not known how to construct periodic approximations of T (see Example 3 below for an exception) but it can be proved [6], [9] that if $(T_{n}, P_{n})$ is a cyclic approximation, then the $T_{n}$ -orbit ${T_{n}^{k} x : k ⩾ 0}$ ‘shadows’ the T-orbit ${T_{n}^{k} x : k ⩾ 0}$ for typical $x \in X$ up to the precision set by the partition $P_{n}$ ; the finer $P_{n}$ , the better $T_{n}$ will mimic the continuous dynamic of T. This fact can be exploited in various ways to define substitutions on n

Conclusion

In this Letter we proposed periodic approximations of mixing dynamical systems as a practicable way one can go to construct cryptographically secure substitutions. Indeed, although the theoretical results are of abstract nature, the leading principle behind can be materialized in a simple form. More importantly, the numerical implementations support this approach in quite satisfactory terms.

Acknowledgements

We are grateful to T. Michalek and A. Ivanovski for stimulating discussions. This research is supported in part by the NSF.

References (10)

E. Biham et al.
J. Cryptology
(1991)
K. NybergK. NybergM. Sivabalan et al.
G.H. Hardy et al.
An Introduction to the Theory of Numbers
(1979)
L.M. Pecora et al.
Phys. Rev. Lett.
(1990)
M.S. Batista
Phys. Lett. A
(1998)
S. Sundar et al.
Phys. Rev. Lett.
(2000)
L. Kocarev
IEEE Circuits Systems Magazine
(2001)
L. Kocarev et al.
Phys. Lett. A
(2001)
G. Jakimovski et al.
IEEE Trans. Circuits Systems, Part I
(2001)
A. Palacios et al.
Phys. Lett. A
(2002)
S. Wang
Phys. Rev. E
(2002)
P. Garcia
Phys. Rev. E
(2002)
N.K. Pareek et al.
Phys. Lett. A
(2003)
R. Tenny
Phys. Rev. Lett.
(2003)
R. Mislovaty
Phys. Rev. Lett.
(2003)
K.W. Wong
Phys. Lett. A
(2003)

There are more references available in the full text version of this article.

Cited by (19)

Exploiting randomness on continuous sets
2007, Information Sciences
In this paper, we introduce a new type of field—continuous sets, where we can exploit randomness in the non-repeating decimal expansions of irrationals for cryptographical purposes, and present two specific sets, a real interval [0, 1) and a functional space F_[0, 1). On [0, 1), we propose ideal irrational random number generator (IIRNG) which generates non-repeating random number sequence as a truly RNG by computing the decimal expansion of an randomly chosen irrational. On F_[0, 1), we propose integral encryption scheme (IES) with which we can encrypt an infinite message and obtain perfect security in one-time encryption by computing the integration of the message on a randomly chosen function. Either the seeds of IIRNG or the keys of IES are sufficiently safe and immune to exhaustive key search. Both IIRNG and IES require the assumption that an element of [0, 1) or F_[0, 1) can be uniformly randomly chosen. Though the assumption cannot be achieved in classical finite machine, we present the discretization of the assumption, i.e., randomly choosing an element of U or V (the set of all possible methods of generating irrationals or functions). The immunity of seeds or keys to exhaustive key search still exists, since any finite search for a random element of U or V is inefficient. This is the basic idea of implementing IIRNG and IES in finite machine. Two corresponding examples IRNG and IBC are also presented, whose securities are guaranteed by the randomly chosen elements of U or V.
Dynamic Analysis and Adaptive Synchronization of a New Chaotic System
2023, Journal of Applied Nonlinear Dynamics
A Dynamic S-Box Construction and Application Scheme of ZUC Based on Chaotic System
2020, Jisuanji Yanjiu yu Fazhan/Computer Research and Development
A Circuit Design of Discretized Chaotic Maps with Two Iterations for Speeding up S-box Generation
2019, Proceedings - APCCAS 2019: 2019 IEEE Asia Pacific Conference on Circuits and Systems: Innovative CAS Towards Sustainable Energy and Technology Disruption
A novel method for constructing the S-box based on spatiotemporal chaotic dynamics
2018, Applied Sciences (Switzerland)
LabVIEW implementation of chaotic masking with adaptively synchronised forced Van der Pol oscillators and its application in real-time image encryption
2017, International Journal of Simulation and Process Modelling

View all citing articles on Scopus

View full text

A chaos-based approach to the design of cryptographically secure substitutions

Abstract

Introduction

Section snippets

Theory

Software implementation

Conclusion

Acknowledgements

J. Cryptology

Phys. Rev. Lett.

Phys. Lett. A

Phys. Rev. Lett.

IEEE Circuits Systems Magazine

Phys. Lett. A

IEEE Trans. Circuits Systems, Part I

Phys. Lett. A

Phys. Rev. E

Phys. Rev. E

Phys. Lett. A

Phys. Rev. Lett.

Phys. Rev. Lett.

Phys. Lett. A