(quoted post by mcdett)

What is being hashed in this function? <— let’s call this item x

If the total number of possible x is smaller than 256bit space that sha256 provides than an attack would come in the form of a table of all sha256(x) values.

If all of the possible combination’s of x is greater than the 256bit space, then here is some math for you (the attack would be at the hash value itself rather than a table on known sha256(x)):

What follows is from www.atmel.com/dyn/resources/prod_documents/doc8668.pdf

If there are 256 bits in the key, then after 2^255 attempts the attacker has a 50% chance of finding the right key and after 2^256 attempts he has tried all possible keys and is guaranteed to have found the key.

Here are some estimates of big numbers:

2^66 Number of grains of sand on the earth 2^76 Number of stars in the universe 2^79 Avogadro’s number. The number of carbon atoms in 12 grams of coal. 2^96 Number of atoms in a cubic meter of water 2^190 Number of atoms in the sun 2^255 Number of attempts to find the key value from above

But what about very well funded entities such as the US National Security Agency (NSA)? Could they build a machine to crack a 256 bit key? Assume they could build a theoretical nanocomputer that executes 10^13 instructions per second (approximate rate of atomic vibrations) in a space of a cube with a side that is 5.43nm across (This is the approximate size of a silicon lattice10 atoms wide, or a crystal containing 1000 silicon atoms). Assume that it could calculate an attempt in 10 cycles. Such a computer the size of the earth would take more than 10^13 years (roughly 58 times the estimated age of the earth) to attack a 256 bit algorithm via brute force.

Quote from: mcdett on July 15, 2010, 03:56:42 PM

…

2^255 Number of attempts to find the key value from above

1. Your equations don’t take into account reversible computing advancements at all. These techniques could halve the search space by being able to take advantage of algorithms that traditional computers find impossible.

2. Your equations assume the algorithm is perfectly secure. Given that NIST is rather gung ho about developing SHA-3, I’m not terribly confident in that analysis.

3. An attacker does not need to find a specific key to compromise the system, they just need to find the keys to someone’s wallet. If you want this to be a viable currency for Earth’s population, plus corporate accounts, you drop the search space by 10^10 to 10^12.

That 2^256 search space could get whittled down to the 2^110 range by the end of the century. Assuming no major attacks on its integrity exist.

I’m not particularly sold on the technical soundness of this program, honestly. Why use SHA256 rather than Whirlpool or SHA512?

Quote from: Some Mouse on July 15, 2010, 11:06:29 PM

I’m not particularly sold on the technical soundness of this program, honestly. Why use SHA256 rather than Whirlpool or SHA512?

For the same reason they didn’t use SHA1024 or SHA2048 or SHA4048 or SHA1000000000000000000000000000000000

There are lots of theoretical attacks that can be done against it, but if a program or new math proof can half the amount of time it takes to crack it, are we really worried about the encryption taking 100 billion years to crack but now with this new attack (insert math,attack,flaw) it’s only going to take only 1 billion years to crack? How about a million years? Even one-hundred thousand years?

When they can crack SHA256 in under 10 minutes, I’ll be worried, but until then, time is on your side.

Quote from: knightmb on July 15, 2010, 11:42:49 PM

For the same reason they didn’t use SHA1024 or SHA2048 or SHA4048 or SHA1000000000000000000000000000000000

No. SHA512 and Whirlpool exist, are well defined, well supported, well analyzed, and they exist for a reason.

Reversible computing techniques ‘cheat’ around the entropy limit. This means they can reach effective speeds far, far beyond what are possible with current computers, as they are effectively capable of performing nondeterministic operations.

You are basically betting the entire economy (if you believe bitcoins will succeed anyway) on no one developing a means to halve the effective bit length as has been done with e.g. AES.

It’s careless.

Ten years, assuming only minor flaws in SHA256.

If there is a major flaw (again, see the push for SHA-3) there is a much more serious problem. There does not appear to be a clear mechanism for handling a compromise of the basic algorithm, and there should be.

That’s why I’m glad we have people like you here to participate in the discussion as well. A room full of “yes men” is a dangerous thing. Grin

Quote from: Some Mouse on July 16, 2010, 12:13:52 AM

Reversible computing techniques ‘cheat’ around the entropy limit. This means they can reach effective speeds far, far beyond what are possible with current computers, as they are effectively capable of performing nondeterministic operations.

Wait, what? I thought reversible computation just uses less energy. Where does the non-determinism come in?

Anyway, about the hashing being insecure: Wikipedia says that attacks on SHA-256 still take on the order of 2250 operations. And unless I made a big thinko here, doesn’t the hash target change every ~10 minutes? Wouldn’t that throw of an attacker? And if it was possible to break SHA faster, wouldn’t the system adjust by raising the difficulty level?

Quote from: DataWraith on July 16, 2010, 11:27:46 AM

Wait, what? I thought reversible computation just uses less energy. Where does the non-determinism come in?

It’s the theoretical limit of how far you can go with it. When doing a brute force search, you can reverse back to any previous state and try new states.

It’s doubtful that SHA2 would be that broken before all coins have been minted. The issue is it then becomes a question of how much it costs to hijack someone’s bank account.

SHA256 is not like the step from 128 bit to 160 bit.

To use an analogy, it’s more like the step from 32-bit to 64-bit address space.  We quickly ran out of address space with 16-bit computers, we ran out of address space with 32-bit computers at 4GB, that doesn’t mean we’re going to run out again with 64-bit anytime soon.

SHA256 is not going to be broken by Moore’s law computational improvements in our lifetimes.  If it’s going to get broken, it’ll be by some breakthrough cracking method.  An attack that could so thoroughly vanquish SHA256 to bring it within computationally tractable range has a good chance of clobbering SHA512 too.

If we see a weakness in SHA256 coming gradually, we can transition to a new hash function after a certain block number.  Everyone would have to upgrade their software by that block number.  The new software would keep a new hash of all the old blocks to make sure they’re not replaced with another block with the same old hash.