Checksum

Cryptographic Hash Function (CHF)

• Hash function: binary ⇒ binary with fixed size
• Although not necessary, They all have time complexity of O(N)
• It is expected to have a collision resistance strength of $n/2$ bits, due to Birthday Paradox
• Uses:
  • Digital Signatures
  • Authentication
  • Checksums
  • Message Digests (example HMAC)
• MD5 and SHA-1 should be avoided to build critical (like password) systems
• Examples
  • MD5
  • SHA-1

MD5

• Message Digest Algorithm
• Created in 1992
• Broken in 2004
• Designed by Robert Rivest
• Output: 16 bytes

# Linux
md5sum <file>
 
# MacOS
md5 <file>

SHA

• Secure Hash Algorithm
• SHA-1
  • Created in 1995
  • Broken in 2005
  • Output: 20 bytes
• SHA-2
  • SHA-256
    • Created in 2001
    • Output: 32 bytes (256 bits)
  • SHA-512
    • Created in 2001
    • Output: 64 bytes (512 bits)
• SHA-3
  • Created in 2013

# Linux
shasum <file>
sha256sum <file>
sha512sum <file>
 
# MacOS
shasum <file>
shasum -256 <file>
shasum -512 <file>

Comparison

• https://en.wikipedia.org/wiki/Secure_Hash_Algorithms
• https://cryptography.fandom.com/wiki/SHA-1#Comparison_of_SHA_functions
• https://crypto.stackexchange.com/questions/68307/what-is-the-difference-between-sha-3-and-sha-256

Algo	Output Size (bytes)	Rounds	Collision Resistance (in bits)	First Published	Broken
MD5	16	4	64	1992	2004
SHA-1	20	80	80	1995	2005
SHA-256 (SHA-2)	32	64	128	2001	-
SHA-512 (SHA-2)	64	80	256	2001	-

Security

• Basic security can be calculated using the following:
  • Pre-image resistance
    • Given value $v$ , difficult to find $m$ such that $v=h(m)$
    • Given final hash value, find input message
  • Second pre-image resistance (aka Weak Collision resistance)
    • Given message $m_1$ , difficult to find $m_2$ such that $h(m_1)=h(m_2)$
    • Given input message, find another input message with same hash value
  • Collision resistance
    • Nothing given, we need to find $m_1$ and $m_2$ such that $h(m_1)=h(m_2)$
    • find arbitrarily two messages with same hash value
    • Birthday Paradox puts upper bound to collision resistance
    • Automatically implies weak collision resistance but not pre-image resistance
• A primitive offers $k$ bits of security if the best known attack against that primitive takes roughly $2^k$ operations
• Theoretically MD5 and SHA-1 should be collision resistant but they were still broken using various techniques
• https://crypto.stackexchange.com/questions/86971/bits-of-security-vs-collision-resistance

Birthday Paradox

• In a set of $n$ randomly chosen people, at least two will share same birthday
• Surprisingly, only 23 people are needed for that probability to exceed 50%
• For hash function which outputs $n$ bits, its security for collision resistance is $n/2$ because of Birthday Paradox
  • which means $2^{n/2}$ operations are required to find collision