24 Questions
What is the main objective of a hash function?
Data integrity
What is the characteristic of a cryptographic hash function that makes it infeasible to find a value x given a value y?
One-way
What is the requirement for a hash function to be considered efficient?
It must be easy to compute
Why do many collisions exist in a hash function?
Because the input space is larger than the output space
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
What is the term used to describe the output of a hash function?
Message digest
How many types of hash functions are mentioned in the text?
Two
What is the term used to describe a hash function that combines message-passing capabilities with security properties?
Cryptographic hash function
What is the main difference between a CRC calculation and ordinary long division?
XOR is used in place of subtraction
What is the main limitation of using CRC checksums?
They are only designed to detect transmission errors
What is the main advantage of the Tiger hash algorithm?
It is a little easier to digest than some other hashes
What was, until recently, the most popular hash algorithm?
MD5
What is the main difference between a cryptographic hash and a non-cryptographic hash?
A non-cryptographic hash is only used for error detection
What is the purpose of appending zeros to the data in a CRC calculation?
To match the number of bits in the divisor
What is the main weakness of using a CRC checksum for data integrity?
An intelligent adversary can easily change the data without detection
What is SHA-1?
A type of cryptographic hash algorithm
What is a primary purpose of hash functions in security?
To verify the integrity of a message
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
What is the purpose of Alice computing S = [h(M)] in the digital signature process?
To sign the hash value of the message
What is a potential attack that Trudy can conduct on Alice's digital signature?
Birthday attack
What is the definition of a collision-resistant hash function?
A hash function that is hard to find two inputs with the same output
What is the benefit of using a digital signature instead of a MAC?
Digital signatures have lower overhead in terms of data transmission
What is the primary property of a hash function that makes it useful in digital signatures?
It is collision-resistant
What is the role of the hash function h in the digital signature process?
To create a 'fingerprint' of the message
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.
Learn about hash functions, their properties, and their role in data integrity. Explore how they compress input data into a fixed-size hash value.
Make Your Own Quizzes and Flashcards
Convert your notes into interactive study material.
Get started for free
