Smart Contract Security @ IT Camp posted June 2018

Today Software Magazine interviewed me at IT Camp about smart contract security.

Yours truly.

Ethereum Smart Contract Security @ IT Camp - Cluj Napoca posted June 2018

I'm giving a talk about smart contract security at the IT Camp conference of Cluj Napoca, Romania on Thursday. If anyone is there and wants to talk about crypto while drinking beer, contact me!

Decentralized Application Security Project posted April 2018

Last month I was in Singapore with Mason to talk about vulnerabilities in Ethereum smart contracts at Black Hat Asia. As part of the talk we released the DASP, a top 10 of the most damaging or surprising security vulnerabilities that we have observed in the wild or in private during audits we perform as part of our jobs.

The page is on github as well and we welcome contributions to the top 10 and the list of known exploits. In addition we're looking to host more projects related to the Ethereum space there, if you are looking for research projects or are looking to contribute on tools or anything that can make smart contracts development more secure, file an issue on github!

Note that I will be giving the talk again at IT Camp in Cluj-Napoca in a few months.

Fed Up Getting Shattered and Log Jammed? A New Generation of Crypto Is Coming posted April 2018

I gave a talk at Black Hat Europe last year and the recording has finally been uploaded.

I gave a summary of the talk here. You can also directly check out the specification of Disco or the libdisco library on www.discocrypto.com.

Two Student Tickets for Black Hat Asia in March 2018 posted January 2018

I'll be giving a talk at Black Hat Asia with Mason in a few months, and thus I was given two tickets for students to come attend the conference for free.

Anyone interested?

EDIT: these have been given away.

On Real World Crypto and Secure Messaging posted January 2018

Paul Rösler and Christian Mainka and Jörg Schwenk released More is Less: On the End-to-End Security of Group Chats in Signal, WhatsApp, and Threema in July 2017.

Today Paul Rösler came to Real World Crypto to talk about the results, which is a good thing. Interestingly, in the middle of the talk Wired released a worrying article untitled WhatsApp Security Flaws Could Allow Snoops to Slide Into Group Chats.
Interestingly as well, at some point during the day Matthew Green also wrote about it in Attack of the Week: Group Messaging in WhatsApp and Signal.

They make it seem really worrisome, but should we really be scared about the findings?

Traceable delivery is the first thing that came up in the presentation. What is it? It’s the check marks that appear when your recipient receives a message you sent. It's mostly a UI feature but the fact that no security is tied to it allows a server to fake them while dropping messages, making you think that your recipient has wrongly received the message. This was never a security feature to begin with, and nobody never claimed it was one.

Closeness is the fact that the WhatsApp servers can add a new participant into your private group chat without your consent (assuming you’re the admin). This could lead people to share messages to the group including to a rogue participant. The caveat is that:

• previous messages cannot be decrypted by the newcomer because a new key is generated when someone new joins the mix

• everybody is receiving a notification that somebody joined, at this point everyone can choose to willingly send messages to the group

Again, I do not see this as a security vulnerability. Maybe because I’ve understood how group chats can work (or miswork) from growing up with shady websites and applications. But I see this more as a UI/UX problem.

The paper is not bad though, and I think they’re right to point out these issues. Actually, they do something very interesting in it, they start it up with a nice security model that they use to analyse several messaging applications:

Intuitively, a secure group communication protocol should provide a level of security comparable to when a group of people communicates in an isolated room: everyone in the room hears the communication (traceable delivery), everyone knows who spoke (authenticity) and how often words have been said (no duplication), nobody outside the room can either speak into the room (no creation) or hear the communication inside (confidentiality), and the door to the room is only opened for invited persons (closeness).

Following this security model, you could rightfully think that we haven’t reached the best state in secure messaging. But the fuss about it could also wrongfully make you think that these are worrisome attacks that need to be dealt with.

The facts are here though, this paper has been blown out of proportion. Moxie (one of the creator of Signal) reacts on hackernews:

To me, this article reads as a better example of the problems with the security industry and the way security research is done today, because I think the lesson to anyone watching is clear: don't build security into your products, because that makes you a target for researchers, even if you make the right decisions, and regardless of whether their research is practically important or not.

I'd say the problem is in the reaction, not in the published analysis. But it's a sad reaction indeed.

Good night.

Updates on How to Backdoor Diffie-Hellman posted January 2018

Early in 2016, I published a whitepaper (here on eprint) on how to backdoor the Diffie-Hellman key agreement algorithm. Inside the whitepaper, I discussed three different ways to construct such a backdoor; two of these were considered nobody-but-us (NOBUS) backdoors.

A NOBUS backdoor is a backdoor accessible only to those who have the knowledge of some secret (a number, a passphrase, ...). Making a NOBUS backdoor irreversible without the knowledge of the secret.

In October 2016, Dorey et al. from Western University (Canada) published a white paper called Indiscreet Logs: Persistent Diffie-Hellman Backdoors in TLS. The research pointed out that one of my NOBUS construction was reversible, while the other NOBUS construction was more dangerous than expected.

I wrote this blogpost resuming their discoveries a long time ago, but never took the time to publish it here. In the rest of this post, I'll expect you to have an understanding of the two NOBUS backdoors introduced in my paper. You can find a summary of the ideas here as well.

Reversing the first NOBUS construction

For those who have attended my talk at Defcon, Toorcon or a meetup; I should assure you that I did not talk about the first (now-known reversible) NOBUS construction. It was left out of the story because it was not such a nice backdoor in the first place. Its security margins were weaker (at the time) compared to the second construction, and it was also harder to implement.

Baby-Step Giant-Step

The attack Dorey et al. wrote about comes from a 2005 white paper, where Coron et al. published an attack on a construction based on Diffie-Hellman. But before I can tell you about the attack, I need to refresh your memory on how the baby-step giant-step (BSGS) algorithm works.

Imagine that a generator \(g\) generates a group \(G\) in \(\mathbb{Z}_p\), and that we want to find the order of that group \(|G| = p_1\).

Now what we could do if we have a good idea of the size of that order \(p_1\), is to split that length in two right in the middle: \(p_1 = a + b \cdot 2^{\lceil \frac{l}{2} \rceil}\), where \( l \) is the bitlength of \(p_1\).

This allows us to write two different lists:

\[ \begin{cases} L = { g^i \mod{p} \mid 0 < i < 2^{\lceil \frac{l}{2} \rceil} } \\ L' = { g^{-j \cdot 2^{\lceil \frac{l}{2} \rceil} } \mod{p} \mid 0 \leq j < 2^{\lceil \frac{l}{2} \rceil} } \end{cases} \]

Now imagine that you compute these two lists, and that you then stumble upon a collision between elements from these two sets. This would entail that for some \(i\) and \(j\) you have:

\[ \begin{align} &g^i = g^{-j \cdot 2^{\lceil \frac{l}{2} \rceil}} \pmod{p}\\ \Leftrightarrow &g^{i + j \cdot 2^{\lceil \frac{l}{2} \rceil}} = 1 \pmod{p}\\ \Rightarrow &i + j \cdot 2^{\lceil \frac{l}{2} \rceil} = a + b \cdot 2^{\lceil \frac{l}{2} \rceil} = p_1 \end{align} \]

We found \(p_1\) in time quasi-linear (via sorting, searching trees, etc...) in \(\sqrt{p_1}\)!

The Construction

Now let's review our first NOBUS construction, detailed in section 4 of my paper.

Here \(p - 1 = 2 p_1 p_2 \) with \( p_1 \) our small-enough subgroup generated by \(g\) in \(\mathbb{Z}_p\), and \(p_2\) our big-enough subgroup that makes the factorization of our modulus near-impossible. The factor \(q\) is generated in the same way.

Using BSGS on our construction

At this point, we could try to reverse the construction using BSGS by creating these two lists and hopping for a collision:

\[ \begin{cases} L = { g^i \mod{p} \mid 0 < i < 2^{\lceil \frac{l}{2} \rceil} } \\ L' = { g^{-j \cdot 2^{\lceil \frac{l}{2} \rceil} } \mod{p} \mid 0 \leq j < 2^{\lceil \frac{l}{2} \rceil} } \end{cases} \]

Unfortunately, remember that \(p\) is hidden inside of \( n = p q \). We have no knowledge of that factor. Instead, we could calculate these two lists:

\[ \begin{cases} L = { g^i \mod{n} \mid 0 < i < 2^{\lceil \frac{l}{2} \rceil} } \\ L' = { g^{-j \cdot 2^{\lceil \frac{l}{2} \rceil} } \mod{n} \mid 0 \leq j < 2^{\lceil \frac{l}{2} \rceil} } \end{cases} \]

And this time, we can test for a collision between two elements of these lists "mod \(p\)" via the \(gcd\) function:

\[ gcd(n, g^i - g^{-j \cdot 2^{\lceil \frac{l}{2} \rceil}}) \]

Hopefully this will yield \(p\), one of the factor of \(n\). If you do not understand why, it works because if \(g^i\) and \(g^{-j \cdot 2^{\lceil \frac{l}{2} \rceil}}\) collide "mod \(p\)", then we have:

\[ p | g^i - g^{-j \cdot 2^{\lceil \frac{l}{2} \rceil}} \]

Since we also know that \( p | n \), it results that the \(gcd\) of the two returns our hidden \(p\)!

Unfortunately at this point, the persnickety reader will have noticed that this cannot be done in the same complexity as the original BSGS attack. Indeed, we need to compute the \(gcd\) for all pairs and this increases our complexity to \(\mathcal{O}(p_1)\), the same complexity as the attack I pointed out in my paper.

The Attack

Now here is the that trick Coron et al. found out. They could optimize calls to \(gcd\) down to \(\mathcal{O}(\sqrt{p_1})\), which would make the reversing as easy as using the backdoor. The trick is as follow:

1. Create the polynomial

\[ f(x) = (x - g) (x - g^2) \cdots (x - g^{2^{\lceil \frac{l}{2} \rceil}}) \mod{n} \]

1. For \(0 \leq j < 2^{\lceil \frac{l}{2} \rceil}\) compute the following \(gcd\) until a factor of \(n\) is found (as before)

\[ gcd(n, f(g^{-j \cdot 2^{\lceil \frac{l}{2} \rceil}})) \]

It's pretty easy to see that the \(gcd\) will still yield a factor, as before. Except that this time we only need to call it at most \(2^{\lceil \frac{l}{2} \rceil}\) times, which is \(\approx \sqrt{p_1}\) times by definition.

Improving the second NOBUS construction

The second NOBUS backdoor construction received a different treatment. If you do not know how this backdoor works I urge you to first watch my talk on the subject.

Let's ask ourselves the question: what happens if the client and the server do not negotiate an ephemeral Diffie-Hellman key exchange, and instead use RSA or Elliptic Curve Diffie-Hellman to perform the key exchange?

This could be because the client did not list a DHE (ephemeral Diffie-Hellman) cipher suite in priority, or because the server decided to pick a different kind of key agreement algorithm.

If this is the case, we would observe an exchange that we could not spy on or tamper with via our DHE backdoor.

Dorey et al. discovered that an active man-in-the-middle could change that by tampering with the original client's ClientHello message to single-out a DHE cipher suite (removing the rest of the non-DHE cipher suites) and forcing the key exchange to happen by way of the Diffie-Hellman algorithm.

This works because there are no countermeasures in TLS 1.2 (or prior) to prevent this to happen.

Final notes

My original white paper has been updated to reflect Dorey et al.'s developments while minimally changing its structure (to retain chronology of the discoveries). You can obtain it here.

Furthermore, let me mention that the new version of TLS —TLS 1.3— will fix all of these issues in two ways:

• A server now signs the entire observed transcript at some point during the handshake. This successfully prevents any tampering with the ClientHello message as the client can verify the signature and make sure that no active man-in-the-middle has tampered with the handshake.
• Diffie-Hellman groups are now specified, exactly like how curves have always been specified for the Elliptic Curve variant of Diffie-Hellman. This means that unless you are in control of both the client and the server's implementations, you cannot force one or the other to use a backdoored group (unless you can backdoor one of the specified group, which is what happened with RFC 5114).

Best crypto blog posts of 2017 posted December 2017

Hello hello,

Merry christmas and happy new year. We're done for the year and so it is time for me to write this blog post (I did the same last year by the way).

I'll copy verbatim what I wrote last year about what makes a good blog post:

• Interesting. I need to learn something out of it, whatever the topic is. If it's only about results I'm generally not interested.
• Pedagogical. Don't dump your unfiltered knowledge on me, I'm dumb. Help me with diagrams and explain it to me like I'm 5.
• Well written. I can't read boring. Bonus point if it's funny :)

Without further adue, here is the list!

• building lattice reduction (LLL) intuition from Kelby Ludwig is a must read if you want to understand how lattices and lattice reductions work. By the way, this post is the perfect example of a blogpost that fits all my criteria of a good blog post. Make sure to check Kelby's blog post of last year as well.

• Introducing Miscreant: a multi-language misuse resistant encryption library from Tony Arcieri is the perfect introduction to key wrapping and SIV modes. AES-GCM-SIV from Adam Langley is a good addition.

• How I implemented my own crypto is a trip report from Loup Vaillant about implementing his own cryptographic library.

• Why TLS 1.3 isn't in browsers yet by Nick Sullivan is a good summary of the mess that TLS 1.3 is (specifically because it needs to support so many legacy versions). For more lolz, make sure to read Matthew Green's The strange story of “Extended Random”.

• Cloudflare has a lot more good blogposts: Privacy Pass - “The Math” from Alex Davidson goes through the math of one of the most crypto-y feature ever seen from a "normal" company, SIDH in Go for quantum-resistant TLS 1.3 by Henry de Valence does the same for the SIDH post-quantum key exchange. (A good addition to this is SIDH a quantum resistant algorithm for DH exchange by Shevek).

• HTTPS on Stack Overflow: The End of a Long Road is a huge post from Nick Craver going into depth about the troubles of migrating towards HTTPS for large infrastructures. In addition, be sure to check Jan Schaumann's work on doing the same thing for yahoo: The Razor's Edge - Cutting Your TLS Baggage.

• SSL Certificate Exchange from Joshua Davies is a really useful walkthrough of a TLS certificate. If you don't know much about TLS certificates and need to know more, it's a really good read.

• Is SHA-3 slow?, Keccak: open-source cryptography and Why Keccak is not ARX . The Keccak team made an excellent job this year of talking (and debunking critics) about the new SHA-3 hash function. You can learn about the different concepts surrounding SHA-3 through these posts.

• Why Replace SHA-1 with BLAKE2? on the other hand, written by JP Aumasson, tells you to replace your SHA-1 instances with his hash function BLAKE2. JP writes a lot of very good blog post, so check this one on Should Curve25519 keys be validated? (that launched the debate on Curve25519 key validation) or the ones on his submission to NIST's PQ crypto not-a-competition thingy: Improving the SPHINCS post-quantum signature scheme, part 1.

• Cryptographic vulnerabilities in IOTA by Neha Narula and the follow up Our response to "A Cryptocurrency Without a Blockchain Has Been Built to Outperform Bitcoin" by Joi Ito (both from the Digital Currency medialab of MIT) because it shows you how hilariously bad some cryptocurrencies are (interestingly IOTA reached and lost to 4th place (in terms of market cap) in the cryptocurrency world a few months ago).

• Confidential Transactions from Basic Principles from Michael Rosenberg is a pedogagical intro to ring signatures, range proofs and other cryptographic concepts. This is useful to dig into especially if you're keen on anonimity inside of cryptocurrencies. For an exploit of these, be sure to check Exploiting Low Order Generators in One-Time Ring Signatures from Jonas Nick.

• What are zk-SNARKs?. Zcash has a series of articles about its underlying technology (anonimity inside of a cryptocurrency), it seems well written (like a lot of things on their website).

• Survey of Discrete Log Algorithms is a good intro to the discrete logarithm problem.

• Walking through an F* proof by Santiago Zanella-Beguelin seems like a good way to get yourself into F*.

That's it!

Have I missed something? Please tell me in the comments.

If you want more links like these, be sure to subscribe to my link section here on this website.

See you in 2018!