Lecture 2 Perfect Ciphers in Theory not Practice Shannon was the person who saw that the binary digit was the fundamental element in all of communication That was really his discovery and from it the whole communications revolution has sprung R G Gallager I just wondered how things were put together Claude Shannon CS588 Cryptology University of Virginia Computer Science Claude Shannon 1916 2001 David Evans http www cs virginia edu evans Menu Survey Results Perfect Ciphers Entropy and Unicity 25 January 2005 University of Virginia CS 588 2 Survey Responses Majors Cognitive Science Computer Science 13 Computer Engineering 2 Economics Math Year Third year 6 Fourth Year 10 Grad 1 2005 1 Midterm March 3 12 March 15 3 March 17 2 March 22 1 Broken in No 13 Yes 5 Full answers are on the course web site 25 January 2005 University of Virginia CS 588 3 What was the coolest thing you learned last semester i ve been sitting here for like five minutes trying to think of something perhaps that aristotle or perhaps plato hates bands that sell out hmm I learned there was a huge molasses explosion at the Boston harbor in the early 20th century not really all that cool i guess because a lot of people died but still pretty interesting 25 January 2005 University of Virginia CS 588 4 Break In Story In high school the administrators installed a fairly restrictive rights control program called FoolProof It was so restrictive however that my AP Comp Sci class was unable to compile and run programs on the main HD forcing us to use a floppy disk for our source and intermediate files which was painfully slow as projects increased in size Having unsuccessfully lobbied to have restrictions lifted so we could compile and run programs on a temporary directory I tried to convince them that there were more eloquent and flexible security programs out there So I did a little research on the version of FoolProof being used It turns out that this version of FoolProof had two major security flaws 25 January 2005 University of Virginia CS 588 5 Break In Story 1 A backdoor password used by tech support that is hardcoded into the executable and 2 The password information is stored in plaintext within main memory some number of bytes into one of its main data structures which was marked by an ascii string which was some sort of constant containing the version information So I acquired a utility which would allow me to browse and search the contents of physical memory determined what this ascii string would be for the given version of FoolProof and searched memory Sure enough I came up with a match and about 8 bytes later a plaintext ascii string WhatAFool 25 January 2005 University of Virginia CS 588 6 Polling Protocol 25 January 2005 University of Virginia CS 588 7 Last Time Big keyspace is not necessarily a strong cipher Claim One Time Pad is perfect cipher In theory depends on perfectly random key secure key distribution no reuse In practice usually ineffective VENONA Lorenz Machine Today what does is mean to be a perfect cipher 25 January 2005 University of Virginia CS 588 8 Ways to Convince I tried really hard to break my cipher but couldn t I m a genius so I m sure no one else can break it either Lots of really smart people tried to break it and couldn t Mathematical arguments key size dangerous statistical properties of ciphertext depends on some provably or believed hard problem Invulnerability to known cryptanalysis techniques but what about undiscovered techniques Show that ciphertext could match multiple reasonable plaintexts without knowing key Simple monoalphabetic secure for about 10 letters of English XBCF CF FWPHGW This is secure Spat at troner 25 January 2005 University of Virginia CS 588 9 Claude Shannon Master s Thesis 1938 boolean algebra in electronic circuits Mathematical Theory of Communication 1948 established information theory Communication Theory of Secrecy Systems 1945 1949 linked from notes Invented rocket powered Frisbee could juggle four balls while riding unicycle 25 January 2005 University of Virginia CS 588 10 Entropy Amount of information in a message n H M Prob Mi log 1 Prob Mi i 1 over all possible messages Mi 25 January 2005 University of Virginia CS 588 11 Entropy If there are nn equally probable messages H M 1 n log n i 1 n 1 n log n log n Base of log is alphabet size so for binary H M log2 n where n is the number of possible meanings 25 January 2005 University of Virginia CS 588 12 Entropy Example M months of the year H M log2 12 3 6 need 4 bits to encode a year 25 January 2005 University of Virginia CS 588 13 Rate Absolute rate how much information can be encoded R log2 Z REnglish Z size of alphabet log2 26 4 7 bits letter Actual rate of a language r H M N M is a source of N letter messages r of months spelled out using 8 bit ASCII log2 12 8 letters 8 bits letter 0 06 25 January 2005 University of Virginia CS 588 14 Rate of English r English is about 28 letters letter 1 3 bits letter Book uses 1 5 How can one estimate this How many meaningful 20 letter messages in English r H M N 28 H M 20 H M 5 6 log26 n n 265 6 83 million of 2 1028 possible Probability that 20 letters are sensible English is About 1 in 2 1020 25 January 2005 University of Virginia CS 588 15 Redundancy Redundancy D is defined D R r Redundancy in English D 1 28 72 letters letter D 4 7 1 3 3 4 bits letter Each letter is 1 3 bits of content and 3 4 bits of redundancy 72 7 bit ASCII as in PS1 problem 5 D 7 1 3 5 7 81 redundancy 19 information 25 January 2005 University of Virginia CS 588 16 Unicity Distance Entropy of cryptosystem K number of possible keys H K logAlphabet Size K if all keys equally likely H 64 bit key log2 264 64 Unicity distance is defined as U H K D Expected minimum amount of ciphertext needed for brute force attack to succeed 25 January 2005 University of Virginia CS 588 17 Unicity Examples Monoalphabetic Substitution H K log2 26 87 D 3 4 redundancy in English U H K D 25 5 Intuition if you have 25 letters probably only matches one possible plaintext D 0 random bit stream U H K D infinite 25 January 2005 University of Virginia CS 588 18 Unicity Distance Probabilistic measure of how much ciphertext is needed to determine a unique plaintext Does not indicate how much ciphertext is needed for cryptanalysis If you have less than unicity distance ciphertext can t tell if guess is right As redundancy approaches 0 hard to cryptanalyze even simple cipher 25 January 2005 University of Virginia CS 588 19