1124 lines
52 KiB
Plaintext
1124 lines
52 KiB
Plaintext
==Phrack Inc.==
|
|
|
|
Volume 0x0e, Issue 0x44, Phile #0x0e of 0x13
|
|
|
|
|=-----------------------------------------------------------------------=|
|
|
|=-----------=[ Secure Function Evaluation vs. Deniability ]=------------=|
|
|
|=------------------=[ in OTR and similar protocols ]=-------------------=|
|
|
|=-----------------------------------------------------------------------=|
|
|
|=-----------------------=[ greg <greg@so36.net> ]=----------------------=|
|
|
|=-----------------------------------------------------------------------=|
|
|
|
|
--[ 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 -------- <OT> -----------> A \
|
|
O <------- <OT> ------------ A |
|
|
O -------- <OT> -----------> 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 -------- <OT> -------------> A \
|
|
O <------- <OT> -------------- A |
|
|
O -------- <OT> -------------> 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 -------- <OT> -------------> A \
|
|
O <------- <OT> -------------- A |
|
|
O -------- <OT> -------------> 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 -------- <OT> -------------> A |
|
|
O <------- <OT> -------------- A | Compute MAC_m2'(AES_c'(X_A)). Both
|
|
O -------- <OT> -------------> 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 -------- <OT> -----------> A \
|
|
O <------- <OT> ------------ A |
|
|
O -------- <OT> -----------> 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 -------- <OT> -----------> A \
|
|
O <------- <OT> ------------ A |
|
|
O -------- <OT> -----------> 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 -------- <OT> -------------> A \
|
|
O <------- <OT> -------------- A | Compute MAC_mk(T_A). Both
|
|
O -------- <OT> -------------> 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
|