Cryptography Evolution and Historical Cipher Systems

Cryptography and Symmetric Key Algorithms AIT 701- Cyber Security: Emerging Threats and Countermeasures Dr. Massimiliano Albanese The content of this series of presentations is adapted from CISSP: Certified Information Systems Security Professional Study Guide , 5thand 6thedition.

Lecture Outline & Objectives Topics Cryptography and Symmetric Key Algorithms (Chapter 9) Historical Milestones in Cryptography Cryptographic Basics Modern Cryptography Symmetric Cryptography Objectives Understanding the goals and applications of cryptography Understanding the basic concepts of encryption, including binary math and other mathematical operations Understanding the difference between symmetric and asymmetric cryptography 2

Cryptography and symmetric key algorithms (Chapter 9) Historical Milestones in Cryptography 3

Caesar Cipher One of the earliest known cipher systems was used by Julius Caesar to communicate with Cicero (see demo) The system is extremely simple To encrypt a message, simply shift each letter of the alphabet three places to the right (the cipher is a.k.a. ROT3 or Rotate 3 cipher) For example, A becomes D, and X becomes A (wrapping around) THE DIE HAS BEEN CAST The Caesar cipher is a mono-alphabetic substitution cipher It is vulnerable to frequency analysis The most common letters in English are E, T, A, N, O, R, I, S, H Attackers seeking to break the cipher simply need to find the most common letters in the encrypted text and experiment with substitutions WKH GLH KDV EHHQ FDVW 4

Discussion Question The following cypher text has been encrypted with a Rotate X cipher: YMJ HNUMJW BFX GWTPJS Can you break it (i.e., find the value of X)? B 1 F 1 G 1 H 1 J 3 M 2 N 1 P 1 S 1 T 1 U 1 W X 2 Y 1 1 5

American Civil War Between the time of Caesar and the early years of the United States, scientists and mathematicians made significant advances beyond the early ciphers used by ancient civilizations During the American Civil War, Union and Confederate troops both used relatively advanced cryptographic systems to secretly communicate along the front lines Each side was tapping into the telegraph lines to spy on the other side These systems used complex combinations of word substitutions and transposition to attempt to defeat enemy decryption efforts 6

Ultra vs. Enigma Prior to World War II, the German military adapted a commercial code machine named Enigma for government use This machine used a series of 3 to 6 rotors to implement an extremely complicated poly-alphabetic substitution cipher The only way to decrypt a message with contemporary technology was to use a similar machine with the same rotor settings of the transmitter The Allied forces began a top-secret effort known by the code name Ultra to attack the Enigma codes Eventually, the Polish military successfully reconstructed an Enigma prototype, and the Allies successfully broke the Enigma code in 1940 According to historians, this success played a significant role in the eventual defeat of the Axis powers 7

Enigma 8

Cryptographic Basics 9

Goals of Cryptography Cryptographic systems are used to meet four fundamental goals Confidentiality (of data at rest and data in motion) Most widely cited goal: facilitating secret communications Enforced by Symmetric and Asymmetric key cryptosystems Integrity Enforced thorough the use of digitally signed message digests/checksums Enforced by both public and private key cryptosystems Authentication Can be achieved using a challenge-response protocol, requiring the knowledge of a shared secret Non-repudiation Can be enforced only by public, or asymmetric, cryptosystems Not all cryptosystems are intended to achieve all four goals 10

Cryptography Concepts (1/2) Plain-text and cypher-text Plain-text message (P) Encryption Cypher-text message (C) Cypher-text message (C) Decryption Plain-text message (P) All cryptographic algorithms rely upon keys (crypto-variables) A key is a number, usually a very large binary number The key space of an algorithm is the range of values that are valid for use as a key for that algorithm A key space is defined by its bit size A 128-bit key can have a value from 0 to 2128 - 1 In private key (or secret key) cryptosystems, all participants use a single shared key In public key cryptosystems, each participant has their own pair of keys 11

Cryptography Concepts (2/2) Cryptography, cryptanalysis, and cryptology Cryptography is the art and science of creating and implementing secret codes and ciphers Cryptanalysis is the study of methods to defeat codes and ciphers Together, cryptography and cryptanalysis are commonly referred to as cryptology Specific implementations of a code or cipher in hardware and software are known as cryptosystems Federal Information Processing Standards -140 (FIPS-140), Security Requirements for Cryptographic Modules Defines the hardware and software requirements for cryptographic modules used by the federal government 12

Kerchoff Principle (or assumption) Most cryptographic algorithms are dictated by the Kerchoff principle (also known as Kerchoff s assumption) algorithms should be known and public, allowing anyone to examine and test them all keys should remain private A large number of cryptographers adhere to this principle Kerchoff s adherents claim that the opposite approach includes the dubious practice of security through obscurity They believe that public exposure produces more activity and exposes more weaknesses more readily, leading to the abandonment of insufficiently strong algorithms and quicker adoption of suitable ones 13

Cryptographic Mathematics Binary mathematics Logical operations (or Boolean operations) AND, OR, NOT, XOR Modulo function One-way functions Confusion & diffusion Nonce Zero knowledge proof Split knowledge Work function 14

Logical Operations (1/2) AND Bitwise AND X Y 0 0 0 1 X 0 0 1 1 Y 0 1 0 1 X: 0 1 1 0 1 1 0 0 Y: 1 0 1 0 0 1 1 1 X Y: 0 0 1 0 0 1 0 0 OR Bitwise OR X Y 0 1 1 1 X 0 0 1 1 Y 0 1 0 1 X: 0 1 1 0 1 1 0 0 Y: 1 0 1 0 0 1 1 1 X Y: 1 1 1 0 1 1 1 1 15

Logical Operations (2/2) NOT Bitwise NOT X 0 1 ~X 1 0 X: 0 1 1 0 1 1 0 0 ~X: 1 0 0 1 0 0 1 1 XOR Bitwise XOR X 0 0 1 1 Y 0 1 0 1 X Y 0 1 1 0 X: 0 1 1 0 1 1 0 0 Y: 1 0 1 0 0 1 1 1 X Y: 1 1 0 0 1 0 1 1 16

Modulo Function The modulo function (or operation) finds the remainder of the division of one number by another Given two positive numbers, a (the dividend) and b (the divisor) a modulo b (abbreviated as a mod b) can be thought of as the remainder of the division of a by b For instance, the expression 10 mod 3 would evaluate to 1 because 10 divided by 3 leaves a remainder of 1, while 9 mod 3 would evaluate to 0 The modulo function is extremely important in the field of cryptography 17

One-Way Functions Mathematical functions that easily compute output values for each possible combination of inputs but make it impossible to retrieve the input values from the output Public key cryptosystems are all based upon some sort of one-way function In practice, however, it has never been proven that any specific known function is truly one-way Cryptographers rely upon functions that they suspect may be one-way For example, consider a function that multiplies 3 prime numbers If input values are restricted to single-digit numbers, it is relatively easy to determine the possible input values by looking at the numerical output 18

Discussion Question Given 30, can you guess the 3 prime numbers used? (2; 3; 5) What about 10,718,488,075,259 ? (17,093; 22,441; 27,943) 19

Confusion and Diffusion Confusion and diffusion are two basic operations that cryptographic algorithms rely upon to obscure plain-text messages Defined by Claude Shannon in his paper Communication Theory of Secrecy Systems , published in 1949 Confusion occurs when the relationship between the plain text and the key is so complicated that an attacker can t merely continue altering the plain text and analyzing the resulting cipher text to determine the key Diffusion occurs when a change in the plain text results in multiple changes spread throughout the cipher text 20

Nonce Cryptography often gains strength by adding randomness to the encryption process A nonce is a random number generator It produces a unique number each time it is used An example of a nonce is an initialization vector (IV) a random bit string that is the same length as the block size and is XORed with the message IVs are used to create unique cipher text every time the same message is encrypted using the same key This makes replay attacks virtually impossible 21

Zero-Knowledge Proof Prove your knowledge of a fact to a third party without revealing the fact itself to that third party Example Peggy knows the password to a secret door located inside a circular cave Victor would like to buy the password from Peggy, but he wants Peggy to prove that she knows the password before paying her for it Peggy doesn t want to tell Victor the password for fear that he won t pay later The zero-knowledge proof can solve their dilemma Magic door illustration 22

Magic Door Illustration Peggy Victor 23

Split Knowledge When the information or privilege required to perform an operation is divided among multiple users, no single person has sufficient privileges to compromise the security of an environment This form of separation of duties is called split knowledge The best example of split knowledge is seen in the concept of key escrow when the security practice of M of N control is enforced M of N control requires that a minimum number of agents (M) out of the total number of agents (N) work together to perform high-security tasks 24

Work Functions The strength of a cryptographic system can be assessed by measuring the effort to break it in terms of cost and/or time using a work function or work factor Usually the work function represents the time and effort required to perform a complete brute-force attack against an encryption system The security and protection offered by a cryptosystem is directly proportional to the value of the work function/factor For cryptography to be cost-efficient, the work function need be only slightly greater than the time value of that asset Bottom line: Spend no more effort to protect an asset than it warrants, but be sure to provide sufficient protection 25

Codes vs. Ciphers Codes are cryptographic systems of symbols that represent words or phrases Sometime they are secret, but they are not necessarily meant to provide confidentiality A common example of a code is the 10 system of communications (or 10-codes) used by law enforcement agencies This code is commonly known by the public, but it does provide for ease of communication 10-23: Arrived at scene Ciphers are always meant to hide the true meaning of a message, using a variety of techniques to alter and/or rearrange the message Ciphers convert messages from plain text to cipher text on a bit basis, character basis, or block basis (a fixed-length segment of a message) 26

Transposition Ciphers Transposition ciphers use an encryption algorithm to rearrange the letters of a plain-text message, forming the cipher- text message The decryption algorithm simply reverses the transposition to retrieve the original message The simplest transposition cipher could reverse the letters of the message E.g., apple encryption elppa Transposition ciphers can be much more complicated than this For example, a keyword can be used to perform a columnar transposition 27

Columnar Transposition We are attempting to encrypt the message The fighters will strike the enemy bases at noon using the secret key attacker Step 1: number the letters of the keyword in alphabetical order Step 2: write the letters of the message in order underneath the letters of the keyword Step 3: form the cypher-text by reading down each column, in the order corresponding to the numbers assigned in Step 1 28

Substitution Ciphers Substitution ciphers use an encryption algorithm to replace each character or bit of the plain-text message with a different one The Caesar cipher (ROT3) is a substitution cipher ROT3 can be expressed in mathematical terms by converting each letter to its decimal equivalent (where A is 0 and Z is 25) The encryption function for the Caesar cipher is C = (P + 3) mod 26 The corresponding decryption function is P = (C - 3) mod 26 As with transposition ciphers, there are many substitution ciphers that are more sophisticated than this Poly-alphabetic substitution ciphers use multiple alphabets in the same message to hinder decryption efforts One of the most notable examples is the Vigenere cipher 29

Vigenere Cipher 1. 2. Write out the plain text Underneath, write out the encryption key, repeating the key as many times as needed to create a line of text that has the same length as the plain text Convert each letter position from plain text to cipher text a. Locate the column in the chart headed by the i-th plain-text character b. Locate the row headed by the i-th key word character c. Write down the letter that appears at the intersection 3. 30

One-Time Pad A one-time pad is an extremely powerful type of substitution cipher It uses a different substitution alphabet for each letter of the plain-text message It can be represented by the following encryption function, where K is the encryption key for the letter represented by C C = (P + K) mod 26 Usually, one-time pads are written as a very long series of numbers When used properly, they are an unbreakable encryption scheme There is no repeating pattern of alphabetic substitution, rendering cryptanalytic efforts useless 31

Running Key Cipher In a running key cipher (a.k.a. a book cipher), the encryption key is as long as the message itself and is often chosen from a common book For example, the sender and recipient might agree in advance to use the text of a given chapter of a book as the key. They would use as many consecutive characters as necessary to perform the encryption and decryption operations add the plain text to the key, and then perform a modulo 26 operation Plain-text Key Numeric plain-text 17 8 2 7 0 17 3 22 8 11 11 . . . . . . Numeric key 22 8 19 7 12 20 2 7 8 13 19 . . . . . . Numeric cipher-text 13 16 21 14 12 11 5 3 16 24 4 Cipher-text N Q V O M L F D Q Y E R I C H A R D W I L L . . . . . . W I T H M U C H I N T . . . . . . . . . . . . . . . . . . 32

Block and Stream Ciphers Block ciphers operate on chunks, or blocks, of a message and apply the encryption algorithm to an entire block at the same time Transposition ciphers are examples of block ciphers The complicated columnar transposition cipher works on an entire message (or a large piece of a message) Most modern encryption algorithms implement some type of block cipher Stream ciphers operate on each character or bit of a message (or data stream) one character/bit at a time The Caesar cipher is an example of a stream cipher The one-time pad is also a stream cipher because the algorithm operates on each letter of the plain-text message independently Stream ciphers can also function as a type of block ciphers A buffer fills up with real-time data that is then encrypted as a block 33

Modern Cryptography 34

Cryptographic Keys Modern cryptosystems do not rely upon the secrecy of their algorithms In fact, the algorithms for most cryptographic systems are widely available for public review and open to public scrutiny Modern cryptosystems rely upon the secrecy of one or more cryptographic keys The length of the key is an extremely important factor in determining the strength of the cryptosystem Longer keys usually provide stronger encryption Several decades ago, when the DES was created, a 56-bit key was considered sufficient to maintain security of data There is now widespread agreement that 56-bit DES keys are no longer secure because of advances in cryptanalysis Modern cryptographic systems use at least a 128-bit key to protect data 35

Symmetric Key Algorithms Symmetric key algorithms rely upon a shared secret encryption key that is distributed to all members who participate in the communications The same key on both ends of the communication is used to both encrypt and decrypt messages When large keys are used, symmetric encryption is very difficult to break Symmetric key cryptography is primarily employed to perform bulk encryption and provides only for confidentiality Also known as secret key cryptography and private key cryptography (not same as a private key in PKI) 36

Discussion Question Why symmetric key cryptography cannot provide authentication? 37

Symmetric Key Cryptography 38

Weaknesses of Symmetric Cryptography Key distribution is a major problem Parties must have a secure method of exchanging the secret key before establishing communications with the symmetric key protocol If a secure electronic channel is not available, an offline key distribution method must often be used (that is, out-of-band exchange) Does not implement nonrepudiation Because any communicating party can encrypt and decrypt messages with the shared secret key, there is no way to prove the origin of a message The algorithm is not scalable Secure private communication between individuals in a large group could be achieved only if each possible combination of users shared a private key Keys must be regenerated often Each time a participant leaves the group, all keys that involved that participant must be discarded 39

Strengths of Symmetric Cryptography The major strength of symmetric key cryptography is the great speed Symmetric keying is very fast Often 1,000 to 10,000 times faster than asymmetric By nature of the mathematics involved, symmetric key cryptography also naturally lends itself to hardware implementations This creates the opportunity for even higher-speed operations 40

Asymmetric Key Algorithms Asymmetric key algorithms, also known as public key algorithms, address the weaknesses of symmetric key encryption Each user has two keys a public key, which is shared with all users a private key, which is kept secret and known only to the user If a message is encrypted with a user s public key, then only the corresponding private key can decrypt it, and vice versa Asymmetric key algorithms also provide support for digital signature technology Example: Bob wants to assure other users that a message with his name on it was actually sent by him He first creates a message digest by using a hashing algorithm He then encrypts that digest using his private key To verify the signature, the recipient decrypts the message digest using Bob s public key and then verifies that the decrypted message digest is accurate 41

Asymmetric Key Cryptography 42

Strengths of Asymmetric Cryptography (1/2) Scalability The addition of new users requires the generation of only one public- private key pair, which is used to communicate with all other users Users can be removed more easily Asymmetric algorithms provide a key revocation mechanism that allows a key to be canceled, effectively removing a user from the system Key regeneration Key regeneration is required only when a user s private key is compromised No other keys are compromised and therefore key regeneration is not required for any other user If a user leaves the community, the system administrator simply needs to invalidate that user s keys 43

Strengths of Asymmetric Cryptography (2/2) Integrity, authentication, and nonrepudiation. If a user does not share their private key with other individuals, a message signed by that user can be shown to be accurate and from a specific source and cannot be repudiated Key distribution is a simple process Users who want to participate in the system simply make their public key available to anyone with whom they want to communicate There is no method by which the private key can be derived from the public key No preexisting communication link needs to exist Asymmetric cryptography does not require a preexisting relationship to provide a secure mechanism for data exchange Two individuals can communicate securely as soon as they start communicating 44

Weaknesses of Asymmetric Cryptography The major weakness of public key cryptography is its slow speed of operation Many applications that require the secure transmission of large amounts of data use public key cryptography to establish a connection and then exchange a symmetric secret key symmetric cryptography for the remainder of the session 45

Number of Symmetric/Asymmetric Keys 46

Comparison Summary 47

Hashing Algorithms A hashing algorithm is a transformation that takes a variable-size input and returns a fixed-size string, which is called the hash value It s extremely difficult, if not impossible, to derive a message from its hash value, and it s very unlikely that two messages will produce the same hash value (demo: http://caligatio.github.io/jsSHA/) Public key cryptosystems can provide digital signature capability when used in conjunction with a message digest Message digests are summaries of a message s content produced by a hashing algorithm Some of the more common hashing algorithms in use today are Message Digest 2 and 5 (MD2 and MD5) Secure Hash Algorithm (SHA-0, SHA-1, and SHA-2) Hashed Message Authentication Code (HMAC) 48

Symmetric Cryptography 49

Data Encryption Standard (DES) The U.S. government published the Data Encryption Standard in 1977 as a proposed standard cryptosystem for all government communications It was superseded by the Advanced Encryption Standard in 2001 DES is a 64-bit block cipher that has five modes of operation Electronic Codebook (ECB), Cipher Block Chaining (CBC), Cipher Feedback (CFB), Output Feedback (OFB), Counter (CTR) All of the DES modes operate on 64 bits of plain text at a time to generate 64-bit blocks of cipher text The key used by DES is 56 bits long DES utilizes a series of XOR operations to generate the cipher text The process is repeated 16 times for each encryption/decryption Each repetition is commonly referred to as a round of encryption 50