Week 5 Part 1 Flashcards
Two online web servers have agreed to authenticate their communication where they seek to achieve confidentiality, integrity and authenticity of the exchanged communication. Their (Authenticated Encryption) system proposal relies on an IND-CPA (see explanation in the guidelines) secure block cipher Enc which uses a key k1 and an existentially unforgeable MAC scheme MAC which uses a key k2. The system works as follows:
- Encrypt message m by computing c1 = Enck1 (m).
- Authenticate message m by computing τ = MACk2 (m)
- Send c = (c1, τ ) to the other party.
Does this construction preserve the IND-CPA property? Also, how can this construction be modified to achieve IND-CCA security?
The authenticated encryption construction is not IND-CPA secure and hence it cannot be IND- CCA secure. The problem is that the MAC is applied to the message rather than the ciphertext. The correct way to construct an authenticated encryption using encryption and MAC schemes is to sign the ciphertext C rather than the plaintext m. As long as Enc itself is IND-CPA secure and the MAC scheme is existentially unforgeable against chosen message attacks, the authenticated encryption construction obtained from interleaving them (Encrypt-then-MAC) is IND-CCA secure.
Two companies would like to communicate confidentially online. They also seek integrity and authenticity of the communication between each other. They require secret-key cryptography to achieve these goals. It is important for the companies that the ciphertexts exchanged are authentic and have not been altered in transit. Note that the communication between the companies comes in the form of short messages which would fit into one plaintext block of AES-128.
The companies already share 2 secret keys,k1which they can use for encrypting with AES-128 andk2which they can use for issuing and verifying MACs. Which of the following solutions fulfils all of the above requirements?Choose only 1 answer.
C=AES-128-ENCk1(M)
T=HMACk2 (C)
Send C and T to the other company
C=AES-128-ENCk1(M)
T=HMACk2(M)
Send C and T to the other company
Any of the 3 solutions would suffice
T=HMACk2 (M)
C= AES-128-ENCk1(T)
Send C and T to the other company
In order to seek integrity and authenticity, the message should be encrypted and signed. With this question the encryption is AES-128 and the signature is with HMAC. The correct order to so this in is encryption then signing. The signature is done on the cipher-text of the encryption so this question is correct. Answer:
- C=AES-128-ENCk1(M)
- T=HMACk2(C)
- Send C and T to the other company
True or False:A secure MACscheme can be constructed from any collision-resistant hash functionHby choosing a MAC keykand computing MACk(M) =H(k || M), where || denotes concatenation.
False because this Hash function is not secure.
- Given m and τ = Sign_k (m) = H(k|| m) , an adversary can compute m* = m || m’ and τ = H(k|| m ) without knowing k
Alice and Bob are using a HMAC for which they already share a keyk. To sign a message M (which is always 4-bit long), the sender parses the message M as a bit string M=ML||MR, i.e. the message is parsed as a left half and a right half (both halves have equal length), then the sender computes X=ML⊕MR(where⊕denotes XOR). The sender then sends M and T=HMACk(X) to the other party.
To show that this construction is forgeable, identify a (4-bit) numerical message (in decimal format) whose MAC tag would collide with that of the message M=13 (in decimal format), which would constitute a forgery.Your answer must be a positive integer value (in decimal format).
So if we look at the binary number of 13 it’s 1101 which according to M=ML||MR is a concatenation of 11 and 01, if we XOR them, we get 10. So this means we need two number ML and MR that gives us 10 when we XOR them. One answer is 10 and 00. When you XOR them you get 10. to get the message we concatenate them to get 1000. The decimal representation of 1000 is 8.
Alice has anexistentially unforgeableMAC scheme that can only sign fixed-length messages which are 64-bit long. Such a MAC requires a 128-bit key. In order to extend this secure MAC to sign arbitrary-length messages, Alice utilised a collision-resistant hash function H that maps arbitrary-length bit strings into 64-bit strings, i.e. H: {0,1}*⟶{0,1}64. To sign a message M, Alice signs H(M) instead of signing the message M using her original secure MAC scheme.
What is the security level offered by this modified MAC construction that supports arbitrary-length messages?
The security level offered by this modified MAC construction is the security level provided by the collision-resistant hash function H because she signs it with a hash function. The security level of the hash function is 2^n/2 which is 32 bits.
What is existential unforgeability?
Unforgeability: Hard to compute a valid pair (m, τ ) without knowing k
- Adversary sends messages to the challenger to sign, and does this q amount of time
- in the end, the challenger say you will win if you send me a new signed message i did not sign for you, and the signature is valid
- our mac is secure if an adversary cant beat this game
What is a replay attack? Are macs secure against replay attacks, why or why not?
A replay attack is when an attacker intercepts and maliciously resends a previously captured message to deceive the recipient into taking unwanted actions.
- Macs are not secure against replay attacks
- The adversary sees a legitimate signature, copies and pastes it and the recipient will keep accepting
- Every time a valid pair (m, τ ) is presented to Verifyk, it will return the same result, i.e. no notion of state is incorporated in MACs
- Protection against replay attacks usually is left to higher-level applications
What are some techniques to prevent replay attacks?
-
Adding a sequence number: Sender signs i||m instead of m for some unique sequence number i
- Receiver keeps tracks of sequence numbers received already
- Using timestamps: Sender appends current time to the message and the receiver checks the time is acceptable
-
Using Nonce: The receiver sends to the sender a random nonce N which the sender includes in the signature
- τ is a signature tag on (m, N )
Can we use the Merkle Dammgard hash function to get a secure MAC scheme?
- This construction is insecure!
- Given m and τ = Sign_k (m) = H(k|| m), an adversary can compute m* = m || m’ and τ* = H(k|| m*) without knowing k
Vulnerability in Merkle-Damgard: The Merkle-Damgård construction allows appending extra blocks to the message without needing to know the entire original message. An attacker can take a valid hash output and use it as the initial value IV for hashing additional blocks, effectively creating a valid hash for a modified message.
Can we use HMAC (Hash Mac) to get a secure hash function?
YES
HMAC involves padding the key with two distinct constants (ipad and opad), then hashing the key and message in two rounds: first with the inner pad and then with the outer pad. The final HMAC value can be used to check that the message hasn’t been changed and that it’s from a legitimate sender. This method is secure as long as the secret key remains confidential.
Construction I for ECBC- MAC only works for fixed-length messages (not any length file), what are some possible ways to extend it to variable-length messages?
- Receiver and sender agree on the message length beforehand
- Encrypt the message length in the first block
- Use 2 different keys (see Construction II)
Construction I for ECBC- MAC only works for fixed-length messages (not any length file), what could the adversary do if its not fixed length?
- Adversary sees 2 pairs of message/tag
- (m = (m1, . . . , mn), τ )and
(m′ = (m′1, . . . , m′n), τ ′)
- (m = (m1, . . . , mn), τ )and
- Adversary computes a forgery
(m∗, τ ∗) where
m∗ = (m1, m2 . . . , mn, m′1 ⊕ τ, m′2, . . . , m′n) and τ ∗ = τ ′
to put it simply:
the adversary takes the first n components of the original message m and appends components of another message m’ to it, but they modify these appended components by XORing them with the tag τ of the original message. Then, the adversary uses the tag τ’ of the second message as the tag for the forged message. If the system or person checking the message only looks at the tag and sees it matches part of the message (even if that part is the one added by the adversary), they might be fooled into thinking the whole message is valid.
How can a secure mac scheme with variable length messages be constructed from block ciphers?
ECBC-MAC but use 2 different keys
- The message m is divided into blocks m= m_1, …. ,m_n
- intermediate ciphertexts are not returned
How can you simultaneously provide confidentiality, integrity and authenticity
- Decryption should fail if ciphertext was not produced using the key
- Authenticated Encryption (combines encryption & MAC) uses an encryption scheme (with key k_{Enc}) and a MAC scheme (with key k_{MAC})
- The right approach is to Encrypt-then-MAC
- Compute MACs on the ciphertexts and not on the plaintexts
- Note: Never use MAC-then-Encrypt or MAC-and-Encrypt!
2- For each of the following cases, prove or disprove whether the resulting MAC construction offers existential unforgeability against chosen-message attacks.
a) A MAC scheme is constructed from a block cipher Enc whose block size is n bits. The construction also utilizes a collision-resistant hash function H : {0, 1}∗ → {0, 1}n. The MAC authenticates a message m as follows:
- If the message m is exactly n-bit long, i.e. |m| = n, compute τ = M AC(m) = Enck(m).
- It the message m is not exactly n-bit long, i.e. |m| 6 = n, compute τ = M AC(m) = Enck(H(m)).
This construction is not existentially unforgeable since any hash of a message m that is not n-bit long, will collide with another n-bit message m′ in which case the same MAC verifies w.r.t. both messages. So the adversary can for instance return a tag obtained for one of those types of message as a tag for the other case. This would constitute a successful forgery.
in other words: if a message m that isn’t n-bits long collides with another message m’ after hashing, the same MAC will authenticate both messages. An attacker could exploit this by using the MAC of one message as a valid tag for the other, resulting in a successful forgery.
