GiladTsur YossiOren ShannonSecrecy

Information about GiladTsur YossiOren ShannonSecrecy

Published on January 5, 2008

Author: WoodRock

Source: authorstream.com

Content

Communication Theory of Secrecy Systems :  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:  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:  Shannon – his life and work Claude E. Shannon (1916-2001):  Claude E. Shannon (1916-2001) 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:  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 Cryptography before Shannon:  Cryptography before Shannon From http://www.cqrsoft.com/history/scytale.htm Themes in cryptography:  Themes in cryptography From http://images.encarta.msn.com/xrefmedia/sharemed/targets/images/pho/t025/T025102A.jpg 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. 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:  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. Ancient Ciphers II:  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:  Ancient Ciphers III 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. So what were these ciphers good for? Ancient Ciphers IV:  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:  Ancient Ciphers V 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. http://plus.maths.org/issue34/features/ekert/ Ancient Ciphers VI:  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:  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 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 :  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:  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:  Cryptanalysis of polyalphabetic substitution ciphers The major classic techniques used for this process involve two steps: Discover the length of cycle. 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:  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:  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 Definitions of a Cryptosystem: Shannon’s version II:  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:  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:  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:  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 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 one-time 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:  Review: Bayes’ Theorem Let X and Y be two random variables. Define: Theorem (Chain Rule): Theorem (Bayes): Theoretical (Perfect) Security:  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|:  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):  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):  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):  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):  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:  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 :  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:  Definition of Entropy If X is a random variable taking values from finite alphabet X, then (note: limx!0xlogx=0) Entropy Rate:  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:  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:  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):  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):  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) :  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) :  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:  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:  Product Ciphers and Combined Cryptosystems “Weighted Sum” 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:  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:  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:  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:  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:  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 key-space 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:  Closing Thoughts Effect of this Paper:  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:  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.

Related presentations


Other presentations created by WoodRock

VoIP endfassung
18. 06. 2007
0 views

VoIP endfassung

Lone Wolf Presentation
22. 04. 2008
0 views

Lone Wolf Presentation

Guersenfinal
17. 04. 2008
0 views

Guersenfinal

10 bridge
16. 04. 2008
0 views

10 bridge

Reveiwfinal spring
14. 04. 2008
0 views

Reveiwfinal spring

ch03 edit
13. 04. 2008
0 views

ch03 edit

Howcroft CME
10. 04. 2008
0 views

Howcroft CME

ARPA07distribute
09. 04. 2008
0 views

ARPA07distribute

PowerPoint Presentation 2007
07. 04. 2008
0 views

PowerPoint Presentation 2007

Central Asia short
30. 03. 2008
0 views

Central Asia short

APALSAGeneralMeeting
27. 03. 2008
0 views

APALSAGeneralMeeting

elements compounds mixtures
04. 01. 2008
0 views

elements compounds mixtures

Moodle for english teachers
27. 06. 2007
0 views

Moodle for english teachers

YagerDOE2005
17. 09. 2007
0 views

YagerDOE2005

JESSICA2 HKJU Dec 18 2002
17. 09. 2007
0 views

JESSICA2 HKJU Dec 18 2002

wipo smes del 07 www 76775
24. 09. 2007
0 views

wipo smes del 07 www 76775

LDAP Integration
24. 09. 2007
0 views

LDAP Integration

SAR presentation Final
24. 09. 2007
0 views

SAR presentation Final

Politics ml Z
02. 10. 2007
0 views

Politics ml Z

sparkles
04. 10. 2007
0 views

sparkles

Extreme Makeover
17. 09. 2007
0 views

Extreme Makeover

current status ebxml cppa tc
29. 10. 2007
0 views

current status ebxml cppa tc

ast201 2007 lect11
28. 11. 2007
0 views

ast201 2007 lect11

judicial
28. 08. 2007
0 views

judicial

Laptop Security
28. 08. 2007
0 views

Laptop Security

hammer fatriv
28. 08. 2007
0 views

hammer fatriv

Air Monitoring
23. 10. 2007
0 views

Air Monitoring

CONFINED
07. 11. 2007
0 views

CONFINED

Kansas GRB 5
15. 11. 2007
0 views

Kansas GRB 5

ATS
16. 11. 2007
0 views

ATS

Lecture 4 Bioterrorism Dunne
17. 11. 2007
0 views

Lecture 4 Bioterrorism Dunne

wieser sybase
20. 11. 2007
0 views

wieser sybase

rushdie
21. 11. 2007
0 views

rushdie

Napoleon I
26. 11. 2007
0 views

Napoleon I

SonnetOL
11. 08. 2007
0 views

SonnetOL

Steve Lafferty optimized
11. 08. 2007
0 views

Steve Lafferty optimized

Tibetian test 2
11. 08. 2007
0 views

Tibetian test 2

Plumbing an Information Space
02. 01. 2008
0 views

Plumbing an Information Space

Tree of Life 3 11 03
11. 08. 2007
0 views

Tree of Life 3 11 03

savas dangerous offenders
11. 08. 2007
0 views

savas dangerous offenders

Memory Revisited
12. 10. 2007
0 views

Memory Revisited

Dermatology Revision
05. 01. 2008
0 views

Dermatology Revision

FROM THE DISCOVERY OF HELIX
16. 10. 2007
0 views

FROM THE DISCOVERY OF HELIX

504d AACR poster 2005 cfg
30. 10. 2007
0 views

504d AACR poster 2005 cfg

Zeeberg
17. 09. 2007
0 views

Zeeberg

sweep
11. 08. 2007
0 views

sweep

Industrialization Ideology
26. 10. 2007
0 views

Industrialization Ideology

CS438 08 Bridges
28. 12. 2007
0 views

CS438 08 Bridges

sa advocacy
24. 09. 2007
0 views

sa advocacy

CausalArguments
26. 11. 2007
0 views

CausalArguments

JostDeutschAwards
07. 01. 2008
0 views

JostDeutschAwards

Class24ImlicatureExp
19. 02. 2008
0 views

Class24ImlicatureExp

Lars Nord Presentation at HA2005
08. 10. 2007
0 views

Lars Nord Presentation at HA2005

ConEvals
27. 02. 2008
0 views

ConEvals

moodle themes
27. 06. 2007
0 views

moodle themes

Moodle lokalp
27. 06. 2007
0 views

Moodle lokalp

Moodle na UE final
27. 06. 2007
0 views

Moodle na UE final

SIRESENAC06
06. 03. 2008
0 views

SIRESENAC06

Seance 4 Alissa fr
24. 10. 2007
0 views

Seance 4 Alissa fr

SKita gesture
11. 08. 2007
0 views

SKita gesture

8 lessons learnt from nms
18. 03. 2008
0 views

8 lessons learnt from nms

WORKING IN THE EU INSTITUTIONS
20. 03. 2008
0 views

WORKING IN THE EU INSTITUTIONS

semantic web applications
25. 03. 2008
0 views

semantic web applications

FutureofNews
05. 10. 2007
0 views

FutureofNews

sxu 1 05 06
11. 08. 2007
0 views

sxu 1 05 06

canarias
23. 10. 2007
0 views

canarias

Reintegration ProgramFinal
28. 12. 2007
0 views

Reintegration ProgramFinal

G Abaee
22. 11. 2007
0 views

G Abaee

tromsoe
11. 08. 2007
0 views

tromsoe

glazerbusan
12. 10. 2007
0 views

glazerbusan

Stockholm Tutorial June 2001
12. 03. 2008
0 views

Stockholm Tutorial June 2001

TF Rschede
18. 06. 2007
0 views

TF Rschede

telwisa 5
18. 06. 2007
0 views

telwisa 5

Teitler Framework
18. 06. 2007
0 views

Teitler Framework

STRUMENTI tris DI ATTUAZIONE
18. 06. 2007
0 views

STRUMENTI tris DI ATTUAZIONE

strategic plan
18. 06. 2007
0 views

strategic plan

STEROIDS
18. 06. 2007
0 views

STEROIDS

Slide musso taranto
18. 06. 2007
0 views

Slide musso taranto

V 005 Gierke
18. 06. 2007
0 views

V 005 Gierke

Vorlesung BGB AT 1
18. 06. 2007
0 views

Vorlesung BGB AT 1

violenza
18. 06. 2007
0 views

violenza

Varma
18. 06. 2007
0 views

Varma

usenix
18. 06. 2007
0 views

usenix

unter Mitglieder wenn das geht
18. 06. 2007
0 views

unter Mitglieder wenn das geht

Unterrichtsbeobachtu ng
18. 06. 2007
0 views

Unterrichtsbeobachtu ng

Traechtigkeit
18. 06. 2007
0 views

Traechtigkeit

todoslossantosanual
02. 11. 2007
0 views

todoslossantosanual

vortrag we mu 220602
18. 06. 2007
0 views

vortrag we mu 220602

SOR Legal Updates 2006 141962 7
11. 08. 2007
0 views

SOR Legal Updates 2006 141962 7

Bigwood 1
13. 03. 2008
0 views

Bigwood 1

lrec metadata
14. 11. 2007
0 views

lrec metadata

termininfo D2D Konferenz2006
18. 06. 2007
0 views

termininfo D2D Konferenz2006

3320 l09
17. 09. 2007
0 views

3320 l09

typologie
18. 06. 2007
0 views

typologie

antalya
03. 09. 2007
0 views

antalya

sermonpp thy will be done
11. 08. 2007
0 views

sermonpp thy will be done

gabriel
24. 09. 2007
0 views

gabriel

tack2
24. 09. 2007
0 views

tack2

VORTRAG BW
18. 06. 2007
0 views

VORTRAG BW

The Perils of Childhood Obesity
11. 08. 2007
0 views

The Perils of Childhood Obesity

GT TurkeyCountryPresent ation
23. 10. 2007
0 views

GT TurkeyCountryPresent ation

Open Everything 3 9
01. 10. 2007
0 views

Open Everything 3 9

arnaud
28. 09. 2007
0 views

arnaud

file1180026507
22. 10. 2007
0 views

file1180026507

yasinsky
24. 09. 2007
0 views

yasinsky

healthy body esteem
03. 10. 2007
0 views

healthy body esteem

moodle presentation epfl final
27. 06. 2007
0 views

moodle presentation epfl final

37 Yale SA Program Overview 07
24. 09. 2007
0 views

37 Yale SA Program Overview 07

song slides
11. 08. 2007
0 views

song slides

Stuttgart
18. 06. 2007
0 views

Stuttgart

site wsa
29. 02. 2008
0 views

site wsa

pearson
24. 09. 2007
0 views

pearson

09 s4 fr
11. 03. 2008
0 views

09 s4 fr

EPS
17. 10. 2007
0 views

EPS

OARS CRJ 2006
24. 09. 2007
0 views

OARS CRJ 2006

7Paul Hopkin
11. 12. 2007
0 views

7Paul Hopkin

Sofia 29 09 30 02
23. 11. 2007
0 views

Sofia 29 09 30 02

CSI NetSec2004
29. 10. 2007
0 views

CSI NetSec2004

santTOPch11
11. 08. 2007
0 views

santTOPch11

HumanCapitalFINAL
24. 09. 2007
0 views

HumanCapitalFINAL

Carmelo Polino
22. 10. 2007
0 views

Carmelo Polino

Poeplau ECLOUD07
03. 01. 2008
0 views

Poeplau ECLOUD07

peytonap
17. 09. 2007
0 views

peytonap

BUTE 2005feb Milano COST291
16. 10. 2007
0 views

BUTE 2005feb Milano COST291