The Internet of Broken Protocols: Showcase #1
(complete list of showcases: https://vnhacker.blogspot.com/search/label/The%20Internet%20of%20Broken%20Protocols)
Updated: scroll down for solutions.
Alice and Bob have a pre-shared secret PSS. They want to build a secure channel. Someone designed the following protocol for them. Your task is to analyze this protocol and find all weaknesses. You might email me at thaidn@gmail.com if you want some privacy. I'll update this post with my solution in 48 hours.
The protocol consists of two sub protocols: key exchange and data encryption.
# Authenticated key exchange
1/ Remind: Alice and Bob have a pre-shared secret PSS.
2/ They perform an unauthenticated Curve25519 key exchange. Let K denote the raw 32-byte shared key.
3/ Alice generates and sends 32-byte random alice_nonce. Bob generates and sends 32-byte random bob_nonce.
4/ Alice sends alice_proof = HMAC-SHA256(K, alice_nonce + PSS). Bob verifies and closes the connection if alice_proof is invalid.
5/ Bob sends bob_proof = HMAC-SHA256(K, bob_nonce + PSS). Alice verifies and closes the connection if bob_proof is invalid.
At this point the authenticated key exchange is considered successful.
# Data encryption
1/ Alice derives two 32-byte keys:
K_read = HMAC-SHA256(K , "Alice")
K_write = HMAC-SHA256(K , "Bob")
2/ Alice uses K_read to decrypt data sent by Bob and K_write to encrypt data sent to Bob. All data encryption is done using AES-GCM with a random 96-bit IV.
---
I got answers from three people. Two persons identified the most critical issue. The best part is the readers also identified a vulnerability that I didn't know. This is really fun and inspiring :). Thanks everyone for participating!
The winner is Andrew L. He wrote:
Problem 1: if the DH algorithm chosen doesn't guarantee contributory behavior, the algorithm fails completely. M can simultaneously authenticate with A and B, forcing the same key K in both exchanges and relaying the authentication messages.
This attack could end up being trivial: just edit the DH shares on the wire to make them both be the identity.
Problem 2: Chuck convinces Alice to initiate a connection to him and claims to be Bob. He sets bob_nonce = alice_nonce. Now he can authenticate without knowing PSS. (This only works if the nonce exchange allows this.)
Problem 3: This use of HMAC is backwards. An attacker pretending to be Alice or Bob (doing DH normally) knows K. That means the attacker can search for collisions to generate a nonce that internally collides with Alice or Bob's nonce. If the underlying hash is strong, this isn't so bad, but if the hash allows first preimages to be found, this allows a harder-to-detect version of #2. (Under normal use where the key is unknown to an attacker, HMAC prevents this type of attack.)
Problem #1 is the issue that I had in mind. I explicitly used Curve25519 to demonstrate the fact that in some badly designed protocols one really needs to verify Curve25519 public keys, contrary to popular belief. The issue is less severed if the protocol uses a NIST curve because as far as I can tell most libraries don't have a valid encoding for the identity point which is also the point at infinity. Another reader, Thắng N., also identified this issue.
Problem 2 is just mind blowing. I saw attacks like this before, if I remember correctly they are called "reflection attack" in the literature, but I failed to recognize it when I first looked at this protocol. To be fair to myself, it was because I focused on decrypting data sent in the second phase. This attacks allows bypassing the authentication phase, but the attacker won't know the shared secret. Another reader, Carl M. also identified this issue.
Problem 3: I don't really think this is a problem, as the search space is huge and most hash functions, even badly broken MD5, are safe against pre-image attacks. Anyway it's really cool that Andrew thinks of issues like this and shares his thought with us.
Thanks everyone!
Updated: scroll down for solutions.
Alice and Bob have a pre-shared secret PSS. They want to build a secure channel. Someone designed the following protocol for them. Your task is to analyze this protocol and find all weaknesses. You might email me at thaidn@gmail.com if you want some privacy. I'll update this post with my solution in 48 hours.
The protocol consists of two sub protocols: key exchange and data encryption.
# Authenticated key exchange
1/ Remind: Alice and Bob have a pre-shared secret PSS.
2/ They perform an unauthenticated Curve25519 key exchange. Let K denote the raw 32-byte shared key.
3/ Alice generates and sends 32-byte random alice_nonce. Bob generates and sends 32-byte random bob_nonce.
4/ Alice sends alice_proof = HMAC-SHA256(K, alice_nonce + PSS). Bob verifies and closes the connection if alice_proof is invalid.
5/ Bob sends bob_proof = HMAC-SHA256(K, bob_nonce + PSS). Alice verifies and closes the connection if bob_proof is invalid.
At this point the authenticated key exchange is considered successful.
# Data encryption
1/ Alice derives two 32-byte keys:
K_read = HMAC-SHA256(K , "Alice")
K_write = HMAC-SHA256(K , "Bob")
2/ Alice uses K_read to decrypt data sent by Bob and K_write to encrypt data sent to Bob. All data encryption is done using AES-GCM with a random 96-bit IV.
---
I got answers from three people. Two persons identified the most critical issue. The best part is the readers also identified a vulnerability that I didn't know. This is really fun and inspiring :). Thanks everyone for participating!
The winner is Andrew L. He wrote:
Problem 1: if the DH algorithm chosen doesn't guarantee contributory behavior, the algorithm fails completely. M can simultaneously authenticate with A and B, forcing the same key K in both exchanges and relaying the authentication messages.
This attack could end up being trivial: just edit the DH shares on the wire to make them both be the identity.
Problem 2: Chuck convinces Alice to initiate a connection to him and claims to be Bob. He sets bob_nonce = alice_nonce. Now he can authenticate without knowing PSS. (This only works if the nonce exchange allows this.)
Problem 3: This use of HMAC is backwards. An attacker pretending to be Alice or Bob (doing DH normally) knows K. That means the attacker can search for collisions to generate a nonce that internally collides with Alice or Bob's nonce. If the underlying hash is strong, this isn't so bad, but if the hash allows first preimages to be found, this allows a harder-to-detect version of #2. (Under normal use where the key is unknown to an attacker, HMAC prevents this type of attack.)
Problem #1 is the issue that I had in mind. I explicitly used Curve25519 to demonstrate the fact that in some badly designed protocols one really needs to verify Curve25519 public keys, contrary to popular belief. The issue is less severed if the protocol uses a NIST curve because as far as I can tell most libraries don't have a valid encoding for the identity point which is also the point at infinity. Another reader, Thắng N., also identified this issue.
Problem 2 is just mind blowing. I saw attacks like this before, if I remember correctly they are called "reflection attack" in the literature, but I failed to recognize it when I first looked at this protocol. To be fair to myself, it was because I focused on decrypting data sent in the second phase. This attacks allows bypassing the authentication phase, but the attacker won't know the shared secret. Another reader, Carl M. also identified this issue.
Problem 3: I don't really think this is a problem, as the search space is huge and most hash functions, even badly broken MD5, are safe against pre-image attacks. Anyway it's really cool that Andrew thinks of issues like this and shares his thought with us.
Thanks everyone!
Comments