This message was too old and has been purged

[deepceleron]

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.

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.

[piotr_n]

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.

[Altoidnerd]

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

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

[Altoidnerd]

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?

[deepceleron]

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.

[Altoidnerd]

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.

[bitpop]

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.

He's kind of a jerk

[Altoidnerd]

I've noticed. But his upside down picture is so funny I can't stay mad at him.

[Altoidnerd]

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.

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.

[Altoidnerd]

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?

[bitpop]

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.

[Altoidnerd]

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

[bitpop]

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.

[Altoidnerd]

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.

This is incorrect. The paper states a solinas prime has the form

f(2^k) = 2^m - 2ⁿ +- 1

However the curve secp256k1 is defined over finite field F_p with prime characteristic

p = 2²⁵⁶ - 2³² - 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(2^k) = 2^m - 2ⁿ +- 1 that allow solinas reduction which define fields over curves

y² = x³ + 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 2²⁵⁶ - 2³² - 977 = 115792089237316195423570985008687907853269984665640564039457584007908834671663

[Mike Hearn]

Thanks for the correction!

[Altoidnerd]

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.

[Evil-Knievel]

This message was too old and has been purged

[Altoidnerd]

Actually the Prime is:

2²⁵⁶ - 2³² - 2¹⁰ - 2⁵ - 2³ - 2² - 2¹ - 2⁰

I do not understand; 977 is prime.  I calculate the sum of your powers of two to be

-2¹⁰ - 2⁵ - 2³ - 2² - 2¹ - 2⁰ = -1071 = -3*3*7*17

[Evil-Knievel]

This message was too old and has been purged

[Altoidnerd]

Careful now

Actually the Prime is:

2²⁵⁶ - 2³² - (2¹⁰ - 2⁵ - 2³ - 2² - 2¹ - 2⁰⁾

But

p = 2²⁵⁶ - 2³² - 977 = 2²⁵⁶ - 2³² + (2¹⁰ - 2⁵ - 2³ - 2² - 2¹ - 2⁰)
  

p = 2²⁵⁶ - 2³² - 977 = 2²⁵⁶ - 2³² - (+2¹⁰ - 2⁵ - 2³ - 2² - 2¹ - 2⁰)

watch that pesky distributive property

whew...