Bitcoin Forum
November 04, 2024, 11:38:01 AM *
News: Latest Bitcoin Core release: 28.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: 1 2 3 4 5 6 7 8 9 10 11 12 [All]
  Print  
Author Topic: NSA and ECC  (Read 48795 times)
natb (OP)
Newbie
*
Offline Offline

Activity: 28
Merit: 12


View Profile
September 07, 2013, 06:17:08 PM
Merited by ABCbits (6), o_e_l_e_o (4), nutildah (1)
 #1

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).

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). For his full essay, go here: https://www.schneier.com/essay-446.html.

Any thoughts on implications here we need to be concerned about?
Mike Hearn
Legendary
*
expert
Offline Offline

Activity: 1526
Merit: 1134


View Profile
September 07, 2013, 06:51:58 PM
Merited by ABCbits (1)
 #2

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.
natb (OP)
Newbie
*
Offline Offline

Activity: 28
Merit: 12


View Profile
September 07, 2013, 07:38:44 PM
Last edit: September 07, 2013, 10:49:47 PM by natb
Merited by ABCbits (1)
 #3

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.
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
September 07, 2013, 09:58:23 PM
Merited by ABCbits (1)
 #4

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.
maaku
Legendary
*
expert
Offline Offline

Activity: 905
Merit: 1012


View Profile
September 07, 2013, 10:09:33 PM
Merited by ABCbits (2), vapourminer (1)
 #5

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.

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
natb (OP)
Newbie
*
Offline Offline

Activity: 28
Merit: 12


View Profile
September 07, 2013, 11:02:44 PM
 #6

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.
etotheipi
Legendary
*
expert
Offline Offline

Activity: 1428
Merit: 1093


Core Armory Developer


View Profile WWW
September 08, 2013, 01:31:55 AM
Last edit: September 08, 2013, 05:54:44 AM by etotheipi
Merited by ABCbits (1)
 #7

In case you don't follow slashdot, there was an article today from John Gilmore 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.


Founder and CEO of Armory Technologies, Inc.
Armory Bitcoin Wallet: Bringing cold storage to the average user!
Only use Armory software signed by the Armory Offline Signing Key (0x98832223)

Please donate to the Armory project by clicking here!    (or donate directly via 1QBDLYTDFHHZAABYSKGKPWKLSXZWCCJQBX -- yes, it's a real address!)
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
September 08, 2013, 02:34:32 AM
Last edit: September 08, 2013, 02:48:35 AM by gmaxwell
Merited by ABCbits (2)
 #8

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. Tongue )

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. Sad  (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.
markm
Legendary
*
Offline Offline

Activity: 2996
Merit: 1121



View Profile WWW
September 08, 2013, 05:17:02 AM
Last edit: September 08, 2013, 05:33:12 AM by markm
 #9

In case you don't follow slashdot, there was an article today from John Gilmore 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?

Browser-launched Crossfire client now online (select CrossCiv server for Galactic  Milieu)
Free website hosting with PHP, MySQL etc: http://hosting.knotwork.com/
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
September 08, 2013, 01:26:34 PM
Last edit: September 08, 2013, 01:49:36 PM by gmaxwell
 #10

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.
So I went and looked at the actual seeds because I wanted to see if I could perhaps reproduce the secp256k1 curve through low entropy methods...

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?!)
 
maaku
Legendary
*
expert
Offline Offline

Activity: 905
Merit: 1012


View Profile
September 08, 2013, 05:43:25 PM
 #11

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.

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
September 08, 2013, 09:26:29 PM
 #12

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.
maaku
Legendary
*
expert
Offline Offline

Activity: 905
Merit: 1012


View Profile
September 08, 2013, 10:23:48 PM
 #13

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.

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
niko
Hero Member
*****
Offline Offline

Activity: 756
Merit: 501


There is more to Bitcoin than bitcoins.


View Profile
September 09, 2013, 03:34:58 AM
 #14

Someone versed in ECC timeline should sift through the appropriate meeting minutes on certicom site, perhaps they already hint at how parameters were chosen.

They're there, in their room.
Your mining rig is on fire, yet you're very calm.
e4xit
Sr. Member
****
Offline Offline

Activity: 302
Merit: 250



View Profile
September 09, 2013, 09:45:16 AM
 #15

... 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?

Not your keys, not your coins.
CoinJoin, always.
jackjack
Legendary
*
Offline Offline

Activity: 1176
Merit: 1280


May Bitcoin be touched by his Noodly Appendage


View Profile
September 09, 2013, 10:03:16 AM
 #16

... 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

Own address: 19QkqAza7BHFTuoz9N8UQkryP4E9jHo4N3 - Pywallet support: 1AQDfx22pKGgXnUZFL1e4UKos3QqvRzNh5 - Bitcointalk++ script support: 1Pxeccscj1ygseTdSV1qUqQCanp2B2NMM2
Pywallet: instructions. Encrypted wallet support, export/import keys/addresses, backup wallets, export/import CSV data from/into wallet, merge wallets, delete/import addresses and transactions, recover altcoins sent to bitcoin addresses, sign/verify messages and files with Bitcoin addresses, recover deleted wallets, etc.
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
September 09, 2013, 10:15:53 AM
Merited by ABCbits (1)
 #17

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.   
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1137

All paid signature campaigns should be banned.


View Profile WWW
September 09, 2013, 11:50:22 AM
Last edit: September 09, 2013, 01:20:56 PM by BurtW
 #18

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.

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
fpgaminer
Hero Member
*****
Offline Offline

Activity: 560
Merit: 517



View Profile WWW
September 09, 2013, 12:16:20 PM
 #19

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 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?

Mike Hearn
Legendary
*
expert
Offline Offline

Activity: 1526
Merit: 1134


View Profile
September 09, 2013, 01:51:42 PM
 #20

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.

BTW what do you mean by "all lower values would have failed the test"? edit: never mind, you mean the seed selection algorithm would be: start at sha1(1), generate candidate parameters, check to see if they are usable, if not move on to sha1(2), etc.
Mike Hearn
Legendary
*
expert
Offline Offline

Activity: 1526
Merit: 1134


View Profile
September 09, 2013, 02:06:01 PM
Merited by ABCbits (2)
 #21

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.
Carlton Banks
Legendary
*
Offline Offline

Activity: 3430
Merit: 3080



View Profile
September 09, 2013, 02:12:13 PM
 #22


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.

Vires in numeris
markm
Legendary
*
Offline Offline

Activity: 2996
Merit: 1121



View Profile WWW
September 09, 2013, 02:36:34 PM
 #23

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-

Browser-launched Crossfire client now online (select CrossCiv server for Galactic  Milieu)
Free website hosting with PHP, MySQL etc: http://hosting.knotwork.com/
piotr_n
Legendary
*
Offline Offline

Activity: 2055
Merit: 1359


aka tonikt


View Profile WWW
September 09, 2013, 02:38:15 PM
Last edit: September 09, 2013, 03:28:08 PM by piotr_n
 #24

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.

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
markm
Legendary
*
Offline Offline

Activity: 2996
Merit: 1121



View Profile WWW
September 09, 2013, 02:41:48 PM
Last edit: September 09, 2013, 02:57:14 PM by markm
 #25

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-

Browser-launched Crossfire client now online (select CrossCiv server for Galactic  Milieu)
Free website hosting with PHP, MySQL etc: http://hosting.knotwork.com/
piotr_n
Legendary
*
Offline Offline

Activity: 2055
Merit: 1359


aka tonikt


View Profile WWW
September 09, 2013, 02:57:18 PM
 #26

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.

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
markm
Legendary
*
Offline Offline

Activity: 2996
Merit: 1121



View Profile WWW
September 09, 2013, 03:00:25 PM
Last edit: September 09, 2013, 03:19:23 PM by markm
 #27

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 (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-

Browser-launched Crossfire client now online (select CrossCiv server for Galactic  Milieu)
Free website hosting with PHP, MySQL etc: http://hosting.knotwork.com/
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1137

All paid signature campaigns should be banned.


View Profile WWW
September 09, 2013, 03:24:27 PM
 #28

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.

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
markm
Legendary
*
Offline Offline

Activity: 2996
Merit: 1121



View Profile WWW
September 09, 2013, 03:27:53 PM
Last edit: September 15, 2013, 05:19:07 PM by markm
 #29

Hmm I wonder how many colours of coloured coin it takes to [something something] a blockchain? Wink Cheesy

(You only need four whatzits to build a DNA strand? Hmm....)

Think like the game "sprouts".

(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-

Browser-launched Crossfire client now online (select CrossCiv server for Galactic  Milieu)
Free website hosting with PHP, MySQL etc: http://hosting.knotwork.com/
maaku
Legendary
*
expert
Offline Offline

Activity: 905
Merit: 1012


View Profile
September 09, 2013, 04:23:49 PM
 #30

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...

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
piotr_n
Legendary
*
Offline Offline

Activity: 2055
Merit: 1359


aka tonikt


View Profile WWW
September 09, 2013, 04:28:14 PM
Last edit: September 09, 2013, 05:39:35 PM by piotr_n
 #31

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 [...]
OK fine, but still: if they chose the constants to strengthen the algo, why is it then a secret how they came to these specific values?
Well at least, from what I see, nobody seems to have an idea why these constants and not some others... not even Bruce Schneier Smiley

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
September 09, 2013, 04:32:50 PM
 #32

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.
maaku
Legendary
*
expert
Offline Offline

Activity: 905
Merit: 1012


View Profile
September 09, 2013, 04:37:39 PM
 #33

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.

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
piotr_n
Legendary
*
Offline Offline

Activity: 2055
Merit: 1359


aka tonikt


View Profile WWW
September 09, 2013, 05:06:47 PM
 #34

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 Smiley

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
balanghai
Sr. Member
****
Offline Offline

Activity: 364
Merit: 253


View Profile
September 09, 2013, 05:38:37 PM
 #35

I think it's not just spying but also controlling. Roll Eyes
DeathAndTaxes
Donator
Legendary
*
Offline Offline

Activity: 1218
Merit: 1079


Gerald Davis


View Profile
September 09, 2013, 07:43:00 PM
Last edit: September 09, 2013, 08:40:03 PM by DeathAndTaxes
Merited by ABCbits (1)
 #36

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
ECDSA        256 bit*      256 bit   512 bits        (* 512 bit using uncompressed PubKeys which was the default in older versions of the client)
DSA         3027 bit       256 bit       512 bits
RSA         3072 bit      3072 bit      3072 bits

Example 2 input, 2 output transaction size
Code:
ECC               370 bytes (434 bytes w/ uncompressed PubKey)
DSA             1,074 bytes (~3x ECC)
RSA             1,714 bytes (~5x ECC)

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.
theymos
Administrator
Legendary
*
Offline Offline

Activity: 5376
Merit: 13368


View Profile
September 09, 2013, 08:13:28 PM
 #37

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?

1NXYoJ5xU91Jp83XfVMHwwTUyZFK64BoAD
Mike Hearn
Legendary
*
expert
Offline Offline

Activity: 1526
Merit: 1134


View Profile
September 09, 2013, 08:32:21 PM
 #38

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.
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
September 09, 2013, 08:56:44 PM
Last edit: September 09, 2013, 10:38:03 PM by gmaxwell
Merited by ABCbits (3)
 #39

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.

gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
September 09, 2013, 09:14:21 PM
 #40

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.

TierNolan
Legendary
*
Offline Offline

Activity: 1232
Merit: 1104


View Profile
September 09, 2013, 09:43:52 PM
 #41

Deterministic wallets are presumably also broken if ECC is broken?

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
September 09, 2013, 09:57:17 PM
 #42

Deterministic wallets are presumably also broken if ECC is broken?
Huh? What do you mean by determinstic wallets there?
TierNolan
Legendary
*
Offline Offline

Activity: 1232
Merit: 1104


View Profile
September 09, 2013, 10:03:16 PM
Last edit: September 09, 2013, 10:23:05 PM by TierNolan
 #43

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.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
natb (OP)
Newbie
*
Offline Offline

Activity: 28
Merit: 12


View Profile
September 09, 2013, 10:04:16 PM
 #44

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?

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.


gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
September 09, 2013, 10:28:45 PM
Merited by ABCbits (3)
 #45

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"Huh.

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 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.
Mike Hearn
Legendary
*
expert
Offline Offline

Activity: 1526
Merit: 1134


View Profile
September 10, 2013, 08:39:28 AM
 #46

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 Smiley
markm
Legendary
*
Offline Offline

Activity: 2996
Merit: 1121



View Profile WWW
September 11, 2013, 02:16:33 AM
Last edit: September 11, 2013, 02:40:39 AM by markm
 #47

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.

Browser-launched Crossfire client now online (select CrossCiv server for Galactic  Milieu)
Free website hosting with PHP, MySQL etc: http://hosting.knotwork.com/
niko
Hero Member
*****
Offline Offline

Activity: 756
Merit: 501


There is more to Bitcoin than bitcoins.


View Profile
September 11, 2013, 02:42:20 AM
 #48


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.

They're there, in their room.
Your mining rig is on fire, yet you're very calm.
markm
Legendary
*
Offline Offline

Activity: 2996
Merit: 1121



View Profile WWW
September 11, 2013, 02:48:27 AM
 #49

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-

Browser-launched Crossfire client now online (select CrossCiv server for Galactic  Milieu)
Free website hosting with PHP, MySQL etc: http://hosting.knotwork.com/
maaku
Legendary
*
expert
Offline Offline

Activity: 905
Merit: 1012


View Profile
September 11, 2013, 03:11:12 AM
 #50

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.

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
markm
Legendary
*
Offline Offline

Activity: 2996
Merit: 1121



View Profile WWW
September 11, 2013, 03:17:08 AM
 #51

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.)


Browser-launched Crossfire client now online (select CrossCiv server for Galactic  Milieu)
Free website hosting with PHP, MySQL etc: http://hosting.knotwork.com/
marcus_of_augustus
Legendary
*
Offline Offline

Activity: 3920
Merit: 2349


Eadem mutata resurgo


View Profile
September 11, 2013, 03:59:25 AM
 #52

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?

maaku
Legendary
*
expert
Offline Offline

Activity: 905
Merit: 1012


View Profile
September 11, 2013, 04:17:28 AM
 #53

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. 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.

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
markm
Legendary
*
Offline Offline

Activity: 2996
Merit: 1121



View Profile WWW
September 11, 2013, 06:01:50 AM
Last edit: September 11, 2013, 06:20:39 AM by markm
 #54

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-

Browser-launched Crossfire client now online (select CrossCiv server for Galactic  Milieu)
Free website hosting with PHP, MySQL etc: http://hosting.knotwork.com/
keystroke
Hero Member
*****
Offline Offline

Activity: 900
Merit: 1014


advocate of a cryptographic attack on the globe


View Profile
September 11, 2013, 06:21:31 AM
 #55

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. 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.)

"The difference between a castle and a prison is only a question of who holds the keys."
markm
Legendary
*
Offline Offline

Activity: 2996
Merit: 1121



View Profile WWW
September 11, 2013, 06:40:08 AM
 #56

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-

Browser-launched Crossfire client now online (select CrossCiv server for Galactic  Milieu)
Free website hosting with PHP, MySQL etc: http://hosting.knotwork.com/
maaku
Legendary
*
expert
Offline Offline

Activity: 905
Merit: 1012


View Profile
September 11, 2013, 07:36:47 AM
Last edit: September 11, 2013, 07:47:32 AM by maaku
 #57

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.

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
markm
Legendary
*
Offline Offline

Activity: 2996
Merit: 1121



View Profile WWW
September 11, 2013, 08:22:37 AM
Last edit: September 11, 2013, 08:34:57 AM by markm
 #58

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-

Browser-launched Crossfire client now online (select CrossCiv server for Galactic  Milieu)
Free website hosting with PHP, MySQL etc: http://hosting.knotwork.com/
maaku
Legendary
*
expert
Offline Offline

Activity: 905
Merit: 1012


View Profile
September 11, 2013, 08:36:29 AM
 #59

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.

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
markm
Legendary
*
Offline Offline

Activity: 2996
Merit: 1121



View Profile WWW
September 11, 2013, 08:44:44 AM
Last edit: September 11, 2013, 12:15:58 PM by markm
 #60

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

Browser-launched Crossfire client now online (select CrossCiv server for Galactic  Milieu)
Free website hosting with PHP, MySQL etc: http://hosting.knotwork.com/
runeks
Legendary
*
Offline Offline

Activity: 980
Merit: 1008



View Profile WWW
September 11, 2013, 08:11:16 PM
 #61

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.
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1137

All paid signature campaigns should be banned.


View Profile WWW
September 11, 2013, 10:16:36 PM
 #62


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.
Done.

Waiting for a response.

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
fpgaminer
Hero Member
*****
Offline Offline

Activity: 560
Merit: 517



View Profile WWW
September 12, 2013, 12:20:35 AM
Merited by ABCbits (3)
 #63

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)

To have an estimated security strength of 128-bits under quantum computing, Lamport signatures would be 256 * 256, which is 8KB. (Source)

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.

runeks
Legendary
*
Offline Offline

Activity: 980
Merit: 1008



View Profile WWW
September 12, 2013, 01:46:15 AM
 #64

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)

To have an estimated security strength of 128-bits under quantum computing, Lamport signatures would be 256 * 256, which is 8KB. (Source)
Thanks. Does that also apply when using a Merkle hash tree over your public keys? If I understand gmaxwell's description, a public key reusable at least 1024 times would be 128 bits + log2(1024)=10 * 128 bits = 176 bytes.

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.
As gmaxwell points out, security decreases for every additional signature you publish made with the same key. It's not like it disappears all at once.

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.
superduh
Hero Member
*****
Offline Offline

Activity: 602
Merit: 500


View Profile
September 12, 2013, 04:46:02 AM
 #65

sorry, but, what's the consensus

ok
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
September 12, 2013, 05:12:12 AM
Merited by ABCbits (3)
 #66

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)

To have an estimated security strength of 128-bits under quantum computing, Lamport signatures would be 256 * 256, which is 8KB. (Source)
In Bitcoin the public key would be part of the signature, when both are sent together there are several 'compression' schemes you can apply which allow you to avoid specify unneeded parts of the keys (since both are tree structured), you can do something which has 256 bits of QC security in about 11kbytes.  This also benefits reducing the size of the public key to a single hash— addresses would be no longer (or only somewhat longer, for 256 bit ones) than the addresses we use today.

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::.
Etlase2
Hero Member
*****
Offline Offline

Activity: 798
Merit: 1000


View Profile
September 12, 2013, 05:15:27 AM
 #67

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.

BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1137

All paid signature campaigns should be banned.


View Profile WWW
September 12, 2013, 04:10:40 PM
 #68

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.

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
jackjack
Legendary
*
Offline Offline

Activity: 1176
Merit: 1280


May Bitcoin be touched by his Noodly Appendage


View Profile
September 12, 2013, 04:17:05 PM
 #69

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

Own address: 19QkqAza7BHFTuoz9N8UQkryP4E9jHo4N3 - Pywallet support: 1AQDfx22pKGgXnUZFL1e4UKos3QqvRzNh5 - Bitcointalk++ script support: 1Pxeccscj1ygseTdSV1qUqQCanp2B2NMM2
Pywallet: instructions. Encrypted wallet support, export/import keys/addresses, backup wallets, export/import CSV data from/into wallet, merge wallets, delete/import addresses and transactions, recover altcoins sent to bitcoin addresses, sign/verify messages and files with Bitcoin addresses, recover deleted wallets, etc.
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1137

All paid signature campaigns should be banned.


View Profile WWW
September 12, 2013, 04:47:22 PM
 #70

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
Bummer.  I have been quoting the wrong number for almost two years now.  I sure wish someone had corrected me at some point.  Embarassing.

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
NewLiberty
Legendary
*
Offline Offline

Activity: 1204
Merit: 1002


Gresham's Lawyer


View Profile WWW
September 12, 2013, 07:02:56 PM
 #71


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.
Done.

Waiting for a response.

Thank you for this.

FREE MONEY1 Bitcoin for Silver and Gold NewLibertyDollar.com and now BITCOIN SPECIE (silver 1 ozt) shows value by QR
Bulk premiums as low as .0012 BTC "BETTER, MORE COLLECTIBLE, AND CHEAPER THAN SILVER EAGLES" 1Free of Government
piotr_n
Legendary
*
Offline Offline

Activity: 2055
Merit: 1359


aka tonikt


View Profile WWW
September 12, 2013, 07:12:46 PM
 #72


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.
Done.

Waiting for a response.

Thank you for this.
I'm betting they won't say.
Who's in? Smiley

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
September 12, 2013, 07:17:27 PM
 #73

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))
balanghai
Sr. Member
****
Offline Offline

Activity: 364
Merit: 253


View Profile
September 13, 2013, 03:18:54 PM
 #74

It would be cool if the engineers of the agency will mine altcoins for fun! Tongue
marcus_of_augustus
Legendary
*
Offline Offline

Activity: 3920
Merit: 2349


Eadem mutata resurgo


View Profile
September 14, 2013, 03:50:07 AM
 #75

It would be cool if the engineers of the agency will mine altcoins for fun! Tongue

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.

BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1137

All paid signature campaigns should be banned.


View Profile WWW
September 15, 2013, 11:18:38 AM
Last edit: September 15, 2013, 12:14:04 PM by BurtW
Merited by ABCbits (3)
 #76

Here is Jerry's response:

Quote
Hello Burt,

  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.
I have emailed all three authors.

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1137

All paid signature campaigns should be banned.


View Profile WWW
September 15, 2013, 12:02:07 PM
Last edit: September 15, 2013, 12:19:17 PM by BurtW
Merited by ABCbits (1)
 #77

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.


Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1137

All paid signature campaigns should be banned.


View Profile WWW
September 15, 2013, 12:27:05 PM
 #78

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.

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
jackjack
Legendary
*
Offline Offline

Activity: 1176
Merit: 1280


May Bitcoin be touched by his Noodly Appendage


View Profile
September 15, 2013, 12:40:16 PM
Last edit: September 15, 2013, 01:01:34 PM by jackjack
 #79

What is n?

Own address: 19QkqAza7BHFTuoz9N8UQkryP4E9jHo4N3 - Pywallet support: 1AQDfx22pKGgXnUZFL1e4UKos3QqvRzNh5 - Bitcointalk++ script support: 1Pxeccscj1ygseTdSV1qUqQCanp2B2NMM2
Pywallet: instructions. Encrypted wallet support, export/import keys/addresses, backup wallets, export/import CSV data from/into wallet, merge wallets, delete/import addresses and transactions, recover altcoins sent to bitcoin addresses, sign/verify messages and files with Bitcoin addresses, recover deleted wallets, etc.
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1137

All paid signature campaigns should be banned.


View Profile WWW
September 15, 2013, 12:51:35 PM
 #80

q = p = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
jackjack
Legendary
*
Offline Offline

Activity: 1176
Merit: 1280


May Bitcoin be touched by his Noodly Appendage


View Profile
September 15, 2013, 12:57:40 PM
Last edit: September 15, 2013, 01:38:40 PM by jackjack
 #81

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
p^2  - 1 % n = 9d671cd581c69bc5e697f5e1d12ab7e0bd57efff7678bda14d8f2b05a6047402
p^3  - 1 % n = ac7a8c3d903db4f5506b3cd06358dbb83c0356f1426f6154796949ebcaf2c963
p^4  - 1 % n = 4a9039c8e0cf1d2e546bf94562b4cdd3f931a37f7210ea3d2448e17471c13846
p^5  - 1 % n = 13257c198a85197265443fa89aac96ccdac5495c438984dc734659a59cd53681
p^6  - 1 % n = 48e1ad01feb908300c9be1bd9d9d7afe6b7d929d4954c6e73f5b35d6d38c8ce7
p^7  - 1 % n = 98c10d11ce5ba0e56349034ff8f0078cefdbb6462b5fadb02b77e6f9b15e63a0
p^8  - 1 % n = d450873664cc63bee8debf0810f4d3885087441407bdebb24ea9c33ab125b3cc
p^9  - 1 % n = 3763ce8ef848dd69408119a522e171d9ad2132e2eb349967bebdea391b96d024
p^10 - 1 % n = 3e07117dea68ea380611113c0988e37608059d1e8315f2dc397457536359b05a
p^11 - 1 % n = 1c16652e13748ed710097fe21c21c0ee3cf4dddca456a0d0900601f2c136da93
p^12 - 1 % n = 0a95c2539eba1d41b55552516bf5a46a2417109fb45813aecc859ccab824fd91
p^13 - 1 % n = a12715798e6b78096c12e8e73a5e1550e4184561cafbb5dbfb34ffcacbbeba6c
p^14 - 1 % n = 637f4698784525945df4080fa4334351f3a8137f01d1b2118cfe4f00a79ff5eb
p^15 - 1 % n = 4adf22895fd4ced7120a9b5bd1bedb0358b25073a52879da089054cef992b7f0
p^16 - 1 % n = cc43712c43c1b51af2e29020520ae03abccd9f5c3ffdeb0c94a585ac91372278
p^17 - 1 % n = ec473f03332198fd61c411b184e81b7093423dd2a245fa278e111aac1c9c7af6
p^18 - 1 % n = 2abbbd0960d7884ac5648cfd88fd6a8485fea0af29300256d827369ccd72db9b
p^19 - 1 % n = 4ced2137a0dc99c48f9203c2dd9b423fd31d95998b29165efb48bf868170e857
p^20 - 1 % n = ac95279e81042a93568de45d91f29ccdd83acb8097ec611ba84fcace3e140ed1

Own address: 19QkqAza7BHFTuoz9N8UQkryP4E9jHo4N3 - Pywallet support: 1AQDfx22pKGgXnUZFL1e4UKos3QqvRzNh5 - Bitcointalk++ script support: 1Pxeccscj1ygseTdSV1qUqQCanp2B2NMM2
Pywallet: instructions. Encrypted wallet support, export/import keys/addresses, backup wallets, export/import CSV data from/into wallet, merge wallets, delete/import addresses and transactions, recover altcoins sent to bitcoin addresses, sign/verify messages and files with Bitcoin addresses, recover deleted wallets, etc.
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1137

All paid signature campaigns should be banned.


View Profile WWW
September 15, 2013, 01:13:47 PM
 #82

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...


Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
NewLiberty
Legendary
*
Offline Offline

Activity: 1204
Merit: 1002


Gresham's Lawyer


View Profile WWW
September 15, 2013, 02:00:34 PM
 #83

Hmm I wonder how many colours of coloured coin it takes to [something something] a blockchain? Wink Cheesy

(You only need four whatzits to build a DNA strand? Hmm....)

Think like the game "sprouts".

(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.
Wink

FREE MONEY1 Bitcoin for Silver and Gold NewLibertyDollar.com and now BITCOIN SPECIE (silver 1 ozt) shows value by QR
Bulk premiums as low as .0012 BTC "BETTER, MORE COLLECTIBLE, AND CHEAPER THAN SILVER EAGLES" 1Free of Government
fpgaminer
Hero Member
*****
Offline Offline

Activity: 560
Merit: 517



View Profile WWW
September 15, 2013, 10:15:40 PM
 #84

Quote
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.
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!).

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).

BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1137

All paid signature campaigns should be banned.


View Profile WWW
September 18, 2013, 07:46:32 PM
Merited by ABCbits (4), o_e_l_e_o (4)
 #85

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

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
Etlase2
Hero Member
*****
Offline Offline

Activity: 798
Merit: 1000


View Profile
September 18, 2013, 09:27:42 PM
 #86

Very interesting, thanks for that Burt.

Carlton Banks
Legendary
*
Offline Offline

Activity: 3430
Merit: 3080



View Profile
September 18, 2013, 09:29:01 PM
 #87

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"  Cheesy.

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]


Vires in numeris
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1137

All paid signature campaigns should be banned.


View Profile WWW
September 18, 2013, 11:04:22 PM
 #88

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.

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
Carlton Banks
Legendary
*
Offline Offline

Activity: 3430
Merit: 3080



View Profile
September 18, 2013, 11:25:46 PM
 #89

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.

Vires in numeris
TierNolan
Legendary
*
Offline Offline

Activity: 1232
Merit: 1104


View Profile
September 19, 2013, 08:42:36 AM
Merited by garlonicon (1)
 #90

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;

public class PrimeTest {

        public static void main(String[] args) {

                BigInteger a = BigInteger.valueOf(2).pow(256);
                BigInteger b = BigInteger.valueOf(2).pow(32);

                BigInteger top = a.subtract(b);

                for (int t = 0; t < 1024; t++) {

                        BigInteger test = top.subtract(BigInteger.valueOf(t));

                        if (test.isProbablePrime(1024)) {
                                System.out.println(test.toString(16) + " (t = " + t + ")");
                        }

                }

        }
}

The result is

Code:
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffef9 (t = 263)
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffe99 (t = 359)
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffe97 (t = 361)
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffe19 (t = 487)
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffd1d (t = 739)
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc4b (t = 949)
fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f (t = 977)

The prime for t = 977 is the one that was selected for the curve.  It is the highest t that is lower than 1024.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
piotr_n
Legendary
*
Offline Offline

Activity: 2055
Merit: 1359


aka tonikt


View Profile WWW
September 19, 2013, 09:42:49 AM
Last edit: September 19, 2013, 04:32:34 PM by piotr_n
 #91

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 Smiley

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1137

All paid signature campaigns should be banned.


View Profile WWW
September 19, 2013, 03:58:17 PM
 #92

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!

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
piotr_n
Legendary
*
Offline Offline

Activity: 2055
Merit: 1359


aka tonikt


View Profile WWW
September 19, 2013, 04:39:07 PM
Merited by ABCbits (1)
 #93

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... Smiley

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
NewLiberty
Legendary
*
Offline Offline

Activity: 1204
Merit: 1002


Gresham's Lawyer


View Profile WWW
September 19, 2013, 05:08:06 PM
Merited by ABCbits (1)
 #94

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... Smiley

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.

FREE MONEY1 Bitcoin for Silver and Gold NewLibertyDollar.com and now BITCOIN SPECIE (silver 1 ozt) shows value by QR
Bulk premiums as low as .0012 BTC "BETTER, MORE COLLECTIBLE, AND CHEAPER THAN SILVER EAGLES" 1Free of Government
piotr_n
Legendary
*
Offline Offline

Activity: 2055
Merit: 1359


aka tonikt


View Profile WWW
September 19, 2013, 05:21:10 PM
Last edit: September 19, 2013, 05:31:39 PM by piotr_n
 #95

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. Smiley

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1137

All paid signature campaigns should be banned.


View Profile WWW
September 19, 2013, 05:56:11 PM
 #96

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.

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1137

All paid signature campaigns should be banned.


View Profile WWW
September 19, 2013, 06:07:24 PM
 #97

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.

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
maaku
Legendary
*
expert
Offline Offline

Activity: 905
Merit: 1012


View Profile
September 19, 2013, 06:27:54 PM
 #98

Anyone have contact info for MinghuaQu ?

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
September 19, 2013, 06:44:50 PM
Last edit: September 19, 2013, 06:56:34 PM by gmaxwell
 #99

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)
niko
Hero Member
*****
Offline Offline

Activity: 756
Merit: 501


There is more to Bitcoin than bitcoins.


View Profile
September 19, 2013, 08:17:18 PM
 #100

 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).

They're there, in their room.
Your mining rig is on fire, yet you're very calm.
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1137

All paid signature campaigns should be banned.


View Profile WWW
September 20, 2013, 08:08:38 PM
 #101

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

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
niko
Hero Member
*****
Offline Offline

Activity: 756
Merit: 501


There is more to Bitcoin than bitcoins.


View Profile
September 20, 2013, 08:53:07 PM
 #102

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.

They're there, in their room.
Your mining rig is on fire, yet you're very calm.
jgarzik
Legendary
*
qt
Offline Offline

Activity: 1596
Merit: 1100


View Profile
September 20, 2013, 11:27:41 PM
 #103

We care about bitcoin's curve ;p

Jeff Garzik, Bloq CEO, former bitcoin core dev team; opinions are my own.
Visit bloq.com / metronome.io
Donations / tip jar: 1BrufViLKnSWtuWGkryPsKsxonV2NQ7Tcj
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
September 20, 2013, 11:30:20 PM
 #104

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.
Peter Todd
Legendary
*
expert
Offline Offline

Activity: 1120
Merit: 1160


View Profile
September 21, 2013, 01:59:19 AM
 #105

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)

piotr_n
Legendary
*
Offline Offline

Activity: 2055
Merit: 1359


aka tonikt


View Profile WWW
September 21, 2013, 08:42:15 AM
Last edit: September 21, 2013, 08:56:42 AM by piotr_n
 #106

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
N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
B = 7
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

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.

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
fpgaminer
Hero Member
*****
Offline Offline

Activity: 560
Merit: 517



View Profile WWW
September 21, 2013, 09:10:58 AM
Last edit: September 21, 2013, 10:09:26 PM by fpgaminer
 #107

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 largestsmallest prime that satisfies: p = 2^256 - 2^32 - t where t < 1024

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?

piotr_n
Legendary
*
Offline Offline

Activity: 2055
Merit: 1359


aka tonikt


View Profile WWW
September 21, 2013, 10:06:54 AM
Last edit: September 21, 2013, 10:59:38 AM by piotr_n
 #108

Quote
and specifically about these five constants:
They've already been explained in this thread.  In summary:
Explained - yes.
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.

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1137

All paid signature campaigns should be banned.


View Profile WWW
September 21, 2013, 03:19:24 PM
Last edit: September 21, 2013, 03:34:39 PM by BurtW
 #109

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.

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
polarhei
Sr. Member
****
Offline Offline

Activity: 462
Merit: 250


Firing it up


View Profile
September 21, 2013, 03:32:58 PM
 #110

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.
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1137

All paid signature campaigns should be banned.


View Profile WWW
September 21, 2013, 03:37:18 PM
 #111

There is no true random. Only exponential.

What?

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
September 21, 2013, 03:37:43 PM
Merited by ABCbits (3)
 #112

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.
Not really, the reasons here are well understood by anyone working on this stuff in detail.

The number is a generalized mersenne prime. 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 to speed up point multiplies. This optimization is used by Pieter's libsecp256k1 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.


piotr_n
Legendary
*
Offline Offline

Activity: 2055
Merit: 1359


aka tonikt


View Profile WWW
September 21, 2013, 04:07:15 PM
 #113

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.
Not really, the reasons here are well understood by anyone working on this stuff in detail.

The number is a generalized mersenne prime. 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.
Thanks for explaining.

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?

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
TierNolan
Legendary
*
Offline Offline

Activity: 1232
Merit: 1104


View Profile
September 21, 2013, 05:13:46 PM
 #114

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.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1137

All paid signature campaigns should be banned.


View Profile WWW
September 21, 2013, 06:13:48 PM
 #115

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).

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
piotr_n
Legendary
*
Offline Offline

Activity: 2055
Merit: 1359


aka tonikt


View Profile WWW
September 21, 2013, 06:32:44 PM
Last edit: September 21, 2013, 07:04:03 PM by piotr_n
 #116

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? Wink

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?

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1137

All paid signature campaigns should be banned.


View Profile WWW
September 21, 2013, 07:26:13 PM
 #117

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

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
Etlase2
Hero Member
*****
Offline Offline

Activity: 798
Merit: 1000


View Profile
September 21, 2013, 07:31:05 PM
 #118

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".

piotr_n
Legendary
*
Offline Offline

Activity: 2055
Merit: 1359


aka tonikt


View Profile WWW
September 21, 2013, 07:38:46 PM
 #119

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 Smiley

I'm just going blind here, trying to find a hole, though still hoping that there isn't any.

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
TierNolan
Legendary
*
Offline Offline

Activity: 1232
Merit: 1104


View Profile
September 21, 2013, 08:03:13 PM
 #120

ask and you shall...

Ahh, thanks, missed that one.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
September 21, 2013, 08:15:08 PM
Last edit: September 21, 2013, 08:26:45 PM by gmaxwell
 #121

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? Wink
You need a six dimensions math library. Smiley

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.

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)
fpgaminer
Hero Member
*****
Offline Offline

Activity: 560
Merit: 517



View Profile WWW
September 21, 2013, 11:46:11 PM
Last edit: September 22, 2013, 03:42:11 AM by fpgaminer
 #122

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 *


# Find the smallest prime that satisfies: p = 2^256 - 2^32 - t where t < 1024.
def find_prime ():
for t in xrange (1023, -1, -1):
p = 2**256 - 2**32 - t

if p in Primes ():
return p

return None


# Find the smallest b, where b results in an elliptic curve of prime order, of the form y^2 = x^3 + a*x + b.
# p specifies the modulus of the underlying finite field.
def find_elliptic_curve (p, a, max_b):
K = FiniteField (p)

for b in xrange (max_b + 1):
if a == 0 and b == 0:
continue

E = EllipticCurve ([K (a), K (b)])
order = E.order ()

if order in Primes ():
return b

return None


p = find_prime ()

# Searches all combinations of a and b, where a and b < 7, until a prime order group is found.
for a in xrange (7, -1, -1):
print "Testing", a
b = find_elliptic_curve (p, a, 7)

if b is not None:
break

print ""
print "p = 0x%064X" % p
print "a = %d" % a
print "b = %d" % b
print "N = 0x%064X" % EllipticCurve (FiniteField (p), [0, b]).order ()
print ""

This requires sagemath, and can be executed by running "sage -python secp256k1_parameter_proof.py"  Here is my output:

Code:
Testing 7
Testing 6
Testing 5
Testing 4
Testing 3
Testing 2
Testing 1
Testing 0

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0
b = 7
N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

real 3m1.191s
user 3m0.716s
sys 0m0.148s

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.

piotr_n
Legendary
*
Offline Offline

Activity: 2055
Merit: 1359


aka tonikt


View Profile WWW
September 22, 2013, 02:06:31 PM
Last edit: September 22, 2013, 02:25:33 PM by piotr_n
 #123

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? Smiley

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).

Check out gocoin - my original project of full bitcoin node & cold wallet written in Go.
PGP fingerprint: AB9E A551 E262 A87A 13BB  9059 1BE7 B545 CDF3 FD0E
Etlase2
Hero Member
*****
Offline Offline

Activity: 798
Merit: 1000


View Profile
September 22, 2013, 02:48:11 PM
 #124

(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? Tongue 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?

fpgaminer
Hero Member
*****
Offline Offline

Activity: 560
Merit: 517



View Profile WWW
September 23, 2013, 04:04:06 AM
 #125

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), 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.

fpgaminer
Hero Member
*****
Offline Offline

Activity: 560
Merit: 517



View Profile WWW
September 23, 2013, 04:25:07 AM
Last edit: September 23, 2013, 05:53:17 AM by fpgaminer
 #126

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 *


def find_group (prime):
K = FiniteField (prime)

for b in xrange (1, 1000):
E = EllipticCurve (K, [0, b])

if E.order () in Primes ():
return b, E.order ()

return None


p = 2**256 - 2**32 + 1

while True:
p -= 1
if not p in Primes ():
continue

result = find_group (p)

if result is not None:
break


print "Found curve: "
print "p = %X" % p
print "a = 0"
print "b = %d" % result[0]
print "N = %X" % result[1]

That helps to explain p a bit more. (In other words, we have an alternative explanation that doesn't involved 2^10).

someone42
Member
**
Offline Offline

Activity: 78
Merit: 11

Chris Chua


View Profile
September 23, 2013, 05:37:32 AM
 #127

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), 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 (from here: 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.
TierNolan
Legendary
*
Offline Offline

Activity: 1232
Merit: 1104


View Profile
September 23, 2013, 09:27:06 AM
 #128

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.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
runeks
Legendary
*
Offline Offline

Activity: 980
Merit: 1008



View Profile WWW
September 25, 2013, 03:48:38 PM
Last edit: September 25, 2013, 03:59:00 PM by runeks
 #129

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? Wink
You can use sage. They have an online version of their shell here. Here's how you calculate the order of secp256k1:

Code:
sage: F = FiniteField(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
sage: F
Finite Field of size 115792089237316195423570985008687907853269984665640564039457584007908834671663
sage: C = EllipticCurve(F, [ 0, 7 ])
sage: C
Elliptic Curve defined by y^2 = x^3 + 7 over Finite Field of size 115792089237316195423570985008687907853269984665640564039457584007908834671663
sage: print(C.cardinality())
115792089237316195423570985008687907852837564279074904382605163141518161494337
sage: hex(C.cardinality())
'fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141'
sage: G = C.point((0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8))
sage: G
(55066263022277343669578718895168534326250603453777594175500187360389116729240 : 32670510020758816978083085130507043184471273380659243275938904335757337482424 : 1)
sage: G.order()
115792089237316195423570985008687907852837564279074904382605163141518161494337
sage: hex(G.order())
'fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141'
Roy Badami
Hero Member
*****
Offline Offline

Activity: 563
Merit: 500


View Profile
September 25, 2013, 08:09:20 PM
 #130

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
maaku
Legendary
*
expert
Offline Offline

Activity: 905
Merit: 1012


View Profile
September 25, 2013, 08:17:29 PM
 #131

If you write the code.

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
Roy Badami
Hero Member
*****
Offline Offline

Activity: 563
Merit: 500


View Profile
September 25, 2013, 10:38:23 PM
 #132

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

gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
September 27, 2013, 10:19:21 PM
Last edit: September 27, 2013, 10:36:45 PM by gmaxwell
 #133

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. Smiley
Wipeout2097
Sr. Member
****
Offline Offline

Activity: 840
Merit: 255


SportsIcon - Connect With Your Sports Heroes


View Profile
September 29, 2013, 07:44:04 AM
 #134

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.

███████████████████████████████████████████████████████████████
██▀       ▀█       ▀████████████        ▀█         █▀       ▀██
██   ▀██▄▄▄█   ██   ████████████   ███   ████   ████   ▀██▄▄▄██
███▄     ▀██       ▄████████████       ▄█████   █████▄     ▀███
██▀▀▀██▄   █   █████████████████   █▄  ▀█████   ████▀▀▀██▄   ██
██▄       ▄█   █████████████████   ██▄  ▀████   ████▄       ▄██
███████████████████████████████████████████████████████████████
██       ██▀      ▀█████████████    ▀██   █████████████████████
████   ███   ▄██▄   ████████████     ▀█   █████████████████████
████   ███   ████████   ████   █   ▄  ▀   █████████████████████
████   ███   ▀██▀   █   ████   █   █▄     █████████████████████
██       ██▄      ▄███        ██   ██▄    █████████████████████
███████████████████████████████████████████████████████████████
██████████████
██
██
██
██
██
██
██
██
██
██
██
██████████████
████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████                                                             ████████████████████████████████████████████████
.
.
.

████████████████████████████████████████████████████████████          ████████████████                                 ██████████████████████████████████████████████████████████████████████████████████████
██████████████
██
██
██
██
██
██
██
██
██
██
██
██████████████
███████
██
██
██
██
██
██
██
██
██
██
██
███████
███████
██
██
██
██
██
██
██
██
██
██
██
███████
►►  Powered by
BOUNTY
DETECTIVE
maaku
Legendary
*
expert
Offline Offline

Activity: 905
Merit: 1012


View Profile
September 29, 2013, 08:09:06 AM
 #135

Yes, and perhaps set up "rogue" full nodes.
What the heck is a "rogue" full node?

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1137

All paid signature campaigns should be banned.


View Profile WWW
September 29, 2013, 08:15:48 AM
 #136

Yes, and perhaps set up "rogue" full nodes.
What the heck is a "rogue" full node?
Obvioiusly a node that "runs wild" and logs every single transaction.  No, wait...

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?

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
niko
Hero Member
*****
Offline Offline

Activity: 756
Merit: 501


There is more to Bitcoin than bitcoins.


View Profile
September 29, 2013, 08:22:16 AM
Merited by ABCbits (1)
 #137

Yes, and perhaps set up "rogue" full nodes.
What the heck is a "rogue" full node?
Obvioiusly a node that "runs wild" and logs every single transaction.  No, wait...

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?
A node which serves, as part of a pool of similar nodes, to identify originating IPs of every transaction?

They're there, in their room.
Your mining rig is on fire, yet you're very calm.
chriswilmer
Legendary
*
Offline Offline

Activity: 1008
Merit: 1000


View Profile WWW
September 29, 2013, 01:26:38 PM
 #138

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. Smiley

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.
oleganza
Full Member
***
Offline Offline

Activity: 200
Merit: 104


Software design and user experience.


View Profile WWW
September 30, 2013, 11:59:42 AM
 #139

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.



Bitcoin analytics: blog.oleganza.com / 1TipsuQ7CSqfQsjA9KU5jarSB1AnrVLLo
chriswilmer
Legendary
*
Offline Offline

Activity: 1008
Merit: 1000


View Profile WWW
September 30, 2013, 12:52:41 PM
 #140

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.
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1137

All paid signature campaigns should be banned.


View Profile WWW
September 30, 2013, 03:19:26 PM
 #141

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.



He meant

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.

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1137

All paid signature campaigns should be banned.


View Profile WWW
September 30, 2013, 03:29:46 PM
 #142

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" Wink key pairs could maybe be used in some way Huh

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?

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
chriswilmer
Legendary
*
Offline Offline

Activity: 1008
Merit: 1000


View Profile WWW
September 30, 2013, 03:58:01 PM
 #143

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" Wink key pairs could maybe be used in some way Huh

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?
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1137

All paid signature campaigns should be banned.


View Profile WWW
September 30, 2013, 04:19:11 PM
Last edit: September 30, 2013, 04:58:43 PM by BurtW
 #144

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?

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
chriswilmer
Legendary
*
Offline Offline

Activity: 1008
Merit: 1000


View Profile WWW
September 30, 2013, 04:57:55 PM
 #145

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.

gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
September 30, 2013, 05:24:02 PM
 #146

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.
bfever
Jr. Member
*
Offline Offline

Activity: 39
Merit: 1


View Profile WWW
October 02, 2013, 07:09:20 PM
 #147

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.
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
October 02, 2013, 09:03:54 PM
 #148

...

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.
fpgaminer
Hero Member
*****
Offline Offline

Activity: 560
Merit: 517



View Profile WWW
October 07, 2013, 11:30:56 PM
 #149

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.
Same for x=1,2,3,4,... I think you can go on for a while before finding a solution that way.
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.

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.

BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1137

All paid signature campaigns should be banned.


View Profile WWW
October 08, 2013, 03:32:58 AM
 #150

...

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.
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:

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?

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
October 08, 2013, 05:15:47 AM
 #151

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?
Not for our G.

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.
AnonyMint
Hero Member
*****
Offline Offline

Activity: 518
Merit: 521


View Profile
October 13, 2013, 10:16:39 PM
 #152

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

unheresy.com - Prodigiously Elucidating the Profoundly ObtuseTHIS FORUM ACCOUNT IS NO LONGER ACTIVE
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
October 13, 2013, 10:59:45 PM
Last edit: October 14, 2013, 06:28:02 PM by gmaxwell
 #153

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.
jedunnigan
Sr. Member
****
Offline Offline

Activity: 279
Merit: 250


View Profile
October 14, 2013, 05:17:15 PM
 #154

Came across this on HN, thought it would be useful here: SafeCurves: choosing safe curves for elliptic-curve cryptography.
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
October 14, 2013, 05:46:44 PM
 #155

Came across this on HN, thought it would be useful here: SafeCurves: choosing safe curves for elliptic-curve cryptography.
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.
AnonyMint
Hero Member
*****
Offline Offline

Activity: 518
Merit: 521


View Profile
October 14, 2013, 05:54:31 PM
Last edit: October 14, 2013, 08:00:16 PM by AnonyMint
 #156

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.  Roll Eyes

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.

unheresy.com - Prodigiously Elucidating the Profoundly ObtuseTHIS FORUM ACCOUNT IS NO LONGER ACTIVE
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
October 14, 2013, 05:56:13 PM
Last edit: October 14, 2013, 06:34:46 PM by gmaxwell
 #157

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)
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1137

All paid signature campaigns should be banned.


View Profile WWW
December 22, 2013, 06:16:15 AM
 #158

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.

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
bluemeanie1
Sr. Member
****
Offline Offline

Activity: 280
Merit: 257


bluemeanie


View Profile WWW
December 22, 2013, 10:34:24 PM
 #159

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).

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). For his full essay, go here: 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

 

  while Fermat's Last Theorem is

  that no three positive integers a, b and c can satisfy the equation
 
  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


Just who IS bluemeanie?    On NXTautoDAC and a Million Stolen NXT

feel like your voice isn't being heard? PM me.   |   stole 1M NXT?
withnail
Newbie
*
Offline Offline

Activity: 12
Merit: 0


View Profile
December 23, 2013, 03:12:47 PM
 #160

"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.



     
bluemeanie1
Sr. Member
****
Offline Offline

Activity: 280
Merit: 257


bluemeanie


View Profile WWW
December 23, 2013, 07:28:48 PM
Last edit: December 23, 2013, 10:18:55 PM by bluemeanie1
 #161

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
Gx3 +7 mod p = 28522264212469271830151728101663411104844712793013968865831688505076558508754

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 (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.


Just who IS bluemeanie?    On NXTautoDAC and a Million Stolen NXT

feel like your voice isn't being heard? PM me.   |   stole 1M NXT?
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1137

All paid signature campaigns should be banned.


View Profile WWW
December 23, 2013, 08:38:51 PM
Last edit: December 23, 2013, 10:51:07 PM by BurtW
 #162

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 Wink

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1137

All paid signature campaigns should be banned.


View Profile WWW
December 23, 2013, 08:52:31 PM
Last edit: December 23, 2013, 10:50:11 PM by BurtW
 #163

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.

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
bluemeanie1
Sr. Member
****
Offline Offline

Activity: 280
Merit: 257


bluemeanie


View Profile WWW
December 23, 2013, 09:07:08 PM
 #164

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?

Just who IS bluemeanie?    On NXTautoDAC and a Million Stolen NXT

feel like your voice isn't being heard? PM me.   |   stole 1M NXT?
jackjack
Legendary
*
Offline Offline

Activity: 1176
Merit: 1280


May Bitcoin be touched by his Noodly Appendage


View Profile
December 23, 2013, 09:40:19 PM
 #165

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

Own address: 19QkqAza7BHFTuoz9N8UQkryP4E9jHo4N3 - Pywallet support: 1AQDfx22pKGgXnUZFL1e4UKos3QqvRzNh5 - Bitcointalk++ script support: 1Pxeccscj1ygseTdSV1qUqQCanp2B2NMM2
Pywallet: instructions. Encrypted wallet support, export/import keys/addresses, backup wallets, export/import CSV data from/into wallet, merge wallets, delete/import addresses and transactions, recover altcoins sent to bitcoin addresses, sign/verify messages and files with Bitcoin addresses, recover deleted wallets, etc.
marcus_of_augustus
Legendary
*
Offline Offline

Activity: 3920
Merit: 2349


Eadem mutata resurgo


View Profile
December 23, 2013, 09:48:57 PM
 #166

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.

rarkenin
Hero Member
*****
Offline Offline

Activity: 784
Merit: 500



View Profile
December 23, 2013, 09:51:19 PM
 #167

On this planet. The design of ECC revolves around age-old mathematical definitions and theorems with that kind of shorthand, so accept it here.
withnail
Newbie
*
Offline Offline

Activity: 12
Merit: 0


View Profile
December 23, 2013, 10:12:28 PM
 #168

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? Grin   


 



bluemeanie1
Sr. Member
****
Offline Offline

Activity: 280
Merit: 257


bluemeanie


View Profile WWW
December 23, 2013, 10:13:36 PM
 #169

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.

Just who IS bluemeanie?    On NXTautoDAC and a Million Stolen NXT

feel like your voice isn't being heard? PM me.   |   stole 1M NXT?
withnail
Newbie
*
Offline Offline

Activity: 12
Merit: 0


View Profile
December 23, 2013, 10:21:12 PM
 #170

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?
bluemeanie1
Sr. Member
****
Offline Offline

Activity: 280
Merit: 257


bluemeanie


View Profile WWW
December 23, 2013, 10:23:00 PM
 #171

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.

Just who IS bluemeanie?    On NXTautoDAC and a Million Stolen NXT

feel like your voice isn't being heard? PM me.   |   stole 1M NXT?
rarkenin
Hero Member
*****
Offline Offline

Activity: 784
Merit: 500



View Profile
December 23, 2013, 10:26:17 PM
 #172

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.
withnail
Newbie
*
Offline Offline

Activity: 12
Merit: 0


View Profile
December 23, 2013, 10:35:41 PM
 #173

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?
rarkenin
Hero Member
*****
Offline Offline

Activity: 784
Merit: 500



View Profile
December 23, 2013, 10:39:05 PM
 #174

AFAIK Bitcoin is unadulterated.
bluemeanie1
Sr. Member
****
Offline Offline

Activity: 280
Merit: 257


bluemeanie


View Profile WWW
December 23, 2013, 10:55:35 PM
 #175

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.

Just who IS bluemeanie?    On NXTautoDAC and a Million Stolen NXT

feel like your voice isn't being heard? PM me.   |   stole 1M NXT?
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1137

All paid signature campaigns should be banned.


View Profile WWW
December 23, 2013, 10:57:44 PM
 #176

My point being, it is very possible that the NSA has secret knowledge of elliptic curves.

It is also possible they do not, right?

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
jackjack
Legendary
*
Offline Offline

Activity: 1176
Merit: 1280


May Bitcoin be touched by his Noodly Appendage


View Profile
December 23, 2013, 11:04:16 PM
 #177

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 back

Own address: 19QkqAza7BHFTuoz9N8UQkryP4E9jHo4N3 - Pywallet support: 1AQDfx22pKGgXnUZFL1e4UKos3QqvRzNh5 - Bitcointalk++ script support: 1Pxeccscj1ygseTdSV1qUqQCanp2B2NMM2
Pywallet: instructions. Encrypted wallet support, export/import keys/addresses, backup wallets, export/import CSV data from/into wallet, merge wallets, delete/import addresses and transactions, recover altcoins sent to bitcoin addresses, sign/verify messages and files with Bitcoin addresses, recover deleted wallets, etc.
rarkenin
Hero Member
*****
Offline Offline

Activity: 784
Merit: 500



View Profile
December 23, 2013, 11:07:55 PM
 #178

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.
NewLiberty
Legendary
*
Offline Offline

Activity: 1204
Merit: 1002


Gresham's Lawyer


View Profile WWW
December 26, 2013, 09:33:04 PM
 #179

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.

FREE MONEY1 Bitcoin for Silver and Gold NewLibertyDollar.com and now BITCOIN SPECIE (silver 1 ozt) shows value by QR
Bulk premiums as low as .0012 BTC "BETTER, MORE COLLECTIBLE, AND CHEAPER THAN SILVER EAGLES" 1Free of Government
justusranvier
Legendary
*
Offline Offline

Activity: 1400
Merit: 1013



View Profile
January 21, 2014, 06:30:18 PM
 #180

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.
Altoidnerd
Sr. Member
****
Offline Offline

Activity: 406
Merit: 251


http://altoidnerd.com


View Profile WWW
January 21, 2014, 09:50:03 PM
 #181

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.

Do you even mine?
http://altoidnerd.com 
12gKRdrz7yy7erg5apUvSRGemypTUvBRuJ
AnonyMint
Hero Member
*****
Offline Offline

Activity: 518
Merit: 521


View Profile
June 29, 2014, 04:30:31 PM
Last edit: June 29, 2014, 05:32:33 PM by AnonyMint
 #182

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.

unheresy.com - Prodigiously Elucidating the Profoundly ObtuseTHIS FORUM ACCOUNT IS NO LONGER ACTIVE
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
June 30, 2014, 12:54:06 AM
Last edit: June 30, 2014, 08:11:10 AM by gmaxwell
 #183

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_.

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.
hashman
Legendary
*
Offline Offline

Activity: 1264
Merit: 1008


View Profile
July 01, 2014, 09:31:02 AM
 #184


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_.


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.      .

gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
July 01, 2014, 10:32:15 AM
 #185

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 [...]".
AnonyMint
Hero Member
*****
Offline Offline

Activity: 518
Merit: 521


View Profile
July 04, 2014, 01:28:08 PM
 #186

@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.

unheresy.com - Prodigiously Elucidating the Profoundly ObtuseTHIS FORUM ACCOUNT IS NO LONGER ACTIVE
cypherdoc
Legendary
*
Offline Offline

Activity: 1764
Merit: 1002



View Profile
July 08, 2014, 11:16:37 PM
 #187

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 largestsmallest prime that satisfies: p = 2^256 - 2^32 - t where t < 1024

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
DeathAndTaxes
Donator
Legendary
*
Offline Offline

Activity: 1218
Merit: 1079


Gerald Davis


View Profile
July 09, 2014, 12:22:34 AM
 #188

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).


Peter R
Legendary
*
Offline Offline

Activity: 1162
Merit: 1007



View Profile
July 09, 2014, 01:22:28 AM
 #189

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.

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}];

263
359
361
487
739
949
977
1049
1057
1339
1607
1969
 

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.  

Run Bitcoin Unlimited (www.bitcoinunlimited.info)
cypherdoc
Legendary
*
Offline Offline

Activity: 1764
Merit: 1002



View Profile
July 09, 2014, 01:58:58 AM
 #190

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.

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}];

263
359
361
487
739
949
977
1049
1057
1339
1607
1969
 

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?
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1137

All paid signature campaigns should be banned.


View Profile WWW
July 09, 2014, 03:00:59 AM
 #191

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.

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}];

263
359
361
487
739
949
977
1049
1057
1339
1607
1969
 

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.  

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.

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
Peter R
Legendary
*
Offline Offline

Activity: 1162
Merit: 1007



View Profile
July 09, 2014, 04:46:01 AM
 #192

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...

Run Bitcoin Unlimited (www.bitcoinunlimited.info)
BurtW
Legendary
*
Offline Offline

Activity: 2646
Merit: 1137

All paid signature campaigns should be banned.


View Profile WWW
July 09, 2014, 08:40:34 AM
 #193

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.

Our family was terrorized by Homeland Security.  Read all about it here:  http://www.jmwagner.com/ and http://www.burtw.com/  Any donations to help us recover from the $300,000 in legal fees and forced donations to the Federal Asset Forfeiture slush fund are greatly appreciated!
Peter R
Legendary
*
Offline Offline

Activity: 1162
Merit: 1007



View Profile
July 10, 2014, 02:46:20 AM
 #194

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.  

Run Bitcoin Unlimited (www.bitcoinunlimited.info)
DeathAndTaxes
Donator
Legendary
*
Offline Offline

Activity: 1218
Merit: 1079


Gerald Davis


View Profile
July 10, 2014, 03:51:58 AM
 #195

Well Bitcoin could always support a second curve.   A curve over F(p) where P = 2^256 - 2^32 - 236, call it Secp256k2 Smiley.  I know I am highly original in my naming convention.
justusranvier
Legendary
*
Offline Offline

Activity: 1400
Merit: 1013



View Profile
July 10, 2014, 03:54:32 AM
 #196

Well Bitcoin could always support a second curve.   A curve over F(p) where P = 2^256 - 2^32 - 236, call it Secp256k2 Smiley.  I know I am highly original in my naming convention.
One of these: http://safecurves.cr.yp.to/bada55.html
cypherdoc
Legendary
*
Offline Offline

Activity: 1764
Merit: 1002



View Profile
July 10, 2014, 04:47:09 AM
 #197

Well Bitcoin could always support a second curve.   A curve over F(p) where P = 2^256 - 2^32 - 236, call it Secp256k2 Smiley.  I know I am highly original in my naming convention.
One of these: http://safecurves.cr.yp.to/bada55.html

Yep, those are badass
ThomasCrowne
Full Member
***
Offline Offline

Activity: 210
Merit: 100

★☆★ 777Coin - The Exciting Bitco


View Profile
July 10, 2014, 08:32:35 AM
 #198

Regarding the OP.

"If the NSA coulda you can bet your bottom dollar they woulda!"   -me

hashman
Legendary
*
Offline Offline

Activity: 1264
Merit: 1008


View Profile
July 11, 2014, 09:09:29 PM
 #199

Well Bitcoin could always support a second curve.   A curve over F(p) where P = 2^256 - 2^32 - 236, call it Secp256k2 Smiley.  I know I am highly original in my naming convention.
One of these: http://safecurves.cr.yp.to/bada55.html

Yep, 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? 




gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
July 11, 2014, 11:28:20 PM
 #200

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.

hashman
Legendary
*
Offline Offline

Activity: 1264
Merit: 1008


View Profile
July 14, 2014, 12:52:07 AM
 #201


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)."

AnonyMint
Hero Member
*****
Offline Offline

Activity: 518
Merit: 521


View Profile
July 14, 2014, 01:14:17 AM
 #202

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?

unheresy.com - Prodigiously Elucidating the Profoundly ObtuseTHIS FORUM ACCOUNT IS NO LONGER ACTIVE
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
July 14, 2014, 05:19:57 AM
 #203

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.
AnonyMint
Hero Member
*****
Offline Offline

Activity: 518
Merit: 521


View Profile
July 14, 2014, 05:35:53 AM
Last edit: July 14, 2014, 09:55:37 AM by AnonyMint
 #204

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.

unheresy.com - Prodigiously Elucidating the Profoundly ObtuseTHIS FORUM ACCOUNT IS NO LONGER ACTIVE
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
July 14, 2014, 11:12:32 AM
 #205

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.
hashman
Legendary
*
Offline Offline

Activity: 1264
Merit: 1008


View Profile
July 14, 2014, 02:21:30 PM
 #206

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 Smiley  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? 
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
July 15, 2014, 12:37:45 PM
Last edit: July 15, 2014, 01:00:36 PM by gmaxwell
 #207

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)— 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.
cypherdoc
Legendary
*
Offline Offline

Activity: 1764
Merit: 1002



View Profile
July 15, 2014, 04:50:58 PM
 #208

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
DeathAndTaxes
Donator
Legendary
*
Offline Offline

Activity: 1218
Merit: 1079


Gerald Davis


View Profile
July 15, 2014, 06:07:34 PM
Last edit: July 15, 2014, 06:20:06 PM by DeathAndTaxes
 #209

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.

uint64 nonce = 0;
do
{
  byte[] curve_bytes = SHA-3(nonce)
  if( ValidateCurve(curve_bytes) == true)
     break
  nonce++;
}while(nonce < uint64.max_value)

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?
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
July 15, 2014, 06:35:24 PM
 #210

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).

DeathAndTaxes
Donator
Legendary
*
Offline Offline

Activity: 1218
Merit: 1079


Gerald Davis


View Profile
July 15, 2014, 07:23:58 PM
Last edit: July 15, 2014, 07:38:06 PM by DeathAndTaxes
 #211

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.
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4270
Merit: 8805



View Profile WWW
July 15, 2014, 07:46:42 PM
Last edit: July 15, 2014, 08:25:08 PM by gmaxwell
 #212

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! Smiley

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.
gmaxwell
Moderator
Legendary
*