Right. They don't discourage you from using an alternative bitcoin solutions, as long as what you are doing with them isn't anything serious  But me at the other hand, I would not use bitcoin-qt for anything serious, because its online-only wallet architecture is completely unacceptable as for my personal security standards. Yeah, I know that there are workarounds to keep the wallet.dat offline - I've been there and I know that they require a user to move gigabytes of blockchain data, and to wait for an endless -rescan, over and over, each time before spending a new coin... but if this is supposed to be the serious solution, then there must be something seriously wrong with my sense of humor |
|
|
|
Some other projects attempt to compete, but it is not recommended to use such software for anything serious. (Lightweight clients like Electrum and MultiBit are OK.) Obviously it's hard to reproduce all the official client's behaviors and misbehaviors, in order to handle the blockchain properly... we all know that it's the only reference there is and by definition you cannot beat the reference. But I did my best and I challenge anyone to break my client by forking its behavior against bitcoin-qt, or get it stuck at a certain block. Especially I encourage the guy who wrote that quote! But until he does, he's just pathetic - I can also say that his children are stupid and far off the right course.. |
|
|
|
I built the test to not only show that b = 7 results in the first prime order, given a = 0, but also that a = 0 and b = 7 is the first result when searching all combinations of a and b < 7. So, if one was looking for a curve, and didn't know about GLV, (0,7) would still be a reasonable choice.
Thanks. That's a decent and quite convincing explanation of why they chose B to be 7, though don't you feel like doing someone's else job here by explaining it to us? I guess we can narrow down our investigation to the G point and the P (since we still don't seem to know what is so great about 1024 aka 2^10). |
|
|
|
I can answer the question about the prime numbers. If you set the certainty high enough you can be certain. For example above in this thread the call test.isProbablePrime(1024) is made. This is asking to test if the number is prime within a certainty of 1 - 0.51024 Right - that should do I'm just going blind here, trying to find a hole, though still hoping that there isn't any. |
|
|
|
pardon me the lame question, but what is the actual formula to calculate the order (N), from the A & B? can I calc it myself, using a python shell, or do I need a six dimensions math library?  moreover, from what I understand, it isn't really possible to check whether 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 is a real prime number, is it? AFAIK, the algos we know only allow us to check whether such a big numbers are prime with a certain probability, but we can never be totally sure about their primness, since checking for that would have taken ages - right? |
|
|
|
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? |
|
|
|
A quick update for people interested in this project, if such even exist WalletConsidering the Android's RNG incident and the rumors that other systems might also be "NSA friendly", I modified the wallet app in a way that its security does not rely on random number source anymore. Note that it never had for private key calculation (since it uses deterministic wallet driven by a password-seed), but it did for signing, and now it doesn't even for signing. ClientI ported sipa's secp256k1 lib (the 10x26 option) to Go. It is now a default option for ECDSA signature checks, so there is no need to struggle with C compilers anymore to get a decent performance. It performs better than the openssl wrapper (so also better than your current satoshi client), though is still like 3-5 times slower from the cgo wrapper using an original secp256k1 lib. The openssl wrapper is still there, if you prefer to use it (having a security concerns). Same applies for the native ECDSA lib, though this one is still deadly slow. There were also some fixes around accessing maps from different threads that were not properly protected, which was causing memory leaks - this should be fixed now. Plus plenty of other things, not really worth mentioning, like a new command to purge orphaned blocks from the database, or replaced block's gzip compression with snappy (performs much better). |
|
|
|
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. 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? 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. |
|
|
|
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: 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. |
|
|
|
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: 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. |
|
|
|
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... |
|
|
|
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 |
|
|
|
This might be Mr Solinas' email address: jasolin@orion.ncsc.milWe 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? |
|
|
|
the way for the attacker to check if you actually did the mistake, is by computing: d = z(s-r)-1 No just to see if r equals the x coordinate of the public key. Oh, OK - that's much easier then. Still unlikely to happen, thought equally likely as picking up zero... So you might have some point here, because EC-Verify functions from the crypto libs I've seen, they all check the k for zero, but not for d... |
|
|
|
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 |
|
|
|
If k is equal to d, the private key can be calculated by d = z(s-r)-1 (z is the reduced message hash)! The subject is not that RNG are broken or bugged or ... I just want to draw attention to a situation on which nobody thinks
That is all true what you say, but generating a really random random k that would be equal to d... hmm, good luck with it! And even if you do it, the way for the attacker to check if you actually did the mistake, is by computing: d = z(s-r)-1Such a computation does not seem to by much more resource friendly then a regular private to public key conversion. So if you want to test each k value whether it might be (by a chance) the d, you might as well start testing k-1, k+1, k-2, k+2, k-3, k+3, and so on... because each of these values, a potential attacker can try to test as the private key. And then, if you get paranoid enough, you will essentially end up with a solution in which any k value is not safe |
|
|
|
|
I think bitcoin wallets should abandon using RNG to generate the k values.
Just use hash of a data that you are signing, or wherever other unique value tied to the data that is being signed.
You can though feed your k with some additional RND data (just in case), but in general the signing process should assume that RNG is not safe - that's the safest approach.
You still have the problem of generating the private keys, but not when you use a brain wallet (a password-seed).
So IMHO bitcoin wallets can (and should) be implemented in a way that makes them 100% resistant against any RNG attacks.
Because RNG attacks are mostly very hard to detect.
|
|
|
|
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 |
|
|
|
|
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.
|
|
|
|
|
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.
|
|
|
|
|
Show Posts
