Practical Cryptography for Developers
  • Welcome
  • Preface
  • Cryptography - Overview
  • Hash Functions
    • Crypto Hashes and Collisions
    • Hash Functions: Applications
    • Secure Hash Algorithms
    • Hash Functions - Examples
    • Exercises: Calculate Hashes
    • Proof-of-Work Hash Functions
  • MAC and Key Derivation
    • HMAC and Key Derivation
    • HMAC Calculation - Examples
    • Exercises: Calculate HMAC
    • KDF: Deriving Key from Password
    • PBKDF2
    • Modern Key Derivation Functions
    • Scrypt
    • Bcrypt
    • Linux crypt()
    • Argon2
    • Secure Password Storage
    • Exercises: Password Encryption
  • Secure Random Generators
    • Pseudo-Random Numbers - Examples
    • Secure Random Generators (CSPRNG)
    • Exercises: Pseudo-Random Generator
  • Key Exchange and DHKE
    • Diffie–Hellman Key Exchange
    • DHKE - Examples
    • Exercises: DHKE Key Exchange
  • Encryption: Symmetric and Asymmetric
  • Symmetric Key Ciphers
    • Cipher Block Modes
    • Popular Symmetric Algorithms
    • The AES Cipher - Concepts
    • AES Encrypt / Decrypt - Examples
    • Ethereum Wallet Encryption
    • Exercises: AES Encrypt / Decrypt
    • ChaCha20-Poly1305
    • Exercises: ChaCha20-Poly1305
  • Asymmetric Key Ciphers
    • The RSA Cryptosystem - Concepts
    • RSA Encrypt / Decrypt - Examples
    • Exercises: RSA Encrypt / Decrypt
    • Elliptic Curve Cryptography (ECC)
    • ECDH Key Exchange
    • ECDH Key Exchange - Examples
    • Exercises: ECDH Key Exchange
    • ECC Encryption / Decryption
    • ECIES Hybrid Encryption Scheme
    • ECIES Encryption - Example
    • Exercises: ECIES Encrypt / Decrypt
  • Digital Signatures
    • RSA Signatures
    • RSA: Sign / Verify - Examples
    • Exercises: RSA Sign and Verify
    • ECDSA: Elliptic Curve Signatures
    • ECDSA: Sign / Verify - Examples
    • Exercises: ECDSA Sign and Verify
    • EdDSA and Ed25519
    • EdDSA: Sign / Verify - Examples
    • Exercises: EdDSA Sign and Verify
  • Quantum-Safe Cryptography
    • Quantum-Safe Signatures - Example
    • Quantum-Safe Key Exchange - Example
    • Quantum-Safe Asymmetric Encryption - Example
  • More Cryptographic Concepts
    • Digital Certificates - Example
    • TLS - Example
    • One-Time Passwords (OTP) - Example
  • Crypto Libraries for Developers
    • JavaScript Crypto Libraries
    • Python Crypto Libraries
    • C# Crypto Libraries
    • Java Crypto Libraries
  • Conclusion
Powered by GitBook
On this page
  • Hash Collisions
  • Cryptographic Hash Functions: No Collisions

Was this helpful?

  1. Hash Functions

Crypto Hashes and Collisions

PreviousHash FunctionsNextHash Functions: Applications

Last updated 5 years ago

Was this helpful?

Different input messages are expected to produce different output hash values (message digest).

Hash Collisions

A collision means the same hash value for two different inputs. For simple hash functions it is easy to reach a collision. For example, assume a hash function h(text) sums of all character codes in a text. It will produce the same hash value (collision) for texts holding the same letters in different order, i.e. h('abc') == h('cab') == h('bca'). To avoid collisions, cryptographers have designed collision-resistant hash functions.

Cryptographic Hash Functions: No Collisions

Collisions in the cryptographic hash functions are extremely unlikely to be found, so crypto hashes are considered to almost uniquely identify their corresponding input. Moreover, it is extremely hard to find an input message that hashes to given value.

Cryptographic hash functions are one-way hash functions, which are infeasible to invert. The chance to find a collision (by brute force) for a strong cryptographic hash function (like SHA-256) is extremely little. Let's define this in more details:

  • Let's have hash value h=hash(p) for certain strong cryptographic hash function hash.

  • It is expected to be extremely hard to find an input p', such that hash(p')=h.

  • For most modern strong cryptographic hash functions there are no known collisions.

The ideal cryptographic hash function should have the following properties:

  • Deterministic: the same input message should always result in the same hash value.

  • Quick: it should be fast to compute the hash value for any given message.

  • Hard to analyze: a small change to the input message should totally change the output hash value.

  • Irreversible: generating a valid input message from its hash value should be infeasible. This means that there should be no significantly better way than brute force (try all possible input messages).

  • No collisions: it should be extremely hard (or practically impossible) to find two different messages with the same hash.

Modern cryptographic hash functions (like SHA2 and SHA3) match the above properties and are used widely in cryptography.