Is it really 256 bit? Or is it really 160 bit?

[doobadoo]

The typical way to spend btc is to lock them to a receiving address which is a 160-bit representation of a 256 bit ECDSA script.  In theory, couldn't an attacker present a different pubkey and  a signed message to redeem coins on an address which happens to hash to the same address as the legit owner?  Wouldn't the odds of this collision be 2^160  (yes yes thats A LOT of keys to generate) but its not 2^256 now is it?

Additionally, lets assume there are 65k addresses worth stealing from, i'll steal from any of these (2^16).  Doesn't that now reduce the number of hashes i'd have to go through to 2^144?

Its still a poopload of key pairs to generate, my guess is only a few hundred or few thousand could be iterated/sec on a standard pc.

But this raises the question:  why didn't satoshi use sept160k1 which would have pubkeys of only 40+ digit hex (corresponding to the strength of ripemd160), instead of 64+ digit hex for sepc256? 

Again, in theory we can reduces the 2^256 sets of key pairs to just 2^160, cuz as I get it, to spend a balance you only have to show a pubkey which ripemd160 hashes to the receiving address.

Did i miss something or is the ECDSA really just 160 (or 144) bit strong?

[1714505825]

1714505825

[1714505825]

1714505825

[1714505825]

1714505825

[1714505825]

1714505825

[DeathAndTaxes]

Yes against a collision attack the effective strength is 2^160.  However it is possible the security of ECDSA will be degraded in the future.  Asymetrical encryption historically has been more vulnerable to cryptoanalysis than hashing functions.  So say in 2020 a defect is found in ECDSA which recudes the effective key strength to only 218 bits.   While we should look towards migrating to stronger addresses types in the futue it would be of only academic value in the short term.

Say on the other hand, Satoshi used 160 bit ECDSA keypair and a flaw is discovered which weakens it to 118 bits.  Still a lot of hashes but you are getting close to what is theoretically possible to attack.  If the flaw was critical and further analysis weakened 160bit ECDSA down to 80 bits you are in brute force range especially with a custom ASIC processor.

TL/DR using a larger keypair provides a level of insurance against marginal degradation in the security of ECDSA but your right the effective key strength is the min of all crypotgraphic primitives.

[doobadoo]

Thanks!  That makes total sense now.

[Zeilap]

But this raises the question:  why didn't satoshi use sept160k1 which would have pubkeys of only 40+ digit hex (corresponding to the strength of ripemd160), instead of 64+ digit hex for sepc256? 

What you're missing is that paying to 160-bit script hash is an addition that wasn't part of the original client. Originally you paid directly to the full public keys.

[gmaxwell]

Did i miss something or is the ECDSA really just 160 (or 144) bit strong?

The 256-bit ECDSA is really only 128 bit strong. The hash is not the limiting factor.

[jackjack]

But this raises the question:  why didn't satoshi use sept160k1 which would have pubkeys of only 40+ digit hex (corresponding to the strength of ripemd160), instead of 64+ digit hex for sepc256? 

What you're missing is that paying to 160-bit script hash is an addition that wasn't part of the original client. Originally you paid directly to the full public keys.

Are you saying that you had to put a public key in the client when you wanted to pay someone?

[killerstorm]

Yes against a collision attack the effective strength is 2^160.

This requires a (second) preimage attack rather than a collision attack. http://en.wikipedia.org/wiki/Collision_attack

As long as SHA-256 isn't broken, ypur only option is bruteforce... Or attack against ECDSA if public key is known.

(Note: preimage attack isn't enough, it will merely give you a set of matching public keys which might make it easier to find a matching keypair. I'm just saying that preimage attack is required to utilize weakness in hash.)

[Mike Hearn]

No. In the original Bitcoin releases, the primary way you were meant to pay other people was by typing in their IP address (no joke) and your client would directly connect to theirs to get a public key. The problem being that it was entirely unauthenticated so anyone who could fiddle with your internet connection could steal the money.

We're bringing this concept back but in a slightly less 1990's era way, with the payment protocol work. But this time it's authenticated so you know who you're paying, it's designed to be useful for hardware wallets, it supports a bunch of other good stuff too. And it'd allow you to ask people to pay directly to a public key, should you so wish to avoid the overhead of addresses.

Now is that really a good idea? As gmaxwell points out, secp256k1 gives you 128 bits of security. So the address form makes no difference. And pay-to-pubkey optimises overall chain size for a larger UTXO set - I think it's presently unclear which is preferable over the long run.

[Shevek]

Did i miss something or is the ECDSA really just 160 (or 144) bit strong?

The 256-bit ECDSA is really only 128 bit strong. The hash is not the limiting factor.

I don't agree with this.

256-bit ECDSA is 128 bit strong in the unlike scenario of anybody searching collisions between two hazard keys (birthday paradox).

But more realistic scenario is looking for collisions with specific keys hoarding large amounts of BTCs. In this case 256-bit strength remains.

[gmaxwell]

I don't agree with this.
256-bit ECDSA is 128 bit strong in the unlike scenario of anybody searching collisions between two hazard keys (birthday paradox).
But more realistic scenario is looking for collisions with specific keys hoarding large amounts of BTCs. In this case 256-bit strength remains.

ECDSA is not a hash function. At attacker with the pubic key isn't confined to use the dumbest possible brute-force attack.

Pollard's lambda algorithm takes sqrt() operations— so roughly 2^128 security.

[n4ru]

You're more likely to steal coins using a brain wallet attack than actually trying to bruteforce any of the addresses with a balance. Even with a GPU rig of 5870s which hash at 30MKeys/sec each you wouldn't be able to bruteforce anything useful for a very, VERY long time.

[kjj]

I don't agree with this.
256-bit ECDSA is 128 bit strong in the unlike scenario of anybody searching collisions between two hazard keys (birthday paradox).
But more realistic scenario is looking for collisions with specific keys hoarding large amounts of BTCs. In this case 256-bit strength remains.

ECDSA is not a hash function. At attacker with the pubic key isn't confined to use the dumbest possible brute-force attack.

Pollard's lambda algorithm takes sqrt() operations— so roughly 2^128 security.

Most people aren't aware that elliptic curve algorithms, in general, require about twice as many bits of keyspace as their security level.    The wikipedia article on key size provides a half-decent introduction to the topic.

Security is measured in effective key length, which really boils down to "how many operations are needed to break this?".  It is the key size of an ideal system that can only be brute forced, but provides the same level of security.

Most symmetric systems have effective key sizes equal to (or nearly equal to) their actual key size.  For example, AES uses 128 bit keys, and provides 128 bits of effective key size.*

Public key systems, however, suck in that regard.  Algorithms based on prime factors require keys at least 16 times as large for the same security level.  Think 2048 bits of keyspace for 128 bits of security.  ECDSA looks a lot better by comparison, only needing twice as many key bits.

*  Two interesting things to note.  First, 2¹²⁸ is WAY beyond our ability to break, and will remain that way for a long time.  Second, AES was designed with quantum attacks in mind.  You should be using the 256 bit extension of AES if you think that someone might actually figure out how to build a machine that can run Grover's algorithm and a reversible single circuit version of the AES transform.  This is because Grover's reduces the effective key size by half, which is the same thing as taking the square root of the key space.

[Shevek]

Pollard's lambda algorithm takes sqrt() operations— so roughly 2^128 security.

Thanks for the point. I was unaware of such "Pollard lambda" attack to DL problem; I only knew about "Pollard rho" for factoring.