Topic: How to prove to someone that an Bitcoin address (or UTXO) belongs to you? - page 2. (Read 1139 times)

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


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

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.

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.


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.

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.

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.


You have to rely on both algorithms.


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.


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


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

@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!

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.

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.

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.

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

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.

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"  

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.

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.

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.

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.

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.

It is not the case with ECDSA-256k1, both QC and conventional digital computers on the hardware side and algorithms on the software side are under development right now and it is feasible to have this scheme broken in near future, hence, it is not safe now.

Once you disclose the public key behind a utxo without spending it (and making it useless this way), you have given a large window of time (as long as you keep the utxo untouched) to the adversary equipped with enough resources and knowledge to break it unlike what happens with an ordinary transaction in which it is exposed to such an attack just for few minutes.

Still I think the line of reasoning you follow makes it pointless to denounces address re-use anyway, if you can't say re-using bitcoin addresses is not safe, why should you discourage such a practice? You think I can't call it "not safe" so it is safe according to you, isn't it? Or may be it is somehow, something between safe and unsafe a shady status in security measures probably, both safe and not safe or neither safe nor not safe. What is it after all?

Lets' go back to the root of this long discussion: exposing the Public key.

Okay, either of the two methods will indirectly expose the address' public key. By spending the UTXO, the user will have to provide a Signature and Public key to the scriptsig.
But as everyone mentioned, it's pretty safe as long as the user hasn't been reusing addresses.

---

The topic is getting derailed from "How to prove that an address belong to you?" to ECDSA security.

To sum it up, since either is "fine", let's categorize the main question from:

• 1. How to prove to someone that an Bitcoin address belongs to you?
• 2. How to prove to someone that an UTXO belongs to you?

[1] Sign a message.
[2] Sign a message or Spend the actual UTXO using coin control.

being bigger does not always translate into being safer. in case of PGP most of them use RSA keys and a 4096 bit RSA key offers nearly the same security than a 256 bit EC key (3072 RSA key has equal strength as 256 bit key used in ECDSA, and 7680 is the same as 384).

i think you are confusing my reply! i never suggested address-reuse or never said it is "as safe" to reuse them. all i said was that you can't say it is unsafe today just because it can be broken some day.
all your arguments here can be said about hashes too. RIPEMD160 and SHA256 are going to become obsolete some day as they will be broken but you can't say it is unsafe to use them just because some day they will be broken. after all that is how cryptography has always been working for literary thousands of years

Proving ownership of an address is not a common practice to be worried about unnecessary on-chain transactions. It can't be faked because before transferring funds you announce the address to the counter party as your address, just like when you give your receiving address to other people, you don't need to prove that you own your receiving address because it is where the funds are supposed to go.

You eventually disclose your public key and counter party has to check its RIPEMD-160 hash against the address you claim as your property. Once s/he approves your public key as being the real key behind the address, information has leaked and it is not safe as we will see.

As of your safety argument: You are absolutely wrong.
1- Historical transactions have been stoned in the blockchain and it is why they are safe not because of security of ECDSA.

2- ECDSA 256k1 becoming broken "some day"does not imply a magical invention that makes it a piece of cake for average intruder to guess keys in like few seconds or minutes, it means progress in algorithms and hardware that primarily makes it feasible for a large processing power to do the job in polynomial time/space (for instance in weeks or months using few Exa bytes of memory). Bitcoin could safely operate for a couple of months or a year after such progress because the public keys are exposed to this attack in a very short window of time (pending phase of the txn) that won't last more than few minutes. But permanently leaked public keys/re-used addresses are exposed to the attack for months or years.

3- You know that re-using addresses in bitcoin is not recommended, I wonder how do you think about it? Are you a fan of re-using addresses? Why not?

I don't agree with this and I will explain why:

If you can provide a signature of a signed message, you are only proving you have seen the signature in the past. A well known example of this is CSW providing a signature of one of satoshi's early transaction as a "signed message" to prove he is satoshi. Does this signature prove CSW is satoshi, no it absolutely does not because the signature he provided is public information. Is CSW actually satoshi, I would keep an open mind if presented with additional credible evidence, but in my opinion he is in no way satoshi.

The above is an extreme example. Another example is someone can trick the "real" owner into signing a vague message and presenting that vague signed message as your own. If "Bob" were to be tricked into giving "Jack" the signature to the following message: "This is Bobs address and it is 2:45 PM" then Jack could present himself as being "Bob, and could present this signed message anytime it is shortly after 2:45 PM.

Using similar names, Jack could be willing to help Bob trick others into believing that Bob owns a particular "address" or UTXO, and could provide Bob with a specific signed message that makes others believe the UTXO belongs to Bob.

You could alleviate a lot of the above risk by asking Bob to sign a specific message that contains random data that you ask to be included in the signed message, and you are personally present when Bob receives the specific message you provide up until he provides the message. This will still not 100% guarantee Bob controls the private key associated with the address in question because he could still be communicating with Jack electronically, and would be risky for Bob if he does control the private key because he could be vulnerable to a "$5 wrench" attack.

In short, all providing a signed message will do is prove you have seen the associated signature.