Topic: Energy requirements to brute force SHA-256 (Read 499 times)

My intuition instantly said "no", way too little energy.
But to make sure, I did a rough, back-of-the-envelope calculation.

2^256 * 1.56×10^-32 joules ~ 1.8 × 10^45 J
e=mc^2 converts that to 20,027,701,008,965,131,779,133,619,367,264g, or give or take 3,350 earths!

Now, that may seem a lot, but the Schwarzschild radius of an object with that mass is less than 30m.
Since we're packing that in a sphere much larger than 30m, it's not a black hole.

Again, I could be off by orders of magnitude and we'd still get nowhere close to a block hole.
So, our only hope for a black hole earth still rests with the LHC.

Hmm.  What's the necessary energy density to form a black hole?

M = E / C²

Is it possible that an earth sized computer with enough energy packed into that earth sized space to "brute force SHA-256 within a human's lifetime" might collapse into a black hole, meaning that even if it could find a key, there'd be no way to get that information out of the computer?

well that example works the way it is, you can't change the example itself. it is a simplified explanation of why it is irreversible.


Gödel's incompleteness theorems is talking about basic arithmetic and is mostly a philosophical theory. not to mention that the reply there is mostly talking about cryptography in general (like encryption) not hash and the reply is making the conclusion about "preimage" attack not reversing the hash function.

you can't say SHA-1 is broken because it is not. that is why it is still being used in many places such as in git and PGP. and it is still irreversible. nothing has changed in that front.

this hash function is only insecure for certain usage where certain type of collision is important, because so far the only attack against SHA-1 has been a special form of collision attack where the attacker can decide what the message is. in other words he controls both m1 and m2 and finds a hash h that is the same for both m1 and m2. and that still requires computing 2^63.1 hashes. and if the attacker has no control on messages then he still has to compute at least 2⁸⁰ hashes (have h(m) and want to find m2 where the hash is equal to h(m)).

No.


No.

Think about it like this...

I have a digital map with directions that show exactly where my buried treasure is hidden.

I also have a secondary password that I used as an encryption key to scramble the map into a digital cipher.

If you have my digital cipher file AND you know my password, then you can decrypt (unscramble) the cipher back into the original digital map and get to my treasure.

HOWEVER, you don't know my password AND you don't have my cipher file. Therefore, you decide to just "brute force" my map.  You start generating completely random digital maps, and checking to see if they lead to a treasure.  After many, many, many years you get extremely lucky and the digital map that you randomly generate is exactly the same as my original map.

Do you now ALSO need my secondary password to go get my treasure?

No.  The only purpose of the secondary password was to decrypt the encrypted map.  Since you now have a copy of the original map, you can just use it to go get the treasure. You no longer need the digital cipher or the password.

Bitcoin works the same way.

If you generate a private key for a vanity address, then the private key is the "map" that allows you to access the funds that are received using that vanity address.  Just like with the map, anyone with that private key has access to those coins.

If you then import the private key into a wallet and have a password for that wallet, all you've done is encrypted (scrambled) the private key using the password as the encryption key, and stored that scrambled cipher in a file that the wallet has access to.  Anytime you want to use the wallet, you provide the password so that the wallet can decrypt the key and then use the decrypted key to access the bitcoins.  If anyone steals your wallet, they need to know your password to decrypt the key.

However, if they "brute force" the private key, and they somehow get lucky enough to generate the actual exact private key, then they no longer need to steal your cipher file or know your password.  They have the map (key) to access the bitcoins.

Okay I need a bit of help. To explain this but let's try.

I have a private key say 12345.   To an address say 1fool it is a vanity address made offline safely.   I input it to a btc wallet with a second password say 24680


A thief inputs random price keys to a wallet.  Brute force all the way.

One day private key comes up 12345  the one for address 1fool

At this point is the thief in.? I think not I think he needs to guess password 24680

Is this correct?

He needs the private key and the second password correct?

Take a 2-bit piece of information.
Use a function to reduce it to one bit.
Is the two-bit-information still in that single bit?
q.e.d.

What you're probably confused about is that for many (if not almost all) problems, it's actually not possible to prove wether or not the information is still there, somehow.
That has a lot to do with the concept of Kolmogorov complexity, i.e. the problem that it's generally unknowable wether some string can not be expressed by some shorter string (very simply put).

The idea that it is unproven wether or not there are irreversible functions is basically true and for cryptography boils down to the question of P=NP, but that has nothing to do with the possibility of simply reducing information in the output and thus rendering it impossible to recreate the input.
Most of today's applied cryptography and most specifically public-key cryptography requires P!=NP.

I took some time to read some texts related to the subject, and nothing I read said that "information is not there to be found".
Information is there, but highly scrambled.

Some interesting quotes from this answer (2nd answer on the topic), which is the best I found.



This problem is mainly related to https://en.wikipedia.org/wiki/Integer_factorization where it is very hard to factorize very big subprime numbers. Factorize is to decompose a number into a product of smaller integers.



This was a good example based on the above problem. But it is still reversible, we just don't know how to easily do it.


On the post I mentioned on stack exchange he explained how MD5 is hard to invert. It is interesting, and the main problem is related to bit depency, which is :

~

So, I looks to be possible. Just not humanly doable. From time to time even some hash functions are considered broken, just like SHA-1 which became vulnerable to shattred attack  (read it  here https://en.wikipedia.org/wiki/Cryptographic_hash_function)

So, personally, I would use your qwk's Planetary Super Efficienty Computer to try to break those hash functions instead of brute forcing them.

I'm not even sure if you simply don't understand or are trolling.
Again: a hash doesn't contain the information to reverse it.
This is not a matter of finding "patterns".
Information that isn't there can not be found.
Thermodynamics / information theory (entropy) is in the way.

I am not convinced, but I didn't read about it yet.
I am not convinced because we have unlimited samples, not just one.

If you have one more samples everything changes.
a+b=18
A-b=1
You can easily determine now. I know it is not that simple, however we have unlimited examples. That's the idea. Teach a machine to train on those examples searching for any kind of pattern.

But we are all just repeating ourselves already...

To break something like this would turn the world into chaos. Blocks could ne mined at will, bank accounts  easily accessed , financial system... probably someone is already looking for this im secrecy

if you want to understand why it is not possible to reverse a hash, i already gave a good example above. and you don't need a super computer or an AI to try and reverse it. basically the reason is the same. you can not reverse (a+b=18) to find a and b because there simply is no way! and lets not confuse guessing different values for a and b with reversing.

what hash algorithms do is the same, it is math. it is a bunch of additions, bit shifts, bit rotates,... in multiple steps that will return a final result. you can not reverse even a single step let alone the entire process.

The tbptjjsja have the information to create the string. However it is very hard to find that pattern, specially with a single example.

However you unlimited amounts of examples of SHA256 to learn from them seeking for that pattern.
Imagine to train a software to train on those examples seeking for that pattern, with huge processing power and an efficient code.
I believe this is something very interesting and doable.

Maybe  not to really break it , but to hugely  narrow the possibilities . Like I your example,  just look for ome single character swap

I never researched about it, just had this idea.


Maybe some people are researching in secret ..?

Uhm, no?
How do you go from "Tbptjblbnpp" to "Tbuptij Oblbnpup"?


Not at all.
"Reversing" in this context probably means taking some information, doing something with it and getting the "real" information out.
This is not possible if the information isn't there in the first place.

The string "Tbptjblbnpp" doesn't contain (all of) the information to create the string "Satoshi Nakamoto".
No matter if you use mathematics, mechanics, chemistry or anything other than magic, there's no way to get from one to the other.

I was not thinking about magic, but about math  just like your example.


This is 100% reversible.
I would like to understand more, and I don't this was a good example...is it not reversible with our current math or not at all? Our paradigms may change in the future

I will take a further look at this.

Supercomputers aren't going to be as powerful as people think when compared to the grand task of taking down an encryption method. However, they're going to be fairly good at niche specific tasks. I think the development behind supercomputers is a good thing, but they are never going to get to the capability of breaking SHA-256 unless something truly groundbreaking develops in physics. Most people's home computers aren't cooled efficiently, but a super computer would literally have to spend its time in a super super cold freezer which allows the computer components to still move. Also, its the small problem of it having to be bigger than Roger Ver's ego.


It depends what you mean by using AI to tackle this problem. AI isn't automatically anymore efficient than other alternatives. The definition of AI is something that can imitate human behaviour. Whereas a human probably wouldn't be able to reverse the SHA 256 hashes why would AI be anymore effective at this? I'm not saying its completely impossible, but it is very unlikely that AI would be capable of this. Most artificial intelligence is quite....how do I put it? Dumb. There's been some advancements in AI over recent years, and there are promising results from various sources. However, these are niche specific, and none of them are related to deconstructing SHA 256 or reversing a hash of SHA 256.

I can't imagine AI to reverse hash of Bitcoin's blockchain, i'd save my storage space


You can't use SHA-256 to encrypt something because it's hash function.

If a software claim using SHA-256 to encrypt information, it's very likely they use other encryption algorithm where it's private key (with length 256 bit) came from hashed password/passphrase.

With SHA-256, it is very easy to go from unencrypted message --> encrypted message that is encrypted with a given public key. It is also very easy to go from encrypted message --> unencrypted message if you have the private key associated with the public key ("Associated Private Key") the message is encrypted to. It is very difficult to (what the OP is referring to) go from encrypted message --> unencrypted message if you do not have the Associated Private Key.

Likewise, if you have a given private key, it is easy to calculate the public key, but it is difficult to calculate the private key with a given public key.

All of the above is given known formulas are used for performing each calculation. In the past, ciphers were broken, not because they were brute forced, but because formulas were discovered to make it trivial to calculate the private key with a given public key.

The risk to those using SHA-256 to encrypt their sensitive information is that a more efficient formula will be discovered that can calculate a private key with a given public key. Will this happen in the future? I don't know, that is above my pay grade.

Yes, it is.
AIs don't magically overcome the laws of mathematics
A (good) hash doesn't contain the information of its input/s.
With no information to go on, there's nothing to "reverse".


I sometimes try and explain hashes to people without mathematics.
My example usually goes like this:

Let's assume you run a night club with a guest list.
You don't want the doorman to know who the guests are before they arrive.
But he should be able to know if a person at the entrance is on the guest list.

Now, what you could do instead of writing the names of guests on the list, is write hashes of their names.
A very simple (not really good) hash could be:
1. shift one letter in the alphabet (ROT-1)
2. leave out all vowels

So, a name like "Satoshi Nakamoto" would turn into:
1. Tbuptij Oblbnpup
2. Tbptjblbnpp

It's obvious that this still contains a lot of information to go on, so it's really not a good hash function at all.
But the doorman at the night club might not know what a prominent guest we'll have tonight.
As soon as satoshi turns up, he'll be able to apply the same hash function to his name and see that he's on the list.

I believe that trying to brute force a hash 256 is the wrong approach. This won't work.

I was thinking about something more effective and efficient (energy speaking).

What if some tries to create an AI that would try to reverse SHA 256 hashes? That is not impossible. Although no one never succeeded , a highly advanced and dedicated AI could try.

I believe that with AI advances a lot of things will change.

Granted, "brute force" is kind of a misnomer here.
Actually, I shouldn't have posted at all in "Technical Discussion", because the whole idea is not about any technical aspect, but rather an idea of how to explain the odds of someone "hacking Bitcoin".
But I don't really know where else to post it.

A hash doesn't even contain information to reverse it, so for a hash of an arbitrary message, you're absolutely right, of course.
Otoh, for the purposes of "hacking Bitcoin", which is what people are concerned about, a hash of e.g. a key from a known search space of 2^256, "brute forcing" collisions in said search space is more or less equivalent to "reversing" the hash.
Yes, there will be (2^90? AFAIR) collisions, any of which could be the key, but all of them kind of "fit the shoe".

Yeah. That would indeed be quite a machine.

But realistically speaking. Sooner or later SHA256 will be "cracked".(or we will be able to find collisions as pooya87 defined cracking in this case) And it wont require earth sized supercomputer to do it.

If you study the history of cryptography, it is full of examples of ciphers that were "impossible" to break, whose cracking would take longer than the age of the universe etc. And they have all been cracked. And it did not take billions of years to break any of them 
Why would it be different this time?

Substitution cipher was impossible to crack
Enigma was impossible to crack
and many many others.

Yeah. if you have to brute force (almost) anything it takes forever, but there will always be a shortcut. We just don't know it yet.