==Phrack Inc.== Volume 0x0e, Issue 0x44, Phile #0x0e of 0x13 |=-----------------------------------------------------------------------=| |=-----------=[ Secure Function Evaluation vs. Deniability ]=------------=| |=------------------=[ in OTR and similar protocols ]=-------------------=| |=-----------------------------------------------------------------------=| |=-----------------------=[ greg ]=----------------------=| |=-----------------------------------------------------------------------=| --[ Contents 1 - Introduction 1.1 - Prelude 2 - Preliminaries 2.1 - Diffie-Hellman 2.2 - RSA 2.3 - Oblivious Transfer 2.4 - Secure Function Evaluation 3 - OTR 4 - The Attack 4.1 - Sharing Diffie-Hellman Keys 4.2 - Generating MAC and Encryption Keys 4.3 - Sending and Receiving Messages 4.4 - The Final Protocol 4.5 - What's Left 5 - References 6 - Greetingz --[ 1 - Introduction Recent cryptographic primitives and protocols offer a wide range of features besides confidentiality and integrity. There are many protocols that have more advanced properties, such as forward secrecy, deniability or anonymity. In this article, we're going to have a deeper look at deniability in communication (e.g. messaging) protocols. One protocol that claims to offer deniability is OTR. Although our construction can probably be extended in a quite general way, we'll stick with OTR as an example protocol. Our goal is to show the limits of deniability, especially in protocols that offer message integrity features (as OTR does). We will do this by constructing a protocol that enables each partner in a conversation to cooperate with an observing party, such that he can prove the authenticity of any message that was part of the conversation to the observing party. ------[ 1.1 - Prelude It was one of these days sitting together with bruhns and discussing stuff (TM). Out of the sudden, he came up with the question: "You know, I'm asking myself what a trusted timestamping service could be good for...?". I told him "timestamps, most probably". He was like "Uhm, yes. And wouldn't that affect the deniability of OTR somehow?". We discussed the matter for quite a while and we finally agreed that a trusted timestamping service itself wouldn't be enough to destroy the deniability of OTR. But our interest remained... --[ 2 - Preliminaries In this section, we're going to give a quick overview of cryptographic primitives we're gonna use. If you're already familiar with those, you can happily skip our explanations and get to the real meat. The explanations in this section will not contain all the mathematical background (i.e. proofs ;) ), which is necessary to really *understand* what's going on. We'd rather like to provide a high-level overview of how all the individual components and how they can be combined. ------[ 2.1 - Symmetric Operations We'll keep this real short; you probably know the most common symmetric crypto algorithms. We will be using symmetric block ciphers (such as AES) and hash functions (SHA for instance). Also, we will need MAC functions in the following sections. You might already know HMAC, which is a MAC scheme based on hash functions. MACs (Message Authentication Codes) are used to protect the integrity of messages. Being a symmetric primitive, creating and verifying the MAC requires knowledge of the same key. If someone can verify a MAC, they can also create one. ------[ 2.1 - Diffie-Hellman The Diffie-Hellman scheme is one of the most widely used key establishment protocols today. The basic idea is the following: Alice and Bob want to securely establish a key over an insecure channel. Diffie-Hellman enables them to do this. During such a key-exchange both parties publicly send some values and after the communication is finished, both can compute a common key, which can *not* be computed by anyone who wiretaps the communication. --------[ 2.1.1 The Math behind it Alice and Bob agree on a prime p and some "generator" g. We won't discuss too many details of the mathematical background here (if you're interested in math, refer to [1]), so it's sufficient to say that in practice, g will often have the value 2 and the prime p will be large. In many cases, p and g are fixed parameters, on which both parties rely. Before describing the actual protocol, we want to show one interesting observation: Given some number x, it's trivial to compute values y = g^x mod p ("square and multiply" are the magic words). Given the value y however, it's not trivial at all to compute the value of x ("discrete logarithm problem", if you're interested). This property can be used to build a key-establishment scheme like this: A --------------- a = g^x mod p --------------> B A <-------------- b = g^y mod p --------------- B A picks a random x, computes a = g^x mod p and sends that value over to B. B picks a random y, computes b = g^y mod p and sends that value over to A. The values a and b are also referred to as Diffie-Hellman public keys. A now performs the following computation: (2.1.1) ka = b^x mod p B does the same and computes (2.1.2) kb = a^y mod p We can observe that due to the equation (2.1.3) ka = b^x mod p = (g^y)^x = g^(yx) = g^(xy) = (g^x)^y = a^y = kb ka and kb are equal. So A and B have established a common key k (k = ka = kb). As an attacker however neither knows x nor y, he cannot perform the same computation. The attacker could try to obtain x from a, but as we outlined above, this is (hopefully) computationally infeasible for large primes p and good generators g. In case of an active attacker, this scheme can be broken by a simple man-in-the-middle attack, where the attacker replaces Alice's and Bob's values by his own ones and then proxies the traffic between both parties. This problem can be fixed by making use of an authentication scheme: Alice and Bob need to "sign" the values that they transfer, so that the attacker cannot modify them without destroying the signature. There are many signature schemes out there (for instance based on RSA, which is described below) and all of them come with additional costs (you need to exchange public keys beforehand etc.). We assume you know about all the higher-level problems, such as key distribution, revocations, trust-models, etc. The basic principle of Diffie-Hellman however stays the same - and that is what we're going to focus on later in this article. ------[ 2.2 - RSA Another gem of modern cryptography is the RSA crypto system. RSA is also based on modular arithmetic, but it works in a different way than Diffie-Hellman. Alice wants Bob to send her an encrypted message. However, Alice and Bob have not exchanged any key material (if they had, Bob could just make use of any block-cipher like AES to send encrypted data to Alice). With RSA, Alice can send Bob a thing called her "public key". This public key can be used by Bob to encrypt messages. However, nobody can decrypt messages encrypted with Alice's public key without knowing another piece of information called Alice's "secret key". As the name suggests, Alice keeps her secret key secret. Therefore everybody can encrypt messages for Alice, but nobody besides Alice can decrypt these messages. --------[ 2.2.1 More Math Alice wants to receive messages from Bob, so she first needs to generate an RSA key-pair. Alice does the following: She picks two primes p and q and computes (2.2.1) N = p * q She picks a value e (in practice, e = 65537 is a common choice) and computes (2.2.2) d = e^-1 mod (p-1)(q-1) (i.e. e*d = 1 mod (p-1)(q-1)) This computation can be performed efficiently using the extended euclidean algorithm (but again, we won't dive into all the mathematical details too much). Alice keeps all the values besides N and e secret. A ---------------- N = p * q, e --------------> B A <--------------- c = m^e mod N --------------- B Alice now sends over N and e to Bob. Bob uses N and e to encrypt his message m as follows: (2.2.3) c = m^e mod N Then, Bob sends the ciphertext c over to Alice. Alice can use d to decrypt the ciphertext: (2.2.4) m = c^d mod N This works due to the way e and d are chosen in equation (2.2.2). To decrypt the ciphertext, an attacker could of course try to compute d. But computing d is hard without knowing p and q. And obtaining p and q from N is assumed to be an infeasible problem for large values of N. The tuple (N, e) is commonly called an RSA public key, whereas (N, d) is called private key. We can view an RSA instance (with fixed keys) as a set of two functions, f and f^-1, where f is the function that encrypts data using the public key and f^-1 is the function that decrypts data using the private key. We'll call such functions one-way functions. Instead of encrypting data with the receiver's public key, we can also use RSA as a signature scheme. The signer of a message first uses a hash function on his message. He then encrypts the hash value with his private key. This signature can be verified using the signer's public key: the verifier uses the public key to decrypt the hash value, computes the hash of the message he received and then compares the hashes. An attacker will not be able to produce such a signature, because he doesn't know the signer's private key. Please be aware that (like all the other algorithms described in this document), RSA should in practice not be used as described above. In particular, we did not describe how to correctly convert messages into numbers (RSA operates on natural numbers, remember?) and how to securely pad plaintexts. Depending on the respective security goals, there are a number of possible padding schemes (such as OAEP+), but we're not going to describe them here in detail. ------[ 2.3 - Oblivious Transfer Oblivious transfer is a real funny primitive. Suppose, Bob knows two values x0 and x1. Alice wants to obtain one of those values, but she doesn't want to tell Bob which value she wants. Now Bob could of course tell Alice both values (that way he wouldn't know, which one Alice was interested in). However, Bob wants to make some money and so he takes $1k per value. Poor Alice however only has $1k, so she can't afford to buy both values from Bob. This problem can be solved with an oblivious transfer. An oblivious transfer is a cryptographic protocol, so it requires a number of messages to be exchanged between Alice and Bob. After the messages are exchanged, Alice will receive the value she wanted and Bob won't know which value that was. --------[ 2.3.1 Math Voodoo There are a number of protocols for performing an oblivious transfer, based on different cryptographic assumptions. We are going to describe one classical example here, which can be implemented using a public-key cryptosystem (such as RSA). More details of this construction can be found in [7]. The system works like this: Bob picks one-way functions f, f^-1 and sends f over to Alice. Along with f, he sends two random values r0 and r1. You can think of f and f^-1 as RSA functions using fixed keys (as described above). A <---------------- f, r0, r1 -------------- B A ------------- z = f(k) XOR rb -----------> B Alice wants to receive value xb (b = 0 or 1) from Bob. She picks a random k, computes f(k) and XORs it with r0 if she wants to receive x0 or with r1 if she wants to receive x1. The XOR operation is sometimes also called "blinding". Depending on the cryptosystem that is used to obtain f and f^-1, there might be more appropriate choices then just using XOR. For RSA, it would be natural to use integer addition and subtraction (modulo N) instead of the XOR operation. Alice now sends the result z to Bob. Bob performs some computations: (2.3.1) k0 = f^-1(z XOR r0) (2.3.1) k1 = f^-1(z XOR r1) One of the k values will be Alice's, but Bob doesn't know which one. The other value will be junk, but it's important to note that this junk value cannot be computed by Alice (she doesn't know f^-1). Now Bob simply does the following: A <---------- x0 XOR k0, x1 XOR k1 --------- B Depending on which k value is the one that Alice actually knows, she can decrypt x0 or x1. And that's it: Alice now knows the value she wanted to receive and one junk value, which doesn't tell her anything. Bob however doesn't know which of the k values was the one that Alice picked, so he he cannot tell, which value Alice wanted to receive. Let's try it out: Say Bob hast two values x0 = 7 and x1 = 1. He is willing to share one with Alice. First he generates f and f^-1. To do that, he just uses RSA. He picks two prime numbers p = 5 and q = 11 and gets N = 55. Also, he picks e = 3 as encryption exponent (don't do that at home, kids!). The decryption exponent would then be d = 27 (you can compute that using the euclidean algorithm or alternatively you could just believe us). Bob now can send out (N, e) = (55, 3) to Alice, along with some random values (r0, r1) = (4, 9). Suppose Alice wants to retrieve the value of x1. First of all, she picks a random k, let's say k = 6. She encrypts it using the public key Bob sent (i.e. she applies Bob's one-way function): f(6) = 6^3 mod 55 = 51. She computes z = f(k) + r1 = 51 + 9 mod 55 = 5, which she sends to Bob. Bob now determines his candidates for k (i.e. k0 and k1) by computing: k0 = f^-1(z - r0) = (5 - 4)^27 mod 55 = 1 k1 = f^-1(z - r1) = (5 - 9)^27 mod 55 = 6 <-- Alice's k, but Bob doesn't know that Bob then sends to Alice: x0 + k0 = 7 + 1 and x1 + k1 = 1 + 6. Alice receives the two values 8 and 7. She knows that Bob's second value was x1 + k. As she is interested in x1, she takes that value and computes x1 = (x1 + k1) - k = 7 - 6 = 1 (observe that k = k1, which only Alice knows). Now Alice could try to cheat and to also obtain x0. But to do that, she would need to know the value that Bob computed for k0, which she won't be able to compute without knowing f^-1 (i.e. the secret exponent d in our case). ------[ 2.4 - Secure Function Evaluation Secure function evaluation is another real gem of modern cryptography. A classical example is the 0day problem. Two hackers A and B have a certain number of 0day exploits each. They want to determine who is more elite, but they are so paranoid that they don't even want the other to know how many 0days they have. So, A knows some number x, B knows y and both want to compute the function f(x, y) = { 1 if x > y, -1 if y > x and 0 otherwise}. Secure Function Evaluation solves this problem. Again, both parties exchange a number of messages and after this is done, both of them know the result of the function without having learned anything about the input of the other party. And instead of the function shown above, they could just arbitrarily agree on any function to be evaluated. One interesting practical application of SFE is to perform mutual authentication based on a shared secret. Two parties knowing a shared secret can jointly compute the function f(x, y) = {1 if x = y, 0 otherwise}. Interestingly, the OTR protocol makes use of such a SFE scheme for authentication. --------[ 2.4.1 More Voodoo Suppose there is a function f(x, y), which two parties want to compute (this is actually secure two-party computation, which is not the most general case - for our purpose however it is sufficient). Both want to share the result and both want to keep their own inputs safe. There are several constructions that allow us to perform SFE. We'll discuss only one of them here: Yao's garbled circuits [3]. As the name suggests, the function to be evaluated by both parties first has to be transformed to a boolean circuit. For many functions, this is generally not a problem. The next step is to "garble" the circuit. The main idea behind this garbling process is that we want everyone to be able to evaluate the circuit, while nobody should see what he actually evaluates. Therefore, we will try to hide all the bits that "flow" through the circuit. For hiding the bits, we could make use of a block cipher. However, we have to take care that the circuit can still be evaluated! Therefore, we will also have to modify all the gates in the circuit somehow, so that they are able to work with "garbled" inputs. Now one could imagine that such a modification is a hard task. Fortunately, there's a simple trick: All the gates in our circuit are very small boolean functions (by small we mean that they don't have many inputs). We can therefore replace every gate by its truth table. The truth table simply maps the input bits to the respective output bits. For a simple NAND gate, the truth table would look like this: \a| b\| 1 0 --+---- 1 | 0 1 0 | 1 1 Now that we have replaced every gate by its truth table, we will just have to modify the truth tables, so that they reflect the fact that all the bit values are garbled. The trick here is the following: Instead of the real values of the input bits (1 or 0), we pick random cryptographic keys (say 128 bits long). We will then use those keys to encrypt the values in the truth table. Instead of the input values for the gate, we will then use the random keys (i.e. instead of 1 or 0, we just pick two random bitstrings per wire). As an example, consider a NAND gate again. We choose four keys ka0, ka1, kb0 and kb1. Those are the keys for the respective input values of the gate (i.e. a=0, a=1, b=0, b=1). Also, we pick an encryption function E and a decryption function D. For simplicity, we assume that if a wrong key is supplied to D, it will signal this (e.g. return an error code) instead of providing a junk plaintext. We now perform the following transformation on the truth table of our gate: \a| \ a| b\| 1 0 b \ | 1 0 --+----- -----> ---------+-------------------------------- 1 | 0 1 1 | E_ka1(E_kb1(0)) E_ka0(E_kb1(1)) 0 | 1 1 0 | E_ka1(E_kb0(1)) E_ka0(E_kb0(1)) The elements in the truth table are double encrypted using the two keys that belong to the values of a or b, respectively. When evaluating the circuit, you only know the keys that correspond to the correct input values (so for example you know ka0 and kb1 but no other key). By simply trying to decrypt every value in the table, it is easy to find the according output value (only one decryption will succeed). The next question would then be: How to garble a whole circuit? It's not much different. Assume that two gates are connected like this: Out | +------+ | G1 | +------+ | | +---+ In_3 |G2 | +---+ | \ In_1 In_2 We have inputs In_1, In_2, In_3 and one output value Out. G2's output is connected to one of the input wires of G1. In the truth table of G2, we therefore put the *key* that corresponds to the respective input value of G1 (so instead of double-encrypting G2's output value 1 or 0, we double-encrypt the respective key for one of G1's input pins). The gate G1 can be garbled as described above. The keys for the input wires In_1, In_2 and In_3 are assumed to be already known by the party evaluating the circuit. G2 can now easily be evaluated and yields the missing key for evaluating the gate G1. However, during the evaluation of the circuit, no intermediate values (like the real output of G2) are disclosed to the evaluating party. Let's try that in practice: Say Alice and Bob want to evaluate a function. The following protocol can be used: A prepares a garbled circuit and hard-codes her input values into the circuit. She sends the result to B. B now needs to retrieve the keys for his input values from A. But beware of two limitations here: 1) B doesn't want to disclose his input values to A (obviously). 2) A doesn't want to tell B the keys for both input values, because then B would be able to reverse-engineer the circuit and to obtain A's input values. You've probably already seen the solution: B uses an oblivious transfer to obtain the keys for his input values from A. For every bit b of his input values, Bob will obliviously obtain the correct key k_b0 or k_b1 like this: A ---------------- f, r0, r1 --------------> B A <------------- z = f(k) XOR rb ----------- B A -------- k_b0 XOR k0, k_b1 XOR k1 -------> B B is now able to evaluate the whole circuit. Depending on how A built the circuit, the output truth tables could contain real or garbled values. Using some simple tricks, we can even split the output between A and B (so that A gets some part of the result and B gets another part). We'll detail on that later. Now there are some problems when one party isn't honest. Alice for instance could just prepare a malicious circuit that leaks information about Bob's secret inputs. There are ways to prevent such attacks ("cut and choose", zero knowledge proofs, etc), but we won't provide the details here. A more detailed description (along with a security proof) can be found in [3]. --[ 3 - OTR For those who are not familiar with the OTR protocol, this section might provide some help. OTR features a number of cryptographic properties, including confidentiality, integrity, forward secrecy and deniability. There are two major phases of the protocol: initial key exchange and message exchange. The initial key exchange is based on the Diffie-Hellman protocol. It is referred to as AKE (Authenticated Key Exchange). To defend against active attackers, a public-key signature scheme (DSA in this particular case) is used. The DSA master keys have to be exchanged beforehand (OTR also offers to authenticate DSA keys using the SMP protocol, but that's not interesting in our case). All the cryptographic details are provided in [2]; it's not particularly helpful to repeat them here. Keeping in mind that OTR's key exchange is based on Diffie-Hellman combined with some symmetric crypto and a signature scheme will suffice. After the key-exchange phase, each party will have a number of symmetric keys for encryption and authentication. Those are derived from the Diffie-Hellman master key by hashing it in various ways (encryption and MAC key will obviously be different). The messages are encrypted using AES in CTR mode, and each message is MACed using the symmetric key material. That offers us confidentiality and integrity. It's important to note that *only* symmetric keys are used for the actual payload crypto. The DSA master keys are only used in the initial key-exchange phase. The next feature we're going to look at is forward secrecy. Forward secrecy means that even if the (DSA) key of a participant is disclosed, past conversations cannot be compromised. Forward secrecy in OTR is established by the Diffie-Hellman protocol: after a conversation ends, both parties can safely wipe the Diffie-Hellman key that they generated. There is no way for an attacker (and not even for the conversation partners) to re-compute that key afterwards: to do that, one would either need to know the private exponent of one party (which is of course also wiped from memory) or one would need to derive the key from the public information exchanged between both parties, which is infeasible (hopefully; that's what Diffie-Hellman relies on in the first place). Having understood how OTR provides forward secrecy, we can move on to deniability. During the conversation, both parties can be sure that the messages they receive are authentic and not modified by an attacker. It is immediately clear that the message authenticity can not be verified without the MAC key. If one of the conversation partners wants to convince a third party that a message is authentic, this conversation partner implicitly proofs his knowledge of the MAC key to the third party. But then again, the third party can not be sure that the conversation partner didn't fake the message (he can do this as he knows the MAC key). This is what we call weak deniability [4]. Obviously, OTR offers weak deniability, as message authentication is performed using only symmetric primitives. But OTR offers even more: In every message, the sending party includes a new Diffie-Hellman key exchange proposal. The proposal is also covered by the MAC to rule out MITM attacks. So both parties frequently generate new key material. And this lets us do a nice trick: as soon as they generate new MAC keys they publicly disclose the old MAC keys. The old keys aren't used anymore, so this is safe. But as the MAC keys are public, *everybody* could create fake messages and compute proper MACs for those. This is what we call strong deniability. OTR ships with a toolkit containing software for actually forging messages. Depending on how much you already know (only the MAC keys, MAC and encryption keys, MAC keys and some message plaintext), you can use different tools to forge messages. If you know parts of the plaintext and the MAC keys, you can exploit the fact that AES is used in CTR mode to directly modify the known parts of the plaintext. If there is no known plaintext, the otr_remac tool might helpful: Every message contains a new Diffie-Hellman key exchange proposal in plaintext (but covered by the MAC). Now you can simply replace that proposal by one that you generated (e.g. using the otr_sesskeys tool) and compute a new MAC for the packet. That allows you to easily fake the rest of the conversation: You know your own private Diffie-Hellman key, so you can generate a plausible set of MAC and encryption keys and just use that one. It will look legitimate because the modified packet (containing your key exchange data) still has a valid MAC. --[ 4 - The Attack The deniability of OTR stems from the fact that a third party does not know whether a message has been sent during a conversation (and before the MAC keys were disclosed) or was generated afterwards (when the MAC keys were public). An obvious way to attack OTR's deniability would therefore be to just monitor all the OTR traffic between A and B. If one party now decides to disclose the MAC and encryption keys used for a particular message, the authenticity of that message can be verified. And as the message has been recorded during the conversation (i.e. before the MAC keys were public), the recording party knows that it was not generated afterwards. Let's look at a real-life example to shed some more light on what we're doing. Imagine two hackers A and B who want to talk about serious stuff (TM) using OTR. Both of them are slightly paranoid and don't trust each other. In particular, Bob fears that Alice might backstab him. However, as OTR is deniable, Bob assumes that even if Alice discloses the contents of their conversation, he could still plausibly argue that Alice just made it up to discredit him. So Bob ignores his paranoia and tells Alice his secrets. Alice indeed plans to backstab Bob. Her first plan is simple: She will just submit all the encrypted and authenticated messages to the police. The police will later be able to state in court that Alice didn't fake the messages after the conversation. She however quickly realizes that this approach is inherently flawed: Bob could argue that Alice just sent fake messages to the police (as Alice knows all the keys she could generate such fake messages). Alice knows that this problem could be fixed if the Police sniffed all the traffic themselves. But she also knows that this is going to be difficult, so she comes up with a second idea: Why not use a trusted third party? Instead of submitting her messages to the police, she will just disclose her private DSA key to her lawyer. Then, during her conversation with Bob, she will use her lawyer as a proxy (i.e. she will let *him* do the crypto). This way the lawyer can be sure that the conversation is authentic. The judges will trust Alice's lawyer in court (at least they'll trust him more than they trust Alice), so her problem is solved. Alice's setup would look like this: +-------+ | Alice | +-------+ ^ | Non-OTR (maybe SSL) v +------------+ | Lawyer | trust +----------------+ | Speaks for | <---------> | Police / Court | | Alice | +----------------+ +------------+ ^ | OTR (Bob thinks he talks to Alice) v +-------+ | Bob | +-------+ But now Alice realizes that she doesn't trust her lawyer enough to give him her private DSA key: He could misuse it to impersonate her. Also, Alice doubts that her lawyer's words would be trusted enough in court. This example shows the problems that Alice has when she wants to break the deniability of OTR. Her problems can be summarized as follows (we'll now call the police the "observing party" and the lawyer will be called "trusted third party"): a) The observing party needs to sniff the network traffic. That implies quite a privileged network position, as the traffic needs to be sniffed passively, i.e. without the help of A or B. Because if A or B would send their traffic to the observing party, A or B might just insert bogus messages into their "sniff" stream and the observing party couldn't be sure about the authenticity. Even worse, paranoid A and B could use an anonymizing network, so that sniffing their traffic would be a non-trivial task. b) Also, the authenticity of a message can only be proven to the observing party, but not to anybody else (as anybody else didn't sniff the traffic and the observing party could just have cut some pieces or inserted new ones). Problem b) is not that much of importance. Just imagine the observing party as the police, the judges or even Fnord. You should always assume that the observing party is exactly the guys you wanna protect yourself against. If you think that the police probably won't even get all the crypto stuff and therefore just believe any plaintext logfile you show them, that's OK (you're probably right). There might however be agencies that would not really trust plaintext logs. And those agencies might be very interested in the contents of some OTR conversations. Problem a) remains open. Obviously, neither A nor B really trust the observing party. If we had a trusted third party, we actually could mount an attack against OTR's deniability, just as described in the lawyer example above. Well, lucky us, neither A, nor B, nor the observing party trust anybody and therefore, there will be no trusted third party ;) Really? Interestingly, a trusted third party can be emulated using secure function evaluation. This is what we didn't tell in the section above: You can view a secure function evaluation scheme as a replacement for a trusted third party. So instead of letting a third party compute some function f(x, y), A and B can perform the computation on their own and still get the same result: both players only receive f(x, y) but A doesn't see y and B doesn't see x. So the main idea of our attack is: Emulate a trusted third party using secure function evaluation. The setup that Alice now plans is the following: +-------+ | Alice |<-----------+ +-------+ | ^ | | | SFE Voodoo for emulating the lawyer | | | v | +----------------+ | | Police / Court | | +----------------+ | | OTR | v +-------+ | Bob | +-------+ Our central idea is the following: A can send all the messages she received from B to the observing party (the police in the figure above, but that could really be everyone). The messages are still encrypted, so this is not a problem. To make sure that the messages are not faked by A, we need to make sure that A cannot produce valid MACs without the help of the observing party. We therefore share the MAC key between A and the observing party. Every time, A wants to validate or produce a MAC, she has to cooperate with the observing party. Later on, A can reveal the encryption key for any message to the observing party, which can be sure that the message is authentic. In the following section (4.1 - 4.3), we will provide a high-level overview of the attack. In section 4.4, you can find the actual protocol that Alice and the observing party use. ------[ 4.1 - Sharing Diffie-Hellman Keys OTR uses Diffie-Hellman to establish sort-lived MAC and encryption keys. The first part of our exercise is therefore to build a Diffie-Hellman compatible 3-party protocol that allows for sharing the generated key between two parties. The following protocol between Alice (A), Bob (B) and the observing party (O) works: O ----- g^o ----> A ---- (g^o)^a ----> B O <---- g^a ---- A A <--- g^b ---- B All computations are done modulo some prime p and g is a generator of a sufficiently large subgroup of Z_p*, just as Diffie-Hellman mandates. B will now compute g^oab as key. However, neither A nor O can reproduce that key. If A wanted to compute it, she would need to know O's secret exponent o. Similar for O. We can therefore say that the key k is shared between O and A, in the sense that A and O need to cooperate in order to actually use it. ------[ 4.2 - Generating MAC and Encryption Keys Now that we have established a shared Diffie-Hellman key, we need to securely derive the MAC and encryption keys from it. Let's assume we have a circuit C, which takes the shared Diffie-Hellman key k as input and returns the corresponding MAC and encryption keys as output. This circuit follows immediately from the OTR specification. Before we can evaluate the circuit, we first need to compute k (which neither A nor O know at this time). So the overall function that A and O want to compute is: f(a, o) = C(((g^b)^a)^o mod p) We can transform this function to a new circuit and evaluate it together (i.e. A and O evaluate the circuit). After the evaluation, A could get the encryption keys. But that's not a good idea, because the OTR spec mandates that MAC_key = hash(encryption_key). If A knew the encryption key, she could compute the according MAC key. Also, it would be bad if O would get the MAC keys, because then O could impersonate A and B. Therefore, we'll slightly modify the circuit, so that A may pick a random bit string, which the circuit XORs to the MAC key and to the encryption key (assuming the random string is long enough for both keys). The "blinded" MAC and encryption keys are then provided to A and O, the bitmask remains in A's memory. If they want to use one of the keys for something, they will evaluate a circuit that first XORs both halves together and then does the actual computation using the key. At no point in time, A or O actually learn the MAC or the encryption key. Now that we know how to generate all the symmetric key material, we are able to perform the full initial key exchange phase of OTR. ------[ 4.3 - Sending and Receiving Messages When A receives a message from B, she cannot immediately decrypt it because she doesn't know the decryption key. Also, verifying and sending messages needs O's cooperation. 1) Message Decryption If A wants to decrypt one of B's messages, she cooperates with O. Both parties will jointly evaluate a decryption circuit. The circuit will be built in such a way that only Alice will learn the result (i.e. Alice will again provide a random bitstring as input the the circuit, which is XORed to the result). 2) Message Verification If A wants to verify one of B's messages, she has to cooperate with O. A and O will jointly evaluate some sort of HMAC circuit, in order to find out whether a message is authentic or not. We can design the message verification function in such a way that O will immediately learn the encrypted message and the MAC verification result. This enables A to afterwards reveal the encryption key for a particular message, so that O will be convinced A didn't fake it. 3) Message Creation When A wants to create a message, she encrypts it together with O, just as described in 1). In order to compute a MAC for the message, A and O again cooperate. As each message has to contain a new Diffie-Hellman public key, A and O will jointly compute such a key using the scheme outlined above. ------[ 4.4 - The Final Protocol In this section we'll describe our final protocol. It offers the following features: * We have three parties: A, B and O. A and O cooperate to backstab B. B is not able to deny any of his messages towards O. * O will not learn any message plaintext, unless A explicitly tells O the respective keys. * O is not able to impersonate neither A nor B. * No trust relation between A and O is required. * A does not have to disclose a whole conversation to O; it is possible to only disclose selected messages. * B does not notice that A and O cooperate. ---------[ 4.4.1 - Initial Key-Exchange This section describes OTR's authenticated key-exchange (AKE). Bob starts the key exchange by picking a random r and x and sending AES_r(g^x), HASH(g^x) to Alice. That's the regular OTR protocol. Alice then does a Diffie-Hellman key-exchange with O as outlined in section 4.1. We assume that A and O communicate over a secure channel. O A <-------- AES_r(g^x), HASH(g^x) ----- B O <------- g^a ------------- A O -------- g^o ------------> A Now Alice sends her Diffie-Hellman public key to Bob. Note that she doesn't know the private exponent of the key: she knows only a and g^ao, but neither ao nor o. A ------------------ g^ao ------------> B Bob has already computed the common key k (which Alice can't do) and uses it to derive encryption keys c and c' and MAC keys m1, m1', m2, m2' (see the OTR specs [2] for details) by hashing k in various ways. Bob builds the following messages: M_B = MAC_m1(g^x, g^ao, pub_B, keyid_B) X_B = pub_B, keyid_B, sig_B(M_B) Where pub_B is Bob's public DSA key and keyid_B is an identifier for Bob's Diffie-Hellman proposal g^x. sig_B is created using Bob's DSA key. Using the already derived symmetric keys, he sends AES_c(X_B),MAC_m2(AES_c(X_B)) over to Alice. A <- r, AES_c(X_B),MAC_m2(AES_c(X_B)) - B Alice is now supposed to also derive all the symmetric keys and to use them to decrypt and verify the stuff that Bob sent. But Alice cannot do that, so she cooperates with O. O sends her a garbled circuit C1, which will compute C1(o, a, mask) = (c, c') XOR mask Alice randomly chooses mask, so only she will learn c and c'. In a number of oblivious transfers, Alice receives the keys for her input values from O. O --------- C1 ------------> A\ \ O -------- -----------> A \ O <------- ------------ A | O -------- -----------> A | Compute c, c' using SFE. Only A . | receives the values. . | . / O <----- eval(C1) ---------- A / O --- (c,c') XOR mask -----> A/ Now Alice is finally able to decrypt the stuff that Bob sent her. She does so and gets X_B. Currently, she is not able to verify the MAC_m2() value Bob sent - she'll do that later. First she sends sig_B(M_B) over to O. O <------- sig_B(M_B) ------ A In order to actually verify sig_B(M_B), A and O first need to compute M_B. As described above, M_B = MAC_m1(g^x, g^ao, pub_B, keyid_B). In order to compute that MAC, both parties again need to cooperate. O creates a circuit C2, which computes: C2(o, a, pub_B, keyid_B) = MAC_m1(g^x, g^ao, pub_B, keyid_B) Alice again uses oblivious transfers to obtain the keys for her secret input value a, evaluates the circuit and both parties obtain the result M_B. O --------- C2 --------------> A\ \ O -------- -------------> A \ O <------- -------------- A | O -------- -------------> A | Compute M_B using SFE. A and O . | receive the value. . | . / O <----- eval(C2) ------------ A / O -------- M_B --------------> A/ Now that both have computed M_B, they first check the signature sig_B(M_B), just as the OTR protocol mandates. If A and O are convinced that sig_B(M_B) is OK, they can verify the MAC_m2(...) that B sent earlier. Again, they perform some SFE voodoo to do that. The observing party prepares a circuit C3, which computes: C3(o, a, AES_c(X_B)) = MAC_m2'(AES_c(X_B)) A again uses oblivious transfers to obtain the keys for her input values and the result is shared between both parties. O --------- C3 --------------> A\ \ O -------- -------------> A \ O <------- -------------- A | O -------- -------------> A | Compute MAC_m2'(AES_c(X_B)) using . | SFE. Both receive the result. . | . / O <----- eval(C3) ------------ A / O --------- MAC -------------> A/ Now A and O are convinced that the key exchange with B succeeded. But they still need to convince B that everything is OK. In particular, OTR mandates that A should compute M_A = MAC_m1'(g^ao, g^x, pub_A, keyid_A) X_A = pub_A, keyid_A, sig_A(M_A) and then send AES_c'(X_A), MAC_m2'(AES_c'(X_A)) over to B. Computing the AES part can be done by A, because A knows the key c'. But for computing the MAC, A and O again need to cooperate. First, A sends AES_c'(X_A) over to O. Then O prepares a circuit C4, which computes: C4(o, a, AES_c'(X_A)) = MAC_m2'(AES_c'(X_A)) Using oblivious transfers, Alice obtains the keys for her inputs from O. After evaluating the circuit, A and O obtain MAC_m2'(AES_c'(X_A)). O <----- AES_c'(X_A) -------- A\ O --------- C4 --------------> A \ \ O -------- -------------> A | O <------- -------------- A | Compute MAC_m2'(AES_c'(X_A)). Both O -------- -------------> A | parties receive the value. . | . / O <----- eval(C4) ------------ A / O -- MAC_m2'(AES_c'(X_A)) ---> A/ That's it. A can now send all the required values to B. - AES_c'(X_A), MAC_m2'(AES_c'(X_A)) -> B B verifies all the stuff (just like A did but without the SFE) and the key exchange is done. ---------[ 4.4.2 - Message Exchange Once they have exchanged their initial key material, Alice and Bob can exchange actual messages. Suppose, Alice wants to send a message to Bob; we'll restrict ourselves to that scenario. Receiving messages works similar. Alice now does the following (from the OTR protocol spec [2]): Picks the most recent of her own Diffie-Hellman encryption keys that Bob has acknowledged receiving (by using it in a Data Message, or failing that, in the AKE). Let key_A be that key, and let keyid_A be its serial number. If the above key is Alice's most recent key, she generates a new Diffie-Hellman key (next_dh), to get the serial number keyid_A+1. To do this, Alice again needs to cooperate with the observing party. The steps are exactly the same as we have already seen in the initial key-exchange: O <------- g^a -------------- A O -------- g^o -------------> A Alice now uses g^ao as next_dh. When she computed next_dh, Alice picks the most recent of Bob's Diffie-Hellman encryption keys that she has received from him (either in a Data Message or in the AKE). Let key_B be that key, and let keyid_B be its serial number. Now Alice would actually need to use Diffie-Hellman to compute a fresh shared key with Bob, which she can use to derive the encryption and MAC key. But as she doesn't really know the private exponent (she knows g^ao, a and g^a, but not ao), she again needs to cooperate with O. So here we go: O prepares a circuit C1: C1(o, a, mask) = (ek, mk) XOR mask The circuit will compute both, ek and mk (the encryption and MAC keys), blinded with some value chosen by Alice. The result will be supplied only to the observing party. Alice will keep the value of mask. In a number of oblivious transfers, Alice receives the keys for her input values from O. O --------- C1 ------------> A\ \ O -------- -----------> A \ O <------- ------------ A | O -------- -----------> A | Compute (ek, mk) XOR mask using SFE. . | Only O receives the result. . | . / O <----- eval(C1) ---------- A / Alice now picks a value ctr, so that (key_A, key_B, ctr) is unique. The ctr value is needed, because AES is going to be used in counter mode to encrypt Alice's payload. The next step for Alice is to encrypt her message. As she doesn't know the encryption key, O prepares a circuit C2 for her: C2(ek_o, ek_a, ctr, msg) = AES-CTR_ek,ctr(msg) The inputs ek_o and ek_a denote O's and A's knowledge about ek, which is ek XOR mask in O's case and mask in A's case. The result of the circuit will only be provided to A (i.e. A just doesn't send it over to O). In a number of oblivious transfers, Alice receives the keys for her input values from O. O --------- C2 ------------> A\ \ O -------- -----------> A \ O <------- ------------ A | O -------- -----------> A | Encrypt msg using SFE. Only A . | receives the result. . / . / Now Alice can compute: T_A = (keyid_A, keyid_B, next_dh, ctr, AES-CTR_ek,ctr(msg)) T_A already contains Alice's message, but she still needs to MAC it. This is again done by A and O together. O prepares a circuit C3: C3(mk_o, mk_a, T_A) = MAC_mk(T_A) O --------- C3 --------------> A\ \ O -------- -------------> A \ O <------- -------------- A | Compute MAC_mk(T_A). Both O -------- -------------> A | parties receive the value. . | . / O <----- eval(C3) ----------- A / O ----- MAC_mk(T_A) --------> A/ Please be aware that Alice will keep T_A secret. Although T_A doesn't contain any plaintext, Alice does not want to disclose it to the observing party. If she did, then her own deniability would also be gone. Also, the OTR protocol mandates that Alice should send her old MAC keys in plaintext to Bob, so that they can be considered public. If A and O wanted to, they could do that (by computing the old MAC key again and sharing the result). But as long as Bob doesn't check what Alice sent, she can just send garbage. Indeed, in its current version (libotr 3.2.0), the OTR implementation doesn't check the disclosed MAC keys. Consider the excerpt from proto.c, line 657: --- snip --- /* Just skip over the revealed MAC keys, which we don't need. They * were published for deniability of transcripts. */ bufp += reveallen; lenp -= reveallen; --- snap --- So Alice can safely send: A -T_A,MAC_mk(T_A),oldmackeys=foobar-> B ------[ 4.5 - What's Left We have seen that in a scenario where at least one party cooperates with the attacker, deniability is non-trivial. Our construction can be extended and adopted and we conjecture that it quite generally applies to deniable messaging protocols. Regarding performance: Yeah, we know that all the SFE voodoo can be quite expensive. Especially modular exponentiation in circuits is not really cheap. However, there are ways to optimize the basic scheme we have outlined here. If you're interested in that, you might wanna read [5] as an introduction. Also, refer to section 4.5.2, which outlines one particular optimization of our Diffie-Hellman-scheme. Regarding network latency: When looking at all the crypto protocols outlined in this article (especially at oblivious transfers), you will notice that often multiple messages need to be exchanged. If you need 3 messages for one oblivious transfer and you want to perform 128 oblivious transfers (for some 128-bit crypto key or so), then you end up with 384 messages being exchanged. In terms of network latency, that might be troublesome. However, there are two things that help us: first, we can perform oblivious transfers in parallel (i.e. still exchange three messages but every message now contains data for 128 oblivious transfers). We can also precompute many values and exchange them before they are really needed (random values for instance). ---------[ 4.5.1 - FAQ Q: This is all bullshit! I could just share my private keys with the police, and that would also kill deniability! Yep. And the police would then be able to impersonate you. One of our key points is that you don't need to trust the observing party, neither need they to trust you. A: But the observing party won't be able to prove anything in court! Well, yes and no. In a constitutional state you'd need to actually prove stuff in court. Unfortunately, such states are rare. But even if you live in such a state, then the observing party could be the judge. Q: But all the conversations that I had before my peer cooperated with the observing party are deniable, right? A: Yes, unless the observing party sniffed your traffic (if you used a decent anonymizer, this is unlikely). Q: Wait, the observing party so far only learned that *somebody* has sent a message. But how do they know it was the person that I tell them it was? Good question. This knowledge is generated during the initial key exchange of OTR. To be precise, the observing party and the backstabber both learn the identity of the conversation peer when he signs his key-exchange proposal with his DSA key. The observing party also sees that and as they track all subsequent key-exchanges, they can build a "chain of evidence". Q: But doesn't [4] already kill the deniability of OTR? A: Ha, even better question! At least it attacks the strong deniability of OTR. However, our scheme also attacks the weak deniability. Furthermore, the attacker in [4] has far more capabilities than in our model. In [4], the attacker is able to arbitrarily read and modify network traffic. In our model, the attacker can rely on the cooperation with one of the two conversation partners. Q: OK, I'm convinced. Is there any implementation? A: You're welcome to build one ;) See section 4.5.2 for details. ---------[ 4.5.2 - How to Implement? If you want to implement the scheme outlined above, first of all, you need some framework for secure function evaluation. There are a number of implementations out there, for instance Fairplay [6] or TASTY [5]. Once you got your SFE framework running, you need to implement all the functions that need to be computed jointly. The Diffie-Hellman stuff is probably most efficient when implemented using a homomorphic cryptosystem (such as RSA or ElGamal maybe). Now you may ask: how does a multiplicatively homomorphic scheme help us computing DH keys? Well. There's some nice optimization, which basically reduces the modular exponentiation to a modular multiplication: Alice picks some random j and sends g^(ab+bj) over to the observing party. The observing party sends g^o. A <---- g^b ------------ B O <------ g^(ab+j) ------ A O -------- g^o ---------> A Note that Bob cannot compute g^abo, because Alice's value is "blinded" with j. Alice cannot do so neither; she doesn't know o. Bob however can compute g^(abo+jo). Alice can compute g^jo and also g^-jo, because she knows j. If Alice would send g^-jo to O, then O could compute g^(abo+jo) * g^-jo = g^abo This is only one modular multiplication. So instead of doing a whole modular exponentiation, the circuit that Alice and the observing party jointly compute does roughly the following: C(o, a) = derive_keys(o*a) Where the function derive_keys() is the OTR key derivation function (hashing the common key in different ways to generate symmetric key material), O's input value will look like g^(abo+jo) and A's input value will look like g^-jo. All the symmetric operations (hashes and block ciphers) should probably be implemented as circuits, for instance using Fairplay. Both SFE schemes (circuits and homomorphic crypto) can be combined using the TASTY approach. --[ 5 - References [1] http://www-ee.stanford.edu/~hellman/publications/24.pdf [2] http://www.cypherpunks.ca/otr/Protocol-v2-3.0.0.html [3] http://eprint.iacr.org/2004/175.pdf [4] http://www.jbonneau.com/OTR_analysis.pdf [5] http://eprint.iacr.org/2010/365.pdf [6] http://www.pinkas.net/PAPERS/MNPS.pdf [7] http://tinyurl.com/84z7wpu --[ 6 - Greetingz First of all I have to give a big shout to bruhns, who developed this stuff together with me! There's this one person, which I'd like to say thanks for everything (and that's quite a lot). Unfortunately, i cannot name this person here. 291646a6d004d800b1bc61ba945c9cb46422f8ac. Also a big thanks to Phrack staff for reading through all this and supplying me with real helpful feedback! Greetingz go out to the following awesome people in no particular order: ths, fabs, joern, nowin, trapflag, jenny, twice#11 --[ EOF