Okay, thank you for joining.
Let's start our next Dev Random Talk by Edinette Nolso and the Flores.
Good, yours.
Thank you.
Yeah, welcome everybody.
Today I want to give you an idea of what modern cryptographic software has to do to avoid compilers breaking our code.
My name is Benayas.
It just said, I'm working for a company that allows me to be a co-maintainer on the Botanical Library, which is a C++ library with the advantage of being endorsed by the German BSI.
So it is used in software that is used to encrypt like NATO restricted data for instance.
And since we're talking about like we trust the math, let's just have a very quick look into the math.
And there are different problems that cryptographic algorithms use nowadays to do modern cryptography.
There's the prime factorization problem, which a lot of people probably know with the RSA algorithm.
The idea is that we believe you can't factor large composite numbers into prime factors.
Other problems that are being used for asymmetric cryptography is the discrete logarithm problem, which is the thing behind elliptic curve cryptography.
And both of these things have a disadvantage because they will be broken eventually once the quantum computer comes around.
So that's why nowadays we have a few new problems that we use for cryptography.
One of them is the learning with errors problem, which is a bit more from the algebraic geometrical part of mathematics, which we believe isn't breakable by quantum computers.
So the community trusts the math and all of these mathematical problems have one thing in common.
They need to deal with some secret information and need to do math and calculations in software on the secrets without losing them or like exposing them to the outside world.
So let's take a very simple example because we don't want to go into the math in 15 minutes.
Imagine you have a web server and you want to authenticate your web server just like we always did with the password.
So you type in your password to password get sent to the web server and the web server compares your password to the password it stores in the database.
It's blatantly ignoring that this is not a good idea and you use salted hashes for things like this or other things.
But for the sake of argument let's just think that it compares the passwords on the server.
So this comparison function is very simple cryptography if you want to select that.
Where we take both passwords and we compare them character by character and since we care about efficiency we return early once the first character doesn't match right.
Better not because this is what we call a site channel because we made our programs behavior dependent on secret values.
These these sort of things can be used to break cryptography and they have been used in the past and keeps coming up every now and then.
Imagine you have an attacker that has a very very high resolution clock and this guy is now doing a.
Well a brute force attack on our password let the password be for them 26 and he just tries with one character tries with a he gets a he gets an error back and he measures the time to be one millisecond.
And then he continues measuring the time for different one character passwords until the time is slightly bit longer now two milliseconds for like such a comparison is probably a bit rich.
But if you do these things a lot of times and do a little bit of statistics these things can be actually exploited.
And now he knows, okay, it's probably an F in the first character and you continue with the second character and this way the brute force attack comes becomes much more efficient.
And you can actually break the password like that very quickly by going character by character.
So this is bad. Let's come up with a better solution and better solution that cryptographers usually use is a so called constant time implementation where the algorithms runtime doesn't depend on the secret input to password anymore and the implementation here is quite simple you just don't return early, but you basically just save.
Whether there was a character that didn't fit and continue checking all the other characters to make the runtime independent of the password you still leak the length of the password, but you can't really avoid that.
Okay, so problem solved right talks over let's compile.
So the compiler, but produces some some assembly we don't want to go into the details just believe me that the first and the last bit is essentially what we programmed and the middle is the loop body there's also the matching of the individual characters and that's an early return.
But the point here is that GCC can reason very well about Boolean values it figured out that once our little flag is false it will never become true again in this loop.
So it doesn't make sense to finish the loop we return early and we have the same vulnerability again.
So what do we do the first thing that usually is done is we don't use rules but we use integers let's say 32 bit integer and we use some some bit shifts and some some bit wise operations to transform inputs into a mask where if the mask is all zeros it is false and if the mask is all one it is true.
So we can use this expand function in all the leg locations where we where we are dealing with integers and now the compiler doesn't look through it anymore right compiling.
Again the beginning and the end of the function is basically a one to one matching mapping but if you look at the loop body something interesting happens.
So there's no early return anymore that's a good start so this thing is perfectly fine but you still see that there are strange things happening so we had an equal sign and the thing doesn't unequal comparison.
And also it doesn't do all of these bit shifts and bit wise operations that we program but it basically just subtract one.
And this is fine because all my bit shifts if we know that we are putting in a Boolean value it's just basically what it collapses to.
So the compiler still reasons and optimizes the code based on the idea that what we have put in is actually a Boolean and not a 32 bit value.
So what happened is it gets in line into our code and well the compiler saw that this was true or a Boolean value from a comparison of what not.
So what we want to do is we want to use some magic of obfuscation function that basically shields from the compiler the information that the V value that comes in has a range like a certain range of values that are allowed.
So the V2 value after it went through this obfuscate function is completely oblivious to the compiler and he needs to assume that it is some integer.
But there's a bit of a catch because there we are extracting the most significant bit from some 32 bit value and if it's just one bit we're again having a Boolean.
So there is again potential for the compiler to screw us over so also here we need to add this obfuscation function.
Now you might see well this is becoming kind of like intricate and very easy to do wrong right and you wouldn't be wrong that's true.
But anyway let's compile this and we see that's now actually what we wanted right we have code that will run a bit slower but it is implementing exactly what we are told the compiler to do in the beginning.
So we basically manage to get the optimizations get rid of the optimizations and now we can be happy about it.
I promised you that I will have a quick look into this magic obfuscation function.
So essentially some inline assembly that is empty but this plus r tells the compiler hey the value we that I'm putting in here will somehow be taken by the assembly and change into some other value I will not tell you what value it will be so you will not be able to use the fact that is might have been a Boolean.
That's how these things are done nowadays.
So what we started with is a fairly neat function that is easy to understand it's also very efficient but vulnerable and we transformed it into this mess.
It's it's now secure and I'm telling you this is a very very simple example right imagine you need to do math on like 4000 bit values with with these sort of things in mind.
So how do we make this scale how do we test this at least so that we can find errors especially because new compilers that are coming out next year they might find other ways to screw us over like this right.
And surprisingly vibrant can help so so vibrant is a tool that is analyzing memory usage in C and C plus plus application other things.
And it is warning you if you are making your programs behavior dependent on an undefined value or an uninitialized memory so to speak.
And that is by coincidence it's exactly what we need. So we just tell vibrant hey our secret password is actually uninitialized memory and then we run the program so it's a dynamic check.
And then vibrant will print out something like this will want us hey in your bad equal implementation there is something fishy.
And this only will show up if there is actually one of those like conditional branches that we don't want.
And vibrant is even so smart that it tracks this secret notion of values across computations so if I do a computation with my secret value also the result of this computation will be considered uninitialized slash secret.
Which is really useful because you need to just basically mark the beginning of your implementation marked parts that are actually secret as secret and then run the calculations and even like secondary values that have to remain secret will be checked by vibrant like this.
And therefore you also need to like kind of like declassify the value that comes out to the okay is also considered secret because it depended on the secret password right but eventually we need to tell the user whether his password was right or wrong.
And this comparison back here is then fine but we need to tell very great hey it's okay you can you can do that now.
You can automate this process a little bit that's what we do in the CI of botan where you know you use different compilers different compiler flags but this only goes so far and the next GCC might break it you can basically can be sure.
To sum up.
Optimizing compiler have they have one goal they want to make your code fast and they're really good at it but they don't put any other qualitative requirements of your implementation into this consideration.
So there's no way to tell the compiler hey don't don't overdo it here.
There are some work being done in the LVM project in that direction but you know we're still some way to go.
It is very important therefore if you build security relevant products or systems to keep things like that in mind because it's impossible to completely rule out such vulnerabilities therefore we need other controls to make sure that such things can't be easily misused for instance.
What you could imagine is like you just have a rate limit on the password tests so that somebody who types in the password from the same IP address more than 10 times is blocked from your from your service to be able to avoid a more her to.
Well used vulnerability like this and last but not least of course you know don't roll your own crypto it is tough.
It's not just a mask that is tough also the implementations can really trip you up if you want to learn this which is quite an interesting topic of work.
Please try and get into projects that already exist where you can get your code reviewed and get.
Well get shown around by people that have done that before and in that regard thank you for your attention.
You have a question here.
So stupid question why can't you just make the timing fixed by adding slips.
Well you can the problem is like how long do you sleep.
I mean you can add jitter but you will need some sort of statistic attack there anyway so if you add jitter chances are that you can just get rid of the jitter again.
But with trying a hundred times and like statistically getting the jitter that you introduce out of out with statistical tools and also you don't want to slow down your program unnecessarily basically.
Another question here.
Since what you're describing is the lifelong arms race between compilers getting faster fortunately.
Is there some merit to just always using externally compiled libraries written directly in assembly to avoid this sort of problem.
There is and I'm sure that there is a way of dealing with these things but of course you get the problem of needing to write these things in assembly which has all its own problems and well if you have a new platform it's not it's not portable and all of these things.
And there is also other side channels that like can produce problems so that is just one of the possible things that can you screw over there.
Could you just break out the function implementations into a separate CPP file and compile it as O0 is there a problem with that or use pragmas to guard that code.
I had trouble acoustically understanding I'm sorry.
So could you just break out the function implementations into a separate CPP file.
You set that to O0 and link that in or use pragmas to do that.
Yes you could do that but then you would get rid of all the optimizations that the compiler is doing for you and you would end up with very slow code which you also don't want.
So most of the optimizations like inlining loop unrolling these things you actually want.
But certain things that introduce these bugs you don't and yes the question before was asked is an eternal arms race for a long time already.
Last question, last question, there's last question.
Do you think the future is going to be compilers that accepts prompts just like an LLM to tell the compiler okay so this bug of code.
This is my intent so please don't over optimise.
There would be great please join the LLM and GCC teams and implement it.
I would like be eternal and grateful for that.
But it's complicated.
Let's thank this speaker again.
Thank you.