How to prove to someone that an Bitcoin address (or UTXO) belongs to you?

[aliashraf]

Neither RIPEMD-160 nor SHA256 are subject to such attack. They are not analytical and only a brute force attack is feasible to be run by adversaries which is not practical and will not be practical in foreseeable future, hence, they are safe now.

Yes SHA256 and RIPEMD160 algorithms are safe today but even if they are not linked to large number arithmetic, there is not proof that they cannot be reversed or predicted in polynomial time and space. As for ECDSA, they is no proof that ECDLP cannot be solved. Today the security of ECDLP256 is ~128bit and 160bit for RIPEMD160. Both are not feasible today but the probability that someone find a way to solve ECDLP256 or to reverse hashing algorithms is not zero. It is not possible to predict which algorithm will be defeated first.
There is no objective reason to say that exposing ECDSA public key for a long time is less safe than exposing an address.

I'm not comfortable with this argument. ECDLP has been discredited by Shor's algorithm which offers polynomial time/space solution for a QC based machine, the very nature of discrete logarithm problem is fragile and vulnerable to further mathematical developments just like what happened with Shor algorithm and QC vulnerability, it is not exactly the case for SHA256 or RIPEMD160 we have no reason to be worried about them to break and if anybody has any concern about such a possibility even in next couple of centuries s/he should stop using bitcoin as a store of value.

[1715561652]

1715561652

[1715561652]

1715561652

[1715561652]

1715561652

[Jean_Luc]

A true 256 qbit register does not exists and probably won't exist. All "quantum computer" today are based on "retry" which means that to experiment a true state superposition over a large number of qbit you need in fact many tries and this number of tries increase with the number of qbit. No worry from the QC.
ECDLP and SHA are not yet vulnerable and no argument can indicate that ECDLP is less vulnerable than SHA. ECDLP256 has a security of 128bit since the beginning and no significant improvement has been made despite intensive research.

[bob123]

There is also no reason today to discourage exposure of public key.

Some wallets state there is some privacy concern with the hd wallets I think.

Exposing a public key is fine.
You shouldn't expose your master public key (xpub) to not compromise your privacy.

The xpub is used to generate all public keys of your wallet (-> all addresses can be generated out of it).

But exposing single public keys is completely fine, privacy- and security-wise.

[aliashraf]

There is also no reason today to discourage exposure of public key.

Some wallets state there is some privacy concern with the hd wallets I think.

Exposing a public key is fine.
You shouldn't expose your master public key (xpub) to not compromise your privacy.

The xpub is used to generate all public keys of your wallet (-> all addresses can be generated out of it).

But exposing single public keys is completely fine, privacy- and security-wise.

No, it is not. Please stop spreading misinformation, exposing public key is identical with address-reuse which is not recommended actually it is strongly discouraged

Recently, I had a debate with Greg Maxwell in which he admitted that Core devs have abandoned a very impressive proposal that allows for multiple utxos with same pubkey to be signed just once in the body of a transaction, because it might have incentivizing impacts on address-reuse. Note that such an improvement would improve bitcoin performance instantly and considerably if it was not refuted because of address-reuse incentivizing side effects!  .

If you think address-reuse is secure please start a topic and enlighten us and be ready for me not mentioning Gregory Maxwell to argue against you, it is a very bad practice to make such arguments that are not based on generally accepted principles in bitcoin in the middle of a QA with newbies.

I'd say something like this If I was you: "Although it is not recommended in bitcoin and actually it is explicitly discouraged to disclose pubkey behind unspent utxo addresses, I think it is fine and mainstream is wrong and I'll prove myself in the future, blah, blah, blah"  

[RHavar]

All things being equal, I agree it's best not to expose your pubkey.  But let's not overstate things. For instance here's an address with 69471 BTC on it 1HQ3Go3ggs8pFnXuHVHRytPCq5fGG8Hbhx  the pubkey is 02545d2c25b98ec8827f2d9bee22b7a9fb98091b2008bc45b3b806d44624dc038c


That's basically a 350 million dollar bounty right there. (and that's not nearly the only address like that).  The sky isn't falling on ECC just yet.

No, it is not. Please stop spreading misinformation, exposing public key is identical with address-reuse which is not recommended actually it is strongly discouraged

Address re-use is absolutely terrible for bitcoin-privacy, I think it's the single-biggest thing that makes blockchain analysis really easy (you can do pretty reliable spend-clustering). So I do my best to try encourage people to never reuse addresses, but the direct security implications are pretty minor.

[Jean_Luc]

Up to now, exposing public key is safe. They're might be wrong implementation of signature software that can allow to guess the private key, that's true. But it is the exactly same problem for addresses generation. Side channel attacks are also possible on software that generates addresses. Lot's of people reuse addresses and continue to do it. Without speaking of privacy, exposing public key is as safe as exposing address. Be afraid of a conspiracy or of unknown mechanisms that can allow your private key to be discovered is totally unjustified.

[ABCbits]

Without speaking of privacy, exposing public key is as safe as exposing address. Be afraid of a conspiracy or of unknown mechanisms that can allow your private key to be discovered is totally unjustified.

Actually, there are 2 valid mechanism to expose one's private key :
1. Finding flaw or put backdoor on random (RNG, PRNG, CSPRNG, etc.) system. Example : https://bitcoin.org/en/alert/2013-08-11-android
2. Put backdoor on k values of ECDSA. Reference : https://bitcoin.fr/public/divers/docs/klepto-ecdsa.pdf

Fortunately, most wallet are open-source so both mechanism to discover user's private key is minimized. Still i wouldn't say "as safe as", but "almost as safe as".

[aliashraf]

All things being equal, I agree it's best not to expose your pubkey.  But let's not overstate things. For instance here's an address with 69471 BTC on it 1HQ3Go3ggs8pFnXuHVHRytPCq5fGG8Hbhx  the pubkey is 02545d2c25b98ec8827f2d9bee22b7a9fb98091b2008bc45b3b806d44624dc038c


That's basically a 350 million dollar bounty right there. (and that's not nearly the only address like that).  The sky isn't falling on ECC just yet.

First of all you are welcome to argue about it in a dedicated topic and we will see how it goes, my main concern is the context in which we are right now: A newbie asks a question and we need to stay in same rail with the accepted literature or we have to explicitly mention that we are speaking off the axis.

Secondly, it is old story in cryptography: cracks and fixes, bitcoin does not rely on ECC as much as most people suppose, side-channel attacks are always possible and the algorithm itself is not proved to be bullet proof, it is very bad idea to put your funds in hands of such a system for a long period of time at least it is not how bitcoin is considered to be secure.

Your example about the exposed pubkey is the first victim of the next successful attack on ECC, being a side-channel attack, a QC computer, a more optimized search algorithm, anything.

No, it is not. Please stop spreading misinformation, exposing public key is identical with address-reuse which is not recommended actually it is strongly discouraged

Address re-use is absolutely terrible for bitcoin-privacy, I think it's the single-biggest thing that makes blockchain analysis really easy (you can do pretty reliable spend-clustering). So I do my best to try encourage people to never reuse addresses, but the direct security implications are pretty minor.

You are overemphasizing on privacy and underestimating security concerns here.
Again, I think this topic is not the right place for such a discussion. As far as it is about generally accepted principles of bitcoin we have to discourage exposure of public keys, specially by using them for signing messages.

[Jean_Luc]

Actually, there are 2 valid mechanism to expose one's private key :
1. Finding flaw or put backdoor on random (RNG, PRNG, CSPRNG, etc.) system. Example : https://bitcoin.org/en/alert/2013-08-11-android
2. Put backdoor on k values of ECDSA. Reference : https://bitcoin.fr/public/divers/docs/klepto-ecdsa.pdf

Fortunately, most wallet are open-source so both mechanism to discover user's private key is minimized. Still i wouldn't say "as safe as", but "almost as safe as".

The first mechanism apply also to address generation. Other mechanisms, such as side channel can applied to address generation too. So saying that public key exposure is not safe and discourage it is not justified at all. People who think that SHA is more safe than ECC has no argument to justify this. No one can say which algorithm will be defeated first. Again there is no proof that SHA cannot be reversed.
Having the feeling that SHA is more safe than ECC because ECC is based on large integer arithmetic is just a feeling. Not a fact !
"A more optimized search algorithm" can also apply to SHA.

[aliashraf]

@Jean_Luc bro, you are seriously wrong in comparing ECC with Sha2 both in their vulnerability to side-channel and direct attack. Bitcoin will collapse immediately if there could be found a flaw, it relies totally on security of sha256. It is not the case with ECDSA256k1, bitcoin needs this scheme to resist just few minutes against search attacks when it is used properly, disclosing pubkey extends this requirement which nobody can guarantee for any encryption algorithm for infinite time (unlike hash functions) to be satisfied. Actually I can guarantee that in less than few decades ECDSA256k1 will be breakable by a QC computer in polynomial time (not necessarily and effectively in few minutes)

Saying that because both sha256 and ECC are some mathematical functions implemented by computer codes and they are both exposed to hypothetical attacks so let's rely on both or rely on none, is not a strong argument.

As of the core algorithm: ECC is based on vague/unproven assumptions about discrete logarithm being non-polynomial in time and space which is challenged already by Shor algorithm and QC. SHA256 is not based on such assumptions.

As of side-channel attacks: ECDSA256k1 is a complicated algorithm with a lot of design and implementation choices, we have a history of successful side-channel attacks against its implementations, it is not the case for SHA256.

last words: Would you personally put your life saving for next two-three decades in a wallet with an exposed public key? I wouldn't!

[Jean_Luc]

@Jean_Luc bro, you are seriously wrong in comparing ECC with Sha2 both in their vulnerability to side-channel and direct attack. Bitcoin will collapse immediately if there could be found a flaw, it relies totally on security of sha256. It is not the case with ECDSA256k1, bitcoin needs this scheme to resist just few minutes against search attacks when it is used properly, disclosing pubkey extends this requirement which nobody can guarantee for any encryption algorithm for infinite time (unlike hash functions) to be satisfied. Actually I can guarantee that in less than few decades ECDSA256k1 will be breakable by a QC computer in polynomial time (not necessarily and effectively in few minutes)

Address generation is also subject to side-channel attack, it depends on the implementation. I agree, if ECDLP can be solved in few minutes, bitcoin would die and if SHA can be reversed in few minutes, bitcoin would also die. Today ECDLP takes ages to be solved. Your argument is ok if ECDLP becomes feasible in let's say few years or months but the probability that ECDLP256 becomes feasible in fews years or month and not in few minutes in nearly zero.

Saying that because both sha256 and ECC are some mathematical functions implemented by computer codes and they are both exposed to hypothetical attacks so let's rely on both or rely on none, is not a strong argument.

You have to rely on both algorithms.

As of the core algorithm: ECC is based on vague/unproven assumptions about discrete logarithm being non-polynomial in time and space which is challenged already by Shor algorithm and QC. SHA256 is not based on such assumptions.

It is exactly the same for SHA, it is based on vague/unproven assumptions that the set of solution becomes more and more difficult to describe at each round.

As of side-channel attacks: ECDSA256k1 is a complicated algorithm with a lot of design and implementation choices, we have a history of successful side-channel attacks against its implementations, it is not the case for SHA256.

I'm speaking of address generation which is also vulnerable to side-channel attack. SHA alone is also vulnerable to Meltdown attack.

last words: Would you personally put your life saving for next two-three decades in a wallet with an exposed public key? I wouldn't!

I wouldn't put my life in a wallet in any case, with pubkey exposed or not.

[aliashraf]

Today ECDLP takes ages to be solved. Your argument is ok if ECDLP becomes feasible in let's say few years or months but the probability that ECDLP256 becomes feasible in fews years or month and not in few minutes in nearly zero.

It is not true.

On the contrary a gradual collapse is exactly what will happen with 99% possibility.

"The authors of the Logjam attack estimate that the much more difficult precomputation needed to solve the discrete log problem for a 1024-bit prime would be within the budget of a large national intelligence agency such as the U.S. National Security Agency (NSA). The Logjam authors speculate that precomputation against widely reused 1024 DH primes is behind claims in leaked NSA documents that NSA is able to break much of current cryptography." (Wikipedia)

Diffie-Hellman Cryptography (DHC) is based on discrete-logarithm problem just like ECC and the above quote from Wikipedia clearly shows that breaking it is not about a "in few minutes or never" scenario, it is about optimizations and technology and costs.

Also your argument proves to be wrong, considering how QC technology is under development right now: they scale qbit by qbit slowly but continuously. Once they've proved to be able to break ESDCA in like couple of years bitcoin community would have enough time to enhance their cryptography scheme and users could gradually move their funds to new addresses.

[Jean_Luc]

It is not true.

On the contrary a gradual collapse is exactly what will happen with 99% possibility.

"The authors of the Logjam attack estimate that the much more difficult precomputation needed to solve the discrete log problem for a 1024-bit prime would be within the budget of a large national intelligence agency such as the U.S. National Security Agency (NSA). The Logjam authors speculate that precomputation against widely reused 1024 DH primes is behind claims in leaked NSA documents that NSA is able to break much of current cryptography." (Wikipedia)

With that kind of information, you can prove what you want. The best known precomputation (Bernstein and Lange) needed to solve the discrete log problem is just huge and not feasible even for the NSA. The only advantages of this precomputation is for solving multiple instance but for a single instance it does not bring benefits.

Also your argument proves to be wrong, considering how QC technology is under development right now: they scale qbit by qbit slowly but continuously. When they proved to be able to break ESDCA in like couple of years bitcoin community will have enough time to enhance their cryptography scheme and users can gradually move their funds to new addresses.

The difficulty of adding qbit does not grow linearly and it is interesting to see that De Broglie's prediction concerning QC seems to be more and more true, and that the Pilot wave theory in which I believe becomes more and more attractive.

[aliashraf]

The best known precomputation (Bernstein and Lange) needed to solve the discrete log problem is just huge and not feasible even for the NSA. The only advantages of this precomputation is for solving multiple instance but for a single instance it does not bring benefits.

Interestingly, we are talking about multiple instances, aren't we?

I'm not saying that it is broken right now, ECC, my argument is about the main attack range not being a magical mathematical technique that solves ECDLP in a glance, it is about optimizations, algorithm back doors, pre-computations,  and technology enhancements that gradually justify costs of an attack against its rewards.

[Jean_Luc]

Interestingly, we are talking about multiple instances, aren't we?

Yes but even for multiple instance, the precomputation is still enormous and not feasible for a 256bit prime.

I'm not saying that it is broken right now, ECC, my argument is about the main attack range not being a magical mathematical technique that solves ECDLP in a glance, it is about optimizations, algorithm back doors, pre-computations,  and technology enhancements that gradually justify costs of an attack against its rewards.

You can think the same for addresses. There is no objective reason today to say that RIPEMD160(SHA2(pukey)) brings a supplementary protection and you can even think that using directly pubkey could be more reliable. A failure can also come from the function f(x) = RIPEMD160(SHA2(x)).

[bob123]

Also your argument proves to be wrong, considering how QC technology is under development right now: they scale qbit by qbit slowly but continuously. Once they've proved to be able to break ESDCA in like couple of years bitcoin community would have enough time to enhance their cryptography scheme and users could gradually move their funds to new addresses.

There it is again. The magic everything-solving-machine called quantum computer 

I like how people - who are extremely far away from that topic - believe that quantum computers are a magic machine which can solve almost any mathematical problem in a short amount of time.


So.. quantum computing will break ECDSA in like a couple years ?    Wtf dude, what did you smoke ?
Quantum computing is BY FAR not developed enough to be used for something useful yet. And it definitely won't be in 'a couple of years'..

Even if quantum computers would be ready to do that by then.. there first has to be an efficient algorithm developed. There aren't much quantum computing algorithms available yet..
It is not like you say 'Hey quantum computer, give me private key of satoshi' and 10 minutes later you get the result.. It is slightly more complicated than that.. even if non-techy people like you can't believe it..

[aliashraf]

Also your argument proves to be wrong, considering how QC technology is under development right now: they scale qbit by qbit slowly but continuously. Once they've proved to be able to break ESDCA in like couple of years bitcoin community would have enough time to enhance their cryptography scheme and users could gradually move their funds to new addresses.

So.. quantum computing will break ECDSA in like a couple years ?    Wtf dude, what did you smoke ?
Quantum computing is BY FAR not developed enough to be used for something useful yet. And it definitely won't be in 'a couple of years'..

I'm not saying QC is ready in few years, not as confused as you thanks god  

I mean QC will be developed enough sooner or later (put it few decades for instance) to break one ECC key in reasonable time window: 2 years or so e.g. A commercial QC with enough power to break a key in a long, still feasible, time window.

Look at the context, I'm arguing that breaking exposed pubkeys is the first damage that QC or any attack to ECC could ever cause.
For ordinary exposure of public keys in bitcoin transactions, the time window to cause any damage is very short and it is unlikely to have QC or any other technology coming from nowhere and managing for such a destructive attack. They'll begin with easier targets and the whole point of this discussion is discouraging bad practices that turn wallets to such targets. Period.

[Jean_Luc]

I simply wanted to say there are valid mechanism to discover private key

OK.

Also, if SHA could be reversed, attacker/thief still need to reverse ECC as well to take user coins (ignoring mining system broken and powerful quantum computer)

Yes but if you manage to reverse the address hashing function, you will be able to get a very large number of public key that match with the address and it will reduce drastically the complexity to find a matching private key.

[bob123]

Yes but if you manage to reverse the address hashing function, you will be able to get a very large number of public key that match with the address

And how exactly do you think you are going to do that?

With quantum computing 

It is magic machine.

[aliashraf]

Neither QC nor any other technology could ever do anything about SHA256 because its search space is astronomical and behind human technology. It is provably resistant to collision attacks up to 128 bits security, there is no way to manage a collision attack on such a huge search space. Plus, it is not used in bitcoin for authentication purposes hence its vulnerability to length extension attacks is irrelevant and finally, the best public attacks break its preimage resistance for 52 out of 64 rounds  and going just one round higher is not considered feasible with current techniques and reaching to 54 rounds is another order of magnitude harder and so on, by using sha256 twice, bitcoin practically resists 128 rounds against preimage attacks which is another astronomical resistance index.

SHA256 is not vulnerable to any form of side-channel attack because of its deterministic nature as a hash function. Above thread @Jean_Luc has argued many times that potential vulnerability of ECC to side-channel attacks is just a general property and applicable to SHA-2 as well. This is not correct, side-channel attacks are effective in cryptography when multiple outputs for the same input(s) are possible and the attacker can narrow the search space by taking advantage of her knowledge about the implementation holes.

Comparing ECC security to SHA256 and asserting that they are equally safe is simply wrong. On one side, ECC has experienced a handful of side channel attacks and belongs to a class of cryptographic algorithms that are basically vulnerable to this attack and on the other side there is a QC compatible algorithm (Shor) provably capable of solving discrete-logaritm problem in feasible polynomial time/space. Whether QC becomes commercially available or not, it proves one point: cryptographic electronic signature algorithms are transient technologies for a specific state of technology and mathematics development, unlike strong hash functions.