ECS726P: Security and Authentication
Week 4: Hash functions, MAC, digital signatures, freshness, dynamic password schemes
EECS, QMUL
Copyright By PowCoder代写 加微信 powcoder
Table of contents
1. Data Integrity
2. Cryptographic Hash Functions
3. Message authentication codes (MAC) 4. Digital signatures
5. Entity authentication
Learning Outcomes
Data Integrity
Cryptographic Hash Functions
• Properties
• Applications
• Birthday Attack
• Well-known Hash functions
Learning Outcomes
• Appreciate there are different levels of data integrity.
• Identify the different properties of a cryptographic
hash function.
• Recognise the significance of the length of the output of a hash function.
• Explain how to use a MAC to provide data origin authentication.
• Compare different ways of providing both confidentiality and data origin authentication.
Learning Outcomes
• Explain general requirements for a digital signature scheme.
• Explain methods of creating a digital signature scheme based on RSA.
• Compare different techniques for providing freshness.
• Recognise a number of different approaches to
providing entity authentication
• Appreciate the limitations of password-based approaches to providing entity authentication.
• Explain the principle behind dynamic password schemes.
Data Integrity
Data Integrity – Introduction
Data Integrity is the assurance that data has not been altered in an unauthorised manner after its creation.
• Data integrity is not about prevention of alteration of data,
• Data integrity is about detecting whether data has been manipulated in an unauthorised way.
Data Integrity: Different levels
levels of Data Integrity:
• Accidental errors: for example caused by noise in a communication channel/storage;
• mitigations: simple parity checks, CRC…
• Active attacks: prevent an attacker from creating a “valid” integrity digest on some data for which they have not seen an integrity digest of.
• mitigations typically require data origin authentication to bind data to its source e.g. provided by Message Authentication Codes (MAC)
Cryptographic Hash Functions
(Cryptographic) Hash Functions
A hash function accepts a variable-size message m and produces a fixed-size message digest h(m) as output.
• Hash functions are publicly computable. We assume an attacker knows the details of a hash function
• Practically: the hash function should be easy to compute.
• a very simple naive example of file digest: first 256 bits of the file xor with second 256 bits of the file xor with third 256 bits etc etc, this results in a 256 bits digest of the file (don’t use this as a hash function!!)
(Cryptographic) Hash Functions
Some use of Hash functions
• a strong one-way function (e.g. digest of passwords)
• component for crypto primitive (MAC, digital signatures, etc…)
• to bind documents (certify sender sent D1 and D2)
• source of pseudorandomness
• bitcoin (proof of work)
(Cryptographic) Hash Functions: Requirements
Security requirements of a cryptographic hash function:
• Preimage Resistance: Given an output (hash) z and the function h, it should be computationally impossible to find any input x such that h(x) = z. (the output h(x) of a function h is often called the image of x, and hence x is referred to as a pre-image of h(x)).
• Second Preimage Resistance: Given an input x1 and its output (hash) value h(x1), it should be a computationally impossible operation to find any other input x2 (x2 ̸= x1 ) such that h(x1) = h(x2).
• Collision Resistance: Given the function h, it should
be computationally impossible to find a collision, that
is, two inputs x1 ̸= x2 such that h(x1) = h(x2). 9
(Cryptographic) Hash Functions: Requirements
”first 256 bits of the file xor with second 256 bits of the file xor with third 256 bits etc etc”
why this simple xor 256 bits blocks function is bad as a hash function?
Preimage Resistance: ? Second Preimage Resistance:? Collision Resistance:?
(Cryptographic) Hash Functions: Applications
There are clear reasons why we want those properties, i.e. there are applications requiring:
• Preimage Resistance
• Second Preimage Resistance • Collision Resistance
(Cryptographic) Hash Functions: Applications
Application Requiring Preimage Resistance: Password check and storage
When you login (high-level workflow):
• you enter username and password on the sever
• the server compute the hash of your password
• server check the hash of your password matches the hash it has stored for that username
• if it matches you are authenticated
• An attacker stealing the hashed passwords’ file from
the server shouldn’t be able to recover the passwords
(Cryptographic) Hash Functions: Applications
Application Requiring Second Preimage Resistance:
Software downloading
your system wants to be sure the software you download has not been altered
• it computes a hash of the software file
• check the hash with the (trusted) vendor hash
• if they don’t match the software downloaded is not correct
• an attacker shouldn’t be able to create a false software with the same hash as the original
(Cryptographic) Hash Functions: Applications
Application Requiring Collision Resistance: contractual committment
• Bob finds two messages with the same hash, one of which requires Alice to pay a small amount and one that requires a large payment.
• Alice signs the first message, and Bob is then able to claim that the second message is authentic (as they have the same hash).
Hash security: The birthday paradox
Consider a group of N people. What is the probability that at least two of them have the same birthday?
How many people are needed to get a probability of at least 0.5?
• it may looks surprising but it only needs 23 people so that the probability of two people having the same birthday is at least 0.5!
• if there are 50 people the probability of two people sharing the same birthday is almost certain! (over 0.95)
how is this related to hash functions?
Hash security: The birthday paradox
• it may looks surprising but it only needs 23 people so that the probability of two people having the same birthday is at least 0.5!
• if there are 50 people the probability of two people sharing the same birthday is almost certain! (over 0.95)
number of people who have a different birthday is given by the formula below
(365 − n)! · 365n
how is this related to hash functions?
Hash security: The birthday paradox
Suppose an attacker wants to create a collision for a cryptographically strong hash function that creates hashes of length L bits. How many random inputs should the attacker try to get a collision with a probability of at least 0:5?
• the attacker needs 2L/2, i.e., only the square root of the number of possible distinct hashes.
• this results suggests some lower bound on the number of bits required for a strong hash function.
• for example for a 256 bits length hash function one would need around 2128 attempts to find a collision with probability 0.5
Some hash functions
• MD5: The hash function MD5 has been one of the most widely deployed hash functions, and was adopted as Internet Standard RFC 1321. It is a 128-bit hash function and is often used for file integrity checking. In 2004, collisions were found in MD5, and MD5 is no longer recommended for use.
• SHA-1 family: The Secure Hash Algorithm was published by NIST in 1993 as a 160-bit hash function. It has been the “default” hash function of the late 1990s and the early 2000s and used in numerous security applications, including SSL/TLS and S/MIME. In 2005, a technique was proposed for finding collisions for SHA-1 after 263 computations, much faster than a birthday attack.
Some hash functions
• SHA-2 family: NIST published four further SHA variants, each of which is labelled by the number of bits of the hash output: SHA-224, SHA- 256, SHA-384, and SHA-512 (collectively they are referred to as SHA- 2). SHA-256 is the minimum security level recommended for many applications.
• SHA-3: In 2006 NIST initiated an AES style SHA-3 competition for new hash functions which would provide a genuine alternative to the SHA- 2 family (2012 winner: KECCAK).
Message authentication codes (MAC)
Message authentication codes (MAC)
• MAC provides data origin authentication which, as we mentioned earlier, is a stronger notion than data integrity.
• MAC is a cryptographic checksum which is sent along with a message in order to provide an assurance of data origin authentication.
Message authentication codes (MAC)
Message authentication codes (MAC)
Message Authentication involves generating a small block of data (the MAC) that is appended to the message.
• The MAC depends on the contents of the message and a secret key MAC(m) = f (kAB , m), where m is the plaintext, f is a function (see some choices in the next slides) and kAB is the shared key between users A and B
• The message plus MAC are transmitted to the receiver.
• The receiver calculates the MAC of the message and compares it with the MAC just received.
• mismatch= something wrong
Message authentication codes (MAC)
If the received MAC matches the calculated MAC then The receiver is assured that the message
• has not been altered (integrity of the message) because only sender and receiver shared the key kAB .
• is from the alleged sender (originator identity validation).
Message authentication codes (MAC)
MAC algorithms
• Can we use Symmetric Encryption algorithms to construct MAC?
• After all, the sender and receiver need to share a secret key?
Message authentication codes (MAC)
MAC algorithms: CBC-MAC
Message authentication codes (MAC)
MAC algorithms: CBC-MAC
• The MAC in CBC-MAC is the last ciphertext block of a computation using the CBC mode of operation.
• For CBC-MAC, the process is started by using the first message block instead of creating an IV.
• In CBC-MAC we discard all the intermediate ciphertext blocks!
Message authentication codes (MAC)
MAC algorithms: HMAC (Hash-based Message Authentication Code)
• HMAC is a MAC derived from a cryptographic hash function, that is, it incorporates a secret key into an existing hash algorithm.
• Let h be a hash function, and let K1 and K2 be two symmetric keys.Then the MAC on message M is computed as follows:
1. compute the hash of K2 concatenated with the message; in other words compute h(K2||M); and
2. compute the hash of K1 concatenated with the
output of step 1; in other words compute: h(K1||h(K2||M)). 27
Message authentication codes (MAC)
Security of HMAC. The security of HMAC depends on:
• The security of the keys. HMAC employs two symmetric keys. Thus, the length of an HMAC key can be regarded as the sum of the lengths of these two keys.
• The security of the underlying hash function.
• The length of the MAC output.
Message authentication codes (MAC)
Security of HMAC. The security of HMAC depends on:
• The security of the keys. HMAC employs two symmetric keys. Thus, the length of an HMAC key can be regarded as the sum of the lengths of these two keys.
• The security of the underlying hash function.
• The length of the MAC output.
Message authentication codes (MAC)
So far, we look at data origin authentication without confidentiality. Not a reasonable assumption!
In most cases, we require confidentiality as well as data origin authentication. We will refer to this combination of security services as authenticated encryption.
How to achieve it?
• MAC-then-encrypt
• Encrypt-then-MAC
• Authenticated-Encryption Primitives (e.g. Galois counter mode of operation)
Message authentication codes: non-repudiation
Can message authentication codes provide non-repudiation?
• Alice send Bob “I owe you 10 pounds” and associated MAC using their shared key
• Alice can then say: I never wrote that, Bob wrote as he has that same key
Digital signatures
Digital Signatures scheme
a digital signature scheme is a cryptographic primitive providing:
• Data origin authentication of the signer. A digital signature validates the underlying data in the sense that assurance is provided about the integrity of the data and the identity of the signer.
• Non-repudiation. A digital signature can be stored by anyone who receives it as evidence of who signed the document.
Digital Signatures
A digital signature on some data is computed from:
• the Data (i.e. the document to sign)
• A secret parameter known only by the signer.
Digital Signatures
Basic requirements of a Digital Signature Scheme
• Easy for the signer to sign data.
• Easy for anyone to verify a message.
• Hard for anyone to forge a digital signature.
Digital Signatures
A digital signature on some data is computed from:
• the Data (i.e. the document to sign)
• A secret parameter known only by the signer.
Digital Signatures
Digital signature schemes based on RSA. One could
• compute the hash of the document
• send (X,Y) where X= the document and Y= encryption, with sender private key of the hash of the document
• the receiver computes the hash of the document received and check whether it matches the decryption of Y using the sender public key
Example Digital Signatures
Alice wants to send Bob the data P signed so Bob can be secure P comes from Alice. (n, e) is Alice’s public key and
Alice’s private key.
Alice computes h = the hash of P
Alice computes s = hd (mod n) and send (P, s) to receive (P, s) and computes t = the hash of P.
Bob checks se (mod n) = t? if so he accept the signature otherwise signature not valid
Example Digital Signatures
Notice that in public signatures the role of public and private keys are “inverted” with respect to RSA.
• Alice uses the private key d for signing (step s = hd (mod n))
• Bob uses Alice public key to verify the signature (step se (mod n) = t)
Inverting the role of RSA public and private key works because xyz = xzy i.e.
Pde = Ped ≡ P(modn)
Digital Signatures: confidentiality
As in the case of MAC public signatures do not provide confidentiality. To add confidentiality:
• Alice encrypt the data P and signature s with Bob’s public key
• Moreover Alice should add to the encryption a message with her identity
• and add to the signature Bob’s identity
• these two steps (adding sender and receiver identities) are to avoid impersonators’ attacks
Entity authentication
Entity authentication
Entity authentication is the assurance that a given entity is involved and currently active in a communication session.
Are you talking to me?
• Replay attack: an adversary capture a message, and then later replays it at some advantageous time.
• Freshness mechanisms are techniques which can be used to provide assurance a given message is new, in the sense that it is not a replay of a message sent at a previous time.
Freshness Mechanisms
Clock-based mechanisms
• relies on the generation of some data that identifies the time the data was created. This is sometimes referred to as a timestamp.
• Suppose Alice and Bob both have such a clock, and Alice includes the time on the clock when she sends a message to Bob. When Bob receives the message, he checks the time on his clock, and if it matches Alice’s timestamp, then he accepts the message as fresh.
• Requires clocks and synchronisation.
Freshness Mechanisms
Sequence numbers
• Logical time maintains a notion of the order in which messages or sessions occur and is normally instantiated by a counter or sequence number.
• Communicating parties need to maintain a database of the latest sequence numbers
Freshness Mechanisms
Nonce-based mechanisms
• Nonces (numbers used only once): randomly generated numbers for one-off use.
• Alice generates a nonce at some stage in a communication session (protocol). If Alice receives a subsequent message containing this nonce, then Alice has assurance the new message is fresh, where by fresh we mean the received message must have been created after the nonce was generated.
• Need to set a window of acceptance beyond which a nonce will no longer be regarded as fresh.
• Requires random generator
Passwords are used to prove identity. Typical problems with passwords:
• Complexity
• Repeatability • Vulnerability
Dynamic Password Scheme
To mitigate these issues one can combine passwords and freshness, e.g. using the password to generate dynamic data which changes on each authentication attempt, thus preventing repeatability:
• Limits the exposure of the password, thus reducing vulnerability.
• Widely deployed in token-based technologies for accessing services such as internet banking or telephone banking.
Dynamic Password Scheme
How to achieve these dynamic passwords:
• use some time-synchronization between the server and the client providing the password
• use an algorithm creating a new password based on a challenge (the challenge can be a nonce sent by the server)
• use an algorithm to generate a new password based on a counter
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com