Wednesday 10th March, 2010: 11:00 -13:00
Cryptography using Chaos
J M Blackledge
Stokes Professor
Dublin Institute of Technology
[Link]
Distinguished Professor
Warsaw University of Technology
Lectures co-financed by the European Union in scope of the European Social Fund
What is the Problem ?
The Concept
Chaos Theory Cryptology
Mathematical study Mathematical study
of Nonlinear of cryptography
Dynamical systems & cryptanalysis
Chaos-based
Cryptology
Why use Chaos ?
A Complexity Theoretic Approach based on
Multi-Algorithmicity
Complexity
Chaotic
Ordered Random
Information Entropy
Applications
Stream coding Spread Spectrum
[Link]
Principal Publication
Multi-algorithmic Cryptography using
Deterministic Chaos with Applications
to Mobile Communications, J M Blackledge,
International Society for Advanced Science &
Technology, Transactions on Electronics and
Signal Processing, No. 1, Vol. 2,23 - 64, 2008;
[Link]
Contents of Presentation I
Part I:
Basic Concepts in Cryptography
Substitution Ciphers
Principal Conditions
Example Algorithms
Diffusion and Confusion
Kerchhoff-Shannon Principle
Summary
Interval (10 Minutes)
Contents of Presentation II
Part II:
Multi-algorithmicity
Designing Chaotic Algorithms
Software Development
Applications
Crypstic
Demonstration
Research Project Proposal
Questions
Cryptology:
Contributing Subject Areas
What is a Cryptosystem?
A cryptosystem is a computer program transforming
information in a key-dependent and apparently
unpredictable manner
key
input output
(plaintext) CRYPTOSYSTEM (ciphertext)
Basic Concepts in Cryptography
Box strength : strength of Encryptor E/D
Combination # : strength of Key K (length of #)
Symmetric Encryption
A & B agree on
combination # a priori
A & B undertake the
same lock/unlock process a symmetric process
Vulnerable to attack if interceptor obtains
combination # when A & B agree upon it
Problem: How should A & B exchange the key?
Multiple Encryption
Uses many locks or Keys Kn
Based on application of the same
encryption/decryption algorithm E/D
Used to increase effective key length, e.g.
Digital Encryption Standard 3 (DES3)
Asymmetric Encryption
A sends B an open lock
with combination known
only to A.
B secures box with lock &
sends box (with message)
back to A an asymmetric process
A is vulnerable to receiving disinformation
if open lock is intercepted
Problem: How can A authenticate the message from B?
Three-Way-Pass Protocol
A locks box with combination
# known only to A and sends
it to B
B locks box with another lock
and a combination # known
only to B and sends it back to A
A (partially) unlocks box and sends it back to B
B (completely) unlocks box to recover message
Protocol is vulnerable to 3-pass interception
Public/Private Key Encryption
A locks box with a public
combination # unique to B
- a public key
Some property of this public
key is known only to B
This property (the private key) allows B to
unlock the box
Vulnerability of method depends on the property which
depends on the design details of the lock
Principal issues in Cryptography
Cryptographic systems should be designed
with respect to three components:
- cyphertext generation
- key exchange
- authenticity
Each component tends to rely on separate
and distinct methods of approach
A Simple Cipher:
The Caesar Cipher
K:
P:
C:
Computing the Caesar Cipher
using Modular Arithmetic
Let A=0, B=1, C=2, , Z=25 and K be the
shifting key
Let Pi denote the Plaintext string
Caesar ciphertext is given by
Decryption is based on
MOD? If Pi + K or Pi - K are not in the range 0-25,
Then subtract or add 26, respectively
The Vigenere Cipher
The Caesar cipher is a monoalphabetic
substitution cipher
The key is easily recovered through statistical
analysis, i.e. searching for the most frequently
occurring letter in the cipher
Vigenere encryption is based on an obvious
extension to produce a polyalphabetic
substitution cipher, i.e.
Vernam Cipher (1919)
Substitution cipher based on generating an
array of random integers to form a vector n
Cipher is given by (vector addition)
Number code used for p (and c) must be
standardised, e.g. 7-bit ASCII code so that
Example of a Vernam Cipher
Substitution (Stream) Ciphers
Plaintext character substituted for randomly
selected character generated by a cipher n
Decimal space
Usually implemented using bit-wise operators,
operating on binary strings, e.g.
Binary space
8-bit XOR based Encryption
Principal Conditions for
|
n - the cipher is generated by some physical
effect or computed using a numerical algorithm
that can be seeded by a key K
The algorithm should produce random numbers
with no statistical bias maximum confusion
n should be ultra-sensitive to K :
a change of 1 bit in K should potentially effect all
the bits of n maximum diffusion
n must have a long cycle length
Examples of Cipher Generation I
SIGSALLY (Green Hornet): AT & T (1942-46)
Noise generated using a vacuum tube
and stored on a phonograph record
Record used to mask 1-to-1
voice signals
Distribution of noise sources
strictly controlled
Records were in effect
one-time-pads
Examples of Cipher Generation II
HotBits
[Link]
Atmospheric radio noise
[Link]
Quantum Mechanical noise using
a reverse biased semiconductor
junction [Link]
Iterative Cryptosystems
Most cryptographic systems are based on a series of
so-called round transformations, which are relatively
simple and produce Pseudo Random Number Streams
Pseudo Random Number Generators (PRNG)
A PRNG is a function or an algorithm that produces a
sequence of numbers from a relatively short seed (initial
conditions: password, plaintext) based on some iteration
function
key
iteration
Input function Output
N rounds
The mod Function
Modular based functions tend to behave
more erratically than conventional functions
amod(b) gives the remainder of a/b, e.g.
23mod(7) = 2, 6mod(8) = 6
amod(b)=a-bfloor(a/b)
Example Algorithms for Computing
Blum Blum Shub generator
where p and q are two prime numbers
Blum Mercali generator
where q is a prime and p is an odd prime
RSA (Rivest, Shamir and Adleman) generator
where e is a relative prime of p-1 and q-1
Maximum Entropy Encryption
Encryption process changes the statistics of cipher
Statistics of the ciphertext become non-uniform
Solution is to pad the plaintext (with ? = 63 for 7-bit ASCII)
Diffusion + Confusion
Cycle Length Analysis using
Autocorrelation & Power Spectrum
Kerchhoff-Shannon Principle
Kerchhoffs Principle:
A cryptosystem should be secure even if everything
about the system, except the key, is public knowledge
Shannons Principle:
The enemy knows the system, i.e.
THE ALGORITHM
Some Golden Rules
Security is a process not a product
Never underestimate the enemy
The longer that any cryptosystem, or part
thereof, remains of the same type with the
same function, the more vulnerable the
system becomes to a successful attack
inclusive of THE ALGORITHM
If you want to know what you are eating then
grow it and cook it yourself
The RSA Algorithm
The Rivest, Shamir & Adleman algorithm is as follows:
Prime numbers p & q are chosen together with e < pq
A obtains public key for B - given by (e, pq) - and sends
B has a private key d such that ed-1 is divisible by
(p-1)(q-1), i.e. d is the solution of
B recovers message using
Important Points
To compute d, e must be a relative prime of (p-1)(q-1). This
means that e & (p-1)(q-1) have no common factors except 1
The prime numbers p & q and the number e < pq must be
distributed to Alice and Bob in such a way that they are
unique to Alice and Bob on the condition that d exists!
This requires an appropriate infrastructure to be established
by a trusted third party whos business is to distribute values
of e, pq & d to its clients a Public Key Infrastructure (PKI)
Internet Communications
Vulnerability to an Attack
e and pq are known and p and q must be prime
numbers - elements of a large but (assumed) known set.
To attack the cipher, d must be found and it is known that d
is the solution of
which is only solvable if e < pq is a relative prime of
(p-1)(q-1).
An attack is based on searching through prime numbers
whose magnitudes are consistent with the product pq until
the relative prime condition is established for factors p and q.
Public Key Infrastructure (PKI)
A PKI is required in order to distribute public keys,
i.e., different but appropriate values of e and pq,
for use in public key cryptography (RSA algorithm)
Requires the establishment of appropriate authorities and
directory services for the generation, management and
certification of public keys
Vulnerable to authorities (operating in UK) having to conform
to the Regulation of Investigatory Powers Act (UK) 2000,
Section 49
Summary
Encryption systems belong to two basic classes:
- symmetric
- asymmetric
Encryption algorithm should provide a cipher with the
following basic properties:
- Maximum entropy of cipher
- Maximum diffusion of key
- Long cycle length of cipher
Encryption algorithm is taken to be public knowledge
The Kerchhoff-Shannon Principle, e.g. RSA Algorithm
In the Following Lecture
We shall investigate the properties of
chaotic signals
Consider a multi-algorithmic approach
for designing encryption engines
Provide an overview of Crypstic
Provide a demonstration of the product
Questions
+
Interval (10 Minutes)
Part II: Contents
Chaos and Cryptography
Iteration Functions Systems
Chaos and Pseudo-Chaos
The Lyapunov Exponent
Designing Chaos-based Encryption Algorithms
Multi-algoritjmicity
Crypstic
Demonstration of Crypstic
Q&A
Cryptography using Chaos
Founders of Founders of
Modern Cryptography Chaos Theory
Claude Vladimir Mitchell Benoit
Shannon Kotelnikov Feigenbaum Mandelbrot
Algorithm(s) for n Iteration Function
Systems (IFS)
Brief History of
Chaos-based Cryptography
Early 1950s: Shannon explicitly mentions
that the basic stretch-and-fold mechanism
of chaos can be used in cryptology.
Silent period until the late1980s.
Chaos theory becomes popular
Cryptography becomes more important
~ 30 publications in 1990s
Various ciphers suggested
Focus on analog circuits
Claude Shannon
2000++: Chaos begins to be recognized
1916 - 2001
spread spectrum for military communications
launch of Crypstic by Lexicon Data Limited
Chaos and Cryptology:
Similarities 1
Deterministic
chaotic map
encryption algorithm
Complex and Unpredictable
random-like behavior for any external
observer with no a priori knowledge of the
algorithm and initial condition - key
Chaos and Cryptology
Similarities 2
Chaos Cryptography
sensitivity to key-dependent
initial conditions confusion & diffusion
Small variations of any variable changes the
outputs considerably
Modification of 1 bit of the plaintext or key
should change all bits of the ciphertext with
probability 50%.
Chaos and Cryptology
Similarities 3
Chaos Cryptography
topological
transitivity with multi-round
iterative process transformations
Bounded state space, self-mapping, extension
of a state point over the whole state space
Iterative transformations with a single chaotic
map
Chaos and Cryptology
Principal Differences
Chaotic systems are defined on real/complex
numbers spaces (bounded continuous space)
whereas cryptography uses binary sequences
(finite discrete space).
Chaos theory aims to understand the asymptotic
behavior of iterative process whereas cryptography
focuses on the properties of a number of first few
iterations
Chaos Theory .v. Cryptography
Simple Example of an IFS:
The Vurhulst Process
Linear exponential model
Nonlinear model
Example Iteration Function
System (IFS)
Feigenbaum Diagram
Self-Affine Characteristics
Properties of Chaotic Systems
Required for Cryptography
Sensitivity to the initial conditions
It is impossible to predict the behaviour of
the system even if we have partial
knowledge of its organization.
Topological transitivity
The state point stays within a bounded
state space and approaches infinitely
closely to any point of the state space.
A Deterministic Chaotic System
Deterministic system is defined by a IFS f(x)
Input is initial condition x0 and parameter r
Output is a sequence of states: x1 , x2 , x3 , where
xi +1 = f (xi , r)
parameter
r
initial iteration time series
condition x0 function f x1, x2,
Matthews Cipher
Chaos and Pseudo-Chaos
True Chaos has an infinite number of
states
Pseudo-Chaos has a finite number of
states
Involves approximation of continuous
chaos with floating- or fixed-point
arithmetic
Leads to discrete chaos-like system with
low cycle lengths
Floating-point Approximation
Continuous Chaos
0 1
x2 x3 x0 x1
Floating-point Approximation
( ) ( ) ( ) ( )
0 1
x2, x3, x4, x0 x1
Example Cycle Length
Distribution (Vurhulst Process)
Chaos .v. Pseudo Chaos
Infinite orbit (Chaos) Finite orbits (Pseudo-Chaos)
Cryptographically Good Orbits
Single orbit Multiple orbits
of the same length
Stability of an Iterative Process
Consider the iterative process
and a model for the error at each
iteration given by
Then
Measure of Stability
Rearranging and summing over N iterations:
Thus
The Lyapunov Exponent
level off
Measures the sensitivity
of an iterated function to
the initial condition (key)
Require the exponent
to be: linear
growth
- >0 (chaotic behaviour) exponential
growth
- approach 1
(extent of chaoticity)
Maximum Entropy Ciphers
PDFs of chaotic iterators are not uniform
Bit stream cipher generated using a uniform PDF
partitioning strategy to maximize entropy of cipher
Encryption based on XOR operation
Example of a Chaotic Cipher with
Poor Statistical Characteristics
Basic Design Steps
Chaos-based .v. Conventional
Encryption Algorithms
Chaos-based cryptography has many disadvantages
accept with regard to one important issue: can invent
an unlimited number of algorithms
Multi-algorithmicity:
Meta-Encryption Engines
Single Encryption Multiple Encryption
Algorithm Algorithms Algorithms
Algorithm
Energy Energy Keys
1D Search Domain 2D Search Domain
Keys Keys
Chaotic Function Selection
over Chaotic Block Lengths
Analogous to the M Algorithm which is a method for
combining multiple pseudo random streams to increase
their security where one generators output is used to
select a delayed output from another generator.
The last floating point number of a current block cipher
is used to seed the next block cipher
Example Algorithms and
Parameter Settings
Crypstic provides a unique encryption engine (unique set of algorithms)
mounted on a single pair of portable USB flash memory units
Includes Honey pot disinformation, e.g. other encryption applications
New meta-encryption engine provided if Crypstic is compromised
Enigma Scherbius Shannon CrypsticTM
Covert Access Through Obfuscation
Camouflage encryption
engine by embedding it in
files of a similar type:
a dll file
Execution is based on
renaming a known dll
to a known exe file
through deletion
Requires that application is
software engineered to be
Forensically Inert
Demonstration of Crypstic
[Link]
Multi-Algorithmic Block Encryption Engine
Unique set of algorithms for each encryption engine
Algorithm selection & initiation seeded by file properties
Passes all statistical test recommended by NIST, USA
Implementation
Flash memory
Forensically inert
Key-logging evasion
Applications to Cloud Computing
Advantages .v. Disadvantages
Sovereignty is a potential
major problem for the Cloud
Need to treat the Cloud as a
hostile territory
User-based security is the
most likely solution
Cloud Security
Cloud computing only represents 4% of current IT spend
and is expected to more than double by 2012
Software as a Service (SaaS) by itself is projected to nearly
double from $9B to $17B (less than 10% of total market)
User-security underpins acceptance of cloud architecture
Each user has own encryption engine enabling both
protection and control PC + Crypstic
Summary
Chaos-based encryption has many disadvantages
compared with conventional encryption algorithms:
- computationally inefficient
- low cycle lengths
The principal advantage is that it provides the potential for
developing an unlimited number of algorithms that can be
used to produce a multi-algorithmic solution
Algorithms can be published so that approach conforms to
the Kerchhoff-Shannon Principle in the knowledge that a
new set of chaos-based algorithms can be developed.
Open Problems
Structurally stable pseudo-chaotic systems
Require a structurally stable cryptosystem, i.e. a system
that has (almost) the same cycle length and Lyapunov
exponents for all initial conditions. Most of the known
pseudo-chaotic systems do not possess this property
Conditions of unpredictability for chaotic systems
What properties of a chaotic system guarantee its
computational unpredictability ?
Research Project Proposal 1:
Chaos based Asymmetric Encryption
Asymmetric cryptographic systems are based
on trapdoor functions, i.e. functions that
have a one-way property unless a secret
parameter (trapdoor) is known
No counterpart of a trapdoor transformation
is, as yet, known in chaos theory
Research Project Proposal 2:
Forensically Inert Software Engineering
Conventional software engineering
Clarity > Efficiency :: Data > Process
Forensically inert software engineering for
Obfuscation > Efficiency :: Camouflage > Process
What are the paradigms best suited to the
development of forensically inert applications?
Q&A