Hash: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
A Hash function takes a variable-length string as an input, returns a fixed-size output and is efficient. | A Hash function takes a variable-length string as an input, returns a fixed-size output and is efficient. | ||
=== Definition === | |||
==== Narayanan definition ==== | |||
A hash function H is cryptographically secure if: | A hash function H is cryptographically secure if: | ||
* is collision-free: for all x, y, H(x) = H(y) => x = y | * is collision-free: for all x, y, H(x) = H(y) => x = y | ||
| Line 9: | Line 12: | ||
* is puzzle-friendly: for every output y, if k is chosen from a probability distribution with high min-entropy, it is infeasible to find x such H(k | x) = y | * is puzzle-friendly: for every output y, if k is chosen from a probability distribution with high min-entropy, it is infeasible to find x such H(k | x) = y | ||
** this means there no solving strategy better than trying random value to find it. | ** this means there no solving strategy better than trying random value to find it. | ||
==== Traditional definition ==== | |||
A hash function H is cryptographically secure if: | |||
* collision-resistant: hard to find x, y, x != y, such H(x) = H(y) | |||
* Pre-image resistant: given h, hard to find x such that H(x) = h | |||
* Second pre-image resistant: given x, hard to find y, y != x such that H(x) = H(y) | |||
=== SHA-256 === | |||
breaks the message into 512-bits blocks with some padding in the last block that contains 64-bit length field (length message in bit), 1 bit and some number of 0 bits. | breaks the message into 512-bits blocks with some padding in the last block that contains 64-bit length field (length message in bit), 1 bit and some number of 0 bits. | ||
The initial input IV is 256-bit. Given c a hash function, SHA-256=c(block n, c(block n-1, c(block n-2, ..., c(block 0, IV)))). | The initial input IV is 256-bit. Given c a hash function, SHA-256=c(block n, c(block n-1, c(block n-2, ..., c(block 0, IV)))). | ||
Theorem: if c is collision-free, then SHA-256 is collision-free. | '''Theorem:''' if c is collision-free, then SHA-256 is collision-free. | ||
SHA-256 is a SHA-2 algorithm which is not resistant to the length-extension attack. | |||
=== SHA-3 === | |||
SHA-3 is resistant to the length-extension attack. | |||
=== Password hash === | |||
Use Argon2. | |||
Latest revision as of 06:01, 12 May 2026
A Hash function takes a variable-length string as an input, returns a fixed-size output and is efficient.
Definition
Narayanan definition
A hash function H is cryptographically secure if:
- is collision-free: for all x, y, H(x) = H(y) => x = y
- but collisions do exist because the output has a fixed size whereas the input size is not
- has a hiding property:
- Given H(x), it is infeasible to find x, it is easy to find x if x does not take many different values
- better definition: If r is chosen from a probability distribution with high min-entropy, given H(r | x), it is infeasible to find x
- is puzzle-friendly: for every output y, if k is chosen from a probability distribution with high min-entropy, it is infeasible to find x such H(k | x) = y
- this means there no solving strategy better than trying random value to find it.
Traditional definition
A hash function H is cryptographically secure if:
- collision-resistant: hard to find x, y, x != y, such H(x) = H(y)
- Pre-image resistant: given h, hard to find x such that H(x) = h
- Second pre-image resistant: given x, hard to find y, y != x such that H(x) = H(y)
SHA-256
breaks the message into 512-bits blocks with some padding in the last block that contains 64-bit length field (length message in bit), 1 bit and some number of 0 bits.
The initial input IV is 256-bit. Given c a hash function, SHA-256=c(block n, c(block n-1, c(block n-2, ..., c(block 0, IV)))).
Theorem: if c is collision-free, then SHA-256 is collision-free.
SHA-256 is a SHA-2 algorithm which is not resistant to the length-extension attack.
SHA-3
SHA-3 is resistant to the length-extension attack.
Password hash
Use Argon2.