MACs and Hash Functions

Disclosure Message Encryption traffic analysis masquerade content modification Message Authentication sequence modification & Message Integrity timing modification source repudiation Digital Signature destination repudiation

Encryption protects message against passive attack, while Message Authentication protects against active attack.

message authentication is concerned with:

• protecting the integrity of a message
• validating identity of originator
• non-repudiation of origin (dispute resolution) Approaches for message authentication
  • Authentication using conventional encryption.
    • Symmetric Encryption
  • Authentication using Public Key Encryption
  • Message Authentication without message encryption.
    • MAC

• Message is not always encrypted, but an authentication tag is generated and appended to the message.
• Authentication and Confidentiality services are combined in a single algorithm by encrypting the message plus the authentication tag.

generated by an algorithm that creates a small fixed-sized block

• depending on both message and some 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

• If MAC matches then message is authenticated, and this means

1.

Message is not altered.

2.

Message is coming from alleged user.

If message includes a sequence number (as used with TCP)

3.

then ordering is guaranteed.

A number of algorithms are used to generate the MAC.

• NIST recommends to use DES to generate an encrypted version of the message and the last number of bits in the ciphertext is used as the code (16 or 32 bits).
• Authentication algorithm needs not to be reversible.

as shown the MAC provides authentication can also use encryption for secrecy

• generally use separate keys for each
• can compute MAC either before or after encryption
• is generally regarded as better done before why use a MAC?
• sometimes only authentication is needed
• sometimes need authentication to persist longer than the encryption (eg. archival use) note that a MAC is not a digital signature

taking into account the types of attacks need the MAC to satisfy the following:

knowing a message and MAC, is infeasible to find

1.

another message with same MAC

2.

MACs should be uniformly distributed

3.

MAC should depend equally on all bits of the message

• use, without modifications, hash functions
• allow for easy replaceability 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

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 generated using the same key) choose hash function used based on speed versus security constraints

• Alternative to MAC.
• Accept a variable – sized message M as input.
• Produce fixed-sized message digest H(M).
• Unlike MAC: a hash function doesn’t take a secret key as input.
• To authenticate a message: the message digest is sent with the message.

A hash function computes a fixed length value from a variable length source

• Example: Check sums in communication protocols
• Indices in databases

More convenient to handle a hash of a document instead of the document itself We will consider cryptographically secure hash functions.

Hash functions are used for:

• message and file integrity
• secure login
• fingerprints of keys
• authentication
• digital signatures

• A hash function is a function f:{0,1}* → {0,1}n.
• The size of the output, n, is a property of the function. Common values are 128, 160 and 256.
• Commonly used hash functions are MD5, SHA and SHA-1

Let H be a hash function One-way

• Given x, unfeasible to compute an v such that H(v) = x

Collision-free

• Unfeasible to find x1 and x2 such that H(x1) = H(x2) and x1 ≠ x2

1. It should be possible to efficiently compute the hash value z=H(m) of a message m.
2. Given the hash value z=H(m), it should be computationally infeasible to find m. A function with this property is called a one-way function.
3. Given a message m, it should be infeasible to find another message m’ such that H(m)=H(m’).
4. It should be infeasible to find two messages m and m’ such that H(m)=H(m’). Property 3) is known as weak collision resistance, and Property 4) is known as strong collision resistance.

simultaneously protect confidentiality and authenticity of communications

• often required but usually separate approaches
• Hash-then-encrypt: E(K, (M || H(M))
• MAC-then-encrypt: E(K2, (M || MAC(K1, M))
• Encrypt-then-MAC: (C=E(K2, M), T=MAC(K1, C)
• Encrypt-and-MAC: (C=E(K2, M), T=MAC(K1, M)

• Brute-force attacks and cryptanalysis
• a preimage or second preimage attack
  • find y s.t. H(y) equals a given hash value
• collision resistance
  • find two messages & with same hash so H(x) = x y H(y)
• cryptanalytic attacks exploit some property of algorithm, so faster than exhaustive search

• Suppose a hash function H produces n bit values.
• Compose a document nice treaty and about 2n/2+1 semantically equivalent versions.
• Similarly, compose an evil treaty and about 2n/2+1 semantically equivalent versions.
• With probability 1⁄2 or more there will be a version of the nice treaty and a version of the evil treaty that have the same hash value.

Uses modified DES as if it were a hash function

• Encrypt NULL string using password as the key
• Truncates passwords to 8 characters!
• Artificial slowdown: run DES 25 times
• Can instruct modern UNIXes to use MD5 hash function

Problem: passwords are not truly random

• With 52 upper- and lower-case letters, 10 digits and 32
  • punctuation symbols, there are 948 ≈ 6 quadrillion possible 8 character passwords
• Humans like to use dictionary words, human and pet names ≈ 1 million common passwords

httpd:Nologin:100:22:httpd:/usr/users/httpd:/bin/sh guest:41LYDCYHYJzHQ:200:15:Guest:/usr/users/guest:/bin/tcsh oracle:Nologin:201:200::/usr/users/oracle:/bin/tcsh mysql:LS6qP.LbvchSk:202:202::/usr/users/mysql:/bin/tcsh Andris:Ie7K1yjGLDqsw:203:203::/usr/users/Andris:/bin/tcsh Password length up to 8 characters, encrypted by 1-way hash function crypt(3).

Are they safe?

The salt introduces disorder in the DES algorithm in one of 16777216 or 4096 possible ways (ie. with 24 or 12 bits: if bit i of the salt is set, then bits i and i+24 are swapped in the DES E-box output).

The DES key is used to encrypt a 64-bit constant using count iterations of DES. The value returned is a null-terminated string, 20 or 13 bytes (plus null) in length, consisting of the setting followed by the encoded 64-bit encryption.

httpd:Nologin:100:22:httpd:/usr/users/httpd:/bin/sh guest:41LYDCYHYJzHQ:200:15:Guest:/usr/users/guest:/bin/tcsh oracle:Nologin:201:200::/usr/users/oracle:/bin/tcsh mysql:LS6qP.LbvchSk:202:202::/usr/users/mysql:/bin/tcsh Andris:Ie7K1yjGLDqsw:203:203::/usr/users/Andris:/bin/tcsh 13 characters (Base64 - 6 bit),78 bits 64 bit hashed value 12 bits of "salt"

Password file /etc/passwd is world-readable

• Contains user IDs and group IDs which are used by many system programs

Dictionary attack is possible because many passwords come from a small dictionary

• Attacker can compute H(word) for every word in the dictionary and see if the result is in the password file
• With 1,000,000-word dictionary and assuming 10 guesses per second, brute-force online attack takes 50,000 seconds (14 hours) on average
• This is very conservative. Offline attack is much faster!

Typical password dictionary

• 1,000,000 entries of common passwords
• people's names, common pet names, and ordinary words.
• Suppose you generate and analyze 10 guesses per second
• This may be reasonable for a web site; offline is much faster
• Dictionary attack in at most 100,000 seconds = 28 hours, or 14 hours on average

If passwords were random

• Assume six-character password
• Upper- and lowercase letters, digits, 32 punctuation characters
• 689,869,781,056 password combinations.
• Exhaustive search requires 1,093 years on average

• The message digest algorithm MD5 by Ron Rivest with 128 bit hash values.
• The secure hash algorithm SHA-1. It was developed by NSA and standardized by NIST. This algorithm uses 160 bit hash values encoded in 5 x 32 bit words.
• The family SHA-256, SHA-384, SHA-512 of hash functions that are supposed to be used with AES. They will be part of the NIST Cryptographic Toolkit. Why are these bit lengths used? Collisions in SHA-1 can be found by 2 63 attempts Collision in MD5 can be found in 8 hours using a notebook PC...

• A detailed description of MD5 is contained in RFC1321.
• Hans Dobbertin has shown that MD5 is not collision resistant, so it is not advisable to use this algorithm.
• It is used in IPSec and other protocols.

MD4 Precursor to MD5 Design goals of MD4 (which are carried over to MD5)

• Security
• Speed
• Simplicity and compactness
• Favor little-endian architecture

MD4

Main differences between MD5 and MD4

1. A fourth round has been added.
2. Each step now has a unique additive constant.
3. The function g in round 2 was changed from (bc v bd v cd) to (bd v c d) to make g less symmetric. ’
4. Each step now adds in the result of the previous step. This promotes a faster "avalanche effect".
5. The order in which input words are accessed in rounds 2 and 3 is changed, to make these patterns less like each other.
6. The shift amounts in each round have been approximately optimized, to yield a faster "avalanche effect." The shifts in different rounds are distinct.

• 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
  • Note, the algorithm is SHA, the standard is SHS
• based on design of MD4 with key differences
• produces 160-bit hash values
• recent 2005 results on security of SHA-1 have raised concerns on its use in future applications

• 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-1 SHA-224 SHA-256 SHA-384 SHA-512

Message digest size

160 224 256

384 512

Message size < 2 64 < 2 64 < 2 64 < 2 128 < 2 128 Block size

512 512 512 1024 1024

Word size

Number of steps

Secure Hash Algorithm (SHA)

Developed by NIST (National Institute of Standards and Technology)

• Published as a FIPS PUB 180 in 1993
• A revised version is issued as FIPS PUB 180-1
• Generally referred to as SHA-1

Input: a message with a maximum length of less than

64 bits

Output: 160-bit message digest 32-bit word units, 512-bit blocks 4 rounds × 20 steps per block Closely models MD4 Slower, stronger than MD5

SHA-1 logic

The overall structure and logic is similar to MD5 Step 1: Append padding bits Step 2: Append length Step 3: Initialize MD buffer

• 160-bit buffer (five 32-bit registers A,B,C,D,E) is used to hold intermediate and final results of the hash function
• A,B,C,D,E are initialized to the following values
• A,B,C,D = same as in MD5, E = C3D2E1F0
• Stored in big-endian format (most significant byte of a word in the low-address byte position)
  • E.g. word E: C3 D2 E1 F0 (low address high address) ...

heart of 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