Hash and Digital Signatures

Lecture 5

What is the primary function of a cryptographic hash function regarding input and output lengths?

It converts an arbitrary long sequence of symbols into a fixed-length sequence.

What term describes the fixed-length output of a hash function h(P)?

Hash value (or digest).

In the context of hash functions, what constitutes a 'collision'?

A pair of distinct plaintexts P and Q that map to the same hash value, such that h(P) = h(Q).

The computation time of an efficient hash function should be proportional to what characteristic of the input?

The length of the input plaintext.

Term: Preimage resistance

Definition: Given a hash value x, it is computationally hard to find any plaintext P such that h(P) = x.

What is the alternative name for 'Preimage resistance'?

One-way function property.

Term: Second preimage resistance

Definition: Given a plaintext P, it is computationally hard to find a different plaintext Q such that h(P) = h(Q).

What is the alternative name for 'Second preimage resistance'?

Weak collision resistance.

Term: Collision resistance

Definition: It is computationally hard to find any pair of distinct plaintexts P and Q such that h(P) = h(Q).

What is the alternative name for 'Strong collision resistance'?

Collision resistance.

Which property of hash functions automatically implies second preimage resistance?

Collision resistance.

What is the minimum recommended length for hash values to defend against brute-force attacks?

At least 256 bits.

In a birthday attack, what is the approximation for the probability p_c(n) of at least one collision after n random messages?

p_c(n) is approximately 1 - e^(-n(n-1)/2m)

How does the required number of messages n relate to the message space m for a reasonable collision probability?

n is proportional to sqrt(m)

If a message digest has b bits, how many different messages must be generated to reach a reasonable collision probability?

2^(b/2) different messages.

Why is a 128-bit message space (where m = 2^128) considered inconveniently vulnerable to collision attacks?

The required number of messages to find a collision is approximately 4 * 10^19.

Who developed the Message-Digest Algorithm 5 (MD5) and in what year?

Ron Rivest in 1991.

What is the bit-length of hash values produced by MD5?

128 bits.

What specific type of MD5 attack allows for two different executable files to share the same hash?

Chosen-prefix collision attack.

What is the hash length of SHA-0 and SHA-1?

160 bits.

Which organizations developed and approved the Secure Hash Algorithm (SHA) standards?

The NSA developed it and NIST approved it as a federal standard.

What are the two common bit-lengths provided by the SHA-2 family?

256 bits (SHA-256) and 512 bits (SHA-512).

In what year was the SHA-3 standard released?

2015.

What is the current security status of MD5 and SHA-1?

They are considered insecure and are primarily found in legacy applications.

Term: Iterated hash function

Definition: A function that extends a fixed-length compression function to handle inputs of arbitrary length using padding and chaining.

An iterated hash function inherits which property from its underlying compression function?

Collision resistance.

What are the three core components used in the construction of an iterated hash function?

Padding, initialization vector (IV), and a chain of compression functions.

Which two major hash algorithm families are examples of iterated hash functions?

MD5 and SHA.

In security concepts, which cryptographic tool is used to ensure confidentiality?

Encryption.

In security concepts, which two cryptographic tools ensure integrity and authentication?

Cryptographic checksums and digital signatures.

How does Alice sign a message m using RSA given her private key dA and modulus nA?

s is congruent to m^dA mod nA

How does Bob verify Alice's RSA signature s using her public key (eA, nA)?

m is congruent to s^eA mod nA

Why is RSA signing a message alone insufficient if the message content must remain secret?

Anyone can read and verify the message using Alice's public key.

When combining RSA signing and encryption, what size constraint is placed on the message m relative to the moduli nA and nB?

m < min(nA, nB)

In the RSA sign-then-encrypt process, if nA < nB, what is the first operation Alice performs?

Signing the message using her private key (s is congruent to m^dA mod nA).

In the RSA sign-then-encrypt process, what is the first operation Bob performs to reveal the message?

Decryption using his private key (s is congruent to c^dB mod nB).

What components make up an Elgamal public key?

The triplet (p, g, y).

In Elgamal signing, what mathematical property must the session random number k satisfy relative to phi_A?

It must be invertible modulo phiA (where phiA = p_A - 1).

In Elgamal signing, how is the first part of the signature, c, computed?

c is congruent to gA^k mod pA

In Elgamal signing, how is the second part of the signature, d, computed?

d is congruent to k^-1(m - xA * c) mod phiA

What is the verification test Bob uses for an Elgamal signed message (c, d)?

yA^c * c^d is congruent to gA^m mod p_A

What is the benefit of signing a message digest h(m) rather than the full message m?

It is more efficient than processing the entire plaintext, especially for long messages.

Term: Message Authentication Code (MAC)

Definition: A cryptographic hash function h(K, M) that takes both a secret key K and a message M as inputs.

What is required for both the sender and recipient to use a MAC for message integrity?

A shared secret key K.

How does a receiver verify the integrity of a message M using a received MAC c?

They recompute the MAC from the received message and compare it with the received c.

Why is an attacker unable to compute a correct MAC for a forged message?

The attacker does not possess the shared secret key K.

How does the efficiency of MACs compare to digital signatures?

MACs are generally more efficient because they are shorter and faster to compute.

When using 'MAC and encrypt', what pair is transmitted over the insecure channel?

The encrypted pair of (message, MAC).

The 'Sign and encrypt' method transmits which encrypted pair?

The encrypted pair of (message, signature).

In a hash function h, what is the property where finding Q such that h(P) = h(Q) is hard for a given P?

Second preimage resistance.

What numerical approximation for c is used in the birthday attack formula n is approximately c * sqrt(m) when seeking a 50% collision probability (p = 0.5)?

c is approximately 1.18

What numerical approximation for c is used in the birthday attack formula n is approximately c * sqrt(m) for a 90% collision probability (p = 0.9)?

c is approximately 2.15

According to the provided data, how does the hashing time of SHA-1 compare to MD5 as input size increases?

SHA-1 takes longer to compute than MD5 for the same input size.

In an iterated hash function, what is the role of the compression function?

It works on input values of a fixed length to produce a digest.

Alice wants to send a secret code to Bob. Which security concept is she addressing by using encryption?

Confidentiality.

To prove that Alice (and not Eve) sent a specific code, which security concept must be established?

Authentication.

In RSA, how is the private key dA derived from the public exponent eA and Euler's totient phi_A?

dA = eA^-1 mod phi_A

What is the result of applying s^eA mod nA to an RSA signature s?

The original message m.

In Elgamal, what value is kept secret as the private key x?

The exponent such that y is congruent to g^x mod p.

The approximation i/m = x is approx 0 which implies e^-x is approx 1 - x is used to derive what probability in cryptography?

The probability of at least one collision in a birthday attack.

For a 64-bit digest (m = 2^64), approximately how many messages n are needed for a 90% collision probability?

n is approximately 9.2 * 10^9

For a 512-bit digest (m = 2^512), approximately how many messages n are needed for a 90% collision probability?

n is approximately 2.5 * 10^77

Which hash algorithm was released in 2015 as the latest in the SHA family?

SHA-3.

MD5 attacks discovered by Stevens, Lenstra, and de Weger required how many hash evaluations to find a collision?

2^50 hash evaluations.

What property of hash functions is most critical for storing and checking passwords?

One-way (preimage resistance).

If Alice uses Bob's public key to encrypt a message, which security goal is she primarily achieving?

Confidentiality.

In the RSA signature verification m is congruent to s^eA mod nA, why can only Alice have created s?

Because only Alice knows the private key dA used to compute s is congruent to m^dA.

What is the transmitted data in a standard Elgamal signature?

The pair (c, d).

Is it possible to forge a digital signature if you only have access to the public key and the hash function?

No, because signing requires knowledge of the private key.

A cryptographic hash function maps a plaintext P to a value x. What is x formally called?

Digest.