We are proud to announce the winners of the 2017 Underhanded Crypto Contest!
Hi everyone, I’m Adam Caudill, and I’m here to announce the winners of the 2017 Underhanded Crypto Contest.
If you don’t know about the contest, we’ve been doing this since 2014 – the contest was originally inspired by the Underhanded C contest, but aims to do more. The underhanded C contest sets to out find ways that you can hide evil in C code – though this is often with obfuscation, while there are clever ways to hide things (especially in C), it doesn’t really push the state of the art forward. In most cases, obfuscated C is fairly obvious – meaning it’s unlikely that it would ever make it into a real system.
Our goal from the beginning was to learn more about how cryptosystems can be subverted, and primarily how this could be done in real-world systems. So, the Underhanded Crypto Contest isn’t just about writing code that is so obfuscated that you can’t tell what it’s doing, but finding new ways to add backdoors through subtle “errors” in code, sabotaged designs, and various other techniques.
The Underhanded Crypto Contest is run by a small core team, Taylor Hornby and myself, with the assistance of the judges, sponsors, and others to make this contest a success year after year – and produce new results that can be used to better understand how cryptosystems can be subverted, helping those that perform code & design reviews, and hopefully helping to produce designs that are more resilient to attack.
All of those that work on this project do so on a volunteer basis, while there are sponsors, they provide the prizes directly to the winners – this project exists purely to gain research information.
We’d like to thank the entire Crypto & Privacy Village team for once again hosting us, and all the help they provide – not only to us, but the entire community. They volunteer their time – and a substantial amount of it – to provide the community with this excellent opportunity to share knowledge and research. They have pushed hard to make this village a success, and deserve everyone’s gratitude for all they’ve done.
Before we talk about this year, allow me to spend a minute talking about the lessons learned from years past.
- Last year, we had a very focused contest, targeted to cryptocurrencies – the winner was a brilliant submission, but it was also the only submission. Despite a lot of interest, lots of discussion, and many ideas being thrown around, only one person was able to come up with a complete submission. Open contests, with minimal focus do far better. This is something that we won’t forget, and future contests will continue to use an open model.
- Over the years, we’ve steadily tightened the rules – with plagiarism being the most problematic thing we’ve seen. We obviously don’t have a problem with building on ideas of others – that’s how research moves forward, but we’ve had cases where submissions were simply copied from material others made available. While it’s unfortunately common in the security community that prior research is rarely cited, blatantly copying the code or analysis of another isn’t acceptable.
- Another thing that has changed over the years, is that we not only require detailed explanations, to simplify judging – scoring a 50-page PDF with no explanation of the issue is quite time consuming – but we also request that each submission include the text of a blog post that we can publish. Over the next few weeks, we’ll release all of the entries, with a description of what they’ve done. This makes it much easier to understand, and find interesting submissions. This is one of the biggest mistakes we made in the early contests – it was too hard for people to find and understand interesting entries.
- If you follow any of the big names in the crypto community on Twitter, you’ve likely seen some mention of the contest – though getting the word out to the larger community has been quite a challenge. The value of the first place prize this year certainly helped get the word out, but we need to do more to spread the word.
This year our first place prize was 15 ZEC provided by Zcash, and at the moment is valued at more than $2,600, the second place prize of $500 is provided by NCC Group – we owe a big thanks to both of these companies for providing the prizes. Zcash is a new sponsor this year, and provided a fantastic prize. NCC Group has been with us from the beginning, sponsoring all of the contests and providing help in promoting the competition.
A special thanks to our judge JP, who has been part of the judging team for every one of the Underhanded Crypto Contests – this year to make things simpler and save time, JP was the sole judge of the contest.
Without further ado, let’s get to the important part of this announcement.
The winner of the 2017 Underhanded Crypto Contest is JP Smith and Will Song; with “Neville Longbottom” taking second place.
The winning entry is a curve generator for a SIDH, a post-quantum key exchange. This curve generator appears on the surface to function properly, but in reality in certain circumstances the curve generated isn’t supersingular – this doesn’t pose a threat if the attacker is using classical computers, but breaks in dramatic fashion if the attacker has a quantum computer available. The generator is written in Python, and takes advantage of a quirk in its behavior to override a value, resulting in invalid curves.
This is a very clever entry, and one that is potentially quite special – as it may be the first quantum backdoor.
Here’s part of the code.
To get a supersingular curve, different cases have to be handled differently. The code defines those cases with an array of lambdas. Each element is a pair, and the first element is a function to check if the case applies. The second element defines what to do in that case (used by code later on).
Below is some code which loops over the
broker array to figure out which case applies and then gets the correct second element.
What’s happening here is a new array of lambdas is being created using python’s “for” syntax for defining an array.
You’d expect the current value of “c” to get saved in each lambda that gets generated, but because of python’s late binding, what actually happens is all of the lambas get the LAST value of c.
So all of the cases are handled like the last one, which leads to non-supersingular curves being output.
This might help understand what’s going on (ctrl+f search for “late binding closures”): https://python-guide-pt-br.readthedocs.io/en/latest/writing/gotchas/
We can check that this works by printing out the elements in the array it generates to loop over.
A researcher going by the pseudonym Neville Longbottom submitted a very clever C application that, by all appearances is secure, though taking advantage of compiler behavior and memory layouts, overwrites the key for longer messages, resulting in them being encrypted with a null key.
It’s written in C, there’s a function for reading the file being encrypted into memory (readString), and a function for doing the encryption (encrypt). It’s set up so that after readString() is called, encrypt() uses the same stack memory.
There’s a line of code that tries to zero out a buffer encrypt() uses, but it’s broken: it keeps zeroing out until it sees a null byte, potentially past the end of the array.
The buffer is uninitialized when this happens, so it’ll contain some of what was in file_read_buffer.
If the message is small, then there will be some leftover zeroes from file_read_buffer on the stack, and those will protect the key.
…but once the message reaches a certain size, those protective null bytes won’t be there anymore, and the key gets zeroed.
This is a very clever method, because it uses known good test vectors, which pass as expected. From an initial inspection there’s no sign of an issue, it works, and works properly. This is the kind of thing that you could see on Github and people would use, with no idea that it doesn’t actually protect their data.
Our second place winner was generous enough to ask that the prize be donated, so $500 will be donated to the EFF in his name.
We’d like to thank everyone else that took part in the contest, and devoted time to making this event successful – and contribute to ongoing research.
We are starting the planning for the 2018 Underhanded Crypto Contest now, and while we aren’t ready to say too much, there are some exciting things in the works and some decisions that have been made – the main contest will continue to be an open contest as it was this year, we are working on getting larger prizes, there’s an academic paper in the works, and we are planning some exciting focused challenges for this time next year. We’ll start releasing details for the main contest around January – giving plenty of time to plan and prepare.
We’ll be making more announcements about other changes that are in the works as time goes on. While we can’t share details yet, next year should be exciting.
And with that, we’d like to again thank the companies that provided the prizes, our judge, JP, all of those that entered the contest, the Crypto Village team for hosting us, and all of you for your attention.
The 2017 Sponsors: