ECC key strenth after many sigs

[doobadoo]

Kind of a junior crypto question here, but does a the strength of a pub/private ecdsa key pair weaken if the privkey is used to sign a significant number of msgs.

I know that reusing the K value is instant death, but assuming the msgs were generated correctly should one be concerned never using a new receiving address?

I ask bc if one were to create a bitcoin service that wanted to provide an instant proof to a user of funds under administrator control, the user could send an arbitrary hash value to the server, which could then be signed by all the privkeys corresponding to all publicly controlled pubkeys.  

would the creator of such a service have to worry about a user DDOSing the service in order to scrape a large number of sigs generated by all his privkeys for all the loot he controls, as a way to make it easier for the attacker to derive the privkeys?

That is to say, imagine if an exchange operator did this.  Should he be worried about using the privkeys securing user funds to send perhaps millions or billions of sigs to an adversary trying to derive the privkeys?

[doobadoo]

I know that satoshi had change by default sent to a new receiving address which the network therefore had no pubkey or signed msg to.  Was this out of 'overly protective' motherly concern for a poor RNG being used to generate sigs and possibly reducing the space of potential K values ala the Sony cockup...

[ktorn]

[...] does a the strength of a pub/private ecdsa key pair weaken if the privkey is used to sign a significant number of msgs.

In a nutshell: In theory it does weaken. In practice, it doesn't matter... yet.

Just spending from an address already weakens it, because it involves signing the transaction with the private key, which is why re-using addresses is a bad practice also from a security point of view (in addition to the privacy issue).

In practice there is no imminent danger when signing transactions and messages, because the computational effort required to derive the private key from the publicly available information is still prohibitively large, but further down the line there is the small matter of quantum computing, as Vitalik explained.

Having said that, the Merkle-Signature Scheme (MSS) is resistant to quantum computing, so it may well become adopted by cryptocurrencies well in advance of quantum computing availability.

Related References:

• Bitcoin Is Not Quantum-Safe, And How We Can Fix It When Needed
• Bitcoin vs. The NSA’s Quantum Computer
• StackExchange: Is it possible to weaken a bitcoin private key by “using” it elsewhere?

Edit: just wanted to add that, as you mentioned, K should never be reused, and a good random number generator should be used if you plan to sign a large number of messages.

[doobadoo]

create a bitcoin service that wanted to provide an instant proof to a user of funds under administrator control, the user could send an arbitrary hash value to the server, which could then be signed by all the privkeys corresponding to all publicly controlled pubkeys.

Um?  Couldn't an attacker just send a hash of  a transaction, and thereby trick the service into signing the transaction so the attacker could steal the bitcoins?

No...the hash must be arbitrarily determined by the user requesting proof, or else an intercepted or purchased sig could be presented as ones own.  BTC sigs include all relevant tx components, amount, time, rec add as well as the sha256 tx hash included in a valid msg sig.  Attacker would have to derive a hash that produces the same sig as a valid tx w/o the privkey (probably harder than outright key forgery).

More likely some one would figure out a way to increment the arbitrary data in such a way the curve parameters are eventually revealed, which brings us back the question of whether or not lots of sigs can be used to weaken a privkey secrecy.

To blunt that possibility:

The server could just rehash the arbitrary user hash w/random salt and transmit that...user informed of server's salt and algo rounds and thus verifies that response msg was generated by holder of privkeys containing crypto proof that sig incorporates user's challenge hash msg.

[DeathAndTaxes]

Under normal circumstances no.  

There is a side channel attack which allows recovery of private key with as little as 200 signatures but that requires access to the physical machine.  Not sure if it could be implemented on a VPS running on hardware the attacker has access to.  

Flawed PRNG is one another possible risk, attacker could attempt to flood you with requests to reduce the entropy pool.  A proper PRNG should block until the entropy pool recovers but if someone took a shortcut you could be signing with reduced entropy which in theory would make the signatures weaker.  Weak enough to brute force?  Not sure but I would use RFC6979 to create deterministic singatures and thus remove the need for PRNG all together.

Lastly this isn't an attack issue but possibly an implementation one.  If the number of signatures is relatively large (say you have 1000 private keys) and lots of users request it you in theory could be talking about a significant computing overhead on the server.   Unless you absolutely need real time proofs I would batch user requests by having user provide a seed/nonce.  Concatenate all user request nonces and add that to the end of the message to be signed.  You probably don't need to have users provide nonces as a message without user provided nonce would prove the same information.  User provided nonces don't really add any security.  The message only proves you have control of the private keys.  The actual verification of the amount those keys control requires auditing the blockchain.

However in either case the message you sign should never be just a nonce or hash as you subject yourself to an impersonation attack.  It should be something explicit and absolutely useless to a third party trying to impersonate you.  

Example:

The results of the cryptographic audit #00000001 for XYZ Inc, as of 05/07/2014 21:37 UTC.  XYZ Inc, currently is holding 999.12345678 BTC of user funds, secured by 38 public keys.  Signatures of this message for all 38 public key are provided with this message.  The following are nonces requested by users since the last audit 0xEBAAEDCE6AF48A03BBFD25E8CD0364141 0xBBFD25E8CD0364141FEBAAEDCE6AF48A03 ... etc

To verify users can confirm their nonce is in the list of nonces for the batch (not really necessary), that the signatures of the message for all keys are valid and that the balance of those keys matches the expected amount.  By signing at a set interval rather in real time the number of signing will not increase exponentially with the number of users.

In summary
a) Don't use VPS for hot wallets (you shouldn't anyways)
b) Use RFC6979 to reduce your dependency on proper PRNG function
c) Batch user requests (once signing per hour/day/etc) to reduce load on server.


Lastly there is no risk of message signatures being substituted for transactions.   The Bitcoin message signing system takes the actual message and prepends "Bitcoin Signed Message:\n" to it.  So even if a user provided you an actual transaction to sign what actually is signed becomes "Bitcoin Signed Message:\n<user provided transaction>".  This was done intentionally to ensure users couldn't be tricked into signing a malicious transaction.