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

[Jean_Luc]

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.

You should claim the recompense to the Clay institute for this

[ryap12]

I would have never know that signing is risky.  

Since you guys are talking about vulnerability when someone signs a bitcoin wallet address, can someone prove that by accessing the 1 BTC puzzle on this thread?

--> https://bitcointalk.org/index.php?topic=5096267.0

The owner signed the wallet address so I want to see how you guys do it for those who are saying that there is a risk doing it. But if the only way of accessing it is using a powerful Quantum computer then I guess we are still a few years away to get our hands into QC.

 

[Jean_Luc]

I fail to see how such a thing could reverse two hashing functions.

You can use the magic Grover's algorithm and a partial RIPEMD160 round reversing (Biclique attack) to decrease drastically the complexity of finding collisions on RIPDEMD160(SHA2(x))

You are way off.

https://www.scottaaronson.com/papers/qchvpra.pdf

In fact the O(2^(n/3)) cannot be achieved due to memory complexity (Read this https://eprint.iacr.org/2017/847.pdf).
But the Grover's algorithm optimization proposed by Inria's researcher can achieve O(2^(n/2.5)) with a feasible memory complexity ( still need few million dollars of investment just for the classic memory ) and this algorithm has a very interesting feature, the complexity can be greatly reduced for multiple targets.
RIPDEMD160 consists of 2 parallel and independent hashes that are merged with simple additions (mod 2^32) at the end, and this can be easily exploited to create efficient multiple target attack on the 2 independent hashes RIPEMD160_1(SHA2(x)) and RIPEMD160_2(SHA2(x)).

[Jean_Luc]

I would have never know that signing is risky.  

It is not if you sign with a reputed secure software on a computer where you are alone (not subject to various side channel attack).

[gmaxwell]

Please keep the thread on-topic. Insulting each other is not on-topic. (This message will self-destruct)

[Jean_Luc]

I would like to apologize if I was hurtful but I was a bit choked by the question of AntiMaxwellian.
Sorry.

[VTC]

I can't believe everyone got this wrong:

There is only one way certain way to prove ownership, and that is by giving your PRIVATE KEY to that someone.

After that moment, both you and them become "owners" of that address as both of you control the ability to sign messages and move funds (if any exist). If one of you discards the private key, and has no physical/mental backup of it, nor any recollection, they lose ownership.

1) Having a signed message that belongs to that public hash does NOT prove you have ownership, it's mearly proves to someone, that you possess that signed message, but you might or might not be the orginal actual signer or owner.

2) Showing that a dust amount from that address has been sent to another address of someone's choice, does NOT prove you have ownership, it only proves that someone, but not nessesary you, is the owner.

A good real life example of the misconceptions of 1 or 2 is all the OTC scams that take place, where the scammer is a man in the middle but appears to be an owner.

If you want to prove ownership of an address that has funds, you move the funds out first, and give out the private key, proving that at one point you possessed ownership of the previous address that had a balance. (Warning: giving out a single private key and xpub key for an unhardened hd wallet derivation can lead to an attacker taking all your wallet funds)

[bob123]

I can't believe everyone got this wrong:

There is only one way certain way to prove ownership, and that is by giving your PRIVATE KEY to that someone.

~snip~

If you want to prove ownership of an address that has funds, you move the funds out first, and give out the private key  [...]

Then a malicious actor just needs to gain access to your master public key (xpub) to derive all of your private keys belonging to this HD wallet (non-hardened only).


Signing messages is fine to prove ownership.

1) Having a signed message that belongs to that public hash does NOT prove you have ownership, it's mearly proves to someone, that you possess that signed message, but you might or might not be the orginal actual signer or owner.
[...]
A good real life example of the misconceptions of 1 or 2 is all the OTC scams that take place, where the scammer is a man in the middle but appears to be an owner.

Of course you wouldn't sign a message like "i own this address".
You would include your name, the current date and the reason for signing this message. And eventually even a random token from the person who wants you to prove the ownership.

A MitM wouldn't be useful in any way here.

[Jean_Luc]

Signing messages is fine to prove ownership.

Of course you wouldn't sign a message like "i own this address".
You would include your name, the current date and the reason for signing this message. And eventually even a random token from the person who wants you to prove the ownership.

Right, this is the good way to do however it is better to define the full format of the message to sign (including restrictions on the fields) with the third party in order to prevent from a birthday paradox attack on the signature.

[bob123]

[...]  in order to prevent from a birthday paradox attack on the signature.

A birthday attack is applicable to hash functions, not encryption or signatures.

Further, with the birthday paradox you would calculate the probability of creating 2 messages which result in the same hash (any random hash!).
Not a second message with the same (given) hash which the signed one has.


This is not applicable in this case. Neither theoretical nor practical.

[Jean_Luc]

OK, i wrote this a bit too fast. I was thinking to create a random walk for the birthday paradox on the hash of the signature in order to exploit it the signature process but it ends in solving the discrete log using classic random walks (of course, with public key previously exposed). So it is even not necessary to create a random walk from the signature hash.

[PrimeNumber7]

There is only one way certain way to prove ownership, and that is by giving your PRIVATE KEY to that someone.

After that moment, both you and them become "owners" of that address as both of you control the ability to sign messages and move funds (if any exist). If one of you discards the private key, and has no physical/mental backup of it, nor any recollection, they lose ownership.

This is a very bad practice, and I think you should not do this under almost any circumstances.

Giving someone your private key can potentially make you look very bad in the future. For example if you publicly state a particular address belongs to you, and the third party later goes on to do some nasty illegal or harmful stuff and that address is involved in receiving or sending a payment for this stuff.

1) Having a signed message that belongs to that public hash does NOT prove you have ownership, it's mearly proves to someone, that you possess that signed message, but you might or might not be the orginal actual signer or owner.

I alluded to this point previously.

A signed message could be the result of the real owner being tricked into signing a message, or the real owner colluding with a third party, attempting to fraudulently prove they own a UTXO/address they do not own.

[bob123]

There is only one way certain way to prove ownership, and that is by giving your PRIVATE KEY to that someone.

If we're strictly talking about certain way to prove ownership,  then even giving private key isn't enough. There are many cases where user tricked into download fake/malicious wallet where the theft could use it to prove ownership.

If we are strictly talking about ownership (in terms of: i created the private key, it belongs to me), there is not a single method to absolutely be sure (in a bulletproof way).

A private key is not something one has, but something one knows. That's a big difference.

Proving ownership of a hardware token (i.e. a hardware token for pgp signing for example) can be done by signing messages easily.
But simply proving ownership of something you know is itself not possible (very strictly talking).

Information (something you know) can be duplicated. Hardware tokens (something you have) can not. Or.. at least they should not be able to be duplicated.


However, i think this is going way too far.
As per OP's title the question is how to prove that an address belongs to you. And regarding this, anything is fine. A signed messages (containing a random token + user not blatantly stupid to get phished) is the best way.
The question was not how to prove that one is the ONLY one who knows this private key. That's simply not possible.