Chapter 11 – Cryptographic

Cryptography and
Hash Functions
Network Security
Each of the messages, like each one he had ever
Chapter 11 read of Stern's commands, began with a number
and ended with a number or row of numbers. No
efforts on the part of Mungo or any of his experts
Fifth Edition had been able to break Stern's code, nor was
by William Stallings there any clue as to what the preliminary number
and those ultimate numbers signified.
Lecture slides by Lawrie Brown
—Talking to Strange Men, Ruth Rendell
(with edits by RHB)

Outline Hash Functions

• we consider: • condenses arbitrary message to a fixed size
• hash functions h = H(M)
— uses, requirements, security
• usually assume hash function is public
• hash functions based on block ciphers
• SHA-1, SHA-2, SHA-3 • hash used to detect changes to message
• want a cryptographic hash function such that
• computationally infeasible to find data that maps
to a specific hash (one-way property)
• computationally infeasible to find two different
data with same hash (collision-free property)
Cryptographic Hash Function

Hash
Functions &
Message
Authent-
ication

Hash Functions & Digital

Other Hash Function Uses
Signatures
• to create a one-way password file
• store hash of password, not actual password
• for intrusion detection and virus detection
• keep & check hashes of files on system
• pseudorandom function (PRF) or
pseudorandom number generator (PRNG)
 Two Simple Insecure Hash
Functions
• consider two simple insecure hash functions
• bit-by-bit exclusive-OR (XOR) of every block
• Ci = bi1 XOR bi2 XOR ... XOR bim
• a longitudinal redundancy check
• reasonably effective as data integrity check
• one-bit circular shift on hash value
• for each successive n-bit block
• rotate current hash value left by 1 bit and XOR block
• good for data integrity but useless for security

Hash Function Requirements Attacks on Hash Functions

• have brute-force attacks and cryptanalysis
• a preimage or second preimage attack
• find y s.t. H(y) equals a given hash value
• collision resistance
• find two messages x and y with same hash
H(x) = H(y)
• hence value 2m/2 determines strength of
hash code against brute-force attacks
• 128-bits inadequate, 160-bits suspect
 Birthday Attacks
• might think a 64-bit hash is secure
• but by Birthday Paradox is not
• birthday attack works thus:
• given user prepared to sign a valid message x
m
• opponent generates 2 /2 variations x’x’ of x, all with
essentially the same meaning, and saves them
m
• opponent generates 2 /2 variations y’y’ of a desired
fraudulent message y
• two sets of messages are compared to find pair with
same hash (probability > 0.5 by birthday paradox)
• have user sign the valid message, then substitute the
forgery which will have a valid signature
• conclusion is that need to use larger MAC/hash
 Hash Function Iterative
Structure
• hash functions use an iterative structure
• they process the message in blocks, with
suitable care about padding and length

• attacks focus on collisions in function f

Hash Function Cryptanalysis Block Ciphers as Hash Functions

• cryptanalytic attacks try to exploit some • a large number of hash functions exist
property of algorithm f • can use block ciphers as hash functions
• attempt to do it faster than exhaustive • using H0 = 0 and zero-pad of final block
search • compute: Hi = Emi(Hi-1)
• and use final block as the hash value
• similar to CBC but without a key
• resulting hash is small (64-bit) if use DES
• both due to direct birthday attack
• and to “meet-in-the-middle” attack
• other variants also susceptible to attack
 Secure Hash Algorithm Revised Secure Hash Standard
• SHA originally designed by NIST & NSA in 1993 • NIST issued revision FIPS 180-2 in 2002
• was revised in 1995 as SHA-1 • adds 3 additional versions of SHA
• US standard for use with DSA signature scheme • SHA-256, SHA-384, SHA-512
• standard is FIPS 180-
180-1 1995, also Internet RFC3174 • designed for compatibility with increased
• algorithm is SHA, the standard is SHS security provided by the AES cipher
• based on design of MD4 with key differences • structure and detail is similar to SHA-1
• produces 160-bit hash values • hence analysis should be similar
• 2005 results on security of SHA-1 have raised • but security levels are rather higher
concerns on its use in future applications
• these days use of SHA-1 is discouraged

SHA Versions SHA-512 Compression Function

• the heart of the algorithm
• it processes message in 1024-bit blocks
• it consists of 80 rounds per block
• updating a 512-bit buffer
• using a 64-bit value Wt derived from the
current message block
• and a round constant based on cube root of
first 80 prime numbers
SHA-512 Overview
Processing
one 1024
bit block

Hi Initial Values Ki
 SHA-512 Round Function SHA-512 Round Function
Bitw.
If-t-e

Bitw.
Maj
vote

XOR
of 3 XOR of 3
ROTR Addition ROTR/SHR Addition
mod 264 mod 264

SHA-3 SHA-3 Requirements

• In hashes, nothing secret, easier to attack • replace SHA-2 with SHA-3 in any use
• SHA-1 considered insecure these days • so use same hash sizes
• SHA-2 (esp. SHA-512) seems secure • preserve the online nature of SHA-2
• shares same structure and mathematical • so must process small blocks (512 / 1024 bits)
operations as predecessors so have concern • evaluation criteria
• NIST announced in 2007 a competition for • security close to theoretical max for hash sizes
the SHA-3 next gen NIST hash function • cost in time and memory
• goal was to have it in place by 2012 • characteristics: such as flexibility and simplicity