CS计算机代考程序代写 algorithm CM30173: CryptographyPart III

CM30173: CryptographyPart III

CM30173:

Cryptography

Part III

Recall

Using unkeyed hash

functions

Motivation for security

requirements

Constructing an

Unkeyed Hash

Function

A family of hash

functions

MD5

SHA-1

Recall

Using unkeyed hash functions

Constructing an Unkeyed Hash Function

A family of hash functions

MD5

SHA-1

Part III

Cryptographic hashes

CM30173: CryptographyPart III

CM30173:

Cryptography

Part III

Recall

Using unkeyed hash

functions

Motivation for security

requirements

Constructing an

Unkeyed Hash

Function

A family of hash

functions

MD5

SHA-1

Recall

Using unkeyed hash functions

Constructing an Unkeyed Hash Function

A family of hash functions

MD5

SHA-1

1 Recall

2 Using unkeyed hash functions

Motivation for security requirements

3 Constructing an Unkeyed Hash Function

4 A family of hash functions

5 MD5

6 SHA-1

CM30173: CryptographyPart III

CM30173:

Cryptography

Part III

Recall

Using unkeyed hash

functions

Motivation for security

requirements

Constructing an

Unkeyed Hash

Function

A family of hash

functions

MD5

SHA-1

Recall

Using unkeyed hash functions

Constructing an Unkeyed Hash Function

A family of hash functions

MD5

SHA-1

Definition of an unkeyed hash function

Definition

An unkeyed hash function is a function h : X ! Y
where:

1 X is the set of possible messages
2 Y is a finite set of possible message digests

A pair (x, y), x 2 X , y 2 Y is valid if h(x) = y.

CM30173: CryptographyPart III

CM30173:

Cryptography

Part III

Recall

Using unkeyed hash

functions

Motivation for security

requirements

Constructing an

Unkeyed Hash

Function

A family of hash

functions

MD5

SHA-1

Recall

Using unkeyed hash functions

Constructing an Unkeyed Hash Function

A family of hash functions

MD5

SHA-1

Security

A n-bit unkeyed hash function is considered to be
secure if:

1 Given a hash output producing a preimage or a
second preimage requires approximately 2n

operations;

2 Producing a collision requires approximately 2n/2

operations.

CM30173: CryptographyPart III

CM30173:

Cryptography

Part III

Recall

Using unkeyed hash

functions

Motivation for security

requirements

Constructing an

Unkeyed Hash

Function

A family of hash

functions

MD5

SHA-1

Recall

Using unkeyed hash functions

Constructing an Unkeyed Hash Function

A family of hash functions

MD5

SHA-1

1 Recall

2 Using unkeyed hash functions

Motivation for security requirements

3 Constructing an Unkeyed Hash Function

4 A family of hash functions

5 MD5

6 SHA-1

CM30173: CryptographyPart III

CM30173:

Cryptography

Part III

Recall

Using unkeyed hash

functions

Motivation for security

requirements

Constructing an

Unkeyed Hash

Function

A family of hash

functions

MD5

SHA-1

Recall

Using unkeyed hash functions

Constructing an Unkeyed Hash Function

A family of hash functions

MD5

SHA-1

Iterative hash function

CM30173: CryptographyPart III

CM30173:

Cryptography

Part III

Recall

Using unkeyed hash

functions

Motivation for security

requirements

Constructing an

Unkeyed Hash

Function

A family of hash

functions

MD5

SHA-1

Recall

Using unkeyed hash functions

Constructing an Unkeyed Hash Function

A family of hash functions

MD5

SHA-1

The Merkle-Damg̊ard construction

Theorem

Any collision resistant compression function can be
extended to a collision resistant hash function which
takes arbitrary length inputs.

This can be done e�ciently by the
Merkle-Damg̊ard construction

This construction specialises the generic
construction above

CM30173: CryptographyPart III

CM30173:

Cryptography

Part III

Recall

Using unkeyed hash

functions

Motivation for security

requirements

Constructing an

Unkeyed Hash

Function

A family of hash

functions

MD5

SHA-1

Recall

Using unkeyed hash functions

Constructing an Unkeyed Hash Function

A family of hash functions

MD5

SHA-1

The Merkle-Damg̊ard construction

Let compress : {0, 1}n+t ! {0, 1}n be a collision
resistant compression function (t � 1).

We construct a collision resistant hash function:

h :
1[

i=n+t+1

{0, 1}i ! {0, 1}n

Break input x, of bitlength b, into blocks
x1, . . . , xr. Set yi = xi, each of bitlength t,
padding out the last block with 0’s if needed.
Put yr+1 = (right justified) binary representation of
b (assume b < 2t) (MD strengthening). CM30173: CryptographyPart III CM30173: Cryptography Part III Recall Using unkeyed hash functions Motivation for security requirements Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 Recall Using unkeyed hash functions Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 The Merkle-Damg̊ard construction Let compress : {0, 1}n+t ! {0, 1}n be a collision resistant compression function (t � 1). We construct a collision resistant hash function: h : 1[ i=n+t+1 {0, 1}i ! {0, 1}n Break input x, of bitlength b, into blocks x1, . . . , xr. Set yi = xi, each of bitlength t, padding out the last block with 0’s if needed. Put yr+1 = (right justified) binary representation of b (assume b < 2t) (MD strengthening). CM30173: CryptographyPart III CM30173: Cryptography Part III Recall Using unkeyed hash functions Motivation for security requirements Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 Recall Using unkeyed hash functions Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 The Merkle-Damg̊ard construction Let compress : {0, 1}n+t ! {0, 1}n be a collision resistant compression function (t � 1). We construct a collision resistant hash function: h : 1[ i=n+t+1 {0, 1}i ! {0, 1}n Break input x, of bitlength b, into blocks x1, . . . , xr. Set yi = xi, each of bitlength t, padding out the last block with 0’s if needed. Put yr+1 = (right justified) binary representation of b (assume b < 2t) (MD strengthening). CM30173: CryptographyPart III CM30173: Cryptography Part III Recall Using unkeyed hash functions Motivation for security requirements Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 Recall Using unkeyed hash functions Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 The Merkle-Damg̊ard construction Algorithm Construct y = y1ky2k . . . kyr+1 z0 = 0 n for i = 1 to r + 1 do zi = compress(zi�1kyi) end do return h(x) = zr+1 CM30173: CryptographyPart III CM30173: Cryptography Part III Recall Using unkeyed hash functions Motivation for security requirements Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 Recall Using unkeyed hash functions Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 Conclusions The Merkle-Damg̊ard construction provably generates a collision-resistant hash-function from a collision-resistant compression function. But: How do we know that our compression function is collision-resistant? The hash function will not be preimage-resistant, in general. One collision yields further collisions by extension attack. CM30173: CryptographyPart III CM30173: Cryptography Part III Recall Using unkeyed hash functions Motivation for security requirements Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 Recall Using unkeyed hash functions Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 1 Recall 2 Using unkeyed hash functions Motivation for security requirements 3 Constructing an Unkeyed Hash Function 4 A family of hash functions 5 MD5 6 SHA-1 CM30173: CryptographyPart III CM30173: Cryptography Part III Recall Using unkeyed hash functions Motivation for security requirements Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 Recall Using unkeyed hash functions Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 A family of hash functions SHA−1 SHA−384 SHA−512SHA−256 SHA RIPEMD RIPEMD−160RIPEMD−128 MD4 MD5 CM30173: CryptographyPart III CM30173: Cryptography Part III Recall Using unkeyed hash functions Motivation for security requirements Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 Recall Using unkeyed hash functions Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 MD5: summary of status The MD5 algorithm is described by Rivest in Internet Working Group, RFC 1321, April 1992 http://portal.acm.org/citation.cfm?id=RFC1321, (includes a reference implementation) MD5 is an extension of MD4 and is deemed to be more conservative Mid-1990s: Collisions found in compression function 2004: Wang et al. produced a collision for MD5 2008: Chosen prefix collision attacks. 2013: 218 collion attacks announced. http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/ CM30173: CryptographyPart III http://portal.acm.org/citation.cfm?id=RFC1321 http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/ CM30173: Cryptography Part III Recall Using unkeyed hash functions Motivation for security requirements Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 Recall Using unkeyed hash functions Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 MD5: summary of status The MD5 algorithm is described by Rivest in Internet Working Group, RFC 1321, April 1992 http://portal.acm.org/citation.cfm?id=RFC1321, (includes a reference implementation) MD5 is an extension of MD4 and is deemed to be more conservative Mid-1990s: Collisions found in compression function 2004: Wang et al. produced a collision for MD5 2008: Chosen prefix collision attacks. 2013: 218 collion attacks announced. http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/ CM30173: CryptographyPart III http://portal.acm.org/citation.cfm?id=RFC1321 http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/ CM30173: Cryptography Part III Recall Using unkeyed hash functions Motivation for security requirements Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 Recall Using unkeyed hash functions Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 MD5: summary of status The MD5 algorithm is described by Rivest in Internet Working Group, RFC 1321, April 1992 http://portal.acm.org/citation.cfm?id=RFC1321, (includes a reference implementation) MD5 is an extension of MD4 and is deemed to be more conservative Mid-1990s: Collisions found in compression function 2004: Wang et al. produced a collision for MD5 2008: Chosen prefix collision attacks. 2013: 218 collion attacks announced. http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/ CM30173: CryptographyPart III http://portal.acm.org/citation.cfm?id=RFC1321 http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/ CM30173: Cryptography Part III Recall Using unkeyed hash functions Motivation for security requirements Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 Recall Using unkeyed hash functions Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 MD5: summary of status The MD5 algorithm is described by Rivest in Internet Working Group, RFC 1321, April 1992 http://portal.acm.org/citation.cfm?id=RFC1321, (includes a reference implementation) MD5 is an extension of MD4 and is deemed to be more conservative Mid-1990s: Collisions found in compression function 2004: Wang et al. produced a collision for MD5 2008: Chosen prefix collision attacks. 2013: 218 collion attacks announced. http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/ CM30173: CryptographyPart III http://portal.acm.org/citation.cfm?id=RFC1321 http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/ CM30173: Cryptography Part III Recall Using unkeyed hash functions Motivation for security requirements Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 Recall Using unkeyed hash functions Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 MD5: summary of status The MD5 algorithm is described by Rivest in Internet Working Group, RFC 1321, April 1992 http://portal.acm.org/citation.cfm?id=RFC1321, (includes a reference implementation) MD5 is an extension of MD4 and is deemed to be more conservative Mid-1990s: Collisions found in compression function 2004: Wang et al. produced a collision for MD5 2008: Chosen prefix collision attacks. 2013: 218 collion attacks announced. http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/ CM30173: CryptographyPart III http://portal.acm.org/citation.cfm?id=RFC1321 http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/ CM30173: Cryptography Part III Recall Using unkeyed hash functions Motivation for security requirements Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 Recall Using unkeyed hash functions Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 MD5: summary of status The MD5 algorithm is described by Rivest in Internet Working Group, RFC 1321, April 1992 http://portal.acm.org/citation.cfm?id=RFC1321, (includes a reference implementation) MD5 is an extension of MD4 and is deemed to be more conservative Mid-1990s: Collisions found in compression function 2004: Wang et al. produced a collision for MD5 2008: Chosen prefix collision attacks. 2013: 218 collion attacks announced. http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/ CM30173: CryptographyPart III http://portal.acm.org/citation.cfm?id=RFC1321 http://www.win.tue.nl/hashclash/ChosenPrefixCollisions/ CM30173: Cryptography Part III Recall Using unkeyed hash functions Motivation for security requirements Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 Recall Using unkeyed hash functions Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 Flame Malware Attack “[Flame is] ... arguably the most complex malware ever found” Flame was discovered in 2012 but probably existed since 2010. It appears to target Iranian computers for the purpose of espionage. Flame authenticates itself to its host using a forged a Microsoft Terminal Server licensing certificate. The forgery uses a (unknown) chosen prefix attack on MD5. CM30173: CryptographyPart III CM30173: Cryptography Part III Recall Using unkeyed hash functions Motivation for security requirements Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 Recall Using unkeyed hash functions Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 1 Recall 2 Using unkeyed hash functions Motivation for security requirements 3 Constructing an Unkeyed Hash Function 4 A family of hash functions 5 MD5 6 SHA-1 CM30173: CryptographyPart III CM30173: Cryptography Part III Recall Using unkeyed hash functions Motivation for security requirements Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 Recall Using unkeyed hash functions Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 SHA- 1: Basic information Input: message of maximum length 264 � 1 Output: 160 bit message digest Iterated hash function Based on the Merkle-Damg̊ard construction It operates on words of 32 bits Three steps: 1 Preprocessing: append padding bits, append length, initialisation 2 Iteration of a compression function 3 Output of hash CM30173: CryptographyPart III CM30173: Cryptography Part III Recall Using unkeyed hash functions Motivation for security requirements Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 Recall Using unkeyed hash functions Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 SHA: summary of status SHA (referred to as SHA-0), is considered insecure). SHA-1 (a minor variation of SHA) is described in FIPS publication 180-1, http://www.itl.nist.gov/fipspubs/fip180-1.htm 2005: Wang et al. showed collisions can be found in SHA-1 in less than 263 steps. However, attempts to find a collision have failed: http://boinc.iaik.tugraz.at/ Members of the SHA-2 family (SHA-256, SHA-384, SHA-512) are more complex than SHA-1. They are currently considered secure. CM30173: CryptographyPart III http://www.itl.nist.gov/fipspubs/fip180-1.htm http://boinc.iaik.tugraz.at/ CM30173: Cryptography Part III Recall Using unkeyed hash functions Motivation for security requirements Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 Recall Using unkeyed hash functions Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 SHA: summary of status SHA (referred to as SHA-0), is considered insecure). SHA-1 (a minor variation of SHA) is described in FIPS publication 180-1, http://www.itl.nist.gov/fipspubs/fip180-1.htm 2005: Wang et al. showed collisions can be found in SHA-1 in less than 263 steps. However, attempts to find a collision have failed: http://boinc.iaik.tugraz.at/ Members of the SHA-2 family (SHA-256, SHA-384, SHA-512) are more complex than SHA-1. They are currently considered secure. CM30173: CryptographyPart III http://www.itl.nist.gov/fipspubs/fip180-1.htm http://boinc.iaik.tugraz.at/ CM30173: Cryptography Part III Recall Using unkeyed hash functions Motivation for security requirements Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 Recall Using unkeyed hash functions Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 SHA: summary of status SHA (referred to as SHA-0), is considered insecure). SHA-1 (a minor variation of SHA) is described in FIPS publication 180-1, http://www.itl.nist.gov/fipspubs/fip180-1.htm 2005: Wang et al. showed collisions can be found in SHA-1 in less than 263 steps. However, attempts to find a collision have failed: http://boinc.iaik.tugraz.at/ Members of the SHA-2 family (SHA-256, SHA-384, SHA-512) are more complex than SHA-1. They are currently considered secure. CM30173: CryptographyPart III http://www.itl.nist.gov/fipspubs/fip180-1.htm http://boinc.iaik.tugraz.at/ CM30173: Cryptography Part III Recall Using unkeyed hash functions Motivation for security requirements Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 Recall Using unkeyed hash functions Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 What now? NIST has released a policy on use of hashes in the SHA family: http://csrc.nist.gov/groups/ST/hash/policy.html NIST cryptographic hash project: http://www.nist.gov/hash-competition CM30173: CryptographyPart III http://csrc.nist.gov/groups/ST/hash/policy.html http://www.nist.gov/hash-competition CM30173: Cryptography Part III Recall Using unkeyed hash functions Motivation for security requirements Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 Recall Using unkeyed hash functions Constructing an Unkeyed Hash Function A family of hash functions MD5 SHA-1 SHA-3 The hash function Keccak was chosen by NIST as the basis for a new standard - SHA-3 (2014). SHA-3 does not replace SHA-2 (which still considered secure) but has some operational advantages. It is based on an iterated sponge construction (not Merkle-Damg̊ard) : at each iteration, a block of the message is XORed into the current state, and then substitution and permutation operations are performed. CM30173: CryptographyPart III