5.2 Secure hash algorithms (SHA)

Secure Hash Algorithms (SHA) are a family of cryptographic hash functions developed to provide data integrity and security. They've evolved over time, with each new version addressing vulnerabilities in previous iterations and offering stronger protection against emerging threats.

SHA functions play a crucial role in modern cryptography, used in digital signatures, message authentication, and password hashing. Understanding their design principles, implementation considerations, and security properties is essential for anyone working with cryptographic systems or developing secure applications.

Evolution of SHA Hash Functions

Development and Standardization

Top images from around the web for Development and Standardization

• 

  Cryptographic hash function - Wikipedia View original

  Is this image relevant?

• 

  Cryptographic hash function - Wikipedia View original

  Is this image relevant?

1 of 1

Top images from around the web for Development and Standardization

• 

  Cryptographic hash function - Wikipedia View original

  Is this image relevant?

• 

  Cryptographic hash function - Wikipedia View original

  Is this image relevant?

1 of 1

• Secure Hash Algorithm (SHA) family developed by National Security Agency (NSA) and standardized by National Institute of Standards and Technology (NIST)
• Provides secure cryptographic hash functions for various applications (digital signatures, message authentication codes)
• SHA-0 introduced in 1993 but quickly withdrawn due to undisclosed significant flaw in compression function

Progression of SHA Variants

• SHA-1 introduced in 1995 produces 160-bit hash value
  • Widely used until vulnerabilities discovered
  • Deprecated for cryptographic purposes due to collision attacks
• SHA-2 introduced in 2001 addresses weaknesses of SHA-1
  • Set of hash functions including SHA-224, SHA-256, SHA-384, and SHA-512
  • Provides stronger security with larger hash sizes (224 to 512 bits)
• SHA-3 selected through public competition in 2012 and standardized in 2015
  • Based on Keccak algorithm
  • Provides alternative to SHA-2 family with different internal structure
  • Designed to be resistant to attacks effective against SHA-2

Ongoing Security Improvements

• Evolution of SHA algorithms demonstrates continuous effort to enhance security
• Addresses emerging cryptographic attacks and computational advancements
• Each new variant incorporates lessons learned from predecessors
• Adapts to increasing computational power and cryptanalytic techniques

SHA Algorithm Design Principles

Merkle-Damgård Construction

• Fundamental design principle used in SHA-1 and SHA-2
• Involves iteratively applying compression function to process message blocks
• Maintains internal state throughout hash computation
• Message padded and split into fixed-size blocks (512 or 1024 bits)
• Blocks processed sequentially with output of each stage becoming input for next
• SHA-1 and SHA-2 use different word sizes and number of rounds in compression functions
  • SHA-1: 80 rounds with 32-bit words
  • SHA-256: 64 rounds with 32-bit words
  • SHA-512: 80 rounds with 64-bit words
• SHA-2 incorporates additional security features (more complex message schedule, additional constants)

Sponge Construction

• Used in SHA-3 (Keccak), fundamentally different from Merkle-Damgård construction
• Consists of two phases: absorbing phase and squeezing phase
• State divided into two parts: rate (r) and capacity (c)
  • Rate determines input/output block size
  • Capacity provides security (larger capacity increases resistance to attacks)
• Absorbing phase processes input data blocks
  • XORs data blocks with rate part of state
  • Applies permutation function (Keccak-f)
• Squeezing phase extracts output blocks from rate part of state
  • Applies permutation function between extractions if necessary
• Offers flexibility in input and output sizes

Security Implications

• Understanding these constructions crucial for analyzing security properties
• Merkle-Damgård construction vulnerable to length extension attacks
  • Attacker can append additional data to a message with known hash
• Sponge construction resistant to length extension attacks
  • Internal state not fully revealed in output
• Different constructions provide varying levels of resistance to other cryptographic attacks (collision, preimage)

Implementing SHA Algorithms

Implementation Considerations

• Careful attention required for bitwise operations, endianness, and padding rules
• Proper handling of message padding crucial for consistent results
• Side-channel attack resistance important, especially for hardware implementations
• Verification against known test vectors essential to ensure correctness

SHA-1 and SHA-2 Implementation

• Initialize state vector with predefined constants
• Process message blocks through multiple rounds of bitwise operations
  • Operations include rotations, shifts, and modular additions
• Produce final hash value by concatenating resulting state
• Example of SHA-256 round function:

  Ch(x,y,z) = (x & y) ^ (~x & z)
  Maj(x,y,z) = (x & y) ^ (x & z) ^ (y & z)
  Σ0(x) = ROTR2(x) ^ ROTR13(x) ^ ROTR22(x)
  Σ1(x) = ROTR6(x) ^ ROTR11(x) ^ ROTR25(x)
  

SHA-3 Implementation

• Initialize state matrix (5x5 array of 64-bit words for SHA3-256)
• Apply Keccak-f permutation function in rounds
• Extract desired output length from final state
• Example of Keccak-f round operations:

  θ (theta): XOR each bit with the parity of two columns
  ρ (rho): Rotate bits of each lane by a specific offset
  π (pi): Rearrange the positions of the lanes
  χ (chi): XOR each bit with a non-linear function of two other bits
  ι (iota): XOR the first lane with a round constant
  

Using Cryptographic Libraries

• Optimized implementations of SHA algorithms provided by cryptographic libraries and APIs
• Preferred over custom implementations for security-critical applications
• Examples of popular libraries:
  • OpenSSL (C/C++)
  • Bouncy Castle (Java)
  • PyCryptodome (Python)

Security and Performance of SHA Variants

Security Properties

• Collision resistance prevents finding two different inputs with same hash output
• Preimage resistance ensures difficulty of finding input given its hash output
• Second preimage resistance prevents finding different input with same hash as given input
• SHA-1 considered cryptographically broken due to demonstrated collision attacks
  • Unsuitable for digital signatures and security-critical applications
• SHA-2 family provides stronger security than SHA-1
  • No practical attacks known against full versions
  • Reduced-round variants analyzed for weaknesses
• SHA-3 designed to resist attacks effective against SHA-2
  • Provides security margin against future cryptanalytic advances

Performance Characteristics

• SHA-2 generally faster in software implementations
  • Optimized for 32-bit and 64-bit architectures
• SHA-3 may have advantages in hardware implementations
  • Simpler structure allows for efficient hardware designs
• Performance varies based on specific variant and implementation
  • SHA-256 often faster than SHA3-256 in software
  • SHA-512 can outperform SHA-256 on 64-bit platforms

Resistance to Attacks

• Length extension attacks applicable to SHA-1 and SHA-2 due to Merkle-Damgård construction
  • Attacker can append data to message with known hash without knowing original message
• SHA-3's sponge construction resistant to length extension attacks
• Larger output sizes generally provide better resistance to quantum computing attacks
  • SHA-512 and SHA3-512 offer stronger post-quantum security than shorter variants

Choosing Appropriate SHA Variants

• Consider security requirements of specific application
• Balance between security level and performance needs
• SHA-256 and SHA3-256 suitable for most current applications
• SHA-512 or SHA3-512 recommended for long-term security or high-value assets
• Regular review and updates necessary as cryptographic landscape evolves