Rust Programming Language RustFest Global 2020, 23 Dec 2020

Previous Meeting Next Meeting

⏯

youtube image

►

From YouTube: Diane Hosfelt & Amber Sprenkels - RFC: Secret types in Rust — RustFest Global 2020

Description

Using empty asm!() directives and empty functions, this talk will show how we can circumvent LLVM's optimizations, and make our binaries secure again. However, these tricks are ugly and unsupported on the stable channel. We need something bigger to solve this issue. We need secret types.

More at https://rustfest.global/session/8-rfc-secret-types-in-rust/

A

Dan and diane get us to the hype of keeping secrets in a type disallowing creation of some optimization that just might tell the fats what you type.

B

Hello, everybody I'm dan spankles and I'm with here with diane hosfelt, and we will be talking about secret types in rust. So the main gist of this talk will be that um there that, like some of you, may know that cryptographic engineers tend to like write a lot of their code in assembly, and um there is a good reason for that, and I will explain why that is. um But as a cryptographic engineer or an aspiring cryptographic engineer, I'd like to write my code in rust.

B

Instead, however, because of some of the compilation quirks in rust, that's not really a good idea, and I will explain why. That is the case and what needs to be done to make rust a programming language that we could actually use for cryptographic code.

B

While this talk is pre-recorded. Both diane and me are here in the uh at the conference and in the chat so feel free to ask any questions either at the end of the talk or just put them in the chat during the talk, and we will take care of them.

C

Hi I'm diane hospital, and this is batman and before we get started, I have a short disclaimer. All of this work was done. While I was a mozilla employee and in no way reflects apple's views.

B

Okay, so I will explain a couple of things and then diane will take over uh first we'll talk about how timing side channels work, what what are timing side channels? Why are they dangerous and then we'll talk about how rust is not suitable to write code? That is actually that actually prevents these timing channels.

B

We'll look at a couple of hacks that we could use to prevent some of these channels in rust.

B

But then we will go more in depth and look at the rfc on secret types to see how we could actually make rust more suitable for side general resistant code.

B

C

A side channel is any attack based on information gained from the implementation of a cryptosystem, not a weakness in the system itself, in this case, we're concerned about timing, side channels which occur when attackers analyze the time taken to execute a cryptographic system algorithm.

C

This can be seen as an implicit output, for example. Imagine that it takes less time to execute part of the code when a bit is zero than it does when a bit is one that difference is measurable and can lead to key recovery attacks.

C

These attacks are a particular threat in the post spectre. World they're primarily used to attack secrets that are long lived that are extremely valuable if compromised, where each bit compromised provides incremental value and where the confidentiality of compromise is desirable, the fix is constant time code or to be more precise data invariant code, where the time it takes to execute the code doesn't depend on the input.

B

Let me explain to you uh why at this point, it's really hard for us to to guarantee that the compiler is constant time. So this is, this story will be true for basically any programming language that is compiled. There are some exceptions, um but we're at the rest conference. So, let's, let's focus on rust.

B

So the main problem here is that compilers are, in some sense problematic, so compilers are allowed to optimize anything that they feel does not change the program um and the the the behavior like or the run time of a program and stuff like that is not it's not considered to change the program um in the view of a compiler, so so the compiler might actually optimize stuff that we don't think would be, would should be possible, and so, for example, there is there is this thing that lvm could do, which is eliminating conditional moves that may load, and let me show you an example of this.

B

Okay, so what you see here on the left is, I have written this nice little c-mop function and what this c-mo malfunction is meant to do. Is it should so? If this conditional value is true, what it should do is it should move the value in b into a, and if this conditional value is false, then then a should just remain. The same. Value and b should just be dropped and thrown away, but the important thing here is that that conditional value is secret.

B

We don't want to leak any information about this secret value, so the runtime of this function should be always the same time. The same length, the same duration like depending on the value of this conditional value. So what we do first, is we generate a mask from this conditional value, and the value that will come out of this mask will be something like either um only only once uh or if the conditional value is true. Sorry, if the conditional value was false, it will be a mask of only zeros.

B

And then we will use this mask so the first line here. What this does is if this mask is only once so, if the conditional value was true, then it will xor the value in a with itself.

B

So this will set the value in a to zero and then only if this conditional value is true, it will xor a again with b and a was zero here, so a will become, like a will, get the value of b and then, if, if this conditional null value was false and then this mask would be all zeros, then both of these these and operations will make sure that this value was zero, and this value was zero and both of these values.

B

Both of these operations would be a nope and then a keeps the same value, and now what we see when lvm compiles this and rust compiles. This is that that the compiler is smart, so the compiler sees hey this.

B

This behavior of this function completely depends on this conditional value. So, first, what it does is it checks. Is this conditional value? Is it actually zero? So is it false? And if it's, if it sees that this conditional value is true, it jumps to this instruction. So it skips this complete instruction, and if this this, uh this conditional value was false, then it just does this instruction then moves the under instruction and that's it. So, basically, in one of the two cases, it skipped this instruction and.

B

The important thing to see here is that, depending on this value, depending on the value of the conditional, um the runtime of the algorithm changes- and so here we have a case where the compiler introduced a side channel which could be a side channel vulnerability.

B

And the the interesting thing is that if we, if we only look at the source code in rust, it looks like something that, like it looks like code that that that feels completely like this could should be implemented. In constant time like we have this, this bitwise and operation this bit wide end and operation, and then these claw operations- and you don't even see them in the in the new implement in the compiled code, because lvm is smart enough to see that they are not needed, and this is actually a pretty big danger for us.

B

um So that that's that's what we mean when we say that compilers are a bit problematic.

C

Obviously we're at rust fest, so we've all bought into rust, but the question remains: if we can do secret invariant programming with assembly, why do we need to do it in rest? At all? Writing cryptographic and other security. Critical code in high-level languages like rest is attractive for numerous reasons: first, they're generally more readable and accessible to developers and reviewers, leading to higher quality more secure code.

C

Second, it allows the integration of cryptographic code with the rest of an application without the use of ffi and finally, we're motivated to have a reference implementation for algorithms that is portable to architectures. That might not be supported by highly optimized assembly.

C

Implementations.

B

So then, why do we focus on rust? Why don't we just like? If we cannot write secure code? Why do we want to use rust in the first place? And that's that's? Well. Obviously, everybody here has their idea of why they reuse rust and in our case it's kind of the same. So we want to use rust. um The reason that we want that we want to use rust is because we have all these types and all these uh nice nice checks um in the compiler that allow us to make our code.

B

That's that's easier to write, secure code um and we want to utilize these checks and these tools as much as possible, because writing just plain assembly is really hard and super error prone and then there's the other thing that if we only write assembly well, then you have written an assembly for an intel processor.

B

uh When you run want to run the same code on an arm processor, you you have to rewrite the whole code and we don't. We don't want to do that, because it also allows you to make more mistakes and we want our crypto code to be really secure.

B

So we would like to use a high-level language if that is at all possible, so it's not at all bad, so there is some way how rust can be in a way side, channel resistant, um and this this, like a couple of these these so so in rust, we can like make these new type style wrappers around integer, so a struct that only has some integer type and implement some operations on that that are presumably in constant time and there's two main examples in the world in the wild.

B

The first one that I'd like to mention is the setup rate from the dalai crypto team, which, if you ever need to do some kind of stuff in constant time, use this crate. This is the current state of the art that we have.

B

This is probably what you should use and we don't have anything better at the moment and the other. The other example that I'd like to mention is the secret integers great. The secret engine just creates a bit more academic of nature and what it does it looks at like what if we would replace all of the integer types with some kind of constant time, integer type would that work and and and and what the secret interest create.

B

Does it it provides side, channel resistant resistance on the language level, so, on the language level, you're you're sure that your code looks like something that should be sidechain resistant, but the secret integers create does not actually prevent these compiler optimizations that might introduce vulnerabilities.

B

The solo crate does that, and that is why I recommend that great, but both of those crates. They are only a best effort, um their only only best effort, and they don't guarantee all of the all of the uh like. They don't fix. All of the compiler optimization issues.

B

Okay, so that is the language level, and we can also look at like more at the the compiler level. What do we need to do in the compiler to actually do it right and it turns out, we need to add some kind of optimization barrier for the secret data.

B

So let me go back to the to the example. Real quick.

B

So it turns out that the problem here is that lvm seems to be able to to completely eliminate this mask variable. So this mask variable is secret because the because it it directly depends on this conditional uh value which, which we said was secret and then because, because lvm can just analyze through this mask variable, um it can do this really nice optimization of adding a branch and then just just eliminating all these bitwise operations.

B

So what we need to do here is we need to optim, add an optimization barrier to this mask variable.

B

And there is a couple of ways that we can add optimization barriers, and the first example is that we can add an optimization barrier by adding an empty assembly directive.

B

So what we do here is we we construct an assembly directive which takes this mask value as an input and always also takes this mask value as an output, and then lvm is not not able to reason about what happens inside of that assembly directive like we know that nothing happens inside assembly directive, but lvm cannot reason about that and because it can't the it will actually keep this mask value completely intact and uh it will not be able to optimize through that variable and at the other trick.

B

So so so the assembly directive um doesn't work on stable rust, because it's because for the assembly directive, you need uh to have a nightly rust version to compile. So that's not really optimal, um and so the other trick that we can use is to to do a volatile read of secret data, and what this does.

B

Is it guarantees that, at some point, this mask value would have existed on the stack and because of that, lvm is also not able to optimize through this um this, this volatile read um both tricks kind of work in 90 of the cases uh they don't. They don't not have like a hundred percent um success rate for all for all uh for our cases.

B

I won't go into why that is at this moment, um but but it's important to know that they don't always work. They are best effort tricks and the most important part is that, although these tricks might work at the moment, um they are not guarantees uh and the compiler might change in the future.

B

So perhaps in five years the compiler is actually able to look into this assembly directive and see that nothing happens and it might eliminate that assembly directive completely and we don't know we don't have any guarantee that this kind of stuff won't happen in the future. So it might be that in in a couple of years a completely secure version of some software now might actually be insecure with a new compiler version, which I find very scary.

B

So yeah we'd like to have guarantees and we don't want to have just hacks so for the next part I'll give the floor to diane, and she will be talking about how how we can use secret types in rust to actually make make our lives a little bit better.

C

So why aren't these language level protections good enough? The compiler and instructions?

C

It turns out that the general purpose instructions on various platforms take a variable number of cycles, so for us to truly have secret independent run times, we need to completely eliminate the problematic instructions. This can't be done at a language level. Only at a compiler level enter rfc number 2859.

C

This roc defines various secret, primitive types and the instructions that should be defined for each type. For all the extra types we implement all of the normal acceptable operations. When we know that a value is safe, we can use the declassify function to convert it back to a public value.

C

Using these integer types, we can build more complex types. For example, a secret key may be an array of secret u8 bytes. These types keep us secure by disallowing any rust code that would result in insecure binary code. So, for example, we don't allow indexing based on secrets. We don't allow using secret bool in an if statement. We don't allow division, which is a non-constant time algorithm.

C

We don't allow printing of secret values, and we say that every time we combine a public value with a secret value, the result is also a secret to give you an example of how this would work, here's a mock-up error message of what would happen if we broke one of these rules here the programmer chose to branch on a secret bool.

C

In this case, the compiler should give us an error because that's not allowed. Now there are two parts to this problem. There is an llvm part and a rust part which I've already described, there's been some work in the allovm realm to propose a similar rfc to this one which we've worked together on at hax 2020., we're not entirely sure what the status of that work is at the moment. But what llvm needs to do is make sure that our constant time rest code is also compiled safely.

C

So llvm needs to make sure to guarantee that what we wrote down in the code is still safe in the emitted binary. That means no branching on secret, no indexing with secret indices and no variable time instructions. At the moment. Zeroing memory is out of scope, but when we have this information about public and secret values, then we've laid the groundwork to support that as well.

C

Thank you so much for your attention. If you have any questions, feel free to ask us, while this is a recorded, talk, we're currently present and ready to answer questions.

D

All right, thank you. So much don and diane uh we're lucky enough to have you both here for a q, a all right, so you've been joined by your friend too.

C

Batman came back.

D

Entirely too ignored during the day right people looking at their screens all day, how dare they um so we do have a couple of questions from the audience which is great. uh The first one we've got is that this is all very complex.

D

How do you discover these kind of problems and how do you even begin to think of a solution very broad, but I think it would be great to hear insight on this. So.

C

There are, um there are tools that you can use um formal verification tools that can determine if um on different inputs, there are different runtimes. um So that's one of the ways that you can determine if a program has um non-secret independent runtimes um for part of it, dan.

B

So yeah, so the way we discover these kinds of issues is like um at some point. Sometimes I write a piece of assembly and the first thing I do before I write. Some piece of assembly is actually just program it in c or rust, and then see what the compiler tells me to do. And then then these are the moments that I that I stumble on these hey wait, but if I would do this, that would this would not be secure um and that's that's when I first discovered this for myself so yeah.

D

Cool, um I mean it's really cool that you like, like you said that you gave us kind of an insight on you, try and see what the compiler tells you first and that's how you can discover it yeah. I guess just be curious about what the compiler actually tells you not just like all right.

D

um Someone is asked if there's a working group working on it on a solution. I suppose.

C

um There isn't a working group um there's just the rfc, which has been a little bit stale, um because you know life gets busy. um So if anyone's interested in commenting on the rfc and trying to you know help me bring it back to life, you know that that's definitely welcome.

D

Really cool I mean, if there's interest for a working group, then yeah. Maybe someone will hop on from the audience.

C

Yeah, that would be great because you know one of the things that needs to happen is on the um on the rest side and on the all of them side we're going to have to eventually do some implementation work. You know it's not enough to just define what has to happen. We also have to implement these instructions on the secret types. So that'll actually be a lot of work.

D

Yeah um so we actually seem to have very little time left, but there was a lot of a lot of chatter in the chat room. So I guess people can find you in there and we can get a few more questions. There were lots of questions and we just didn't have enough time, but thank you so much for joining us. It was really great to to have you here and oh batman. Let me see if I can get she's asleep, she's melted into a puddle huh say.

C

Bye to your new friend, hi.

D

Awesome thanks fiona.

D

All right then see you both. Thank you for joining us thanks. So.

D