Topic: Script variation for improved account security (Read 1462 times)

Hi Revalin.

First, thank you for the crypto info and the wallet suggestions.  Your suggestions are almost the same as what I concluded.

Regarding: In 2001 IBM successfully used Shor's Algorithm to factor 15 into 3x5,
See: https://en.wikipedia.org/wiki/Shor%27s_algorithm  and  https://en.wikipedia.org/wiki/Nuclear_magnetic_resonance_(NMR)_quantum_computing
"NMR quantum computing experiments are likely to have been only classical simulations of a quantum computer."
So the IBM experiment does not satisfy true quantum requirements.  There are other experiments that did demonstrated entaglement, but only for a couple qbits.
There is a huge problem bridging classical and quantum mechanics.  The general relativity equivalence principle (the heart of GR) has been verified through measurement to at least 12 decimal places. That is more accurate than many laws of physics.
Single photon measurements are not sufficiently accurate to confirm some very basic quantum properties like in a Mach-Zehnder interferometer.
Vacuum energy density esimates are not even close between classical and quantum predictions.

The proof of concept examples only demonstrate a very small/simple factorization that has only one answer.  Does this demonstrate by measurement the polynomial time factorization speed?

Sorry, this is off topic.  I do find it fascinating though.

Kind regards.

Incorrect.  Quantum mechanics is a set of actual physical phenomena which are completely real and observable.

Quantum computers exist today.  In 2001 IBM successfully used Shor's Algorithm to factor 15 into 3x5, which is the smallest meaningful application possible.

The threat is not imminent, but it's definitely a concern in the long run (50+ years).  It's not yet known if a quantum computer powerful enough to crack crypto will ever be possible.  It's possible that the power requirements will prevent it from being feasible.  NMRQC (as used by IBM) certainly won't scale to crypto-cracking sizes.  Nonetheless, it's still a significant proof of concept.

As for ECDSA, the short term threat that it, like all public key crypto, is based on principles that are less thoroughly explored and understood than symmetric and one-way crypto.  It is therefore generally considered more likely that a significant cryptographic flaw will be found in ECDSA than in SHA2 or RIPEMD.



I suggest:  create a series of paper wallets and make one deposit to each address, using standard RIPEMD addresses, which I consider to be the strongest form.  By breaking it into a series of smaller wallets you remove the incentive to crack a single large wallet (in case of a partial break which requires considerable cost to complete).  When you eventually spend, send the change to another new address each time.

Then make several copies of the paper, and keep them in several safe locations.  You are far more likely to lose your coins because you either lost the keys or someone else found your wallet than due to a crypto break.

I think that new version of Satoshi ("official") wallet can redeem multisigs if you have all the keys. One of recent betas can also create multisigs if you have all the pubkeys by using "addmultisigaddress" commands, but I don't know if it was already deployed to release versions.
For instructions see this: https://en.bitcoin.it/wiki/BIP_0016_QA

Also this functionality was recently removed from blockchain.info online wallet. Try asking the author to re-enable it.

Thanks DeathAndTaxes and DeepBit.

I also found: https://bitcointalksearch.org/topic/iswill-bitcoin-wallet-trawling-become-a-thingthreat-78471
and that Revalin is an expert.  As the founder of Tangible Cryptography LLC, DeathAndTaxes probably is also.  It is great to get comments from people that really know what they are talking about.

The main issue with using the public key instead of the Bitcoin address appears to be what Revalin stated:
"Once coins have been sent FROM the address the pubkey is known and ECDSA is probably the weakest link (about 128 bits of security equivalent).  This may be plausible to attack in the distant future, but probably not in my lifetime unless a cryptographic flaw is discovered."
Using the address hash appears to be actually more secure than ECDSA, so the drop in security bits from 256 to 160 is not actually real, only perceived due to the weakness of ECDSA.

So, it appears that trying to use a long term account is not really worthwhile.  For anonymity, it tends to tie all your other accounts/transactions together in the blockchain.  Not good either.
Using a new account number for each receiving transaction, including for change accounts, appears to be the safest solution.
It also is about as well as one can do for anonymity.  It is very difficult to purchase anything using Bitcoins that requires delivery of the purchase by a commercial carrier (to a street address or PO Box) without compromising yourself to some extent.  For online only there is TOR.
The key for anonymity appears to be to minimize linkages between accounts (all permutations for sending/receiving).

This seems to imply that a wallet should try to minimize the number of transactions used for the source coins and also avoid using a change account if practical.
The wallet is definitely the weakest link.

Am I on track here?

BTW DeepBit, how does one do multi-signature transactions on Bitcoin?
Do you know a good website link?

Thanks.

If you need a long term storage just don't withdraw from that transaction output and your pubkey will never be published.

At this moment bruteforcing even just your hashed pubkey is not feasible (unless if was created by known methods from meaningful words/passphrase).
While ECDSA is not broken and quantum computers don't exist it can be considered safe enough.

Also if you think that ECDSA bruteforce is a threat, you may try multisignature transactions like 2-of-2 or 3-of-3 so it would take a bit longer :)
(sadly it's not as effective as doubling the key length)

You already answer it is above (2^256)/(2^160)  Of course that large number is of only academic interest.  160bit or 256 bit neither can be bruted forced.  Not with a single computer, not with a planetary sized super computer (and yes including the effect of Moore's law for the next century).

IF addresses are ever vulnerable in the future it is because one of the cryptographic primitives has become compromised not because of some brute force attack.  In such a compromise storing coins at an address where the public key is unknown to the public (and thus some future generation attack) "could" prevent an attack.  It would depend on exactly which cryptographic primitive is compromised, how it is compromised and how severe that compromise is.


Baring a cryptographic flaw in ECDSA?  Secure.  Unless there was a flaw in selecting the private key (cryptographically weak random number generator) your only option would be brute force.  A far more useful layer of protection for the ultra paranoid would be a hardware RNG where the output is simply not repeatable. 

Thank you Gavin Andresen, gmaxwell, Revalin and DeepBit for your replies.  They are very helpful.

I am starting to understand this better.  My concern is based in the long term safe storage of Bitcoins.  Directly using a single account for this would leave many transactions in the blockchain for both receiving and spending coins.  While this could be masked by using temporary (wallet) accounts to transfer coins into and out of the long term account before transfers from or to other's accounts, it will still be in the blockchain, so the public key would not be completely hidden (like if not used in any transaction), and would be easy to obtain from the blockchain if one knows one of the temporary account numbers.

I don't believe that the quantum computer threat is very immanent. I find it very difficult to believe that quantum computers will ever physically exist.
Quantum physics is based on a purely mathematical formulation rooted in probability, not physical phenomena.  It does not have a direct tie to reality.

The Bitcoin address does hide the public key using a hash {RIPEMD160(SHA256())}, which does a very good job of protecting the public key.  It makes a lot more sense why it is recommended not to spend from the same account number more than once.  Then, the public key is not exposed except for a very brief duration, leaving very little time to try to exploit it.  Does exposure of the public key really matter?

I do not disagree that the probability of an accidental address collision is incredibly improbable.
My concern is the intentional collision possibility.  Guessing a private key that will result in the same public key seems less likely than a key pair that has the same address hash.  However, depending on how many public keys have the same address hash, the guesser gets an advantage due to the increased possibility of a collision at the address hash level, relative to the public key level.

According to https://en.bitcoin.it/wiki/Elliptic_Curve_Digital_Signature_Algorithm
"public key: A number that corresponds to a private key, but does not need to be kept secret."  So one would either have to guess at the private key or determine a way to crack ECDSA using the blockchain info related to the address and/or public key.  Guessing at a truly random private key is incredibly improbable.  If the private key is derived from a passphrase (brain wallet), the possibility might become feasible or even likely.

The private key has a security level of 256 bits.  The MD160 has a security level of 160 bits.  It would appear that a single Bitcoin address would collide with about (2^256)/(2^160) or about 8x10^28 public keys.  It is probably not this simple, but an address collision certainly seems much more probable than a public key collision, if that is even possible.

If someone would be willing to comment on this, I would really appreciate it.

The key issues seem to be:
1) Approximately how many ECDSA public keys can have the same address hash?
2) How secure is the private key when the public key is known?
      (This is addressed a little at http://en.wikipedia.org/wiki/Elliptic_Curve_DSA, which seems to indicate it is as difficult as guessing the private key.  Also at http://eprint.iacr.org/2002/129.pdf   and   https://bitcointalksearch.org/topic/is-the-ecdsa-public-key-hashed-as-a-extra-level-of-protection-10697)
Also: http://bitcoin.stackexchange.com/questions/22/is-it-possible-to-brute-force-bitcoin-address-creation-in-order-to-steal-money

Thanks!

No, hiding your public key is more secure for long-term storage, especially against (potential) attackers with quantum computers :)

Example of send-to-pubkey transaction:
https://blockexplorer.com/tx/e39c0c43ddc4bc8d3fd3bd1faf93dc22adac8778a32a66fe1d65c64af5a5fd84
(see output 0)

It's an extremely small possibility because 2^160 is a very big number:

1461501637330902918203684832716283019655932542976

If 10 billion people generate a million addresses every day for 100 years, you end up with:
365000000000000000000

Notice that there are a LOT less digits in that number.  Due to the birthday paradox the possibility that SOME address will collide is considerably larger (but still remote), but the possibility that YOUR address will collide is practically zero.

As mentioned above, you can use the sig directly if you wish, but I would not recommend it.  The chance that it would be a problem on accident is vanishingly small.  The real concern is an attacker creating a collision on purpose.  ECDSA is considered much weaker cryptographically than RIPEMD160(SHA256()), so for practical purposes, you're probably better off using the MD160 key with a virgin address with no public spends (which would reveal the pubkey).

As Gavin says, spend-to-pubkey is valid— and it's used by the reference software for mined blocks. (and, IIRC, it used to be use for send-to-IP transactions, you'd connect to an IP and the peer would give you a pubkey to send to)

That it would increase the security is doubtful, however.  The hash function has comparable size to the ECDSA security margin, and while hash functions can be attacked being able to generate a _valid_ ecdsa key which you have the private component to which matches an arbitrary (or even any of billions) of specific hashes is basically inconceivable to me and itself would likely require both an ECDSA break and a hash break of a kind never seen on any modern hash.

If I were a betting man, I'd say it's more likely (but still unlikely) that someone would find a way of compromising some ECDSA public keys with large but feasible amounts of computation.  Under this threat model the use of hashed keys is protective, because your public key isn't revealed until just before compromising it is pointless so long as you do not reuse addresses.

There is, in fact, a oddbal altcoin proposal call MAVEPAY which uses ordered disclosures of hash preimages as its _only_ signing primitive.  (it's crazy for a bunch of reasons, but fact that you can build a plausible signing system out of just ordered disclosures of single hash inputs (e.g. not high overhead like lamport) suggests that you shouldn't discount the security benefit of that)

Hi Gavin.

I was reading at: https://en.bitcoin.it/wiki/Transactions#Types_of_Transaction

I am still a little confused and/or misunderstanding.  Let's look at a very simple transaction, using all the bitcoins from a single previous transaction sent to another single account.  Am I correct here?
For a transfer to bitcoin address transaction, the scriptSig contains the sig and the public key, where the sig is the altered current transaction encoded using the private key.  This is the first part of the transaction and specifies the previous transaction (transaction ID hash in the outpoint) that is the source of the coins.
The scriptPubKey is retrieved from that previous transaction and used to verify that this new transaction is authorized.
Now, the scriptSig should always be self consistent as it should have been generated by a private/public key pair.
For the scriptPubKey of: OP_DUP OP_HASH160 OP_EQUALVERIFY OP_CHECKSIG
The public key from scriptSig is duplicated, hashed, compared to the scriptPubKey hash (to verify authority) and then the signature is checked for validity.  If the scriptPubKey was generated by a private/public key pair, it will verify, even if it is not the correct public key, as long as the public key has the same hash (Bitcoin address).  So this does not stop two public keys that have the same hash from each being able to access the coins.

For a transfer to IP address, which you seem to be referencing, the process is simpler and even more secure, as it splits the scriptPubKey data between the two transactions.
The public key is specified in the previous transaction in the scriptPubKey.  The current transaction only provides the sig in the scriptSig.  Now, both authorization and verification are combined into one step.  The public key from the previous transaction is used to verify the sig encoded using the private key in the current transaction.  There cannot exist two private keys such that a single public key can verify the sig generated using either private key, right?

Do I understand this correctly?

I like the latter method better as it avoids the hash issue and results in shorter transactions.  Its main drawback is it requires the previous sender to use the public address instead of the bitcoin address (short address).  It also precludes obtaining a balance from the block chain using the Bitcoin address.  The balance has to be obtained using both the public key and the bitcoin address to be complete (both types of transactions being possible in the block chain).

Why is it called a transfer to IP address if the IP address is not part of the transaction?

Thanks.

{full public key} OP_CHECKSIG is a valid, standard transaction type, redeemed by providing just {signature}.

I'm trying to determine if the following variation for the script associated with the transaction receiving account is valid for processing by the Bitcoin network.
Can someone answer this?
I could just try it, but I decided to ask first to see if someone knows the answer or has other informative comments.

Instead of:
OP_DUP OP_HASH160 {hash of public key} OP_EQUALVERIFY OP_CHECKSIG

use:
OP_DUP {full public key} OP_EQUALVERIFY OP_CHECKSIG

The purpose of this being to avoid the possibility of two public keys having the same hash, which would allow either party to spend the bitcoins.
I am not familiar with how small this possibility actually is.
The only reason to use it would be to transfer coins into a "savings" type account (like a paper wallet) so they are more securely "stored" in the block chain.
This would be a transfer between two (or more) accounts belonging to the same person.
It is not appropriate for regular transactions since it is not part of the standard wallet and it is much easier to use the base-58 Bitcoin address for such transactions.

I appreciate your comments.

Thanks.