English
Menu

What is Hash function?

A function that computes a value of fixed length (a hash value) from data of any length. Those used in cryptography, such as SHA-256, are built so that it is practically impossible either to find the original data from a hash value or to find two pieces of data with the same hash value, and they are used for detecting tampering, digital signatures and password storage.

Japanese name: ハッシュ関数

Hash function appears in 7 practice questions across 2 topics, including Information Security Basics, Data Structures and Algorithms.

Field: Information Security Basics

Properties required of cryptographic hash functions

Hash functions used in cryptography must have three properties. Preimage resistance (one-wayness) means it is hard to find an input that produces a given hash value. Second-preimage resistance means that, given one input, it is hard to find a different input with the same hash value. Collision resistance means it is hard to find any two different inputs with the same hash value. They also have the property that changing a single bit of the input changes roughly half the bits of the output (the avalanche effect).

Output length and security

For an ideal hash function with an n-bit output, finding a preimage by brute force takes about 2^n computations, but thanks to the birthday paradox a collision becomes likely after about 2^(n/2). SHA-256 is therefore considered to have about 128-bit strength against collisions. For MD5 and SHA-1, methods have been found that create collisions with far fewer computations than brute force, so they are not to be used where security is required, such as in digital signatures.

Main uses

A hash value can serve as a "fingerprint" of data. Comparing the hash of a downloaded file with the officially published value shows whether it is corrupted or has been swapped (provided the official value itself was obtained through a trustworthy channel). In digital signatures, the hash value of a long document is signed instead of the document itself. For password storage, a salt is added and deliberately expensive schemes such as bcrypt or Argon2 are used. HMAC, which combines a hash with a key, is used as a message authentication code to detect tampering.

Try it: questions about Hash function

For an ideal hash function with a 256-bit output, which combination gives the approximate number of computations needed for a brute-force attack in two cases: finding an input that produces a given hash value (a preimage attack), and finding any two different inputs that produce the same hash value (a collision attack)?

  1. APreimage attack: about 2^256; collision attack: about 2^128
  2. BPreimage attack: about 2^128; collision attack: about 2^256
  3. CAbout 2^256 for both the preimage attack and the collision attack
Show answer and explanation

Answer: A. Preimage attack: about 2^256; collision attack: about 2^128

An ideal hash function with an n-bit output has 2^n possible hash values, and each input tried matches a given hash value with probability 1/2^n. A preimage attack therefore needs about 2^n computations, which for n = 256 is about 2^256. In a collision attack, however, any two inputs may match, so trying k inputs gives about k^2/2 pairs to compare. Once k^2/2 approaches 2^n, that is, when k is around 2^(n/2), a collision becomes likely; for n = 256 that is about 2^128. This is the same idea as the birthday paradox, in which a group of 23 people has a better than 50% chance that two share a birthday, so it is called a birthday attack. Consequently, a hash function's strength against collisions is estimated at half its output length, and achieving 128-bit strength requires a 256-bit output.

For storing passwords, it is recommended not to use a fast hash function such as SHA-256 directly but a scheme deliberately designed to take time to compute, such as bcrypt or Argon2. Why?

  1. ASlow schemes have longer outputs, so collisions no longer occur
  2. BSpending time on the computation lets only legitimate users recover the original password from the hash value
  3. CIf the stored hash values are leaked, each guess an attacker tries also becomes expensive, greatly increasing the time needed for brute-force and dictionary attacks
Show answer and explanation

Answer: C. If the stored hash values are leaked, each guess an attacker tries also becomes expensive, greatly increasing the time needed for brute-force and dictionary attacks

If password hashes are leaked, attackers can hash candidate passwords one after another on their own computers and look for a match. General-purpose hash functions such as SHA-256 are built to process large amounts of data quickly, so with GPUs and similar hardware an enormous number of candidates can be tried per second. Schemes designed for password storage, such as bcrypt and Argon2, have an adjustable number of iterations (cost) and deliberately make each computation heavy. Making each computation a million times slower, for example, makes a brute-force search take a million times longer as well. A legitimate user logging in needs only one computation, so a delay of around 0.1 seconds is not a problem. Argon2 can also be configured to use a lot of memory, which makes massively parallel computation on GPUs or dedicated circuits difficult. Whichever scheme is used, it is combined with a per-user salt.

FAQ

What is the difference between a hash function and encryption?

Encryption is a transformation that uses a key and can be reversed (decrypted), whereas a hash function uses no key and is a one-way computation that cannot be reversed. Hash values are therefore used not to keep secrets but to check whether data is the same.

How many bits is a SHA-256 hash value?

256 bits (64 hexadecimal characters), regardless of the input length. A one-character input and a large file both give a value of the same length.

Hash function in the explanations

Questions that mention Hash function (7)

  1. For an ideal hash function with a 256-bit output, which combination gives the approximate number of computations needed for a brute-force attack in two cases: finding an input that produces a given hash value (a preimage attack), and finding any two different inputs that produce the same hash value (a collision attack)?
  2. For storing passwords, it is recommended not to use a fast hash function such as SHA-256 directly but a scheme deliberately designed to take time to compute, such as bcrypt or Argon2. Why?
  3. Keys 10, 17, 24 and 3 are stored in this order in a hash table of size 7 (positions 0 to 6) with the hash function h(k) = k mod 7. Collisions are resolved by linear probing, which moves forward one position at a time (wrapping from 6 to 0) to find a free slot. At which position is key 3 stored?
  4. Which statement correctly describes a property of hash functions used in cryptography (cryptographic hash functions)?
  5. When a web service stores users' passwords, it adds a random value that differs for each user (a salt) to the password before computing and storing the hash value. What is the main purpose of the salt?
  6. Which statement correctly compares a message authentication code (MAC) with a digital signature?
  7. Which is the correct description of a collision in a hash table?

Books on Information Security Basics Ad

As an Amazon Associate I earn from qualifying purchases.

Semiconductor, Electronics and Computing Calculators

Password Brute-Force Time CalculatorCompute the number of combinations and the entropy from the character set and length, and estimate brute-force time

Related terms

Salt Hash table Modulo operation Message authentication code Digital signature Cross-site scripting (XSS) Multi-factor authentication Phishing Principle of least privilege Public-key cryptography

Back to the glossary