Message Integrity and Authentication

• Message Integrity and Authentication verifies that data has not been altered and confirms its origin.

Hash Functions

• A hash function produces a fingerprint of a file/message/data to detect changes.
• A hash function is mathematically represented as h = H(M), where M is the message and h the hash value.
• These functions compress variable-length messages into fixed-size fingerprints for efficiency.
• Once a message and its hash are created, they can be transmitted separately.
• Hash functions are often assumed to be public and unkeyed, requiring methods to protect the hash value.
• Hash functions are mostly used when creating digital signatures.

Properties for Hash Functions

• Pre-image Resistance: Difficult to find a message M' that hashes to the same value as a given hash h(M).
• Second Pre-image Resistance: Given a message M, it is difficult to find another message M' with the same hash value.
• Collision Resistance: Difficult to find two different messages, M and M', that hash to the same value.

Pigeonhole Principle

• Hashing condenses a message into a digest, which should be shorter than the original message.
• The pigeonhole principle implies that if you have more items than containers, at least one container must hold more than one item; thus, collisions can occur because the digest is shorter.

Merkle-Damgard Scheme

• It is an iterated hash function.
• Message length and padding are added to create an augmented message that can be evenly divided into blocks of 'n' bits, where 'n' is the block size for the compression function.
• The message is divided into 't' blocks of 'n' bits each, M1, M2, ... Mt.
• Digests are created through 't' iterations, resulting in H₁, H2, ... Ht.
• Before the function starts, H₀ is set to a fixed IV initialization vector.
• The compression function 'f' is such that Hᵢ = f(Hᵢ₋₁, Mᵢ).
• H_t is the cryptographic hash function of the original message, h(M).
• It serves as the foundation for many cryptographic hash functions.
• Collision resistance in the compression function implies collision resistance in the overall hash function.
• Only one collision resistant compression function needs to be designed for insertion into the Merkle-Damgard scheme.
• Two Hash Function groups: Compression functions made from scratch, and symmetric block ciphers serving as the compression function.

Compression Function From Scratch

• Message Digest (MD) and Secure Hash Algorithm (SHA) can be made from scratch

Message Digest Algorithm : MD5

• Ronald Rivest (of RSA) designed it
• MD5 is the latest in a series of MD2 and MD4.
• It produces a 128-bit hash value.
• Brute-force and cryptanalytic concerns have surfaced in recent times.
• Specified as Internet standard RFC1321.
• Input is processed in 512-bit blocks, taking a message of arbitrary length and producing a 128-bit message digest.

MD5 Overview

• The processing consists of 5 steps
• The message is padded to ensure its length is congruent to 448 mod 512 using 1 to 512 bits, starting with 1 followed by zeros.
• A 64-bit length value of the original message is appended; if the message exceeds 2^64, the lower 64 bits are used.
• The first two steps yield a message that is an integer multiple of 512 bits in length.
• A 128-bit buffer holds intermediate and final hash function results and consists of four 32-bit registers in little-endian format, initialized with specific hexadecimal values.
• The registers are initialized as
• A:01 23 45 67
• B: 89 AB CD EF
• C: FE DC BВА 98
• D:76 54 32 10
• Every one of fours rounds contains 16 steps
• each step is of the form: a = b + ((a + g(b,c,d) + X[k] + T[i]) <<< s)
• Variables a, b, c, and d represent the four words of the buffer
• g is one of the primitive functions F, G, H, I
• <<<s indicates a circular left shift of a 32-bit argument by s bits
• X[k] is the kth 32-bit word in the qth 512-bit message block, with q varying from 0 to L-1 and k from 0 to 15
• T[i] is the ith 32-bit word in matrix T derived from a sine function.
• The output of each round goes as input to the next round to form a new buffer value.
• After all L 512-bit blocks are processed, the output from the Lth stage is the 128-bit message digest.
• Each of the 16 words of X[i] is used exactly once, differing round to round.
• In the first round the words are used with the same order.
• Rounds 2 to 4 use permutations p₂(i) = (1 + 5i) mod 16, p3(i) = (5 + 3i) mod 16, and p4(i) = 7i mod 16.
• MD5 security is dependent on all message bits and, according to Rivest, is as secure as possible
• Known attacks include: Berson's 1992 differential cryptanalysis on any round (though unable to extend), Boer & Bosselaers' 1993 pseudo collision, and Dobbertin's 1996 MD compression function collisions.
• MD5 is considered vulnerable and requires replacement.

Secure Hash Algorithm (SHA-1)

• NIST (National Institute of Standards and Technology) & NSA (National Security Agency) designed it in 1993 and revised it in 1995 as SHA-1.
• SHA-1 is a US standard for use with DSA signature scheme
• The standard is FIPS 180-1 1995, also Internet RFC3174.
• The algorithm is SHA, while SHS defines the standard.
• It produces 160-bit hash values.
• SHA-1 is generally preferred and based on the design of MD4 with key differences.

SHA Overview

• Pad message so its length is 448 mod 512 append a 64-bit length value to message initialize a 5-word (160-bit) buffer (stored in big endian format) to
• A = 67 45 23 01
• B = EF CD AB 89
• C = 98 BA DC FE
• D = 10 32 54 76
• E = C3 D2 EI FO
• Process message in 16-word (512-bit) chunks:
• Uses 4 rounds each of 20 steps operations on message block & buffer
• Add output to input to form new buffer value
• The output hash value is the final buffer value

SHA-1 Compression Function

• Each round consists of 20 steps which transform the 5 buffer words such that: (A,B,C,D,E) <-(E+f(t,B,C,D)+(A<<5)+W+K+),A, (B<<<30),C,D)
• a,b,c,d refer to the 4 words of the buffer
• t is the step number
• f(t,B,C,D) is nonlinear round functions
• Wt is derived from the message block using (Wt = S¹(Wt-16 XOR Wt-14 XOR Wt-8XOR Wt-3))
• Kt is an additive constant
• The primitive logical function fₜ is:
• Round 1: (b^c)v(b'^d)
• Round 2: b XOR c XOR d
• Round 3: (b^c)v(b^d) v (c^d)
• Round 4: b XOR c XOR d
• Constant additives Kₜ:
• Round 1: Kₜ = 5A827999
• Round 2: Kₜ = 6ED9EBA1
• Round 3: Kₜ = 8F1BBCDC
• Round 4: Kₜ = CA62C1D6
• Brute force attacks on SHA-1 are harder (160 vs 128 bits for MD5).
• Not vulnerable to any known cryptanalytic attacks (compared to MD4/5).
• A little slower than MD5 (80 vs 64 steps).
• Designed to be simple and compact.
• Optimized for big endian CPUs (vs MD5, which is for little endian).

Revised Secure Hash Standard

• NIST has issued a revision FIPS 180-2 that adds SHA-256, SHA-384, and SHA-512.
• Designed for compatibility with the greater security given by the AES cipher
• Similar structure and detailing to SHA-1, so analysis looks similar

Hash Functions based on Block Ciphers

• Iterated hash functions can employ symmetric-key block ciphers as compression functions, offering a way to create one-way functions without developing new compression functions.
• In this case, block ciphers only perform encryption

Rabin Scheme

• Its design is based on the Merkle-Damgard scheme.
• Replaces the compression function with encryption cipher.
• Message block serves as the key.
• Previously created digest is used as the plaintext and the ciphertext is the new message digest.
• Digest size matches the block cipher size in the underlying cryptosystem
• Vulnerable to meet-in-middle attacks.

Davies-Meyer Scheme

• Forward feed is used to protect against meet-in-middle attack and is the only way it differs from Rabin scheme

Matyas-Meyer-Oseas Scheme

• It is a dual version of the Davies-Meyer scheme
• Previous message digest is used as the key to the cryptosystem; can be used when key and ciphertext are of same size (e.g.AES).

Miyaguchi-Preneel Scheme

• Algorithm is made stronger against attacks by XORing the Plaintext, the key and the ciphertext together to create the new digest, and can be seen as an extended version of the Matyas-Meyer-Oseas sheme

Whirlpool

• Based on AES, it is an iterated cryptographic hash function with the Miyaguchi-Preneel scheme.
• It replaces the compression function with a symmetric-key block cipher.
• The block cipher is a tailored version of AES.
• Before hashing, the message must be less than 2256 bits.
• Message padding consists of 1 followed by 0s to create an odd multiple of 256.
• After padding, a 256-bit block defines the length of the original message.
• Block size: 512 bits
• Cipher key size: 512 bits
• Number of rounds: 10
• Key expansion: using the cipher itself with round constants as round keys
• Substitution: SubBytes transformation
• Permutation: ShiftColumns transformation
• Mixing: MixRows transformation
• Round Constant: cubic roots of the first eighty prime numbers

Drawback of Iterated Hash Function

• The iterated nature of Merkle-Damgard based hash functions can lead to weaknesses, prohibiting their use as keyed hash functions (Message Authentication Codes).
• Ideally, learning a message digest should only be possible through computation and previously computed hash values should not expose new message digests.
• Practical applications such as MACs cannot use hash functions that do not meet this criteria

Modification Detection Code

• The digest created by the cryptographic hash function can detect any code modification or it provides data integrity, but it cannot provide data origin authentication.
• To ensure data integrity and authenticate the data origin, a Modification Detection Code (MDC) needs to become a Message Authentication Code (MAC).

Message Authentication Code (MAC)

• A MAC provides a small, fixed-size block generated by an algorithm dependent on both a message and a secret key.
• The block is appended to the message as a signature.
• The receiver computes the MAC and verifies it against the received MAC to confirm authenticity and integrity
• MAC = Cₖ(M), where M is the input message, C is the MAC function, and K is the shared secret key.
• The MAC ensures that the message is unaltered and from the sender.
• Given a secret key and a matching received MAC, the receiver is assured of authenticity and the message's proper sequence when a sequence number is included.
• The MAC function is many-to-one, where potentially many messages have the same MAC, but finding these collision causing messages needs to be very difficult.
• Domain of the MAC function consists of messages of arbitrary lengths, whereas the MAC range is all possible MACs and keys.
• The MAC must meet these requirements: Observing a message M and its MAC CK(M), it is computationally infeasible to find a new message M' where C(M)=C(M')
• For chosen messages M and M' the likelihood that CK(M)=CK(M') is 2⁻ⁿ, where n is the number of bits in the MAC. MACs must be evenly distributed
• Let M' be equal to some known transformation on M i.e. M'= f(M). Then Pr[CK(M) = CK(M')] = 2-n; MAC should depend equally on all bits of the message

Security of MAC

• It depends on the integrity of the underlying hash algorithms.
• Nested MAC is used to improve security. It involves a two-step process: first, concatenating the key with the message and hashing; second, concatenating the key with the intermediate digest and hashing again

HMAC (Hashed MAC)

• HMAC is an Internet standard for achieving a nested MAC.
• It employs hash functions: HMACₖ = Hash[(K+ XOR opad) || Hash[(K+ XOR ipad)||M)]]
• K represents a key padded to size, combined with specified padding constants opad, ipad, and any hash function can be applied like MD5, SHA-1, RIPEMD-160, Whirlpool.

CMAC

• Also known as Data Authentication algorithm or CBCMAC.

Birthday Attacks

• Birthday Paradox: Finds the minimum number k, of students in a classroom such that the probability that at least 2 students have the same birthday is greater than 0.5. Generalizing the problem : a uniformly distributed random variable with N possible values ( between 0 and N-1), the minimum number of instances, k, such that the probability that at least two instances are equal is greater than 0.5
• Birthday attack: Generates 2n/2 variations of valid messages, and opponent generates 2n/2 variations of a desired fraudulent message, comparing variations to find pair with same hash.

Digital Signatures

• Digital Signatures ensures the authenticity and integrity of the digital documents

Difference between Conventional and Digital Signatures

• Inclusion: Inclusion: a conventional signature is included in the document; a digital signature is a separate document send along with the message document.
• Verification method: For a conventional signature, the recipient compares the signature with an already recorded one, whereas for a digital signature the recipient apply a verification technique to the combination of the message and the signature to verify the authenticity.
• Relationship: a conventional message typically involves a one-to-many relationship between the signature and the documents, whereas a digital signature creates a one-to-one relationship where each message requires a new message.
• Duplicity: Copies of conventional signatures can be distinguished from originals: digital signatures are difficult to differentiate unless timestamped.

Services provided by Digital Signatures

• Message authenticity: data origin authentication, verification by sender's public key authenticates the sender.
• Message integrity: uses hash function like SHA.
• Nonrepudiation: Nonrepudiation: using Trusted third party the sender sends the message and signature to a trusted center which verifies the sender, stores copy of signature and additionally signs it with its private key and dispatches to the receiver. The receiver can verify the signature with the center's public key and in case of dispute, approach the center which possess the message signed by the sender. To hide message from center confidentiality can be added.

Digital Signature Properties

• Must depend on the message signed.
• Must use information unique to sender to prevent both forgery and denial.
• Must be relatively easy to produce.
• Must be relatively easy to recognize and verify.
• Must be computationally infeasible to forge with new message for existing digital signature and with fraudulent digital signature for given message.
• Be practical to save digital signature in storage.
• Two approaches: Direct Digital Signature, and Arbitrated Digital Signature

Attacks on Digital Signature

• Key-Only Attack: The attacker can only access public details released by the sender and tries to copy their signature onto a message to mislead receiver.
• Known-Message Attack: The attacker accesses past signed messages and constructs new messages with forged signatures, similar to known-Plaintext attack.
• Chosen- Message Attack: The attacker gets sender to sign chosen messages and uses these message-signature pairs to forge signatures which similar to chosen-plaintext attack.

Forgery Types

• Existential Forgery: An attacker creates a valid but unusable message-signature pair, and is probable but can not be used as the message cannot be read properly.
• Selective Forgery: An attacker forges a signature on a chosen message, which is difficult but may harm the sender.

Digital Signature Schemes

• RSA Digital signature
• ElGamal Digital signature
• Schnorr Digital signature
• Digital Signature Standard

RSA Digital Signature

• The sender creates a signature out of the message using his private component as S = Md mod n.
• The receiver verifies the signature by applying the public component of the sender on the signature and creates a copy of the message M'= Smod n. if M' = M, receiver accepts the message. M' = M(mod n) S = M (mod n) Mex d = M (mod n)

RSA Signature on Message Digest

• Instead of the message itself, using the digest and signing depends on the strength of the hash algorithm.

ElGamal Digital Signature Scheme

• Key generation:
• Choose a large prime number p.
• Select a primitive element e₁ from the set Zp*.
• Choose a number d (less than p-1) as the private key.
• Calculate e2 = e₁ d
• Sender's public key is the tuple (e₁, e2, p) and private key is d.
• Signing:
• Sender Chooses a secret random number r.
• Calculates first signature S₁=e₁'mod p.
• Calculates the second signature.
• S2 = (M – d x S₁) X r 1 mod (p-1) where r 1 is inverse of r modulo p.
• Sends M, Si and S2 to the receiver.
• Verifying:
• Checks if 0 < S₁ < p.
• Checks if 0 < S2 < p-1.
• Calculates V₁ = e₁M mod p. S S -2 mod p.
• Calculates V2 = e21 x S₁
• If V₁ is congruent to V₂ message is accepted else rejected.

Schnorr Digital Signature Scheme

• The problem with the Elgamal digital signature is that p needs to be very large to guarantee that the discrete logarithm problem is intractable in Z*. The recommendation is a p of at least 1024 bits. This could make the signature as large as 2048 bits. To reduce the size of the signature, Schnorr proposed a new scheme based on ElGamal, but with a reduced signature size.

Key Generation:

• Sender selects a prime p, (1024 bits).
• Selects another prime q, which is same size as the digest created by the cryptographic hash function, and is modulo 0 with p
• Chooses eo, a primitive element in Zp and calculates e₁= eo(p-1)/q mod p.
• Chooses an integer d, as private key.
• Calculates e2 =e₁d mod p.
• Public key is (e₁, e2, p, q), with private key (d)

Signing:

• Choose a random number r between 1 and q
• Calculate the first signature S₁ = h(Mle₁" mod p)
• Calculate the second signature S₂ = r + d x S₁ mod q
• Sends M, Si and S2 to receiver

Verifying:

• The receiver calculates V = h(M] e₁^S₂ e₂^-S₁ mod p)
• If S₁ is congruent to V modulo p, the message is accepted, otherwise it is rejected.

Digital Signature Standard (DSS)

• US Govt approved signature scheme FIPS 186 designed by NIST & NSA in early 90's
• DSS is the standard, DSA is the algorithm.
• Uses the SHA Hash algorithm.
• A variant on ElGamal and Schnorr schemes.
• Creates a 320 bit signature, but with 512-1024 bit security.
• Security depends on difficulty of computing discrete logarithms.

DSA Key Generation

• It is required to generate keys and make the publics ones known before signing the message
• Selects a prime p between 512 and 1024 bits but multiple of 64.
• Selects a 160-bit prime q such that q divides (p-1).
• Uses two multiplication groups <Zp*, x> and <Zq*, x>; the second is a subgroup of the first. e₁d mod p
• Choose a primitive element eo from Zp and calculate e₁= eo(p-1)/q mod p
• Choose d as the private key and calculates e2 = e₁
• Public key is (e₁, e2, p, q), with private key (d)

DSA Signature Creation

• The sender chooses a random number r (1≤ r ≤ q).
• Calculates the first signature S₁=(e₁'mod p) mod q.
• Creates of digest of message h(M).
• Calculates the second signature S₂ = (h(M) – d x S₁) X r¹ mod q
• Sends M, Si and S2 to the receiver.

DSA Signature Verification

• Checks if 0 < S₁ < q.
• Checks if 0 < S2 < q.
• Calculates a digest of M using the same hash algorithm used by the sender.
• Calculates V = [(e₁h(M)S₂11 e2S1S2¹) mod p] mod q S2
• If S1 is congruent to V, the message is accepted; otherwise, it is rejected.

Variations of Digital Signature

• Time Stamped Signatures: timestamps a signatures to prevent replays
• Having current date and time in document may pose problem if the clocks of the peers are not synchronized and a universe time is not used.
• One solution is to use a nonce which is a one time random number as a time stamp.
• With a blind digital signature schemes (patented by the researcher David Chum), a document that we want to get signed without revealing the contents of the document to the signer.
• B creates a message and blinds it, sending to A, signs it with the sending algorithm while blinded, then returns it. B unblinds it to obtain a signature.
• With the RSA scheme, B first computes the blinded message with M'=M * b^e (mod n), then A signs this with S_blind= M'^d (mod n). A is a document may get signed by B causing harm.
• Schnorr Digital Signature Scheme needs large p to guarantees discrete logarithm problem is difficult in Z*p reducing the signature size by signing.
• Undeniable Digital Signature: Consisting of a signing, verification and disavowal protocol, this solution uses challenge-response mechanisms and makes A more integral to make forgeries more obvious.