George Danezis has put together a great series of lectures on modern anonymous communications, available from his Conspicuous Communication blog here. The lectures cover
About 150 slides of material.
Back in August 2008 I posted on some research I did on traffic confirmation attacks. Traffic analysis is a collection of techniques for inferring communication relationships without having access to the content that is being communicated. Traffic confirmation is a special sub-case that attempts to infer communication relationships amongst users whose communications are mediated through an anonymity system.
The graph below shows two curves representing the observed frequency of recipients from a MIX anonymity system. The attacker is targeting a particular user Alice, and the red curve represents the minimal number of times her communication partners are observed, while the blue curve represents the maximal number of observations for all other recipients. The graph is created from an anonymity system with N = 20,000 users, using a MIX of batch size 50 and assuming Alice has 20 communication partners.
What surprised me was how easily the data for this graph could be programmed in the R programming language. The native vector operations of R makes this all very simple, and the code is below.
b = 50
N = 20000
m = 20
Nset = c(1:N)
mset = c(1:m)
N.plot = 0
m.plot = 0
m.min = 0
N.max = 1
s = sample(N, b, replace=T)
s = c(s, sample(mset,1,replace=T))
for ( t in c(1:500) )
{
s = c(s, sample(Nset, b, replace=T), sample(mset,1,replace=T))
ts = table(s)
m.min = min(ts[c(1:m)])
N.max = max(ts[-c(1:m)])
N.plot = c(N.plot, N.max)
m.plot = c(m.plot, m.min)
}
plot(m.plot, type="l", col = "red")
lines(N.plot, col = "blue")
New client connections from within Iran have increased nearly 10x over the past 5 days. Overall, Tor client usage seems to have increased 3x over the past 5 days. There are a lot of rough numbers in these statements, and they are very conservative.You can find some additional technical details from Lewman's own post on the topic, including this graphic
(repost from October 2008 for SBN)
In June I blogged about an anonymity incident concerning the ToR network. The draft version of the article was quite long and I eventually edited out a lengthier introduction. I would like to return to one interesting topic here. The popularity of commercial and open source internet anonymity services has waxed and waned over the last decade. A high profile company from the late 90's was Zero Knowledge Systems (recently renamed to Radialpoint) that possessed a collection of anonymity services, notably their flagship offering, the Freedom Network. For various reasons, the company was downsized to near extinction during the dot.com bust, though much of the technology, experience and expertise lives on in other products and former employees. ToR was a major beneficiary, and luminaries, such as Adam Shostack and Stefan Brands, are now employees of Microsoft (Ian Goldberg returned to academia). Shostack has an interesting presentation entitled Will People Ever Pay For Privacy? where his gives his views on the lack of commercial success of privacy and anonymity offerings, circa 2003.
The company name, Zero Knowledge Systems, is not just a puzzling juxtaposition of words but actually a deliberate reference to an underlying technology that formed the basis of their intellectual property. In this post we look more closely at the paradoxical-sounding concept of Zero Knowledge.
Proofs
Let's start by recalling a proof that is a few thousand years old which at the time it was discovered caused considerable consternation amongst integer-loving Greeks. We are referring to the (unpleasant) fact that the square root of two is irrational (can't be expressed of the ratio of two whole numbers). Here's one proof. Assume root 2 is rational and let sqrt(2) = P/Q where P/Q are in lowest terms (share no factors). Squaring and rearranging yields that P^2 = 2*Q^2, so P must be even, from which it follows that Q must be odd (not in lowest terms otherwise). Since P is even then P^2 must be divisible by 4, but since Q is odd then Q^2 must also be odd. Hence 2*Q^2 is not divisible by 4 and we have our proof (by contradiction).
So we began with a statement S = "root 2 is irrational" and the proof is the evidence that the statement is correct. We read the proof and are convinced that is it correct. Not only that, we can remember the proof and use it to prove to someone else that root 2 is irrational. We might say that this proof is transferable. This seems a natural property since we commonly think of proofs as being available to be read and verified by anyone who has the interest and patience to do so. Would we ever have a need to create proofs that are not transferable? Does this notion even make sense? For security, yes.
In security we deal with proofs pertaining to authentication (S = "I claim this is my identity") and authorization (S = "I claim these privileges and access rights"). The proof of these assertions is typically achieved by a user Alice providing the appropriate credentials to a target system for verification. Proof in this case can be equated to presentation, or to the transfer of credentials from Alice to the target system. If the target system is a phishing site then Alice gives away (transfers) her security information to a potentially malicious party. Could Alice prove statements concerning her authenticity and authorization privileges without transferring the full details of those credentials to the target system?
Zero Knowledge proofs a
re a technique created in theoretical computer science which show how one party can convince another party that a given statement is true but not reveal any other information. In particular, if Alice uses a Zero Knowledge Proof to convince Bob that a statement S is true, then Bob cannot use the proof supplied by Alice to prove that S is true to another party Carol. This is the zero knowledge aspect - Bob is convinced that S is true (he learns something) but he cannot convince anyone else (what he learns has zero value in the sense Bob can't transfer it). This seems counterintuitive and indeed it is.
Recall vs. Capability
Passwords are a common authentication mechanism used to prove your identity to a system. You prove that you know the password associated with a given user identifier by providing the password to the target system. The target system will have a copy of your password in a database and it simply compares its (hashed) copy of the password with the purported copy that you provide, and a match completes the authentication proof. So in this case demonstrating (proving) that you know a password is achieved by revealing it (or a suitable hashed derivative).
We might call this a full knowledge proof in the sense that what you know is fully transferred to the system for authentication. And if it happens that you are responding to a phishing email or your DNS service has been poisoned then your full authentication details are transferred to a rogue system.
To improve the situation consider the user answering 5 questions when they register for a system account, such that 3 are randomly chosen to be asked at each login. There are 10 ways 3-from-5 questions can be selected, so if a rogue phishing system observes the answers then the probability that the same three answers can be used to logon again is 0.1. If the number of questions is increased to 10 then there are 120 ways 3-from-10 questions and the probability of transfer is under 0.009.
So you prove your identity by answering a few simple questions that hopefully someone who is not you would find difficult to all answer correctly. The proof of identity can be made non-transferable with high probability by having a K-from-N question system where getting the same K questions from one login to another is unlikely.
The idea is sound but there are problems in practice. Our memory is not that good so the number of questions can't be made too large. Also think of Sarah Palin who recently had the password to her email account reset by someone answering the 3 questions: what is your birthday, what is your postal code, and where did you meet your spouse? Unfortunately, this is public information for Palin. We can make the questions more personal and hopefully easier to remember but people may object for privacy purposes.
A better approach is to move away from knowledge-based questions & answers to capability-based tasks & solutions. That is, you prove who you are not by answering questions that you should know but by performing some tasks that only you should be able to do.
Cube Logic
Consider Alice proving her identity to Bob by proving her capability to solve the Rubik's cube (yes many people can do this, but the example is instructive). Alice could opt for a full transfer proof by writing a set of instructions for solving the cube which she could give to Bob for verification. But let's assume that Alice is too lazy to create such a set of instructions, and that Bob is equally too impatient to read them in any case. They both agree that a practical demonstration is better: Bob will take a cube, repeatedly twist and turn it until he is satisfied that it is in a random-looking configuration, and then ask Alice to return the cube to its monochrome state (one colour on each face).
He hands the scrambled cube to Alice, who turns her back to Bob and starts solving the cube (she turns away so if Bob does not know how to solve the cube he is not improving by watching her). If Alice can actually solve the cube then she can use her skills to return Bob's cube to the monochrome state. If she does not have the cube-solving capability then she can take a stab at the solution but she will have to be lucky.
While Bob may be sceptical of Alice's cube-solving abilities, he is prepared to believe that Alice may have memorized a large number of solution sequences to specific configurations. If Bob arranged the cube into one of these configurations then Alice is able to solve the cube directly from memory. Let's be wildly optimistic here and assume that Alice has memorized the solutions for half of the possible 10^(19) configurations.
So Bob can proceed as follows. He randomizes the cube and asks Alice to solve it. If she can't then he knows that she has falsely claimed to have the cube-solving capability. If she does solve the cube, he repeats the test again by re-randomizing the cube and asking Alice for the solution. Each time Bob poses a cube to be solved by Alice there is a 50% chance that she will be caught out if she can't in fact solve the cube (Bob did not randomize the cube to one of her memorized configurations). After 20 iterations there is only 1 chance in a million that Alice could fake having the cube-solving capability.
So here we have replaced questions (do you know the answer to this?) by tasks (do you know the solution to this?). The advantage of tasks is that they are capability-based rather than knowledge-based, and in general more tasks can be posed than questions answered from recall. Also we don't have to recall a skill, we just use it. As we mentioned the cube has 10^(19) configurations, which means that someone with the cube-solving capability can solve 10^(19) tasks of the form "return the cube to its monochrome state from this configuration". There is really no comparison to the number of knowledge-based questions that we could answer accurately on a regular basis.
Finally, Bob is not learning anything about the cube-solving capability. If he does not have this capability, after interacting with Alice he is none wiser. He has observed that she unscrambled a series of scrambled cubes chosen by him. He is convinced that she can unscramble the cube but he will not be able to convince Carol that either he or Alice can unscramble the cube. This is the Zero Knowledge aspect.
Zero Knowledge Proofs
The example above explained to essence of Zero Knowledge proof (ZKP) which we can summarize here as
But how will this work in practice? The capabilities used in practice for ZKPs are derived from computational secrets such as the prime factors of a number or the discrete logarithm of a number modulo a prime. Alice can easily create a public and private key pair suitable for this purpose. The private key takes the role of Alice's secret, and her capability is being able to easily solve specific equations involving her secret. The role of the public key is to verify that her solutions are correct. So when Bob wants proof that Alice knows her claimed secret, he creates tasks in the form of equations that Alice can solve using her secret key. If Alice does not know the secret key then she can guess the solution but will be caught out after a few rounds.
In a future post we will talk about some practical applications of ZKPs, but if you just can't wait then take a look at the Direct Anonymous Attestation (DAA) protocol used in the Trusted Computing Platform (TPM) from the Trusted Computing Group.
After quite a delay (since the initial idea) I have finally completed a good draft of some research on traffic confirmation attacks. Traffic analysis is a collection of techniques for inferring communication relationships without having access to the content that is being communicated. Traffic confirmation is a special subcase that attempts to infer communication relationships amongst users whose communications are mediated through an anonymity system.
We assume that the underlying anonymity system is a threshold MIX, with batch size B, supporting N participants, each of whom may act as both a sender or receiver. Typical MIX system parameters are N = 20,000 participants (all potentially send and receiving), and a batch of size B = 50 (the MIX accepts 50 messages, randomises their order, then delivers them). The MIX makes it difficult to correlate the 50 senders to the 50 receivers.
The traffic confirmation attack targets a specific user Alice and attempts to infer her M communication partners (who she is sending to) by observing her communication patterns through the MIX. Alice for example might be sending messages to M = 20 people on a regular basis.
The attacker observes when Alice sends a message in a batch, and can also observe who receives a message from that batch. This will include at least one of Alice's communication partners, but which one? The uncertainty that the attacker has with respect to the M communication of Alice is called the entropy her partners.
It is well-known that given the properties of the MIX and the power of the adversary (what she can see), that the entropy of Alice's partners is decreasing as the number of message batches that Alice participates in are observed (a higher entropy means more uncertainty). Eventually the entropy of her partners will go to zero and their identities will be known to the attacker. But how many such observations need to be made before the anonymity of Alice's communications partners is effectively zero?
My paper shows that after the attacker has observed approximately
M * log N
messages, subsequent messages drive the entropy to zero at a geometric rate. That is, the MIX system protects Alice's partners to a point but then essentially collapses from that point forward. So if the attacker is prepared to wait for (and observe) those first M * log N messages from Alice, then the uncertainty of her partners reduces rapidly as Alice sends additional messages. One reason that the attacker has to wait for that first group of messages to be sent by Alice is that she won't be able to uniquely determine Alice's communication partners until Alice has communicated with all of them at least once.
By way of an example, consider a system with N = 20,000 participants, a batch size of B = 50, and Alice having 20 communicating partners. In this case, after observing 292 initial messages, the attacker can identify Alice's partners with 99% certainty after observing an additional 110 messages (that's 402 messages in total). So way before she has sent 400 messages, Alice should either change her partners or change her MIX system (probably the later).
You can find the draft paper here. Comments welcome!
Pictured left is Dan Egerstad, a 21-year old Swedish computer security consultant (at times also called a hacker, researcher and other colourful titles) who approaching a year ago now ran afoul of various authorities for his involvement in the exposure of account details harvested from the Internet-based anonymity service Tor. He obtained password information for 1,000 e-mail accounts belonging to foreign embassies, corporations and human rights organizations, and posted some details to his web site. For his trouble he was taken to the local police headquarters for questioning, and various computing equipment and written material were seized from his domicile. Egerstad claims he only wanted to bring attention to the inherent weaknesses in Tor that he expects are not well-known to its users. Another case of irresponsible disclosure or over-zealous awareness? Before examining the details of the Egerstad case we need some background on anonymity (the research material used to write this article was collected in Freemind and is available as a flash web application here).
When we speak of anonymity here we mean anonymity with respect to a digital action, such as sending an email, paying a bill or browsing a site. Such actions are considered to be anonymous if they can be attributed to nobody or attributed to everybody. In practice it is very difficult to ensure that digital actions are attributed to nobody since Internet protocols are very generous in the disclosing information as part of their operation. On the other hand, building systems that attribute actions to everyone is also impractical. Deployed internet anonymity solutions take the approach of making digital actions attributable to a sufficiently large set of users. So while it would be nice to have an anonymous email system whose messages could be attributed to anyone on the planet (once they all have email), the sender may feel that their anonymity is sufficiently protected if the system renders their email potentially attributable to a million people who were online when the email was sent. Anonymity loves a crowd, as the saying goes.
We will now give a short overview of how two well-known anonymity services work, and then get back to the transgressions of Mr. Egerstad.
Dealer-Based Systems
In dealer-based systems, we imagine a large number of people sitting around a big table, with one person, Dixie, distinguished as the dealer. Each person at the table can send or receive a message from someone else at the table. When Alice wants to send a message to Bob, she puts the message in an envelope, writes Bob's name on the front, and passes the addressed envelope face down to Dixie. Dixie accepts the envelope from Alice, and continues collecting envelopes from people until she collects a pre-determined number of messages, let's say 100. Dixie then shuffles the 100 envelopes until their order is random as compared to the order in which they were received, and she then deals the envelopes out as they are addressed.
Someone at the table watching all this, say Eve, learns that Alice gave a message to Dixie, and that one of the people who was dealt an envelope by Dixie was her intended recipient (which must include Bob). So the anonymity of Alice's receiver might be said to be 1-in-100 assuming that the 100 messages collected by Dixie were delivered to 100 different people. If Bob is a popular fellow then he may have 10 messages dealt to him by Dixie, and the anonymity of Bob as Alice's receiver is reduced (there are fewer possible receivers to consider).
Here the value of 100 is called the threshold, and reaching the threshold number of messages triggers Dixie to shuffle and deliver. Alice may search for another table where the dealer Debbie has a threshold of 1000 say, because she wants to hide her recipient amongst a larger set of people. Alice will wait longer for her messages to be delivered since it will take Debbie more time to collect her threshold of 1000 envelopes as compared to Dixie's 100. There is tradeoff here between anonymity and latency: that is, how many other messages your message is shuffled with (the size of the threshold) and the delay to deliver of your messages (waiting for the dealer to gather the threshold).
The dealer can pull other tricks. A dealer Dylan may have a threshold of say 500 messages but on the first collection he actually accepts 600 envelopes. The 600 envelopes are shuffled, but he puts aside 100 (called the pool) and then delivers the other 500. The next 500 received messages are shuffled with the current pool, 100 set aside for the next pool, and the remaining 500 messages delivered. The pool breaks the direct correlation between when Alice submits her message and when it is dealt by Dylan. Eve will need to consider more potential receivers to determine who Alice might be communicating with.
What we have described here as dealer-based systems gives the simple intuition behind MIX anonymity systems, originally proposed by David Chaum, a prolific and influential cryptographic researcher. Chaum's seminal ideas have been greatly elaborated on in the last 20 years or so, and for a practical internet service providing anonymity based on the MIX principle, please see JonDonym.
Lotto-Based Systems
The other class of anonymity systems we will consider shall be referred to as lotto-based systems (these are the ones that got Mr. Egerstad in hot water). We are proceeding by analogy as before with dealer-based systems. In the game of lotto players are attempting to predict which balls will be selected by a mechanical process that seems very random. A collection of numbered balls (say 40) are released into a clear and hard plastic sphere or cylinder, which when rotated, causes the balls to bounce around in an unpredictable manner. After a "sufficiently large" number of revolutions, an arm reaches into the sphere and catches one of the balls as it is bouncing around. The selected ball becomes the first number. The arm then reaches in again, catches another ball, and so on, until the required number of balls to complete the game are selected (say 6). All the time the sphere is rotating, and the remaining balls bounce off each other and the hard surface of the sphere.
Imagine now that instead of adding 40 balls at the beginning to the sphere, we keep on adding new balls, for example at the rate of a few per second. Also imagine that the arm does not just pull out 6 balls but rather it continuously extracts one ball at a time. We might think of this setup as the perpetual lotto system with balls continuously entering and leaving the system. If we put a ball into the sphere, how long would it take to come out? If we took the numbers off the balls (let them all just be white balls), when would we know that a given ball has come out?
These principles underpin several anonymity systems, such as Crowds. We replace the balls with messages and the rotating sphere becomes a collection of servers that randomly route (bounce) the messages amongst themselves before delivering the message to the intended recipient. In dealer-based systems the anonymity of Alice's receiver was tied to the size of the threshold used by the dealer. In lotto-based systems Alice's message is potentially mixed with all messages in the system at the same time, which may be a large depending on the traffic rate into the system.
Tor - The onion routerTor is a particular, and seemingly popular, implementation of an anonymity network that falls into our simple lotto-based classification. Tor is short for "The onion router", and is considered to be a second generation version of onion routing for anonymous communication (onion routing 2.0 in common parlance). Here an onion refers to a message that is encrypted multiple times, or in layers. When Alice wants to send a message she first chooses a path through the Tor network based on a list of available servers. So instead of her message bouncing around randomly in the system (as in Crowds), she actually chooses the route before submitting the message. To protect her selected path she encrypts the message with the public key of the last server in the path, then encrypts that encrypted message with the key of the second last server in the path, and so on, for each server in her chosen path. The following diagram shows the process (see this wikipedia article for better resolution and more explanation).
Once all the layered encryption is completed, Alice sends her encrypted message (now called an onion) to the first server she selected in the path. The server decrypts one layer of the onion to reveal yet another onion and the next server in the path. The first server sends the onion to the second server in the path who decrypts the next layer and forwards the remaining onion to the next named server in the path, and so on. The final server in the path decrypts the onion one final time to reveal the original message and the intended recipient. The final server delivers the message to Alice's intended recipient.
Back to Dan
In Tor there are 3 roles for servers nodes: entry nodes that accept messages into the network, routing nodes that decrypt one onion layer and then forward the remaining onion, and finally exit nodes that deliver the message out of the network to the intended recipient. Any physical server in the Tor network can act in any of these node roles. What is revealed about Alice? Well the entry node sees her IP address, while the routing nodes learn the previous and next nodes in the path. However the exit nodes learns the message itself and the address of the recipient. If Alice wants this last hop to be secure then she must explicitly use a protocol like SSL to protect her message. But apparently this is a little known fact as Dan Egerstad demonstrated. This caveat is (now) clearly indicated on the Tor project site, and a general warning: Be smart and learn more. Understand what Tor does and does not offer. This list of pitfalls isn't complete, and we need your help identifying and documenting all the issues.
Servers can be donated to the Tor network to act as nodes, and currently there are about 1500 nodes. So Dan Egerstad created/donated 5 exit nodes and sniffed the traffic contents of these nodes as they forwarded traffic out of the Tor network. He was not targeting any specific users of Tor, only looking at the traffic that was routed to his exit node as part of the overall Tor protocol.
Surprisingly Egerstad obtained login and password information for over 1,000 e-mail accounts belonging to foreign embassies, corporations and human rights organizations. More specifically he harvested information on users from embassies belonging to Australia, Japan, Iran, India and Russia, and also accounts information belonging to the foreign ministry of Iran, the United Kingdom's visa office in Nepal and the Defence Research and Development Organization in India's Ministry of Defence. Egerstad ensured controversy (and more than that actually) when he published the login and password details for 100 select email accounts, using the justification that he felt it would be the most effective way to make the account owners aware that their communication had been compromised. Mr. Egerstad has stated that there is no security flaw with Tor - the real threat comes from user expectations that their message contents are being protected end-to-end by Tor, when in fact encryption is only applied to internal Tor network communication.
Lessons Learned
Mr. Egerstad has highlighted that Tor obfuscates the path that a message follows through the Tor network (protecting the sender), but confidentiality is not provided at the exit point to the network. Of course the Tor people have documented this property, but there is nothing like an incident to drive the message home. Users should also understand that the role of the exit nodes is still based on the honour system, for both delivery and respecting the privacy of message content.
The main threat addressed by the design of Tor is protecting the identity of Alice from eavesdroppers - that is, it should be difficult to correlate the identity of a sender through the routing of her messages in the Tor network. So if an attacker is targeting Alice they may have to compromise a large number of nodes (or introduce a large number of their own nodes) into the Tor network to trace a path back to Alice. This sounds like hard work. Mr. Egerstad has shown how to harvest account details by merely attaching a new exit node and eavesdropping on the Tor business-as-usual traffic that is routed through the node by user path choices. So while passive eavesdropping may not compromise a specific person like Alice, it can still reveal valuable security information for the attacker.
Posts
All Comments
