Unless one can deeply understand the math and cryptography for
themselves, we all have to trust the community and those
that do have the specialized knowledge.
I try to understand as best I can as a hobby, but
I simply don't have the time or energy to devote
to understanding every aspect of Bitcoin.
Topic: This message was too old and has been purged (Read 7931 times)
legendary
Activity: 1302
Merit: 1008
Core dev leaves me neg feedback #abuse #political
Yeah using secp256r1 would have been a nightmare. The NSA doesn't screw up this badly. Cryptographic constants should be "nothing up my sleeve numbers". Lets look how the NSA "randomly" came up with the parameters for secp256r1
Ok so lets work backwards.
We want p & q to be prime numbers (or probably prime).
So we use a generator to try values in sequence and use the first curve for a given security strength which meets our requirements. Why do we use the FIRST value? To provide a level of reassurance that it is legit and not chosen for a malicious reason. If there were 4872498374938247398 valid curves and the NSA picked the 4872498374938247399th one that would be suspicious right. Alright so we are using the first one we find, building some trust here. That is good.
Ok so how do we seed the generator. We take the hash of some number at random? WTF? Did some 2 bit scammer on bitcointalk come up with this method? I mean this is the fracking NSA. They know a "little" about cryptography. There is no possible way they "forgot" that this makes all the subsequent steps worthless. I mean it is like saying "You can trust me because you can trust me" See I am not asking you to trust me blindly. I gave you a specific reason why you can trust me."
Now the NSA isn't stupid. The obvious elephant in the room is how do we know the "random" seed value is random. Maybe the NSA went through quadrillions of random seed values until they found one which when hashes produces a sequence such that the first valid curve is the one which has a property that the NSA knows has a weakness. In other words all the song and dance about following this generator sequence and performing various checks is predicated on the generator seed being chosen "fairly" but they just happened to forget that the seed for the generator isn't provable or even probably fair (nothing up my sleeve) and thus the entire process is security theater.
Formally
You can stop reading at step #1. The foundation is sand. So what was the domain parameter seed picked at random over all others (you can trust us )?
c49d3608 86e70493 6a6678e1 139d26b7 819f7e90
A totally arbitrary number. Was this the first one the NSA tried? Or did they have their super computer crunching for years before they came up with this seed which when you follow the rest of their "sleight of hand" generator produced the "random" curve which is EXACTLY what they wanted it to be for some reason only they know? The rest of their security process is just feel good security. It is the wand in a magic trick so you don't look closely to the fact that the magician is just cheating with his other hand.
Now if the seed for secp256r1 was say the first 160 bits of pi well we would have at least some confidence that the curve produced was strong. It would be a rather extreme coincidence that the first 160 bits of pi happened to produce a curve which the NSA knew was weak.
Quote
Previous versions of this Standard contained a method for the generation of the domain
parameters p and q using SHA-1 and probabilistic methods. This method is no longer approved
for domain parameter generation; however, the validation process for this method is provided in
Appendix A.1.1.1 to validate previously generated domain parameters.
A method for the generation and validation of the primes p and q using probabilistic methods is
provided in Appendix A.1.1.2 and is based on the use of an approved hash function; this method
shall be used for generating probable primes. The validation process for this method is provided
in Appendix A.1.1.3.
The probabilistic methods use a hash function and an arbitrary seed (domain_parameter_seed).
Arbitrary seeds could be anything, e.g., a user’s favorite number or a random or pseudorandom
number output by a random number generator (see SP 800-90). The domain_parameter_seed
determines a sequence of candidates for p and q in the required intervals that are then tested for
primality using a probabilistic primality test (see Appendix C.3). The test determines that the
candidate is either not a prime (i.e., it is a composite integer) or is “probably a prime” (i.e., there
is a very small probability that a composite integer will be declared to be a prime). p and q shall
be the first candidate set that passes the primality tests. Note that the domain_parameter_seed
shall be unique for every unique set of domain parameters that are generated using the same
method.
parameters p and q using SHA-1 and probabilistic methods. This method is no longer approved
for domain parameter generation; however, the validation process for this method is provided in
Appendix A.1.1.1 to validate previously generated domain parameters.
A method for the generation and validation of the primes p and q using probabilistic methods is
provided in Appendix A.1.1.2 and is based on the use of an approved hash function; this method
shall be used for generating probable primes. The validation process for this method is provided
in Appendix A.1.1.3.
The probabilistic methods use a hash function and an arbitrary seed (domain_parameter_seed).
Arbitrary seeds could be anything, e.g., a user’s favorite number or a random or pseudorandom
number output by a random number generator (see SP 800-90). The domain_parameter_seed
determines a sequence of candidates for p and q in the required intervals that are then tested for
primality using a probabilistic primality test (see Appendix C.3). The test determines that the
candidate is either not a prime (i.e., it is a composite integer) or is “probably a prime” (i.e., there
is a very small probability that a composite integer will be declared to be a prime). p and q shall
be the first candidate set that passes the primality tests. Note that the domain_parameter_seed
shall be unique for every unique set of domain parameters that are generated using the same
method.
Ok so lets work backwards.
We want p & q to be prime numbers (or probably prime).
So we use a generator to try values in sequence and use the first curve for a given security strength which meets our requirements. Why do we use the FIRST value? To provide a level of reassurance that it is legit and not chosen for a malicious reason. If there were 4872498374938247398 valid curves and the NSA picked the 4872498374938247399th one that would be suspicious right. Alright so we are using the first one we find, building some trust here. That is good.
Ok so how do we seed the generator. We take the hash of some number at random? WTF? Did some 2 bit scammer on bitcointalk come up with this method? I mean this is the fracking NSA. They know a "little" about cryptography. There is no possible way they "forgot" that this makes all the subsequent steps worthless. I mean it is like saying "You can trust me because you can trust me" See I am not asking you to trust me blindly. I gave you a specific reason why you can trust me."
Now the NSA isn't stupid. The obvious elephant in the room is how do we know the "random" seed value is random. Maybe the NSA went through quadrillions of random seed values until they found one which when hashes produces a sequence such that the first valid curve is the one which has a property that the NSA knows has a weakness. In other words all the song and dance about following this generator sequence and performing various checks is predicated on the generator seed being chosen "fairly" but they just happened to forget that the seed for the generator isn't provable or even probably fair (nothing up my sleeve) and thus the entire process is security theater.
Formally
Quote
D.5 Generation of Pseudo-Random Curves (Prime Case)
Let l be the bit length of p, and define
v = ( l – 1) /160
w = l – 160v – 1.
1. Choose an arbitrary 160-bit string s as the domain parameter seed.
2. Compute h = SHA-1(s).
3. Let h0 be the bit string obtained by taking the w rightmost bits of h.
4. Let z be the integer whose binary expansion is given by the 160-bit string s.
5. For i from 1 to v do:
5.1 Define the 160-bit string si to be binary expansion of the integer
(z + i) mod (2 160).
5.2 Compute hi = SHA-1(si).
6. Let h be the bit string obtained by the concatenation of h0 , h1, … , hv as follows:
h = h0 || h1 || … || hv.
7. Let c be the integer whose binary expansion is given by the bit string h.
8. If ((c = 0 or 4c + 27 ≡ 0 (mod p))), then go to Step 1.
9. Choose integers a, b ∈GF(p) such that
c b^2 ≡ a^3 (mod p).
(The simplest choice is a = c and b = c. However, one may want to choose differently for
performance reasons.)
10. Check that the elliptic curve E over GF(p) given by y^2 = x^3 + ax + b has suitable order.
If not, go to Step 1.
Let l be the bit length of p, and define
v = ( l – 1) /160
w = l – 160v – 1.
1. Choose an arbitrary 160-bit string s as the domain parameter seed.
2. Compute h = SHA-1(s).
3. Let h0 be the bit string obtained by taking the w rightmost bits of h.
4. Let z be the integer whose binary expansion is given by the 160-bit string s.
5. For i from 1 to v do:
5.1 Define the 160-bit string si to be binary expansion of the integer
(z + i) mod (2 160).
5.2 Compute hi = SHA-1(si).
6. Let h be the bit string obtained by the concatenation of h0 , h1, … , hv as follows:
h = h0 || h1 || … || hv.
7. Let c be the integer whose binary expansion is given by the bit string h.
8. If ((c = 0 or 4c + 27 ≡ 0 (mod p))), then go to Step 1.
9. Choose integers a, b ∈GF(p) such that
c b^2 ≡ a^3 (mod p).
(The simplest choice is a = c and b = c. However, one may want to choose differently for
performance reasons.)
10. Check that the elliptic curve E over GF(p) given by y^2 = x^3 + ax + b has suitable order.
If not, go to Step 1.
You can stop reading at step #1. The foundation is sand. So what was the domain parameter seed picked at random over all others (you can trust us
c49d3608 86e70493 6a6678e1 139d26b7 819f7e90
A totally arbitrary number. Was this the first one the NSA tried? Or did they have their super computer crunching for years before they came up with this seed which when you follow the rest of their "sleight of hand" generator produced the "random" curve which is EXACTLY what they wanted it to be for some reason only they know? The rest of their security process is just feel good security. It is the wand in a magic trick so you don't look closely to the fact that the magician is just cheating with his other hand.
Now if the seed for secp256r1 was say the first 160 bits of pi well we would have at least some confidence that the curve produced was strong. It would be a rather extreme coincidence that the first 160 bits of pi happened to produce a curve which the NSA knew was weak.
so........ where does all that put us about the likelihood
that insider knowledge of elliptic curve manipulation
exists?
After researching this quite a bit and several emails with one of the guys from the group that designed secp256k1 without input from NIST or the NSA. I personally, and many others who were involved, are convinced that all the parameters used in the secp256k1 curve are reasonable and can be accounted for. In other words, as opposed to the more popular secp256r1 curve, which was designed directly by NIST/NSA and uses "magic numbers" supplied directly by them, there are no "magic numbers" used in the design of the curve we use in the Bitcoin protocol. that insider knowledge of elliptic curve manipulation
exists?
legendary
Activity: 1302
Merit: 1008
Core dev leaves me neg feedback #abuse #political
so........ where does all that put us about the likelihood
that insider knowledge of elliptic curve manipulation
exists?
that insider knowledge of elliptic curve manipulation
exists?
This message was too old and has been purged
Just wanted to throw in that *every* multiplicative group of a finite field is cyclic.
You are right. That's what I get for trying to be smart about a subject I don't understand well. The point was that you have to be careful when selecting the finite field.
It seems it can be great idea to make new curve based on open and peer reviewed standards.
There is no need to do that. There is nothing wrong with or even slightly hinky about the curve we are using as discussed in detail in the thread described in this post:https://bitcointalksearch.org/topic/m.4568250
It seems it can be great idea to make new curve based on open and peer reviewed standards.
This message was too old and has been purged
and do you want to know what is even more bizarre?
just prior to the release of ECC, there was a significant mathematical work in the realm of Elliptic Curves and Cyclic groups! Thus it very plausible to suspect that insider knowledge of elliptic curve manipulation exists.
http://math.stanford.edu/~lekheng/flt/wiles.pdf
is it a coincidence that ECC became a standard not long after pioneering work in the exact theoretical field in which they are situated?
-bm
Hey Guys,
We all know, that the security of ECDSA relies on the complexity of solving the discrete logarithm problem in cyclic groups. ECDSA works on Kolitz-Curves which have a prime number, that they use as the modulo, and a generator which is a primitive root on the curve which - when exponentiated - is able to generate all other elements of the group.
To all of you, who do not know what the discrete logarithm is, here comes a short explanation:
Let us say we work on the Group Z/29Z - that means we have a cyclic group modulo 29. Further let's say we have a generator point 3. It is impossible to solve the equation:
3^x mod 29 = 13 mod 29
The solution is by the way x=26, which can be only found out by trying all possible combinations.
However, being n the primnumber to calculate the modulus, to compute a discrete logarithm it suffices to be able to get the prime factorization of n+1. To make this as hard as possible the prime number n is usually chosen to be 2q+1 where q is another very large prime number.
NOW COMES THE DANGER:
If the creator of the curve (be it the NIST or the founder of secp256k1) chooses the primenumbers in such a way that p-1 has a small known prime factor
... then despite the prime looks purely random to the average joe, the creator knows the prime factorization and may solve any discrete logarithm in this cyclic group easily (for example using the Pohlig-Hellman algorithm)
What I want to say: If any of the creators remembered the prime factors during creation of the curve, he can calculate your private key in an instant.
All I want to say is: do not trust anyone!
We all know, that the security of ECDSA relies on the complexity of solving the discrete logarithm problem in cyclic groups. ECDSA works on Kolitz-Curves which have a prime number, that they use as the modulo, and a generator which is a primitive root on the curve which - when exponentiated - is able to generate all other elements of the group.
To all of you, who do not know what the discrete logarithm is, here comes a short explanation:
Let us say we work on the Group Z/29Z - that means we have a cyclic group modulo 29. Further let's say we have a generator point 3. It is impossible to solve the equation:
3^x mod 29 = 13 mod 29
The solution is by the way x=26, which can be only found out by trying all possible combinations.
However, being n the primnumber to calculate the modulus, to compute a discrete logarithm it suffices to be able to get the prime factorization of n+1. To make this as hard as possible the prime number n is usually chosen to be 2q+1 where q is another very large prime number.
NOW COMES THE DANGER:
If the creator of the curve (be it the NIST or the founder of secp256k1) chooses the primenumbers in such a way that p-1 has a small known prime factor
... then despite the prime looks purely random to the average joe, the creator knows the prime factorization and may solve any discrete logarithm in this cyclic group easily (for example using the Pohlig-Hellman algorithm)
What I want to say: If any of the creators remembered the prime factors during creation of the curve, he can calculate your private key in an instant.
All I want to say is: do not trust anyone!
It's well known thath you can't have an elliptic curve over any arbitrary field. If you have an EC over a cyclic group, the discrete logarithm can be easily computed. You need special groups over which you contrstruct EC for them to be usable in cryptography.
legendary
Activity: 1302
Merit: 1008
Core dev leaves me neg feedback #abuse #political
Can anyone recommend a good ECC video for beginners? I watched 1 or 2 but they were kind of dry, so please let me know if you know of some really good ones. Not looking to become an expert...I just want to learn some of the basic principles. Thanks. JF
and do you want to know what is even more bizarre?
just prior to the release of ECC, there was a significant mathematical work in the realm of Elliptic Curves and Cyclic groups! Thus it very plausible to suspect that insider knowledge of elliptic curve manipulation exists.
http://math.stanford.edu/~lekheng/flt/wiles.pdf
is it a coincidence that ECC became a standard not long after pioneering work in the exact theoretical field in which they are situated?
-bm
Hey Guys,
We all know, that the security of ECDSA relies on the complexity of solving the discrete logarithm problem in cyclic groups. ECDSA works on Kolitz-Curves which have a prime number, that they use as the modulo, and a generator which is a primitive root on the curve which - when exponentiated - is able to generate all other elements of the group.
To all of you, who do not know what the discrete logarithm is, here comes a short explanation:
Let us say we work on the Group Z/29Z - that means we have a cyclic group modulo 29. Further let's say we have a generator point 3. It is impossible to solve the equation:
3^x mod 29 = 13 mod 29
The solution is by the way x=26, which can be only found out by trying all possible combinations.
However, being n the primnumber to calculate the modulus, to compute a discrete logarithm it suffices to be able to get the prime factorization of n+1. To make this as hard as possible the prime number n is usually chosen to be 2q+1 where q is another very large prime number.
NOW COMES THE DANGER:
If the creator of the curve (be it the NIST or the founder of secp256k1) chooses the primenumbers in such a way that p-1 has a small known prime factor
... then despite the prime looks purely random to the average joe, the creator knows the prime factorization and may solve any discrete logarithm in this cyclic group easily (for example using the Pohlig-Hellman algorithm)
What I want to say: If any of the creators remembered the prime factors during creation of the curve, he can calculate your private key in an instant.
All I want to say is: do not trust anyone!
We all know, that the security of ECDSA relies on the complexity of solving the discrete logarithm problem in cyclic groups. ECDSA works on Kolitz-Curves which have a prime number, that they use as the modulo, and a generator which is a primitive root on the curve which - when exponentiated - is able to generate all other elements of the group.
To all of you, who do not know what the discrete logarithm is, here comes a short explanation:
Let us say we work on the Group Z/29Z - that means we have a cyclic group modulo 29. Further let's say we have a generator point 3. It is impossible to solve the equation:
3^x mod 29 = 13 mod 29
The solution is by the way x=26, which can be only found out by trying all possible combinations.
However, being n the primnumber to calculate the modulus, to compute a discrete logarithm it suffices to be able to get the prime factorization of n+1. To make this as hard as possible the prime number n is usually chosen to be 2q+1 where q is another very large prime number.
NOW COMES THE DANGER:
If the creator of the curve (be it the NIST or the founder of secp256k1) chooses the primenumbers in such a way that p-1 has a small known prime factor
... then despite the prime looks purely random to the average joe, the creator knows the prime factorization and may solve any discrete logarithm in this cyclic group easily (for example using the Pohlig-Hellman algorithm)
What I want to say: If any of the creators remembered the prime factors during creation of the curve, he can calculate your private key in an instant.
All I want to say is: do not trust anyone!
*listen*
Is that your final answer? 
Better check wolfram alpha, shit
...I have however not seen any statistical analysis of how high the chances are given we have x bitcoin addresses with balance right now.
perhaps https://eprint.iacr.org/2013/734.pdf
This message was too old and has been purged
Is that your final answer?
Wait a second...
...well I'm glad that's over
This message was too old and has been purged
Careful now
But
p = 2256 - 232 - 977 = 2256 - 232 + (210 - 25 - 23 - 22 - 21 - 20)
p = 2256 - 232 - 977 = 2256 - 232 - (+210 - 25 - 23 - 22 - 21 - 20)
watch that pesky distributive property
whew...
Actually the Prime is:
2256 - 232 - (210 - 25 - 23 - 22 - 21 - 20)
2256 - 232 - (210 - 25 - 23 - 22 - 21 - 20)
But
p = 2256 - 232 - 977 = 2256 - 232 - (+210 - 25 - 23 - 22 - 21 - 20)
whew...
This message was too old and has been purged
Actually the Prime is:
2256 - 232 - 210 - 25 - 23 - 22 - 21 - 20
2256 - 232 - 210 - 25 - 23 - 22 - 21 - 20
I do not understand; 977 is prime. I calculate the sum of your powers of two to be
-210 - 25 - 23 - 22 - 21 - 20 = -1071 = -3*3*7*17
This message was too old and has been purged
Thanks for the correction!
Mike, FYI the solinas curves (rather, the curves employing the primes of that form) offer a reduction/computational speed up that secp256k1 (apparently) does not.
However our curve offers a different computational speed up because of the term a=0 meaning we do not have a term linear in x; our curve is
y^2 = x^3 + 7
So there exists some methods of speeding up division due to group theoretic endomorphisms.
Thanks for the correction!
The prime used in our curve was selected for performance reasons. Unfortunately, this won't help conspiracy theories because the prime used is what's called a Solinas prime:
http://eprint.iacr.org/2010/058.pdf
.... named after Jerome Solinas, who is one of the NSA's top mathematicians.
http://eprint.iacr.org/2010/058.pdf
.... named after Jerome Solinas, who is one of the NSA's top mathematicians.
This is incorrect. The paper states a solinas prime has the form
f(2k) = 2m - 2n +- 1
However the curve secp256k1 is defined over finite field Fp with prime characteristic
p = 2256 - 232 - 977
So "our prime" is not a solinas prime as described in your linked article. It is a generalized mersenne prime, but it needn't have the properties stated in solinas' paper.
There are 5 NIST recommended primes of the form f(2k) = 2m - 2n +- 1 that allow solinas reduction which define fields over curves
y2 = x3 + a x + b
all with a = -3. (for example secp256r1)
secp256k1 is in fact once again different in that it specifies a=0. So be careful with comparisons like this. The curve in bitcoin is actually "weird" for multiple reasons.
----------------------------------------------------------------
for kicks, a decimal expansion 2256 - 232 - 977 = 115792089237316195423570985008687907853269984665640564039457584007908834671663
You know if it gets compromised, all of us will lose our bitcoins, so we'll just fork. Very simple. We have a ledger backup at all times. There's no threat.
Well that's not true because if some fellow does have a backdoor, he's probably bright enough to use his advantage wisely e.g. not create a catastrophic, obvious system wide failure before profiting immensely from theft. But this is mythology anyway...
True but scammers are greedy and would give themselves away. Most will also want to get caught to get credit. They'll work for the nsa afterwards.
You know if it gets compromised, all of us will lose our bitcoins, so we'll just fork. Very simple. We have a ledger backup at all times. There's no threat.
Well that's not true because if some fellow does have a backdoor, he's probably bright enough to use his advantage wisely e.g. not create a catastrophic, obvious system wide failure before profiting immensely from theft. But this is mythology anyway...
You know if it gets compromised, all of us will lose our bitcoins, so we'll just fork. Very simple. We have a ledger backup at all times. There's no threat.
Full-strength ECDSA has a $1 billion bounty on it, in every unspent generate transaction that IS a public key.
Woah, wait. Can you explain what would qualify as "Full-strength ECDSA" as you term it? Would a low cost perfect random number generation technique do the trick?
I'm not really familiar with this level of math but I believe I can watch and draw accurate conclusions.
My actual concern is that there are no really people who would have said that bitcoins ecdsa are safe.
It's all based on no proof of a wrongdoing.
If I was to put all my money on it, I would not have been so sure. Nor should you.
My actual concern is that there are no really people who would have said that bitcoins ecdsa are safe.
It's all based on no proof of a wrongdoing.
If I was to put all my money on it, I would not have been so sure. Nor should you.
This is worth discussing...I would be willing to write a primer of some kind on finite fields if its wanted. It looks more complicated than it really is, but that is always true in mathematics I guess.
I can read these papers because I got a math bachelors I never thought I'd use until now...I am curious as to what people with pure CS backgrounds know about finite fields and groups. If some feedback is given, I can try to bridge the gap.
I've noticed. But his upside down picture is so funny I can't stay mad at him.
Deepceleron, would you please PM me your email address?
Yes, I could have PMed this request. Previously mr celeron was more prompt with my forum posts than with PMs. Excuse the needless bump.
Yes, I could have PMed this request. Previously mr celeron was more prompt with my forum posts than with PMs. Excuse the needless bump.
He's kind of a jerk
Deepceleron, would you please PM me your email address?
Yes, I could have PMed this request. Previously mr celeron was more prompt with my forum posts than with PMs. Excuse the needless bump.
Yes, I could have PMed this request. Previously mr celeron was more prompt with my forum posts than with PMs. Excuse the needless bump.
Therefore, best practice is to not reuse addresses.
Can we tease apart "one time secret reuse vulnerability" with "bad random numbers"?
Question 1: does the reuse of a bitcoin address make the blatant mistake of reusing the k value from the paper I linked
-or-
is this only a problem which arises if the random number generator is poor?
Question 2: will you be in miami this weekend?
Non-reuse is a preventative measure against generic unknown problems. The Android random fault was only exploitable when multiple sends allowed mathematical deduction of the private key, and so not reusing addresses after they have spent would have protected users.
I won't be going anywhere unless you are buying the airfare and sunscreen.
Full-strength ECDSA has a $1 billion bounty on it, in every unspent generate transaction that IS a public key.
Therefore, best practice is to not reuse addresses.
Can we tease apart "one time secret reuse vulnerability" with "bad random numbers"?
Question 1: does the reuse of a bitcoin address make the blatant mistake of reusing the k value from the paper I linked
-or-
is this only a problem which arises if the random number generator is poor?
Question 2: will you be in miami this weekend?
We are not playing with psychology here. Nor politics.
It's all math and science - stick to it.
The risk that these algos have a backdoor are not just some crazy theories. At least not to me. This is a serious shit :-)
Are you really going to risk all you money on the fact that there is no backdoor?
Because I'd prefer not to...
It's all math and science - stick to it.
The risk that these algos have a backdoor are not just some crazy theories. At least not to me. This is a serious shit :-)
Are you really going to risk all you money on the fact that there is no backdoor?
Because I'd prefer not to...
Nothing up my sleeve numbers are a problem for ANY cryptographic scheme. The statement "there may be a backdoor in xyz encryption" is ALWAYS true....
It is my opinion having looked into the matter intensely in the past few days that there is some misinformation being propagated here about secp256k1. In my research I did NOT find any particularly fishy constants in the construction of this scheme.
I have some concerns about secp256k1 that have been documented and are well known, but are distinct in principle to the general message of this thread which is "somebody might know a something about that prime number."
I'm not really familiar with this level of math but I believe I can watch and draw accurate conclusions.
My actual concern is that there are no really people who would have said that bitcoins ecdsa are safe.
It's all based on no proof of a wrongdoing.
If I was to put all my money on it, I would not have been so sure. Nor should you.
My actual concern is that there are no really people who would have said that bitcoins ecdsa are safe.
It's all based on no proof of a wrongdoing.
If I was to put all my money on it, I would not have been so sure. Nor should you.
deepceleron, have you read this paper https://eprint.iacr.org/2013/734.pdf
Can you help me understand the re-use of address problem and whether it applies to the "per message secret" denoted k in the above paper.. introduced in section 2.4
To avoid using the same per message secret, what are your recommendations for best practices?
Your expertise would be appreciated, as the foundations educ. committee loosely suggested that I research this topic for publications for businesses.
I do not wish to continue to bump this thread which has an explosive title. I want to discuss secp256k1 maturely somewhere, without frightening muggles. mods/heores/gmaxwell feel free to tell me where you'd prefer I go...
The paper I posted refers to ways of covertly weakening elliptic curve cryptography by injecting and exploiting faults in use, such as causing off-curve points to be used. This is not a large concern with Bitcoin due to it's address hash protection, but exposes the ways that it can be subverted, such as by a corrupted address generator or a backdoored random number generator. It reminds us that we must not blindly trust the address generation of Bitcoin clients or other tools like vanity generators, and to be vigilant about the random number generator used when signing, spending money.Can you help me understand the re-use of address problem and whether it applies to the "per message secret" denoted k in the above paper.. introduced in section 2.4
To avoid using the same per message secret, what are your recommendations for best practices?
Your expertise would be appreciated, as the foundations educ. committee loosely suggested that I research this topic for publications for businesses.
I do not wish to continue to bump this thread which has an explosive title. I want to discuss secp256k1 maturely somewhere, without frightening muggles. mods/heores/gmaxwell feel free to tell me where you'd prefer I go...
The public key is not exposed until money is spent from a Bitcoin address. After that, there is only one layer of protection, ECDSA, and as we saw with the bad Android implementation where the random nonce is poorly implemented, address reuse may allow others to discover the private key. Therefore, best practice is to not reuse addresses.
We are not playing with psychology here. Nor politics.
It's all math and science - stick to it.
The risk that these algos have a backdoor are not just some crazy theories. At least not to me. This is a serious shit :-)
Are you really going to risk all you money on the fact that there is no backdoor?
Because I'd prefer not to...
It's all math and science - stick to it.
The risk that these algos have a backdoor are not just some crazy theories. At least not to me. This is a serious shit :-)
Are you really going to risk all you money on the fact that there is no backdoor?
Because I'd prefer not to...
It is also a good reason to send your own payments from a well-vetted Bitcoin client, and not reuse addresses or sign lots of stuff with a "money" address.
deepceleron, have you read this paper https://eprint.iacr.org/2013/734.pdf
Can you help me understand the re-use of address problem and whether it applies to the "per message secret" denoted k in the above paper.. introduced in section 2.4
To avoid using the same per message secret, what are your recommendations for best practices?
Your expertise would be appreciated, as the foundations educ. committee loosely suggested that I research this topic for publications for businesses.
I do not wish to continue to bump this thread which has an explosive title. I want to discuss secp256k1 maturely somewhere, without frightening muggles. mods/heores/gmaxwell feel free to tell me where you'd prefer I go...
Let's assume for a minute, that we will be able to manage a migration, that a hard-fork can be successfully executed, is there any other digital signing scheme with comparable performance, key length, history of wide usage like ECC and RSA, that we can migrate to? Anyone cares to enlighten me?
Also Apple doesn't seem to be particularly worried about Curve25519....
Also Apple doesn't seem to be particularly worried about Curve25519....
i think the points you mentioned are precisely why cryptography has gone the way it has in the past 30-40 years. algorithms are not considered usable unless everyone else is already using them, creating a chicken-and-the-egg problem that is tilted substantially to the benefit of the NSA and its sockpuppet, NIST. since people are apprehensive about using lesser-used ciphers and modes, it makes manipulation of the standards process a very potent technique for the NSA to control the quality and ubiquity of encryption.
there are few other options besides ECC for a system with small keys with, as far as anyone knows publicly, comparatively strong security. i would certainly take curve25519 over secp256k1, but migrating the BTC address space would be very non-trivial and everyone would supply the usual "but you can't prove it's broken!" argument. i'm not familiar with any other small-key ciphers that could be a good replacement.
it's too bad that NTRU has such massive key sizes and is covered by many patents: imo, it is the most interesting option for pki currently since it involves almost zero magic constants, unlike RSA and ECC.
If everyone only keeps a ultrapruned chain(not recommended of course) then NTRU key size may not be a problem as only the key hash will be kept anyway.
But in the end I think it's probably a better idea to keep the Damocles sword of ECDSA hanging over us, so that everyone feels some urgency when it comes to the adoption of deterministic addresses.
Let's assume for a minute, that we will be able to manage a migration, that a hard-fork can be successfully executed, is there any other digital signing scheme with comparable performance, key length, history of wide usage like ECC and RSA, that we can migrate to? Anyone cares to enlighten me?
Also Apple doesn't seem to be particularly worried about Curve25519....
Also Apple doesn't seem to be particularly worried about Curve25519....
i think the points you mentioned are precisely why cryptography has gone the way it has in the past 30-40 years. algorithms are not considered usable unless everyone else is already using them, creating a chicken-and-the-egg problem that is tilted substantially to the benefit of the NSA and its sockpuppet, NIST. since people are apprehensive about using lesser-used ciphers and modes, it makes manipulation of the standards process a very potent technique for the NSA to control the quality and ubiquity of encryption.
there are few other options besides ECC for a system with small keys with, as far as anyone knows publicly, comparatively strong security. i would certainly take curve25519 over secp256k1, but migrating the BTC address space would be very non-trivial and everyone would supply the usual "but you can't prove it's broken!" argument. i'm not familiar with any other small-key ciphers that could be a good replacement.
it's too bad that NTRU has such massive key sizes and is covered by many patents: imo, it is the most interesting option for pki currently since it involves almost zero magic constants, unlike RSA and ECC.
Let's assume for a minute, that we will be able to manage a migration, that a hard-fork can be successfully executed, is there any other digital signing scheme with comparable performance, key length, history of wide usage like ECC and RSA, that we can migrate to? Anyone cares to enlighten me?
Also Apple doesn't seem to be particularly worried about Curve25519....
Also Apple doesn't seem to be particularly worried about Curve25519....
If there is a backdoor, it doesn't appear to have been used yet, so what would they be waiting for?
Awesome topic.
Thanks!
Thanks!
This, along with other platform-dependent concerns, would seem to be a good argument for Bitcoin to pull code out of OpenSSL and roll its own implementation of ECDSA and it's own entropy gathering non-deterministic random generator, so it is not affected by compiling against blindly-trusted user libraries. FIPS140 may be a reduced-security random, and it is a compile option in OpenSSL.
It is also a good reason to send your own payments from a well-vetted Bitcoin client, and not reuse addresses or sign lots of stuff with a "money" address.
It is also a good reason to send your own payments from a well-vetted Bitcoin client, and not reuse addresses or sign lots of stuff with a "money" address.
As Bitcoin knows from painful personal experience our ECDSA depends on a source of good random numbers but that is not the fault of the curve parameters. It has been suggested that we move to a new ECDSA that does not require a nonce. That would solve this random number issue once and for all.
There is already an old thread by Hal about this curve: https://bitcointalk.org/?topic=2699.0
I always been intrigued about why Satoshi choose secp256k1, Bitcoin is the only software I know that use it.
But now we have Ed25519...
I always been intrigued about why Satoshi choose secp256k1, Bitcoin is the only software I know that use it.
But now we have Ed25519...
When I contacted the guy and told him Bitcoin is using secp256k1 his first response was "Fantastic! I didn't think anyone used our curve"
Either by design or luck Bitcoin uses one of the few curves not designed or selected by either the NSA or NIST.
We have a highly technical thread about this already:
https://bitcointalksearch.org/topic/nsa-and-ecc-289795
In this thread I actually contacted the person who is currently the head of the organization that originally selected the parameters for secp256k1 and we had a great email conversation about how the parameters were selected. Please read that thread.
I think most of the people that participated in that thread were convinced that the parameter selections all made sense and there was no way a "back door" was placed in the parameter selection.
The same cannot be said for secp256r1.
There is a pretty good summary of most of the information starting here:
https://bitcointalksearch.org/topic/m.3203238
but I think the entire thread, including the process of discovery is pretty good.
https://bitcointalksearch.org/topic/nsa-and-ecc-289795
In this thread I actually contacted the person who is currently the head of the organization that originally selected the parameters for secp256k1 and we had a great email conversation about how the parameters were selected. Please read that thread.
I think most of the people that participated in that thread were convinced that the parameter selections all made sense and there was no way a "back door" was placed in the parameter selection.
The same cannot be said for secp256r1.
There is a pretty good summary of most of the information starting here:
https://bitcointalksearch.org/topic/m.3203238
but I think the entire thread, including the process of discovery is pretty good.
There is already an old thread by Hal about this curve: https://bitcointalk.org/?topic=2699.0
I always been intrigued about why Satoshi choose secp256k1, Bitcoin is the only software I know that use it.
But now we have Ed25519...
I always been intrigued about why Satoshi choose secp256k1, Bitcoin is the only software I know that use it.
But now we have Ed25519...
Since this thread will get read more because of its incendiary first post subject without problem or solution, I'll repost more prominently a paper that I've had a glance through. Essentially, implementation of the fault attack described on compressed keys may make a ECDSA secret discoverable to an attacker with few or even one signature and security reduced to 2^50 instead of ~2^128, but may effected from a very subtle implementation client code change, such as changing the sign of the y.
http://perso.univ-rennes1.fr/reynald.lercier/file/FLRV08.pdf
This, along with other platform-dependent concerns, would seem to be a good argument for Bitcoin to pull code out of OpenSSL and roll its own implementation of ECDSA and it's own entropy gathering non-deterministic random generator, so it is not affected by compiling against blindly-trusted user libraries. FIPS140 may be a reduced-security random, and it is a compile option in OpenSSL.
It is also a good reason to send your own payments from a well-vetted Bitcoin client, and not reuse addresses or sign lots of stuff with a "money" address.
http://perso.univ-rennes1.fr/reynald.lercier/file/FLRV08.pdf
Quote
With the curve secp256k1, the order of the twist is
3×197×1559×96769×
146849×2587814237219×375925338294461779×
101009178936527559588563023359.
So on implementations without protections, the attacker can compute the discrete logarithm in the twist with a cost of 250 and retrieve the secret scalar for n = 256.
3×197×1559×96769×
146849×2587814237219×375925338294461779×
101009178936527559588563023359.
So on implementations without protections, the attacker can compute the discrete logarithm in the twist with a cost of 250 and retrieve the secret scalar for n = 256.
This, along with other platform-dependent concerns, would seem to be a good argument for Bitcoin to pull code out of OpenSSL and roll its own implementation of ECDSA and it's own entropy gathering non-deterministic random generator, so it is not affected by compiling against blindly-trusted user libraries. FIPS140 may be a reduced-security random, and it is a compile option in OpenSSL.
It is also a good reason to send your own payments from a well-vetted Bitcoin client, and not reuse addresses or sign lots of stuff with a "money" address.
The prime used in our curve was selected for performance reasons. Unfortunately, this won't help conspiracy theories because the prime used is what's called a Solinas prime:
http://eprint.iacr.org/2010/058.pdf
.... named after Jerome Solinas, who is one of the NSA's top mathematicians.
http://eprint.iacr.org/2010/058.pdf
.... named after Jerome Solinas, who is one of the NSA's top mathematicians.
so we can't trust NSA-supplied magic numbers?
next thing you know we'll find out we're all being spied on all the time to protect us from invisible islamic badguys.
The prime used in our curve was selected for performance reasons. Unfortunately, this won't help conspiracy theories because the prime used is what's called a Solinas prime:
http://eprint.iacr.org/2010/058.pdf
.... named after Jerome Solinas, who is one of the NSA's top mathematicians.
http://eprint.iacr.org/2010/058.pdf
.... named after Jerome Solinas, who is one of the NSA's top mathematicians.
We are using p = 2^256 - 2^32 - 977
source: https://en.bitcoin.it/wiki/Secp256k1
Vitalik Buterin wrote a great paragraph addressing exactly your point:
source: http://bitcoinmagazine.com/7781/satoshis-genius-unexpected-ways-in-which-bitcoin-dodged-some-cryptographic-bullet/
source: https://en.bitcoin.it/wiki/Secp256k1
Vitalik Buterin wrote a great paragraph addressing exactly your point:
Quote
The simplicity of these parameters gives the NSA / NIST very little wiggle room to create a deliberately bad curve. And even the specific values of 0, 7 and 977 can be justified by security and efficiency constraints, so the chance that Bitcoin’s elliptic curve parameters were chosen with any malicious intent is very low indeed.
source: http://bitcoinmagazine.com/7781/satoshis-genius-unexpected-ways-in-which-bitcoin-dodged-some-cryptographic-bullet/
Disclaimer: I'm not a cryptography expert (not even close).
But I believe that the Elliptic curve [secp256k1] that is used in Bitcoin is in a special class called Koblitz curves, for some reason this makes it less likely (impossible?) that the pre-defined curve parameters have been "cooked" to make a backdoor attack possible for the creators.
Although I'm lead to believe this curve has performance benefits for signature verification, but with the drawback that it only offers about 128-bit level security vs. the assumed security level of 256-bit.
Hopefully an expert out there can explain it better than I have.
But I believe that the Elliptic curve [secp256k1] that is used in Bitcoin is in a special class called Koblitz curves, for some reason this makes it less likely (impossible?) that the pre-defined curve parameters have been "cooked" to make a backdoor attack possible for the creators.
Although I'm lead to believe this curve has performance benefits for signature verification, but with the drawback that it only offers about 128-bit level security vs. the assumed security level of 256-bit.
Hopefully an expert out there can explain it better than I have.
legendary
Activity: 1862
Merit: 1011
Reverse engineer from time to time
The way you word the thread reminds me a lot about the X-Files http://en.wikipedia.org/wiki/Trust_No_1
This message was too old and has been purged
This message was too old and has been purged
Jump to: