The well-deserved winner of the 2017 Underhanded Crypto Contest is JP Smith and Will Song for 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.
# ... broker = [ (lambda x: x == 2, lambda x: [0,0,1,0,0]), (lambda x: x % 4 == 3, lambda x: [0,0,0,-1,0]), (lambda x: smallestCongPrime(x) % 4 != 3, lambda x: getCurve(x)), (lambda x: True, lambda x: [0,0,0,0,-1])] def coeffs(x): for func in [lambda x: c(x) if c(x) else False for c in broker]: if func(x): return func(x) # ...
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 this 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.
For this entry, the authors have received a prize of 15 ZEC generously provided by Zcash.
From the author’s notes:
DEFEATING THE NSA FOR DUMMIES
By japesinator + incertia
As everyone knows, the NSA has general quantum computers which they use to look at our dickpics. As such, we’re all moving to post-quantum algorithms like SIDH, which are much harder for the NSA to crack! However, the NSA is known to backdoor important curves, and as such choosing just one curve to use with this algo is obviously foolhardy compared to just generating a fresh one per use.
As Broker showed, if the generalized Riemann hypothesis is true (it is, we just didn’t include a proof b/c of these damn tiny margins), this can be done in O(log(q)^3), where q is the size of the field. As that algorithm is mildly involved, we have provided a reference implementation in sage, to enable better NSA-busting for all!
Thus, we suggest the following algorithm for parameter negotiation:
- Alice picks some
p, a prime, to send to Bob
curvegen.sageand sends Alice the returned curve
Q_A, Bob chooses
Q_B, and we’re off to the races!
Because of python/sage’s late-binding, every entry in
broker will be
(lambda x: True, lambda x: [0,0,0,0,-1]). In about half of all cases, this will work fine, and the curve will be supersingular.However, about half the time, (more
or less depending on how Alice picks
p), it will not be supersingular, and while the algorithm will retain strength against classical attacks, it will be weak to any quantum ones.
We posit this is the first exclusively post-quantum backdoor and claim bragging rights.
The code is available for download.