|
Title: NSA and ECC Post by: natb on September 07, 2013, 06:17:08 PM I've been reading up recently on the revelations that the NSA is subverting implementations/service providers to undermine various internet crypto standards (see this: http://www.theguardian.com/world/2013/sep/05/nsa-gchq-encryption-codes-security (http://www.theguardian.com/world/2013/sep/05/nsa-gchq-encryption-codes-security)).
Now this has all of the basic hallmarks of a 'scare campaign' where people are led to believe that crypto techniques/mathmatics themselves are insecure rather than the truth that the NSA is attacking the services or implementations directly (much easier). Therefore I was ready to write this off as 'not relevant' to an open source peer reviewed protocol like Bitcoin. However, something Bruce Schneier (someone intimately familiar with the mathematics behind crypto algorithms) said has given me some concern. He is suggesting that the ECC constants have been manipulated to facilitate subversion (see his blog comment here: https://www.schneier.com/blog/archives/2013/09/the_nsa_is_brea.html#c1675929 (https://www.schneier.com/blog/archives/2013/09/the_nsa_is_brea.html#c1675929)). For his full essay, go here: https://www.schneier.com/essay-446.html (https://www.schneier.com/essay-446.html). Any thoughts on implications here we need to be concerned about? Title: Re: NSA and ECC Post by: Mike Hearn on September 07, 2013, 06:51:58 PM He's worried about constants that have no explanation. The SEC random curves have "random numbers" in them, but are they really random? AFAIK nobody knows how one might exploit the algorithms if they weren't, but hesitation is reasonable.
However Bitcoin does not use a random curve. It uses a Koblitz curve where there are explanations for why the constants are the way they are. Also, the NSA is not going to crack the crypto used on Bitcoin because their goal is not to actively attack Bitcoin (I doubt the NSA care much about financial regulations). Their goal is to spy on everyone. They're much more likely to do graph analysis of the block chain than worry about the crypto. Title: Re: NSA and ECC Post by: natb on September 07, 2013, 07:38:44 PM Ok, so your take is basically the same as the commenter on Schneier's blog (https://www.schneier.com/blog/archives/2013/09/the_nsa_is_brea.html#c1678526).
Basically he says what you are saying - that a recommended 'random' number generator for use with ECC has been proven to have backdoors, and that some families of ECC curves have weaknesses. However, because we're using secp256k1, a known curve with explainable/justifiable constants, the concern cited by Bruce is not applicable to Bitcoin in addition to the weak motivation for attacking it anyhow. Thanks for the reply. Title: Re: NSA and ECC Post by: gmaxwell on September 07, 2013, 09:58:23 PM The SEC random curves have "random numbers" in them, but are they really random? FWIW, the "random" curves have their parameters selected by a deterministically random machine search... this seems like it would have made choosing their parameters maliciously even harder.I do sometimes worry about ECC since there are techniques for DLP solving which have scalability more like modern factoring but which (currently) only apply to supersingular curves. If someone figures out how to apply them to ordinary curves, e.g. by solving a related problem on extension fields, we'd need to use ECC with more RSA like key sizes to obtain comparable security. Fortunately none of this is fundamental to Bitcoin— Bitcoin could add another checksig operator very quickly if there appeared to be an urgent need... and addresses which are not reused only have their public keys exposed to a hypothetical ECC cracker for a brief time between a spend announcement and confirmation. Title: Re: NSA and ECC Post by: maaku on September 07, 2013, 10:09:33 PM Schneier's reasoning is basically this: we don't know what cryptanalysis the NSA is capable of (Schneier might after seeing the leaked documents, but he's not letting on). But it is likely that if there were a weakness it would likely affect only certain categories of curves. The random curves were (presumably) chosen at random, but so were the Koblitz curves: there are many possible Koblitz curves, and the specific ones enumerated in the standard (like secp256k1) were purportedly chosen at random from the set of possible Koblitz curves of that length. But here's the rub: how do we know the NSA didn't search through the space of Koblitz curves looking for one that was secure as far as academia knew, but susceptible to attacks based on mathematics only the NSA knew?
Pre-Snowden, this would have been considered tinfoil hat paranoia because it is not a new concern. The exact same situation existed with DES, which was the federal standard for cryptography for decades. Designed by IBM but with parameters chosen by the NSA, some paranoids thought they had inserted a back door (there was even a Senate investigation). But as we later found out, the tweaked S-boxes strengthened the algorithm against differential cryptanalytic attacks, which weren't known to the public until recently. The rules of the game until now had been: we work with the NSA through NIST competitions to standardize cryptography. The NSA continues to collect the intelligence it needs through exploiting side channels, weak random number generators, bugs, and even strong-arm techniques, but the algorithms are secure. You can trust the math. These new revelations apparently throw that out the window. In recent years the NSA actively pushed NIST for standards that it knew were insecure. Not easy-to-get-wrong, like DSA (choose a predictable K value, or reuse an old value and you reveal your private key - a slight of hand that puts the master keys inside the RNG, something which the app has little control over and the NSA can influence), but rather fundamentally broken in subtle ways. How do we know they did not do the same for ECDSA, or any other standardized crypto system that has chosen parameters? Schneier is justified in his recommendation, IMHO. But there is one bright spot: even if the standard ECDSA curves were broken in this way, if you do not reuse addresses it would not concern you as no public key or ciphertext is available until the coins are spent. So don't re-use bitcoin addresses (you shouldn't anyway). EDIT: gmaxwell, was the algorithm for parameter selection published? If so, I must have missed this. Title: Re: NSA and ECC Post by: natb on September 07, 2013, 11:02:44 PM The rules of the game until now had been: we work with the NSA through NIST competitions to standardize cryptography. The NSA continues to collect the intelligence it needs through exploiting side channels, weak random number generators, bugs, and even strong-arm techniques, but the algorithms are secure. You can trust the math. These new revelations apparently throw that out the window. In recent years the NSA actively pushed NIST for standards that it knew were insecure. ... EDIT: gmaxwell, was the algorithm for parameter selection published? If so, I must have missed this. This is the key revelation to me as well. It seems that the trust in the parameters chosen for the various curves must be questioned at this point. Does anyone have a history of how our secp256k1 curve parameters were chosen, by whom, and by what process it was tested to give it a 'recommended curve' stamp of approval? It is just a curiosity for me - the point that the Bitcoin framework allows for a substitution of signing technique is noted and understood in the event that a flaw was discovered in our curve, or techniques to accelerate cracking ECC itself were discovered. Title: Re: NSA and ECC Post by: etotheipi on September 08, 2013, 01:31:55 AM In case you don't follow slashdot, there was an article today from John Gilmore (http://en.wikipedia.org/wiki/John_Gilmore_(activist)) about obstructionism by NSA folks he's seen over the years:
http://www.mail-archive.com/cryptography@metzdowd.com/msg12325.html It's mostly about simple obstruction of implementing standardized security systems. But it wouldn't surprise me if the same folks also attempted some more subtle things, like trying to inject pre-selected "random" constants into crypto systems. But I'm not all that familiar with the processes they use or how easy that would be. Title: Re: NSA and ECC Post by: gmaxwell on September 08, 2013, 02:34:32 AM EDIT: gmaxwell, was the algorithm for parameter selection published? If so, I must have missed this. Not for the "Koblitz" (in quotes because normally Koblitz refers to curves over a field of characteristic 2 and not a prime field) curves but for the random ones which almost everyone else uses. Thats why I think the claim is kind of odd, virtually all EC usage on the internet uses the prime random ones (like P-256r) which have their selection scheme published as part of the SEC document. I believe Bitcoin is the only widespread user of the SECP*k curves. (Although the curve used in Ed25519 has a similar structure, which is also why it's performance is similar). P256k1 was not included in any of the NIST standards, it's only a part of the certicom spec. So if you're hypothesizing NIST as the _specific_ vector of pushing for weak ECC then your theory really should exclude Bitcoin's curve from the start. (In other words: good rational reasoning is that if your argument is ECC is dubious because NSA influences NIST, then you should equally find our use of a non-nist curve comforting, no?) (This isn't to say that I would find it hard to believe that certicom is a pawn of CSE. :P ) I would, however, be concerned that the "vulnerability" were the use of koblitz form alone. Part of the problem is that once you start assuming mystery math anything is possible. My comments about the public keys not being disclosed with good use and our ability to upgrade still stand... though, uh, if our upgrade option were to change to a non-koblitz curve (or a much larger field) I'd have some concerns about the scalability impact. Making things more secure against conjectured weaknesses doesn't help if the fixes make the system non-viable or drive us into centralization. :( (Though I've long wondered with PGP, which doesn't really have the same scaling concerns doesn't use multiple asymmetric schemes in parallel in such a way that an attacker would have to break all of them...) Personally, I'd like to see us deploy— as an option— Lamport/Merkle signatures because they have totally orthogonal security properties and are based on assumptions most cryptographers would consider fundamentally stronger... plus they answer any QC fud. They also permit very fast validation, even with trivially implemented code (fast SECP256k1 validation is far from trivial). The tradeoff is that the signatures are much larger... but at least signatures don't end up in the UTXO set. I haven't considered this urgent, but it's been on my long term wishlist since early 2011. It might be fun to ask certicom to publish the procedure used to select SECP256k1's parameters. Though the design space of near maximally sized "Koblitz" curves is smaller than you may be guessing. It may be the case that we could reverse engineer the procedure. Title: Re: NSA and ECC Post by: markm on September 08, 2013, 05:17:02 AM In case you don't follow slashdot, there was an article today from John Gilmore (http://en.wikipedia.org/wiki/John_Gilmore_(activist)) about obstructionism by NSA folks he's seen over the years: http://www.mail-archive.com/cryptography@metzdowd.com/msg12325.html It's mostly about simple obstruction of implementing proper security systems. But it wouldn't surprise me if the same folks also attempted some more subtle things, like trying to inject pre-selected "random" constants into crypto systems. But I'm not all that familiar with the processes they use or how easy that would be. The part (a post or few up and down that page) about "good guys" aka "on our side" seems weird since we seem to be heading toward or to have already reached (maybe long ago by now) a place where we have figured out certain actions are bad, and that therefore it wouldn't be good to do those acts. So is this about whether good guys can do bad things, deliberately, with aforethought, and still be considered to be good guys? Is the fundamental problem here that we think that, as good guys, we would prefer having to fight world war three in a world of perfect cryptography for all than to fight it in some kind of Luddite hell in which encryption is only for two-legs, four-legs shouldn't have it? (CF "four legs good, two legs bad", Orwell, Animal Farm) Do we want to be four-legs, with two-legs looking after us, maybe believing the propaganda promulgated by the conclusion of Animal Farm that two legs really is some kind of superior being, that we could never govern ourselves so need two-legs to govern us? Are we so weak and pitiful that we need to cripple ourselves before the enemy does so that we can intercept to find out ahead of time how exactly the enemy plans to attempt to cripple us? -MarkM- EDIT: maybe its not "we" (the people) who are weak and pitiful but that the Peter Principle is still in effect so "they" (the so called government or its agencies) are? Title: Re: NSA and ECC Post by: gmaxwell on September 08, 2013, 01:26:34 PM EDIT: gmaxwell, was the algorithm for parameter selection published? If so, I must have missed this. Not for the "Koblitz" (in quotes because normally Koblitz refers to curves over a field of characteristic 2 and not a prime field) curves but for the random ones which almost everyone else uses. Thats why I think the claim is kind of odd, virtually all EC usage on the internet uses the prime random ones (like P-256r) which have their selection scheme published as part of the SEC document. And I realize that while the P-NNNr curves do use a deterministic value their provided seeds are completely fucking implausible. E.g. the seed for P-256r is c49d360886e704936a6678e1139d26b7819f7e90. They procedure generates random data by feeding the seed into SHA1. There is no reason I could tell that the seed wouldn't have been something like "15" (and all lower values would have failed the test). Secg says about these curves: Quote Verifiably random parameters offer some additional conservative features. These parameters are chosen from a seed using SHA-1 as specified in ANSI X9.62 [1]. This process ensures that the parameters cannot be predetermined. The parameters are therefore extremely unlikely to be susceptible to future special-purpose attacks, and no trapdoors can have been placed in the parameters during their generation. But that a great big fucking lie, since a special purpose attack only has to applicable to randomly selected curves more often than you can iterate sha1 for you to be able to slip one into one of these "verifiable random" curves. Maybe they used this freedom to apply additional tests and make them stronger... Maybe? SECG adds another tidbit: Quote The elliptic curve domain parameters over (primes) supplied at each security level typically consist of examples of two different types of parameters — one type being parameters associated with a Koblitz curve and the other type being parameters chosen verifiably at random — although only verifiably random parameters are supplied at export strength and at extremely high strength. I would note that if you read "verifiable random" as "backdoored as all fuck" the fact that only verifiable random are provided for export strength (<=128 bit), and perhaps thats some suggestion that the Koblitz curves are not "backdoored as all fuck". Though thats really handwavy speculation... and it could just be that they didn't care about the performance of the export grade ones. (Or... made the export grade ones weak and the others stronger?!) Title: Re: NSA and ECC Post by: maaku on September 08, 2013, 05:43:25 PM Just to make sure I have this right, Bitcoin does not use these "backdoored as all fuck" ECC specifications? or Does bitcoin use an ECC specification with a "magic number"? Bitcoin uses a curve whose magic numbers were specified by Certicom - thanks for the correction, gmaxwell - a U.S. subsidary of Research in Motion (makers of Blackberry, who have been funneling user communications into the NSA since the early days, apparently) that owns most of the patents related to ECC. Whether that is more or less threatening in light of recent revelations, I'll let you decide. Title: Re: NSA and ECC Post by: gmaxwell on September 08, 2013, 09:26:29 PM Bitcoin uses a curve whose magic numbers were specified by Certicom - Certicom is canadian. And in our curve the magic numbers are generally more tightly constrained by the special form of the curve. But who knows. The special form itself may ultimately turn out to be weaker... but the performance impact is considerable and this does matter for our usage.Title: Re: NSA and ECC Post by: maaku on September 08, 2013, 10:23:48 PM Once again I defer to gmaxwell. I drive by their headquarters in Scotts Valley about once a month .. but apparently this is just the headquarters of their U.S. branch. They are in fact a Canadian company.
Title: Re: NSA and ECC Post by: niko on September 09, 2013, 03:34:58 AM Someone versed in ECC timeline should sift through the appropriate meeting minutes on certicom site, perhaps they already hint at how parameters were chosen.
Title: Re: NSA and ECC Post by: e4xit on September 09, 2013, 09:45:16 AM ... The special form itself may ultimately turn out to be weaker... but the performance impact is considerable and this does matter for our usage. Is this related to something you responded to me in another thread, when we were talking about brute-forcing bitcoin-wt wallet.dat's, that the time taken for each brute-force was relatively high - what I am asking is, is this a result of choosing these magic numbers? Title: Re: NSA and ECC Post by: jackjack on September 09, 2013, 10:03:16 AM ... The special form itself may ultimately turn out to be weaker... but the performance impact is considerable and this does matter for our usage. Is this related to something you responded to me in another thread, when we were talking about brute-forcing bitcoin-wt wallet.dat's, that the time taken for each brute-force was relatively high - what I am asking is, is this a result of choosing these magic numbers? AFAIK wallet.dat is encrypted using AES Title: Re: NSA and ECC Post by: gmaxwell on September 09, 2013, 10:15:53 AM Is this related to something you responded to me in another thread, when we were talking about brute-forcing bitcoin-wt wallet.dat's, that the time taken for each brute-force was relatively high - what I am asking is, is this a result of choosing these magic numbers? No. The wallet encryption is relatively boring symmetric cryptography. We've intentionally designed it to be slow to inhibit brute-forcing. The fast stuff I'm discussing in this thread is primarily ECDSA signature validation, which must be very fast because all full nodes validate all the transactions. Title: Re: NSA and ECC Post by: BurtW on September 09, 2013, 11:50:22 AM Speaking of the ECDSA, I was wondering if it might be a good idea to have everyone start including a second (more secure?) signature algorithm that does not require a random nonce. Then when a vast majority of the network nodes contain the new "nonceless" signature algorithm switch over to it but leave the current algorithm as a deprecated option.
On the other hand, thinking out loud here, using the nonce allowed us to discover the bad RNG on android devices. By switching the ECDSA we might actually mask any future RNG issues which might then cause even harder to detect problems like identical private key generation. Title: Re: NSA and ECC Post by: fpgaminer on September 09, 2013, 12:16:20 PM Quote I was wondering if it might be a good idea to have everyone start including a second (more secure?) signature algorithm that does not require a random nonce. gmaxwell proposed BIP 0032.5, calling for the usage of a deterministic version of ECDSA. Deterministic ECDSA signature generation (like the one defined by RFC 6979) is compatible with existing ECDSA verification implementations, so any Bitcoin client could use it today. Neat! I have a thread open (https://bitcointalk.org/index.php?topic=285142.0) discussing RFC 6979.Quote On the other hand, thinking out loud here, using the nonce allowed us to discover the bad PRNG on android devices. It may be wise for applications to run continuous health checks on any RNG they're using. FIPS 140-2 requires a simple one, for example. Maybe even run a cut-down version of DIEHARD every so often?Title: Re: NSA and ECC Post by: Mike Hearn on September 09, 2013, 01:51:42 PM And I realize that while the P-NNNr curves do use a deterministic value their provided seeds are completely fucking implausible. E.g. the seed for P-256r is c49d360886e704936a6678e1139d26b7819f7e90. They procedure generates random data by feeding the seed into SHA1. There is no reason I could tell that the seed wouldn't have been something like "15" (and all lower values would have failed the test). Well, damn. Presumably they'd argue the seed is also supposed to be random for "extra randomness" or something? If the NSA did know of an attack on ECC for specific curve parameters, doing a brute force search over SHA-1 inputs until you found a breakable output would appear one way to do it. It'd be really fantastic to know where the hell that seed value came from. Schneier might have a point about not trusting ECC! Or at least only using it with something like curve25519. Title: Re: NSA and ECC Post by: Mike Hearn on September 09, 2013, 02:06:01 PM These slides are interesting:
http://cr.yp.to/talks/2013.05.31/slides-dan+tanja-20130531-4x3.pdf It says right out that the NSA generated the curves: Quote Important example: IEEE P1363 standard Surveys all ECDLP attack techniques known in 1999 Prohibits all curves breakable by these techniques Speci es method of generating random non-prohibited curve Jerry Solinas at NSA used this to generate the NIST curves (or so he says) However it also implies that the generation criteria might be more complicated than just "iterate a hash input until a functioning curve is found". Is it possible the seed looks strange because large classes of output curves were discarded due to known attacks? This might be Mr Solinas' email address: jasolin@orion.ncsc.mil We could ask him if how the curves were generated is reproducible. Apparently the NSA controlled all membership to the IEE P1363 working group: http://grouper.ieee.org/groups/1363/WorkingGroup/announcements/Nov96.txt Quote Due to NSA requirements, THOSE PLANNING TO ATTEND THE MEETING MUST CONTACT JERRY SOLINAS IN ADVANCE OF THE MEETING to be placed on the attendance list. This just looks worse and worse, doesn't it. I didn't realise ECC was so heavily influenced by the NSA before. I thought it had been primarily developed by the academic sector. Title: Re: NSA and ECC Post by: Carlton Banks on September 09, 2013, 02:12:13 PM This might be Mr Solinas' email address: jasolin@orion.ncsc.mil We could ask him if how the curves were generated is reproducible. Maybe better ask first if the generation methodology is classified. Title: Re: NSA and ECC Post by: markm on September 09, 2013, 02:36:34 PM So maybe there is a class or category of attacks, making all ECC broken, and they iterated through SHA1 generating curves knowing they could, with their clever class or category, break them, but wanting to not bother recommending those the public already had found attacks for?
The attacks known to the public would maybe mostly be individual subsets of the secret class or individual classes of the secret category or something like that. (I'd have to go read up on what class and category mean in class theory and category theory if I wanted to check whether I used the words set, class and category correctly.) -MarkM- Title: Re: NSA and ECC Post by: piotr_n on September 09, 2013, 02:38:15 PM It indeed is weird (to say the least) that NSA was involved in choosing random constants for these industrial standards.
At the other hand, from what I understand these constants are like 10 years old. If there is any secret math that can be used to exploit ECC with a certain curve parameters (and NSA had known about it before these constants were chosen), it would basically mean that all the academic world sucks, if it have not managed to discover the same formulas ever since then. It even seems unlikely that such a breakthrough math inventions would not have leaked out, for all these years. So there is still hope... but it would still be good to find out how (and why) these constants were picked up. Title: Re: NSA and ECC Post by: markm on September 09, 2013, 02:41:48 PM Whozit's conjecture or whatever, written in a margin long ago, took frikkin centuries for academics to figure out.
Had the guy maybe not really solved it himself afterall but just imagined he had? I made a proof, as a child, of the four colour theorem that still looks good to me. In my late teens someone even tried submitting it to Scientific American because it looked so good. Yet to this day I still have not managed to get any actual proper refutation of it or explanations as to how, if it is not a "proof", it fails to be one. My maths teacher when I first came up with it said the whole thing was so far beyond him he could not even begin to judge if it was or was not mathematically a proof but that it sure seemed to be an irrefutable argument to him, lacking as he was in deep enough mathematical training to figure out where it went wrong, if it did in fact go wrong. (It is so simple, even children "get it", thus suspect as in hmm maybe it is not state-able mathematically in rigorous math.) So between the margin-written thing that people bumped heads with for so long, and my own personal experience, it does not seem far fetched at all to me that some kid somewhere pointed out some insanely simple thing that mathematicians had all overlooked and continue still to overlook. Then too there is Bell's Theorem, which even now while Joy Christian keeps pointing out Bell's massive deep fundamental flaw in it a lot of physicists just cannot see / understand the flaw, seemingly because they make the same categorical or dimensional error themselves in judging his work. -MarkM- Title: Re: NSA and ECC Post by: piotr_n on September 09, 2013, 02:57:18 PM I guess many things are possible.
But for sure it is impossible that, if there is the secret math, nobody knows about it. No matter how secret NSA would like to keep it, there should be at least tens of people who would know about it. But more likely hundreds, or even thousands... Ever since bitcoins have become an actual money, and since people are able to short BTC, there is an actual incentive to make such an info public - and leaking it out anonymously (using tor, or whatever) does not seem to be so much of a challenge. At the other hand, if you know the secret math and how to exploit the constants, maybe you would earn more just by stealing bitcoins - but then we would also find out about it. Title: Re: NSA and ECC Post by: markm on September 09, 2013, 03:00:25 PM Sure, if they actually believe it.
But suppose even though you see in front of your eyes the computer produce a solution, all your mathematicians claim it is impossible thus you believe what is really happening is rubber hoses are being wielded somewhere then the PR department is passing off the miraculous results as being due to a secret formula in the computer? Maybe those who know solutions can be found by that computer think whistleblowing "the government has rubber hoses!" is not exactly breaking news... The number of people who know the computer really is using math to get the answers need not be nearly as large as the number of people who know the computer is in regular use providing answers. I probably wouldn't tell people only four colours are needed to colour a 2-D map if knowing it would kill gosh knows how many agents of the five-eyes (https://www.google.com/search?q=Reteif+five+eyed+little+sticky-fingers&ie=utf-8&oe=utf-8&aq=t&rls=org.mozilla:en-US:official&client=firefox-a) (brits, canucks, yanks, aussies, kiwis) and the world had not yet proven it to be so. (Scientific American didn't consider it proven until some ridiculously huge computer-generated proof involving iterating over stuff finally proved it long after I thought I had, maybe because my "even a child can grok it" approach is just too darn simple for their complicated little minds.) Maybe they tell people who would whistleblow if it were rubber hoses that it is math, and people who would whistleblow if it were math that it is rubber hoses, if just letting people imagine whichever they like doesn't seem likely to work in some particular case? -MarkM- Title: Re: NSA and ECC Post by: BurtW on September 09, 2013, 03:24:27 PM I for one would like to see your four color proof. Can you publish it in an off topic thread or PM me a copy?
RE the parameter selection process: I will email and ask if no one else has already. We probably do not want to bury him him emails. Title: Re: NSA and ECC Post by: markm on September 09, 2013, 03:27:53 PM Hmm I wonder how many colours of coloured coin it takes to [something something] a blockchain? ;) :D
(You only need four whatzits to build a DNA strand? Hmm....) Think like the game "sprouts (http://en.wikipedia.org/wiki/Sprouts_%28game%29)". (And maybe read Piers Anthony's "Macroscope" while you're at it.) One point is a point, two is a line, three is a circle. If the fourth is inside the circle, it is surrounded, no luck there. If the fourth is outside the circle, how you gonna connect it to the other three without surrounding any of them? -MarkM- Title: Re: NSA and ECC Post by: maaku on September 09, 2013, 04:23:49 PM It indeed is weird (to say the least) that NSA was involved in choosing random constants for these industrial standards. It is not at all weird. Like I posted earlier, this was the case with the DES S-boxes as well, which was a similar opportunity to back-door symmetric encryption. In that case the NSA took the high route and strengthened the algorithm against attacks that would not be (re-)discovered by industry and academia until decades later. So when NSA employees stepped in and did a similar thing with ECC curve parameters, there was no compelling reason at the time not to trust them. Of course looking back, DES was only strengthened against attacks that were known by IBM employees at the time, but kept classified. Other forms of attack have shown theoretical success in recent years, and may or may not have been known to the NSA at that time. Maybe this is being paranoid? But with these new revelations, what level of paranoia is justified? Fool me once, shame on me, fool me twice... Title: Re: NSA and ECC Post by: piotr_n on September 09, 2013, 04:28:14 PM It indeed is weird (to say the least) that NSA was involved in choosing random constants for these industrial standards. It is not at all weird. Like I posted earlier, this was the case with the DES S-boxes as well [...] Well at least, from what I see, nobody seems to have an idea why these constants and not some others... not even Bruce Schneier :) Title: Re: NSA and ECC Post by: gmaxwell on September 09, 2013, 04:32:50 PM However it also implies that the generation criteria might be more complicated than just "iterate a hash input until a functioning curve is found". Is it possible the seed looks strange because large classes of output curves were discarded due to known attacks? The procedure described to the public would not discard very many.The seed is a very large number... so wherever they started from, it wasn't 0. It could be that they discarded many while making the curve stronger, not weaker, using unknown criteria. ... or that they hardly discarded any any at all and just used a secure RNG to pick their next seed instead of incrementing, a left over from a less deterministic procedure. It seems that there is no way to tell, and unless it turns out that the values are really just hashed newspaper headlines, it seems unlikely that they could convince the public any which way on the matter. Quote This just looks worse and worse, doesn't it. I didn't realise ECC was so heavily influenced by the NSA before. I thought it had been primarily developed by the academic sector. I knew that that there was heavy NSA influence, at least in the public standards, but after all— NSA has a dual mission, the strengthening security / spying on people... and they likely are the single largest employer of cryptographic mathematicians, so it wouldn't be surprising or unusually concerning.Ultimately if these curves can be weak based on unknown-to-the-world math, thats bad regardless of tinkering with the parameter selection— and another (actually) random curve could be worse against that kind of threat. But I suppose that there is nothing like postulating a specific attacker to help crystallize the attacks that perhaps we should have worried about all along. Title: Re: NSA and ECC Post by: maaku on September 09, 2013, 04:37:39 PM Because even if the information they used to construct the S-boxes is now public, it still reveals the limit of the NSA's knowledge. What if X for some X in the intelligence agencies of Russia, China, Israel has Super Cryptanalysis Technique that the NSA doesn't know about. Then the NSA publishes what technique was used to come up with the S-boxes / curve parameters and -- egads! The NSA didn't check for weaknesses from Super Cryptanalysis Technique! That's exploitable knowledge.
This is why these things are kept secret for something like 70 years. Because showing the sum total of what you know reveals what you didn't know you didn't know. Title: Re: NSA and ECC Post by: piotr_n on September 09, 2013, 05:06:47 PM Because even if the information they used to construct the S-boxes is now public, it still reveals the limit of the NSA's knowledge. I'm starting to feel less and less comfortable reading how the ECC security might not rely as much on the well known math that proves their safety, but rather on NSA secretly choosing their shapes :)Title: Re: NSA and ECC Post by: balanghai on September 09, 2013, 05:38:37 PM I think it's not just spying but also controlling. ::)
Title: Re: NSA and ECC Post by: DeathAndTaxes on September 09, 2013, 07:43:00 PM While I don't believe NSA has compromised the secp256k1 curve it would be a good idea for Bitcoin to support different address "types". Today Bitcoin only supports a single type of address construction (excluding P2SH) but this isn't a requirement. It would be possible to extend the protocol to support multiple methods of address generation. If ECDSA, RIPEMD-160 or SHA-256 are partially broken to avoid a loss of confidence (and eventually loss of fund security) it will eventually be necessary to extend the Bitcoin protocol to support a new address types. Doing this now (before mandatory due to compromise of current primitives) would lay the foundation for a more extensible/adaptable protocol.
Bitcoin uses both digital signatures (ECDSA) and hashing functions (RIPEMD-160, SHA-256) in transactions/addresses. The protocol could be extended to support a second "type" of address using DSA, RSA, or ElGamal for key generation and a different hashing algorithm (RIPEMD without SHA, SHA-3, WHIRLPOOL) to derive the address from the public key. An even better solution would be one which allows mixing and matching keys and checksumed hashes (addresses). Alternative curves for ECDSA could also be explored. The main disadvantage of using non-ECC based signature systems is that they generally have larger key and signature sizes for an equivalent 128 bit security. Code: Algorithm PubKey Len PrivKey Len Sig Len Example 2 input, 2 output transaction size Code: ECC 370 bytes (434 bytes w/ uncompressed PubKey) This assumes the use of explicit key (PubKey is included with signature). I am unsure if Public Key Recovery is possible with DSA or RSA (it is for ECC but unused by Bitcoin protocol). If possible then using implicit public keys would provide a significant reduction in transaction size (45% to 75%) as it would allow the elimination of the PubKey (384 bytes) in each input. Title: Re: NSA and ECC Post by: theymos on September 09, 2013, 08:13:28 PM And I realize that while the P-NNNr curves do use a deterministic value their provided seeds are completely fucking implausible. Ah, very interesting! I never bothered to check that (and I bet a lot of other people didn't, either). Wouldn't it be hilarious if Satoshi managed to choose one of the few standard curves that was not backdoored? Title: Re: NSA and ECC Post by: Mike Hearn on September 09, 2013, 08:32:21 PM An alternative CHECKSIG would almost certainly use curve25519 for various reasons, including but not limited to side channel attack resistance. It also doesn't use random values for K.
Title: Re: NSA and ECC Post by: gmaxwell on September 09, 2013, 08:56:44 PM Today Bitcoin only supports a single type of address construction (excluding P2SH) but this isn't a requirement. Why do you ignore P2SH? It is the only practical way to actually _deploy_ another cryptosystem... without it you couldn't start using your fooknapsack key until everyone you might want to send you funds updated, and why would they update when you're not using fooknapsack? P2SH removes the script-type catch22.Quote The protocol could be extended to support a second "type" of address using DSA, RSA, or ElGamal Integer F_p systems with acceptable security have pubkey+signature sizes which make merkle/lamport keys look more attractive than by comparison with ECC. More importantly, you don't mention the validation speed: My laptop can do 7000 RSA verifies per second vs twice that with secp256k1. They're all based on the effectively the same underlying security assumptions. If we were to support something else out of prudence and paranoia, something orthogonal to the hidden subgroup problem would be good, which is why I would prefer we implement merkle/lamport keys. They are QC hard, have security assumptions unrelated to those of the DLP/factoring asymmetric crypto, and very fast implementations are trivial (unlike DSA/RSA/ElGamal/Ecc). By curve25519 I assume Mike means Ed25519 (curve25519 is for ECDH only). I'm not a big fan of the idea of using it for us (though I'm a big fan of Ed25519 generally): Another fast ECC implementation means another pile of orthogonal highly complicated (probably assembly) ECC validation code that all full nodes will need to have to validate and keep up with the chain. If we accept the idea that there exists mathematical weaknesses unknown to the public which could be found with enough searching in randomly selected curves, which is the reason for wanting an alternative here, then what reason do we have to believe that Ed25519 doesn't suffer from the same or worse? Arguably NSA could have known about such weaknesses and _strengthened_ their choices based on that. Reasoning under uncertainty stinks. The Curve25519 curve also, like our SECP256K1, has some special structure which yields fast implementations... which could ultimately turn out to be a source of weakness. I would go further to suggest this transaction structure optimization: OP_CHECKSIG2 If stack.size() < 2: fail The "public key" is popped. The "signature" is popped. If the size of "public key" <1: fail mode = publickey[0]&63; Modes: 0 SECP256k1 1 COMPRESSED LAMPORT 2-63 NOP If mode is 2-63: return PASS the signature is accepted for forwards compatibility. hashtype = pubkey[0]>>6; Hashtypes: 0: HASH160(pubkey)+SHA256 1: SHA256 2: (Some non-nist cryptographic hashfunction) 3: SHA3-512-256 The remainder of the "public key" [1..n] and the signature value are taken to be hashtype hashes of the mode-relevant public key and signature. The actual public key and signature are not included in the transaction (thus making future proofs over transactions which don't care about the signatures compact) but the data is instead appended to the end of the transaction externally and only included in the transaction hash through the embedded hash. When the public key or signature data is being stored or transmitted, the opcodes in the script could be replaced with placeholder references, so there would be no storage/bandwidth overhead of the indirection, just as there is no overhead from using hashtrees in our blocks. This would also permit, if we were to choose the degrade the Bitcoin security model slightly, us to declare that once a transaction is "XXX deep" in a chain no node will need verify its signature, and so _no_ node would need to store the signatures older than that point. (XXX perhaps being sum POW equal to two months of the highest difficulty ever seen in that chain). Though this security model reduction does have some moral hazard, as it potentially increases the economic benefits of an enormous rewrite attack. Realistically, I think, XXX can be set high enough that such a rewrite attack would be simply infeasible as manual consensus could resolve it. The overhead of longer signature schemes would be pure bandwidth, and not long term storage. Even if we didn't go the full route of drooping old signature data we could use the hash of a block committing to a transaction as the virtual counterparty in a non-interactive cut and choose. E.g. The block hash randomly tells you which 1/2 of the lamport signature data you can drop... the weaking of the signature offset by the huge computational work of producing a block committing to the whole thing. Even vs our current compressed EC signatures this CHECKSIG2 operator could halve long term storage signature size. Title: Re: NSA and ECC Post by: gmaxwell on September 09, 2013, 09:14:21 PM I suppose should mention that I have (now couple year old) half finished implementation of the above, along with lamport that I've been sort of sitting on in case of cryptographic doomsday.
I'd like to go even further with a new checksig and totally replace the sighash type with the ability to include operators inside the pubkey and/or signature which instruct the node to PUSH various values from the transaction to be signed onto a tagged stack, and then the stack is signed instead of the masked transaction. This would allow you to do things like "I sign any transaction that pays >=3 BTC to XYZ -- love, pubkey Q", or even just the equal of SIGHASH_SINGLE_AND_ALSO_OUTPUT_N... but everyone has a pet design, I guess. Title: Re: NSA and ECC Post by: TierNolan on September 09, 2013, 09:43:52 PM Deterministic wallets are presumably also broken if ECC is broken?
Title: Re: NSA and ECC Post by: gmaxwell on September 09, 2013, 09:57:17 PM Deterministic wallets are presumably also broken if ECC is broken? Huh? What do you mean by determinstic wallets there?Title: Re: NSA and ECC Post by: TierNolan on September 09, 2013, 10:03:16 PM Huh? What do you mean by determinstic wallets there? The system that deterministic wallets use is inherently linked to the elliptic curves. If an alternative system is used (or a different curve), then deterministic wallets would no long work. All funds would have to be moved to a new root. Title: Re: NSA and ECC Post by: natb on September 09, 2013, 10:04:16 PM Lamport signatures - cool I never heard of that until today. However, one property (I think) is that a keypair can only be used to sign something once (http://en.wikipedia.org/wiki/Lamport_signature#Signing_the_message (http://en.wikipedia.org/wiki/Lamport_signature#Signing_the_message)). Is this another reason you favor Lamport - to essentially mandate the single use of addresses to enhance privacy?
I suppose should mention that I have (now couple year old) half finished implementation of the above, along with lamport that I've been sort of sitting on in case of cryptographic doomsday. I'd like to go even further with a new checksig and totally replace the sighash type with the ability to include operators inside the pubkey and/or signature which instruct the node to PUSH various values from the transaction to be signed onto a tagged stack, and then the stack is signed instead of the masked transaction. This would allow you to do things like "I sign any transaction that pays >=3 BTC to XYZ -- love, pubkey Q", or even just the equal of SIGHASH_SINGLE_AND_ALSO_OUTPUT_N... but everyone has a pet design, I guess. Title: Re: NSA and ECC Post by: gmaxwell on September 09, 2013, 10:28:45 PM Lamport signatures - cool I never heard of that until today. However, one property (I think) is that a keypair can only be used to sign something once (http://en.wikipedia.org/wiki/Lamport_signature#Signing_the_message). Is this another reason you favor Lamport - to essentially mandate the single use of addresses to enhance privacy? No. While I prefer people behave in privacy maximizing ways, I think mandating it is unrealistic or at least too risky to be worth the benefit. Fortunately we don't have to.What you can do is construct N lamport keys, where N is some reasonable number like say 1024 or 8192 (this is super fast, of course, since it's just hashes)... and then your public key is a hashtree over those lamport public keys. And in your signature you just provide the log2(N) additional hashes to connect the particular key you are using. Alternatively the hashtree could be some other binary tree than a fully populated one, to give you different tradeoffs between reuse amount and signature size. (google: merkle signature scheme) The usage is still finite, but it's not just one use. (and Lamport doesn't become completely insecure if you reuse it, it just starts losing its security... so if you had some extra unsolicited payments past your keys lifetime, it isn't the end of the world.) Of course, the fact that privacy in Bitcoin calls for minimizing address reuse makes the finite lifetime even less of an issue then it would be in some other cases. The system that deterministic wallets are inherently linked to the elliptic curves. "The system that"???.The concept of _deterministic_ wallets is general and works for just about any cryptographic system. Are you talking specifically about derivation using the "public" type-2 (https://bitcointalk.org/index.php?topic=19137.0) homorphism? That works only with cryptosystems based on trapdoor permutation that have certain properties (the permutation must support composition), and obviously a single derivation chain only works with a single cryptosystem. If you're asking about BIP32, BIP32 is specific to SECP256k1 (as its results are well defined), but it supports both public and private derivation. The private derivation could be applied to any cryptosystem, though that wouldn't be BIP32 anymore. The public derivation could be applied to at least any ECDSA cryptosystem. Title: Re: NSA and ECC Post by: Mike Hearn on September 10, 2013, 08:39:28 AM Oops, yes, ed25519, thanks for the correction.
The reason I suggested it is simply that if we assume elliptic curve maths is basically sound modulo some unknown exotic attack that requires very specific parameters to work, then ed25519 is a good answer as it's the same core maths but without any magic NSA-originated numbers. It also doesn't change any performance characteristics of the system for the worse. But I quite agree, postulating solutions to a problem we don't understand (or that may not even exist) is an excellent way to waste time :) Title: Re: NSA and ECC Post by: markm on September 11, 2013, 02:16:33 AM Here is a potentially related potential problem...
If Joy Christian is correct that Bell made a trivial blunder right at the start of his "Bell's Theorem", which has led "everyone" for decades now to think there is something "spooky" as in non-classical (unable to be computed with a Turing machine) going on, then the whole "entanglement" thing is not afterall non-classical, it is simply the topology of space itself, fully classical if you use octonians for the math. (The apparent spookiness is really just the topology of the 7-sphere, in some cases not even needing 7-sphere math just uh hmm 3-sphere is it maybe, whatever, some sphere less than 7.) What this should mean as far as I can see/figure is that if someone, NSA or otherwise, were to believe Joy Christian, then a so called "quantum computer" should be able to be fully simulated (emulated) using classical computing, that is to say, a Turing machine, of classical construction, that is to say, such as the NSA has lots of and even we ourselves have on our desks, in our phones etc. This should mean that it is not necessary to build computers out of non-classical parts in order to run so called quantum algorithms, one should be able to run them on existing computers, such as the NSA has lots of, "simply" by using octonian math and not making the elementary blunder that Bell made at the start of his so called "Bell's Theorem". Might the NSA, or other actors, be using such an approach and simply not bothering to acknowledge Joy Christian's work due to this very implication of that work? -MarkM- EDIT: The "elementary blunder" consists of "losing information" by means of using booleans (yes/no) to represent what in real life real space are actually "bivectors". It thus seems "spooky" that in real life, measuring what are actually "bivectors", you get different results than you get when you compute using booleans where you should be using bivectors. Or something like that anyway. Yes your "did the light turn on yes or no" is a boolean, but, your "polarisation" is not "is it polar yes or no" but rather is a bivector that will reduce to passing the filter yes or no depending on the bivector of the particle/photon and presumably something along the lines of a bivector or something of the filter. Title: Re: NSA and ECC Post by: niko on September 11, 2013, 02:42:20 AM Might the NSA, or other actors, be using such an approach and simply not bothering to acknowledge Joy Christian's work due to this very implication of that work? I've heard rumors that that's all D-Wave has been doing. Title: Re: NSA and ECC Post by: markm on September 11, 2013, 02:48:27 AM Yes, all their little atoms in cold states etc could be mere theater to distract from the fact quantum algorithms can be done using classical computers.
On the other hand, I have also suspected too that it is only very small things like factoring the number 15 that can be done using actual so called quantum computers, because if Christian is right there is no spooky and thus those frozen atoms cannot really do anything we cannot do with octonians aka the topology of the 7-sphere. (That is, maybe 15 is so trivial that it gets solved anyway, even though the whole quantum spookiness thing isn't real thus isn't really how it is doing it.) Thus that it would turn out that the quantum algorithms will not even actually work since they depend upon a spookiness that does not actually exist, or, at best, they will simply be mechanically-faster at doing the octonian math that can perfectly well, albeit slower, be done by Turing machines. I used to think that once we got to more qubits we would find oops they don't behave spooky afterall, quantum algorithms don't actually work. Now though I am also thinking hmm maybe qubits are merely a faster chip, maybe the algorithms will turn out to work, but if so, they should work on simulated (by Turing machines aka classical computers) "quantum" computers too. Just maybe slower. Basically what the frozen atoms would be buying you is analog high-resolution floating-point numbers, in essence obfuscating how many bits your floating point registers actually effectively are. They might even amount to analog floating-point octonian registers. Maybe even more than one such register per atom! Oh and also I guess maybe an analog floating point octonian arithmetic process (agency) too not just passive registers. -MarkM- Title: Re: NSA and ECC Post by: maaku on September 11, 2013, 03:11:12 AM Bell's argument doesn't apply to the many worlds interpretation, which also conveniently resolves all the spooky-action “paradoxes”. But regardless, under no consistent quantum theory is quantum computing with classical parts possible. Joy Christian is a crank.
Title: Re: NSA and ECC Post by: markm on September 11, 2013, 03:17:08 AM Unfortunately there doesn't seem to be any more reason to believe your claim that he is a crank than to believe others who say so.
The part about consistent quantum theory though does seem to offer a lead aka line of enquiry so thanks for that part. Can you point to a proof of that part? -MarkM- EDIT: I have not seen anything in explicit quantum theory math yet that looks like classical computing cannot do it, except the sheer amount of computing it would take and of course the infinite size of the arrays/vectors implied in the event of an infinite number of items being involved in a particular universe or situation. (That is, the math in the abstract tends to be math that theoretically works even for infinite numbers of dimensions, particles etc, but in practice in a given problem the number actually of interest tends not to be infinite.) Title: Re: NSA and ECC Post by: marcus_of_augustus on September 11, 2013, 03:59:25 AM And I realize that while the P-NNNr curves do use a deterministic value their provided seeds are completely fucking implausible. Ah, very interesting! I never bothered to check that (and I bet a lot of other people didn't, either). Wouldn't it be hilarious if Satoshi managed to choose one of the few standard curves that was not backdoored? ... or coincidental beyond implausible. He just used what they always use when they need it to be secure from themselves ... Edit: more than a few reports speak of a "huge breakthrough" circa 2010(?), wonder if that is Riemann or similar or a hardware jump like quantum computer? Title: Re: NSA and ECC Post by: maaku on September 11, 2013, 04:17:28 AM Unfortunately there doesn't seem to be any more reason to believe your claim that he is a crank than to believe others who say so. The part about consistent quantum theory though does seem to offer a lead aka line of enquiry so thanks for that part. Can you point to a proof of that part? -MarkM- EDIT: I have not seen anything in explicit quantum theory math yet that looks like classical computing cannot do it, except the sheer amount of computing it would take and of course the infinite size of the arrays/vectors implied in the event of an infinite number of items being involved in a particular universe or situation. (That is, the math in the abstract tends to be math that theoretically works even for infinite numbers of dimensions, particles etc, but in practice in a given problem the number actually of interest tends not to be infinite.) Um, for credentials I'm a physicist, my undergraduate adviser does his research in quantum computing and I've actually done laboratory experiments demonstrating entanglement and (so-called) non-locality. Is that sufficient? Joy Christian is of that category of people that looks at the data and says 'that can't be right!' and willfully ignores it. You can verify that something apparently spooky is going on with relatively simple experiments that have been replicated many, many times. It's like rejecting Einstein because the twin paradox is just too weird a concept. It doesn't stop the atom bomb from being possible. Anyway I only bring up many worlds interpretation (MWI) because it's a simpler meta-theory that explains all observed quantum phenominon without resorting to the wave function collapse (and therefore without the EPR paradox of non-locality), or the privileged observer frame of reference. It still has all that quantum weirdness, but with very simple, easy to understand (albeit mind-blowing) explanation. The best long-winded introduction to MWI is this FAQ (http://www.anthropic-principle.com/preprints/manyworlds.html). In a couple of decades when we have atomic-scale reversible computers we'll be able to do actual experiments that will tell once and for all if the wave collapse is real or merely a belief resulting from our anthropic bias. Regarding quantum computation, you can simulate it on a classical computer, sure. But then you only get a simulated “speedup”. It would definitely not be any faster than classical computation. Title: Re: NSA and ECC Post by: markm on September 11, 2013, 06:01:50 AM Thanks.
Supposedly the topology of the 7-sphere reproduces all of the "spooky" results, and it does not require multiple worlds to do so, merely that this one world has 7-sphere topology. So he is not looking at the results and claiming they cannot be right, he is looking at the theories as to how/why they are right and finding a simpler theory. Basically just wondering how the results can be right and finding a relatively simple mathematical explanation of how they come about, without resorting to multiple worlds. That does not seem particularly - if at all - "cranky" to me. I do agree though that hardware that naturally consults the topology of space directly is likely to be faster than software that simulates such space. I am surprised that you agree you can simulate quantum computation on classical computers at all. Previously it had seemed the whole point with quantum computation was that it took advantage of spookiness that does not and cannot exist in classical. That classical computing could not even obtain the same results. That was part of what was spooky. "Look at this truth table! It is inconsistent! No way classical space could behave like that!" He is basically pointing out (or claiming, anyway, it seems) that, actually, classical 7-sphere space behaves exactly like that. -MarkM- Title: Re: NSA and ECC Post by: keystroke on September 11, 2013, 06:21:31 AM Anyway I only bring up many worlds interpretation (MWI) because it's a simpler meta-theory that explains all observed quantum phenominon without resorting to the wave function collapse (and therefore without the EPR paradox of non-locality), or the privileged observer frame of reference. It still has all that quantum weirdness, but with very simple, easy to understand (albeit mind-blowing) explanation. The best long-winded introduction to MWI is this FAQ (http://www.anthropic-principle.com/preprints/manyworlds.html). In a couple of decades when we have atomic-scale reversible computers we'll be able to do actual experiments that will tell once and for all if the wave collapse is real or merely a belief resulting from our anthropic bias. How would reversible computing allow us to determine if the wave function collapses? Unfortunately I don't have access to Deutsch's works. (Sorry to derail the thread - maybe this can be taken elsewhere. Getting Lamport signatures in bitcoin looks like a very important safeguard.) Title: Re: NSA and ECC Post by: markm on September 11, 2013, 06:40:08 AM If you could reverse the arrow of time maybe it is as simple as having a three-dimensional past and a three-dimensional future and a one-dimensional arrow of time, adding up to seven dimensions?
if you only consider three dimensional objects, of course, and relate past and future with a one-dimensional arrow of time. Things might have more dimensions than that of course but the layman's versions of Bell's paradox typically are looking at a simple macroscopic 3-D black box in the past and similarly a 3-D macroscopic black box in the present or future so maybe 7 dimensions is all you need to explain the experiment. (Q: "How do we get from this 3-D situation to that 3-D situation?" A: "That adds up to 7-D so we use the 7-sphere.") -MarkM- Title: Re: NSA and ECC Post by: maaku on September 11, 2013, 07:36:47 AM Christian's math doesn't work out:
http://arxiv.org/abs/1109.0535 You can certainly simulate a quantum computer, just as you can simulate the core of a neutron star without actually creating one. There's nothing magical about a quantum computer. It's just capable of running an amazing number of calculations in parallel - literally in parallel if you subscribe to MWI. You can simulate that by running the calculations in series on a classical computer. Of course for the kinds of problems people usually want a quantum computer for, that simulation would take longer than the lifetime of the universe. But you could do it, in principle. There's nothing magical about quantum computation. How would reversible computing allow us to determine if the wave function collapses? It's in the FAQ that I linked to, but in summary you run a quantum computation requiring a wave function collapse forward and reversibly measure the result. If the wave function collapse is real then it would be resolved to a single state. When you run it in reverse the wave function maintains that single state. If, on the other hand, the MWI meta-theory is correct then the reversibility keeps the wave function coherent and it 'collapses' again as you reverse the operation possibly ending up in a different state. Of course there is no collapse, it's just an artifact of us ending up in one of many previously coherent worlds. Title: Re: NSA and ECC Post by: markm on September 11, 2013, 08:22:37 AM Christian's math doesn't work out: http://arxiv.org/abs/1109.0535 Yeah I have read that too, and huge threads where various such guys argue about it all. If I recall correctly Christian already shot that one down though I don't have a link offhand as to exactly where he did so and don't recall exactly what misconception(s) that specific "refutation" of Christian is (according to Christian) making. Sites like that and online papers in general should have "pro" and "con" links on them so you can click through from any paper either to others that claim it is correct or to others that claim it is not. (Maybe a citations-mapping site that colours citations according to whether the cited paper is being confirmed, or merely assumed correct (taken as an axiom?), or refuted would be useful?) Since I still have no good grounds to determine which is right, I so far have to wait for the macroscopic splitting weighted balls experiment to be done that Christian proposes that will discover whether the exact same inequalities are found using macroscopic objects (particles) instead of subatomic ones, or someone beats the computer program challenge that is out there linked from the long thread in which those guys all argue with each other. I did not find the computer program challenge reasonable though myself because it defines in advance the type of variables you have to use, like real numbers, integers, whereas it seemed to me from Christian's arguments that one should use octonians. It is partly because of the computer program challenge that I still find it weird that you so blithely accept that a classical computer can reproduce Bell's inequality and similar inequalities, as the argument seems to be that unless Christian is right no such program can be written/executed; and similarly, the fact that no one can (aka has so far) produced such a computer-program Christian is proven wrong by the proven fact that such a program has (so far) not been created. There is a reward of $10000 or some such thing for such a computer program so if you agree one can be written could it be commissioned for $10000 or less? It might even have been $100,000 I am not sure offhand would have to track it down somehow (google-fu maybe). -MarkM- Title: Re: NSA and ECC Post by: maaku on September 11, 2013, 08:36:29 AM I don't even know how to respond to that. Quantum physics is governed by a wave equation. Quantum computers are just a neat arrangement of coherent waves and barriers that has computationally interesting properties. You simulate it by solving the wave equation, which is just math. How do you think Bell came up with his inequality? He solved a 'simulation' by hand, with pencil and paper. If someone actually has money on the line, then maybe you are misinterpreting what the challenge is?
Anyway, we're wandering deeply offtopic. Title: Re: NSA and ECC Post by: markm on September 11, 2013, 08:44:44 AM I agree this isn't really the thread for this.
But he didn't run the simulation by hand and get the experimental results, that is the point. The inequality is between what one ought to get according to logic and what one actually gets in the experiments. -MarkM- EDIT: This thread inspired me to go post in my blog: http://markmetson.blogspot.ca/2013/09/the-lure-of-physics-raises-its.html Title: Re: NSA and ECC Post by: runeks on September 11, 2013, 08:11:16 PM I suppose should mention that I have (now couple year old) half finished implementation of the above, along with lamport that I've been sort of sitting on in case of cryptographic doomsday. How large are Lamport signatures with security equal to 256 bit ECDSA?Also, would there be any reason not to get this into Bitcoin right now? Instead of waiting for cryptography doomsday? The addition of new opcodes shouldn't impact the security the existing ones, so as far as I can see we're only adding an option for the paranoid. But maybe that's the exact issue. Without making this new scheme the default one, there's really no reason to add it now, instead of waiting to see if secp256k1 is compromised and then adding it. If no one is using it it won't really be tested anyway. Title: Re: NSA and ECC Post by: BurtW on September 11, 2013, 10:16:36 PM This might be Mr Solinas' email address: jasolin@orion.ncsc.mil We could ask him if how the curves were generated is reproducible. Maybe better ask first if the generation methodology is classified. Waiting for a response. Title: Re: NSA and ECC Post by: fpgaminer on September 12, 2013, 12:20:35 AM Quote How large are Lamport signatures with security equal to 256 bit ECDSA? 256-bit ECDSA has a security strength of 128-bits under classical computing. Under Lamport, that would require signatures of length 128 * 128 bits, which is 2 KB. The public keys would be 4 KB. (Source (http://en.wikipedia.org/wiki/Lamport_signature#Mathematical_description))To have an estimated security strength of 128-bits under quantum computing, Lamport signatures would be 256 * 256, which is 8KB. (Source (http://en.wikipedia.org/wiki/Lamport_signature#Security_parameters)) Quote Also, would there be any reason not to get this into Bitcoin right now? I would say the size of the signatures would be one reason. The inability to re-use them being another. What if you received bitcoins to a Lamport derived address after you already spent from it? Now you can't spend the extra bitcoins.Also, are Lamport signatures going to offer significantly more protection than one-time ECDSA with pay-to-hash? Using ECDSA that way, even if ECDSA is broken, would only be weak for the 10 minutes or so before a transaction gets into a block. Can we reasonably foresee a break in ECDSA so profound that it can be performed in under 10 minutes? Seems like the real issue is that broken ECDSA will break BIP32, our means of allowing convenient one-time-addresses. And BIP32 can't be applied to Lamport, so Lamport doesn't help here either. Title: Re: NSA and ECC Post by: runeks on September 12, 2013, 01:46:15 AM Quote How large are Lamport signatures with security equal to 256 bit ECDSA? 256-bit ECDSA has a security strength of 128-bits under classical computing. Under Lamport, that would require signatures of length 128 * 128 bits, which is 2 KB. The public keys would be 4 KB. (Source (http://en.wikipedia.org/wiki/Lamport_signature#Mathematical_description))To have an estimated security strength of 128-bits under quantum computing, Lamport signatures would be 256 * 256, which is 8KB. (Source (http://en.wikipedia.org/wiki/Lamport_signature#Security_parameters)) What you can do is construct N lamport keys, where N is some reasonable number like say 1024 or 8192 (this is super fast, of course, since it's just hashes)... and then your public key is a hashtree over those lamport public keys. And in your signature you just provide the log2(N) additional hashes to connect the particular key you are using. Alternatively the hashtree could be some other binary tree than a fully populated one, to give you different tradeoffs between reuse amount and signature size. (google: merkle signature scheme) Quote Quote Also, would there be any reason not to get this into Bitcoin right now? I would say the size of the signatures would be one reason. The inability to re-use them being another. What if you received bitcoins to a Lamport derived address after you already spent from it? Now you can't spend the extra bitcoins.Quote Also, are Lamport signatures going to offer significantly more protection than one-time ECDSA with pay-to-hash? Using ECDSA that way, even if ECDSA is broken, would only be weak for the 10 minutes or so before a transaction gets into a block. Can we reasonably foresee a break in ECDSA so profound that it can be performed in under 10 minutes? That is a good point. I'd be inclined to say it's not worth it yet.Title: Re: NSA and ECC Post by: superduh on September 12, 2013, 04:46:02 AM sorry, but, what's the consensus
Title: Re: NSA and ECC Post by: gmaxwell on September 12, 2013, 05:12:12 AM Quote How large are Lamport signatures with security equal to 256 bit ECDSA? 256-bit ECDSA has a security strength of 128-bits under classical computing. Under Lamport, that would require signatures of length 128 * 128 bits, which is 2 KB. The public keys would be 4 KB. (Source (http://en.wikipedia.org/wiki/Lamport_signature#Mathematical_description))To have an estimated security strength of 128-bits under quantum computing, Lamport signatures would be 256 * 256, which is 8KB. (Source (http://en.wikipedia.org/wiki/Lamport_signature#Security_parameters)) There is no severe reuse issue, for a very minor increase in size you use a merkle signature scheme, where you have a tree of lamport keys. This significantly reduces the reuse problem. In the context of Bitcoin some reuse would also not be completely fatal. You could very nearly implement lamport signatures in our existing script with no special functionality at all, we're basically only missing code to push the raw data-to-be-signed onto the stack... though doing it that way wouldn't get you public key compression. I'm not sure if we should implement such things prophylacticly: It would be great to have an already deployed answer to "OMG WHAT ABOUT QCs?!" or "OMG WHAT IF NSA ECDSA?!"... but I suspect a lot of people who would ask such things aren't really looking for answers. Our common infrastructure is also very sensitive to size— my "structure it so you can forget old signatures" is a major security model change which might have severe economic consequences in the long run... and additional block-chain bloat absolutely would have consequences. So ::shrugs::. Title: Re: NSA and ECC Post by: Etlase2 on September 12, 2013, 05:15:27 AM Using ECDSA that way, even if ECDSA is broken, would only be weak for the 10 minutes or so before a transaction gets into a block. Can we reasonably foresee a break in ECDSA so profound that it can be performed in under 10 minutes? It depends on how ECDSA is broken. It also depends on how ECDSA is used. While using pubkeys only once is "recommended", it is certainly not a requirement, and it is not possible to predict how ECDSA will be used by the bitcoin protocol in the future. But if discrete logarithm problem over elliptic curves stops being "hard", only the pubkeys are necessary, and they will probably be broken at break-neck speed. If it is a weakness with the signatures revealing information (much more likely), it will take time, but reused pubkeys are at serious risk. Quote I would say the size of the signatures would be one reason. The inability to re-use them being another. Well Merkle-Lamport constructions are probably what is of interest. On the bright side, the pubkey is only n bits where n is the security level. However, there is research into merkle + one-time sig schemes with smaller signatures. "On the Security of the Winternitz One-Time Signature Scheme" by Buchmann et al shows signature sizes of about 800 bytes for 129-bit effective security level at a Winternitz parameter of 16 (increasing it raises the difficulty of creating signatures, but makes the signatures smaller and weaker, I don't know the exact tradeoffs). 800 bytes is well within reason for a QC-resistant signature algo (although it might have to be more depending on how many qubits are available to crack hash algos). It is still a significant hurdle though for world-wide use, and will obviously increase the costs of running the network significantly. Title: Re: NSA and ECC Post by: BurtW on September 12, 2013, 04:10:40 PM While everyone is gathered here I have a quick easy question. I always assumed that the private keys came from the finite field defined by the parameter p specified here (and secg of course):
https://en.bitcoin.it/wiki/Secp256k1 However, this wiki page states that the valid private keys are specified by the parameter n: https://en.bitcoin.it/wiki/Private_key#Range_of_valid_private_keys Either I need to be fixed (ouch!) or the wiki needs to be fixed. Title: Re: NSA and ECC Post by: jackjack on September 12, 2013, 04:17:05 PM While everyone is gathered here I have a quick easy question. I always assumed that the private keys came from the finite field defined by the parameter p specified here (and secg of course): https://en.bitcoin.it/wiki/Secp256k1 However, this wiki page states that the valid private keys are specified by the parameter n: https://en.bitcoin.it/wiki/Private_key#Range_of_valid_private_keys Either I need to be fixed (ouch!) or the wiki needs to be fixed. The correct number is n as G^(n+1) = G Title: Re: NSA and ECC Post by: BurtW on September 12, 2013, 04:47:22 PM While everyone is gathered here I have a quick easy question. I always assumed that the private keys came from the finite field defined by the parameter p specified here (and secg of course): https://en.bitcoin.it/wiki/Secp256k1 However, this wiki page states that the valid private keys are specified by the parameter n: https://en.bitcoin.it/wiki/Private_key#Range_of_valid_private_keys Either I need to be fixed (ouch!) or the wiki needs to be fixed. The correct number is n as G^(n+1) = G Title: Re: NSA and ECC Post by: NewLiberty on September 12, 2013, 07:02:56 PM This might be Mr Solinas' email address: jasolin@orion.ncsc.mil We could ask him if how the curves were generated is reproducible. Maybe better ask first if the generation methodology is classified. Waiting for a response. Thank you for this. Title: Re: NSA and ECC Post by: piotr_n on September 12, 2013, 07:12:46 PM This might be Mr Solinas' email address: jasolin@orion.ncsc.mil We could ask him if how the curves were generated is reproducible. Maybe better ask first if the generation methodology is classified. Waiting for a response. Thank you for this. Who's in? :) Title: Re: NSA and ECC Post by: gmaxwell on September 12, 2013, 07:17:27 PM Presumably, since it was government work, it should be possible to FOIA any records they have relating to the procedures they used to generate those ECC parameters.
If no secret information was used to select them, e.g. strengthening or weakening the selection there should be no reason for the result to be classified. If we don't get a response with a casual request we could try the FOIA route. Might be fun. (As an aside: I think that there is weak evidence that they didn't use the selection to strengthen the curves as there are criteria by which these curves are considered weaker (see the Brainpool curves RFC for the extra criteria they used)) Title: Re: NSA and ECC Post by: balanghai on September 13, 2013, 03:18:54 PM It would be cool if the engineers of the agency will mine altcoins for fun! :P
Title: Re: NSA and ECC Post by: marcus_of_augustus on September 14, 2013, 03:50:07 AM It would be cool if the engineers of the agency will mine altcoins for fun! :P Would be even cooler if they just fucked off and died and left the rest of us alone to do the right thing .... just saying. Title: Re: NSA and ECC Post by: BurtW on September 15, 2013, 11:18:38 AM Here is Jerry's response:
Quote Hello Burt, I have emailed all three authors.I have looked at the SECG standard you pointed to. The secp256k1 curve is not one of the NIST curves, and I'm afraid I had nothing to do with it. It uses the technology described in the Crypto 2001 paper by Gallant, Lambert, and Vanstone (https://www.iacr.org/archive/crypto2001/21390189.pdf). Since the authors were all affiliated with Certicom, and Certicom was the main partner in the SECG consortium, I'm guessing the Certicom folks came up with that curve. I would suggest getting in touch with one of them for more info on where the particular parameters came from. Regards, -- Jerry S. Title: Re: NSA and ECC Post by: BurtW on September 15, 2013, 12:02:07 PM From the referenced paper I would expect our curve to at least satisfy these criteria:
Quote 5 Security Considerations Elliptic curves having effciently-computable endomorphisms should be regarded as "special" elliptic curves. Using "special" instances of cryptographic schemes is sometimes done for effciency reasons (for example the use of low encryption- exponent RSA, or the use of small subgroups hidden in a larger group as with DSA). However in any instance of a cryptographic scheme, there is always the chance that an attack will be forthcoming that applies to the special instance and signifcantly weakens the security. Such is the case here as well. When selecting an elliptic curve E over Fq for cryptographic use, one must ensure that the order #E(Fq) of the elliptic curve is divisible by a large prime number n (say n >= 2160) in order to prevent the Pohlig-Hellman [22] and Pol- lard's rho [23, 21] attacks. In addition, one must ensure that #E(Fq) != q in order to prevent the Semaev-Satoh-Araki-Smart attack [26, 25, 28], and that n does not divide qi - 1 for all 1 <= i <= 20 in order to prevent the Weil pairing [16] and Tate pairing attacks [8]. Given a curve satisfying these conditions, there is no attack known that signifcantly reduces the time required to compute elliptic curve discrete logarithms. Many such curves having effcient endomorphisms ex- ist and hence appear suitable for cryptographic use. One attack on the elliptic curve discrete logarithm problem on such curves is along the lines of [9] and [34]. The application of such ideas does not reduce the time to compute a logarithm by more than a small factor. The number of curves for which this technique applies seems to be reasonably large. For instance, one of the Examples 3, 4, 5 and 6 provide a candidate for most primes p. Title: Re: NSA and ECC Post by: BurtW on September 15, 2013, 12:27:05 PM 1) I believe that #E(Fq) of the elliptic curve is divisible by a large prime
number n (say n >= 2160) is true 2) I believe that #E(Fq) != q is true [#E(Fp) != p in our case] 3) n does not divide qi - 1 for all 1 <= i <= 20 We would need to write a small program to verify the last one. Title: Re: NSA and ECC Post by: jackjack on September 15, 2013, 12:40:16 PM What is n?
Title: Re: NSA and ECC Post by: BurtW on September 15, 2013, 12:51:35 PM q = p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 Title: Re: NSA and ECC Post by: jackjack on September 15, 2013, 12:57:40 PM They say
Quote the order #E(Fq) of the elliptic curve is divisible by a large prime number n (say n >= 2^160) So their n (random prime number) isn't our n (order of the EC) (?)With p=FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F and n=FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 Code: p^1 - 1 % n = 000000000000000000000000000000014551231950b75fc4402da1722fc9baed Title: Re: NSA and ECC Post by: BurtW on September 15, 2013, 01:13:47 PM I believe the order #E(Fp) of our elliptic curve n is prime and is in fact their n.
I think this is also validated by the fact that h = 1. But hey, I am just treading water here... Title: Re: NSA and ECC Post by: NewLiberty on September 15, 2013, 02:00:34 PM Hmm I wonder how many colours of coloured coin it takes to [something something] a blockchain? ;) :D (You only need four whatzits to build a DNA strand? Hmm....) Think like the game "sprouts (http://en.wikipedia.org/wiki/Sprouts_%28game%29)". (And maybe read Peirs Anthony's "Macroscope" while you're at it.) One point is a point, two is a line, three is a circle. If the fourth is inside the circle, it is surrounded, no luck there. If the fourth is outside the circle, how you gonna connect it to the other three without surrounding any of them? -MarkM- Congratulations to your child-self. The personal implications of your avatar icon are suddenly more manifold. ;) Title: Re: NSA and ECC Post by: fpgaminer on September 15, 2013, 10:15:40 PM Quote I believe the order #E(Fp) of our elliptic curve n is prime and is in fact their n. To be specific, n in BurtW's quote is any prime number that divides the order of the elliptic group. In our case, the order of the secp256k1 group is prime, which means n can only be the order of the elliptic group (convenient!).I think this is also validated by the fact that h = 1. Given that our elliptic group is of prime order, we know a few things. There are no subgroups. It's cyclic. It's abelian. To the best of my knowledge, that also implies that we can pick any element of the group, except the identity element, to be our generator. Which makes me wonder how secp256k1's generator was picked. I don't yet know what restrictions one must apply to the generator. I can only assume it doesn't matter ... By the way, I ran a little experiment. Given our finite field, and setting a to 0, 7 is the first (counting from 0) value for b that results in a prime order elliptic group. I don't understand GLV well enough to know what restrictions it places on a and b, but if we have to pick a curve where a is 0, it seems like b being 7 would be a logical choice (again, given our finite field). Title: Re: NSA and ECC Post by: BurtW on September 18, 2013, 07:46:32 PM This is the reply I got form Dan Brown the current SECG chair:
Quote Hi Burt, Rob forwarded your email to me. I am the current SECG chair, so I will try to provide a partial answer. I did not know that BitCoin is using secp256k1. Indeed, I am surprised to see anybody use secp256k1 instead of secp256r1. With my SECG chair hat on, I am pleased because this curve is a pure SECG curve, not a NIST curve (but see * below). Minor aside: SECG updated SEC2 in 2010. The curve secp256k1 is now in Section 2.4, which is smaller because SECG removed the very small curves. I was not involved in the parameter selection for secp256k1, and may not have even been a Certicom employee at the time of secp256k1 parameter selection. I am going to assume that you are mainly concerned about a potential backdoor, given the coincidence of your query with certain news coverage. I will attempt to address this concern mainly by looking directly SEC2 document and parameters. 1. The defining Weierstrass coefficients (a,b) of the curve are (0,7). The SEC2 document says, in Section 2.1, “The recommended parameters associated with a Koblitz curve were chosen by repeatedly selecting parameters admitting an efficiently computable endomorphism until a prime order curve was found”. Furthermore, I see that the small values 0 and 7 are certainly nothing-up-my-sleeve values. More precisely, they cannot be the result of a malicious exhaustive search of curve selection until the curve lands in a weak class. So, the only risk is that the special class, with small coefficient and efficient endomorphism is somehow weak. I am not aware of any such weakness. Indeed, I highly doubt such a weakness, at least in the ECDLP: it would constitute a major breakthrough in ECDLP. Also, some ECC theorists have established the equivalence ECDLP between curves of the same order, via something called isogenies. I am not expert in that area, but it may imply that mere fact that the curve coefficients are small is insufficient to constitute a weak class of ECDLP. 2. The defining field size p seems to be a 256-bit prime of the special form 2^256-s where s is small. This form is for efficiency. I am not sure why this particular value of s is chosen, because I expect that smaller s could be found. Nevertheless, there does not seem to be too much wiggle room in this choice of s, because s itself also has a special form: s = 2^32 + t, where t < 1024. I would not be surprised if s was the smallest value of this form, but I did not check. In any case, there are no known weak classes of prime order field for elliptic curves. 3. The base point G is something I cannot explain, but the general understanding, at the time and still now, is that the base point G cannot contain a backdoor in the main problem underlying ECC, namely ECDLP and ECDHP. Indeed, random self-reducibility applies to prove that the choice of G is irrelevant for most versions of these problems. Some cryptographic schemes, including ECDSA, seem to depend mildly on some other problems, in which the choice of G may be more relevant. In particular, the ECDSA verification of a signature (r,s) includes a check that r is not zero. If this check is dropped, then there is a possibility that party who chose G can have chosen G in such that to make some signature (0,s) valid for a particular message m. (For details and examples, see my chapter in Advances in Cryptology II, or my paper “Generic Groups, Collisiion Resistance, and ECDSA”, or my IACR eprint “The One-Up Problem for ECDSA”.) I strongly doubt that G is malicious, because these properties were not widely known at the time, and the adversary seems to have little to gain, the verifier has to be faulty. 4. Rob Lambert and John Goyo were present at the time Certicom generated the secp256k1 parameters, but were not directly involved either. John Goyo recalls that two former employees generated the domain parameters. In particular, no external organization, including any that some now asperse with backdoor insertion, generated the parameters. We will continue to investigate our records and archives. I hope that the four points above address your main concerns, despite them not fully answering your questions. Feel free to request further clarification, but, unfortunately, I am not sure if we have maintained all the archives. (*) With my SECG chair hat off now, I recognize some validity of the following argument: the NIST curves have received more scrutiny than the other SECG curves, because the prominence of NIST created a greater incentive to study these curves. Putting my SECG chair back on, a mild counterargument to the latter argument is that: none of the known weak classes of curves resulted by targeting particular parameters. Rather they are results from basic research on ECC. Best regards, Dan Title: Re: NSA and ECC Post by: Etlase2 on September 18, 2013, 09:27:42 PM Very interesting, thanks for that Burt.
Title: Re: NSA and ECC Post by: Carlton Banks on September 18, 2013, 09:29:01 PM This is the reply I got form Dan Brown the current SECG chair: Quote Hi Burt, [...] I hope that the four points above address your main concerns, despite them not fully answering your questions. Feel free to request further clarification, but, unfortunately, I am not sure if we have maintained all the archives. Technical details aside (not qualified to comment), this comes across as an unambiguous "yes, no, ....maybe". Well, I suppose he could've skimped on information, and he certainly did not do that. But lines like the bolded text are concerning; you'd think they would be pretty meticulous, given that any rogue mathematician who deliberately did not disclose or document flaws and promptly moved to China for a "quiet retirement" could be a candidate for the "disposition matrix" :D. Bitcoin Foundation should be tendering research grants (or perhaps more appropriately commissioning long term studies) specifically to attract cryptographers of the highest calibre. At least in the more medium term that is. I fail to see how contributing mathematical prowess to the fundamental substance of what could morph into the 21st century monetary system couldn't attract the right talent. And the average Bitcoiner has to pay how much to join, only to discover this is not happening for whatever reason? This should be a serious endeavour, and their current focus is a political meat shield. [/cynical bullishness] Title: Re: NSA and ECC Post by: BurtW on September 18, 2013, 11:04:22 PM Technical details aside (not qualified to comment), this comes across as an unambiguous "yes, no, ....maybe". I think he did a great job answering our questions to the best of his ability under the circumstances (people who actually did the work are no longer with SECG. Bitcoin Foundation should be tendering research grants (or perhaps more appropriately commissioning long term studies) specifically to attract cryptographers of the highest calibre. I am totally impressed by the calibre of the math, programing and cryptographers we have already. Just read this very thread.I am very satisfied with his answers. The only thing left is to find out (if we can) is exactly how the random parameters were selected. I am waiting for responses to my emails on that subject. Title: Re: NSA and ECC Post by: Carlton Banks on September 18, 2013, 11:25:46 PM Technical details aside (not qualified to comment), this comes across as an unambiguous "yes, no, ....maybe". I think he did a great job answering our questions to the best of his ability under the circumstances (people who actually did the work are no longer with SECG. Bitcoin Foundation should be tendering research grants (or perhaps more appropriately commissioning long term studies) specifically to attract cryptographers of the highest calibre. I am totally impressed by the calibre of the math, programing and cryptographers we have already. Just read this very thread.I am very satisfied with his answers. The only thing left is to find out (if we can) is exactly how the random parameters were selected. I am waiting for responses to my emails on that subject. I am similarly more than impressed with the abilities of our current development team. What I'm suggesting is a dedicated team for long-term analysis and theoretical work, not only accomplished software developers that have well honed cryptography knowledge who apply pre-existing work to this project. You'll notice if you look at the SCIP thread that one well seasoned developer admits to being out of his depth at a certain stage, and he's certainly a capable developer. The answers he gives can be interpreted as given, but could also be a well devised evasion tactic, although there is no way of knowing for certain at this stage. I commend that you did this, despite any misgivings. As I say, it could be that he is being totally upfront and honest, so whatever the eventual assessment, you have done us all a service. Title: Re: NSA and ECC Post by: TierNolan on September 19, 2013, 08:42:36 AM I am very satisfied with his answers. The only thing left is to find out (if we can) is exactly how the random parameters were selected. I did a quick check on this assumption Quote Nevertheless, there does not seem to be too much wiggle room in this choice of s, because s itself also has a special form: s = 2^32 + t, where t < 1024. I would not be surprised if s was the smallest value of this form, but I did not check. The test code finds all primes of the form p = 2^256 - 2^32 - t where t < 1024. Code: import java.math.BigInteger; The result is Code: fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffef9 (t = 263) The prime for t = 977 is the one that was selected for the curve. It is the highest t that is lower than 1024. Title: Re: NSA and ECC Post by: piotr_n on September 19, 2013, 09:42:49 AM The explanations are exactly like the one I had expected to be. I am quite sure you would receive a very similar ones from NIST.
It all can all be wrapped in one sentence: Even though we are a highly professional and experienced scientists, who were assigned with a formal task to select a proper constants that would assure a security of the encryption, we have no idea how and why the specific constants were selected, but we are almost certain that none of them can weaken EC security, therefore you have nothing to worry about. Professional scientists like hell :) Title: Re: NSA and ECC Post by: BurtW on September 19, 2013, 03:58:17 PM piotr_n:
Your post is totally unfair and uncalled for. Having been a contributing member of several technical specifications I can assure you that his email rings true. Just try to find out how any decision was made on any technical specification and you will find that most of the decisions and grunt work are done by emails, phone calls, hallway conversations, conversations over meals during face to face meetings, etc. Unless you actually participated in the decision the reason for most technical decisions in all the technical specifications I have worked on would be almost impossible to find. For example, one time we were having a problem where the disk drive I was designing would not properly work in master/slave mode with a competitor’s disk drive. I called up the competitor’s lead architect and we re-designed the master/slave protocol right there, on the spot, over the phone. Our two companies implemented it and it eventually found its way into the ATA specification and is still there to this day. The fact that the prime selected has the highest possible value of t lower than 1024 looks to be the answer to that particular question – unless we can find the person who actually selected the prime number, or the people present in the meeting that day when he presented the number and explained his selection to them. This guy did not need to take the time to answer my query. He did not know me from Adam. If the situation was as you described he would have simply not answered my email and been done with it. TierNolan: Thanks for that! Great work! Title: Re: NSA and ECC Post by: piotr_n on September 19, 2013, 04:39:07 PM Sorry BurtW, but I totally disagree.
What is the point of creating a standard if you cannot justify the values you chose for it, nor you are able to reproduce a path that was taken to calculate them? This is not a science! This is a sloppy designing at best. And at worst? Oh, let's hope not... :) Title: Re: NSA and ECC Post by: NewLiberty on September 19, 2013, 05:08:06 PM Sorry BurtW, but I totally disagree. What is the point of creating a standard if you cannot justify the values you chose for it, nor you are able to reproduce a path that was taken to calculate them? This is not a science! This is a sloppy designing at best. And at worst? Oh, let's hope not... :) His answer appears honest (at least so far as we've been able to check), rather than arguing from authority as you claimed. He admits what he doesn't know, and why. He made reasonable guesses at some points and stated they were such. I agree that the answer is not perfect nor complete, but neither was your characterization of it accurate. Keep in mind that it didn't take a FOIA request to get this, it was given freely and without lawyers in a friendly, informal and collegian manner. It might look different were it a submission to a peer reviewed journal and meant to withstand critical review, instead it was a VERY swift and candid response at no benefit to himself. Gratitude is warranted. What you are seeking (a justification of values along with the path taken to calculate) may yet come, but that will take them some research and effort. Just our asking for this may stimulate such an effort. We are helping to guide them to do more meaningful work in light of the current reports and questions raised. Title: Re: NSA and ECC Post by: piotr_n on September 19, 2013, 05:21:10 PM I think you guys got a wrong idea.
I was not criticizing the guy who wrote that email - not at all. In fact I also find him as a very nice and sincere person who is trying to help. Still, it does not help us at all, does it? So let me quote again what I believe all the other answers concerning this issue will be about: Quote Even though we are a highly professional and experienced scientists, who were assigned with a formal task to select a proper constants that would assure a security of the encryption, we have no idea how and why the specific constants were selected, but we are almost certain that none of them can weaken EC security, therefore you have nothing to worry about. Making the sarcastic comment, my only point was: if anyone will manage to get an answer that goes beyond what I had already figured, then we can talk.. I will be more than happy to turn out as an asshole again, if this is the price for finding out where these values come from. And if we don't ever get to know how the values in question were chosen - well, feel free to perceive me as an asshole, anyway. :) Title: Re: NSA and ECC Post by: BurtW on September 19, 2013, 05:56:11 PM Does anyone have a copy of ANSI X9.62 I can borrow? Or does anyone know of a free link? I would like to read it but don't really want to shell out the $100 for it.
Have not read it yet but this looks to be interesting: http://cs.ucsb.edu/~koc/ccs130h/notes/ecdsa-cert.pdf Part: Quote The Elliptic Curve Digital Signature Algorithm (ECDSA) is the elliptic curve analogue of the DSA. ECDSA was first proposed in 1992 by Scott Vanstone [108] in response to NIST’s (National Institute of Standards and Technology) request for public comments on their first proposal for DSS. It was accepted in 1998 as an ISO (International Standards Organization) standard (ISO 14888-3), accepted in 1999 as an ANSI (American National Standards Institute) standard (ANSI X9.62), and accepted in 2000 as an IEEE (Institute of Electrical and Electronics Engineers) standard (IEEE 1363-2000) and a FIPS standard (FIPS 186-2). It is also under consideration for inclusion in some other ISO standards. In this paper, we describe the ANSI X9.62 ECDSA, present rationale for some of the design decisions, and discuss related security, implementation, and interoperability issues. Since ANSI X9.62 was accepted into IEEE as 1363-2000 I can probably get it there since I am a member. Title: Re: NSA and ECC Post by: BurtW on September 19, 2013, 06:07:24 PM Here is a suggestion from Dan on the seeds for the random curves: Convert them to ASCII and see what pops!
Quote Hmm, I just checked some of the seeds for the non-NIST random curves in SECG. I noticed that some of the seeds look similar to each other, and had very non-random looking hex representations. So, I just converted them to ASCII, and noticed that a large middle portion of some of the seeds contain the string “MinghuaQu”, which is the name of one of the inventors of MQV, and the person who was generating the seeds. I would not be surprised if the remainder of the seeds also had some meaning, with just a little part left for the necessary searching. If so, then the curves are really nothing-up-sleeve type values. Unfortunately, most of these curves may be too small by today’s recommendations. Best regards, Dan It would be fun to convert all the seeds we can find, especially the seeds used for the curves we are interested in, to ASCII and see what is there. Title: Re: NSA and ECC Post by: maaku on September 19, 2013, 06:27:54 PM Anyone have contact info for MinghuaQu ?
Title: Re: NSA and ECC Post by: gmaxwell on September 19, 2013, 06:44:50 PM I'd already tried hextoasciiing the p256r curve's seed, before ever commenting on it, no such joy. (I'd also hoped to find a similar answer to our generator, but no such question, as the message said though— the generator isn't a known cause for concern, as you can generally convert numbers relative to one generator relative to another trivially. I'd though perhaps the generator would result in low hamming weight in the multiplies, allowing some stems to be avoided but it seems not)
Title: Re: NSA and ECC Post by: niko on September 19, 2013, 08:17:18 PM Keep in mind that it didn't take a FOIA request to get this, it was given freely and without lawyers in a friendly, informal and collegian manner. FOIA only applies to the US government agencies, it is irrelevant in the context of secg, fujitsu, certicom,etc. You might be able to get something from the US-based governmental member (NIST).Title: Re: NSA and ECC Post by: BurtW on September 20, 2013, 08:08:38 PM Ok, our friend Dan at SECG is really trying to dig into this and find out exactly how the random curves were generated. He has asked me to narrow down the search to the curves we are actually interested in so he does not waste time researching curves we do not care about.
So, I need a list of the random curves that we actually care about - or maybe people have stopped caring about NIST/NSA random curves since the one we use is not a NSA/NIST curve. Here is what he has done and found out so far in his preliminary analysis: Quote Yesterday, I dug a little into this: I extracted the seeds from the LaTeX source, using a not very careful grep search, and found 22 seeds (some of which are now commented out in SEC2). I may have missed some seeds whose LaTeX did not match my criteria. Twelve seeds contain the ASCII string “MinghuaQu”, but in some cases they are shifted by 4 bits. I concluded that these 12 were not NIST curves, and that the remaining 10 curves must be NIST curves. I believe that the 12 seeds containing “MinghuaQu” are curves are mostly 163 bit or smaller, so I doubt that you are considering them. So far, I have not detected any clear pattern in the remaining ten seeds, but I have not tried hard, mainly I suspect that they are the output of some PRNG, and therefore such tests would likely fail. My main check so far was to compare the sorted set of byte frequencies among the 400 seed bytes to the same statistic for random sets of 400 pseudorandom bytes. A few trials of the random sets had a higher maximum frequency, and some had a lower maximum frequency. I did not calculate any kind of P-test. The point of this test was to see the seeds were some byte-encoding which might favour some particular bytes. I have done to nothing examine the order of the bytes. Again: many of the smaller curves are now absent from SEC2 version 2.0, which has 11 random curves, 10 of which are NIST curves. Best regards, Dan Title: Re: NSA and ECC Post by: niko on September 20, 2013, 08:53:07 PM So, I need a list of the random curves that we actually care about - or maybe people have stopped caring about NIST/NSA random curves since the one we use is not a NSA/NIST curve. From all the recent revelations it appears that NSA operates also by proxies and shills in private and academic institutions who push the NSA agenda. Title: Re: NSA and ECC Post by: jgarzik on September 20, 2013, 11:27:41 PM We care about bitcoin's curve ;p
Title: Re: NSA and ECC Post by: gmaxwell on September 20, 2013, 11:30:20 PM We care about bitcoin's curve ;p Other than the SECP256k1 we use in Bitcoin, a lot of the internet cares about the NIST P256r and P224r curves.Title: Re: NSA and ECC Post by: Peter Todd on September 21, 2013, 01:59:19 AM We care about bitcoin's curve ;p Other than the SECP256k1 we use in Bitcoin, a lot of the internet cares about the NIST P256r and P224r curves.OpenPGP ECDSA uses those curves right? (and the 512r one too) Title: Re: NSA and ECC Post by: piotr_n on September 21, 2013, 08:42:15 AM So, I need a list of the random curves that we actually care about - or maybe people have stopped caring about NIST/NSA random curves since the one we use is not a NSA/NIST curve. Thanks Burt for digging into it.I don't know about others, but personally I only care about SECP256k1, and specifically about these five constants: Code: P = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F How the above values were chosen/calculated/generated? What process a person shall follow to get to the same values? If we know the process of calculating these values, I guess we should be able to draw our own conclusions on whether it was an honest one, or rather a backdoor driven. B and N were rather chosen intentionally not randomly - but also here I would like to hear a fair explanation (a scientific justification) on why this values and not some others. Title: Re: NSA and ECC Post by: fpgaminer on September 21, 2013, 09:10:58 AM Quote and specifically about these five constants: They've already been explained in this thread. In summary:The first constant we care about is p; TierNolan already explained that one. It's the From that we can explain b. If we're searching for the smallest combination of a and b that results in a prime order elliptic curve, a = 0 and b = 7 is the first one. I don't know the specifics on why a and b should be small (probably GLV optimization), but they aren't suspicious regardless. N is just the order of the elliptic curve; no explanation needed. The last piece of the puzzle is the choice for G. Since the order of the elliptic curve is prime, we can pick any point on the curve (except infinity), and get a group with the same order (i.e. there are no subgroups). Why SECG picked the particular G they did is unexplained. However, there is no reason to believe any G is weaker or stronger than any other G (against a compliant ECDSA verifier). I would guess that either G is totally random, or it has sentimental meaning to the author(s). Since the curve is not weak to any publicly known attacks, and the constants are not suspicious, then what else are we looking for with regards to secp256k1? Title: Re: NSA and ECC Post by: piotr_n on September 21, 2013, 10:06:54 AM Quote and specifically about these five constants: They've already been explained in this thread. In summary:Justified - no. At least not according to my understanding of what "science" is. To be more specific: The first constant we care about is p; TierNolan already explained that one. It's the largest prime that satisfies: p = 2^256 - 2^32 - t where t < 1024 But why 1024? What does 1024 have to do with the EC math?Why the largest prime for t<1024, not e.g. the smallest prime for t>1024? This explanation, instead of answering questions, only creates more. Quote From that we can explain b. If we're searching for the smallest combination of a and b that results in a prime order elliptic curve, a = 0 and b = 7 is the first one. I don't know the specifics on why a and b should be small (probably GLV optimization), but they aren't suspicious regardless. I'd like to know "the specifics" though.For you they aren't suspicious because they are small - but maybe B is suspicious exactly because it is small? Or maybe it is suspicious because it leads to a specific N that is suspicious... Don't get me wrong - it's not that I believe in B being suspicious, but before we know exactly why it is 7, we cannot exclude any possibility, can we? Quote Since the curve is not weak to any publicly known attacks, and the constants are not suspicious, then what else are we looking for with regards to secp256k1? If you believe that the curve is not weak to any attacks, then what are you doing in this topic? In such case it should not concern you.But if you believe that the curve might be weak to some attacks that are not publicly known, though they are known to someone, then the statements you are making are kind of weird, since whether such weaknesses exist is exactly what we are trying to figure out here, while you are throwing your "no worries" conclusion on us. If there is a weakness that depends on the constants (which is the thesis from the OP), the best way to find it goes through questioning the values. Title: Re: NSA and ECC Post by: BurtW on September 21, 2013, 03:19:24 PM With regard to the selection of a and b, from Dan:
Quote Also, I read a little more on the subject: the curve parameters (0,7) belong to the class of curves with a=0 which have an efficient endomorphism of order 3 (as listed in the GLV paper). I am curious to know if BitCoin is using GLV method which takes advantage of this feature. I did not know the answer to Dan's question so I asked gmaxwell and he responded to Dan, through me, with: Quote No, the production Bitcoin software uses a completely straight forward curve-generic implementation. However, the possibility of high speed implementations is one of the major attractive characteristics of this curve. Bitcoin uses a zero-trust design where all participating nodes verify all signatures, so the whole network's scalability depends on the weakest full participants. One of our core developers has created a high performance secp256k1 implementation which we may use in the future: https://github.com/sipa/secp256k1 This implementation can do around 14k validations per second per core on a modern i7 cpu. (Which makes it about 6x faster than the generic code we use today). One of the barriers in deploying this implementation is having more ECC experienced eyes looking at it. Therefore we know that a=0 on purpose and b=7 is the smallest value that works given a=0. Title: Re: NSA and ECC Post by: polarhei on September 21, 2013, 03:32:58 PM He's worried about constants that have no explanation. The SEC random curves have "random numbers" in them, but are they really random? AFAIK nobody knows how one might exploit the algorithms if they weren't, but hesitation is reasonable. However Bitcoin does not use a random curve. It uses a Koblitz curve where there are explanations for why the constants are the way they are. Also, the NSA is not going to crack the crypto used on Bitcoin because their goal is not to actively attack Bitcoin (I doubt the NSA care much about financial regulations). Their goal is to spy on everyone. They're much more likely to do graph analysis of the block chain than worry about the crypto. There is no true random. Only exponential. Title: Re: NSA and ECC Post by: BurtW on September 21, 2013, 03:37:18 PM There is no true random. Only exponential. What? Title: Re: NSA and ECC Post by: gmaxwell on September 21, 2013, 03:37:43 PM The first constant we care about is p; TierNolan already explained that one. It's the largest prime that satisfies: p = 2^256 - 2^32 - t where t < 1024 But why 1024? What does 1024 have to do with the EC math?Why the largest prime for t<1024, not e.g. the smallest prime for t>1024? This explanation, instead of answering questions, only creates more. The number is a generalized mersenne prime (http://en.wikipedia.org/wiki/Mersenne_prime#Generalization). The reason for this is that our we are doing calculations in this field so when we multiply we must take the result mod p where p is the size of the field. If p is a freely chosen prime to compute the mod we must divide which is hideously complex. Instead, if P has special form, we can break the larger value at the word level into small fragments and compute the mod p as some sum of them with negations. The performance impact is enormous. This is just an extension of how it's easier to compute x%16, which can be computed as x&15, then it is to compute x%13. The reason to use largest prime is just to have the largest field size for one admitting the optimization. The same reasonable sounding criteria has been used to select primes for many different curves, so it's unlikely that a bad prime was selected and then a complicated explanation was found. The explanation gives a real performance improvement, makes sense, and then was used many times to pick many numbers. Likewise the efficient endomorphism selection of the a and curve formula permits using the GLV method (http://www.iacr.org/archive/crypto2001/21390189.pdf) to speed up point multiplies. This optimization is used by Pieter's libsecp256k1 (https://github.com/sipa/secp256k1) to make ECDSA verification on x86_64 something like 6x faster than OpenSSL for our curve. Maybe it turns out that these selections for performance also turn out to select for some weakness. No one knows what unknown math will bring. But the performance benefits are not small, so you don't have to hypothize some rigged process to explain this stuff. (And certainly ECDSA performance is very important to our applications.) As a side effect, this eliminates all random parameters, save the generator. So thats a great relief for anyone concerned that our parameters were mysterious and could have been rigged via non-public selection. I have no blinking idea where the generator comes from, but also can't come up with _any_ way it could be an attack even if I assume that our curve has a weakness of every form which I've heard of for discrete log on an abelian variety. The generator is generally irrelevant. You might be able to pick one which permits faster multiplication under some specific multiplication scheme, but I asked Pieter about that and he seemed to believe that it would take a exponentially hard search, so was unlikely to be very useful... I've only bothered expending time thinking about it because I can't figure out why, due to the irrelevance of its specific value, they didn't pick one with a more compact binary representation, and because its the only parameter thats unexplained though it is the only one which there is no real reason to care about. This isn't to say that the curve selection couldn't be better: Ed25519 is still somewhat faster than Pieter's code. Our parameters pick a curve who's quadratic twist is not of prime order, which means that some optimizations (e.g. the ones used in Ed25519) are not available, and it also means that a single bit error during a multiply (e.g. for doing ECDH) could basically leak the private key. (Basically an off by one in the x coordinate instead gives a value on the twist, and because the twist's order is factorable, the discrete log problem can be solved on it with complexity related to its largest factor, which is only about 2^50). But the ideas behind making curves for high performance which are better in these respects all came after these parameters were selected. Title: Re: NSA and ECC Post by: piotr_n on September 21, 2013, 04:07:15 PM The first constant we care about is p; TierNolan already explained that one. It's the largest prime that satisfies: p = 2^256 - 2^32 - t where t < 1024 But why 1024? What does 1024 have to do with the EC math?Why the largest prime for t<1024, not e.g. the smallest prime for t>1024? This explanation, instead of answering questions, only creates more. The number is a generalized mersenne prime (http://en.wikipedia.org/wiki/Mersenne_prime#Generalization). The reason for this is that our we are doing calculations in this field so when we multiply we must take the result mod p where p is the size of the field. If p is a freely chosen prime to compute the mod we must divide which is hideously complex. Instead, if P has special form, we can break the larger value at the word level into small fragments and compute the mod p as some sum of them with negations. The performance impact is enormous. This is just an extension of how it's easier to compute x%16, which can be computed as x&15, then it is to compute x%13. I am not going to pretend that I am working on this stuff in detail, since honestly I have no freaking idea what all these XY vs XYZ calculations do, nor I'd dare to question your expertise in this field. But still I didn't get it, from your explanation, why it is 1024 and not e.g. 512 or 2048? Title: Re: NSA and ECC Post by: TierNolan on September 21, 2013, 05:13:46 PM Quote and specifically about these five constants: They've already been explained in this thread. In summary:The first constant we care about is p; TierNolan already explained that one. It's the largest prime that satisfies: p = 2^256 - 2^32 - t where t < 1024 It is technically the smallest prime, since it is the largest t (and t is subtracted). I don't know where 1024 comes from. Maybe there is something in the internals of large multipliers. The 2^32 is presumably linked to 32 bit words in the multipliers. Quote From that we can explain b. That is past my expertise, but a check should be made that b < 7 wouldn't have given a prime order. Title: Re: NSA and ECC Post by: BurtW on September 21, 2013, 06:13:48 PM That is past my expertise, but a check should be made that b < 7 wouldn't have given a prime order. ask and you shall... By the way, I ran a little experiment. Given our finite field, and setting a to 0, 7 is the first (counting from 0) value for b that results in a prime order elliptic group. I don't understand GLV well enough to know what restrictions it places on a and b, but if we have to pick a curve where a is 0, it seems like b being 7 would be a logical choice (again, given our finite field). Title: Re: NSA and ECC Post by: piotr_n on September 21, 2013, 06:32:44 PM pardon me the lame question, but what is the actual formula to calculate the order (N), from the A & B?
can I calc it myself, using a python shell, or do I need a six dimensions math library? ;) moreover, from what I understand, it isn't really possible to check whether 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 is a real prime number, is it? AFAIK, the algos we know only allow us to check whether such a big numbers are prime with a certain probability, but we can never be totally sure about their primness, since checking for that would have taken ages - right? Title: Re: NSA and ECC Post by: BurtW on September 21, 2013, 07:26:13 PM I can answer the question about the prime numbers. If you set the certainty high enough you can be certain. For example above in this thread the call test.isProbablePrime(1024) is made. This is asking to test if the number is prime within a certainty of 1 - 0.51024
When I try to calculate this number on my calculator I get 1.00 So pretty darn certain. 0.51024 = 5.562684646268e-309 Title: Re: NSA and ECC Post by: Etlase2 on September 21, 2013, 07:31:05 PM Maybe this needs its own thread, but there are a lot of crypto-smart people in this thread who will see it and it needs some discussion I think:
"Some Lattice Attacks on DSA and ECDSA" http://eprint.iacr.org/2009/363.pdf Abstract: In this paper, using the LLL reduction method and computing the integral points of two classes of conics, we develop attacks on DSA and ECDSA in case where the secret and the ephemeral key and their modular inverse are quite small or quite large. I wasn't able to find any papers or discussion referencing it. The authors conclude that the attacks can be "quite efficient". Title: Re: NSA and ECC Post by: piotr_n on September 21, 2013, 07:38:46 PM I can answer the question about the prime numbers. If you set the certainty high enough you can be certain. For example above in this thread the call test.isProbablePrime(1024) is made. This is asking to test if the number is prime within a certainty of 1 - 0.51024 Right - that should do :)I'm just going blind here, trying to find a hole, though still hoping that there isn't any. Title: Re: NSA and ECC Post by: TierNolan on September 21, 2013, 08:03:13 PM ask and you shall... Ahh, thanks, missed that one. Title: Re: NSA and ECC Post by: gmaxwell on September 21, 2013, 08:15:08 PM pardon me the lame question, but what is the actual formula to calculate the order (N), from the A & B? You need a six dimensions math library. :)can I calc it myself, using a python shell, or do I need a six dimensions math library? ;) For curves of particular structure there are simple formulas, but the general case is hard. Fancy math packages just have functions to implement fancy techniques (http://www-scf.usc.edu/~burhanud/project/satoh-FGH1.pdf). There is an overview of techniques in section 5 here: http://cdn.intechopen.com/pdfs/29703/InTech-Elliptic_curve_cryptography_and_point_counting_algorithms.pdf Quote moreover, from what I understand, it isn't really possible to check whether 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 is a real prime number, is it? The optimality testing we can do has exponential confidence with additional testing... so you can be arbitrarily confident. 2^256 is also small enough that you can try factoring numbers to increase your confidence (though you may need to take care to defeat initial primality testing in your factoring software).(E.g. I successfully factored the order of secp256k1's twist just using the factor command on my Fedora system: $ time factor 1286578769603068245382716924545379906921918859152521322839515520912848165551 1286578769603068245382716924545379906921918859152521322839515520912848165551: 3 3 3 197 1511 1559 96769 146849 2587814237219 375925338294461779 7427691663837602734654241 real 6m35.889s) I wasn't able to find any papers or discussion referencing it. The authors conclude that the attacks can be "quite efficient". I've seen this paper before.It's "quite efficient", at least relative to recovering the key the exponential time way by computing the discrete log of the public key, under their assumptions that you've signed messages with either a pair of very small (or large) K values, or a single message with a permitted combination large and small K and signature. The definition of small/large depends which of their cases you're concerned with, but picking one at random, requires (K1 * K2) < (order^(1/2))/6^(3/4). So e.g. <2^61. The probability of picking a single 256 bit K less than 2^61 is 1e-59. So the probability is negligible even if you sign many times (and I think there were additional constraints as well— it certainly would have been nice if the authors had given concrete figures rather than requiring the readers to fuddle through the math themselves…). (Though I suppose if you want to be extra paranoid you can use this kind of thing as yet another argument for not reusing keys, at if we didn't already have enough). (And even in this case, it's not clear to me that the solution is actually tractable, just exponentially better than the DLP solving way) Title: Re: NSA and ECC Post by: fpgaminer on September 21, 2013, 11:46:11 PM Quote That is past my expertise, but a check should be made that b < 7 wouldn't have given a prime order. Well, you put in the work to check p for us, so here's my contribution:secp256k1_parameter_proof.py Code: from sage.all import * This requires sagemath, and can be executed by running "sage -python secp256k1_parameter_proof.py" Here is my output: Code: Testing 7 I built the test to not only show that b = 7 results in the first prime order, given a = 0, but also that a = 0 and b = 7 is the first result when searching all combinations of a and b < 7. So, if one was looking for a curve, and didn't know about GLV, (0,7) would still be a reasonable choice. Title: Re: NSA and ECC Post by: piotr_n on September 22, 2013, 02:06:31 PM I built the test to not only show that b = 7 results in the first prime order, given a = 0, but also that a = 0 and b = 7 is the first result when searching all combinations of a and b < 7. So, if one was looking for a curve, and didn't know about GLV, (0,7) would still be a reasonable choice. Thanks. That's a decent and quite convincing explanation of why they chose B to be 7, though don't you feel like doing someone's else job here by explaining it to us? :)I guess we can narrow down our investigation to the G point and the P (since we still don't seem to know what is so great about 1024 aka 2^10). Title: Re: NSA and ECC Post by: Etlase2 on September 22, 2013, 02:48:11 PM (and I think there were additional constraints as well— it certainly would have been nice if the authors had given concrete figures rather than requiring the readers to fuddle through the math themselves…). Super math geeks, what do you expect? :P Hopefully the more cryptography enters into the public eye, cryptographers will be more apt to write papers that are digestible by a wider audience. Is it possible to simply avoid getting into the situations described by the paper? Or would doing so effectively reduce the security by the same amount? Title: Re: NSA and ECC Post by: fpgaminer on September 23, 2013, 04:04:06 AM Quote I guess we can narrow down our investigation to the G point and the P (since we still don't seem to know what is so great about 1024 aka 2^10). An explanation on G would be nice to have, yes. As for p, someone would need to dig into the implementation of optimized reduction algorithms to explain why t being less than 1024 is helpful. I've implemented a secp256k1 specific reduction algorithm before (link to source (https://github.com/fpgaminer/strong-arm/blob/master/src/finite_field/ff_big.c#L124)), but it's been awhile and I didn't take the time to intuitively understand exactly which Mersenne-like primes make the method work effectively. Nor do I understand why they chose the smallest p, and not the largest. Perhaps that particular p allowed a small (a,b) for the curve? I recall there being better (less code required) Mersenne-like primes to choose.Title: Re: NSA and ECC Post by: fpgaminer on September 23, 2013, 04:25:07 AM Here's another interesting data point. If we search all primes of the form 2**256 - 2**32 - t, starting from t = 0 to t = infinity, the first prime order curve with a = 0 and b < 1000 is the secp256k1 curve. Code:
Code: from sage.all import * That helps to explain p a bit more. (In other words, we have an alternative explanation that doesn't involved 2^10). Title: Re: NSA and ECC Post by: someone42 on September 23, 2013, 05:37:32 AM Quote I guess we can narrow down our investigation to the G point and the P (since we still don't seem to know what is so great about 1024 aka 2^10). An explanation on G would be nice to have, yes. As for p, someone would need to dig into the implementation of optimized reduction algorithms to explain why t being less than 1024 is helpful. I've implemented a secp256k1 specific reduction algorithm before (link to source (https://github.com/fpgaminer/strong-arm/blob/master/src/finite_field/ff_big.c#L124)), but it's been awhile and I didn't take the time to intuitively understand exactly which Mersenne-like primes make the method work effectively. Nor do I understand why they chose the smallest p, and not the largest. Perhaps that particular p allowed a small (a,b) for the curve? I recall there being better (less code required) Mersenne-like primes to choose.I'm not sure if this is the optimisation you're after, but section 2.2.6 of http://www.springeronline.com/sgw/cda/pageitems/document/cda_downloaddocument/0,11996,0-0-45-110359-0,00.pdf (http://www.springeronline.com/sgw/cda/pageitems/document/cda_downloaddocument/0,11996,0-0-45-110359-0,00.pdf) (from here: http://cacr.uwaterloo.ca/ecc/ (http://cacr.uwaterloo.ca/ecc/)) describes the property as: the prime must be a sum or difference of powers of 2^32. secp256k1 doesn't have this property exactly, which is why your code has all that shifting in it. Title: Re: NSA and ECC Post by: TierNolan on September 23, 2013, 09:27:06 AM An explanation on G would be nice to have, yes. As for p, someone would need to dig into the implementation of optimized reduction algorithms to explain why t being less than 1024 is helpful. The thing is that they went for largest t less than 1024. They could have gone for largest prime less than 2^256 or (2^256 - 2^32), but they went for smallest prime greater than (2^256 - 2^32 - 2^10). Quote Perhaps that particular p allowed a small (a,b) for the curve? I recall there being better (less code required) Mersenne-like primes to choose. That might be worth checking. It might have nothing to do with 2^10. 2^256 - 2^32 has some advantage when dealing with a 32 bit words. If you multiply two 256 bit numbers together, you get a 512 bit number. They can be broken down into x and y with a base (b) of 2^256. x * b + y Taking mod p x * b + y mod p b can be replaced by b mod p x * (b mod p) + y mod p If p = 2^256 - 2^32 - t, then (b mod p) is 2^32 + t x * [2^32 + t] + y mod p x * 2^32 + x * t + y mod p (x * 2^32) is easy to compute, since it is just move all the words over by 1 (x * t) is a little harder, since you have to handle carry, but it is still a small number [ * ] y is unchanged Assuming t is a 10 bit number, this gives 288 bit number + 266 bit number + 256 bit number = 289 bit number This gives a much smaller number than originally. x is at most 33 bits and the process can be repeated. 65 bit number + 43 bit number + 256 bit number = 257 bit number This could be handled "manually" by subtracting p until it is less than p. I would suggest checking all primes of the form 2^256 - t 2^256 - 2^32 - t for t < 2048 and then seeing what the lowest a and b are for each prime. If there are no good values for 2^256 - t, then that might explain why they switched to 2^256 - 2^32 - t. [ * ] this is like multiplying 123456 by 7, it is easier than if both numbers are multiple digits. That helps to explain p a bit more. (In other words, we have an alternative explanation that doesn't involved 2^10). Can you run the same check for 2^256 - t. Title: Re: NSA and ECC Post by: runeks on September 25, 2013, 03:48:38 PM pardon me the lame question, but what is the actual formula to calculate the order (N), from the A & B? You can use sage. They have an online version of their shell here (http://www.sagenb.org/). Here's how you calculate the order of secp256k1:can I calc it myself, using a python shell, or do I need a six dimensions math library? ;) Code: sage: F = FiniteField(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F) Title: Re: NSA and ECC Post by: Roy Badami on September 25, 2013, 08:09:20 PM If you're asking about BIP32, BIP32 is specific to SECP256k1 (as its results are well defined), but it supports both public and private derivation. The private derivation could be applied to any cryptosystem, though that wouldn't be BIP32 anymore. The public derivation could be applied to at least any ECDSA cryptosystem. Is it still the intention for Bitcoin-QT to move to BIP 32 in the future? roy Title: Re: NSA and ECC Post by: maaku on September 25, 2013, 08:17:29 PM If you write the code.
Title: Re: NSA and ECC Post by: Roy Badami on September 25, 2013, 10:38:23 PM If you write the code. ? My point is that previously the core devs have suggested an intention to migrate from bag-of-keys to heirarchical deterministic wallets. The argument, AIUI, is that it simplifies backup, but such a decision would seem to negate the argument given in this thread that Bitcoin is largely safe from ECDSA attacks as long as we avoid address reuse. So, in the light of the concerns over NSA activity in this area, I'm wondering whether it's still the intention to trust our coins (more than at present) to the security of ECDSA. roy Title: Re: NSA and ECC Post by: gmaxwell on September 27, 2013, 10:19:21 PM I've finally come up with a way to exploit ECDSA given control of only the generator.
Basically, you set the generator to some random multiple of an existing "public key". Then you can effectively use the "public key" as the secret for signing arbitrary messages from that "public key". In quotes because the whole idea of a public key is ill defined if you don't yet have a generator. Imaging a Bitcoin' where all coins had to be assigned to some pubkey. And lets also imagine that coins in this system expire, to make them unspendable it assigns them to SHA256("expired"). If I can pick G I can set G to SHA256("expired")*N ... and 1/N is now effectively the private key for SHA256("expired")! So what _looks_ like a nothing up my sleeve address really isn't one, and I can spend those coins. I don't think this exposes us to any particular risk, since it only works for one key, and we have no nothing up my sleeve pubkeys, and the parameters for our system were fixed before Bitcoin existed. But if some nice man from the NSA or Certicom claims to have a nothing up his sleeve pubkey for some protocol or another... perhaps you'd be wise to not believe him. :) Title: Re: NSA and ECC Post by: Wipeout2097 on September 29, 2013, 07:44:04 AM Also, the NSA is not going to crack the crypto used on Bitcoin because their goal is not to actively attack Bitcoin (I doubt the NSA care much about financial regulations). Their goal is to spy on everyone. They're much more likely to do graph analysis of the block chain than worry about the crypto. Yes, and perhaps set up "rogue" full nodes.Title: Re: NSA and ECC Post by: maaku on September 29, 2013, 08:09:06 AM Yes, and perhaps set up "rogue" full nodes. What the heck is a "rogue" full node?Title: Re: NSA and ECC Post by: BurtW on September 29, 2013, 08:15:48 AM Yes, and perhaps set up "rogue" full nodes. What the heck is a "rogue" full node?Maybe it just takes in transactions but does not send them out! No, wait... Maybe it makes up a lot of bogus transactions? No, wait... Hmmm. I guess I don't know. What is a "rogue" full node? Anyone? Title: Re: NSA and ECC Post by: niko on September 29, 2013, 08:22:16 AM Yes, and perhaps set up "rogue" full nodes. What the heck is a "rogue" full node?Maybe it just takes in transactions but does not send them out! No, wait... Maybe it makes up a lot of bogus transactions? No, wait... Hmmm. I guess I don't know. What is a "rogue" full node? Anyone? Title: Re: NSA and ECC Post by: chriswilmer on September 29, 2013, 01:26:38 PM I've finally come up with a way to exploit ECDSA given control of only the generator. Basically, you set the generator to some random multiple of an existing "public key". Then you can effectively use the "public key" as the secret for signing arbitrary messages from that "public key". In quotes because the whole idea of a public key is ill defined if you don't yet have a generator. Imaging a Bitcoin' where all coins had to be assigned to some pubkey. And lets also imagine that coins in this system expire, to make them unspendable it assigns them to SHA256("expired"). If I can pick G I can set G to SHA256("expired")*N ... and 1/N is now effectively the private key for SHA256("expired")! So what _looks_ like a nothing up my sleeve address really isn't one, and I can spend those coins. I don't think this exposes us to any particular risk, since it only works for one key, and we have no nothing up my sleeve pubkeys, and the parameters for our system were fixed before Bitcoin existed. But if some nice man from the NSA or Certicom claims to have a nothing up his sleeve pubkey for some protocol or another... perhaps you'd be wise to not believe him. :) Interesting! So G could be a secret multiple of some number. You say this only works for one key... could it work for a set of related keys? Presumably you could derive an entire set of public/private keys deterministically from the private key you got by choosing G. Title: Re: NSA and ECC Post by: oleganza on September 30, 2013, 11:59:42 AM Imaging a Bitcoin' where all coins had to be assigned to some pubkey. And lets also imagine that coins in this system expire, to make them unspendable it assigns them to SHA256("expired"). If I can pick G I can set G to SHA256("expired")*N ... and 1/N is now effectively the private key for SHA256("expired")! So what _looks_ like a nothing up my sleeve address really isn't one, and I can spend those coins. G cannot be SHA256 * N because both SHA256 and N are scalar numbers in your example. You need a 2D point somewhere in this equation. Title: Re: NSA and ECC Post by: chriswilmer on September 30, 2013, 12:52:41 PM Imaging a Bitcoin' where all coins had to be assigned to some pubkey. And lets also imagine that coins in this system expire, to make them unspendable it assigns them to SHA256("expired"). If I can pick G I can set G to SHA256("expired")*N ... and 1/N is now effectively the private key for SHA256("expired")! So what _looks_ like a nothing up my sleeve address really isn't one, and I can spend those coins. G cannot be SHA256 * N because both SHA256 and N are scalar numbers in your example. You need a 2D point somewhere in this equation. I think this is just a matter of encoding. You can map integers to 2D integer-valued points in a 1-to-1 way. Title: Re: NSA and ECC Post by: BurtW on September 30, 2013, 03:19:26 PM Imaging a Bitcoin' where all coins had to be assigned to some pubkey. And lets also imagine that coins in this system expire, to make them unspendable it assigns them to SHA256("expired"). If I can pick G I can set G to SHA256("expired")*N ... and 1/N is now effectively the private key for SHA256("expired")! So what _looks_ like a nothing up my sleeve address really isn't one, and I can spend those coins. G cannot be SHA256 * N because both SHA256 and N are scalar numbers in your example. You need a 2D point somewhere in this equation. Quote If I can pick G I can set G to ("expired")*N ... and 1/N is now effectively the private key for SHA256("expired")! It is just a typo, ("expired") is a point on the curve.Title: Re: NSA and ECC Post by: BurtW on September 30, 2013, 03:29:46 PM This totally hypothetical situation can be generalized to an arbitraty number of points that are selected before G is selected:
Select P0 P1 = n0*P0 P2 = n1*P1 P3 = n2*P2 ... G = nM*PM Now all these "premined" ;) key pairs could maybe be used in some way ??? But it seems to me that all of these key pairs are just like any other key pairs that get generated after G is selected, right? Title: Re: NSA and ECC Post by: chriswilmer on September 30, 2013, 03:58:01 PM This totally hypothetical situation can be generalized to an arbitraty number of points that are selected before G is selected: Select P0 P1 = n0*P0 P2 = n1*P1 P3 = n2*P2 ... G = nM*PM Now all these "premined" ;) key pairs could maybe be used in some way ??? But it seems to me that all of these key pairs are just like any other key pairs that get generated after G is selected, right? Wait wait wait... I may be out of my depth here, but isn't the generating point supposed to be able to generate a group of the same size as the order of the curve? If you pick G to be a multiple of an existing point on the curve, then it won't be a "good" generator... it will only generate a smaller sub-group. Am I making any sense? Title: Re: NSA and ECC Post by: BurtW on September 30, 2013, 04:19:11 PM Our group is prime and has no sub groups so any point should work as G.
This brings up something that I have been wondering about: If any point will work equally well for G why not use an "easy" point or an "obvious" point? x = 0 or x = 1 or x = 2n all come to mind. Anyone have any idea why G is not a more "obvious" starting point? Title: Re: NSA and ECC Post by: chriswilmer on September 30, 2013, 04:57:55 PM Our group is prime and has no sub groups so any point should work as a G. Ah ha! Thanks. I was wondering why the group order needed to be prime. Title: Re: NSA and ECC Post by: gmaxwell on September 30, 2013, 05:24:02 PM Anyone have any idea why G is not a more "obvious" starting point? Not being able to answer that was why I spent a bunch of time trying to come up with "attacks" that selection of a non-obvious G could yield. But all I could come up with doesn't seem to be too much. ::shrugs::Ah ha! Thanks. I was wondering why the group order needed to be prime. Not just that, but if there are subgroups there are reductions that allow you to solve the DLP with basically no more work than solving it over a field thats the size of the largest factor.Title: Re: NSA and ECC Post by: bfever on October 02, 2013, 07:09:20 PM Our group is prime and has no sub groups so any point should work as G. This brings up something that I have been wondering about: If any point will work equally well for G why not use an "easy" point or an "obvious" point? x = 0 or x = 1 or x = 2n all come to mind. Anyone have any idea why G is not a more "obvious" starting point? Well, the point must lie on the curve, so it must satisfy y2 = x3 + 7 (mod p). So x=0, means y2=7, which has no solution for an integer y, so there is no point on the curve with x coordinate 0. Same for x=1,2,3,4,... I think you can go on for a while before finding a solution that way. I think there is no "obvious" solution, so one starts with a "random" value for x and incrementing this until x3+7 has an integer square root. I saw some posts of people generating their own curves incorporating hex-art and/or hashes of "copyright notes" into the value + a counter. It really should not be different, the only thing is everybody needs to use the same G otherwise the key pairs (public/private key) don't match. Title: Re: NSA and ECC Post by: gmaxwell on October 02, 2013, 09:03:54 PM ...
1 : 29896722852569046015560700294576055776214335159245303116488692907525646231534 is a point on our curve, as is 2 : 46580984542418694471253469931035885126779956971428003686700937153791839982430 and so on. The first missing x, other than zero obviously, is 5. Title: Re: NSA and ECC Post by: fpgaminer on October 07, 2013, 11:30:56 PM Quote So x=0, means y2=7, which has no solution for an integer y, so there is no point on the curve with x coordinate 0. We aren't dealing with your ordinary, run-of-the-mill integers here. We're dealing with a finite field! y2 = 13 + 7 has a solution (two, in fact). It's 4218F20AE6C646B363DB68605822FB14264CA8D2587FDD6FBC750D587E76A7EE. Square that number, modulus our prime, and you get 8.Same for x=1,2,3,4,... I think you can go on for a while before finding a solution that way. So yeah, G could have been selected as an obvious, nothing-up-my-sleeve number. It wasn't. I'd bet on it being some sentimental thing, like the hash of the author's name or something. Title: Re: NSA and ECC Post by: BurtW on October 08, 2013, 03:32:58 AM ... Now I am really out of my depth here but since P = n * G is a very commonly needed operation is is faster or simpler to use, for example the point:1 : 29896722852569046015560700294576055776214335159245303116488692907525646231534 is a point on our curve, as is 2 : 46580984542418694471253469931035885126779956971428003686700937153791839982430 and so on. The first missing x, other than zero obviously, is 5. x = 1, y = 29896722852569046015560700294576055776214335159245303116488692907525646231534 as G In other words, is there any possible efficiency argument that can be made for the selection of G? In my gut I expect that any G is equally computationally difficult as far as P = n * G goes. Correct? Title: Re: NSA and ECC Post by: gmaxwell on October 08, 2013, 05:15:47 AM In other words, is there any possible efficiency argument that can be made for the selection of G? Not for our G.In my gut I expect that any G is equally computationally difficult as far as P = n * G goes. Correct? It should be possible, with an expensive search (e.g. >2^32 tries), to find a G that results in a lower hamming weight in the multiplies in a particular implementation and get a very small speed improvement. But I can find nothing about our G that suggests such a thing was done. Title: Re: NSA and ECC Post by: AnonyMint on October 13, 2013, 10:16:39 PM He's worried about constants that have no explanation. The SEC random curves have "random numbers" in them, but are they really random? AFAIK nobody knows how one might exploit the algorithms if they weren't, but hesitation is reasonable. However Bitcoin does not use a random curve. It uses a Koblitz curve where there are explanations for why the constants are the way they are. He is also worried about math breakthroughs and the shorter key sizes of ECC, and he recommending never use unless required: https://www.schneier.com/crypto-gram-9911.html#EllipticCurvePublic-KeyCryptography And he recommends using symmetric instead of public-key (so Lamport instead): https://www.schneier.com/blog/archives/2013/09/the_nsas_crypto_1.html And the Koblitz curve explanations doesn't remove the lack of transparency in the seeds: https://bitcointalk.org/index.php?topic=309594.msg3332190#msg3332190 Also, the NSA is not going to crack the crypto used on Bitcoin because their goal is not to actively attack Bitcoin (I doubt the NSA care much about financial regulations). Their goal is to spy on everyone. They're much more likely to do graph analysis of the block chain than worry about the crypto. Until the government requires them to do so because Bitcoin becomes a tax-haven. The G20 has been ramping up their plans to go after all tax havens. Ok, so your take is basically the same as the commenter on Schneier's blog (https://www.schneier.com/blog/archives/2013/09/the_nsa_is_brea.html#c1678526). Basically he says what you are saying - that a recommended 'random' number generator for use with ECC has been proven to have backdoors, and that some families of ECC curves have weaknesses. However, because we're using secp256k1, a known curve with explainable/justifiable constants, the concern cited by Bruce is not applicable to Bitcoin in addition to the weak motivation for attacking it anyhow. Thanks for the reply. Disagree that he said that, also disagree that makes Bitcoin safe. See links above. Schneier is justified in his recommendation, IMHO. But there is one bright spot: even if the standard ECDSA curves were broken in this way, if you do not reuse addresses it would not concern you as no public key or ciphertext is available until the coins are spent. So don't re-use bitcoin addresses (you shouldn't anyway). That bright spot is not assured: https://bitcointalk.org/index.php?topic=309594.msg3331735#msg3331735 Title: Re: NSA and ECC Post by: gmaxwell on October 13, 2013, 10:59:45 PM And the Koblitz curve explanations doesn't remove the lack of transparency in the seeds: There is no seed in the scheme Bitcoin uses, I am not sure how many times you will need to be told this.Title: Re: NSA and ECC Post by: jedunnigan on October 14, 2013, 05:17:15 PM Came across this on HN, thought it would be useful here: SafeCurves: choosing safe curves for elliptic-curve cryptography (http://safecurves.cr.yp.to/).
Title: Re: NSA and ECC Post by: gmaxwell on October 14, 2013, 05:46:44 PM Came across this on HN, thought it would be useful here: SafeCurves: choosing safe curves for elliptic-curve cryptography (http://safecurves.cr.yp.to/). Their rigidity page doesn't appear to explain the choice of generator for any of their "Fully rigid" cases. See upthread that it would be preferable for the generator to be rigid too, if not essential.Title: Re: NSA and ECC Post by: AnonyMint on October 14, 2013, 05:54:31 PM And the Koblitz curve explanations doesn't remove the lack of transparency in the seeds: There is no seed in the scheme Bitcoin uses, I am not sure how many times you will need to be told this.Seed has a generic meaning. http://www.thefreedictionary.com/seed 8. A source or beginning Is that the best FUD you can do to avoid addressing the point? Is the only way you know how to discuss and debate is via personal insults? Btw, I guess you forgot that is the first time you've told me that. ::) Edit: since he edited his reply below, I will add he has deleted all my retorts which have refuted his reply below (specifically refuting full rigidity, his claim of decreased degrees-of-freedom, and his claim that he isn't being disingenuous). He even deleted my attempt to add my retorts to my thread. I would add a link to my retorts (and I bet you can find them if you really want to), yet he would then likely delete this post or edit or some other infantile, weasel, trolling behavior. Enjoy the bliss. The edit I made which gmaxell refers to in his reply below is the definition of "seed" quoted above, as if he doesn't know the English language. Also he edited his upthread post to remove his large point size text that I quoted above. Good to see he is embarrassed and had to backtrack on his trolling. Title: Re: NSA and ECC Post by: gmaxwell on October 14, 2013, 05:56:13 PM Seed has a generic meaning. Is that the best FUD you can do to avoid addressing the point? There is nothing in the scheme that we use which can be generically described as a seed either. Our curve meets the SafeCurves definition of "Fully Rigid" (as I explained to you elsewhere by comparison to curve25519).Edits: Quote from: AnonyMint Btw, I guess you forgot that is the first time you've told me that. It isn't: I specifically addressed your transparency FUD when you were spewing it elsewhere on the forum: The parameters in secp256k1 (which is not a NIST selected curve, contrary to your repeated instance) are fixed entirely by performance considerations, similar to the Ed25519 work which you lauded up-thread. There (far) are fewer degrees of freedom in secp256k1 than in SHA1. As an aside: I've now removed AnonyMint from this thread. (Also, note that he edited the message after I responded to it, my quote is the version at the time I responded) Title: Re: NSA and ECC Post by: BurtW on December 22, 2013, 06:16:15 AM Presumably, since it was government work, it should be possible to FOIA any records they have relating to the procedures they used to generate those ECC parameters. Please go back and read this entire thread, especially the part where this exact idea was brought up and the part where I personally emailed the current committee head and did get some of the answers to our questions.BTW out of all the threads I have ever participated in this one is, by far, my favorite. Title: Re: NSA and ECC Post by: bluemeanie1 on December 22, 2013, 10:34:24 PM I've been reading up recently on the revelations that the NSA is subverting implementations/service providers to undermine various internet crypto standards (see this: http://www.theguardian.com/world/2013/sep/05/nsa-gchq-encryption-codes-security (http://www.theguardian.com/world/2013/sep/05/nsa-gchq-encryption-codes-security)). Now this has all of the basic hallmarks of a 'scare campaign' where people are led to believe that crypto techniques/mathmatics themselves are insecure rather than the truth that the NSA is attacking the services or implementations directly (much easier). Therefore I was ready to write this off as 'not relevant' to an open source peer reviewed protocol like Bitcoin. However, something Bruce Schneier (someone intimately familiar with the mathematics behind crypto algorithms) said has given me some concern. He is suggesting that the ECC constants have been manipulated to facilitate subversion (see his blog comment here: https://www.schneier.com/blog/archives/2013/09/the_nsa_is_brea.html#c1675929 (https://www.schneier.com/blog/archives/2013/09/the_nsa_is_brea.html#c1675929)). For his full essay, go here: https://www.schneier.com/essay-446.html (https://www.schneier.com/essay-446.html). Any thoughts on implications here we need to be concerned about? the fact is Elliptic Curve mathematics are a somewhat mysterious region of mathematical knowledge. They were used in the famous proof of Fermat's Last Theorem: http://en.wikipedia.org/wiki/Wiles%27_proof_of_Fermat%27s_Last_Theorem , thus it's not implausible to suggest that perhaps there are aspects to Elliptic Curves that are not public information. The Fermat Proof was incredibly complex and verbose. Note that Fermat's Last Theorem was only proven very recently, here's something interesting an Elliptic Curve is http://upload.wikimedia.org/math/9/2/b/92bc19343fd705e286b3954f528b0993.png while Fermat's Last Theorem is that no three positive integers a, b and c can satisfy the equation http://upload.wikimedia.org/math/d/6/b/d6b5906f4f141193833eb466cd0d4b83.png if n is an integer not equal to one or two. Elliptic Curve Cryptography relies on the supposed computational difficulty of the Discrete Logarithm Function. http://www.certicom.com/index.php/52-the-elliptic-curve-discrete-logarithm-problem Supposedly, according to modern public crypto knowledge, there are no shortcuts to solving this problem. As long as there are no shortcuts, then ECC remains secure. Interestingly, Fermat's Last Theorem was proven in 1993, and ECC came into widespread use around 2005 [1]. Coincidence? [1] although it was suggested earlier Title: Re: NSA and ECC Post by: withnail on December 23, 2013, 03:12:47 PM "somewhat mysterious region of mathematical knowledge"
no it is not. it might be so 100 years ago but not now. It is a generalization of ordinary arithmetic (ordinary arithmetic is arithmetic on a "flat line") and it is a major branch of present day math. See a mathematician's take on NSA backdoor http://jiggerwit.wordpress.com/2013/09/25/the-nsa-back-door-to-nist/ this will appear in AMS Notices. As a lot of folks have pointed out, it is unlikely that SHA-2 has been compromised, since to compromise it you need genuine breakthrough in math (say, progress towards P vs NP, if you know what it is) not just sloppiness with malicious intentions. I mean if you can crack SHA-2 then getting insanely rich is the least you can do; try domination of the world, dude. Title: Re: NSA and ECC Post by: bluemeanie1 on December 23, 2013, 07:28:48 PM I tried to supply more detail for my post last night, but literally moments after I mentioned Elliptic Curve Cryptography and Wiles' Proof Of Fermat's Last Theorem, bitcointalk.org went down. Later that night, my website was hacked by a fairly sophisticated hacker.
Anyway, let me establish a few things. At this point in history it's fairly clear and obvious that NSA et al. are sabotaging not only our cryptographic technology, but our KNOWLEDGE OF CRYPTOGRAPHY. I don't see it as a coincidence that just years after a very talented mathematician spends at least 5 years exploring the arcane properties of elliptic curves, suddenly, Elliptic Curves become fully accepted methods for cryptography for public use. I've suggested some months ago that the NSA sabotages our cryptography and most on here thought the idea was ridiculous, today there is PROOF they are doing just that. For starters most people on here really don't know much about this subject and there is quite a bit of posturing going on. It's an open forum so that's to be expected. People pretending to correct other people, while making no useful input to the conversation and posting links of which they don't even understand the content. Even this thread is riddled with math mistakes that these people posing as experts seem to miss. For example: Well, the point must lie on the curve, so it must satisfy y2 = x3 + 7 (mod p). this equation is wrong and doesn't even work for the point G on the Elliptic Curve. Gy2 = 3032293323238629131397093708741358902059848828670291900490749632219017966501037 851199852273530008094362088328117359813331037184493212192641774435470977600 (http://www.wolframalpha.com/input/?i=55066263022277343669578718895168534326250603453777594175500187360389116729240+^+2) Gx3 +7 mod p = 28522264212469271830151728101663411104844712793013968865831688505076558508754 (http://www.wolframalpha.com/input/?i=32670510020758816978083085130507043184471273380659243275938904335757337482424+^+3+%2B+7+mod+115792089237316195423570985008687907853269984665640564039457584007908834671663) no one is checking anything, most on here are just chattering away on subjects to look knowledgeable. If anyone on here knew about EC math(there are few), they would have pointed out that to express the equation over field http://upload.wikimedia.org/math/0/b/1/0b100eeff3848a15dbb46291e7fe52ad.png(integers) for instance the equation is: y = ( x3 + 7 ) (1/2) (mod p) having established that... the fact is if you followed the progression of events it was indeed highly suspect. If you review the Fermat Proof you will see that there are people who can process elliptic curves in ways that make just about anything that has ever been discussed on here look pedestrian by comparison. If you want to understand how the Fermat Proof works, you can start by studying the works of Galois. http://en.wikipedia.org/wiki/Galois , as well as mastering half a dozen higher order math concepts: cover and lift, finite field, isomorphism, surjective function, decomposition group, j-invariant of elliptic curves, Abelian group, Grossencharacter, L-function, abelian variety, Jacobian, Néron model, Gorenstein ring, Torsion subgroup (including torsion points on elliptic curves here[20] and here[21]), Congruence subgroup, eigenform, Character (mathematics), Irreducibility (mathematics), Image (mathematics), dihedral, Conductor, Lattice (group), Cyclotomic field, Cyclotomic character, Splitting of prime ideals in Galois extensions (and decomposition group and inertia group), Quotient space, Quotient group , meanwhile people on here are claiming all these things are simple, but not offering any useful pointers on all the things the people in this very thread got wrong so far. In other words- useless nerd. Part of what the NSA et. al. have been doing for some time is making our crypto algorithms APPEAR simpler than they are. I sometimes suspect that this Bruce Schneier job. As I have established, the theory of elliptic curves is very deep and very complex, but rarely do you ever hear any of these ideas applied to our crypto systems. Once in a while they pop up and the 'experts' pretend as if this is some surprising event that came out of left field. For quite some time, our spying agencies have sequestered mathematicians, pay them and gag them to create this kind of fog of understanding around whatever math we use to hide our information. This tradition goes back at least to Alan Turing. Title: Re: NSA and ECC Post by: BurtW on December 23, 2013, 08:38:51 PM You may have a point in your post above but claiming that y2 (mod p) does not equal x3 + 7 (mod p) for G is incorrect. Your calculations above are totally incorrect. Using the same web site you tried to use the correct calculations are:
Hex: P = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8 Dec: P = 115792089237316195423570985008687907853269984665640564039457584007908834671663 Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240 Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424 (Gy)2 (mod p) = http://www.wolframalpha.com/input/?i=%2832670510020758816978083085130507043184471273380659243275938904335757337482424%5E2%29+%28mod+115792089237316195423570985008687907853269984665640564039457584007908834671663%29 = 32748224938747404814623910738487752935528512903530129802856995983256684603122 (Gx)3 + 7 (mod p) = http://www.wolframalpha.com/input/?i=%2855066263022277343669578718895168534326250603453777594175500187360389116729240%5E3+%2B+7%29+%28mod+115792089237316195423570985008687907853269984665640564039457584007908834671663%29 = 32748224938747404814623910738487752935528512903530129802856995983256684603122 [EDIT] at least I know this is all correct ;) Title: Re: NSA and ECC Post by: BurtW on December 23, 2013, 08:52:31 PM Maybe you did not realize that:
y2 = x3 + 7 (mod p). is shorthand for: y2 (mod p) = x3 + 7 (mod p) y = ( x3 + 7 ) (1/2) (mod p) is identical to the equation you corrected. Title: Re: NSA and ECC Post by: bluemeanie1 on December 23, 2013, 09:07:08 PM Maybe you did not realize that: y2 = x3 + 7 (mod p). is shorthand for: y2 (mod p) = x3 + 7 (mod p) because knowing that your correct equation: y = ( x3 + 7 ) (1/2) (mod p) is identical to the equation you corrected. on what planet would that be? Title: Re: NSA and ECC Post by: jackjack on December 23, 2013, 09:40:19 PM Maybe you did not realize that: y2 = x3 + 7 (mod p). is shorthand for: y2 (mod p) = x3 + 7 (mod p) because knowing that your correct equation: y = ( x3 + 7 ) (1/2) (mod p) is identical to the equation you corrected. on what planet would that be? Tell me you're trolling Title: Re: NSA and ECC Post by: marcus_of_augustus on December 23, 2013, 09:48:57 PM He has history ... and seriously guys please keep the pissing contests to the other sections of the forum.
Need I remind you this is a "Development and Technical Discussion" topic, we have enough crap to wade through elsewhere. Title: Re: NSA and ECC Post by: rarkenin on December 23, 2013, 09:51:19 PM On this planet. The design of ECC revolves around age-old mathematical definitions and theorems with that kind of shorthand, so accept it here.
Title: Re: NSA and ECC Post by: withnail on December 23, 2013, 10:12:28 PM Maybe you did not realize that: y2 = x3 + 7 (mod p). is shorthand for: y2 (mod p) = x3 + 7 (mod p) because knowing that your correct equation: y = ( x3 + 7 ) (1/2) (mod p) is identical to the equation you corrected. on what planet would that be? I don't know which part the rhetorical question refers to. If it is about the notation then indeed it is standard. If it is about the square root part, then in principle it is OK, although one needs to note that not every element in a finite field is a square (after all this is what Gauss' quadratic reciprocity law is all about) and hence one would implicitly agree that the equation is meaningful if and only if the righthand side is defined. This in math literature is called "abuse of notation". The list of "advanced math topics" you listed above, well, they are all very advanced for high school kids, but only half of them are advanced in any sense for a math major, and none of them should be advanced for a math graduate. Of course a topic like L-functions really emcompasses a large area of research and is still ongoing, so some part of it is really advanced. For instance, you favorite Fermat's last theorem is not really considered very advanced anymore these days, but things related to the BSD conjecture (google it) is very advanced even for professionals. You know I am a professional, don't you? ;D Title: Re: NSA and ECC Post by: bluemeanie1 on December 23, 2013, 10:13:36 PM On this planet. The design of ECC revolves around age-old mathematical definitions and theorems with that kind of shorthand, so accept it here. if Maybe you did not realize that: y2 = x3 + 7 (mod p). is shorthand for: y2 (mod p) = x3 + 7 (mod p) how do I say y2 = x3 + 7 (mod p)? in this idiotic language this person just made up that is understood by precisely one person? have fun kids, the adults can't spend all day playing around on the internet. have a nice day. Title: Re: NSA and ECC Post by: withnail on December 23, 2013, 10:21:12 PM I did not read through all the craps above, but why are people talking about elliptic curves? SHA-256 is not based on elliptic curve cryptography, it is simple prime factorisation cryptography, am I mistaken?
Title: Re: NSA and ECC Post by: bluemeanie1 on December 23, 2013, 10:23:00 PM I did not read through all the craps above, but why are people talking about elliptic curves? SHA-256 is not based on elliptic curve cryptography, it is simple prime factorisation cryptography, am I mistaken? might have something to do with the title of this thread: "NSA and ECC". ECC stands for Elliptic Curve Cryptography. Title: Re: NSA and ECC Post by: rarkenin on December 23, 2013, 10:26:17 PM I did not read through all the craps above, but why are people talking about elliptic curves? SHA-256 is not based on elliptic curve cryptography, it is simple prime factorisation cryptography, am I mistaken? Neither really. ECC is indeed based on elliptic curves. It's used to sign transactions in the bitcoin blockchain. SHA is not prime factorization. That's RSA, just about. SHA is its own little thing, based on AFAIK a Merkle-Damgard construction. Title: Re: NSA and ECC Post by: withnail on December 23, 2013, 10:35:41 PM I did not read through all the craps above, but why are people talking about elliptic curves? SHA-256 is not based on elliptic curve cryptography, it is simple prime factorisation cryptography, am I mistaken? Neither really. ECC is indeed based on elliptic curves. It's used to sign transactions in the bitcoin blockchain. SHA is not prime factorization. That's RSA, just about. SHA is its own little thing, based on AFAIK a Merkle-Damgard construction. yeah? I am a newbie when it comes to the inner workings of the bitcoin code, but I am a bit concerned since NIST standard for pseudo-random number generation based on ECC is compromised. Perhaps bitcoin uses an unadulterated version? Title: Re: NSA and ECC Post by: rarkenin on December 23, 2013, 10:39:05 PM AFAIK Bitcoin is unadulterated.
Title: Re: NSA and ECC Post by: bluemeanie1 on December 23, 2013, 10:55:35 PM Oh ok. Do you reckon there is any need to switch bitcoin over to Ed25519 at the moment? Or do you trust the magic numbers in Secp256k1? If it's possible for any of these ECC systems to be intentionally insecure that would require some profound math which is unknown to the public. If we assume the existence of profound math which is unknown to the public, I do not see a reason to also assume Ed25519 is more secure.Including it would be a significant burden (a fast ecc signature validation implementation is not simple code, and would not overlap with our existing code) which would carry its own risks. this is an example of what I'm talking about. this 'profound math unknown to the public' does exist! Just look at the Fermat Proof. It shows that there is an extensive field of knowledge about elliptic curves(developed just a few years before the ECC came into widespread use). Granted, more people today know these things, but even now it is considered arcane knowledge. As a matter of fact, much of the Fermat Proof deals exactly with the area of theory that ECC resides. Are these things pure coincidences? My point being, it is very possible that the NSA has secret knowledge of elliptic curves. Title: Re: NSA and ECC Post by: BurtW on December 23, 2013, 10:57:44 PM My point being, it is very possible that the NSA has secret knowledge of elliptic curves. It is also possible they do not, right? Title: Re: NSA and ECC Post by: jackjack on December 23, 2013, 11:04:16 PM On this planet. The design of ECC revolves around age-old mathematical definitions and theorems with that kind of shorthand, so accept it here. if Maybe you did not realize that: y2 = x3 + 7 (mod p). is shorthand for: y2 (mod p) = x3 + 7 (mod p) how do I say y2 = x3 + 7 (mod p)? in this idiotic language this person just made up that is understood by precisely one person? Only 100% of mathematicians use that notation You should track them down to make them learn your notation have fun kids, the adults can't spend all day playing around on the internet. have a nice day. Yeah let the kids play together and never come backTitle: Re: NSA and ECC Post by: rarkenin on December 23, 2013, 11:07:55 PM You just can't take modulo on one side since that's not fundamentally following from theorems and not going to lead you anywhere. The (mod 9) annotation applies to the entire line, putting it into modular arithmetic. It looks like you screwed up and now hate us all for your own stupidity.
Title: Re: NSA and ECC Post by: NewLiberty on December 26, 2013, 09:33:04 PM I did not read through all the craps above, but why are people talking about elliptic curves? SHA-256 is not based on elliptic curve cryptography, it is simple prime factorisation cryptography, am I mistaken? Neither really. ECC is indeed based on elliptic curves. It's used to sign transactions in the bitcoin blockchain. SHA is not prime factorization. That's RSA, just about. SHA is its own little thing, based on AFAIK a Merkle-Damgard construction. yeah? I am a newbie when it comes to the inner workings of the bitcoin code, but I am a bit concerned since NIST standard for pseudo-random number generation based on ECC is compromised. Perhaps bitcoin uses an unadulterated version? Read this whole thread. It isn't that long and will give you answers, even as a newbie. Title: Re: NSA and ECC Post by: justusranvier on January 21, 2014, 06:30:18 PM For the sake of completeness I'd like to point out that:
Quote from: Dan John Goyo recalls that two former employees generated the domain parameters. In no way implies:Quote from: Dan In particular, no external organization, including any that some now asperse with backdoor insertion, generated the parameters. It's not possible to prove that an employee of a given organization is not also an employee of a different organization. The latter statement might be true, but we'll never know since it's unfalsifiable. Title: Re: NSA and ECC Post by: Altoidnerd on January 21, 2014, 09:50:03 PM Quote My point being, it is very possible that the NSA has secret knowledge of elliptic curves. It is very possible santa claus does as well. Only evidence for a vulnerability is notable in this regard. Title: Re: NSA and ECC Post by: AnonyMint on June 29, 2014, 04:30:31 PM Seed has a generic meaning. Is that the best FUD you can do to avoid addressing the point? There is nothing in the scheme that we use which can be generically described as a seed either. Our curve meets the SafeCurves definition of "Fully Rigid" (as I explained to you elsewhere by comparison to curve25519).Edits: Quote from: AnonyMint Btw, I guess you forgot that is the first time you've told me that. It isn't: I specifically addressed your transparency FUD when you were spewing it elsewhere on the forum: The parameters in secp256k1 (which is not a NIST selected curve, contrary to your repeated instance) are fixed entirely by performance considerations, similar to the Ed25519 work which you lauded up-thread. There (far) are fewer degrees of freedom in secp256k1 than in SHA1. secp256k1 is "somewhat rigid" not "fully rigid": http://safecurves.cr.yp.to/rigid.html https://bitcointalk.org/index.php?topic=151120.msg3131916#msg3131916 Also some of us don't want to trust an industry consortium. http://secg.org/ http://www.secg.org/collateral/sec2_final.pdf Given that efficiency claims have been arbitrary. http://safecurves.cr.yp.to Quote Subsequent research (and to some extent previous research) showed that essentially all of these efficiency-related decisions were suboptimal, that many of them actively damaged efficiency, and that some of them were bad for security. Title: Re: NSA and ECC Post by: gmaxwell on June 30, 2014, 12:54:06 AM secp256k1 is "somewhat rigid" not "fully rigid": Incorrect. The parameters _are_ minimal, there is a script to reproduce them from first principles _in this very thread (https://bitcointalk.org/index.php?topic=289795.msg3206788#msg3206788)_.Quote Given that efficiency claims have been arbitrary. There is nothing arbitrary about it, with use of the efficient endomorphism enabled libsecp256k1 is (AFAIK) the fastest implementation of ECDSA verification on general purpose hardware in existence, obviously if it contained an implementation of schnorr signatures over this group they'd be even faster due to being able to skip the modular inversion too, but as far as I know it is unparalleled by any other actual ECDSA implementation with comparable security...Nor are there any obviously strictly superior alternatives, _even today_ much less several years ago, the best contenders have a cofactor greater than one— allowing a non-prime group at a minimum costs several bits of security (e.g. equal or worse to the rho improvement from the efficient endomorphism), and depend on implementation hacks that require private keys to be in a particular sub-group, making things like multiparty key derivation (e.g. BIP32) incompatible with those implementations. Title: Re: NSA and ECC Post by: hashman on July 01, 2014, 09:31:02 AM secp256k1 is "somewhat rigid" not "fully rigid": Incorrect. The parameters _are_ minimal, there is a script to reproduce them from first principles _in this very thread (https://bitcointalk.org/index.php?topic=289795.msg3206788#msg3206788)_.Thanks as usual gmaxwell.. hanging on your words here! Well this one doesn't explain G so it's not all the parameters.. and out of all of the the generator point is the only one that looks like an obvious question "where did this come from?" I also hadn't noticed until recently that b (=7 in secp256k1) can be replaced with anything at all with no effect on all bitcoin operations.. so definitely a waste of time investigating that choice further. . Title: Re: NSA and ECC Post by: gmaxwell on July 01, 2014, 10:32:15 AM Well this one doesn't explain G so it's not all the parameters.. and out of all of the the generator point is the only one that looks like an obvious question "where did this come from?" Yes, but G is security irrelevant for our normal usage in Bitcoin (and generally, except for some contrived examples— e.g. where I need to convince you that I don't know the discrete log of some nothing up my sleeve point X (X!=G), and I picked X long in advance and selected G so that I knew the discrete log of X, but this is contrived and isn't something that I can think of any reason we'd do in Bitcoin.The term 'fully rigid' comes from safer curves and I complained to DJB that his own curves had no obvious specification for their generator on the site, and (after some back and forth there I gave him a sage implementation of an 'attack' in a contrived protocol) the page was revised to include an argument why the base point selection is irrelevant "What about rigid choices of base points? For each curve considered by SafeCurves, the specified base point is a generator of the specified subgroup. SafeCurves does not place restrictions on the choice of this base point [...]". Title: Re: NSA and ECC Post by: AnonyMint on July 04, 2014, 01:28:08 PM @gmaxwell, in any case I think you'd have to admit that one-time use Lamport signatures employing a cryptographic hash with considerable cryptanalysis history, would be more immune (against theft of coins) to potential and unknown number theoretic vulnerabilities whether planted or discovered after the fact.
I acknowledge we had the prior discussion in some thread wherein you pointed out that the public keys are hashed so aren't known until the spend, so the attacker would only have a short period of time to issue a double-spend. Nevertheless as the mining has become incredibly centralized (one or two pools control 50+% of hashrate last time I checked), taken together with potential vulnerabilities that might reduce attack to trivial calculation, then the hash may not be enough protection since the public key is revealed when the transaction is sent. Title: Re: NSA and ECC Post by: cypherdoc on July 08, 2014, 11:16:37 PM Quote and specifically about these five constants: They've already been explained in this thread. In summary:The first constant we care about is p; TierNolan already explained that one. It's the From that we can explain b. If we're searching for the smallest combination of a and b that results in a prime order elliptic curve, a = 0 and b = 7 is the first one. I don't know the specifics on why a and b should be small (probably GLV optimization), but they aren't suspicious regardless. N is just the order of the elliptic curve; no explanation needed. The last piece of the puzzle is the choice for G. Since the order of the elliptic curve is prime, we can pick any point on the curve (except infinity), and get a group with the same order (i.e. there are no subgroups). Why SECG picked the particular G they did is unexplained. However, there is no reason to believe any G is weaker or stronger than any other G (against a compliant ECDSA verifier). I would guess that either G is totally random, or it has sentimental meaning to the author(s). Since the curve is not weak to any publicly known attacks, and the constants are not suspicious, then what else are we looking for with regards to secp256k1? why does the wiki constant for p say this: p = 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1 instead of this: p = 2^256 - 2^32 - 977 ? https://en.bitcoin.it/wiki/Secp256k1 Title: Re: NSA and ECC Post by: DeathAndTaxes on July 09, 2014, 12:22:34 AM They are equivalent: 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1 = 977.
The former provides some clarity on how 977 was chosen ("nothing up my sleeve" http://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number). Title: Re: NSA and ECC Post by: Peter R on July 09, 2014, 01:22:28 AM I understand that secp256k1's p has the form
2^256 - 2^32 - x because this is a sort of generalized Mersenne prime and the "32" means that modular reductions can be carried out efficiently with 32-bit words (http://www.springerreference.com/docs/html/chapterdbid/317073.html). But I still don't understand why x = 977. Mathematica tells me that there were lots of choices: Code: Table[If[PrimeQ[2^256 - 2^32 - x], Print[x]], {x, 1, 2000}];Why not 263 = 2^8 + 2^2 + 2^1 + 2^0? It's the smallest. Earlier in the thread it was pointed out by TierNolan that 977 is the closest choice smaller than 1024, but why does 1024 matter? For example, 487 is closer to 512 than 977 is to 1024. Title: Re: NSA and ECC Post by: cypherdoc on July 09, 2014, 01:58:58 AM I understand that secp256k1's p has the form 2^256 - 2^32 - x because this is a sort of generalized Mersenne prime and the "32" means that modular reductions can be carried out efficiently with 32-bit words (http://www.springerreference.com/docs/html/chapterdbid/317073.html). But I still don't understand why x = 977. Mathematica tells me that there were lots of choices: Code: Table[If[PrimeQ[2^256 - 2^32 - x], Print[x]], {x, 1, 2000}];Why not 263 = 2^8 + 2^2 + 2^1 + 2^0? It's the smallest. Earlier in the thread it was pointed out by TierNolan that 977 is the closest choice smaller than 1024, but why does 1024 matter? For example, 487 is closer to 512 than 977 is to 1024. What do words have to do with these calculations? Title: Re: NSA and ECC Post by: BurtW on July 09, 2014, 03:00:59 AM I understand that secp256k1's p has the form I believe the choice of 977 was explained up thread. Something about a (future?) optimization if it is as close to 1024 as possible without going over 1024 therefore the choice is 977.2^256 - 2^32 - x because this is a sort of generalized Mersenne prime and the "32" means that modular reductions can be carried out efficiently with 32-bit words (http://www.springerreference.com/docs/html/chapterdbid/317073.html). But I still don't understand why x = 977. Mathematica tells me that there were lots of choices: Code: Table[If[PrimeQ[2^256 - 2^32 - x], Print[x]], {x, 1, 2000}];Why not 263 = 2^8 + 2^2 + 2^1 + 2^0? It's the smallest. Earlier in the thread it was pointed out by TierNolan that 977 is the closest choice smaller than 1024, but why does 1024 matter? For example, 487 is closer to 512 than 977 is to 1024. Title: Re: NSA and ECC Post by: Peter R on July 09, 2014, 04:46:01 AM I believe the choice of 977 was explained up thread. Something about a (future?) optimization if it is as close to 1024 as possible without going over 1024 therefore the choice is 977. I noticed that line of reasoning but it didn't make sense to me in the same way that the explanation for the 2^32 term did. The "32" corresponds to the bit width of physical registers on many processors. The "10" relates to ?? In other words, how does 977 being close to but smaller than 1024 (2^10) lead to more optimizations than 487 being close to but smaller than 512 (2^9)? I'm not actually worried; I think secp256k1 is highly secure. I'm just wondering if I'm missing something... Title: Re: NSA and ECC Post by: BurtW on July 09, 2014, 08:40:34 AM From the letter I got from Dan Brown, shown here:
https://bitcointalk.org/index.php?topic=289795.msg3183975#msg3183975 We have: Quote 2. The defining field size p seems to be a 256-bit prime of the special form 2^256-s where s is small. This form is for efficiency. I am not sure why this particular value of s is chosen, because I expect that smaller s could be found. Nevertheless, there does not seem to be too much wiggle room in this choice of s, because s itself also has a special form: s = 2^32 + t, where t < 1024. I would not be surprised if s was the smallest value of this form, but I did not check. In any case, there are no known weak classes of prime order field for elliptic curves. So t could be any of the values you found less than 1024. I don't know but if all of them are equally safe then the guy/group that decided may have just picked 977 just because it was the largest number less than 1024 and no other reason. It would be interesting to track down the person that was there in the room when that decision was made. Alas, all of my attempts to do that have failed. Title: Re: NSA and ECC Post by: Peter R on July 10, 2014, 02:46:20 AM From the letter I got from Dan Brown, shown here: https://bitcointalk.org/index.php?topic=289795.msg3183975#msg3183975 We have: Quote 2. The defining field size p seems to be a 256-bit prime of the special form 2^256-s where s is small. This form is for efficiency. I am not sure why this particular value of s is chosen, because I expect that smaller s could be found. Nevertheless, there does not seem to be too much wiggle room in this choice of s, because s itself also has a special form: s = 2^32 + t, where t < 1024. I would not be surprised if s was the smallest value of this form, but I did not check. In any case, there are no known weak classes of prime order field for elliptic curves. So t could be any of the values you found less than 1024. I don't know but if all of them are equally safe then the guy/group that decided may have just picked 977 just because it was the largest number less than 1024 and no other reason. It would be interesting to track down the person that was there in the room when that decision was made. Alas, all of my attempts to do that have failed. Thanks Burt. It's interesting to note that 263 would have been the choice for t that Dan Brown expected. My new theory is that they just screwed up a minus sign somewhere and picked 977 instead of 263 lol. Title: Re: NSA and ECC Post by: DeathAndTaxes on July 10, 2014, 03:51:58 AM Well Bitcoin could always support a second curve. A curve over F(p) where P = 2^256 - 2^32 - 236, call it Secp256k2 :). I know I am highly original in my naming convention.
Title: Re: NSA and ECC Post by: justusranvier on July 10, 2014, 03:54:32 AM Well Bitcoin could always support a second curve. A curve over F(p) where P = 2^256 - 2^32 - 236, call it Secp256k2 :). I know I am highly original in my naming convention. One of these: http://safecurves.cr.yp.to/bada55.htmlTitle: Re: NSA and ECC Post by: cypherdoc on July 10, 2014, 04:47:09 AM Well Bitcoin could always support a second curve. A curve over F(p) where P = 2^256 - 2^32 - 236, call it Secp256k2 :). I know I am highly original in my naming convention. One of these: http://safecurves.cr.yp.to/bada55.htmlYep, those are badass Title: Re: NSA and ECC Post by: ThomasCrowne on July 10, 2014, 08:32:35 AM Regarding the OP.
"If the NSA coulda you can bet your bottom dollar they woulda!" -me Title: Re: NSA and ECC Post by: hashman on July 11, 2014, 09:09:29 PM Well Bitcoin could always support a second curve. A curve over F(p) where P = 2^256 - 2^32 - 236, call it Secp256k2 :). I know I am highly original in my naming convention. One of these: http://safecurves.cr.yp.to/bada55.htmlYep, those are badass I can't help but notice that not one of the safecurves.cr.yp.to families are implemented by openssl: $ openssl ecparam -list_curves secp112r1 : SECG/WTLS curve over a 112 bit prime field secp112r2 : SECG curve over a 112 bit prime field secp128r1 : SECG curve over a 128 bit prime field secp128r2 : SECG curve over a 128 bit prime field secp160k1 : SECG curve over a 160 bit prime field secp160r1 : SECG curve over a 160 bit prime field secp160r2 : SECG/WTLS curve over a 160 bit prime field secp192k1 : SECG curve over a 192 bit prime field secp224k1 : SECG curve over a 224 bit prime field secp224r1 : NIST/SECG curve over a 224 bit prime field secp256k1 : SECG curve over a 256 bit prime field secp384r1 : NIST/SECG curve over a 384 bit prime field secp521r1 : NIST/SECG curve over a 521 bit prime field prime192v1: NIST/X9.62/SECG curve over a 192 bit prime field prime192v2: X9.62 curve over a 192 bit prime field prime192v3: X9.62 curve over a 192 bit prime field prime239v1: X9.62 curve over a 239 bit prime field prime239v2: X9.62 curve over a 239 bit prime field prime239v3: X9.62 curve over a 239 bit prime field prime256v1: X9.62/SECG curve over a 256 bit prime field sect113r1 : SECG curve over a 113 bit binary field sect113r2 : SECG curve over a 113 bit binary field sect131r1 : SECG/WTLS curve over a 131 bit binary field sect131r2 : SECG curve over a 131 bit binary field sect163k1 : NIST/SECG/WTLS curve over a 163 bit binary field sect163r1 : SECG curve over a 163 bit binary field sect163r2 : NIST/SECG curve over a 163 bit binary field sect193r1 : SECG curve over a 193 bit binary field sect193r2 : SECG curve over a 193 bit binary field sect233k1 : NIST/SECG/WTLS curve over a 233 bit binary field sect233r1 : NIST/SECG/WTLS curve over a 233 bit binary field sect239k1 : SECG curve over a 239 bit binary field sect283k1 : NIST/SECG curve over a 283 bit binary field sect283r1 : NIST/SECG curve over a 283 bit binary field sect409k1 : NIST/SECG curve over a 409 bit binary field sect409r1 : NIST/SECG curve over a 409 bit binary field sect571k1 : NIST/SECG curve over a 571 bit binary field sect571r1 : NIST/SECG curve over a 571 bit binary field c2pnb163v1: X9.62 curve over a 163 bit binary field c2pnb163v2: X9.62 curve over a 163 bit binary field c2pnb163v3: X9.62 curve over a 163 bit binary field c2pnb176v1: X9.62 curve over a 176 bit binary field c2tnb191v1: X9.62 curve over a 191 bit binary field c2tnb191v2: X9.62 curve over a 191 bit binary field c2tnb191v3: X9.62 curve over a 191 bit binary field c2pnb208w1: X9.62 curve over a 208 bit binary field c2tnb239v1: X9.62 curve over a 239 bit binary field c2tnb239v2: X9.62 curve over a 239 bit binary field c2tnb239v3: X9.62 curve over a 239 bit binary field c2pnb272w1: X9.62 curve over a 272 bit binary field c2pnb304w1: X9.62 curve over a 304 bit binary field c2tnb359v1: X9.62 curve over a 359 bit binary field c2pnb368w1: X9.62 curve over a 368 bit binary field c2tnb431r1: X9.62 curve over a 431 bit binary field wap-wsg-idm-ecid-wtls1: WTLS curve over a 113 bit binary field wap-wsg-idm-ecid-wtls3: NIST/SECG/WTLS curve over a 163 bit binary field wap-wsg-idm-ecid-wtls4: SECG curve over a 113 bit binary field wap-wsg-idm-ecid-wtls5: X9.62 curve over a 163 bit binary field wap-wsg-idm-ecid-wtls6: SECG/WTLS curve over a 112 bit prime field wap-wsg-idm-ecid-wtls7: SECG/WTLS curve over a 160 bit prime field wap-wsg-idm-ecid-wtls8: WTLS curve over a 112 bit prime field wap-wsg-idm-ecid-wtls9: WTLS curve over a 160 bit prime field wap-wsg-idm-ecid-wtls10: NIST/SECG/WTLS curve over a 233 bit binary field wap-wsg-idm-ecid-wtls11: NIST/SECG/WTLS curve over a 233 bit binary field wap-wsg-idm-ecid-wtls12: WTLS curvs over a 224 bit prime field Oakley-EC2N-3: IPSec/IKE/Oakley curve #3 over a 155 bit binary field. Not suitable for ECDSA. Questionable extension field! Oakley-EC2N-4: IPSec/IKE/Oakley curve #4 over a 185 bit binary field. Not suitable for ECDSA. Questionable extension field! What's the consensus here.. should we not be using openssl? Should we use openssl and add the safecurves by hand? Or just ignore the supposed vulnerabilities listed by the safecurves website and continue to use one of the above curves like secp256k1? Title: Re: NSA and ECC Post by: gmaxwell on July 11, 2014, 11:28:20 PM I can't help but notice that not one of the safecurves.cr.yp.to families are implemented by openssl: All of the curves most preferred on there are ones that DJB made. Some of them have no implementation in software, only the curve25519/ed25519 stuff has any non-trivial deployment at all.While the analysis there is generally good and thoughtful, I believe that the page crosses the line into being a bit ... uh .. marketing motivated. This has been discussed before several times— e.g. it cites several points which are irrelevant to us (e.g. the elegator encoding), are 'one time costs' completeness making a correct implementation take some more work, and other points which are compensated by increased security of secp256k1 in other respects. (E.g. the efficient endomorphism for secp256k1 that yields very fast verification for our curve reduces security by a couple bits, which is pretty comparable to the cofactor of 8 in ed25519 that reduces their security by a couple bits (actually slightly more). Whats implemented in openssl has more or less nothing to do with what bitcoin uses, and getting rid of openssl wouldn't change it. Title: Re: NSA and ECC Post by: hashman on July 14, 2014, 12:52:07 AM Yes, but G is security irrelevant for our normal usage in Bitcoin (and generally, except for some contrived examples— e.g. where I need to convince you that I don't know the discrete log of some nothing up my sleeve point X (X!=G), and I picked X long in advance and selected G so that I knew the discrete log of X, but this is contrived and isn't something that I can think of any reason we'd do in Bitcoin. For normal usage I am considering a signature verification operation which just for fun is: sig = ((HashOfThingToSign + EccMultiply(Gx,Gy,RandNum)%N*privKey)*(modinv(RandNum,N))) % N If I stare at this long enough I can convince myself you are right.. and the more I deal with really big numbers like these the more I think it is bulletproof. but I'd still love to hear some story about where these lovely numbers Gx and Gy come from, 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8 or 55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424 I've heard: "value of G should be generated canonically (verifiably random)." Title: Re: NSA and ECC Post by: AnonyMint on July 14, 2014, 01:14:17 AM I can't help but notice that not one of the safecurves.cr.yp.to families are implemented by openssl: All of the curves most preferred on there are ones that DJB made. Some of them have no implementation in software, only the curve25519/ed25519 stuff has any non-trivial deployment at all.While the analysis there is generally good and thoughtful, I believe that the page crosses the line into being a bit ... uh .. marketing motivated. This has been discussed before several times— e.g. it cites several points which are irrelevant to us (e.g. the elegator encoding), are 'one time costs' completeness making a correct implementation take some more work, and other points which are compensated by increased security of secp256k1 in other respects. (E.g. the efficient endomorphism for secp256k1 that yields very fast verification for our curve reduces security by a couple bits, which is pretty comparable to the cofactor of 8 in ed25519 that reduces their security by a couple bits (actually slightly more). Whats implemented in openssl has more or less nothing to do with what bitcoin uses, and getting rid of openssl wouldn't change it. If I am not mistaken, aren't you moving the goal posts in that you appear to be talking about bits of security which is orthogonal to what he was talking about verifiable randomness of the parameters to eliminate any suspicion of a backdoor? Title: Re: NSA and ECC Post by: gmaxwell on July 14, 2014, 05:19:57 AM If I am not mistaken, aren't you moving the goal posts in that you appear to be talking about bits of security which is orthogonal to what he was talking about verifiable randomness of the parameters to eliminate any suspicion of a backdoor? Unlike the NIST curves the Bitcoin curve is not "random": There is no parameter question there. The comments on the safer curves page addresses a whole host of analysis points, so with the randomness off the table I was speaking to some of the other things where there are meaningful engineering differences between Bitcoin and curve25519.Title: Re: NSA and ECC Post by: AnonyMint on July 14, 2014, 05:35:53 AM Okay but my point remains that I think the person you were replying to appeared to be ask why not use bada55 curves which claim verifiable randomness of the parameters and the post from Peter R preceding it asked why 977 was arbitrarily chosen and appears (?) no sufficient justification has been provided.
I hope we agree there is a distinct difference between "arbitrarily or even justifiably chosen" and "verifiably random"? Edit: note I did not dig into the bada55 curves to make sure I understand what they mean by verifiable random. So I am not sure if it is distinct. I am just speaking conceptually above. Title: Re: NSA and ECC Post by: gmaxwell on July 14, 2014, 11:12:32 AM Edit: note I did not dig into the bada55 curves to make sure I understand what they mean by verifiable random. So I am not sure if it is distinct. I am just speaking conceptually above. The bada55 curves were created to show the worthlessness "verifyably random" (at least as done by NIST), they are "random"— but the authors (ab)used the process to make sure the parameters had "bada55" in them. You are supposed to imagine an attacker armed with a mathematical breakthrough who could compromise 1/2^24 random curves doing the same kind of seed grinding.I didn't believe the post I was responding to was at all talking about the bada55 curves, the subject had drifted and the post was talking about the curves recommended by the site. Presumably if I failed to answer the authors question he could respond. Title: Re: NSA and ECC Post by: hashman on July 14, 2014, 02:21:30 PM Edit: note I did not dig into the bada55 curves to make sure I understand what they mean by verifiable random. So I am not sure if it is distinct. I am just speaking conceptually above. The bada55 curves were created to show the worthlessness "verifyably random" (at least as done by NIST), they are "random"— but the authors (ab)used the process to make sure the parameters had "bada55" in them. You are supposed to imagine an attacker armed with a mathematical breakthrough who could compromise 1/2^24 random curves doing the same kind of seed grinding.I didn't believe the post I was responding to was at all talking about the bada55 curves, the subject had drifted and the post was talking about the curves recommended by the site. Presumably if I failed to answer the authors question he could respond. Thanks, if you mean me yes I was not talking specifically about the bada55 curves, though thanks for explaining how they are badass :) I was looking for some insight into whether any of the vulnerabilities mentioned by Daniel J. Bernstein and Tanja Lange are serious and why nobody has added more curves to the openssl default list. I'm not too concerned with the 977 parameter but to the untrained eye of for example an investor the presence of unexplained numbers in the generator could still be troubling. Earlier in the thread we heard: SECG chair Dan Brown: 3. The base point G is something I cannot explain, [snip]... I strongly doubt that G is malicious, [snip] OK so I took him a little bit out of context but you can see how someone researching the security of the DSA of bitcoin might not feel 100% satisfied. It's a pity we can't do better and determine where they really came from but I guess whoever picked those points probably had no idea they would one day secure millions of people's finances. Shall we offer a bounty? Title: Re: NSA and ECC Post by: gmaxwell on July 15, 2014, 12:37:45 PM how someone researching the security of the DSA of bitcoin might not feel 100% satisfied Please read the thread. We explain in detail how choice of G is not relevant for our own applications. If you don't believe that, DJB also argues why choice of G is usually irrelevant on safe-curves (SafeCurves does not place restrictions on the choice of this base point. If there is a "weak" base point W allowing easy computations of discrete logarithms, then ECDLP is weak for every base point (http://safecurves.cr.yp.to/rigid.html))— an argument he added after I emailed him and suggested he add an explanation of his own G choice, which he did not previously provide... it took me inventing a novel attack against a contrived hypothetical protocol (not Bitcoin) where choice of G actually mattered to convince him to say anything at all.Title: Re: NSA and ECC Post by: cypherdoc on July 15, 2014, 04:50:58 PM In making its recommendations, the VCAT specifically addressed NIST's interactions with the National Security Agency (NSA). The report states, "NIST may seek the advice of the NSA on cryptographic matters but it must be in a position to assess it and reject it when warranted."
"The report also recommends that NIST review the current requirement for interaction with the NSA and recommends changes in instances where it "hinders [NIST's] ability to independently develop the best cryptographic standards." "We will continue to work with the best cryptography experts in the world, both inside and outside of government," said May. "At the same time, we recognize and agree with the VCAT that NIST must strengthen its in-house cryptography capabilities to ensure we can reach independent conclusions about the merits of specific algorithms or standards." http://www.nist.gov/public_affairs/releases/crypto-review-071414.cfm Title: Re: NSA and ECC Post by: DeathAndTaxes on July 15, 2014, 06:07:34 PM Edit: note I did not dig into the bada55 curves to make sure I understand what they mean by verifiable random. So I am not sure if it is distinct. I am just speaking conceptually above. The bada55 curves were created to show the worthlessness "verifyably random" (at least as done by NIST), they are "random"— but the authors (ab)used the process to make sure the parameters had "bada55" in them. You are supposed to imagine an attacker armed with a mathematical breakthrough who could compromise 1/2^24 random curves doing the same kind of seed grinding.That is the rub isn't it. Any "verifiably random" curve which is just a deterministic process starting from an arbitrary and claimed (but completely unprovable) random seed value is worthless. I mean provably fair bitcoin casinos are better constructed in their proof and transparency. This is the logic one is suppose to accept from NIST/NSA: Generate "random value" -> curve parameters = insecure because one could just pick "random values" until they find one which produces a weak curve. Generate one* "random value" -> seed -> deterministic process -> curve parameters are the first valid curve = "secure" because look it is a deterministic process. Yes NIST claims the seed for secp256r1 was the first and only one they generated. It might actually be but it can't be proven and they know it can't be proven so the "provably random" is just "random". It is no different than NIST just randomly generating curves directly. In both cases you have to trust that what they published as the "first valid curve" is actually the first valid curve and not the first valid but weak curve" after they attempted and discarded quadrillions of other more secure curves. Trusting the seed is actually random is no different than trusting the parameters are random. Now doing something like the following the term "provably random" might actually mean something: Code: note: this is just psuedocode. The process is completely deterministic, each curve can be documented as to the reason for rejection. The criteria for "valid" can be closely analyzed. Some may choose to use a lower nonce curve that while less efficient is purer in the sense that the window for manipulation by setting criteria is small. Others may select a higher nonce curve which is more efficient than a lower nonce one. The probability that the hash of an incrementing nonce would in sequence produce a curve that looks secure but has a flaw NIST/NSA is aware of before a strong curve is remote. There would be some value in random curves using a generator that is open and transparent. Now this isn't a very hard concept and NIST/NSA have lots of very smart people so I am sure someone had to think of something functionally similar to this. It wasn't used and instead they created a dog and pony show about deterministic curve generation from a random seed which does nothing but make the process more opaque. So the obvious question becomes why? Title: Re: NSA and ECC Post by: gmaxwell on July 15, 2014, 06:35:24 PM It is no different than NIST just randomly generating curves directly. Well, it is different— say there is a class of weak curves known to the NSA but the weakness requires you to select a one in 2^128 set of parameters... without a pre-image attack on the hash function you couldn't use one of these 'random' procedures to pick such a curve.If the weakness was a 2^32 one— you could, thus the bada55 curves. The scheme you suggest has a weakness in that there are potentially too many plausible schemes. For example, an attacker might use their ability to choose a hash function and value serializations to choose insecure parameters. What I would prefer is a scheme that worked like this: (1) Take a scheme like yours, but give it an initialization seed as an input. The scheme should be designed such that all acceptable parameters are equally likely to be selected (assuming good properties of some cryptographic hash). (2) Publish the scheme, and ask various mutual distrusting parties to compute random values R_0, R_1 ... and each of them publishes X_n = H(R_n). (3) Take the H(scheme) and X_n and commit to them in a bitcoin transaction, publicly announce this commitment. (4) 100s blocks after the commitment, take the block hash 100 blocks after the comment and have the parties release their R_x numbers. H(scheme||R_n...||block hash) The idea here is that up to the preimage resistance of the hash function, to influence the selection you must both compromise all the distrusting parties AND do a huge amount of sha256 computation. But thats all for where a random selection can't be avoided... the "fixed by security/performance considerations" approach is probably best. An interesting question how reasonable it would be to formalize all those considerations in order to combine the approaches... since DJB's claims notwithstanding, there really is many degrees of freedom in within that (otherwise secp256k1 _and_ ed25519 wouldn't both exist). Title: Re: NSA and ECC Post by: DeathAndTaxes on July 15, 2014, 07:23:58 PM If the weakness was a 2^32 one— you could, thus the bada55 curves. ... The scheme you suggest has a weakness in that there are potentially too many plausible schemes. For example, an attacker might use their ability to choose a hash function and value serializations to choose insecure parameters. That is true however it is about reducing the window as much as possible. The number of permutations of possible hash functions and serializations is relatively small compared to the number of "random" seeds that can be produced at "reasonable" cost by an intelligence agency. Thanks for pointing out that the system used by Certicom/NIST does have some merit in preventing the exploit of weak parameters which occur rarely. Those flawed parameters which occur less frequently than than 1 in > 2^96 are probably not exploitable . The problem is that computing 2^80 curves (or at least 2^64) would be possible and would allow exploit of even weaknesses which occur rarely. If (and it may not be possible) one found a weakness which occurs at least one in 2^80 random parameters an agency could produce a "verifiably random" curve that they have pre-compromised. It may not even be a scenario where they know the curve can be compromised but rather generating a huge number of curves and then having their top minds pick the curves they believe show the most promise for cryptanalysis in the future. So while it would be possible for one to try more than one permutation of an incrementing nonce curve the window would be significantly smaller right? How many possible serializations and hash functions could be used. 2^20? 2^10? less? Of those how many would be greeted with suspicion? There are only a handful of hashing algorithms which would be seen as logical choices. Likewise with serialization, simple is better and more transparent. Using some exoteric serialization would be seen with suspicion "why did you do x,y,z when you could just do x". Still I do like the idea of using the blockchain to act as both a timestamp mechanism and very difficult to manipulate entropy source. Instead of a single block hash the computational cost can be easily increased by using a sequence of n block hashes starting from the the block containing the commitment txn (block_x). Since miners are in fact distrusting parties you could optionally avoid the need for step #2. H(scheme||blockhash_x || blockhash_x+1 ... || blockhash_x+n-1) or H(scheme||R_n...||blockhash_x || blockhash_x+1 ... || blockhash_x+n-1) I also like the idea that you can in essence do a trial run. Pretest the system to be sure it works as expected without knowing what the official seed is going to be. Get peer reviewed feedback and then commit it to the blockchain and wait for the entropy source to be generated. Now everyone can use the generator to produce curves in an open and transparent manner. I know I would trust it more than any other so called "provably random" curves. Title: Re: NSA and ECC Post by: gmaxwell on July 15, 2014, 07:46:42 PM Instead of a single block hash the computational cost can be easily increased by using a sequence of n block hashes starting from the the block containing the commitment txn (block_x). Since miners are in fact distrusting parties you could optionally avoid the need for step #2. I think since each block already hashes the prev block we already have that property without doing it explicitly! :)There is an argument that it should be using toeplitz hashing with as much data as possible as an input as the entropy extraction, but there is a tradeoff that more "unusual crypto" in the scheme makes it harder to trust. Quote I also like the idea that you can in essence do a trial run. Pretest the system to be sure it works as expected without knowing what the official seed is going to be. Get peer reviewed feedback and then commit it to the blockchain and wait for the entropy source to be generated. I know I would trust it more than any other so called "provably random" curves. Yep. The idea is that you lay out all the "influence" parts up front, then use the blockchain to 'cut the deck' in a hard to rig way. Even if someone didn't personally witness the process they still have the blockchain POW as evidence for a minimum computational cost in retrying. E.g. doing 2^70 blockchain work multiple times to rig it might be conceivable, but not the 2^128 work required to do 2^58 retries. The next annoying property is that you want to have curve-acceptability tests but too many tests and perhaps you are actually testing for weakness-included. E.g. DJB would perhaps have you test that there exists a specific mapping to nearly uniform scalars (e.g. elegator), but perhaps that guarantees a vulnerability. Or in our case secp256k1 is selected with the efficient endomorphism to permit the GLV method for faster operations. Title: Re: NSA and ECC Post by: gmaxwell on July 15, 2014, 08:00:52 PM A neat variation is that for the parties that compute H(R_n) you make H() really be g*R_n on bitcoin, and require that the transaction commuting to the scheme actually be doing a coinjoin with the R_n parties, putting up some non-trivial amount of bitcoin to be held under each of the private keys for the duration of mining time. This means that if any of the parties leak their R_n value to a miner (or other R_n) holders during the mining interval so that the miner could attempt to grind a solution with a particular output then someone could instead steal their coins... so the integrity of the process would be bonded. The bonds could potentially be very large.
Title: Re: NSA and ECC Post by: DeathAndTaxes on July 15, 2014, 08:11:34 PM I think since each block already hashes the prev block we already have that property without doing it explicitly! :) On second thought I believe you are right. My thinking was it is unlikely but possible someone (maybe NSA with their super secret hashing farm) could attempt multiple blocks and discard them until it found one which produced a weak curve. In essence stacking the deck. I failed to realize that adding more blocks wouldn't help as they are indirectly included in the prev_block and to change the seed the attacker would still only need to change the last block. So control over block n is the only thing which matters. Honestly it is probably a non-issue as even if the attacker rented a majority of the hashrate and discarded blocks he is paying a cost per block and eventually he will fall to far behind. As you indicate below Also there is the human element while it isn't doesn't disprove manipulation, any manipulation would be very easy to spot. If there suddenly was a 238 block reorg which replaced the magic block well it might be prudent to not use the results. :) Quote Yep. The idea is that you lay out all the "influence" parts up front, then use the blockchain to 'cut the deck' in a hard to rig way. That is a good analogy. Quote Even if someone didn't personally witness the process they still have the blockchain POW as evidence for a minimum computational cost in retrying. E.g. doing 2^70 blockchain work multiple times to rig it might be conceivable, but not the 2^128 work required to do 2^58 retries. Agreed. That should be ~2^66 not 2^70 right? I assume it represents the average amount of work needed to solve one block and thus created and test one set of curve parameters for vulnerabilities. Quote The next annoying property is that you want to have curve-acceptability tests but too many tests and perhaps you are actually testing for weakness-included. E.g. DJB would perhaps have you test that there exists a specific mapping to nearly uniform scalars (e.g. elegator), but perhaps that guarantees a vulnerability. Or in our case secp256k1 is selected with the efficient endomorphism to permit the GLV method for faster operations. Agreed and I would lean towards minimal validity testing. Still if some people decide to be more restrictive the use of a standard how to cheat generator is still beneficial. For example lets say curve 283 is minimally valid but it doesn't have some properties that DJB et all see are important for security. If they can convince people to not used curve 283 (the first valid nonce) and instead use curve 13,288 (the first nonce which passes all his tests) than more power to him. If nothing else it puts them both out there on an equal playing field. If the additional criteria worth the possibility of manipulating the selection by bypassing other currently valid curves? Title: Re: NSA and ECC Post by: DeathAndTaxes on July 15, 2014, 08:13:50 PM A neat variation is that for the parties that compute H(R_n) you make H() really be g*R_n on bitcoin, and require that the transaction commuting to the scheme actually be doing a coinjoin with the R_n parties, putting up some non-trivial amount of bitcoin to be held under each of the private keys for the duration of mining time. This means that if any of the parties leak their R_n value to a miner (or other R_n) holders during the mining interval so that the miner could attempt to grind a solution with a particular output then someone could instead steal their coins... so the integrity of the process would be bonded. The bonds could potentially be very large. Awesome. A provable "secrecy bond". Title: Re: NSA and ECC Post by: hashman on July 19, 2014, 09:14:44 PM how someone researching the security of the DSA of bitcoin might not feel 100% satisfied Please read the thread. We explain in detail how choice of G is not relevant for our own applications. If you don't believe that, DJB also argues why choice of G is usually irrelevant on safe-curves (SafeCurves does not place restrictions on the choice of this base point. If there is a "weak" base point W allowing easy computations of discrete logarithms, then ECDLP is weak for every base point (http://safecurves.cr.yp.to/rigid.html))— an argument he added after I emailed him and suggested he add an explanation of his own G choice, which he did not previously provide... it took me inventing a novel attack against a contrived hypothetical protocol (not Bitcoin) where choice of G actually mattered to convince him to say anything at all.I understand how the choice of G can be irrelevant. However this fact is irrelevant to my question: why were they chosen as such? My argument here is for better marketing. I'm sure you understand the "nothing up your sleeve" motivation.. sure having something in your sleeve is not going to have relevance to ECC but the idea is to still show that there is nothing in your sleeve. My question stands: where did those numbers come from? The probable answer is that they came from a random number generator that was lying around at the time, probably initialized by the date. It's too bad this wasn't documented. Title: Re: NSA and ECC Post by: gmaxwell on July 20, 2014, 04:09:46 AM My question stands: where did those numbers come from? The probable answer is that they came from a random number generator that was lying around at the time, probably initialized by the date. It's too bad this wasn't documented. Seems no one knows, but likewise— who created the paper the printed version of the spec was printed on? What software was used to spell check the document? Who came up with the shortname for the curve? maybe they were a secret NSA plant! :P if you want to go down the rat whole of _provably_ irrelevant things there is no end to it. Ultimately people who are not technically sophisticated are at risk of being FUDed by people who are dishonest or themselves confused, but no amount of good process can prevent that. Title: Re: NSA and ECC Post by: hashman on July 24, 2014, 01:10:06 AM Seems no one knows, but likewise— who created the paper the printed version of the spec was printed on? What software was used to spell check the document? Who came up with the shortname for the curve? maybe they were a secret NSA plant! :P if you want to go down the rat whole of _provably_ irrelevant things there is no end to it. I'd like to clarify this terminology a bit. When I think of your three examples, yes the word irrelevant comes to mind. The issuer of the paper, the spell checker, and the short name of the curve, are all things which I don't even need to know to use bitcoin or to write my own client. One might even say "provably" irrelevant for that reason, in that the relevance in question here implied by the forum in which we are using. However I personally would avoid using that terminology, perhaps because of my mathematics background. However the G points are hardly irrelevant in this context, please correct me if I am wrong. If I don't know them I can't validate TXs, can't sign TXs, and so I can't use bitcoin at all. Every ECC operation in bitcoin requires every bit of G to be exactly right. When you say G is provably irrelevant, I can only assume (and I'd rather not hence this reply) that you mean a choice of G cannot effect the ability of an attacker to brute force a private key. While there are convincing arguments of that in this thread, I wouldn't call any of them a proof. AFAIK the difficulty of discrete logs, on elliptic curves, or even the difficulty in factoring large numbers, has not been proven and probably a proof that these things cannot be done in polynomial time would be equivalent to a proof that P!=NP. Title: Re: NSA and ECC Post by: gmaxwell on July 24, 2014, 01:58:24 AM When you say G is provably irrelevant, I can only assume (and I'd rather not hence this reply) that you mean a choice of G cannot effect the ability of an attacker to brute force a private key. While there are convincing arguments of that in this thread, I wouldn't call any of them a proof. You can transform any pubkey on any G to a pubkey on another generator by means of addition. In particular, if there is some bad generator O where you can compute the log of Ox for arbitrary x easily, one can use find the discrete log of Gx as log_O(Gx)/log_O(G) mod order. One doesn't need to prove anything about the hardness of the discrete log to just show the arithmetic relation that if on a curve discrete log is insecure with respect to one generator then discrete log is insecure with respect to all generators of that group.A better example that I could have given is how the byte order is chosen (big endian or little endian). You surely can't create an implementation without knowing how to deseralize the bytes, but byte order isn't relevant to security. Title: Re: NSA and ECC Post by: AnonyMint on August 19, 2014, 10:44:44 AM Schneier is justified in his recommendation, IMHO. But there is one bright spot: even if the standard ECDSA curves were broken in this way, if you do not reuse addresses it would not concern you as no public key or ciphertext is available until the coins are spent. So don't re-use bitcoin addresses (you shouldn't anyway). I understand that in Bitcoin the public address is a cryptographic hash of the public key thus the public key is obscured often until it is spent. In addition to reusing addresses (https://bitcoin.org/en/developer-guide#avoiding-key-reuse), doesn't also the ability to sign a message to prove you own some coins reveal the public key? And the adversary has a lot of time to attempt to crack your public key then (but no publicly known feasible attacks exist at this time). Also I made the point else where recently that since one Bitcoin pool sometimes controls near to or more than 50% of the hashrate, then intercepting a transaction before it is on the blockchain is feasible. In this case, I understand ECDSA would still need to be more than just a little bit broken because the time to crack would be measured in minutes, thus a quantum computer would need much more than just a few qubits or the number theoretic breakage would need to be severe. Title: Re: NSA and ECC Post by: brainless on August 27, 2023, 12:43:58 PM I am very satisfied with his answers. The only thing left is to find out (if we can) is exactly how the random parameters were selected. I did a quick check on this assumption Quote Nevertheless, there does not seem to be too much wiggle room in this choice of s, because s itself also has a special form: s = 2^32 + t, where t < 1024. I would not be surprised if s was the smallest value of this form, but I did not check. The test code finds all primes of the form p = 2^256 - 2^32 - t where t < 1024. Code: import java.math.BigInteger; The result is Code: fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffef9 (t = 263) The prime for t = 977 is the one that was selected for the curve. It is the highest t that is lower than 1024. pls check is your above found p is correct or wrong, or maybe i am doing calc wrong, advice here is your selection P 115792089237316195423570985008687907853269984665640564039457584007908834672377 115792089237316195423570985008687907853269984665640564039457584007908834672281 115792089237316195423570985008687907853269984665640564039457584007908834672279 115792089237316195423570985008687907853269984665640564039457584007908834672153 115792089237316195423570985008687907853269984665640564039457584007908834671901 115792089237316195423570985008687907853269984665640564039457584007908834671691 115792089237316195423570985008687907853269984665640564039457584007908834671663 115792089237316195423570985008687907853269984665640564039457584007908834671591 115792089237316195423570985008687907853269984665640564039457584007908834671583 115792089237316195423570985008687907853269984665640564039457584007908834671301 115792089237316195423570985008687907853269984665640564039457584007908834671033 115792089237316195423570985008687907853269984665640564039457584007908834670671 go to this ecc calc and fill following details http://www.christelbach.com/eccalculator.aspx p = 115792089237316195423570985008687907853269984665640564039457584007908834671583 a = 0 b = 7 px = 115301655840403608332148854465368444683257224081574702572138639602380667382125 py = 103799472776126890762485670055583971987299536955028941653349419016168013365384 qx = 52658829913452240860711750781961153521895864895692055913373819304893658879667 qy = 33725064078989563529395744584539757872089003472888698368252453876478056770565 and press P + Q you will see B=7 changed to b = 32267065813313537246304986561842436172856576584501774751507060994620472625355 mean your Prime value for fit in formula Y2=X3+AX+B , p prime Failed save try all with P value to change, only p value original got by 977 will work, and b =7 will never change on that testing site can you all start again to find correct P other then - 977, which stand for b =7 or advice me where i am wrong Title: Re: NSA and ECC Post by: vjudeu on August 27, 2023, 02:48:10 PM Quote can you all start again to find correct P other then - 977, which stand for b =7 The next value is far away from that, it is this one:Code: p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffeb1f9 Code: p=previous_prime(0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f) Code: p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffef9 Quote or advice me where i am wrong You are simply checking p-value only, while you should also check n-value. Recently, garlonicon had the same problem, see this topic: https://bitcointalk.org/index.php?topic=5464362.0Also note that p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffeb1f9 does not allow you to use n-value to form another curve, that will give you p-value back. But it is acceptable, because for other curves it is also not the case, it is just a coincidence that secp256k1 has such property. Title: Re: NSA and ECC Post by: Nellyj200x on August 27, 2023, 11:34:49 PM I wrote a small program that allows you to quickly check if a Bitcoin file has a transaction in it, and also checks whether it is a valid Bitcoin file and whether it is locked.
https://github.com/Humble2020/BitcoinFile-Verifier Title: Re: NSA and ECC Post by: brainless on August 28, 2023, 12:06:39 PM pls check is your above found p is correct or wrong, or maybe i am doing calc wrong, advice here is your selection P 115792089237316195423570985008687907853269984665640564039457584007908834672377 115792089237316195423570985008687907853269984665640564039457584007908834672281 115792089237316195423570985008687907853269984665640564039457584007908834672279 115792089237316195423570985008687907853269984665640564039457584007908834672153 115792089237316195423570985008687907853269984665640564039457584007908834671901 115792089237316195423570985008687907853269984665640564039457584007908834671691 115792089237316195423570985008687907853269984665640564039457584007908834671663 115792089237316195423570985008687907853269984665640564039457584007908834671591 115792089237316195423570985008687907853269984665640564039457584007908834671583 115792089237316195423570985008687907853269984665640564039457584007908834671301 115792089237316195423570985008687907853269984665640564039457584007908834671033 115792089237316195423570985008687907853269984665640564039457584007908834670671 go to this ecc calc and fill following details http://www.christelbach.com/eccalculator.aspx p = 115792089237316195423570985008687907853269984665640564039457584007908834671583 a = 0 b = 7 px = 115301655840403608332148854465368444683257224081574702572138639602380667382125 py = 103799472776126890762485670055583971987299536955028941653349419016168013365384 qx = 52658829913452240860711750781961153521895864895692055913373819304893658879667 qy = 33725064078989563529395744584539757872089003472888698368252453876478056770565 and press P + Q you will see B=7 changed to b = 32267065813313537246304986561842436172856576584501774751507060994620472625355 mean your Prime value for fit in formula Y2=X3+AX+B , p prime Failed save try all with P value to change, only p value original got by 977 will work, and b =7 will never change on that testing site can you all start again to find correct P other then - 977, which stand for b =7 or advice me where i am wrong [/quote] Question is below is simple formula for use P to substract 2 point, there is no n value involve, p4 = int(2**256 - 2**32 - 977) dx = (x1 - x2) % p4 dy = (y1 - ((p)-y2)) % p4 c1 = (dy * gmpy2.invert(dx, p4)) % p4 cu = dy * gmpy2.invert(dx, p4) % p4 Rx = (((c1*c1)%p4) - x2 - x1) % p4 Ry = ((c1*((x2 - Rx))) - y3) % p4 print (Rx , Ry) # 6 sub, 3 mul, 1 inv print (hex(Rx), hex(Ry)) if P we choose from your generated P list as above you mention, results goes wrong, and even its fail to comply with B = 7 Title: Re: NSA and ECC Post by: brainless on August 31, 2023, 04:52:17 PM Quote can you all start again to find correct P other then - 977, which stand for b =7 The next value is far away from that, it is this one:Code: p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffeb1f9 Code: p=previous_prime(0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f) Code: p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffef9 Quote or advice me where i am wrong You are simply checking p-value only, while you should also check n-value. Recently, garlonicon had the same problem, see this topic: https://bitcointalk.org/index.php?topic=5464362.0Also note that p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffeb1f9 does not allow you to use n-value to form another curve, that will give you p-value back. But it is acceptable, because for other curves it is also not the case, it is just a coincidence that secp256k1 has such property. Can we reverse this script, like we insert N for search P, in series search |
