[curves] Million Dollar Curve

D. J. Bernstein djb at cr.yp.to
Wed Feb 24 17:08:11 PST 2016


> “provably” random parameters

Consider the October 2015 conviction of an insider who successfully
compromised the security of a typical modern lottery "by using his
privileged access to an MUSL facility to install a rootkit on the
computer containing Hot Lotto's random number generator":

   https://en.wikipedia.org/wiki/Hot_Lotto_fraud_scandal

He won $14.3 million. He was caught only because he didn't realize in
advance that Iowa required winners to be identified publicly---he had
foolishly bought the ticket himself and didn't manage to prepare his
accomplices adequately for a retroactive coverup:

   http://www.thedailybeast.com/articles/2015/07/07/inside-the-biggest-lottery-scam-ever.html

There are many other documented examples of people who successfully
broke lottery security and then were caught purely by luck. Presumably
there are also many people who successfully broke lottery security and
then _weren't_ caught.

How much would it cost for a serious attacker to quietly manipulate all
of the "last" lotteries used in the Million Dollar Curve? Not much, and
then the attacker has tremendous flexibility to choose the resulting
curve. Presumably the same attacker also has massive computer power, and
can therefore target a weakness in an incredibly small fraction of all
curves, far beyond a Brainpool user's worst nightmares.

For comparison, https://bada55.cr.yp.to/bada55-20150927.pdf points to a
small amount of wiggle room in the "fastest curve" approach, since the
curve generator can change the choice of curve by changing security
criteria (e.g., is 2^255-19 big enough?). The Million Dollar Curve
attempts to eliminate this wiggle room by having the curve chosen by
uncontrollable lotteries after the security criteria are specified. The
big problem is that lotteries are actually controllable, so the Million
Dollar Curve ends up giving the attacker vastly _more_ wiggle room.

---Dan


More information about the Curves mailing list