Breaking Monero Episode 09: Poisoned Outputs (EAE Attack)
https://youtu.be/iABIcsDJKyM
Monero’s ring signatures provide plausible deniability, but they aren’t perfect. We model examples where two colluding parties ‘E’ attempt to learn information about an individual ‘A.’ By sending outputs to individuals and tracing their transaction graphs, these colluding parties may perform powerful statistical tests to learn significant information, especially for repeated transactions where they would not normally occur by chance.

All Breaking Monero Episodes

Episode Transcription

Justin: Welcome back to Breaking Monero. This is our ninth episode on Poisoned Outputs, or the EAE attack, or the Knacc attack. It’s given several names and we’re here to discuss, honestly, a pretty difficult and nuanced topic to talk about, so we’ll do our best. We’re here with me, Justin, and with Surae and Sarang. It’s great to have everyone here. This video is going to be diagram heavy, so if your listening to this as a podcast, we’d suggest watching the video form later if you’re confused, because there’s a lot of stuff going on. But first, we’re going to have Surae talk about the general idea of the marked funds that we’re talking about, and then I’ll jump in with the diagrams to explain the situation to you all.

Surae: Here is a thought experiment for everyone in the Breaking Monero audience. Let’s say that you’re living in an oppressive society and you want to buy some banned books. Let’s say that you have a local banned book dealer who stands on the corner, you can go give them cash and they will give you your ‘Bible’ or your ‘To Kill a Mockingbird’ or whatever banned textbook you want. One question you might have is how would this tyrannical government come to the conclusion that you are a purchaser of these devices, or rather, how would they go about tracking the person who is supplying all these banned books, these nasty little devices, to society? Well one to do it, and this is how law enforcement has done this, good old-fashioned police work going back hundreds of years, you’d go do a controlled purchase from one of the street dealers. You’d go buy a book six or seven times in a row and then look for bank deposits at local banks. What will happen is that street dealer will give the cash to his boss and eventually make it’s way into a deposit in a bank account. If those dollar bills were used to purchase the banned books, or are marked, the bank will alert law enforcement and they will have found their kingpin boss who is depositing money from these controlled purchases. The essential idea is that someone is buying a book and there’s going to be a chain of custody of the money that will eventually end up in some Know Your Customer (KYC) bank’s hands. Once that money ends up in the bank’s hands, they can start linking real-life identities with those original purchases and find the interior hops of those transactions. Unfortunately, this is a problem that Monero faces. I’ll hand this back to Justin.

Justin: Excellent, we’re going to take a look at this attack in a little more detail just to show people what it is. Again, warning, this is a very heavy series of slides. So brace for impact here. As discussed, you have person Eve who is sending funds to a specific Monero address. They’re learning information when this person then takes funds and puts in on an exchange, or some other colluding entity. It doesn’t matter what these entities are, all that matters is that Eve is colluding with this exchange, or this party A is colluding with party B. Again, it doesn’t matter who these parties specifically are. Let’s say that Eve sent a transaction to that address, they create a ring signature as shown here. They use their real output here, that’s related to Eve and then create a transaction with two outputs. One output is given to that address, we’ll call it output A, and the other address is given back to Eve. So Eve doesn’t worry about this, she doesn’t try to track this output. So let’s say that Eve comes back, looks at the blockchain and notices that there are three transactions that have this output (A) in their ring signature. These are not associated by time or anything, let’s just say that there are three transactions. An observer is not sure necessarily that A is truly spent in these ring signatures, it could be a decoy in all three, but they’re still trying to learn information about what the situation is. Let’s say for this second transaction here, for instance, that someone deposited this output on an exchange. This one yellow output here was sent to an exchange and Alice was the person who sent the funds to the exchange. So for this EAE example, you have Eve as the first E, Alice in the middle and then you have the exchange on the last portion. What we have to note here is the exchange might suspect, in conjunction with Eve that Alice is the holder of this Monero address. This is a heuristic, it’s not very strong, especially if there’s only one instance. We don’t know what the real case is here. It could be that Alice just used this output as the decoy in the ring, and if this only happens once, there’s a pretty high chance that this just happened by chance and that Alice is not the true person who controls this address. But if this happens twice, or three times, or four times, now you’re starting to get a pattern where Eve sends multiple transactions to this address and this address has several deposits on to the exchange, all under Alice’s account. Now the exchange and Ever are learning a lot of information where they can say that the chance that one person that deposits funds on our exchange is able to have a possible, recent spend from the outputs we assigned to this address is very low, it’s a very low probability that this happens by chance. As a results, we’re going to assume that there’s a good enough amount of evidence that Alice is the same person as this address. This is not the only circumstance where this can happen. This graph gets really messy, especially as you add other situations, we’re trying to keep it simple for this episode, while nevertheless while discussing some of the things that can get in the way. Let’s say for this ring here that there is another output that was sent to the exchange as I’m highlighting here. In this case, maybe this was sent to Charlie who sent the funds to the exchange. The exchange probably would have at least some suspicion of Charlie, it’s far more likely that in Charlie’s case it happened by chance, it’s certainly some limitation of this sort of model and it’s a very complex system on how these things get added. Ultimately it is a statistical test to say what is the likelihood that this would have happened by chance. You’re going to have type 1 and type 2 error as you conduct these statistical tests, but ultimately there are ways for them to be much stronger in some circumstances than others.

Surae: Do you mind if I jump in really quick Justin? One thing I want to point out is just to connect this graph to what I discussed a little bit ago about controlled purchases. One way you can visualize this is that Eve for example is a detective who’s purchasing banned books online. They’ve constructed these for purchases from this anonymous online vendor (the address 43WI...) and then later this exchange notices that Alice make all four of these deposits, the exchange comes to the conclusion that these four deposits are probably related to those banned bookseller purchases. The difference is that in Monero we have these ring signatures that point back to several previous spenders and so in the cash scenario I have this linear chain of money going from one person to another. Here we have each output is used possibly in multiple ring signatures and is only probabilistically implicated. So what you end up having is this exchange is capable of developing this probability profile of Alice.

Justin: Exactly, we can even expand this, we’re going to take this example and do a little bit more with it. Instead of Alice sending four different transactions to an exchange, she takes even less precaution and decides that she just wants to sent one big transaction, so this one transaction has four rings. There are four inputs, each with their own rings. You see that one of these is A, B, C and D and this transaction is deposited on the exchange in Alice’s account. Well now we can be even more clear. What is the likelihood that a single transaction would contain all of these four outputs that are being watched in each independent ring? It’s very, very low and especially as the number of transactions grow that are tracked to one user, it becomes increasingly unlikely. This is certainly a consideration where Alice, if she was interacting with an exchange, should be concerned about revealing that she is related to this one entity, this address, because it’s very likely that this did not happen by chance. The errors are very low. Both of these examples were with one layer of separation where you have one person who sends funds to one intermediary who then sends it on to an exchange. But this could get more complex and I’m going to show an example where you have more intermediary steps. In this case, I’m only showing two because that’s about what will fit on a slide, but this could be much longer depending on what you’re really assessing. So again, let’s start with a simple, single transaction case. We have Eve here, who sends one transaction to this entity, and this output is used in three transactions. In all likelihood it would be much more, but for the sake of fitting on a slide, let’s say three. But let’s say that none of these transactions were deposited on an exchange or a service that Eve was working with to learn more information. What Eve might do is say that even though I didn’t learn anything specifically from these transactions, I’m still going to watch these new outputs that are generated. Now each of these outputs has independently, once again a set of three other transactions where these are spent. So let’s say this output was used in these transactions, this output was used in these transactions and so on. Let’s say that in this second layer, that there is one transaction that deposited funds to the exchange. The exchange knows that Alice deposited these funds on the exchange. What does Eve and the exchange really know? How good is there test for determining whether or not Alice is really the same person that controls this account? This is similar to the first situation we went over except that in this case there is more ambiguity. There’s less certainty because now, instead of saying okay there’s three transactions that I’m worried about. Well there’s a lot more transactions here that you’re worried about, the graph gets a lot larger. Eve can try to learn more information by sending more transactions. Let’s say that Eve sends transaction B, this doesn’t come with any initial red flags and the first transactions that immediately use B. But let’s say that in the second set of transactions that there is another deposit to the exchange and Alice also made this deposit. Now the exchange and Eve get a little bit more information about who actually deposited these funds because now you’re having enough strength in a statistical model to say that it’s unlikely that Alice would have deposited both sources of these funds if they did not receive outputs A and B. So it’s important to show how this grows over time and gets more complicated as you have more layers to this. To simplify it, I have a nice, stupid example here where we have a transaction tree, and it purposely looks very much like a pyramid here. For each tree here, this is the depth of an output as it goes on. So you have your initial transaction here that generates outputs, that generates more outputs and so on and this tree gets bigger and bigger over time. If you have two people that are involved on both sides of the transaction again. Let’s say you have Eve here who sends funds to Alice who then sends funds to an exchange early on. Well, there’s not a very deep transaction graph and so Eve and the exchange have at least a decent idea. They can do a statistical test that has a pretty high degree of probability. But if there's only one test all the way down here, there’s a ton of other entropy that could occur and the statistical test is far weaker. But if a user does this twice, sure it might be deep down in the transaction trees, but there are several trees that they can collect information from. The test becomes stronger again. In summary, and this can be applied to any sort of application of these statistical tests, the more points of information that the user has, the more trees that Eve, the exchange or any sort of observer is able to construct, and the further up the tree that the outputs are, the better the statistical test. As you have more instances of information about a user and as there’s less ambiguity for those sets of information, the statistical tests get stronger. Now you should at least understand the very basics of what an EAE or Poisoned Output set of attacks are. It’s the case where users try to be as associated with as many of these trees as possible and to learn as much observable information as possible to get actionable information. I am done ranting.

Surae: I just wanted to say one quick thing. As Justin said, if you go to the bottom of the tree, the intuition is that you’re going to be more likely to be hidden by obscurity because you have more hops as you go down into the tree, you have more options. But one of the interesting things about these trees, is that if you go really, really deep they get scraggly and unhealthy and they don’t have a nice full base like a good tree does. They get less dense as you go further down. So even though it seems like the further deep you go the safer you are, if you go too deep you may also be creating problems for yourself. That’s just one of the interesting properties of these tree structures. I just wanted to throw that out there.

Justin: Right, thanks Surae. Sarang, can you talk a little bit about how these attacks get harder? What some of the implications are and little bit more detail about how the statistical probabilities for these tests get determined?

Sarang: They’re determined by a few different thing and you talked about two different aspects. You talked about the number of trees and that just depends on how the adversary, Eve, is doing controlled purchases, which might be out of your control depending on the circumstances. But one parameter that we do control, that we talked about pretty frequently, is ring size. Ring size is the number of different outputs that you’re throwing around in each ring which affects in some ways the level of plausible deniability you have as the spender of a particular transaction. In that circumstance, the idea of working your way down this tree and changing the ring size can affect the width of these trees. In particular, every single time you go one layer deeper on the tree, a bigger ring size, will in general, depending on transaction volume and things like that, affect how wide the tree is and therefore how many different paths there are that could lead an adversary toward a statistical model of what’s going on. All other things being equal, an increase in ring size can make this a bit harder for the adversary. Of course, the number of times that you send funds to another entity and idea of churn is just sending the funds to yourself, basically brings you deeper and deeper down into this tree. Which may lead you to believe, well in that case why don’t I send funds to myself a bunch of different times before I eventually go to the exchange? I’m far enough down the tree and we said that’s good. But the way that you go about doing those transactions, the timing that you use for example, could also in effect leak information if it’s not done safely. Timing data that might be available to others looking at the chain or to your ISP who knows when you’re online and things like that. Different types of metadata like that can affect the way that churn is done, which is why when people ask, how often should I churn, how should I do it? It’s tricky question because it depends a lot on your threat model and how you go about timing it. Those are two interesting parameter that affect the way that these trees are structured.

Justin: So how do you avoid this sort of problem? Do larger ring sizes alone help with this, where users don’t need to care or even with larger ring sizes is it something to worry about?

Sarang: Well you can take this to an extreme. Suppose that the ring size got as big as it could possibly get, that every possible output was used as a possible decoy. Then you run into this large anonymity set situation that ZeroCoin or ZCash type protocols and assets have. In that circumstance you’re pretty much as good as you can get. Everything is equally probable as a spender and building this tree would be absolutely incomprehensible. So to some extent it does become really good, but ring size in our particular case is a parameter that does affect things like transaction time and transaction size, so it definitely needs to be balance against what we believe the possible benefit could be. It’s definitely not a one-size-fits-all answer for what the ideal ring size should be. It’s tough. It’s tough and tricky.

Justin: We also want to make clear that the examples that I showed were not exhaustive. There’s a ton of different nuances or different things you could have thrown in there that would either make the statistical tests far more or less accurate in practice. Imagine if they start bringing IP address metadata in and they could say that these transactions were also sent from this IP, it’s going to get far more involved. Or what if there’s many people making deposits on the exchange and therefore a ton of different users that have similar behavior then it will become weaker. There isn’t really a simple answer we can have for you based off how it all works because users can come up with whatever statistical tests, they can pull in other outside information in conjunction with this. It’s all fine and good for us to look at the blockchain and say that absent external information then this, but again, it’s not really the case. Even in the sort of attack that we described, Eve’s involvement, the person sending the poisoned outputs that they’re tracking is still sort of like external information by itself, so we’re still testing an external information parameter.

Surae: That’s a really good point. One of the main things that these E characters, the exchange and Eve, they know they are sending these transactions to this one suspicious address in the first place. That’s not information that hits the blockchain, they just know that, it’s external. In addition to that, to elaborate on Sarang’s point about ring sizes being counterintuitive and elaborating on your point that if you pick your own metric or heuristic, then you’re going to draw a different conclusion. You can look at a variety of anonymity metrics and apply them to Monero, and what’s interesting is that some of them have some counterintuitive results. For example, increasing ring size once it’s bigger than eight or nine gives you these reduced returns according to some anonymity metrics. But sometimes according to other anonymity metrics, the blockchain getting larger alone is enough to reduce the anonymity metric. So balancing ring size, the heaviness of the blockchain and all of these properties in order to guarantee people that you have a negligible probability of your transactions being traced, it’s not really functionally possible, currently. Especially because you can draw different conclusions using different metrics.

Justin: All right. Sarang, do you have any big takeaways for people watching this episode? We sort of discussed what this is and the fact that it’s nuanced, what are the takeaways for people who are watching?

Sarang: Some of the big takeaways are that it really depends on your threat model. Like we’ve said, many different forms of this attack assumed that you had cooperating entities on both sides. You have some kind of KYC/AML exchange that knows who you are when you’re doing deposits and you have an entity on the other side colluding with that exchange who’s making controlled purchases. If you are concerned about that, part of it has to do with knowing the entities with whom you’re interacting, if possible. Obviously in some situations and threat models you may not be able to have more control over what those entities are and what they’re doing. Basically, if we can reduce the number of E’s, like the exchanges and the Eves, the more we can get rid of those, the better. But again, that’s not always possible. Some users and certain circumstances may have a lot of choices over how they’re doing deposits and from whom they’re accepting funds, but other’s might not.

Justin: Brandon, can you speak about the difference between plausible deniability, we’ve discussed this in previous episodes, but with this sort of statistical tests do people still have the plausible deniability provided by ring signatures?

Surae: Going back to what Sarang said a moment ago about a threat model. If your threat model is that your tyrannical nation id going to shoot you if there is a probability of more that 50% that they can link you with this transaction on the Monero blockchain. I would say don’t use blockchains at all, because you’re going to be in a similar probability category as if you use ZCash or any other blockchain. If your threat model is that you’re going to be punished just for probabilistically even using the technology, then it’s not really going to help you out. On the other hand, if your threat model is one of plausible deniability like Justin asks and you’re living in a nation with rule of law where you would be prosecuted in a court and you could demonstrate there are 10,000 additional transaction histories none of which include my alleged transactions, they just pulled this transaction history out of the space of all transaction histories and they’re accusing me of it. If you can make that plausible deniability argument, then Monero is fantastic and honestly if you can’t make that argument then even cash is dangerous, physical cash. In terms of plausible deniability, I would always look at cryptocurrency technology as a plausible deniability technology, not as a way of hiding your transactions forever. On a certain level, we’re in an arms race with the people who want to learn your financial information and we’re trying to protect you guys as much as possible. But black holes leak information about their contents, the idea that we would be able to devise a blockchain that will protect people forever from the most extreme threat model where a government is going to nab you if you have a 15% chance that you were guilty then we have a completely different situation on our hands than finances.

Justin: Thanks Brandon, Sarang, last question. Is moving past ring signature still something that is necessary long-term or is it reasonable for us to make the ring size like 100 or whatever?

Sarang: Increasing the ring size such that we have a ton of different path possibilities in this big tree that makes it very, very improbable that an adversary who’s not doing a ton of controlled purchases would be able to that. Is it possible? Yes. In theory we can increase the ring size to be whatever we want depending on how you do the selection of decoys and things like that, but of course that increases the size of transactions which has scaling issues, it also increases the verification time of transactions, which has scaling issues. To some extent, this is always kind of a balance game about this. To what benefit is it? You’d probably have to increase the ring size fairly substantially to be able to get a negligible probability of this ever being an issue. That’s unfortunate and that’s why the research community right now is really big into taking rings out of the picture entirely to go to a more complete anonymity sets. Something like ZCash and the protocols they are based on, when used correctly, offer excellent anonymity sets, complete anonymity sets, but we know that has trade-offs with the whole trusted setup aspect, and ZCash has had issues with that in the past. There’s always trade-offs with this, whether or not we’ll be able to find something relatively soon that’s able to do away with those trade-offs, that’s uncertain. A lot of people are looking into it, and like I’ve always said, I personally look forward to the day when we don’t have to deal with the anonymity set problems anymore. So we can continue trying to iterate as best as we can until the entire ecosystem gets there.

Justin: Okay, thank you so much Sarang and Surae for joining me today for this very difficult episode. But frankly on Poison Outputs, EAE, Knacc attacks, whatever you want to call them there’s tons of different names and tons of different circumstances where it could be applied. So I think this serves as a good episode for understanding how people should look at how their transactions tree is growing as they use Monero and keep that in mind. Beyond that, make sure to draw comparisons between this episode and other episodes with what information you’re giving an observer about how you’re sending transactions. All right, that’s all from us today. Thanks for watching and take care everybody.