##### # #
# # # ## #### #### ## ###
# # # # # # # # #
# # # # #### #### #
# # ###### # # # #
# # # # # # # # # # ###
##### ###### # # #### #### ##### #
#####
# # # ## #### #### # #### ## #
# # # # # # # # # # # #
# # # # #### #### # # # # #
# # ###### # # # # ###### #
# # # # # # # # # # # # # # #
##### ###### # # #### #### # #### # # ######
# #
## ## ###### ##### # # #### ##### ####
# # # # # # # # # # # # #
# # # ##### # ###### # # # # ####
# # # # # # # # # # #
# # # # # # # # # # # #
# # ###### # # # #### ##### ####
Some interesting books:
Douglas R. Stinson
Cryptography: Theory and Practice
CRC Press 1995, 0-8493-8521-0.
Bruce Schneier
Applied Cryptography
John Wiley, 1996, 0-471-12845-7.
1 Symmetric Key cryptosystems Stinson Chap 1
1.1 Some classical Cryptosystems
1.1.1 Description of methods.
1.1.2 Some cryptographic attacks
1.2 Perfect Secrecy. Stinson Chap 2
1.3 The DES algorithm. Stinson Chap 3
1.3.1 Description of the Algorithm.
1.3.2 Background and criticism. Schneier Chap 12
1.4 Attacks on DES
1.4.1 Known Plain Text, Brute Force.
1.4.2 Ciphertext-only attack, Brute force.
1.4.3 Hellman's Cubic Root Attack.
1.5 Double and Triple DES.
1.5.1 Meet-in-the-Middle attack
1.5.2 3DES triple-DES.
1.5.3 Design Myths of DES
1.6 Attacks on DES machinery.
1.6.1 Differential Cryptanalysis.
1.6.2 Differential fault Analysis
1.7 Conclusions
1 Symmetric Key cryptosystems
-----------------------------------
Suppose Alice and Bob are communicating but don't want their
communication to be overheard by others; specifically, they are
bothered by an opponent we shall call Oscar. Alice and Bob may hide
their message using a CRYPTOSYSTEM S = (P,C,K,E,D):
P = Plaintext alphabet
C = Ciphertext alphabet
K = set of keys
E = a collection {Ek} (k in K) of functions P --> C
D = a collection {Dk} (k in K) of functions C --> P
satisfying D_k(E_k(x)) = x.
Alice and Bob agree secretly on a KEY k and further send y = Ek(x)
instead of x; Bob, knowing k, may apply Dk and retrieve x. We call
the symmetric because Alice and Bob use the same key, or, to put it
differently, knowing Ek implies knowing Dk. Oscar cannot find x
from y in the same way as Bob since he doesn't know the key used.
Usually the symbols in P, C, and K are bitstrings of a certain length
and moreover, P and C are usually the same. Assume |P| = |C| = m; we
shall interpret symbols as numbers modulo m.
1.1 Some classical Cryptosystems
------------------------------------
Cryptography has a long history, starting back at the ancient
Egyptians; we mention here a few tricks that have been used through
the ages in order to describe some principles.
1.1.1 Description of methods.
SHIFT system.
The key is an element of Zm, and encryption means shifting m positions
through the alphabet:
Ek(x) = x+k
Dk(y) = y-k.
Example: with k=3 APEKOP becomes DSHNRS so Oscar won't understand.
AFFINE system.
Uses a linear transformation; k = (a,b) where a has an inverse mod m.
Ek(x) = ax+b
Dk(y) = (y-b).a^ (a^ means the inverse of a).
These two methods are both special cases of
PERMUTATION:
The key is a permutation pi of Zm and
Ek(x) = pi(x)
Dk(y) = pi^-(y).
1.1.2 Some cryptographic attacks
Why do we bother about having something more complicated than SHIFT?
Well, because it isn't good enough. Despite the effort of Alice and
Bob Oscar will try to read the message. To find out why he can be
ever succesful, assume Oscar has overheard the SHIFT-ciphertext
DSHNRS.
We shall adopt Kerckhoff's principle:
OSCAR KNOWS WHAT CRYPTOSYSTEM IS BEING USED;
ONLY THE KEY IS UNKNOWN TO HIM.
Couldn't Alice and Bob do better by keeping their algorithm secret as
well as their key?
1. This is not always possible in practice, for example if the
algorithm is implemented in a computer program that can be freely
bought by everyone.
2. Even if A and B do not reveal their algorithm, the possibility that
the working of the method leaks out cannot be neglected. And
because it is not easy to change algorithm (it IS easy to change
key!) it is generally agreed that SAFETY should not rely on
secrecy of algorithms but only on secrecy of keys.
3. By making their algorithm known, Alice and Bob can rely on a vast
society of cryptographers that will warn them if there is something
wrong with their method.
Concluding, hiding algorithms is seen as insensible.
And so Oscar receives DSHNRS and knows it is a shifted text; because
the ciphertext is Oscar's only information, we call this a Ciphertext
Only Attack (COA). He will shift the letters back one by one
DSHNRS
CRGMQR
BQFLPQ
APEKOP
and after three shift will learn a valid word (of Dutch langage in
this case, but by Kerckhoff's principle Oscar knows Dutch! Alice
isn't very polite to Bob, because `Apekop' means `head of a monkey' so
Oscar assumes Alice and Bob are having a little dispute). In the
worst case, Oscar needs about m shifts before seeing the plaintext.
In fact, Oscar is trying all the keys and there are only m of them.
This attack illustrates what is meant by Brute Force: simply trying
all the keys, and this is feasible for every system if the keyspace
is small or the opponent can mobilize a lot of computing power.
AFFINE
(phi(m) denotes the number of integers in [1..m-1] that are relatively
prime to m; we discuss number theory in Class 2 in more depth.)
The AFFINE system with m symbols has m.phi(m) keys and for m=32 this
means 512 which is within feasibility of a modern computer but I shall
demonstrate a more subtle attack. Now
assume that Oscar knows a small fragment of the plaintext: the first
two letters, x1 and x2 say, and the ciphertext is y1 y2 y3 ...
From y1 = a.x1 + b
and y2 = a.x2 + b
(a linear system of two equations with unknown a and b)
we find y1 - y2 = a (x1 - x2)
So a = (y1 - y2) / (x1 - x2) (if x1-x2 has an inverse)
and b = y1 - a.x1
Oscar is unlucky if x1-x2 has no inverse, but if he also knows x3 he has
has more chances because x1-x2, x2-x3, or x3-x1 may be invertible, and
this attack is successful knowing only surprisingly few letters of
plaintext.
The attack can be extended to a COA with statistical analysis, because
not all letters are equally frequent. Blank occurs most often (25%),
followed by e (13%) and t (12%; the exact distribution is language
dependent). In a ciphertext of a few lines, Oscar may pick the symbols
with highest occurrence and guess them to be blank and e and carry out
the above calculations. He will find the key in a few tries.
In this case we observe that some `internal structure' of the system
can be used to have an attack with a complexity that is much lower
than a search of the key space, and the existence of such attacks is
considered a weakness of the algorithm.
SUBSTITUTION
Unfortunately, even the most general system we've seen isn't very
strong. The number of keys (32! = 2.6E35) is large enough to
withstand an attack that tries them all, but as we saw for AFFINE some
well-applied intelligence can be far more effective than `Brute
Force'.
Any permutation, though permuting the symbols, leaves the highest
symbol frequency, the second and third highest, etc, intact (though
they move to another letter). And by counting the relative
frequencies it is easy for Oscar to bring back the blank, e and t in
position, after which he can guess his way to the other letters.
Still more complicated systems work on blocks of letters, combining
substitutions of letters by others of the alphabet with permuting
them with other letters in the text. But these systems didn't
withstand computerized efforts to break them, so we should look for
something more!
1.2 Perfect Secrecy.
------------------------
We saw that in the attack against the shift system it was used that
the attacker can distinguish meaningful messages from random strings.
In fact this difference makes that most cryptosystems reveal the
content of even very short messages. Or, rather, they do not hide
them PERFECTLY but only COMPUTATIONALLY.
Definition.
A system is COMPUTATIONALLY secure if, given a ciphertext Y but not
the key, it is computationally infeasible to extract the plaintext X.
A cryptosystem is PERFECTLY secure if, given a ciphertext Y, for
each plaintext X (of the same length) there exists a key K such
that D_K(Y) = X.
Understandably, perfect secrecy is stronger because the ciphertext
alone, without the key DOES NOT CONTAIN the plaintext information,
while in a computationally secure system the ciphertext may contain
this information.
Lemma: If system S is safe, |K| >= |P|.
Proof: Perfect secrecy states that, given Y, the function D: K -->P
given by D(k) = Dk(Y) is surjective. []
So, in order to send a 100kB file perfectly secure we need a 100kB key
also; surprisingly, such a system exists: the one-time pad.
Alice and Bob share a (long) file of random bits, and XOR with this
file for encryption and decryption: k = k1 ... kn
For message X = x1 .. xl, A computes y1..yl with yi = xi XOR ki
For cipher Y = y1..yl, B computes yi XOR ki and finds xi back.
The next message uses fresh bits, ie, Alice starts with k{l+1}.
Oscar, intercepting Y, still has no clue regarding X, because for each
file X it is possible that the key Y XOR X was used.
Because the size of this key is impractical, it is usually the case
that a small key protects a larger amount of data and we shall now
study how well it can protect it.
Not all n-bit strings are meaningful in the language used by A and B.
Definition: A language L of bitstrings has ENTROPY alpha if there are
2^{alpha n} strings of length n. The redundancy rho is 1-alpha.
Suppose a message Y = Ek(X) was intercepted; of course Dk(Y) = X, but
what happens if Y is `decoded' with a different key k'? If a string
outside L is found the key can be rejected, but if the result is a
meaningful string, we call k' a spurious key. WE ASSUME THE
CRYPTOSYSTEM MESSES UP THE STRUCTURE OF STRINGS SUFFICIENTLY TO MAKE
Dk'(Ek(X)) A RANDOM BIT STRING.
Lemma: The probability that k' is spurious is 2^{alpha n} / 2^n.
Proof: There are 2^{alpha n} strings in L out of a total of 2^n. []
So the expected number of spurious keys in the key space is (at most)
2^b . 2^{alpha n} / 2^n = 2^b / 2^{n.rho},
and if n > b/rho, we expect less than one spurious key!
In this case, it is most likely that there is only one key that can be
used with Y and give a meaningful result; in other words, there exists
only one plaintext that is the decryption of Y.
The number b/rho is called the UNICITY DISTANCE of a cryptosystem /
languag combination and it is usually surprisingly low. Natural
languages have high redundancy: their entropy is below 25%, so rho is
0.75. The subtitution system, with 26! = 2.58E22 = 2^75 keys has a
unicity distance of about 100 bits (circa 20 characters)!
The difference between perfect and computational security can be
illustrated. Indeed, for messages longer than the unicity distance, no
perfect secrecy exists because each message has a UNIQUE decryption.
Finding it may require the inspection of all 2^b keys, which should be
infeasible so that we do have computational secrecy.
Exercises:
---------
What happens to the unicity distance if Alice and Bob compress their
messages before encryption? Assume their language is 25% entropic and
their key is 80 bits. What is the unicity distance and how does it
change with a 2-fold, three-fold, four-fold or five-fold compression?
Prove that SHIFT is perfectly secure as long as you encrypt only a
single character.
1.3 The DES algorithm.
-------------------------
Around 1970 it was recognized that cryptography should move from the
military and diplomatic apparatus to the civil industry because banks
and industries needed cryptography to do business over computer
networks. The methods must be PUBLICLY KNOWN to allow cooperation
between various businesses. This is widely accepted in the scientific
community (Kerckhoff!) but the idea to show your algorithms was quite
controversial in the world of the military and the American
government. The American NBS, national bureau of standards, invited
proposals for a cryptographic standard. The proposal of IBM was the
only one, hence `chosen' as the Data Encryption Standard, DES.
Brief DES History:
1970 IBM has cryptosystem LUCIFER
1972 Banks want cryptography and ask NBS for standard.
1974 IBM develops LUCIFER into system that encrypts
128b blocks using 112b key.
NSA `works' on DES and presses IBM to halve the block
and key size!!
1976 DES adapted as standard
1978 First inventions of PUBLIC KEY cryptography.
1980 Invention of Hellman's Cubic Root Attack
1990 Invention of Differential Cryptanalysis
Proposal for IDEA
1996 Invention of Differential Fault Analysis
1.3.1 Description of the Algorithm.
------------------------------------
The DES algorithm uses a 56 bit key and operates on blocks of 64 bits
of data. In other words, DES specifies a collection of 2^56 functions
of {0,1}^64 to itself and their inverse.
The data undergoes 16 iterations, each driven by a 48b iteration key;
for the iteration key a selection of the 56 master bits is made (which
bits are used in each iteration is fixed and public).
In each iteration (sheet 2-2), half of the data is passed unchanged
and combined with the key to mess up the other half; so
Y1 = X1
Y2 = X2 XOR f(X1,K)
And this iteration is self-inversive; indeed, with
Z1 = Y1
Z2 = Y2 XOR f(Z1,K)
we find Z1,Z2 = X1,X2.
Sheet 2-3 shows how you can iterate this three times, and 2-4 shows
the layout of the complete machine with its 16 rounds.
If you were to build a machine, I would give you some extra details.
Such as, which bits of the key are used in each iteration, and I would
specify f. But you can find this information in any book.
1.3.2 Background and criticism.
--------------------------------
The algorithm was designed with hardware implementation in mind. It
contains a lot of bit-wise operations, and operations like a shift or
permutation of bits, actually costing nothing when implemented in
hardware.
Current hardware chips are extremely fast: there are 10$ chips that
perform circa 100 million en/decryptions (1E8) per second.
DES is a VERY GOOD ALGORITHM: there is no better attack known than to
try all the keys (Brute Force Attack), but here we have the main DES
problem: the key size is too small to withstand a serious BFA. The
original proposal used 112b keys on 128b data blocks, but an American
Agency, NSA, said that in the standard the width of data and keys
should be smaller. Critics say they wanted this so that they would be
able to read all encrypted data themselves, and there is truth in
this; we shall study the attacks below.
Meanwhile, DES is tremendously popular in the banking and
administration world, and is not likely to disappear very soon.
Around 1990 a new algorithm, called IDEA, was developped. This
algorithm is a little bit like DES, but it has 128 bit key and 64b
data, and it operates on the data in 16b blocks rather than individual
bits, making it more suitable for software implementation.
1.4 Attacks on DES
----------------------
Most of the attacks launched agains DES are very general in the sense
that they treat the DES algorithm as a `block box' and hence apply
against ANY cryptosystem.
1.4.1 Known Plain Text, Brute Force.
First assume Oscar has somehow learned the plain version X of ONE
intercepted ciphertext Y; how long does it take to test all keys k if
Ek(X) = Y?
Well, there are 2^56 = 7E16 keys; so with 10000 of the chips (an
investment of circa 100 k$) you can try 1E12 per second and finish in
7E4 seconds, just under a day.
The conclusion is that today DES is simply not strong enough against a
modestly rich opponent. In 1974 the computational effort for a BFA
was restricted to a very powerful organization, and at the time there
was one: NSA.
1.4.2 Ciphertext-only attack, Brute force.
Even without knowing some plain text, Oscar is not really going to
have a bad time, because the unicity distance is deplorably small;
assume Oscar knows A and B communicate in ascii, which is 1/8 redundant.
Then the unicity distance is 56/(1/8) bit, or just 7 blocks!
So Oscar must decrypt seven blocks (instead of just 1) with every key
and test if the result is ascii.
A BRUTE FORCE ATTACK ON CIPHERTEXT ONLY IS JUST SEVEN TIMES MORE WORK
THAN A KNOWN PLAINTEXT ATTACK!
In seven days the job is done.
Compression (BEFORE encryption) helps, but no miracles should be
expected.
1.4.3 Hellman's Cubic Root Attack.
Mathematicians would view Encryption as a function on TWO parameters,
mapping a plaintext & key combination on a ciphertext:
E: P x K --> C
Alice and Bob, having fixed k, view it as a function on plaintext
because the variable key is not of interest to them:
Ek : P --> C.
Oscar however, does not know the key and there is an attack based on
the effect of encryption on a SINGLE plaintext; Oscar views E as a
one-way function:
Ex: K --> C.
(I call it one-way because Oscar doe not have any computable inverse
at his diposition.)
Oscar fixes some arbitrary x and at some point seduces Alice to
encrypt x, and overhears the result Y = Ex(k): we call this a Chosen
Plaintext Attack.
DISCUSSION: How can you ever make a chosen plaintext attack?
(Fake Secret, Bank Card, Version number)
In fact, Hellman's algorithm is a general strategy to retrieve
inverses of one-way functions. First consider these two extreme
strategies for Oscar:
1. Time intensive, no storage.
After hearing Y = Ex(k), Oscar tries all
2^56 possible k. We have seen that, though this is on the border of
feasibility for some opponents, generally very time consuming.
2. No time, memory consuming:
Oscar PRECOMPUTES all 2^56 values of Ex(k), and after hearing Y can
retrieve k from his table.
Storing 2^56 pairs of 112bits takes 5E17 Bytes of storage, which is
500 million Gigabyte disks. Not exactly feasible.
Hellman's method takes a way inbetween by trading memory for time;
the PRECOMPUTATION remains the same 2^56, but time and memory of the
actual attack are between these limits, with the same product. The
attack is based on iterating the function Ex, but it is a bit annoying
that it takes a 56b key and has 64b output; therefore Oscar combines
Ex with an (arbitrary) REDUCTION function R that selects 56 of the 64
bits. R.Ex is function that maps 56b on 56b, and let y=R(Y).
Suppose Oscar wants to spend M memory and T time on an attack; write S
= M.T.
Precomputation of one attack:
1. Choose M random strings (56b) X10...XM0.
2. For each i, iterate REx T times on Xi0, ie, compute a chain
Xi0, Xi1, Xi2, ... XiT.
3. For each i, store Xi0 and XiT.
Now Oscar evaluated the function S times, namely on
Xij for i=1..M and j=0..T-1.
When Oscar gets y = R(Ex(k)), he can find k in T time IF the value of
k did appear among the S values Xij. Observe that
IF k = Xij, THEN RE^{T-j}(k) = RE^{T-j-1}(y) = XiT
but not necessarily vice versa.
1. Iterate REx on y T times:
Compute y, RE(y), RE(RE(y)), etc, until RE^T(y).
2. For each RE^j(y), check if it equals XiT for some i.
3. If so, compute k' = RE^{T-j-1}(Xi0) and check if Ek(X)=Y.
There may be some `false hits' in step 1 where RE^j(y) = XiT
but the key k' = RE^{T-j-1}(Xi0) does not work. Fortunately the
expected number of false hits is very small (the expected number of
good hits also, By the way!!) so this does not influence the
complexity significantly, and the search time is about T.
The success probability equals the fraction of the keys present among
the S values Xij; unfortunately, this number can be even smaller than
S because of overlap. Probability theory reveals that the number of
different values stays well above 0.8S as long as MT^2 < N ( = 2^56).
So we take M = T = N^1/3, yielding a table with N^2/3 values, about as
many of these different; the succes probability is then approximately
S/N, or 1/(N^1/3). To have more success, Oscar launches N^1/3 of
these attacks independently, namely, with different reduction
functions!
As the cubic root of 2^56 is about a million, the idea is:
- There are a million tables, each made with a different R.
- Each table has a million pairs Xi0 XiT.
- To search one table you iterate a million times.
Each table is about 16 MB which fit main memory; iterating a million
times plus table search takes one tenth of a second with good hardware
and with only 1000 machines you search all million tables in about 2
minutes.
The only problem is the total size of a million tables: 16000GB, so
you need a couple of optical disks here.
Alternatively, use a bit less memory and some more time!
I like to remark that Oscar's overall computational effort is still
proportional to N (the key space); the trick only allows him to do the
work IN ADVANCE and spend only little time after the interception of
Y.
QUESTION. This is a Chosen Plaintext attack, but the value of x is in
no way special. Why didn't I call it a Known Plaintext attack then?
1.5 Double and Triple DES.
------------------------------
The conclusion is clear: even though algorithmically sound, DES stinks
because the key size is simply TOO SMALL. The American solution is:
"OK, if it stinks, let us do it twice and see if the smell disappears!"
Alice and Bob now communicate with a 112b key K = (k1 k2) and use
these 112b as two DES keys: Y = Ek2(Ek1(X)). We call this double-DES
or 2DES.
In general, we can have 56.j bit masterkeys and iterate DES j times
with a different key.
What will happen? First consider iteration of the SHIFT system:
Alice first shifts over k1 positions, then over k2.
QUESTION: What will happen?
THEOREM: The set of m encryption functions Ek used in the SHIFT
system is a group.
Most notably, shifting twice is the same as a single shift by a
different amount and will not make an attack any more difficult.
Alice has m^2 different ways of computing, but computes only m
different functions.
Concerning DES it has been shown in 1992 by Campbell and Wiener that
it is not a group, and with 2^112 different keys we are indeed
expecting about 2^112 different functions.
Considering brute force or even Hellman's cubic root attack, a key
size of 112b would be utterly sufficient for the decennia to come.
All `millions' in the attack become million-squares!
Unfortunately for the 2DES users (there are none BTW), breaking 2DES
does NOT require a computational effort proportional to the key space!
1.5.1 Meet-in-the-Middle attack
This attack shows that repeating any (symmetric) encryption method
does not increase the complexity of a BFA; the method is very general,
it can be applied against other algorithms.
We consider a Known Plaintext Attack, ie, assume that Oscar knows
several X and Y s.t. Y = Ek2(Ek1(X)) (we shall see that Oscar needs
about 3 or 4 64b blocks only). Though the key-space has size 2^112,
Oscar finds the key with a computational effort of only 2^56 !!
Oscar makes a RIGHT and LEFT list, the right with all 2^56 possible
values of k1 and the LEFT with the 2^56 possibilities for k2.
Oscar takes the first pair (X,Y) and ENCRYPTS from X and DECRYPTS from
Y; he computes the N values Ek1(X) for all N k1, and the N values
Dk2(Y) for the N possible k2.
Each list contains circa 2^56 strings of length 64, ie, less than 1/256
of all strings occur in these lists. However, the encryption method
of Alice ENSURES that there exists a single value Z such that
Z = Ek1(X) = Dk2(Y)
for the k1, k2 actually used!!
So Oscar will trim the lists, preserving from RIGHT ONLY the keys k1
for which Ek1(X) appears in LEFT, and from LEFT
ONLY the k2 for which Dk2(Y) appears in RIGHT.
This reduces the size of each list by circa 1/256, so the lists become
2^48 long.
Step 2: Take the second pair and compute Ek1(X') for the remaining k1
and Dk2(Y') for the remaining k2. As each list now only contains 2^48
strings, we expect only a 1/2^16 fraction of the strings in RIGHT to
appear in LEFT also and vice versa, so the lists will be reduced by a
factor of 2^16 and become 2^32 long each!
Step 3 uses the third pair (X",Y") and the lists are reduced to
contain the true key plus a few bastard values that can be eliminated
using the fourth pair.
We emphasize that this attack is NOT practically feasible due to the
enormous amount of storage required. But it feels a bit uncomfortable
that the computational effort for breaking 2DES is not more than the
effort for DES!
1.5.2 3DES triple-DES.
So DES has a bad smell that doesn't disappear if apply it twice...
... we'll have to apply it thrice.
The key K is a 168 bit string (k1,k2,k3) and we apply DES three times
with different keys:
EK(X) = (Ek3(Dk2(Ek1(X)))
DK(Y) = (Dk1(Ek2(Dk3(Y)))
The second encryption is in fact a decryption, this was done to have
backward compatibility with DES: setting k1=k2=k3=k makes EK the same
as Single DES Ek.
A meet in the middle attack is possible, for example by focussing on
the intermediate result after TWO encryptions; but this would require
a precomputation with the 2^112 possible values for k1 and k2.
The bottom line is that 3DES offers a security (2^112 work) that we
had naively expected to achieve with 2DES.
Needless to say, 2DES is NOT used (it offers no significant
improvement over DES) but 3DES is tremendously popular with the
banks.
1.5.3 Design Myths of DES
The NSA has been criticized from the start about having halved the key
size of DES. As we have seen, 56b is just TOO SMALL because it allows
all kinds of smart attacks that somehow view the algorithm as a black
box. Indeed, we have not yet seen any attack that actually looks at
the inside of the algorithm and does something that is better than
these `black box' attacks. This shows that the algorithmical ideas
brought into DES are very strong! It is just a pity that the key size
was defined so small.
NSA was also criticized for their work on the f functions used inside
DES: it was a frantically denied (by NSA) public secret that NSA has
dictated to IBM how f should work, but they refused to reveal the
design criteria. There was a public fear that persisted for about
twenty years:
i) The key size had been chosen this small deliberately so that
NSA (biggest computer owner in the world) would be able to
read all DES communication in the interest of national
security.
ii) The design of the f function contains a dirty trick, only known
to NSA, allowing to crack DES even faster.
1.6 Attacks on DES machinery.
--------------------------------
Actually there exist two attacks that DO use the internal working of
the DES algorithm.
1.6.1 Differential Cryptanalysis.
In 1990, two Israelis Biham and Shamir considered a simplified version
of DES, where only 3 rounds were used INSIDE the algorithm instead of
the actual 16.
They discovered that it is possible to launch a Chosen Plaintext
attack with pairs of plaintext, and using some of these pairs, read
about 48 of the key bits by analysing the output.
Number of Chosen Known PT
Rounds PT Pairs pairs
---------------------------------------------
3 3 2^17
Moreover, it was found out that the attack can be generalized to
encryption with more rounds:
8 2^14 2^44
The cryptography scene got in a frenzy, which gradually sank away when
the complexity of the attack became clear.
12 2^31 2^47
14 2^39 2^51
16 2^47 2^55.1
When this became known, NSA revealed the design secrets of DES.
NSA claimed that DFA was already known inside the NSA walls as early
as 1975 (and before that!).
The f function had been modified by them so as to have the numbers in
the last column grow as fast as possible.
16 is the first number of rounds where the KPA complexity exceeds the
normal brute force attack searching all keys! This explains why 16
was chosen to be the number of rounds.
1.6.2 Differential fault Analysis
Another attack of the `internal' type was discovered in 1996: the idea
here is to have a DES chip (with unknown key) encrypt or decrypt some
string TWICE, but to induce in some way a bit error in one of the
computations, preferrably in the final iterations. By comparing the
two outcomes, information about the key can be retrieved.
Though the Differential Fault Analysis can be shown to be
mathematically sound and quite effective, the practical application is
in the first place limited to situations where the attacker has the
possibility to `torture' the computing machinery a bit, such as a
smart card inserted in Oscar's shop's cardreader.
Second, it remains doubtful whether random single-bit errors can
indeed be induced reliably.
1.7 Conclusions
-------------------
The DES algorithm is called a SYMMETRIC algorithm because the keys
held by Alice and Bob are the same. All `classical' encryption
methods (used in WWII and the cold war) are of the symmetric type and
DES can be seen as the ultimate symmetric algorithm, barring the
reservations concerning its key size. DES has dominated our
perception of symmetric algorithms during the last two decades, and
its hegemony hasn't ended (thanks to the invention of triple DES).
The algorithm is simple and allows extremely fast hardware
implementations: the lastest chip generation achieves Gigabit per
second rate at 300$ cost.
Software implementsations are slower, because DES wasn't optimized for
software implementations.
Around 1990 a new algorithm was proposed, IDEA, that appears to be as
strong as DES, while operation on the data in chunks of 16b rather
than bit-wise, thus facilitating software implementations. IDEA has
128b keys and encrypts in 64b blocks.