Using the procedures from some well-known academic papers, software developers around the world implemented some complicated encryption schemes for banks and exchanges. That encryption protected billions of dollars. But the instructions the developers followed had a fatal flaw. Those billions of dollars were suddenly an easy target for criminal and nation state hackers. Fortunately for all of us, there's a guy named Jim.
Jim Miller is the cryptography team lead at Trail of Bits. Before joining Trail of Bits, Jim attended graduate programs at both Cambridge and Yale, where he studied and researched both Number Theory and Cryptography, focusing on topics such as lattice-based cryptography and zero-knowledge proofs. During his time at Trail of Bits, Jim has led several security reviews across a wide variety of cryptographic applications and has helped lead the development of multiple projects, such as ZKDocs and PrivacyRaven.
Matthew Green is a cryptographer and an associate professor at the Johns Hopkins Information Security Institute. His research includes techniques for privacy-enhanced information storage, anonymous payment systems, and bilinear map-based cryptography. He is one of the creators of the Zerocash protocol, which is used by the Zcash cryptocurrency, and a founder of an encryption startup Zeutro. He was formerly a partner in Independent Security Evaluators, a custom security evaluation and design consultancy. From 1999-2003, he served as a senior technical staff member at AT&T Laboratories/Research in Florham Park, New Jersey.
An accomplished information and physical security professional, Nick leads the Software Assurance Practice at Trail of Bits, giving customers at some of the world's most targeted companies a comprehensive understanding of their security landscape. He is the creator of the Trail of Bits podcast, and does everything from writing scripts to conducting interviews to audio engineering to Foley (e.g. biting into pickles). Prior to Trail of Bits, Nick was Director of Cyber Intelligence and Investigations at the NYPD; the CSO of a blockchain startup; and VP of Operations at an industry analysis firm.
Story Editor: Chris Julin
Associate Editor: Emily Haavik
Executive Producer: Nick Selby
Executive Producer: Dan Guido
Recorded at Rocky Hill Studios, Ghent, NY - Nick Selby, Engineer; and 22Springroad Tonstudio, Übersee, Germany - Volker Lesch, Engineer
Remote recordings were conducted at Whistler, BC, Canada; and Tarrytown, NY
Edited and Mastered by Chris Julin
Trail of Bits supports and adheres to the Tape Syncers United Fair Rates Card)
Dispatches From Technology's Future, the Trail of Bits theme, Chris Julin
True Detectives: Ian Post
Big Band Lemonade: Shirker Big Band
Duda: Ian Post
Bread and Butter: Ziggy
Scapes: Gray North
Watch this episode as a video on YouTube.
With the exception of any Copyrighted music herein, Trail of Bits Season 1 Episode 1; Zero Knowledge Proofs and ZKDocs © 2022 by Trail of Bits is licensed under Attribution-NonCommercial-NoDerivatives 4.0 International. This license allows reuse: reusers may copy and distribute the material in any medium or format in unadapted form and for noncommercial purposes only (noncommercial means not primarily intended for or directed towards commercial advantage or monetary compensation), provided that reusers give credit to Trail of Bits as the creator. No derivatives or adaptations of this work are permitted. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-nd/4.0/.
The talk at Real World Crypto 2020 that Jim discusses was "This is not a proof: Pitfalls in real-world verifiable elections" by Sarah Jamie Lewis, Olivier Pereira, and Vanessa Teague. It was based on the academic paper, “How not to Prove Yourself: Pitfalls of the Fiat-Shamir Heuristic and Applications to Helios," by David Bernhard, Olivier Pereira, and Bogdan Warinschi. It’s about some problems researchers have uncovered in an open-source e-voting system called Helios Voting.
You can learn much more about ZKDocs and the latest Trail of Bits projects on our blog: trailofbits.com/blog
Jim Miller uses a tennis analogy to help describe some of the issues we discussed in this episode: Serving up zero-knowledge proofs
Trail of Bits and Matthew Green teamed up to use Zero Knowledge proofs to form a trusted plane in which tech companies and vulnerability researchers can securely communicate, in a research project that's part of a larger DARPA-funded effort: Reinventing Vulnerability Disclosure using Zero Knowledge Proofs
In December 2020, a Trail of Bits intern wrote an extensive post called Reverie: An Optimized Zero Knowledge Proof System. Reverie is a ZK proof system using techniques from secure multiparty computation that optimizes for prover efficiency and doesn't require any trusted setup.
To learn more about the Trail of Bits Internship and Winternship programs, visit the Trail of Bits Careers Page
Chris Julin has spent years telling audio stories and helping other people tell theirs. These days he works as a story editor and producer for news outlets like APM Reports, West Virginia Public Broadcasting, and Marketplace. He has also taught and mentored hundreds of young journalists as a professor. For the Trail of Bits podcast, he serves as story and music editor, sound designer, and mixing and mastering engineer.
For the past 10 years Emily Haavik has worked as a broadcast journalist in radio, television, and digital media. She’s spent time writing, reporting, covering courts, producing investigative podcasts, and serving as an editorial manager. She now works as an audio producer for several production shops including Us & Them from West Virginia Public Broadcasting and PRX, and APM Reports. For the Trail of Bits podcast, she helps with scripting, interviews, story concepts, and audio production.
NARRATOR (NICK SELBY) Let’s say you had to protect your life’s savings - in cash - all by yourself. You’d need to figure out a lot of things, but hey: there’s this book, it’s been around as long as anyone can remember, and it tells you the 30 steps you need to take to protect it, so no one can steal it.
SFX: MONTAGE, FADE UNDER: Steel welding, power hacksaw, pneumatic ratchet
What kind of steel to buy for the vault, how to do the welding, how to put together the door, that kind of stuff, but really detailed. So you build it, and one day about ten years later, you find out that steps 14 and 24? They’re wrong. And they’re wrong in a way that makes it easy for your whole protection scheme to be foiled by any kid with, like, a playing card and a stick of gum.
Well, in December 2021, that’s what happened. But not just to one person. Using the procedures from some well-known academic papers, software developers around the world had implemented some complicated encryption schemes for banks and exchanges. That encryption protected billions of dollars. But the instructions the developers followed had fatal flaws. Those billions of dollars were suddenly an easy target for criminal and nation-state hackers.
Fortunately for us all, there’s a guy named Jim.
JIM MILLER: "Yeah, yeah."
Two years ago, Trail of Bits Lead Cryptography Analyst Jim Miller went to a conference, and he left one of the talks early.
JIM MILLER: I listened to a few minutes and it was interesting, but I ended up leaving halfway through to get some tea or to talk to one of my colleagues, something like that.
But he kept mulling over what he'd heard, and that eventually led to a series of revelations. Revelations that inspired the research this episode is about. Jim didn’t set out to be a crypto hero - he set out to get a drink.
[MUSIC UNDER: True Detectives]
In this episode, we tell the story of the bug that Jim and his colleagues found, how they found it, and how the team created and published new and freely available documentation to help cryptographers and developers avoid the same kinds of mistakes.
We’ll tell you why Jim and his team even started looking for problems in the first place. How following the trail, from academic curiosity about a bug in an e-voting system, to implementation problems in the blockchain world, led to the discovery of critical vulnerabilities across a range of systems, run by some of the best companies in the business. It’s like our own little geeky detective story.
END MUSIC
NARRATOR Before we tell you Jim's story, you need to know about something called a Zero Knowledge proof. For those of us who use the Internet – so … all of us … - Zero Knowledge proofs are changing - actually, they’ve already changed - the way things are protected online, especially in the blockchain space.
MATTHEW D GREEN: Zero knowledge proofs are a pretty old technology. They go back to the 1980s.
NARRATOR: That's Matthew Green. He's a cryptographer at Johns Hopkins, and kind of a man-about-town in the cryptography world.
MATTHEW D GREEN: Zero knowledge proofs were originally invented as kind of a privacy technology.
NARRATOR: Let's say I know a secret, like, the location of buried treasure, and you don't. But let's also say that you need to be sure that I know the secret. Maybe I promised to use some of my treasure to pay you for something, and you want to make sure I’m good for it. I’d need to prove to you that I know the secret, but of course I don't want to actually tell you the secret (because then you’d know where my treasure is, too). A zero knowledge proof is a mathematical tool that allows me to prove to you that I know a secret without actually telling you the secret. So you get proof that I know the secret, but beyond that, you have zero knowledge about me.
MATTHEW D GREEN: Let me give you an example. Let's say that I have a proof that I have some funds, but I don't want to tell you my exact bank balance, and I don't want to tell you where my, my, my funds are. So we might together write a little program that checks the blockchain, make sure the funds are greater than some amount that we both agree on and outputs, “Yes,” if that information is true. If I prove to you that I have this amount in my bank balance, you learn that fact, but you learn nothing else. There's zero additional knowledge. You don't learn where my bank balance is. You don't learn what my bank balance is. You just learn that that particular statement is true.
NARRATOR: There are lots of ways to use zero knowledge proofs.
MATTHEW D GREEN: I could log into a website without telling the website exactly who I am, and there were other advances in the area of E Cash where I could use zero knowledge proofs to prove that I possessed a coin. I could spend that coin with you, but I didn't have to tell a merchant, for example, who I was, and they wouldn't be able to track me. And this was all kind of interesting and the privacy capabilities were important.
NARRATOR: But in the early 2000s, people started to design new forms of zero knowledge proof that were more efficient. Well, everything’s more efficient except the name:
MATTHEW D GREEN: Zero knowledge, succinct, non-interactive arguments of knowledge.
NARRATOR: You’ll be pleased to know there’s a nickname for that:
MATTHEW D GREEN: ZK Snarks. You'll probably hear that term a lot. And what's special about these is they're still zero knowledge proofs in the sense that I can prove to you that a mathematical statement is true or that I ran some program and it output true. What's different is that the size of that zero knowledge proof is very, very small.
NARRATOR: And if most people on the planet have never heard of ZK proofs or ZK Snarks, part of the reason is that while everybody's aware that they’re using more encryption than ever, these days, when we hear the word “crypto…”,
MONTAGE (0:04)
ACT: News reporters saying “Crypto”
FADE UNDER
NARRATOR…it’s generally within a story talking not about cryptography per se, but about cryptocurrency.
This really irritates a lot of cryptography nerds. They think Cryptocurrencies are…You know…Cute.
MUSIC: BIG BAND LEMONADE
But as much as the purists hate to admit it, the financial success of cryptocurrency is fueling - actually funding - the most concentrated period of advancement in the field of cryptography since the dawn of humankind.
For the first time since the advent of the World Wide Web, encryption isn’t tied to the movement of money, it’s tied to the manufacture of the money itself. Even with Bitcoin’s wild price fluctuations, the biggest banks, hedge funds, and payment systems in the world depend on cryptocurrencies, and even countries have adopted them as legal tender. Cryptography is literally the coin of the digital realm.
MUSIC: FADE AND END
NARRATOR: Now, before you think we’re about to try to sell you some Dogecoin, it’s almost certain that, while they are driving current development, cryptocurrencies, blockchain technologies, and the like, are not the pinnacle of cryptographic utility. They are, though, the most practical, generally useful application of cryptography we’ve ever seen. Which is ironic: The security community has long tried to protect privacy through encryption, but it’s been so frustratingly difficult to implement that it has remained the realm of geeks, spies, and the tin-foil hat brigade. But applying cryptography to something we all understand - money? That opened the flood-gates. We can expect even more democratic use of cryptography in the future.
But cryptocurrency is exactly why ZK Proofs and ZK Snarks and a whole range of other things are getting so much attention these days. They make blockchains run faster.
MATTHEW D. GREEN: For example, the Ethereum system is a bunch of volunteers who are executing these programs called smart contracts.
NARRATOR: Here's Matt Green again.
MATTHEW D. GREEN: And all of these people are untrustworthy, and they're all kind of assumed to be trying to steal money from you and, you know, tamper with the execution of your smart contract.
The way systems like Ethereum deal with this today is they actually require everybody in the network to run the smart contract program a second time to make sure that what happened in the smart contract is correct. Thousands and thousands of people run that program a second time to double check the work, make sure that there was no cheating. And this works OK, but you can see the problem is it requires you to do, you know, a thousand times as much work. And this is why systems like Ethereum are so slow they can only handle a few dozen transactions globally per second. So the big dream is that rather than having that whole program be run a second time, we can actually send out one of these succinct zero knowledge proofs to the whole world. And then all we have to do is check that little tiny zero knowledge proof, and we know that the transactions were all run correctly and all of the results are correct.
NARRATOR: OK. So, Zero Knowledge Proofs let people prove something by giving away a very limited piece of information; ZK Snarks make that process more efficient. Great. But the real challenge that remains? Crypto - and by that I mean cryptology - Crypto is, like, really hard to get right. And the more demand there is for easier, faster, but stronger ways to use encryption, the more people and companies use it, and the fewer people understand what’s going on behind the curtain.
It’s a perfect storm: Zero Knowledge proofs are complicated, more people are using them, and a lot of the developers who do use them don’t understand how they work - they just, kinda, shove them into their applications and … hope it all works. So, when it comes to modern encryption anyway, it turns out that hope actually is a strategy.
It’s just not a very good one.
SFX: CONFERENCE AMBIANCE
NARRATOR: It’s January, 2020, before the pandemic shutdowns. Trail of Bits cryptographer Jim Miller
JIM MILLER: "Yeah, yeah."
is at the Real World Crypto Conference in New York City.
One of the talks that he’s wanting to see is called “This is not a Proof: Pitfalls in real-world verifiable elections." It’s about some problems researchers have uncovered in an open-source e-voting system called Helios Voting. We’ve linked to the talk and the paper it was based on in the show notes.
Jim wasn't particularly interested in e-voting, but he wanted to hear about a bug that researchers had discovered in the system. The bug undermined Zero Knowledge proofs. It allowed attackers to trick someone into believing that a statement was true when it wasn’t. Remember what he said at the beginning of the episode…he left the talk early.
JIM MILLER: I listened to a few minutes and it was interesting, but I ended up leaving halfway through to get some tea or to talk to one of my colleagues, something like that.
NARRATOR: As I said, Jim wasn't super interested in e-voting. But something from the talk stuck with him. He kept rolling it around in his head after he left.
JIM MILLER: There was this really cool issue found related to the insecure use of what's known as the Fiat Shamir Transform.
NARRATOR: Oh, dear.
To make the rest of this a little less gobbledygooky, we need two more concepts: the Schorr Protocol, and Fiat Shamir transform.
This won’t hurt a bit.
So…there are lots of ways to do Zero Knowledge Proofs. One of the most common was cooked up by a German cryptographer named Claus Schnorr.
A Schnorr proof is interactive — a two-way street:
JIM MILLER: You have to generate something random, send it to a verifier or have them send you something back and then you generate the final proof.
NARRATOR: Jim says it works… but it takes three steps. You need someone to respond to you.
JIM MILLER: And specifically in the blockchain world, that's kind of a non-starter.
Those three interactive steps slow things down. And when you’re dealing with things like money, slow is bad.
That's the Schnorr Proof. It's an effective way to perform a Zero Knowledge proof, but it's a bit slow because it's a two-way interaction.
Enter Amos Fiat and Adi Shamir. They're cryptographers. And back in the 80s, they figured out a way to speed up an interactive protocol like Schnorr.
Fiat and Shamir developed a technique that turns the proof into a one-step process. Instead of sending a message, receiving a challenge, processing it, and then computing and sending the final proof back, you do it all at once. Now you send a single message and the receiver can confirm the proof. Boom. One step. No more back and forth.
Cryptographers call this the Fiat-Shamir Transform.
JIM MILLER: so it turns out that this transformation is fairly generic and you can apply to really any proof system that follows this same structure that the Schnorr protocol has. So in practice you can really apply this to pretty much all proof systems to make them non-interactive.
NARRATOR: So you’ll see it in Schnorr, in bullet proofs, in some ZK snarks …
JIM: You go all the way down on some level, you probably see this Fiat Shamir transform being used. Does that cover it, or should I go into more?
NARRATOR: Nope, that’s enough!
The talk Jim’s going to walk out of is based in part on an academic paper called, “This is not a proof: Pitfalls in real-world verifiable elections” (again, we link to it in the show notes), which says that researchers looking at that e-voting system have recognized that there are two ways to do a Fiat-Shamir transformation, and one of them is weak.
OK, so back to the conference: Jim was still thinking about that talk, so he wrote something:
JIM MILLER: I wrote this blog post, but I just kind of quickly wrote it in an afternoon and threw it onto the Trail of Bits internal blog posts, which is where we can just kind of talk about something that's on our mind.
NARRATOR: Trail of Bits internal blog posts are dispatches from our engineers and consultants about things they find interesting; they’re not for public distribution.
JIM MILLER: : And it wasn't until probably like a year after I made that initial internal blog post one of our editors came to me and was like, Hey, this looks like a cool post. Can we spend some time and clean it up and make it ready for public use? And as I was going through it, I kind of didn't like where the end of the post was, which is where it started to talk about these, these Fiat-Shamir issues.
NARRATOR: So Jim started reworking that blog post for public consumption. And as he dug in, it started becoming clearer that this vulnerability affected a lot more than e-voting. And then, to drive that point home, a customer came to Trail of Bits with a problem. Someone had attacked their Zero Knowledge-based security system and gotten away with a small amount of money. The company couldn’t figure out how it happened.
Jim’s team started reviewing the code, and all of a sudden, it started looking familiar. This bug - the one that subverted the voting system? These people had it, too.
JIM MILLER: Wow ok this is actually a real thing, this isn’t some kind of uncommon theoretical issue that popped up once in an election scheme, like this actually happens in other places, too.
NICK: To confirm his findings, Jim joined up with another scientist.
JIM MILLER: Dr Sarang Noether, who had worked previously with Monero on some of their stuff.
NARRATOR: The two of them, and their respective teams, found that lots and lots of places were using code that made them susceptible to being hacked. As part of the investigation, Jim double-checked the code, and the academic paper on which the code was based. And he noticed something was weird about what the developers had done:
JIM MILLER: They implemented step by step exactly what the paper said. And you know, we looked at the paper and I saw there the recommendation for the Fiat Shamir transform and that did exactly what the paper recommended.
NARRATOR: The vulnerability was there … in the code in the academic paper. And developers around the world had inserted that code into security protocols in all kinds of Zero Knowledge proof systems. This wasn’t carelessness. This wasn’t sloppy work. The engineers and developers had followed the instructions, step by step, from peer-reviewed academic papers. But the papers were wrong.
JIM MILLER: I was like, how is that even possible? All these papers are peer-reviewed. How could there possibly be such a glaring issue in this paper that no one really mentioned or no one caught before here? And that's when it really hit me, that wow, like not only is this a real thing, but this is affecting a lot of different proof systems, and the scale of this is going to be pretty big because not only do security people generally not know about this, it even seems like a lot of cryptographers aren't aren't very knowledgeable on this issue, either.
NARRATOR: The papers everyone was cribbing from were spectacularly opaque, and a little hand-wavy:
JIM MILLER: - You go to step four and it says, Oh yeah, for this step. Read this paper from the eighties that kind of does something similar and then continue to step five. Of course, everyone's going to mess that up. It's not the right way to to produce this guidance.
And because the paper it pointed to are both hard to follow and also wrong, and because every project followed the papers, the problem is everywhere.
JIM MILLER: This is a legitimately widespread issue. Wow, this is this is terrifying.
NARRATOR: Matt Green, the Johns Hopkins cryptographer, says this thing with the papers happens a lot - he himself made a program that depended on an academic research paper, that itself depended on another academic research paper that was flawed. This is, actually, how most of cryptography works: it’s collaborative, community-based, and a lot of trial and error.
Meaning, as Jim Miller says, this is all part of the process:
JIM MILLER: I don't want to make it seem like all of the fault lies on the shoulders of these kind of theoretical cryptographers, right? With all cryptography, the most important part is collaboration, having as many people staring at something as possible.
NARRATOR: There is some good news in this. While the problem is widespread, it’s easy to fix:
JIM MILLER: it's a one to two line fix. Just make the adjustment, include all the information and transform, and you're good to go.
NARRATOR: The Trail of Bits team looked at the issue and concluded a couple of things.
First, developers were trying to find the documentation of how to do these proofs correctly, but there just wasn’t enough of it, and some of what’s out there is wrong.
And second, since this wasn’t a case of developer-laziness. If we made the documentation, people would use it. Jim’s team realized that our job wasn’t to fix what was out there, it was stopping it from happening in the first place.
JIM MILLER: - It's just a lack of information. It's a lack of knowledge around this specific issue and other kinds of implementation considerations that again, aren't always covered in these academic papers.
NARRATOR: The team envisioned a collaborative, open-source project, shared under creative Commons licensing. Anyone could use it free of charge. The project would provide the documentation that Jim and the Trail of Bits team feel is missing - not to replace academic papers, but to provide an instruction manual on how to implement in practice what the papers describe in theory:
JIM MILLER: The idea is we want to produce this guidance that goes into the nitty gritty details that are essentially out of scope for academic papers. So we talk about similar issues. We talk about how to generate certain random values. We talk about all these other things that again won't be covered in the academic papers for a variety of reasons.
NARRATOR: Over the course of three months, Jim, along with Trail of Bits cryptographers and engineers, created and quality-controlled the guide. They called it ZKDOCS. It’s available now at zkdocs dot com. ZKDocs provides comprehensive, detailed, and interactive documentation on zero-knowledge proof systems and related primitives.
JIM MILLER: - it's my hope that through the ZKDocs, we get a collaborative effort across a variety of zero knowledge proof schemes and also just non-standard cryptographic protocols generally.
NARRATOR: It was posted in late December. Since then, hundreds of cryptographers and thousands of developers have read through ZKDocs and used the interactive calculators. And they've started collaborating. The community has begun making contributions to the project. To us, that’s a home run.
JIM MILLER: - And it's my hope that no developer will ever have to develop something by just looking at the original academic paper.
MUSIC UNDER: SCAPES BY GRAY NORTH:
You can learn much more about Zero Knowledge Proofs on the Trail of Bits blog, at blog dot trailofbits dot com. There are links in the show notes on these articles and more:
In, “Serving up zero-knowledge proofs,” Jim Miller uses a tennis analogy to describe some of the issues we discussed in this episode.
Trail of Bits and Matthew Green team up to use Zero Knowledge proofs to form a trusted plane in which tech companies and vulnerability researchers can securely communicate, in Reinventing Vulnerability Disclosure using Zero Knowledge Proofs, a research project that's part of a larger DARPA-funded effort.
In December 2020, a Trail of Bits intern wrote an extensive post called, "Reverie: An Optimized Zero knowledge Proof System". Reverie is a ZK proof system using techniques from secure multiparty computation that optimizes for prover efficiency and doesn't require any trusted setup.
And by the way, another Season 1 episode dives deep into our Internship and Winternship Programs - learn more about these incredible opportunities to make a difference, at trailofbits dot com slash careers.
Season One of Trail of Bits is available for download now, wherever you get your podcasts.
The people who worked on this episode are Chris Julin, Emily Haavik, Joe Dobkin, Trail of Bits CEO Dan Guido, Jim Miller, Matthew Green, and hi, I’m Nick Selby, I’m the Director of the Software Assurance Practice here at Trail of Bits.
Chris Julin made our theme music.
Trail of Bits helps secure some of the world's most targeted organizations and devices. We combine high-end security research with a real-world attacker mentality to reduce risk and fortify code. We believe the most meaningful security gains hide at the intersection of human intellect and computational power. Learn more at trailofbits dot com. On Twitter, we’re AT trailofbits; Dan Guido’s Twitter is AT guido and I’m AT fuzztech.