12 ms·

Million Dollar Curve

309 points by aburan28 11y ago

api 11y ago
I get the concern with NIST but I'm unsure about the concern with Curve25519. Is there any reason to suspect shenanigans there to be plausible? Also I'm not sure that future public lotteries are really that great. Technically such a thing could be rigged, though it would be hard. A truly good source would be something cosmic and public like sunspot records in the future that could be independently verified and recorded by multiple people and could not be tampered with unless God wants to backdoor our crypto.
- vessenes 11y ago
  Yes, I hate the idea of future public lotteries, published ahead of time. The entire idea is to be resistant to a nation-state attack; lotteries seem pretty far down the chain. If you're in love with lotteries, you could do something like order all lotteries in the world in a published list, and then choose them based on the last digits of bitcoin block hashes over a certain period. I'm not sure what bitrate you could get through sunspots, but I agree we shouldn't worry about subversion from that angle.
  - baby 11y ago
    It's based on lotteries from different countries all around the world. No way ONE state adversary could rig this. It's also set in the future, you need to commit to the time frame where you'll be doing that. I think their plan was to tweet it and sing it on soundcloud (among other things)
    - api 11y ago
      > No way ONE state adversary could rig this. What about multiple state adversaries? It would be hard as hell but it could be done. I'd still opt for an astronomical source. If God wants to backdoor our crypto we're SOL, but other than that it would be pretty solid. I also don't get what's wrong with nothing up my sleeve constants. Hashing the word "YOLO" is mathematically unlikely to be a rigged constant to almost "probability of falling through the floor due to random quantum fluctuations" degrees.
      - baby 11y ago
        > What about multiple state adversaries? It would be hard as hell but it could be done. Highly unlikely, there is too much money in play, too many processes to corrupt... Cryptography is usually made solid enough so that there are easier ways to break the system. http://cryptoexperts.github.io/million-dollar-curve/#lotteries http://cryptoexperts.github.io/million-dollar-curve/#lotteri... > what's wrong with nothing up my sleeve constants It's not unpredictable. There are a million constants you could choose from if you wanted to make a backdoor. I think the badass paper is about that.
  - tlrobinson 11y ago
    Why not just use Bitcoin blocks directly? A SHA-256 hash of 100 consecutive blocks should be sufficient.
    - paulajohnson 11y ago
      I wondered about that, but Bitcoin mining is increasingly dominated by a small number of big players, and they also have the hardware to do exhaustive searches on hash codes to find inputs that give the answer they want. I'm not saying its necessarily a bad idea, but its not immediately obvious that this is going to be harder to subvert than a selection of national lotteries.
- deleted 11y ago
  [deleted]
- saganus 11y ago
  Could it be something like stock market values in specific dates? If an actor can rig the stock market, the problems are different I Would think? Does the cosmic source not have an issue of who actually can make that measurement? will you not require some sort of specific tools and knowledge? or you mean using some astronomy databases created by reputable institutions?
gherkin0 11y ago
> Of course, one should not conclude that cryptographic algorithms using similar constants are systematically insecure (certainly, some designers are honest!) and we will not dispute the right to trust those algorithms. I'm reminded a controversial aspect of the design of DES. The values of the S-Boxes were unjustified, and some people feared they constituted a backdoor (much like what's alleged with Dual-EC-DRGB). It turns out that in fact they were specially chosen to strengthen DES against a cryptographic attack that the NSA was trying to keep secret. https://en.wikipedia.org/wiki/Data_Encryption_Standard#NSA.27s_involvement_in_the_design https://en.wikipedia.org/wiki/Data_Encryption_Standard#NSA.2...
- vessenes 11y ago
  The attack is "differential analysis" -- essentially, if you have a black box encoder, carefully chosen plaintexts sent through the system can leak information, and substantially weaken DES as described. Academic literature started discussing differential analysis in the early '90s if memory serves -- NSA helped harden against it in the 1970s! Current wisdom is that the NSA is not nearly so far ahead of the cryptography curve these days. But, it could just be speculation. :)
  - ikeboy 11y ago
    What about the weakdh stuff? See e.g. http://www.scottaaronson.com/blog/?p=2293 http://www.scottaaronson.com/blog/?p=2293
    - tptacek 11y ago
      That's less about advances NSA may have made ahead of industry/academia and more about the operational advantages NSA has in deploying already-plausible attacks.
- 1024core 11y ago
  My crypto prof in uni commented on this. (This is from memory). Apparently, the number of rounds (16) seemed to have been chosen arbitrarily. Many years later, when attacks on Feistel(?) ciphers (of which DES is one) became public, it turned out that these attacks only worked up to .... 15 rounds! So the speculation was that the NSA knew about the attack, and chose to set the round number just out of reach...
tomp 11y ago
I wonder how many global sources of randomness they've discarded before finding one that is both plausibly safe and exploitable.
FullyFunctional 11y ago
"Curve25519 was designed to be as fast as possible, with no security compromise. This is both a strength and a potential weakness: a strength because it gives a valid argument that no trapdoor was introduced in the design, a potential weakness because Curve25519 uses a very specific prime field. As of now, no attack exploiting this specificity is known. For applications where speed is paramount, Curve25519 is probably the best option. But for most applications, where losing a little on the efficiency side is "not a big deal", Million Dollar Curve is probably the safest choice." Sorry, no. Many more eyeballs have been on Curve25519 and DJB reputation, both of which gives me _more_ confidence in that than any new alternative. Secondly, the implementation is as important as the design. Again, Curve25519 have vetted implementations, something which takes time. Finally, the notion that speed is a liability is ludicrous. The lack of speed is a major liability. Move along, nothing to see here.
- diziet 11y ago
  Plus, Curve25519 and EdDSA have djb's stamp of approval.
  - baby 11y ago
    I think the team at cryptoexperts is way more impressive.
    - tptacek 11y ago
      What's the other curve work they've done that makes you say that? I agree with the implication that an appeal to Bernstein isn't dispositive. But Curve25519 isn't just credible because of Bernstein; it's also been scrutinized intensively by lots of other research groups.
      - baby 11y ago
        from their FAQ: > We, at CryptoExperts, actually use Curve25519 and recommend it to our partners. Yet, we think that people should not rely on the same few safe curves that are currently out. Our methodology allows to easily produce safe alternatives.
tptacek 11y ago
The thesis of this paper seems to be that there aren't many alternatives to 25519. But anybody who watched the fiasco of the IRTF trying to standardize a recommendation on 25519 knows that's not true. Browser vendors were sold on DJB's curve and asked IETF to add it to TLS; given that simple charter, people came out of the freaking woodwork with alternatives. The "randomness derived from lotteries" property seems like a gimmick. Generating plausible random seeds isn't the hard problem with generating new curves. Rather, the problem is coming up with curves that are performant on common hardware without any patent-encumbered techniques. It's also not clear to me how the $1MM curve is a meaningful alternative to 25519. Almost the entire paper is given to considering how to generate random parameters. Having accomplished that task, the paper simply generates a random Edwards curve, using their lottery generator to find a random prime, d, and base point, filtered against the SafeCurve requirements. So they end up with (in effect) a randomized version of Bernstein's curve. If 25519 somehow falls, why wouldn't this curve fall with it? Compare this paper to those of 25519: https://cr.yp.to/ecdh/curve25519-20060209.pdf https://cr.yp.to/ecdh/curve25519-20060209.pdf ... or to FourQ: https://eprint.iacr.org/2015/565.pdf https://eprint.iacr.org/2015/565.pdf Also: the swipe at Brainpool seems disingenuous. Zero is the number of people who believe that Brainpool's mathematical constants were arranged specifically to create a backdoor. The point of BADA55 is that Brainpool's use of mathematical constants as seeds isn't dispositive, and that the performance-targeting parameters of 25519 are equally credible.
- AlyssaRowan 11y ago
  Indeed. One might be biased, given one was quite... um... vocal in the whole process! I personally feel Curve25519 and Ed448-Goldilocks were very thoroughly discussed, absolutely fine, and they are the final CFRG recommendations. I am quite certain of that, and I do believe we have proved that just about as well as anyone possibly can. (I'd like to thank everyone who suffered through the whole thing. I am just a participant there, I do not speak for anyone at all except myself, and hold no special anything.) Both of the CFRG curves are rigid 'safe' curves, with (unlike the NIST curves) solid criteria given for each and every aspect of their definition, all of which were argued in the open, and fully-reproducible parameter generation algorithms are included in RFC7748 - https://datatracker.ietf.org/doc/rfc7748/ https://datatracker.ietf.org/doc/rfc7748/ CFRG made the decision to select rigid 'safe' curves pretty early on, so that everyone could see exact reasons why we picked what we did at every stage, in the open, and that therefore absolutely no shenanigans were afoot. Specifically, we ended up picking one curve over a near-Mersenne prime (2^255-19), and one curve over a trinomial golden-ratio Solinas prime (2^448-2^224-1) - because they're about the right sizes, and rigidly-structured in a way that makes them almost uniquely fast in software. (We voted on specific sizes, and had supporting reasons even for that.) Both curves are also very handily - thanks djb & Mike Hamburg! - both already present in the existing literature, and indeed quite a few examples of X25519 (DH) and Ed25519 (sig) deployment in particular already exist. During the middle of the process, some people (some of whom were hardware developers involved in the selection of the "Brainpool" curves, a similar set of random prime field curves) showed up pushing for a new set of curves with random, unstructured prime fields. CFRG didn't go that way, and we discussed that decision and the reasons why thoroughly. Mostly because the performance of curves over randomly-structured primes absolutely sucks in software (I'm paraphrasing here, but we are talking an order of magnitude difference, at least), but also because given we were even arguing about endianness for God's sake, we'd probably never have been able to agree on a sound, unbiased-in-the-face-of-future-scrutiny method for selecting random parameters in an unbiased way, let alone one that we were positive we could convince sceptical third parties about. It would appear this curve comes from the hardware developers who really wanted new random curves in any case, and have tried to do just that anyway. Good luck to them there. The only possible advantage really with a random prime field is if some big problem exists with using elliptic curves over prime fields with a sparse bit pattern that doesn't also apply to random prime fields. We argued about that for a while (you may be detecting a pattern here...!), and the conclusion was that we simply don't know of any good underlying reason that would happen that wouldn't also pose a huge threat to random prime fields, or elliptic curve-based cryptography in general (e.g. big practical quantum computers - in which case, arguing about which elliptic curve to use would be pointless and maybe we just ought to burn our worldly possessions and go live in caves. I'm paraphrasing a bit here! <g>). The only thing that popped up was that if one has old crypto hardware that one is trying to reheat and present as new crypto hardware with go-faster stripes, and one is trying to get better performance from it by abusing its pre-existing RSA multiplier to do your ECC maths as well (like, for example, a certain hardware developer, ahem, might do), the side-channel blinding technique there would not work properly, because it's only designed to work with unstructured prime fields as you usually see in RSA, rather than a field with lots of concurrent 0s or 1s in there. So, um, friendly reminder, as I said at the time: if you have an RSA multiplier, please don't abuse it to implement your elliptic curves. (Note: this would also present an issue if you did it with the NIST curves, which are also so structured.) All the software out there that I've seen that implements Curve25519 appears to be at least timing side-channel resistant (this also being a goal, and why we went with Montgomery/Edwards forms specifically to simplify this, because short Weierstrass form is a bloody nightmare by comparison). If you are tasked with designing new crypto hardware today, I do feel you'd be better placed doing what a friend of mine suggested: instead of bolting new bits on decades-old designs like most people seem to, actually go and design new open hardware (RISC-V?) and try to restore some verifiability in that. Put all the crypto in open-source, verifiable software which the user loads and verifies (a friend's prototype design just uploads the whole executable EEPROM to the host for comparison with a known-good image whenever you connect it, and zeroises the data EEPROM in hardware whenever the executable EEPROM is written by the host) - and then ship the hardware absolutely blank. Then you hopefully have one less problem, as you don't really have dedicated crypto hardware as much as a solid general-purpose microcontroller with side-channel protection. (I wonder what impact that might have on export controls, if any?) In any case, you probably also have enough problems to worry about in your supply chain already without risking becoming the next Gemalto... or, God forbid should things not go well, Apple. Just a thought there. I know several people are working on open hardware now; I've heard of a couple of dedicated hardware implementations of 25519 floating around, too. I don't know of anyone who actually wants to use this so-called "million dollar curve". CFRG aren't recommending it. I'm certainly not. Not because it's bad. Just because - sorry, but as I said at the time - it's kind of... pointless? If you're using the Brainpool curves already, there's not really any reason you couldn't use this... but unless: a) you believe the Brainpool curves are deeply flawed somehow, enough to avoid, but these somehow aren't; and, b) you believe there's a huge breakthrough in number theory that affects structured primes but not unstructured primes or elliptic curves in general; and also, c) you believe nobody's going to show up with a quantum computer in the time period you're worried about... I just don't - personally! - see why you would bother switching. Clearly these people do. I suppose we simply disagree there, which wouldn't be the first time.
cperciva 11y ago
Sigh The issue here is that we need a trusted source of "nothing up my sleeve" numbers: https://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number https://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number This is why the RFC 3526 groups use primes derived from Pi: https://tools.ietf.org/html/rfc3526 https://tools.ietf.org/html/rfc3526 I'm sure that it would be difficult to tamper with the results of lotteries held all over the world. But it's even harder to tamper with the value of Pi.
- baby 11y ago
  Problem, pi is not unpredictable.
  - cperciva 11y ago
    It doesn't need to be. The group you're using is part of the cryptosystem, not part of the key.
    - baby 11y ago
      And the cryptosystem might be backdoored by the way you choose the constants. (they are way too many constants to choose from)
      - tptacek 11y ago
        It really isn't backdoored, though. Bada55 made a legit point that curves shouldn't be required to derive from simple math constants, but it does less of a good job showing that math constants are themselves necessarily untrustworthy. You'd need an awfully funky looking set of constants to get the degree of freedom bada55 proposes.
      - cperciva 11y ago
        Right. Hence "nothing up my sleeve" numbers. It's hard to fit a backdoor into Pi.
        11y ago
matt_wulfeck 11y ago
From a practical point having sources of randomness/entropy isn't very useful. A CSPRNG will do a great job generating random numbers. It will create secure Tls connections and a ssh_key that's never been seen before. However it's Achilles heel is that it MUST be seeded with random numbers. That's hard to do in a predictable state, such as a headless vm. If the seeds no good it can't establish a secure Tls connection to fetch random data (ala Ubuntu pollinate service). The next thing to push crypto security forward is easy, efficient, and trustworthy ways to generate this seed.
- tptacek 11y ago
  Yeah, you're missing the point a little. If you want to generate and standardize a random curve (like, in this paper, the "random" version of Curve25519, which doesn't rely on specific magic parameters carefully chosen for speed), you have a big problem: even though your CSPRNG might be perfectly fine, nobody is going to believe that you actually used it, because you can't prove that you did. Hence: lotteries.
PaulHoule 11y ago
see https://en.wikipedia.org/wiki/Numbers_game https://en.wikipedia.org/wiki/Numbers_game
deleted 11y ago
[deleted]
jdlyga 11y ago
I'm donating 35 dollars to Million Dollar Curve. Who wants to match me?
jdlyga 11y ago
I'm donating 35 dollars to Million Dollar Curve. Who wants to match me?
yandrypozo 11y ago
more garbage over the garbage !!
tonyhb 11y ago
Elliptic curves are going to be rendered redundant with the introduction of quantum computing via shor's algorithm. 25519 is already trusted and fast, and in all likelihood will probably last until we need to shift from this type of cryptography. Seems as though this is pretty futile and doesn't need to exist.
cyphar 11y ago
One thing that is ignored is that you can't be sure that a lottery isn't rigged. We've seen cases (Serbia) where lotteries were rigged, so it's very possible that someone with enough money could rig your entropy source.
- daodedickinson 11y ago
  It's relatively rare that lotteries AREN'T rigged. It's a bunch of money sitting RIGHT THERE to the people implementing the lottery. And like any other situation where human beings have a GIGANTIC incentive to commit fraud, they often do: https://thehornnews.com/authorities-lottery-may-be-rigged/ https://thehornnews.com/authorities-lottery-may-be-rigged/ http://www.nydailynews.com/news/national/lottery-employees-rigged-14-3-win-officials-article-1.2185601 http://www.nydailynews.com/news/national/lottery-employees-r... "State lotteries in Colorado, Wisconsin, and Oklahoma have confirmed they paid jackpots worth $8 million to Tipton associates, including his old college roommate, Robert Rhodes. Investigators are looking at payouts in the other 37 states and U.S. territories that used random-number generators from the Iowa-based association, which administers games and distributes prizes for the lottery consortium." NOTICE THAT 40+ STATES AND US TERRITORIES ACTUALLY USED ONE RIGGED RNG FROM THIS CORRUPT DUDE IN IOWA I don't know what they these curves are used for, but, if there is anything at stake, it's worth looking into whether some of the people working on this project had college roommates that are now in lottery sinecures.
codezero 11y ago
Is it conceivable that a government agency could manipulate lottery results specifically to break this?
- jlgaddis 11y ago
  cf. the FAQ
  - codezero 11y ago
    Doh, thanks!
daodedickinson 11y ago
Hahaha they haven't seen all the past instances of lotteries being rigged? And they don't think it will happen in the future?
aagha 11y ago
ELI5
red_admiral 11y ago
Sigh, yet another attempt at solving the wrong problem. There is no shortage of proposals for how to generate curves. There is a shortage of implementations that you can just "npm install" or whatever and use. For ECC, I can name you one library that people like me can use - libsodium based on djb's Curve/Ed25519. It got into the TLS standard not because it's so much better than anything else but because it has an implementation that works, is available for many languages and has decent documentation. Of course it's helpful that djb spent a lot of time securing the thing against side-channel/timing attacks and employed the best coding practices and writing and presenting papers on the thing but no amount of writing papers is a substitute for sitting down and actually building the thing in a "production quality" way.
imdsm 11y ago
https://simple.wikipedia.org/wiki/Elliptic_curve https://simple.wikipedia.org/wiki/Elliptic_curve needs more input, so if anyone here is feeling up to it...

309 points by aburan28 11y ago

api 11y ago

I get the concern with NIST but I'm unsure about the concern with Curve25519. Is there any reason to suspect shenanigans there to be plausible? Also I'm not sure that future public lotteries are really that great. Technically such a thing could be rigged, though it would be hard. A truly good source would be something cosmic and public like sunspot records in the future that could be independently verified and recorded by multiple people and could not be tampered with unless God wants to backdoor our crypto.

vessenes 11y ago
Yes, I hate the idea of future public lotteries, published ahead of time. The entire idea is to be resistant to a nation-state attack; lotteries seem pretty far down the chain. If you're in love with lotteries, you could do something like order all lotteries in the world in a published list, and then choose them based on the last digits of bitcoin block hashes over a certain period. I'm not sure what bitrate you could get through sunspots, but I agree we shouldn't worry about subversion from that angle.
- baby 11y ago
  It's based on lotteries from different countries all around the world. No way ONE state adversary could rig this. It's also set in the future, you need to commit to the time frame where you'll be doing that. I think their plan was to tweet it and sing it on soundcloud (among other things)
  - api 11y ago
    > No way ONE state adversary could rig this. What about multiple state adversaries? It would be hard as hell but it could be done. I'd still opt for an astronomical source. If God wants to backdoor our crypto we're SOL, but other than that it would be pretty solid. I also don't get what's wrong with nothing up my sleeve constants. Hashing the word "YOLO" is mathematically unlikely to be a rigged constant to almost "probability of falling through the floor due to random quantum fluctuations" degrees.
    - baby 11y ago
      > What about multiple state adversaries? It would be hard as hell but it could be done. Highly unlikely, there is too much money in play, too many processes to corrupt... Cryptography is usually made solid enough so that there are easier ways to break the system. http://cryptoexperts.github.io/million-dollar-curve/#lotteries http://cryptoexperts.github.io/million-dollar-curve/#lotteri... > what's wrong with nothing up my sleeve constants It's not unpredictable. There are a million constants you could choose from if you wanted to make a backdoor. I think the badass paper is about that.
- tlrobinson 11y ago
  Why not just use Bitcoin blocks directly? A SHA-256 hash of 100 consecutive blocks should be sufficient.
  - paulajohnson 11y ago
    I wondered about that, but Bitcoin mining is increasingly dominated by a small number of big players, and they also have the hardware to do exhaustive searches on hash codes to find inputs that give the answer they want. I'm not saying its necessarily a bad idea, but its not immediately obvious that this is going to be harder to subvert than a selection of national lotteries.
deleted 11y ago
[deleted]
saganus 11y ago
Could it be something like stock market values in specific dates? If an actor can rig the stock market, the problems are different I Would think? Does the cosmic source not have an issue of who actually can make that measurement? will you not require some sort of specific tools and knowledge? or you mean using some astronomy databases created by reputable institutions?

gherkin0 11y ago

> Of course, one should not conclude that cryptographic algorithms using similar constants are systematically insecure (certainly, some designers are honest!) and we will not dispute the right to trust those algorithms. I'm reminded a controversial aspect of the design of DES. The values of the S-Boxes were unjustified, and some people feared they constituted a backdoor (much like what's alleged with Dual-EC-DRGB). It turns out that in fact they were specially chosen to strengthen DES against a cryptographic attack that the NSA was trying to keep secret. https://en.wikipedia.org/wiki/Data_Encryption_Standard#NSA.27s_involvement_in_the_design https://en.wikipedia.org/wiki/Data_Encryption_Standard#NSA.2...

vessenes 11y ago
The attack is "differential analysis" -- essentially, if you have a black box encoder, carefully chosen plaintexts sent through the system can leak information, and substantially weaken DES as described. Academic literature started discussing differential analysis in the early '90s if memory serves -- NSA helped harden against it in the 1970s! Current wisdom is that the NSA is not nearly so far ahead of the cryptography curve these days. But, it could just be speculation. :)
- ikeboy 11y ago
  What about the weakdh stuff? See e.g. http://www.scottaaronson.com/blog/?p=2293 http://www.scottaaronson.com/blog/?p=2293
  - tptacek 11y ago
    That's less about advances NSA may have made ahead of industry/academia and more about the operational advantages NSA has in deploying already-plausible attacks.
1024core 11y ago
My crypto prof in uni commented on this. (This is from memory). Apparently, the number of rounds (16) seemed to have been chosen arbitrarily. Many years later, when attacks on Feistel(?) ciphers (of which DES is one) became public, it turned out that these attacks only worked up to .... 15 rounds! So the speculation was that the NSA knew about the attack, and chose to set the round number just out of reach...

tomp 11y ago

I wonder how many global sources of randomness they've discarded before finding one that is both plausibly safe and exploitable.

FullyFunctional 11y ago

"Curve25519 was designed to be as fast as possible, with no security compromise. This is both a strength and a potential weakness: a strength because it gives a valid argument that no trapdoor was introduced in the design, a potential weakness because Curve25519 uses a very specific prime field. As of now, no attack exploiting this specificity is known. For applications where speed is paramount, Curve25519 is probably the best option. But for most applications, where losing a little on the efficiency side is "not a big deal", Million Dollar Curve is probably the safest choice." Sorry, no. Many more eyeballs have been on Curve25519 and DJB reputation, both of which gives me _more_ confidence in that than any new alternative. Secondly, the implementation is as important as the design. Again, Curve25519 have vetted implementations, something which takes time. Finally, the notion that speed is a liability is ludicrous. The lack of speed is a major liability. Move along, nothing to see here.

diziet 11y ago
Plus, Curve25519 and EdDSA have djb's stamp of approval.
- baby 11y ago
  I think the team at cryptoexperts is way more impressive.
  - tptacek 11y ago
    What's the other curve work they've done that makes you say that? I agree with the implication that an appeal to Bernstein isn't dispositive. But Curve25519 isn't just credible because of Bernstein; it's also been scrutinized intensively by lots of other research groups.
    - baby 11y ago
      from their FAQ: > We, at CryptoExperts, actually use Curve25519 and recommend it to our partners. Yet, we think that people should not rely on the same few safe curves that are currently out. Our methodology allows to easily produce safe alternatives.

tptacek 11y ago

The thesis of this paper seems to be that there aren't many alternatives to 25519. But anybody who watched the fiasco of the IRTF trying to standardize a recommendation on 25519 knows that's not true. Browser vendors were sold on DJB's curve and asked IETF to add it to TLS; given that simple charter, people came out of the freaking woodwork with alternatives. The "randomness derived from lotteries" property seems like a gimmick. Generating plausible random seeds isn't the hard problem with generating new curves. Rather, the problem is coming up with curves that are performant on common hardware without any patent-encumbered techniques. It's also not clear to me how the $1MM curve is a meaningful alternative to 25519. Almost the entire paper is given to considering how to generate random parameters. Having accomplished that task, the paper simply generates a random Edwards curve, using their lottery generator to find a random prime, d, and base point, filtered against the SafeCurve requirements. So they end up with (in effect) a randomized version of Bernstein's curve. If 25519 somehow falls, why wouldn't this curve fall with it? Compare this paper to those of 25519: https://cr.yp.to/ecdh/curve25519-20060209.pdf https://cr.yp.to/ecdh/curve25519-20060209.pdf ... or to FourQ: https://eprint.iacr.org/2015/565.pdf https://eprint.iacr.org/2015/565.pdf Also: the swipe at Brainpool seems disingenuous. Zero is the number of people who believe that Brainpool's mathematical constants were arranged specifically to create a backdoor. The point of BADA55 is that Brainpool's use of mathematical constants as seeds isn't dispositive, and that the performance-targeting parameters of 25519 are equally credible.

AlyssaRowan 11y ago
Indeed. One might be biased, given one was quite... um... vocal in the whole process! I personally feel Curve25519 and Ed448-Goldilocks were very thoroughly discussed, absolutely fine, and they are the final CFRG recommendations. I am quite certain of that, and I do believe we have proved that just about as well as anyone possibly can. (I'd like to thank everyone who suffered through the whole thing. I am just a participant there, I do not speak for anyone at all except myself, and hold no special anything.) Both of the CFRG curves are rigid 'safe' curves, with (unlike the NIST curves) solid criteria given for each and every aspect of their definition, all of which were argued in the open, and fully-reproducible parameter generation algorithms are included in RFC7748 - https://datatracker.ietf.org/doc/rfc7748/ https://datatracker.ietf.org/doc/rfc7748/ CFRG made the decision to select rigid 'safe' curves pretty early on, so that everyone could see exact reasons why we picked what we did at every stage, in the open, and that therefore absolutely no shenanigans were afoot. Specifically, we ended up picking one curve over a near-Mersenne prime (2^255-19), and one curve over a trinomial golden-ratio Solinas prime (2^448-2^224-1) - because they're about the right sizes, and rigidly-structured in a way that makes them almost uniquely fast in software. (We voted on specific sizes, and had supporting reasons even for that.) Both curves are also very handily - thanks djb & Mike Hamburg! - both already present in the existing literature, and indeed quite a few examples of X25519 (DH) and Ed25519 (sig) deployment in particular already exist. During the middle of the process, some people (some of whom were hardware developers involved in the selection of the "Brainpool" curves, a similar set of random prime field curves) showed up pushing for a new set of curves with random, unstructured prime fields. CFRG didn't go that way, and we discussed that decision and the reasons why thoroughly. Mostly because the performance of curves over randomly-structured primes absolutely sucks in software (I'm paraphrasing here, but we are talking an order of magnitude difference, at least), but also because given we were even arguing about endianness for God's sake, we'd probably never have been able to agree on a sound, unbiased-in-the-face-of-future-scrutiny method for selecting random parameters in an unbiased way, let alone one that we were positive we could convince sceptical third parties about. It would appear this curve comes from the hardware developers who really wanted new random curves in any case, and have tried to do just that anyway. Good luck to them there. The only possible advantage really with a random prime field is if some big problem exists with using elliptic curves over prime fields with a sparse bit pattern that doesn't also apply to random prime fields. We argued about that for a while (you may be detecting a pattern here...!), and the conclusion was that we simply don't know of any good underlying reason that would happen that wouldn't also pose a huge threat to random prime fields, or elliptic curve-based cryptography in general (e.g. big practical quantum computers - in which case, arguing about which elliptic curve to use would be pointless and maybe we just ought to burn our worldly possessions and go live in caves. I'm paraphrasing a bit here! <g>). The only thing that popped up was that if one has old crypto hardware that one is trying to reheat and present as new crypto hardware with go-faster stripes, and one is trying to get better performance from it by abusing its pre-existing RSA multiplier to do your ECC maths as well (like, for example, a certain hardware developer, ahem, might do), the side-channel blinding technique there would not work properly, because it's only designed to work with unstructured prime fields as you usually see in RSA, rather than a field with lots of concurrent 0s or 1s in there. So, um, friendly reminder, as I said at the time: if you have an RSA multiplier, please don't abuse it to implement your elliptic curves. (Note: this would also present an issue if you did it with the NIST curves, which are also so structured.) All the software out there that I've seen that implements Curve25519 appears to be at least timing side-channel resistant (this also being a goal, and why we went with Montgomery/Edwards forms specifically to simplify this, because short Weierstrass form is a bloody nightmare by comparison). If you are tasked with designing new crypto hardware today, I do feel you'd be better placed doing what a friend of mine suggested: instead of bolting new bits on decades-old designs like most people seem to, actually go and design new open hardware (RISC-V?) and try to restore some verifiability in that. Put all the crypto in open-source, verifiable software which the user loads and verifies (a friend's prototype design just uploads the whole executable EEPROM to the host for comparison with a known-good image whenever you connect it, and zeroises the data EEPROM in hardware whenever the executable EEPROM is written by the host) - and then ship the hardware absolutely blank. Then you hopefully have one less problem, as you don't really have dedicated crypto hardware as much as a solid general-purpose microcontroller with side-channel protection. (I wonder what impact that might have on export controls, if any?) In any case, you probably also have enough problems to worry about in your supply chain already without risking becoming the next Gemalto... or, God forbid should things not go well, Apple. Just a thought there. I know several people are working on open hardware now; I've heard of a couple of dedicated hardware implementations of 25519 floating around, too. I don't know of anyone who actually wants to use this so-called "million dollar curve". CFRG aren't recommending it. I'm certainly not. Not because it's bad. Just because - sorry, but as I said at the time - it's kind of... pointless? If you're using the Brainpool curves already, there's not really any reason you couldn't use this... but unless: a) you believe the Brainpool curves are deeply flawed somehow, enough to avoid, but these somehow aren't; and, b) you believe there's a huge breakthrough in number theory that affects structured primes but not unstructured primes or elliptic curves in general; and also, c) you believe nobody's going to show up with a quantum computer in the time period you're worried about... I just don't - personally! - see why you would bother switching. Clearly these people do. I suppose we simply disagree there, which wouldn't be the first time.

cperciva 11y ago

Sigh The issue here is that we need a trusted source of "nothing up my sleeve" numbers: https://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number https://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number This is why the RFC 3526 groups use primes derived from Pi: https://tools.ietf.org/html/rfc3526 https://tools.ietf.org/html/rfc3526 I'm sure that it would be difficult to tamper with the results of lotteries held all over the world. But it's even harder to tamper with the value of Pi.

baby 11y ago
Problem, pi is not unpredictable.
- cperciva 11y ago
  It doesn't need to be. The group you're using is part of the cryptosystem, not part of the key.
  - baby 11y ago
    And the cryptosystem might be backdoored by the way you choose the constants. (they are way too many constants to choose from)
    - tptacek 11y ago
      It really isn't backdoored, though. Bada55 made a legit point that curves shouldn't be required to derive from simple math constants, but it does less of a good job showing that math constants are themselves necessarily untrustworthy. You'd need an awfully funky looking set of constants to get the degree of freedom bada55 proposes.
    - cperciva 11y ago
      Right. Hence "nothing up my sleeve" numbers. It's hard to fit a backdoor into Pi.
      - 11y ago

matt_wulfeck 11y ago

From a practical point having sources of randomness/entropy isn't very useful. A CSPRNG will do a great job generating random numbers. It will create secure Tls connections and a ssh_key that's never been seen before. However it's Achilles heel is that it MUST be seeded with random numbers. That's hard to do in a predictable state, such as a headless vm. If the seeds no good it can't establish a secure Tls connection to fetch random data (ala Ubuntu pollinate service). The next thing to push crypto security forward is easy, efficient, and trustworthy ways to generate this seed.

tptacek 11y ago
Yeah, you're missing the point a little. If you want to generate and standardize a random curve (like, in this paper, the "random" version of Curve25519, which doesn't rely on specific magic parameters carefully chosen for speed), you have a big problem: even though your CSPRNG might be perfectly fine, nobody is going to believe that you actually used it, because you can't prove that you did. Hence: lotteries.

PaulHoule 11y ago

see https://en.wikipedia.org/wiki/Numbers_game https://en.wikipedia.org/wiki/Numbers_game

deleted 11y ago

[deleted]

jdlyga 11y ago

I'm donating 35 dollars to Million Dollar Curve. Who wants to match me?

jdlyga 11y ago

I'm donating 35 dollars to Million Dollar Curve. Who wants to match me?

yandrypozo 11y ago

more garbage over the garbage !!

tonyhb 11y ago

Elliptic curves are going to be rendered redundant with the introduction of quantum computing via shor's algorithm. 25519 is already trusted and fast, and in all likelihood will probably last until we need to shift from this type of cryptography. Seems as though this is pretty futile and doesn't need to exist.

cyphar 11y ago

One thing that is ignored is that you can't be sure that a lottery isn't rigged. We've seen cases (Serbia) where lotteries were rigged, so it's very possible that someone with enough money could rig your entropy source.

daodedickinson 11y ago
It's relatively rare that lotteries AREN'T rigged. It's a bunch of money sitting RIGHT THERE to the people implementing the lottery. And like any other situation where human beings have a GIGANTIC incentive to commit fraud, they often do: https://thehornnews.com/authorities-lottery-may-be-rigged/ https://thehornnews.com/authorities-lottery-may-be-rigged/ http://www.nydailynews.com/news/national/lottery-employees-rigged-14-3-win-officials-article-1.2185601 http://www.nydailynews.com/news/national/lottery-employees-r... "State lotteries in Colorado, Wisconsin, and Oklahoma have confirmed they paid jackpots worth $8 million to Tipton associates, including his old college roommate, Robert Rhodes. Investigators are looking at payouts in the other 37 states and U.S. territories that used random-number generators from the Iowa-based association, which administers games and distributes prizes for the lottery consortium." NOTICE THAT 40+ STATES AND US TERRITORIES ACTUALLY USED ONE RIGGED RNG FROM THIS CORRUPT DUDE IN IOWA I don't know what they these curves are used for, but, if there is anything at stake, it's worth looking into whether some of the people working on this project had college roommates that are now in lottery sinecures.

codezero 11y ago

Is it conceivable that a government agency could manipulate lottery results specifically to break this?

jlgaddis 11y ago
cf. the FAQ
- codezero 11y ago
  Doh, thanks!

daodedickinson 11y ago

Hahaha they haven't seen all the past instances of lotteries being rigged? And they don't think it will happen in the future?

aagha 11y ago

ELI5

red_admiral 11y ago

Sigh, yet another attempt at solving the wrong problem. There is no shortage of proposals for how to generate curves. There is a shortage of implementations that you can just "npm install" or whatever and use. For ECC, I can name you one library that people like me can use - libsodium based on djb's Curve/Ed25519. It got into the TLS standard not because it's so much better than anything else but because it has an implementation that works, is available for many languages and has decent documentation. Of course it's helpful that djb spent a lot of time securing the thing against side-channel/timing attacks and employed the best coding practices and writing and presenting papers on the thing but no amount of writing papers is a substitute for sitting down and actually building the thing in a "production quality" way.

imdsm 11y ago

https://simple.wikipedia.org/wiki/Elliptic_curve https://simple.wikipedia.org/wiki/Elliptic_curve needs more input, so if anyone here is feeling up to it...