Crypto & Privacy Village Contest Winners!

The Crypto & Privacy Village mini-contest is over. Despite the tight deadline, we received five high-quality submissions in two categories. The categories were, in brief:

Backdoor GnuPG. Patch GnuPG to leak the private key.

Backdoored Password Authentication: Design (and optionally implement) some kind of password authentication where a secret value known to the attacker can be used in place of the correct password.

For complete details, see the rules page.

We had three submissions to the GnuPG category. The winner is Joseph Birr-Pixton. The submission takes advantage of how GnuPG 1.4 generates DSA nonces.

The randomness of the DSA nonce is crucial. If the nonce is not chosen randomly, or has low entropy, then it is possible to recover the private key from digital signatures. GnuPG 1.4 generates nonces by first generating a random integer, setting the most-significant bit, and then checking if the value is less than a number Q (a requirement of DSA). If it is not, then the most-significant 32-bits are randomly generated again, leaving the rest the same.

This shortcut enables the backdoor. The patch looks like an improvement to GnuPG, to make it zero the nonce after it is no longer needed. Unfortunately for GnuPG, but fortunately for this contest, there’s an extra call to memset() that zeroes the nonce in the “greater than Q” case, meaning the nonce that actually gets used will only have 32 bits of entropy. The attacker can fire up some EC2 instances to brute force it, and recover the private key.

There were two entries to the password authentication category. The winner is Scott Arciszewski. This submission pretends to be a solution to a user enumeration side channel in a web login form. The problem is that if the username doesn’t exist, the login will fail fast. If the username does exist, but the password is wrong, the password check will take a long time, and the login will fail slow. This way, an attacker can check if a username exists by measuring the response time.

The fix is to, in the username-does-not-exist case, check the password against the hash of a random garbage value. The garbage value is generated using rand(), a random number generator that is not cryptograhically secure.  Some rand() output is also exposed to the attacker through cache-busting URLs and CSRF tokens. With that output, the attacker can recover the internal rand() state, predict the garbage value, and use it in place of the password.

An archive with all of the entries can be downloaded here: UHCCryptoVillageV2.tar (80KiB, last updated: August 9, 2015).

The judging was done by Jean-Philippe Aumasson, to which we extend our sincerest thanks.