SHA New Revised Version - SHA-512 Syllabus Module 3

CS526 Topic 5: Hash Functions and
Message Authentication
1
Computer Security
CS 526
Topic 5
Cryptography: Cryptographic Hash
Functions And Message Authentication Code

Announcements
• HW1 due on Sept 5
• Quiz 1 will be on Sept 10, covering topics 1-5
• Both projects will be allow a team of two
– May want to start forming teams
• Mid-term exam tentatively scheduled to be Tuesday
Oct 15, during lecture time
2

3
Readings for This Lecture
• Wikipedia
• Cryptographic Hash Function
s
• Message Authentication Cod
e

4
Data Integrity and Source
Authentication
• Encryption does not protect data from modification
by another party.
• Why?
• Need a way to ensure that data arrives at destination
in its original form as sent by the sender and it is
coming from an authenticated source.

Hash Functions
• A hash function maps a message of an arbitrary length to
a m-bit output
– output known as the fingerprint or the message digest
• What is an example of hash functions?
– Give a hash function that maps Strings to integers in [0,2^{32}-1]
• Cryptographic hash functions are hash functions with
additional security requirements
5

6
Using Hash Functions for Message
Integrity
• Method 1: Uses a Hash Function h, assuming an
authentic (adversary cannot modify) channel for short
messages
– Transmit a message M over the normal (insecure) channel
– Transmit the message digest h(M) over the secure channel
– When receiver receives both M’ and h, how does the receiver
check to make sure the message has not been modified?
• This is insecure. How to attack it?
• A hash function is a many-to-one function, so collisions
can happen.

7
Security Requirements for
Cryptographic Hash Functions
Given a function h:X Y, then we say that h is:
• preimage resistant (one-way):
if given y Y it is computationally infeasible to find a
value x X s.t. h(x) = y
• 2-nd preimage resistant (weak collision resistant):
if given x  X it is computationally infeasible to find a
value x’  X, s.t. x’x and h(x’) = h(x)
• collision resistant (strong collision resistant):
if it is computationally infeasible to find two distinct
values x’,x  X, s.t. h(x’) = h(x)

8
Usages of Cryptographic Hash
Functions
• Software integrity
– E.g., tripwire
• Timestamping
– How to prove that you have discovered a secret on an
earlier date without disclosing it?
• Covered later
– Message authentication
– One-time passwords
– Digital signature

9
Bruteforce Attacks on Hash Functions
• Attacking one-wayness
– Goal: given h:XY, yY, find x such that h(x)=y
– Algorithm:
• pick a random value x in X, check if h(x)=y, if
h(x)=y, returns x; otherwise iterate
• after failing q iterations, return fail
– The average-case success probability is
– Let |Y|=2m
, to get  to be close to 0.5, q 2m-1
|
|
|
|
1
1
1
Y
q
Y
q






 




10
Bruteforce Attacks on Hash Functions
• Attacking collision resistance
– Goal: given h, find x, x’ such that h(x)=h(x’)
– Algorithm: pick a random set X0 of q values in X for
each xX0, computes yx=h(x) if yx=yx’ for some x’x
then return (x,x’) else fail
– The average success probability is
– Let |Y|=2m
, to get  to be close to 0.5, q 2m/2
– This is known as the birthday attack.
1
|
|
1
1
1 |
|
2
)
1
(
2
)
1
(
Y
q
q
q
q
e
Y
















11
Well Known Hash Functions
• MD5
– output 128 bits
– collision resistance completely broken by researchers in China in
2004
• SHA1
– output 160 bits
– no collision found yet, but method exist to find collisions in less than
2^80
– considered insecure for collision resistance
– one-wayness still holds
• SHA2 (SHA-224, SHA-256, SHA-384, SHA-512)
– outputs 224, 256, 384, and 512 bits, respectively
– No real security concerns yet

Merkle-Damgard Construction for
Hash Functions
12
• Message is divided into fixed-size blocks and padded
• Uses a compression function f, which takes a chaining variable (of
size of hash output) and a message block, and outputs the next
chaining variable
• Final chaining variable is the hash value
M=m1m2…mn; C0=IV, Ci+1=f(Ci,mi); H(M)=Cn

NIST SHA-3 Competition
• NIST is having an ongoing competition for SHA-3, the next generation of
standard hash algorithms
• 2007: Request for submissions of new hash functions
• 2008: Submissions deadline. Received 64 entries. Announced first-round
selections of 51 candidates.
• 2009: After First SHA-3 candidate conference in Feb, announced 14
Second Round Candidates in July.
• 2010: After one year public review of the algorithms, hold second SHA-3
candidate conference in Aug. Announced 5 Third-round candidates in Dec.
• 2011: Public comment for final round
• 2012: October 2, NIST selected SHA3
– Keccak (pronounced “catch-ack”) created by Guido Bertoni, Joan Daemen and Gilles Van
Assche, Michaël Peeters
13

The Sponge Construction: Used by
SHA-3
14
• Each round, the next r bits of message is XOR’ed into the first r bits of the
state, and a function f is applied to the state.
• After message is consumed, output r bits of each round as the hash
output; continue applying f to get new states
• SHA-3 uses 1600 bits for state size

15
Choosing the length of Hash outputs
• The Weakest Link Principle:
– A system is only as secure as its weakest link.
• Hence all links in a system should have similar levels of
security.
• Because of the birthday attack, the length of hash outputs
in general should double the key length of block ciphers
– SHA-224 matches the 112-bit strength of triple-DES (encryption
3 times using DES)
– SHA-256, SHA-384, SHA-512 match the new key lengths
(128,192,256) in AES

16
Limitation of Using Hash Functions
for Authentication
• Require an authentic channel to transmit the
hash of a message
– Without such a channel, it is insecure, because
anyone can compute the hash value of any message,
as the hash function is public
– Such a channel may not always exist
• How to address this?
– use more than one hash functions
– use a key to select which one to use

17
Hash Family
• A hash family is a four-tuple (X,Y,K,H ), where
– X is a set of possible messages
– Y is a finite set of possible message digests
– K is the keyspace
– For each KK, there is a hash function hKH . Each
hK: X Y
• Alternatively, one can think of H as a function
KXY

18
Message Authentication Code
• A MAC scheme is a hash family, used for
message authentication
• MAC(K,M) = HK(M)
• The sender and the receiver share secret K
• The sender sends (M, Hk(M))
• The receiver receives (X,Y) and verifies that
HK(X)=Y, if so, then accepts the message as from
the sender
• To be secure, an adversary shouldn’t be able to
come up with (X’,Y’) such that HK(X’)=Y’.

Security Requirements for MAC
• Resist the Existential Forgery under Chosen Plaintext
Attack
– Challenger chooses a random key K
– Adversary chooses a number of messages M1, M2, .., Mn, and
obtains tj=MAC(K,Mj) for 1jn
– Adversary outputs M’ and t’
– Adversary wins if j M’≠Mj, and t’=MAC(K,M’)
• Basically, adversary cannot create the MAC for a
message for which it hasn’t seen an MAC
19

Constructing MAC from Hash
Functions
• Let h be a one-way hash function
• MAC(K,M) = h(K || M), where || denote
concatenation
– Insecure as MAC
– Because of the Merkle-Damgard construction for hash
functions, given M and t=h(K || M), adversary can
compute M’=M||Pad(M)||X and t’, such that h(K||M’) =
t’
20

21
HMAC: Constructing MAC from
Cryptographic Hash Functions
• K+
is the key padded (with 0) to B bytes, the
input block size of the hash function
• ipad = the byte 0x36 repeated B times
• opad = the byte 0x5C repeated B times.
HMACK[M] = Hash[(K+
 opad) || Hash[(K+
 ipad)||M)]]
At high level, HMACK[M] = H(K || H(K || M))

22
HMAC Security
• If used with a secure hash functions (e.g.,
SHA-256) and according to the specification
(key size, and use correct output), no known
practical attacks against HMAC

23
Coming Attractions …
• Cryptography: Public Key
Cryptography

SHA New Revised Version - SHA-512 Syllabus Module 3

Recommended

More Related Content

Similar to SHA New Revised Version - SHA-512 Syllabus Module 3 (20)

Recently uploaded (20)

SHA New Revised Version - SHA-512 Syllabus Module 3

Editor's Notes