Transcript מצגת של PowerPoint - The Faculty of Mathematics and Computer

Communication Theory of
Secrecy Systems
On a paper by Shannon
(and the industry it didn’t
spawn)
Gilad Tsur
Yossi Oren
December 2005
What you’ll see today
Shannon – his life and work
 Cryptography before Shannon
 Definition of a cryptosystem
 Theoretical and practical security
 Product ciphers and combined
cryptosystems
 Closing thoughts

Shannon – his life and work
Claude E. Shannon (1916-2001)
Claude E. Shannon (1916-2001)

Important facts:
M. Sc. Thesis founded an industry
 Ph. D. finished in 1.5 years
 Married a computer in 1949
 Wrote scientific papers on a variety of topics,
including juggling

Shannon’s Information Theory Paper
“Mathematical Theory of Communication”,
published in 1948
 Main claim:

All sources of data have a rate
 All channels have a capacity
 If the capacity is greater than the rate,
transmission with no errors is possible


Introduced concept of entropy of a random
variable/process
From http://www.cqrsoft.com/history/scytale.htm
Cryptography before Shannon
Themes in cryptography
• Seals were used as authentication means
for signing contracts, for royal decrees
and for other documents.
• Passwords were used by military and
other organizations to identify members.
From
http://images.encarta.msn.com/xrefme
dia/sharemed/targets/images/pho/t025/
T025102A.jpg
• Codes are semantic while ciphers are
syntactic.
• All these methods (in the case of seals,
as rubber stamps) are also in use today.
Ancient Ciphers I
‫א ב ג ד ה ו ז ח ט י כ ל מ נ ס ע פ צ ק רש ת‬
‫תש ר ק צ פ ע ס נ מ ל כ י ט ח ז ו ה ד ג ב א‬
• Atbash cipher used in old testament “‫“בבל = ששך‬
• Of course, anyone who’d ever heard of this cipher could
easily crack it.
• This is also true for another famous cipher, the Caesar
cipher.
A BC
D E F
…
…
X Y Z
A B C
Ancient Ciphers II
• The Caesar cipher is just a specific case of what are
generally known as Shift Ciphers.
• A Shift cipher is one where the code is simply a
rotation of the alphabet with K steps, where the
number K can be considered the key. Easier for us in
CS – think of it as a constant added modulo the size
of the alphabet.
• Obviously, finding the key for such a code is not a
lengthy process.
Ancient Ciphers III
So what were these ciphers good for?
• Text took an active effort to understand (This was
used with ROT-13 on Usenet).
• Probably the real reason – security through
obscurity.
• The concept of cryptography was not that well
known, and codes such as Atbash were simply
assumed not to be known by people you didn’t want
reading them.
Ancient Ciphers IV
• Both Atbash and Shift ciphers are specific cases of
a more general type of ciphers used in the ancient
world: Monoalphabetic Substitution Ciphers.
• As these ciphers were used by people who wanted
to remember them, keyword and keyphrase ciphers
were often used.
• The keyword could be changed daily to make it
harder to decrypt.
• Some of these ciphers didn’t use a 1-1
correspondence, trusting the redundancy of language
or allowing multiple representations.
Ancient Ciphers V
http://plus.maths.org/issue34/features/ekert/
• Not all ancient ciphers used
substitution methods.
• The earliest known
cryptographic device (to the
best of our knowledge) is the
Spartan scytale.
• Using this device the letters
of the message weren’t
changed, but their order was.
Ancient Ciphers VI
• The scytale was a device assisting in the creation of
a Transposition Cipher.
• Perhaps the most notable example of a
transposition cipher is the column transposition.
• Other geometrical transposition ciphers abound,
mostly route ciphers.
• Transposition ciphers based on a local permutation
are also common, but offer a less apparently
convenient way of writing quickly.
Ancient Ciphers VII
• We have written records of frequency analysis
dating to the 9th century.
From http://en.wikipedia.org/wiki/Caesar_cipher
http://plus.maths.org/issue34/features/ekert/
• Using multiple options to substitute frequent
letters could make frequency analysis much harder.
Cryptography during the dark
ages (‘till around 14th century)
• Cryptography didn’t advance in Europe much during the
dark ages.
• Some religious and mystical sects used cryptographic
techniques to encode their writings, often substitution
ciphers to an arcane alphabet.
• However, the church considered most people using
cryptography as heretics, sorcerers or witches, and was in
the habit of burning them.
• Coupled with low levels of literacy, cryptography was
only studied outside of Europe.
• While texts (such as the cryptanalytic one mentioned
above) appeared, we are unaware of major advances.
Codes and ciphers in the
renaissance
• In Italy, and later all over Europe,
cryptography returns to fashion.
• Different city-states and countries
begin to employ professional
cryptanalysts for encoding and
decoding mail.
• The most common codes are
Polyalphabetic Substitution
Ciphers.
• Many devices are made to aid
encryption and decryption.
Polyalphabetic substitution
ciphers
• These ciphers can simply be considered as a list of
shift ciphers or monoalphabetic substitution ciphers to
be used consecutively.
• The use of some of these ciphers was aided by a
cipher disk.
• Other such ciphers used tables to assist encryption and
decryption.
• Notably, some in of these cipher were polygraphic –
each encoded symbol represented a combination of
plaintext symbols.
Cryptanalysis of polyalphabetic
substitution ciphers
•
The major classic techniques used for this process
involve two steps:
1. Discover the length of cycle.
2. Use monoalphabetic cryptanalysis techniques for
each alphabet (+ information gained from
previous alphabets).
• Step 1 can be done systematically (Brute force
approach) but this may be a very hard process.
• A shortcut that often helps (and is published in the
19th century, ‘though probably known before) is
finding repeating sequences in the text.
Cryptography in the 19th and 20th
Centauries I
• WWI sees the full use of
cryptography in the battle field.
• Advances in radio and telegraph
allow military units to communicate
better than ever before. This means
easy to use, generic ciphers are
required. Mechanized cipher
machines offer this option.
Cryptography in the 19th and 20th
Centauries II
• WWII is famous for being a
scientific war in general, and for
cryptography in particular.
• German Enigma cracked by
British, Japanese “Purple” by the
US.
• Enigma, in fact, a polyalphabetic
cipher system with around 20,000
alphabets.
Definitions of a Cryptosystem
Definitions of a Cryptosystem:
Shannon’s version II
• A cryptosystem can be viewed as a distribution of possible
plaintexts (P), a set of possible ciphertexts (C),
a distribution of possible keys (K) and an encoding transformation
(E) With its inverse (D).
Definitions of a Cryptosystem:
modern variations
• Many things have changed in our thinking about
cryptography.
• Different functions: Not only trying to transmit secret
information.
• Different settings for “Alice” and “Bob” – we now
have public key cryptosystems and extensive use of
randomness.
• Different settings for “Eve” – we now have a variety of
attacks such as known plain text, chosen ciphertext,
chosen plain text and side channel attacks.
Shannon’s 1948 Paper
Published one year after his monumental
“information theory” paper
 Inspired by Von-Neumann’s paper on game
theory
 “transformed cryptography from art to
science”

Main Contributions




Notions of theoretical security and practical
security
Observation that the secret is all in the key, not in
the algorithm – “the enemy knows the system”
(also attributed to Auguste Kerckhoffs)
Product ciphers and mixing transformations –
inspiration for LUCIFER and later DES
Proof that Vernam’s cipher (one-time pad) was
theoretically secure
Theoretical Security and
Practical Security
Theoretical Security and Practical
Security



Theoretically secure cryptosystems cannot be
broken – even by an all-powerful adversary
Practically secure cryptosystems “require a large
amount of work to solve”
Bad news:



The only theoretically secure cryptosystem is the onetime pad
The only practically secure cryptosystem is… the
one-time pad
We do have some cryptosystems which are provably
[as] secure as a difficult problem
Review: Bayes’ Theorem

Let X and Y be two random variables.
Define:

Theorem (Chain Rule):

Apriori
Theorem (Bayes):
Aposteriori
Theoretical (Perfect) Security
What does it mean for a cryptosystem to be
perfectly secure?
 Essentially, the adversary doesn’t learn
anything from the ciphertext:

Perfect Security means |K|¸|P|
Reminder: adversary “knows the system”
and has unlimited power
 If key-space is finite, each ciphertext must
map to a finite number of plaintexts
 If |P|>|K|, some plaintexts will be

“impossible” for some ciphertexts
The Vernam Cipher (1)


Is there a perfectly secure cryptosystem
for which |K|=|P|?
Theorem (Shannon): Let (P,K,C,E,D) be a
cryptosystem for which |K|=|P|=|C|. Then the
cryptosystem provides perfect secrecy iff:
The Vernam Cipher (2)



Proof: Let (P,K,C,E,D) be a cryptosystem
for which |K|=|P|=|C|.
Because of perfect secrecy:
|K|=|P|=|C|, so there is a unique key associated
with every pair (p,c)
The Vernam Cipher (3)


Fix c. For all possible plaintexts pi, let ki be the
key satisfying eki(pi)=c
By Bayes:
The Vernam Cipher (4)
Cipher was invented by Gilbert Vernam of
Bell Labs in 1919
 Idea – key is a long random sequence,
C=P©K
 By above proof, cipher is unbreakable
 Disadvantage – key is huge and cannot be
used twice
 Advantage – algorithm is so simple we can
give it to the Soviets…

Towards real-world cryptography


How secure are cryptosystems with a smaller key
space?
Rules of the game:

Symmetric (deterministic) encryption

|P|=|C|, all keys chosen equiprobably



Ciphertext-only attack
Adversary wishes to recover the key
Question: How fast does the set of possible keys
shrink as the amount of ciphertext grows?
A Brief Introduction to
Information Theory
Some random events are more
unexpected than others
 Some facts are more significant than
others
 Shannon Entropy measures the amount
of uncertainty regarding a random
variable, or the amount of information an
event provides
 Entropy Rate measures the growth of
information in an infinitely-long sequence

Definition of Entropy

If X is a random variable taking values
from finite alphabet X, then
(note: limx!0xlogx=0)
Entropy Rate

If L is a language formed of a sequence of
identically distributed (possibly dependent)
variables, then

The redundancy of a language is defined
as:
Basic Properties of Entropy

H(X)¸0, with equality iff X is constant

H(X)·log2|X|, with equality iff p(x=X)=1/|X|
8 x2X
H(X,Y)·H(X)+H(Y), with equality iff X
and Y are independently distributed
 H(X|Y)·H(X) , with equality iff X and Y
are independently distributed
 Chain Rule:H(X,Y)=H(X|Y)+H(Y)

Entropy of Cryptosystem
Components
Reminder – Cryptosystem = (P,K,C,E,D)
 H(C|K) =H(P)
 H(C|P,K)=H(P|C,K)=0
 H(P,K)=H(P)+H(K)
 H(C)¸H(P)
 H(C,P,K)=H(C,K)=H(P,K)
 H(K|C)=H(K)+H(P)-H(C)
 H(K|Cn)=H(K)+H(Pn)-H(Cn)

Example: A strong cipher which is
very weak (1)



Everything Haley
says is encrypted
with a
monoalphabetic
substitution cipher
Could you break
it?
Q: Which 2
romantic era
authors had their
heroes break this
cipher?
(archive.org cache)
A strong cipher which is very weak (2)
Observation: There are 26!¼1026 possible
substitution ciphers over the lowercase
English alphabet
 This is equivalent to 88-bit security – so
why was it so easy to break?
 Shannon: Any monoalphabetic cipher over
the English language is easily broken,
given a sequence of 25 letters of unknown
ciphertext

Unicity distance of a language (1)

By definition of the entropy rate:

Since |P|=|C|, we have:

Substituting into the formula for H(K|Cn):
Unicity distance of a language (2)


The cryptosystem is broken when
H(K|Cn)=0:
Plug in English (|P|=26, RL¼0.75) and the
substitution cipher (log2|K|¼ 88) and we get
n0¼25 (woops).
Tricks to raise the unicity distance
The idea – raise the entropy of the
language without disturbing content
 Adding random nulls – “hello” becomes
“h;e;;l;lo;;”
 Replace characters with homophonic sets
– “hello” becomes “hello”
 Compress the data

Good compression – good for encryption
 Good encryption – bad for compression

Product Ciphers and
Combined Cryptosystems
“Weighted Sum” Cryptosystems
Different cryptosystems can be combined
to create a new cryptosystem.
 Given two cryptosystems with the same
message space, consider a probabilistic
combination of the two systems: with
probability p use system A, otherwise use
system B.

Endomorphic cryptosystems and
product ciphers



Another way to use two cryptosystems is to
encrypt and decrypt messages consecutively. We
call this a product cipher.
An endomorphic cryptosystem is a system
where the message space is transformed to itself.
With such a system we can even create a product
of the system with itself.
The set of endomorphic cryptosystems with the
aforementioned operations almost create a linear
associative algebra.
Idempotent and commutative
cryptosystems
A cryptosystem S is called
idempotent if S2 = S.
 Combining two idempotent secrecy
systems that commute will create
another idempotent secrecy system –
isn’t of any use.

Designing cryptosystems that are
hard to attack I
Shannon recognizes that aside of brute
force attacks, reasonable attacks attempt to
find keys according to their probability,
hopefully reducing the probability of many
of them near 0 without actually testing each
and every one.
 To do this one needs to create statistics of
the ciphertext.

Designing cryptosystems that are
hard to attack II

Statistics must be:
Simple to measure
 Depend more on the key (if we’re trying to
find the key) than the message
 Useful – divide the key-space into areas of
similar probability and eliminate most
 Usable – the separation of the key-space must
be natural

Confusion and Diffusion

To make finding such statistics harder (without an
ideal system) Shannon suggests:



Diffusion: Spreading the information in such a way
that it is hard to get exact results.
Confusion: Make the natural separation of the keyspace hard to use. (Make all parameters of key
dependant in natural decryption).
He believes that a combination of an initial
transposition with alternating substitutions and
linear operations may do the trick.
Closing Thoughts
Effect of this Paper




Paper did not bring forth an explosion similar to
the 1947 paper
“The problem of good cipher design is essentially
one of finding difficult problems”
This type of problem was made very public with
the creation of DES.
Both DES and AES use Shannon’s ideas of
combining confusion and diffusion (although
other ideas that he hadn’t mentioned appear in
both).
Some closing thoughts




Cryptography is always in the context of
communication between agents.
Not only what messages are transmitted but from
whom to whom is important. We can hardly hide
the size of messages.
One can encrypt messages in ways that allow
breaking them, to misinform.
In huge information environments one could
easily(?) conceal the existence of messages and
the identities of the sender and the receiver.