Hash Functions in Computer Science

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

What is the main objective of a hash function?

Error detection

Data integrity (correct)

Data compression

Data encryption

What is the characteristic of a cryptographic hash function that makes it infeasible to find a value x given a value y?

Compression

One-way (correct)

Weak collision resistance

Strong collision resistance

What is the requirement for a hash function to be considered efficient?

It must be computationally expensive

It must be easy to compute (correct)

It must be difficult to compute

It must be computationally infeasible

Why do many collisions exist in a hash function?

Because the input space is larger than the output space Signup and view all the answers

What is the property of a hash function that ensures it is infeasible to find two different inputs with the same output?

Strong collision resistance Signup and view all the answers

What is the term used to describe the output of a hash function?

Message digest Signup and view all the answers

How many types of hash functions are mentioned in the text?

Two Signup and view all the answers

What is the term used to describe a hash function that combines message-passing capabilities with security properties?

Cryptographic hash function Signup and view all the answers

What is the main difference between a CRC calculation and ordinary long division?

XOR is used in place of subtraction Signup and view all the answers

What is the main limitation of using CRC checksums?

They are only designed to detect transmission errors Signup and view all the answers

What is the main advantage of the Tiger hash algorithm?

It is a little easier to digest than some other hashes Signup and view all the answers

What was, until recently, the most popular hash algorithm?

MD5 Signup and view all the answers

What is the main difference between a cryptographic hash and a non-cryptographic hash?

A non-cryptographic hash is only used for error detection Signup and view all the answers

What is the purpose of appending zeros to the data in a CRC calculation?

To match the number of bits in the divisor Signup and view all the answers

What is the main weakness of using a CRC checksum for data integrity?

An intelligent adversary can easily change the data without detection Signup and view all the answers

What is SHA-1?

A type of cryptographic hash algorithm Signup and view all the answers

What is a primary purpose of hash functions in security?

To verify the integrity of a message Signup and view all the answers

What happens when a single bit of the original message M is changed to create a new message M'?

The hash values will almost certainly differ Signup and view all the answers

What is the purpose of Alice computing S = [h(M)] in the digital signature process?

To sign the hash value of the message Signup and view all the answers

What is a potential attack that Trudy can conduct on Alice's digital signature?

Birthday attack Signup and view all the answers

What is the definition of a collision-resistant hash function?

A hash function that is hard to find two inputs with the same output Signup and view all the answers

What is the benefit of using a digital signature instead of a MAC?

Digital signatures have lower overhead in terms of data transmission Signup and view all the answers

What is the primary property of a hash function that makes it useful in digital signatures?

It is collision-resistant Signup and view all the answers

What is the role of the hash function h in the digital signature process?

To create a 'fingerprint' of the message Signup and view all the answers

Study Notes

Hash Functions

A hash function is a mathematical function that converts a numerical input value into another compressed numerical value.
It accepts a variable-length block of data M as input and produces a fixed-size hash value h = H(M).
The principal object of a hash function is data integrity.
A change to any bit or bits in M results, with high probability, in a change to the hash value.

Types of Hash Functions

There are two types of hash functions:
- Cryptographic Hash Function
- Non-Cryptographic Hashes

Cryptographic Hash Function

A cryptographic hash function combines the message-passing capabilities of hash functions with security properties.
It must provide all of the following:
- Compression: the output length of y = h(x) is small and fixed.
- Efficiency: it must be easy to compute h(x) for any input x.
- One-way: it's computationally infeasible to find a value x such that h(x) = y.
- Weak collision resistance: it's infeasible to find any y, with y ≠ x, such that h(y) = h(x).
- Strong collision resistance: it's infeasible to find any x and y, such that x ≠ y and h(x) = h(y).

Properties of Cryptographic Hash Functions

Many collisions must exist since the input space is much larger than the output space.
Collision resistance properties say that all of these collisions are computationally hard to find.
Hash functions are extremely useful in security.
They are used to verify the message integrity only.
h(M) can be viewed as a "fingerprint" of the file M, that is, h(M) is much smaller than M but it identifies M.

Digital Signatures

The correct way to sign is:
- Alice has a cryptographic hash function h.
- Alice will sign M by first hashing M then signing the hash.
- Alice can send Bob M and S.
- Bob verifies the signature by hashing M and comparing the result to the value obtained when Alice's public key is applied to S.

Birthday Attack

The birthday paradox or birthday problem considers the probability that some paired people in a set of n randomly chosen of them, will have the same birthday.
Trudy (attacker) can conduct a birthday attack as follows:
- Trudy selects an "evil" message E that she wants Alice to sign, but which Alice is unwilling to sign.
- Trudy also creates an innocent message I that she is confident Alice is willing to sign.

Non-Cryptographic Hashes

An example of a non-cryptographic hash is the cyclic redundancy check (CRC).
The CRC calculation is essentially long division, with the remainder acting as the CRC "hash" value.
In contrast to ordinary long division, in a CRC, we use XOR in place of subtraction.
CRCs and similar checksum methods are only designed to detect transmission errors—not to detect intentional tampering with the data.

Tiger Hash

Tiger is a specific cryptographic hash algorithm.
It is not a particularly popular hash, but it is a little easier to digest than some of the big-name hashes.

Other Hash Functions

Until recently, the most popular hash in the world was MD5 (message digest).
The other contender for title of world's most popular hash function is SHA-1 (Secure Hash Algorithm) which is a U.S. government standard.

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Description

Learn about hash functions, their properties, and their role in data integrity. Explore how they compress input data into a fixed-size hash value.