Skip to content

Instantly share code, notes, and snippets.

@ajylee

ajylee/unsilencing-eve-v5.4.md

Last active July 7, 2018 05:19
Show Gist options
  • Save ajylee/7fc35e3028478b10ee30f1cfd6eeac44 to your computer and use it in GitHub Desktop.
Save ajylee/7fc35e3028478b10ee30f1cfd6eeac44 to your computer and use it in GitHub Desktop.
Download ZIP
Unsilencing Eavesdroppers: Forcing Eavesdroppers to Blindly Corrupt Messages
Raw
unsilencing-eve-v5.4.md

Unsilencing Eavesdroppers: Forcing Eavesdroppers to Blindly Corrupt Messages

Andrew Lee
Dec 10 2017
Latest Revision: Jul 6 2018 (v5.4)

Preamble

Suppose all keys have been compromised, or there is no trusted channel to establish public keys. I show that it is possible to force a MITM attacker to commit a corrupted message for each legitimate message they decrypt. The goal is to make it difficult for the attacker to learn anything new from the conversation that they could not have learned by conversing with the participants individually. Additionally, the continuous corrupting of messages endangers the stealthiness of the attacker.

The main idea is to commit to a key and message before revealing the message. This forces the attacker to change both the key and message contents if they want to exploit and maintain their MITM position.

Note that the protocol described here is intended as an extra layer of security on top of a more traditional protocol for securing communications. This protocol is only useful in case the other protocol is compromised.

Another use for the protocol is to make an easy-to-use interface to set up secure communications that is strictly more secure than applying a trust-on-first-use policy and does not require manual effort in verifying public keys. Requiring new users to manually trade public keys over a secure out-of-band channel can decrease usability.

Notation

senc denotes symmetric authenticated encryption (AEAD). senc(k, m) means that the message m is encrypted and authenticated under key k. pk denotes a public key, sk denotes a secret (private) key, k denotes a symmetric key. The generic function h denotes a secure hash function.

Protocol Definition

The steps are:

  1. Alice and Bob generate new Diffie-Hellman keys, public pk_a, pk_b, and private sk_a, sk_b. They also generate symmetric keys k_a and k_b. These symmetric keys are not used directly but are first passed through a secure hash function h. This will be explained later.

  2. Alice sends (HMAC(kdf(senc(h(k_a), m_a)), pk_a), pk_a). Then Bob sends (HMAC(kdf(senc(h(k_b), m_b)), pk_b), pk_b).

  3. Alice and Bob obtain a Diffie-Hellman shared secret, k_ab, from their private keys and each other's public keys.

  4. Alice sends senc(k_ab, senc(h(k_a), m_a)). Bob sends senc(k_ab, senc(h(k_b), m_b)).

  5. Alice checks HMAC(kdf(senc(h(k_b), m_b)), pk_b), with the value received in step 2, and Bob similarily checks HMAC(kdf(senc(h(k_a), m_a)), pk_a). If the checks fail, they abort the conversation.

  6. Alice sends senc(k_ab, k_a). Bob decrypts and reads m_a. Then Bob sends senc(k_ab, k_b). Alice decrypts and reads m_b.

If the messages are not received in the expected order, or the authentication tags fail to verify, the conversation is aborted. Otherwise, the conversation will continue using the new shared secret.

The reason for the hash in step 2 is in case the following attack can be achieved. At step 2, knowing pk_a, the MITM attacker generates and sends some ciphertext c_m, an authentication tag t_m, and Diffie-Hellman public key pk_m. At step 5, after learning k_a and m_a, the MITM attacker generates a key k_m such that m_a = sdec(k_m, c_m) and pk_m and t_m verify under k_m. By hashing the symmetric keys, even if the attacker could produce a key that can decrypt their ciphertext to Alice's message m_a, they would still need to achieve a preimage attack on the hash function to complete the attack.

From Alice's perspective, if there is an attacker Mallory on the network, then she does not know if she actually received pk_b or pk_m in step 2. Similarly, she does not know if she received m_b or m_m. Let us denote the unknown public key she received pk_x and the message m_x, and similarly for others. The HMAC check at step 5 implies to Alice that the sender of pk_x in step 2 also knew senc(h(k_x), m_x) in step 2. She trusts that Bob will only reveal k_b and therefore m_b in step 6. Therefore when Alice reads m_x at step 6, she knows that if the sender of m_x is really Bob (i.e. m_x = m_b), then Bob must have sent the authentication tag for pk_x = pk_b in step 2, and that she now has a shared secret with Bob. If the sender of m_x is actually Mallory, i.e. m_x = m_m, Alice can still be sure that Mallory had committed to m_m without having seen m_b, or that Mallory has reached step 6 with Bob before initiating step 2 with Alice, so that m_m = m_b. This effectively means m_b is from a previous "conversation" with Bob.

In order to eavesdrop on the conversation, Mallory needs to either make up her own responses, or to be able to impersonate one side of the conversation. If she is already able to impersonate one side of the conversation, then she does not need to execute a MITM attack in the first place.

Detailed Attack Scenario

Consider that Alice and Bob's communications have been compromised by Mallory. For simplicity, this is essentially the same as considering that all messages are in the clear and that Mallory is the only other person on the network.

In order to maintain their ability to decrypt future communications, Mallory needs to substitute their own key for pk_b and pk_a. Furthermore, if Mallory wants to pass checks on authentication tags, she needs to commit her own messages before having read Alice's or Bob's messages.

  1. Alice, Bob, and Mallory generate new asymmetric keys, public pk_a, pk_b, pk_m, and private sk_a, sk_b, sk_m. They also generate symmetric keys k_a, k_b, and k_m.

  2. Alice sends (HMAC(kdf(senc(h(k_a), m_a)), pk_a), pk_a) to Mallory, and Mallory sends (HMAC(kdf(senc(h(k_m), m_ma)), pk_m), pk_m) to Bob. Then Bob sends (HMAC(kdf(senc(h(k_b), m_b)), pk_b), pk_b) to Mallory, and Mallory sends (HMAC(kdf(senc(h(k_m), m_mb)), pk_m), pk_m) to Alice.

  3. Alice and Mallory arrive at the shared secret k_am. Bob and Mallory obtain the shared secret k_bm.

  4. Alice sends senc(k_am, senc(h(k_a), m_a)) to Mallory, and Mallory sends senc(k_am, senc(h(k_m), m_mb)) to Alice. Mallory sends senc(k_bm, senc(h(k_m), m_ma)) to Bob. Bob sends senc(k_bm, senc(h(k_b), m_b)) to Mallory.

  5. Alice checks HMAC(kdf(senc(h(k_m), m_mb)), pk_m) with the value received in step 2, and Bob similarily checks HMAC(kdf(senc(h(k_m), m_ma)), pk_m). If the checks fail, they abort the conversation.

  6. Alice sends senc(k_am, k_a). Mallory decrypts and reads m_a. Mallory sends senc(k_bm, k_m) to Bob. Bob decrypts and reads m_ma. Bob sends Mallory senc(k_bm, k_b). Mallory decrypts and reads m_b Mallory sends Alice senc(k_am, k_m). Alice decrypts and reads m_mb.

    Note that if Bob insists on obtaining k_m before sending k_b, then if he senses something is wrong when he reads m_ma, he can refuse to send k_b.

In this attack, Mallory decrypts m_a and m_b, but Alice and Bob do not read each other's messages. Instead they read Mallory's messages. If Mallory does not know how to react appropriately in order to impersonate Alice and Bob, she risks detection. As noted previously, if Mallory already knows how either Alice or Bob would react to any situation, she does not need to perform a MITM attack in the first place, and could directly impersonate one side of the conversation to gather the information she wants from the other side. Therefore it is exactly the situations in which the MITM attack would be useful to Mallory that the risk of detection is highest.

Use Cases

This method can be used in a client-server scenario. This use case will be developed in another document.

This method can be used in a video conference context, by having each side commit a speakable nonce, then revealing the nonce only after the call has started, and reading out loud the nonces. (To the user this would be similar to the old speakable nonces in Signal.)

Credits / Citations / Development History

June-October 2017: Andy Lee uses symmetric authenticated encryption to perform the pre-commit. In this version, the MITM attacker can read the initial message once the keys are exchanged, even if they did not tamper with anything.

October 2017: Ryan Hileman clean-rooms a similar protocol starting from the security goals. He uses an HMAC to perform the pre-commit, which means that the MITM attacker can no longer obtain the plaintext after the key exchange, if they did not tamper with the key exchange and substitute their own key.

November 2017: In order to resist preimage attacks on the HMAC for low-entropy, Andy Lee uses another set of symmetric keys to encrypt the plaintext. The pre-commit now happens on ciphertexts. In this scheme the legitimate users can authenticate the HMACs before deciding expose their plaintext message contents. Furthermore, the HMAC is done with the hash of the message as the key, in order to be consistent with the specification of HMAC.

December 2017: First public gist.

July 2018: Revision with extra precautions. Instead of directly using symmetric keys, they are passed through a secure hash function first.

Notes

Could be a good use for VRF. Also, a digital signature could be used in place of HMACs. Whether or not this is advantageous will explored further.

Rights

This protocol is placed in the public domain (CC0).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment