Cryptography and Network Security PDF

CS3009 – Cryptography and Network Security Week 9-11 MESSAGE INTEGRITY The cryptography systems that we have studied so far provide secrecy, or confidentiality, but not integrity. However, there are occasions where we may not even need secrecy but instead must have integrity.  Document and F...

CS3009 – Cryptography and Network Security Week 9-11 MESSAGE INTEGRITY The cryptography systems that we have studied so far provide secrecy, or confidentiality, but not integrity. However, there are occasions where we may not even need secrecy but instead must have integrity.  Document and Fingerprint One way to preserve the integrity of a document is through the use of a fingerprint. If Alice needs to be sure that the contents of her document will not be changed, she can put her fingerprint at the bottom of the document.  Message and Message Digest The electronic equivalent of the document and fingerprint pair is the message and digest pair. Message and digest  Difference The two pairs (document / fingerprint) and (message / message digest) are similar, with some differences. The document and fingerprint are physically linked together. The message and message digest can be unlinked separately, and, most importantly, the message digest needs to be safe from change. Note The message digest needs to be safe from change. Checking Integrity Checking integrity  Cryptographic Hash Function Criteria A cryptographic hash function must satisfy three criteria: preimage resistance, second preimage resistance, and collision resistance. Criteria of a cryptographic hash function Preimage Resistance Preimage  Example 11.1 Can we use a conventional lossless compression method such as StuffIt as a cryptographic hash function? Solution We cannot. A lossless compression method creates a compressed message that is reversible. Example 11.2 Can we use a checksum function as a cryptographic hash function? Solution We cannot. A checksum function is not preimage resistant, Eve may find several messages whose checksum matches the given one. Second Preimage Resistance Second preimage Collision Resistance Collision RANDOM ORACLE MODEL The Random Oracle Model, which was introduced in 1993 by Bellare and Rogaway, is an ideal mathematical model for a hash function.  Example 11.3 Assume an oracle with a table and a fair coin. The table has two columns. a. The message AB1234CD8765BDAD is given for digest calculation. The oracle checks its table.  Example 11.3 b. The message 4523AB1352CDEF45126 is given for digest calculation. The oracle checks its table and finds that there is a digest for this message in the table (first row). The oracle simply gives the corresponding digest (13AB).  Example 11.4 The oracle in Example 11.3 cannot use a formula or algorithm to create the digest for a message. For example, imagine the oracle uses the formula h(M) = M mod n. Now suppose that the oracle has already given h(M1) and h(M2). If a new message is presented as M3 = M1 + M2, the oracle does not have to calculate the h(M3). The new digest is just [h(M1) + h(M2)] mod n since This violates the third requirement that each digest must be randomly chosen based on the message given to the oracle.  Pigeonhole Principle If n pigeonholes are occupied by n + 1 pigeons, then at least one pigeonhole is occupied by two pigeons. The generalized version of the pigeonhole principle is that if n pigeonholes are occupied by kn + 1 pigeons, then at least one pigeonhole is occupied by k + 1 pigeons.  Example 11.5 Assume that the messages in a hash function are 6 bits long and the digests are only 4 bits long. Then the possible number of digests (pigeonholes) is 24 = 16, and the possible number of messages (pigeons) is 26 = 64. This means n = 16 and kn + 1 = 64, so k is larger than 3. The conclusion is that at least one digest corresponds to four (k + 1) messages.  Attacks on Random Oracle Model Preimage Attack  Example 11.6 A cryptographic hash function uses a digest of 64 bits. How many digests does Eve need to create to find the original message with the probability more than 0.5? Solution The number of digests to be created is k ≈ 0.69 × 2n ≈ 0.69 × 264. This is a large number. Even if Eve can create 230 (almost one billion) messages per second, it takes 0.69 × 234 seconds or more than 500 years. This means that a message digest of size 64 bits is secure with respect to preimage attack, but, as we will see shortly, is not secured to collision attack. Second Preimage Attack. Collision Attack  Example 11.7 A cryptographic hash function uses a digest of 64 bits. How many digests does Eve need to create to find two messages with the same digest with the probability more than 0.5? Solution The number of digests to be created is k ≈ 1.18 × 2n/2 ≈ 1.18 × 232. If Eve can test 220 (almost one million) messages per second, it takes 1.18 × 212 seconds, or less than two hours. This means that a message digest of size 64 bits is not secure against the collision attack. Alternate Collision Attack Summary of Attacks Table 11.4 shows the level of difficulty for each attack if the digest is n bits.  Example 11.8 Originally hash functions with a 64-bit digest were believed to be immune to collision attacks. But with the increase in the processing speed, today everyone agrees that these hash functions are no longer secure. Eve needs only 264/2 = 232 tests to launch an attack with probability 1/2 or more. Assume she can perform 220 (one million) tests per second. She can launch an attack in 232/220 = 212 seconds (almost an hour).  Example 11.9 MD5 which was one of the standard hash functions for a long time, creates digests of 128 bits. To launch a collision attack, the adversary needs to test 264 (2128/2) tests in the collision algorithm. Even if the adversary can perform 230 (more than one billion) tests in a second, it takes 234 seconds (more than 500 years) to launch an attack. This type of attack is based on the Random Oracle Model. It has been proved that MD5 can be attacked on less than 264 tests because of the structure of the algorithm.  Example 11.10 SHA-1, a standard hash function developed by NIST, creates digests of 160 bits. The function is attacks. To launch a collision attack, the adversary needs to test 2160/2 = 280 tests in the collision algorithm. Even if the adversary can perform 230 (more than one billion) tests in a second, it takes 250 seconds (more than ten thousand years) to launch an attack. However, researchers have discovered some features of the function that allow it to be attacked in less time than calculated above.  Example 11.11 The new hash function, that is likely to become NIST standard, is SHA-512, which has a 512-bit digest. This function is definitely resistant to collision attacks based on the Random Oracle Model. It needs 2512/2 = 2256 tests to find a collision with the probability of 1/2. MESSAGE AUTHENTICATION A message digest does not authenticate the sender of the message. To provide message authentication, Alice needs to provide proof that it is Alice sending the message and not an impostor. The digest created by a cryptographic hash function is normally called a modification detection code (MDC). What we need for message authentication is a message authentication code (MAC).  Modification Detection Code (MDC) A modification detection code (MDC) is a message digest that can prove the integrity of the message: that message has not been changed. If Alice needs to send a message to Bob and be sure that the message will not change during transmission, Alice can create a message digest, MDC, and send both the message and the MDC to Bob. Bob can create a new MDC from the message and compare the received MDC and the new MDC. If they are the same, the message has not been changed. Modification detection code (MDC) Message Authentication Code (MAC) Message authentication code Note The security of a MAC depends on the security of the underlying hash algorithm. Nested MAC Nested MAC  Message Authentication message authentication is concerned with: ⚫ protecting the integrity of a message ⚫ validating identity of originator ⚫ non-repudiation of origin (dispute resolution) will consider the security requirements then three alternative functions used: ⚫ hash function ⚫ message encryption ⚫ message authentication code (MAC) Message Security Requirements disclosure traffic analysis masquerade content modification sequence modification timing modification source repudiation destination repudiation Symmetric Message Encryption encryption can also provide authentication if symmetric encryption is used then: ⚫ receiver know sender must have created it ⚫ since only sender and receiver know key used ⚫ know content cannot have been altered... ⚫... if message has suitable structure, redundancy or a suitable checksum to detect any changes Public-Key Message Encryption if public-key encryption is used: ⚫ encryption provides no confidence of sender since anyone potentially knows public-key ⚫ however if sender signs message using their private-key then encrypts with recipients public key have both secrecy and authentication ⚫ again need to recognize corrupted messages ⚫ but at cost of two public-key uses on message Public-Key Message Encryption Dirty little detail on PKCS Every time you encrypt, size expands Due to protections in PKCS#1 So signing (by encryption) then encrypting, the size is more than doubled!  Message Authentication Code (MAC) generated by an algorithm that creates a small fixed-sized block ⚫ depending on both message and secret key ⚫ like encryption though need not be reversible appended to message as a “signature” receiver performs same computation on message and checks it matches the MAC provides assurance that message is unaltered and comes from sender Message Authentication Code asmall fixed-sized block of data generated from message + secret key MAC = C(K,M) appended to message when sent  Message Authentication Codes asshown the MAC provides authentication can also use encryption for secrecy ⚫ generally use separate keys for each ⚫ can compute MAC either before or after encryption  Message Authentication Codes why use a MAC? ⚫ sometimes only authentication is needed ⚫ sometimes need authentication to persist longer than the encryption (e.g. archival use) note that a MAC is not a digital signature Does NOT provide non-repudiation  MAC Properties a MAC is a cryptographic checksum MAC = CK(M) ⚫ condenses a variable-length message M ⚫ using a secret key K ⚫ to a fixed-sized authenticator is a many-to-one function ⚫ potentially many messages have same MAC ⚫ but finding these needs to be very difficult  Requirements for MACs taking into account the types of attacks need the MAC to satisfy the following: 1. knowing a message and MAC, is infeasible to find another message with same MAC 2. MACs should be uniformly distributed 3. MAC should depend equally on all bits of the message  Security of MACs likeblock ciphers have: brute-force attacks exploiting m/ ⚫ strong collision resistance hash have cost 2 2 128-bit hash looks vulnerable, 160-bits better ⚫ MACs with known message-MAC pairs can either attack keyspace (cf. key search) or MAC at least 128-bit MAC is needed for security  Security of MACs cryptanalytic attacks exploit structure ⚫ like block ciphers want brute-force attacks to be the best alternative morevariety of MACs so harder to generalize about cryptanalysis Keyed Hash Functions as MACs want a MAC based on a hash function ⚫ because hash functions are generally faster ⚫ crypto hash function code is widely available hash includes a key along with message original proposal: KeyedHash = Hash(Key|Message) ⚫ some weaknesses were found with this eventually led to development of HMAC  Problem with Keyed Hash KeyedHash = Hash(Key|Message) Recall hash function works on blocks Let M = Key | Message | Padding and M M=M1 M2 … ML, where |Mi| = Blocksize Hash=H(H(…H(H(IV,M1),M2),…,ML) But can add extra block(s) ML+1 by Hash’=H(Hash,ML+1) HMAC Details of HMAC ipad = block size * 0x5c opad = block size * 0x36  HMAC Design Objectives use, without modifications, hash functions allow for easy replacement of embedded hash function preserve original performance of hash function without significant degradation use and handle keys in a simple way. have well understood cryptographic analysis of authentication mechanism strength  HMAC specified as Internet standard RFC2104 uses hash function on the message: HMACK(M)= Hash[(K+ XOR opad) || Hash[(K+ XOR ipad) || M)] ] ⚫ where K + is the key padded out to block size ⚫ opad, ipad are specified padding constants overhead is just 3 more hash block calculations than the message needs alone any hash function can be used ⚫ eg. MD5, SHA-1, RIPEMD-160, Whirlpool  HMAC Overview  HMAC Security proved security of HMAC relates to that of the underlying hash algorithm attacking HMAC requires either: ⚫ brute force attack on key used ⚫ birthday attack (but since keyed would need to observe a very large number of messages) choosehash function used based on speed verses security constraints  Hash Functions condenses arbitrary message to fixed size h = H(M) usuallyassume hash function is public hash used to detect changes to message want a cryptographic hash function ⚫ computationally infeasible to find data mapping to specific hash (one-way property) ⚫ computationally infeasible to find two data to same hash (collision-free property) Cryptographic Hash Function  Hash Function Uses Message Integrity Check (MIC) ⚫ send hash of message (digest) ⚫ MIC always encrypted, message optionally Message Authentication Code (MAC) ⚫ send keyed hash of message ⚫ MAC, message optionally encrypted Digital Signature (non-repudiation) ⚫ Encrypt hash with private (signing) key ⚫ Verify with public (verification) key  Hash Functions & Message Authentication Symmetric Key Unkeyed Hash a) Message encrypted b) Message unencrypted  Hash Functions & Message Authentication Symmetric Key Keyed Hash a) Message unencrypted d) Message encrypted Hash Functions & Digital Signatures - PKCS  Other Hash Function Uses pseudorandom function (PRF) ⚫ Generate session keys, nonces ⚫ Produce key from password ⚫ Derive keys from master key cooperatively pseudorandom number generator (PRNG) ⚫ Vernam Cipher/OTP ⚫ S/Key, proof of “what you have” via messages  More Hash Function Uses to create a one-way password file ⚫ store hash of password not actual password ⚫ e.g., Unix, Windows NT, etc. ⚫ salt to deter precomputation attacks ⚫ Rainbow tables for intrusion detection and virus detection ⚫ keep & check hash of files on system ⚫ e.g., Tripwire Lamport One-time Passwords Password safety in distributed system ⚫ server compromise does not compromise P ⚫ interception of authentication exchange does not compromise password either Alice picks Password PA ⚫ Hashes password N times, HN(PA) ⚫ Server stores (Alice, N, HN(PA)) ⚫ Attacker can’t get PA from HN(PA) Lamport One-time Passwords Protocol ⚫ Alice sends “I’m Alice” ⚫ Server sends “N-1” ⚫ Alice sends “X” where X=HN-1(PA) ⚫ Server verifies H(X) = HN(PA) ⚫ Server updates to (Alice, N-1, X) Attackerstill can’t get PA or authenticate as Alice  Two Simple Insecure Hash Functions consider two simple insecure hash functions bit-by-bit exclusive-OR (XOR) of every block ⚫ Ci = bi1 xor bi2 xor... xor bim ⚫ a longitudinal redundancy check ⚫ reasonably effective as data integrity check one-bit circular shift on hash value ⚫ for each successive n-bit block rotate current hash value to left by1bit and XOR block ⚫ good for data integrity but useless for security Hash Function Requirements  Birthday Attacks might think a 64-bit hash is secure but by Birthday Paradox is not birthday attack works thus: ⚫ given user prepared to sign a valid message x m ⚫ opponent generates 2 /2 variations x’ of x, all with essentially the same meaning, and saves them m ⚫ opponent generates 2 /2 variations y’ of a desired fraudulent message y ⚫ two sets of messages are compared to find pair with same hash (probability > 0.5 by birthday paradox) ⚫ have user sign the valid message, then substitute the forgery which will have a valid signature conclusion is that need to use larger MAC/hash  Birthday Attacks What are chances we get a match? N distinct values, k randomly chosen ones ⚫ P(N,i) = prob(i randomly selected values from 1..N have at least one match) ⚫ P(N,2) = 1/N ⚫ P(N,i+1) = P(N,i)+(1-P(N,i))(i/N) ForP(N,k)>0.5, need k ≈ N1/2 Need double # bits in hash value Hash Function Cryptanalysis cryptanalytic attacks exploit some property of algo so faster than exhaustive search hash functions use iterative structure ⚫ process message in blocks (incl length) attacks focus on collisions in function f  Block Ciphers as Hash Functions can use block ciphers as hash functions ⚫ using H0=0 and zero-pad of final block ⚫ compute: Hi = EMi [Hi-1] ⚫ and use final block as the hash value ⚫ similar to CBC but without a key resulting hash is too small (64-bit) ⚫ both due to direct birthday attack ⚫ and to “meet-in-the-middle” attack other variants also susceptible to attack  Block Ciphers as Hash Functions H 0 Block cipher key length B Pad Message M to multiple of B M1 E Break padded M into L blocks L = |M|/B M2 E M = M1 M2 … ML Use blocks of M as keys in block cipher, iteratively encrypt state value starting with constant H0 resulting in ML E hash value H = HL = E(ML,….E(M2,E(M1,H0))…) HL  Secure Hash Algorithm SHA originally designed by NIST & NSA in 1993 was revised in 1995 as SHA-1 US standard for use with DSA signature scheme ⚫ standard is FIPS 180-1 1995, also Internet RFC3174 ⚫ nb. the algorithm is SHA, the standard is SHS based on design of MD4 with key differences produces 160-bit hash values 2005 results on security of SHA-1 raised concerns on its use in future applications  Revised Secure Hash Standard NIST issued revision FIPS 180-2 in 2002 adds 3 additional versions of SHA ⚫ SHA-256, SHA-384, SHA-512 designed for compatibility with increased security provided by the AES cipher structure & detail is similar to SHA-1 hence analysis should be similar but security levels are rather higher SHA-512 Overview  SHA-512 Compression Function heartof the algorithm processing message in 1024-bit blocks consists of 80 rounds ⚫ updating a 512-bit buffer ⚫ using a 64-bit value Wt derived from the current message block ⚫ and a round constant based on cube root of first 80 prime numbers SHA-512 Round Function Structure of each round in SHA-512  Majority Function Conditional Function Rotate Functions Compression Function There are 80 constants, K0 to K79, each of 64 bits. Similar These values are calculated from the first 80 prime numbers (2, 3,…, 409). For example, the 80th prime is 409, with the cubic root (409)1/3 = 7.42291412044. Converting this number to binary with only 64 bits in the fraction part, we get The fraction part: (6C44198C4A475817)16  Example 12.7 We apply the Majority function on buffers A, B, and C. If the leftmost hexadecimal digits of these buffers are 0x7, 0xA, and 0xE, respectively, what is the leftmost digit of the result? Solution The digits in binary are 0111, 1010, and 1110. a. The first bits are 0, 1, and 1. The majority is 1. b. The second bits are 1, 0, and 1. The majority is 1. c. The third bits are 1, 1, and 1. The majority is 1. d. The fourth bits are 1, 0, and 0. The majority is 0. The result is 1110, or 0xE in hexadecimal.  Example 12.8 We apply the Conditional function on E, F, and G buffers. If the leftmost hexadecimal digits of these buffers are 0x9, 0xA, and 0xF respectively, what is the leftmost digit of the result? Solution The digits in binary are 1001, 1010, and 1111. a. The first bits are 1, 1, and 1. The result is F1, which is 1. b. The second bits are 0, 0, and 1. The result is G2, which is 1. c. The third bits are 0, 1, and 1. The result is G3, which is 1. d. The fourth bits are 1, 0, and 1. The result is F4, which is 0. The result is 1110, or 0xE in hexadecimal. Words A message block and the digest as words Word Expansion Word expansion in SHA-512 SHA-512 Round Function Show how W60 is made. Solution Each word in the range W16 to W79 is made from four previously-made words. W60 is made as Message Digest Initialization  Message digest creation SHA-512 12.89  Message Preparation SHA-512 insists that the length of the original message be less than 2128 bits. Note SHA-512 creates a 512-bit message digest out of a message less than 2128. 12.90  Example 12.1 This example shows that the message length limitation of SHA- 512 is not a serious problem. Suppose we need to send a message that is 2128 bits in length. How long does it take for a communications network with a data rate of 264 bits per second to send this message? Solution A communications network that can send 264 bits per second is not yet available. Even if it were, it would take many years to send this message. This tells us that we do not need to worry about the SHA-512 message length restriction.  Example 12.2 This example also concerns the message length in SHA-512. How many pages are occupied by a message of 2128 bits? Solution Suppose that a character is 32, or 26, bits. Each page is less than 2048, or approximately 212, characters. So 2128 bits need at least 2128 / 218, or 2110, pages. This again shows that we need not worry about the message length restriction. Padding and length field in SHA-512  Example 12.3 What is the number of padding bits if the length of the original message is 2590 bits? Solution We can calculate the number of padding bits as follows: The padding consists of one 1 followed by 353 0’s.  Example 12.4 Do we need padding if the length of the original message is already a multiple of 1024 bits? Solution Yes we do, because we need to add the length field. So padding is needed to make the new block a multiple of 1024 bits.  Example 12.5 What is the minimum and maximum number of padding bits that can be added to a message? Solution The minimum length of padding is 0 and it happens when a. (−M − 128) mod 1024 is 0. This means that |M| = −128 mod 1024 = 896 mod 1024 bits. In other words, the last block in the original message is 896 bits. We add a 128-bit length field to make the block complete.  Example 12.5 b) The maximum length of padding is 1023 and it happens when (−|M| −128) = 1023 mod 1024. This means that the length of the original message is |M| = (−128 −1023) mod 1024 or the length is |M| = 897 mod 1024. In this case, we cannot just add the length field because the length of the last block exceeds one bit more than 1024. So we need to add 897 bits to complete this block and create a second block of 896 bits. Now the length can be added to make this block complete.  SHA-3 SHA-1 not yet "broken” ⚫ but similar to broken MD5 & SHA-0 ⚫ so considered insecure SHA-2 (esp. SHA-512) seems secure ⚫ shares same structure and mathematical operations as predecessors so have concern NIST announced in 2007 a competition for the SHA-3 next gen NIST hash function Keccak winner Oct 2012 – std in Q2,2014  SHA-3 Requirements replace SHA-2 with SHA-3 in any use ⚫ so use same hash sizes preserve the online nature of SHA-2 ⚫ so must process small blocks (512 / 1024 bits) evaluation criteria ⚫ security close to theoretical max for hash sizes ⚫ cost in time & memory ⚫ characteristics: such as flexibility & simplicity Two Groups of Compression Functions 1. The compression function is made from scratch. Message Digest (MD) 2. A symmetric-key block cipher serves as a compression function. Whirlpool Iterated Hash Function Merkle-Damgard Scheme Rabin Scheme Davies-Meyer Scheme Miyaguchi-Preneel Scheme Secure Hash Algorithm (SHA-1) SHA was designed by NIST & NSA in 1993, revised 1995 as SHA-1 US standard for use with DSA signature scheme standard is FIPS 180-1 1995, also Internet RFC3174 note: the algorithm is SHA, the standard is SHS produces 160-bit hash values now the generally preferred hash algorithm based on design of MD4 with key differences 106 SHA Overview 1. pad message so its length is 448 mod 512 2. append a 64-bit length value to message 3. initialise 5-word (160-bit) buffer (A,B,C,D,E) to (67452301,efcdab89,98badcfe,10325476,c3d2e1f0) 1. process message in 16-word (512-bit) chunks: expand 16 words into 80 words by mixing & shifting use 4 rounds of 20 bit operations on message block & buffer add output to input to form new buffer value 2. output hash value is the final buffer value 107 SHA-1 Compression Function each round has 20 steps which replaces the 5 buffer words thus: (A,B,C,D,E)