The 2018 Contest Winners

T

First, an apology: we’re super late posting the 2018 entries, and we’re sorry. We know some of you have been waiting to see them for a long time. We have more to say about the future of the contest, but first, let’s see the winners!

Winner: Matt Cheung – Incomplete Elliptic-Curve Parameter Validation

The winning entry comes from Matt Cheung. You can find the full submission here.

Matt’s entry is a tool for checking an elliptic curve’s parameters to ensure that it is safe for cryptographic use. The code is missing an important check, which isn’t easy to spot, because unless you’re well-versed in elliptic-curve cryptography, you’re unlikely to even know about the kind of check that’s not there! The backdoor is exploitable by constructing curves that pass the security test, yet are still vulnerable to the Smart attack.

Matt earned a prize of $1500 worth of Zcash, provided by The Zcash Foundation.

Zcash Foundation

 

Second Place: Ella Rose – Backdoored Key Agreement

Ella Rose‘s entry comes in second place. It’s a backdoored key agreement protocol. To agree on a shared secret, Alice and Bob use the following protocol (e and n are public parameters known to both Alice and Bob, and ms256b is a function that returns the most significant 256 bits of its input):

Alice

  1. Generate a random 256-bit private key x and a random r.
  2. Alice’s public key is A=(ex + r) mod n.
  3. Given Bob’s public key B, Alice computes S=ms256b(xB mod n)

Bob

  1. Generate a random 256-bit private key y and a random z.
  2. Bob’s public key is B=(ey + z) mod n.
  3. Given Alice’s public key A, Bob computes S*=ms256b(yA mod n).

This works, i.e. Alice and Bob arrive at the same shared secret, because S = ms256b(xB mod n) = ms256b(x(ey + z) mod n) = ms256b((exy + xz) mod n) = ms256b((exy + yr) mod n) = ms256b(y(ex + r) mod n) = ms256b(yA mod n) = S*. The underlined “=” is true because the sizes of x, z, y, and r are carefully tuned so that ms256b chops off the difference the xz and yr terms create.

The equations defining Alice’s and Bob’s public keys, (ex + r) and (ey + z), are what’s called noisy modular multiplication. One might expect the process to protect the secret keys, since without knowing r or z you can’t multiply by e’s inverse to recover x or y.

However, the parameters e and n can be chosen to make the protocol insecure in a non-obvious way! If we were to choose e so that it has a multiplicative inverse d where x < d and x + dr < n, then computing dA = d(ex + r) mod n gives (dex + dr) mod n = (x + dr) mod n = x + dr. Then, we can compute (x + dr) mod d = x, which is Alice’s private key.

That’s too easy, though! The real cleverness of Ella’s entry is to notice that if we instead choose e and another number k and do a similar thing to Alice’s public key mod nk instead of mod n, the attack still works. To carry out the attack you need to compute the inverse of e mod nk, and it turns out that if you don’t know k then that’s as hard as breaking RSA. So, you can use this approach to craft a key agreement protocol that only you can break (barring other vulnerabilities in the protocol).

You can find Ella’s full entry, including more detail on the nk variant of the backdoor, here.

Ella earned a prize of $750 from NCC Group Cryptography Services.

NCC Group Cryptography Services

 

Third Place: James Bofh – Obscure Off-By-One Breaks Encryption

The final entry comes from James Bofh. It’s a bash script that encrypts files. For each file, it generates a random password and encrypts the file using OpenSSL. But, due to a “bug”, the password isn’t properly passed to OpenSSL and anyone will be able to decrypt the files. Take a look at the script and see if you can spot the problem.

We originally announced the winners at Crypto & Privacy Village at DEF CON 26. Here are the slides from that presentation.

Hiatus

As we mentioned at the start, we were very late posting these entries.

Running the contest is a substantial time investment, and it’s a process that continues for long stretches of time as we go through the stages of setting up the prizes, promoting the contest, selecting judges, collecting and reading entries, and so on. There’s always a next thing to do, so stress accumulates, and things get put off.

Rather than run the contest poorly, we’ve agreed to put the Underhanded Crypto Contest on hiatus until we find more time to dedicate to it or we find a more effective way to promote underhanded attack research.

Conclusion

Before we sign off for now, a special thanks is in order to JP Aumasson, who has been volunteering as a judge for the contest since the beginning and selected the winning entries above. Thanks so much, JP!

All of the raw contest entries, dating back to 2014, can be found in the entries archive. Our attempts at accessible explanations of past years’ winning entries can be found spread across several posts on this website.

Stay tuned to our Twitter, @UnderCrypto, for any future announcements.

Recent Posts

Categories