Today I'm going to talk a bit about some sort of ongoing work that I'm currently doing with a pair of my students that is aimed at automatically detecting and finding new attacks on format oracles, which are a generalization of padding oracles.  This is work that really the bulk of the awful painful work was done by my two PhD students, Gabrielle Beck and Max Inkas, who aren't here to take credit for it, so I'm here to take credit for them. There's a draft online. You can see the actual paper there. I also want to mention that this is work in progress. This is the result of months of wrestling with SAT solvers and we're still wrestling with SAT solvers. We actually had to like repair bugs in SAT solvers. So this is kind of like the preliminary results and there will be more results later on down the line. The last thing I want to say in this intro slide is that, you know, they say that sometimes a lot of research papers are born as the result of an argument and this research paper is actually born as the result of kind of a painful story, where we found a vulnerability a few years ago in an Apple product and we had to spend like weeks and months manually exploiting it. So we just determined we would never have to do that again, so we wanted to automate that process. And I'm going to come back to that story in just a little bit. Okay, so quick background.  I actually spent some time trying to go into the pre-research literature to see where the first examples of practical chosen ciphertext attacks, a text attacks exist. I wasn't really able to find anything kind of before the 90s. I'm sure that they happened, you know, maybe back in the days of the enigma, but nobody was able to give me any examples. But we do know that starting in about the mid-1990s, there was a bunch, maybe earlier late 80s, there was a bunch of formal work in the research community looking at ways we could immunize schemes against chosen ciphertext attacks. We knew these things were real. We came up with models and we started to sort of build the groundwork for schemes that were actually secured in this particular model. But at the time, this is the 80s and 90s, this was really theory. Nobody thought this was actually something that would affect us until the late 1990s and the early 2000s, when suddenly two attacks, which we've talked about today, kind of came out of nowhere and made industry and people who actually do things with real crypto care about this problem. The first, as we discussed in the last talk, in the asymmetric crypto world was the Blikenbacher attack. And in the symmetric crypto world, the first was the Vaudenay attack. I have it as 2001, maybe it was 2002, and this was a padding oracle attack. And since this talk is mostly or almost entirely about symmetric crypto, I'm going to focus on that and not go back to Blikenbacher for a while. So the Vaudenay attack, and I'm really glad I don't have to sort of start from scratch on this. We just saw it in the previous attack. Basically works on the theory that a lot of schemes don't use authenticated encryption. A lot of protocols don't use authenticated encryption. There is a padding check function. This was a vulnerability in SSL that is all over the place, as we now know, that will basically give you back some signal, let's say a zero or a one, depending on whether the padding checks out in a decrypted ciphertext. And so if the ciphertext is not authenticated, we can exploit this to do useful things. It's a very famous old attack, amazingly still exists today in 2019. There is a generalization of this called the format oracle attack. And it's the same idea. It's just that now we're going to replace that format checking function, the padding check function, with an arbitrary predicate that basically says, hey, let's look at whatever it is about this decrypted message and tell you whether or not this is valid. OK, so we're just going to define this as an arbitrary function F. And the basic idea is a format oracle does decryption, evaluates this function and then tells you whether or not things worked. The neat thing about format oracle attacks from my perspective is that they can be very deep. So typically we like to think about crypto in terms of cryptographic libraries and cryptographic code, and that's even the case for padding oracle attacks because padding check functions are in libraries like OpenSSL. But format oracle attacks can go way, way beyond the crypto code. If you're vulnerable to a format oracle attack, that stuff that might be vulnerable could be like your application specific parsing logic, your decompressor. It could even be something completely insane, like you're decrypting a firmware image and trying to run code from that firmware image. So this goes way, way beyond the crypto if you're vulnerable, if you're not authenticating your encryption. Now, the answer to this problem is you should be authenticating your encryption. I want to put this up front. Obviously, that's the kind of obvious the solution. We tell people to do this. They don't always listen to us, unfortunately. The fact that we're still seeing vulnerabilities in TLS in 2019 tells us that we haven't really solved this problem. So people don't like to change legacy systems unless they see proof of exploitability. Even like in this very well-trodden area of just simple patting oracle attacks on TLS, we're seeing problems. When it comes to custom protocols, it's much, much harder to get people to change. And there's still this problem of misuse, right? Even if you use authenticated encryption, somebody goes with AESGCM and they reuse a nonce. All of a sudden you have a new malleability issue that pops right up. And we're trying to fix this with SIV and other kinds of modes of operation. But we're not there yet. And the last sort of reason that AE doesn't solve this is because open SSL. And I'm not going to say anything else about that. So we're always going to be suffering from this. I'm going to grab a follow up. One of the personal story that I kind of meant to relay, and this is along the lines of you can't get people to fix things without an exploitable vulnerability. So several years ago, back in 2015, I went and I gave a talk at Apple. And the night before the talk, I pulled open their iOS security guide and I looked to specifically see how iMessage security, how the crypto in iMessage worked. And I noticed really just like a basic observation that they weren't using authenticated encryption. They were using sign encryption and they weren't using it right. So that meant they might have some kind of padding oracle at a format oracle attack in their system. So the next day when I was giving this a talk to the entire Apple security team, I put this in the last few slides of my talk and I said, look, you folks, you have this problem here. You're not authenticating. There might be some kind of padding oracle unless you have some kind of extra protocol level check that makes this attack not work. And Apple doesn't talk to you. They like wink and twinkle their eyes at you because they're not allowed to share information. So I looked at the head of the security team and I swear that his eyes twinkled, which to me said, yeah, we have some kind of countermeasure to this down at the protocol level. About two, three months later, I went back with my students and we actually looked to see what that countermeasure was and there was nothing, there was nothing at all. So later on we spent three months or so trying to exploit this. It involved a GZIP format oracle attack. We did all this work. We went back to Apple and we said, hey, we pointed out this vulnerability, you know, we should get credit in terms of the disclosure timeline for telling you this and they said, what vulnerability? We have no recollection of any of that happening at all. So the point is just telling people like you're not using encryption correctly, you should use authenticated encryption. Doesn't make them do anything. When you come to them and say we can exploit this and decrypt your ciphertext, suddenly they care. But unfortunately that's incredibly painful. I just want to give you some examples of recent work in the crypto and the systems community of people doing this. These don't have dates, but they're all within the last few years. Some folks probably here did them. There have been exploits on XML encryption that take advantage of the fact that parsers can leak information about well-formedness of ciphertext. There have been examples, eFail a year or two ago took advantage of GZIP compression just like the iMessage attack I mentioned did. There are other kind of miscellaneous problems with PGP parsing. It's a little unfair to pick on PGP because PGP sucks, but like obviously you know there are going to be things like that. And then of course we have this recent talk about padding oracles still cropping up and in new and exciting ways and I'm not giving you a full list here. I'm just giving you like the quick examples I could find by searching. The point that I want to make here is even though just by searching for five minutes I can come up with maybe eight or nine papers on the subject of format oracles and modern protocols, this is almost certainly the tip of a really, really big iceberg. And the reason this is the case is that if you see any protocol that's not properly authenticating the encryption or is vulnerable to non-sure use attacks, it is almost certainly vulnerable to some kind of format oracle attack. You have to dig down into the code of whatever it's doing deep inside of message parsing. It might be incredibly complex. It might involve compression and some kind of like proprietary binary format on marshalling but there's going to be something there. The question is how easy is it to exploit? How much data can you get out of it? That's the hard part and that can take months and months for human beings to actually figure out. And you know just knowing there might be a vulnerability doesn't tell you how much you can actually do with it. And so the problem with this is we have some really smart people in this audience spending time poking at these protocols and trying to make or break them when we shouldn't be doing that. We should have the computers we use be doing that. So the solution to this problem obviously is just to get rid of the human beings. Not like that. We want to do it in a way that's helpful. So we want to build machines that can actually help us do exploitation in a useful way. So the idea of this talk or this work is we want to try to automate the development of novel format oracle attacks. So I don't want to just execute things that have been done before. They're really good works like some of the things we saw in the last session that do that really well. We want to take format oracles that we've never seen before. We want to come up with exploits and determine exploitability and go from there. What does that mean more concretely? OK, let's assume we have the following ingredients. So we have some knowledge about the system we're attacking. Specifically, we have a machine readable description of a format checking function. I'll talk about what machine readable description means. Maybe it's Python, but we'll go from there. We also have some kind of machine readable description of the malleability characteristics of the symmetric encryption scheme that we're working with.  I don't want to have to reason over an entire encryption scheme, but I might want to know that when I flip certain bits, this is going to happen after decryption. So that's the kind of thing that I want to know about. We want to have a target ciphertext C star that we want to attack. And of course, we need a format oracle. So the goal is using that information with no further human interaction, derive an adaptive chosen ciphertext attack that will recover as much information about the decryption of C star in, you know, as little time as possible. So this is basically, you know, kind of our goal. So we want it to be fast in terms of the number of queries it takes, and we want it to be fast in terms of wall clock time as well. Okay. This slide is standing in for a lot of works that I'm not explicitly citing, but they are cited in the paper. There is some work in this area that doesn't focus on this specific problem, but does focus on the problem of side channel attacks, which is really interesting. It does basically symbolic execution of like Java code, and it uses SAT solvers in ways that are related to what we're doing, basically tries to solve a related problem. You can actually show there's kind of an equivalence between these two problems. The problem with the works that I've seen, they're really, really interesting techniques. And I'm trying to sort of figure out how they translate into our techniques. Unfortunately, most of the results in those papers deal with very, very small secret domain sizes. So, for example, a couple of the papers, the secret is restricted to being three bytes long, and the size of the message is very small. There's some work where you have like modular exponentiation side channel attacks, but the modulus is maybe like 10 bits long, or like 30 bits long or something. So, these techniques work, but it's not clear how scalable it is. We want to be very scalable, so this is the direction we're going in. All right, so reminding, just to remind you, the basic attack setting that we're in looks like this. We have this ciphertext, C star, we want, we know it encrypts some unknown plain text, M star. Our goal is to decrypt this, or if we can't fully decrypt it, get as much information as possible. And we want to do this by basically adaptively coming up with experiments that we can submit to this online decryption article. All right, so any time you develop an adaptive chosen ciphertext attack, you're doing something like the following, whether it's a computer doing it or you doing it. The first thing you're doing is you're building up a set of initial constraints on the unknown message, M star.  You're going to take that experiment, you're going to run it. And then having run it, you're going to use that result of the running it on the actual oracle to increase or extend the set of constraints. And if that works, you go back to step two and you continue that process adaptively until you can't do it anymore. That's the entire nature of pretty much every adaptive chosen ciphertext attack. Now, it should be obvious that the hard part, all the actual work comes inside of this step two. How do we generate useful experiments? Because everything else is just a constraint solving problem. To do this, we're going to need to introduce or at least talk about a couple of building blocks. The first building block, and it should be pretty obvious based on what I've said so far, is we need to have some kind of solver that can reason over constraint systems. We're going to work with constraint systems. The obvious tool is to use theory solvers. These come in two flavors. The most famous flavor is SAT solving. We know that we have a bunch of nice research slash production SAT solvers that can solve pretty complex formulas, typically given in CNF form. We also have these great SMT solvers like Z3, which extend the logic beyond SAT to other sorts of maybe bit vector arithmetic, other kinds of logic that we can use. The nice thing about these SMT solvers is they also provide a bunch of simplification and additional tools that normal SAT solvers don't provide us. This is just something we're going to use as kind of a black box. The good news about theory solvers is that they exist, they work. If we have a set of constraints, we can solve. This is terrific. The bad news is they don't solve our problem. There is no notion in a theory solver of basically getting a theory solver to say, hey, generate an experiment that gives me useful information. If you have a set of constraints, you can solve, but there's no kind of idea of an oracle query inside of a theory solver. So we need to come up with some way to do that. The next thing we need is we need to talk about what we're actually specifically going to say when it comes to encryption malleability. So we want a reason over the scheme's malleation properties. We need to define that. The pretty basic way to define that is to define a pair of functions. We'll call them the ciphertext malleation function and the plaintext malleation function, not surprisingly. And they work as follows. So each of these functions takes in some string. We're going to call this string, it's the S up there. We're going to call this the malleation instruction string or just a malleation string. Ciphertext malleation takes in a ciphertext and this malleation string and spits out a new ciphertext, hopefully in the same domain of valid ciphertexts. The plaintext malleation takes in a plaintext, does the same thing with the same kind of malleation string and spits out, in this case, I'm saying just a new plaintext, but it could spit out a set of plaintext. In fact, for some schemes like CBC mode, it actually does do that. Okay, so we have to specify a few things. You should think about these. They're really obvious examples. If we're just dealing with simple XOR based stream ciphers, both of these functions could be realized using simple XOR. Treat S, the malleation string, as just a string to be XORed into the plaintext or the ciphertext and you're done. They're the same function. CBC, as we saw in the previous talk, is a bit more complicated because if you flip a bit in a particular block of a message, you essentially trash upon decryption that same block in the plaintext because you're using a pseudo random permutation. So you have to define a more complex malleation function and that can be a little bit more interesting. But malleation functions don't have to be limited just to XOR. You could have malleation functions that do editing, that do truncation, that do chop-chop attacks, do all kinds of things. The point here is we don't care. From our perspective, S is this opaque string. It can specify any set of instructions to these two functions. We don't care about the nature of S. We care about the description of the functions as we go forward. So now that we have these ingredients, let's talk about at a very high level what this technique looks like. So when we start the attack, we have a set of initial constraints. It's called this G0. This formula basically tells us everything that we currently know about the plaintext that underlies the ciphertext. Now, G0 might be null. We might not have any information or we might know it's a valid ciphertext and that sort of restricts the space a bit. This really terrible visualization, my students call this the amoeba, basically just gives us the set of messages that could be valid. I've cheated a little bit by showing you that one of these is actually M star, but we don't know that information when we run this attack. So we start with our initial constraints. Our high level goal is to spit out an experiment. In this case, an experiment is a concrete maliation instruction string S that we can use to mall the target ciphertext and submit to the oracle. And the goal is we want to come up with an experiment that's going to eliminate some of these candidate plaintext messages so we gradually reduce our space down until we get the actual M star. The real question is how do we identify the experimental string S? What do we do? How do we guarantee that we come up with a string that's useful? We could pick it random, but these strings are large. If we have, let's say, a 512-bit long counter mode encrypted message, there are a lot of possible maliation instruction strings. There are 2 to the 512 approximately. We can't just guess. We have to do this in a principled way. So the way we do it is as follows. What we do is we ask the solver, given our knowledge of G0. We ask it to find two different messages. We're going to call them M0. This is a toy example. This will not be efficient, but this inefficient approach works as follows. We ask the solver to come up with 3-bit vectors. One of them represents a first candidate plaintext M0 drawn from the set. The second one represents a second M1 also drawn from the set. They have to be different. And a maliation instruction string S that has a specific property. And the property is this. If we were to run an experiment using this candidate maliation string S, we would be guaranteed to get either a 0 or a 1 result from the oracle. We could use that result then to add a new constraint to the existing constraint system. And what we require is that adding that new constraint will definitively rule out one of these two messages. So roughly speaking, we're just going to basically enforce this equation on the solver. Solvers are good at solving this kind of thing. And then we just ask it to do that. Terrific. It comes up with some concrete value S. We now conduct the experiment. We send, we maul the ciphertext and we send it off to the oracle. And the end result is we get back a concrete bit B from the oracle. We add a new constraint of this form. We add it to G0 to make the next iteration of the constraint system. And we're done. So this is a beautiful attack. If you run it on a plaintext of size 2 to the 24, it runs in less than an hour. It's incredibly cool. You can do it. If you run it on a plaintext space of size 2 to the 128, it does not ever come back. And the reason is obvious, right? All we've really guaranteed is that at least one candidate plaintext is going to be eliminated each round of this process.  If we have 2 to the 128 candidate plaintext, we'll be running this forever. We might get lucky. Some of these queries might eliminate many possible values, but we're not going to be doing this in any reasonable amount of time. So this does guarantee progress, but it's not very efficient. So we need to make this more efficient. So we need to maximize the cut, basically. We need to make sure that as many plaintexts get eliminated at each set as possible. So here is the, if we didn't care about the limitations of actual solvers, it's a very obvious and simple solution. What we want to do is instead of saying, find me two different messages and emaliation string, we just ask the solver, find me two different subsets and make them as large as possible. Make sure that every single candidate plaintext within a given subset shares the property that, you know, that first candidate plaintext would have, meaning that all of the values in one subset will be eliminated when we get a concrete result from the oracle. If we make sure that we get these large classes of subsets and we can eliminate one of those two subsets, they're disjoint, we can eliminate them after each query and we make them very large, then we're gradually going, we're going to much more quickly winnow down the space and after a much smaller number of queries, we're going to arrive at the candidate plaintext itself or quit. Does that make sense? Okay, good. If we lived in a world where this was actually the way we could use solvers, this would be a great solution. We just have to make sure the size is as large as possible. It becomes an optimization problem. We tell the solver, just find the set that matches these properties and maximize it. But in the world of theory solvers and SAT solvers, nothing is good. Like everything is bad. Everything you want to do beyond simple equations turns out to be really, really hard to do. And it turns out that that kind of thing is not easy at all to do. So we have to think a little bit harder about the way we do it. So there do exist, this is the good news, there exist SMT and SAT solvers that can reason over sets. They're experimental, there's one out of Stanford, there are a couple of others that have tried to add set logic to the first-order logic that the solver handles. The problem is that the sets I'm talking about are small sets. They're sets that like, you know, the number of people in this room kind of sets, not sets like 2 to the 128 or 2 to the 256 or larger. When we start to talk about large plaintext bases, we need to reason over very, very interestingly large sets. And this is not going to work at all. And worse, even if we start working with those set solvers, we don't have a notion of set size, solution size maximization. You can maximize variables, but you don't have a way to say, find me the solution that has the most, or find me a value S that gives me the largest cut for these two variables. It doesn't work like that, or at least most of the time it doesn't. And things get worse. They get like much worse. And by the way, you have to understand I'm coming at this with zero knowledge of theory solving and learning like way too much as I go in. It turns out that this problem, even the problem of counting the number of solutions to a given constraint formula is a very, very hard problem. In the solver community this is known as model counting. And model counting is something where there is an enormous amount of work, some of it's successful and some of it less successful. This problem is actually a version of the sharp set problem. And sharp set is theoretically actually pretty hard. It's strictly harder than sat. It's sharp P complete. So we've kind of wandered into a domain that's sort of like dragons are all around us just by trying to tackle this problem of just counting, forget about the optimization. But the great news about the solver communities, they don't care about whether something is NP complete or P sharp complete, it doesn't matter, sharp P complete, they're willing to try.  When you think about how a solver works, it's basically reasoning over a large tree of possible solutions, it's trying to eliminate as many solutions as quickly as possible. And you can, if you're lucky in the fact that all of the solutions that satisfy your constraint formula live in a particular subtree, you can get lucky and you can be able to count that very efficiently. If you're not lucky, and if you happen to have a particular constraint formula where the satisfying assignments to that formula are sparse and finely distributed all over the tree, it's actually very hard to do this kind of counting, it often just fails. And the problems that we're dealing with here tend to be the latter kind, the kind that are not well distributed for exact model counting. So this approach probably is not viable, maybe in the future it will be. So when you can't do something exactly, the obvious answer is to approximate it. And we can deal with approximation, we're just trying to make something more efficient. So maybe we can find a way to do it approximately that gives us a pretty good solution. And the great news is there are some really, really efficient approximate model counting techniques that work with existing solvers. The old idea is the basic idea, the one that is most commonly used with a lot of refinements is due to Valiant and Vasarani from the 1980s, even before solvers were a thing. It's a really kind of cute, obvious in retrospect, and I hate to say obvious, it's the worst thing to say, but it's so elegant that you think, why didn't I think of that five minutes ago? The basic idea is this, you start with some constraint formula. You want to determine whether there are approximately two to the N possible solutions for that formula. Well, if you just go and you ask a solver, whether there's a solution, it will come up with either one or it will say unsat. So what we have to do is we have to add some additional constraints that reduce the number of possible solutions, it seems obvious. So if we want to know if there are two to the N possible solutions, we want to add some constraints that reduce the number of possible solutions by approximately a factor of two to the N. Seems easy enough, but we need to do it in a way that we are reducing the number of solutions uniformly, so we're not going to be dependent on the structure of the underlying data. And the way you can do this is using pairwise independent hash functions. So basically using universal hash functions, which turn out to be very easy to implement using parity checks or parity constraints, you basically construct a series of N universal hash functions, each of which outputs a bit. You add those on to your initial constraint formula and then you run the SAT solver on that revised formula. If you get a satisfying solution, the logic is that you should have approximately two to the N underlying solutions to the original equation, it seems pretty reasonable. It's probabilistic, it doesn't always work. Sometimes you have to run multiple trials to see if you can increase the probability of getting a good solution, but roughly speaking, that's it. It's a beautiful and simple technique and it has been used for counting. When it comes to optimization, it's a little trickier to actually figure out what the underlying theory is, but it turns out empirically, it just works in a really kind of lovely way. So what we do is we modify our original idea from a few slides ago. We take this idea of find me M0 and M1 as well as a maliation instruction string S, but now we add N hash constraints to each of the values M0 and M1, which tells us that we should only get a maliation instruction string back if we are actually identifying not just an individual message for each case, but a large set of size approximately two to the N. If we don't find a solution for this new revised equation, we reduce N and we try again. So N gradually falls down and we're identifying looking for smaller and smaller cut sets until hopefully we find one and then we use the resulting maliation string, which should reduce the space by a significant amount. And so this kind of eventually gives us a new algorithm. This is the basics of our algorithm. There's a lot of detail in this in terms of the number of trials we have to run, how we build the actual queries we make to the solver, but this is kind of the basic idea. Okay, so this is the first, I would say 10% of the work and everything else comes down to agony.  I started with the idea that SAT solvers are magical and it turns out that when you actually have to use them, like SAT solvers are horrifyingly bad. So we started out by trying to work with a bunch of different research and production, SMT and SAT solvers, but I hope nobody here is offended by that. Sorry, if you work on solvers, they're wonderful, you're the best. I'm sorry, I didn't mean anything by that. We started by working through a bunch of these. We found that some of them were really good, but unfortunately they didn't handle the Gaussian reduction that we need to do XOR. These very complex XOR constraints very efficiently, like Z3 for example, doesn't handle XORs. There's an exponential increase in the number of gates. If you feed it big piles of parity constraints, they get exponentially blown up into much larger CNF formulae, which take forever to solve. So it's totally unworkable. There's basically one solver out there called Crypto Minisat that can handle this kind of stuff very efficiently. So we tried to use that. It connects to an SMT solver called SMT. We tried that, unfortunately we started to realize that we were working in a domain of solver queries that like nobody else was working with. And we knew this when we started feeding bit vectors into the SMT solver that were of size 65 bits and the solver began to just completely segfault. And it turned out that the people who were developing these solvers had made a specialized data structure for bit vectors under 64 bits and bit vectors over 64 bits and had apparently never tested the bit vectors over 64 bits because it was done by a grad student. So we went back in, we said this'll be easy to fix. Turned out it was actually a giant one million line commit.   So it was really bad.  I mean, people are working on these in their spare time. It's just to point out that like for this particular scale of problem, let me give you one more reason why I'm sort of surprised by this, there was a paper at Usenek security that was doing fuzzing and they were doing fuzzing. One of their targets was one of these solvers. And for me, I was like, why do you have to fuzz them? Just ask them to solve a problem that has more than 64 bits. Like this is not like a hard thing. So it turns out that when you're dealing with these particular class of problems, they're not well tested at all. Z3 is very good. The rest of everything else is kind of the Wild West. So we had to do a lot of painful fixes. We sent some code upstream. Ultimately, we decided on this really ad hoc jerry rig solution of using Z3 to output CNF files that are then eaten by crypto mini-sat. And this unfortunately reduces our performance by 90% which turns out to be better than using any of the other combination of solvers. So we're working on a direct integration between Z3 and crypto mini-sat because it's a cool tool but we just haven't done that. So our results are much slower than they should be. Okay, so the result of all this is we built a tool called Delphinium. Delphinium is ultimately intended to be a practical tool that cryptographers can go out and use to actually build exploits. It's not quite there yet, but I wanna show you kind of some examples of what it can do today and hope that it can do more in the future. So we saw the PKCS, we saw the TLS padding example, the CBC mode padding where you actually throw padding bytes onto the end of a cypher block. This is just a quick overview of kind of what that looks like. The string down here, the bottom string is a plain text that has several bytes of message followed by five bytes of padding. Each of these bytes has to be five. If you go to an undergraduate and you say go implement a PKCS seven padding oracle attack, what they're gonna do is something like this. They're gonna come up with a maliation string that changes those bytes of padding by causing them to increments. Your plain text maliation function is gonna be the XOR function that causes them to increment to a six. And then what's gonna happen is the format oracle is gonna look at those bytes and compare them to the last byte of the message.  And so to fix that problem, you have to iterate through every possible maliation of that last message byte until you get a match and that tells you what the last message byte is.  What I'm showing you here is just the maliation strings, the XORs that are added to the cypher text. That looks like this. It's kind of intuitive and I'm gonna just zoom in on this. What you see in the zoom is you see that somebody has kind of mauled the rightmost bytes of padding a little bit and they are now counting their way on the sort of leftmost byte. They're counting their way through all the possible solutions until they get lucky and find one and then they increment leftwards. This is what a human being does. So let's take our pkcs7 padding code. This is implemented in Python. Let's feed it into the solver and see what it starts to produce. And what we get looks like this which actually isn't that surprising when you think about it. You notice it's a lot noisier looking than the human attack. Let me jump in. It takes about the same amount of time in terms of queries as the human attack so it does develop the attack but it looks random, right? So clearly everything on the left side is now unconstrained to the solver so it's picking arbitrary solutions there instead of the pretty white space that we saw in the previous attack. But also you can sort of look at this and you're like what's happening in that leftmost padding byte? Is it doing something new or is it just counting? When you go and you actually sort these results, you find out that actually it is just running the counting attack but it's doing it in the order it pleases. So basically we have kind of ground truth that it rediscovers the standard padding oracle attack you would expect but does it with about as much efficiency as a human being? I'm just gonna show those two attacks next to each other so you get kind of a visualization of what the human and the machine do. Another way we can look at this attack is we can say how much of the message space gets cut after each query. So here we have, by the way, this is just two examples. So the difference between the speed of these is basically down to the fact that these particular runs happen to come out this way, they can be faster or slower depending on what happens. But here is basically the purple line is the machine developed attack and you can see it starts at about two to the 120 something possible candidates based on the left side. And as it goes, you can see it's making jumps downward by about a space of two to the eight. So it's finding one byte at a time with this little kind of bent downward trajectory. You can see that the machine developed attack and the human developed attack are doing basically the same thing. So we can actually see progress in the same way. So we came up with some of the other examples that were new things. We came up with a bitwise padding scheme. This bitwise padding scheme's a little goofy. It basically says at the right most bits of the plain text we're going to have a series of bits that give the padding length in bits and then every previous bit is going to be set to one and then you're gonna have to the left of that the message. What happens when we feed that in? This is just much easier because it's a padding scheme that's guaranteed to give us about one bit of information per query and it happens that we get a very similar looking attack. You can see the solver basically coming up with these queries and rapidly kind of fixing individual bits of the padding and the message as you go down until it basically figures out the message after about 153 queries in this case. Okay, so the other example that we have that we worked out, don't ask me why we did this, but we know that set solvers are great at solving Sudoku. So imagine that you have a encryption protocol that involves encrypting Sudoku boards. Sorry, this was just a ridiculous example. It's a small Sudoku board. It's a four by four Sudoku. So we're not really killing ourselves here on the size of this, but we encoded this four by four Sudoku board as a ciphertext and we basically said, here is the ciphertext, go try to solve it. So what the solver can do now is it knows the rules of Sudoku, which is our check function. It can go and it can mall the ciphertext and try to switch things around and what it gets back is, was the resulting decrypted board a valid Sudoku? And what's kind of neat is after seven whole queries to four by four board, it basically comes back with the actual, we give it a Sudoku board that's valid, it tweaks it for a while and it comes back. What you can see on the right side is the solver's knowledge and on the left side you see the actual query that it's making when you decrypt the ciphertext. And you can see it kind of like fiddles around for a while, gradually figures out, hey, this particular square is a one or a two or a three and its knowledge becomes more constrained over time and then all of a sudden it has the right solution. So these kind of things show that this works. Obviously we wanna do things that are more interesting than Sudoku. This is kind of bound by engineering problems right now. So we're working our way through it.  Obviously using these stream ciphers is kind of silly. We wanna use other modes of operation. CBC is a little more complicated because as Robert showed, when you flip a bit in a particular block of a CBC ciphertext, if it's not the IV, you trash the resulting decrypted plaintext. This is actually a little bit hard to encode to a solver. You have to tell it, hey, you can't trust any of the bits in this plaintext because they're pseudo random. There's no way for your maliation to predict what's gonna happen to them. So we have a different encoding scheme where we can actually tell the solver that it should not reason over those broken bits and it should only reason over ones where it can save for certain what's happening. And that actually guides the maliation string selection. It will avoid breaking ciphertext in interesting ways and it will constrict its changes to the ciphertext to places where it can actually get results. So this is kind of working backwards from the nature of the scheme to the actual solution. We also have solutions that do truncation. So it's much easier in some cases to truncate the ciphertext size, either by a whole block or by a bit or a byte. And the solver will gladly go out and it will find the right truncation for you and it will go and it will make its life easier. We can even make the solver hunt down the best truncation that will reduce the amount of time it takes to solve. So there's a lot of work there you can do. There have been some recent vulnerabilities. One of them was in OpenSSL and there are some other formats that we're currently running experiments on. And so we're trying to develop some kind of novel attacks for things like GZIP encryption. We're trying to show that you can actually do, not GZIP encryption, GZIP compression, that have some different formats. And so we're sort of working those to the solver. The reason that we don't have results on those, unfortunately, is that we haven't been able to steal enough compute time to actually get these things done. So one of the experiences that I've had in doing this work is finding out for the first time in my career that I actually need to buy computers instead of just relying on Nadia to loan me your computers every now and then, which has been great in the past, but it turns out that these SAT solvers are incredibly intensive and we burn through a few thousand dollars of Amazon time just kind of getting the basic results that we have. So there's a huge amount of work here in optimizing and we think that the value of this is now we're working with some of the people in the SAT solver community to actually take these problems and consider them in the design and optimization of their solvers. The problems are really interesting. We're working with CNF formulae that are on the orders of hundreds of thousands of constraints and variables. Whereas a lot of the tests that people use in SAT competitions are maybe 10,000 variables. So we're really kind of pushing this to the outer edge of what SAT solvers can do right now, but I think there's a lot of room to optimize and actually solve useful cryptographic problems here. There's a lot of future work in terms of other kinds of attack, for example, attacks on public eCrypto, attacks on side channels and so on. So I think we're kind of entering this area where we're actually gonna be able to make progress in building attacks, but this is just a first step towards that. So that's all, thank you very much. Please. Hi, Greg Rose, Tech Art Technologies. If people will live with me, I can give you an example of a chosen ciphertext attack in World War II. Okay. The attack that defeated the Japanese fleet at Midway, the Americans could decrypt the message, the Japanese naval traffic, but they super encrypted the location's names. So they'd get a message saying the fleet's going to assemble at such and such an island, but it didn't, there was a super encryption on the name of the island. And they couldn't get around that very easily. So the US sent messages to all of the different possible islands that they had bases on. With instructions, sorry, yeah, they sent messages to the islands saying, report back that you have a particular problem. In the case of Midway, they reported back in their regular report that they had a shortage of fresh water. And so when they decrypted the naval traffic, the routine naval traffic that said island X, Y, Z has a shortage of fresh water and another message that said island X, Y, Z is where we're going to attack. And yeah, so it was chosen ciphertext attack. I have heard of this one, I'm familiar with it. The debate that I've heard people have is, is this a chosen plain text attack or is it a chosen ciphertext attack? So I'm not sure. Okay, I'll give you that. Yeah, no, no, it's tough. It's really hard to find like examples where the US actually sent traffic encrypted traffic. If we could find something like that to the Japanese and then somehow saw the response, that would be amazing. I've just happened to find that. It's very tricky, but there were a lot of these kinds of attacks. It is, yeah. Thank you. Hi, I'm Markus Brinkmann from Boer University, Bochum. You have, and I'll talk, thank you. You have talked about the scalability problems when it comes to complexity, like pirated checks and XOR. Are you also concerned about the performance when it comes to scaling the actual application code, like PDF reader or email clients have a lot of code and do these types of scale to these programs? So I think that the answer is, and there was some work in user security where people were basically taking large programs and what they're doing is they're extracting kind of a simplified, and by the way, simplified means still huge. A simplified constraint set from the program. So I think the direction here is not, I may not be answering your question properly, but stop me if I'm not. But the basic idea is yes, if we just try to feed an incredibly complex application code that has everything in it, probably not gonna work. So the idea is to ultimately marry this to symbolic execution kind of techniques where we can go through and we can extract at least a simplified version of the constraint formula and then use these techniques to actually develop the attack. There is a big direct in that there. So if I can follow up on this, then this means you need to have an hunch which part of the parser, for example, like focusing on NAs and one parser or a PDF parser and not the whole application. Yes, yes, so I'd like to live in a world where I can just push those problems off to somebody else, that's like the best world to live in, but definitely like this is, if you have description of the system, what can you do? How do you get a description of the system that's useful for like this particular processor is a big problem too. Okay, thank you. Okay, I think now it's a good time to have the first coffee and to enjoy the coffee break. So please, let's thank the speaker again.


Welcome to Globe Fish Interviews, where we speak with leading experts on international trade and fisheries. My name is Joe Zalazny. Today, we're joined by Auden Lem, Deputy Director of FAO's Fisheries Division. Auden, it's great to have you with us. Nice to be here with you. Well, Auden, let's get started. Last year, FAO celebrated the 25th anniversary of the Code of Conduct for Responsible Fisheries. Fish production and trade is an important economic and social activity in many regions around the world. How does the Code of Conduct foster sustainable trade and strong participation of developing countries and small scale fishers in national, regional and global markets? Well, the Code of Conduct, although it was established more than 25 years ago, it was really a forward looking document. It sets at the very high level the principles of sustainable trade, sustainable production, and also the sustainability of social sustainability. So it really includes all the three dimensions of sustainability. And then what about trade? As I said, it sets the principles. So the details of how to implement sustainable trade is then developed both globally and regionally and nationally through other instruments, implementation instruments, such as either national legislation, international agreements, the framework, for example, of the WTO. And of course, the Code of Conduct says specifically that anything that deals with trade should be within the framework of the international rules set down by the WTO. And what then about specifically sustainable practices, sustainable trade? Well, as I said, the Code of Conduct sets at the very high level the principles of sustainability, including that of sustainable trade. And we have developed a number of guidelines that flow, that come out of the Code of Conduct that subsequently have been adopted by the international community, have been endorsed by FAO members, and therefore fostering international trade in a sustainable manner. For example, the guidelines on catch documentation schemes, which allows for proper traceability and the legality of products when the international trade come out of the Code of Conduct. The same with the guidelines, the specific guidelines for sustainable trade. Again, the Chapter 11 of the Code of Conduct deals with trade and deals with how to make it more sustainable. And we have developed guidelines that have then been endorsed by our members and are being implemented also nationally by policy makers, but even more important by the industry, by the stakeholders themselves. So I think the Code of Conduct, although inspirational as a voluntary code, it really has encouraged and made a number of instruments and tools come forward that really ensure that trade and markets and consumption is now much more sustainable than it was in the past. Of course, there is still potential for improved things, but the principles of further improvement are there and can be found in the Code of Conduct. Access to market information, such as prices on fisheries and aquaculture products is an important step towards ensuring producers have equitable access to markets. How is FAO contributing to this end? Well, FAO in general and globally specifically is making available a number of data, a number of information that is really useful for the operators. First of all, FAO is the only agency or organization in the world that provides global statistics for production, for catches, for aquaculture production, and also specifically for trade in fishing and fishery products. So in that sense, FAO provides a lot of very useful information for policy makers, but also for operators. Then specifically, globally, which of course provides up-to-date market information, price information for a number of very important products in international trade. It provides analysis on trade trends, on markets, on consumption trades in all major markets of the world. So in this sense, also, Glowfish fulfills a very important role as a provider of information, but market access is more than information on products and more than information on prices. Glowfish is also doing an excellent role in providing information on import requirements, what to do in order to be able to export to the most important import markets in the world. Of course, the EU, US, Japan, but also many other important markets. And in fact, the markets in the world that really are growing the quickest now are in emerging economies, in Asia, but also in a number of other very important emerging economies of the world. So Glowfish, together with its sister network of regional organizations and organizations such as InfoFish, Infosamac, EuroFish, InfoPesh and InfoPesca are together providing a lot of information, not only on the products and prices on market trends, but also what to do in order to be able to fulfill the import requirements in these markets, especially related to quality and safety issues, but also to legality of cultures, of traceability, et cetera. So also for this first purpose, Glowfish is doing a very important role together with our colleagues in FAO as such. Glowfish is a long-established source of information on trade in fisheries and aquaculture products. Are there any new products being developed that we can expect to see rolled out over the coming months? Well, since Glowfish started out more than 35 years ago, a lot of things have changed. Of course, and Glowfish is changing and evolving, not only because of new technology, IT technology, but also because the needs of its constituents are changing. Glowfish continues to provide the analysis on market developments, on input requirements, but also it's launching a number of new information products, more interactive, more innovative, and increasing also the dialogue with stakeholders to be able to ensure that what is provided, it really reflects also the needs of the industry and the stakeholders. So Glowfish is really changing and evolving with the needs of its constituents. Some have argued that exporting fisheries and aquaculture products can diminish food security for local communities. Is international trade compatible with raising social, nutritional, and economic standards in local fishing communities? Well, I think that when we look back over the last 25 years after the implementation or the endorsement and implementation of Kodokondog, I think it's incredible the changes we've seen in production, in consumption, and in trade. And I think one of the biggest achievement of the fish and fishery sector in this period has been its ability to produce more and to raise consumption patterns, consumption of fish and fishery products all over the world to an average today of 20, 21 kilos. And of course, this is done through increased production, through the stability of capture fisheries, but in particular the increase in aquaculture production. And of course, this reflects and responds to changes in demand and changes in the consumer habits. Now, is there a conflict between exports and local consumption? I would say no. As long as the fisheries are sustainably managed, as long as fisheries are sustainably managed, there is no problem as such in exporting products because exports are not only allowing consumers in areas with no access to waters or no lakes or no oceans, but an active population that needs a supply of fish and fishery products. But certainly it also raises the economic well-being of people in the other population in the exporting countries through job provision, through processing activities and trade and export activities. It also allows the generation of very important revenues from exports. And in fact, if you look at some of the countries with the lowest levels of consumption of fish and fishery products in the world, you still see that they do export and that they may have a net export in terms of value, but they do import more in terms of volumes than in fact the exports. So even when you have important activities in export, this also allows you to import and very often what is exported is high value species that is not always the most nutritious, lobster and other high product or high price, high valued product that allows you to import a number of much larger numbers of very nutritional fish and fishery products, such as small pelagic. And this is the pattern, for example, that you see in regions such as Africa, which prefers exporting high value products and import with the export revenues generated, very nutritious products such as small pelagic, mackerel in particular. But again, the key to this is sustainable management of the resources you have in order to enable you to continue the export in the future. That's a good point and something to keep in mind. Trade works in both directions. It's not only experts, but also imports. Next, I'd like to ask something about a new trend that we've seen. Increasingly, consumers are demanding more information about the products they consume, including about the social and environmental impacts of their production. How is this trend affecting the international trade of fisheries and aquaculture products? And how can FAO support the sector in adapting to these new trends? Well, the trade, the trend we see in which consumers and all actors, I wouldn't only eliminate the consumers, but consumers certainly, but also retailers and traders and the public at large, seeking more information about what they eat, what they consume, what they drink. And of course, this also affects us in the fishery sector. FAO, of course, supports this need and drive towards more transparency on trade, on production methods, on the legality and the origin of the product and how the fish was produced or caught or farmed and where it was caught and farmed, and what are the tools, the production methods, the nets or the trolling or the pursing or whatever is the activity or the type of farming. We all support and encourage this provision of additional information that consumers in the past did not seek as they do today. And consumers really, of course, also want to ensure that what they consume has been sustainably produced. And not only from an environmental point of view, they want to know that it has been farmed sustainably and caught sustainably, but they also want to know that it has been done from respecting the social aspects and the well-being and the livelihoods and the decent working conditions of those or the millions and millions of people, men and women that are engaged in fish and fishery products. So FAO are encouraging this. We have provided a number of guidelines, whether it's on certification as such, but also now more and more on decent work and on the social responsibility of the operators. And this is something we are not doing alone. We are doing it together with FAO members, with stakeholders, with other agencies, such as ILO, UNCTAD and others. And this is something that we are being encouraged to intensify this work. And we are doing this, in fact, right now through regional consultations, and we will bring this to the subcommittee on fish trade and then to COFI for its further recommendations on this. And just to say something finally on this, it's been very encouraging to deal with these issues. And I must say that in particular, the response from industry, whether we talk about producers or distributors or retailers, I think this support has been very encouraging and will ensure that the final result is also robust and can be useful and practical for the operators. That's great to hear. FAO isn't just on the sidelines watching these trends, but is using its convening power to bring people together to foster conversation, to reach consensus and help the industry respond. Now, changing gears, I'd like to talk about the COVID-19 pandemic. Everybody is living it and it's had a profound effect on the fisheries and aquaculture sector, like all sectors. Despite the many negative impacts caused by changes in demand and consumption patterns, as well as disruptions to supply changed, caused by mitigation measures that were put in place, particularly at the beginning of the pandemic, some positive market opportunities have also emerged. We've witnessed innovation and seen a reorientation toward local and domestic markets, as well as the creation of new products. What lessons can be learned from these opportunities? And do you think that these changes are here to stay? Of course, the COVID-19 pandemic has been a terrible event, which is still ongoing with incredible consequences for all economic sectors, including the fish and aquaculture sector. Of course, the first thing we did was to work together with the stakeholders in developing policies for how to ensure the safety, first of all, safety of the millions and millions of men and women that are engaged in fisheries or aquaculture and distribution. And then further to ensure that food production was continuing, that supplies of food and of fish and fish and products would continue to go unhindered as much as possible in order to reach consumers that need fish and fish and products. However, as you allude to, there also have been some positive outcomes or some outcomes that also have been positive. You mentioned innovation versus digitalization, and I would also say that a number of processes that we use have become safer because they've been standardized, they've become more digitalized and allowing for a smoother pattern of work. And of course, this will also make the operation in the future more smooth and easy. Also in terms of development of products and changes, we've seen development in new packaging, of course, safer and more sustainable packaging, maybe a change in sizes because of the tremendous impact on the catering sector in particular, which has then forced the operator to channel more products that direct consumption. We've seen innovation in terms of distribution and the way products are sold through electronic platforms, et cetera. So I think this is something that will remain. So it's not that the COVID has brought along so much change, it's that the speed of change has increased. We saw these trends already, but certainly the pandemic has increased tremendously the speed of change. And I think this we will only see and I think it has also opened up the minds, not only of consumers, but the operators of the many opportunities that exist out there. Now we all work virtually electronically. So I think it has also overcome the physical distance that in the past was a barrier to many of the ways and the contact that we entertain. Now I think the world has, or the sector has become even more globalized than it was. It was already one of the most globalized sectors in food production with one third of everything that is produced farmed or caught entering international trade. So among food sectors, I think it's not wrong to say that our sector is the most globalized, but this pattern of globalization has not stopped. And I think it will continue at a quicker pace than we've seen in the past. So perhaps a little silver lining to this pandemic and maybe moving forward, greater opportunities for producers and also more options for consumers. The last question I want to ask you today is related to FAO's work on fisheries and aquaculture, which is guided, of course, by the Committee on Fisheries, which is where member states consider relevant international policy issues, as well as the subcommittee that deals specifically with issues related to fish and trade. How are the decisions of these committees affecting the global seafood market? Well, as you mentioned, the FAO's Committee on Fisheries is the only international forum which really makes recommendation on issues related to fisheries and aquaculture issues, whether they relate to aquaculture production or fisheries management or trade, et cetera. And I think these meetings that take place every two years with up to 700, 800 participants are doing a very important, playing a very important role, but in order to facilitate their work, some of the technical work has to be prepared by what we call the two subcommittees, so one subcommittee on aquaculture and one subcommittee on fish trade. In particular, the one on fish trade has then developed through expert consultation, technical consultations, consultations at large with its members, with stakeholders, et cetera, in preparing the technical work that then feed into Kofi and then goes to Kofi for further endorsement. Some of the outcomes of the work of the subcommittee on fish trade, for example, are the guidelines from FAO on certification, on certification related to marine fisheries and to inland fisheries, for example. I mentioned already the guidelines on catch documentation schemes, which ensures the legality of catches of a product as they enter international trade. Also the ongoing work on social responsibility is dealt with by the subcommittee on fish trade. So again, being more specific, they're able to prepare the work at the technical level before it's moved to the higher level, to the policy level by the policy makers meeting at Kofi. So I think they're doing a tremendous work which is crucial to the work of Kofi by preparing it in detail before it goes to Kofi. Well, it's clear that the decisions of these committees in the form of the guidance they're issuing have an impact on the sector and influence the way seafood is traded. But where can industry go if they want more information about the issues and topics being considered by these two bodies? Well, the countries that come to Kofi, of course they come with all the subcommittees, come with national delegations and very often industry is represented in these national delegations through its national associations, not as individual companies. Of course, FAO is a very transparent organization and through its global project, to those of other programs, we make sure that the information we have is made available through our website, through our communication products in general. I would also say that industry, individual companies are encouraged to engage with the national or international associations and thereby interact with FAO and other agencies at the higher level. So certainly industry participation in national or international associations allow them also to interact with bodies such as the FAO. In terms of the agenda of Kofi and the subcommittees, of course, these are set in a dialogue between FAO as a secretariat and its member countries. There is a dedicated bureau of all these bodies which with national representation of the FAO members. Now, in terms of being relevant for the sector and for industry, of course, we deal mostly with policy issues, setting the agenda and therefore working on guidelines and other instrument that will one day also impact directly the operations of individual companies. And we try to be as transparent as possible in this by not only putting the agenda and the reports and all the various documents for the various meetings online, of course, well in advance of the meetings. And also I would encourage the industry and individual companies to become even more active through their national association, through international associations that have relationships with FAO and with other international agencies, whether they are Unktad or IMO or WTO for that sake. So we certainly encourage this engagement but through the FAO members and the industry association that are approved and registered NGOs and observers at our international meetings such as Kofi and the two subcommittees. Alden, it was great having you with us today. Thanks for sharing your insights and we hope to see you again soon. Well thank you Joe and I was pleased to be here. Thank you for joining this installment of Globe Fish Interviews where we speak with leading experts on international trade and fisheries. We look forward to having you with us next time when we'll continue the conversation. In the meantime, subscribe to the Globe Fish newsletter and get the latest information from our website at globefish.org. Goodbye for now.