$ echo -n "The SHA256 for this sentence begins with: one, eight, two, a, seven, c and nine." | sha256sum
182a7c930b0e5227ff8d24b5f4500ff2fa3ee1a57bd35e52d98c6e24c2749ae0 -
> Was just verifying your tweet's hash, and then...omg!!! I couldn't believe what I realised. The SHA256 of THIS tweet starts with exactly the same 7 characters as your tweet's hash. What are the chances of that?
$ echo -n $'Was just verifying your tweet\'s hash, and then...omg!!! I couldn\'t believe what I realised. The SHA256 of THIS tweet starts with exactly the same 7 characters as your tweet\'s hash. What are the chances of that?' | sha256sum
182a7c9c08b2f0f9333bf23828c5fbf47addf74e815b6a22ca10825450bc2ee1 -
I'm confused as to how they've done this. The original message, sure, you can brute force the digits and hope you get a collision, and try a new, plausible preamble if not. But I don't see how they've found this collision without it looking like anything is brute forced.
Is it using substitute Unicode characters or something?
7 digits of the hash makes for 16*7 possible hashes. I spot 4 potential "filler" lines in that tweet, so if you find log4(16*7)=14 candidates for each of those filler lines, then one combination would be expected to yield that hash.
You can generate sentences of the form "This sentence begins with: " followed by seven comma-separated english words denoting hex digits. Then search that space of digits, until you get a hit.
For each digit combination, you can try it with multiple variations of the sentence like "The SHA256 of this sentence begins with", "The SHA256 hash of this text starts with" and many more. That increases the search space without increasing the number of digits that have to match, making it more likely that a hit is found.
Throwing a loop of numbers on the end seems far more feasible. I put together a hasty Python implementation which can immediately find three hits at 5 characters. TQDM is reporting ~450k tries per second, so depending on how lucky you are, would probably want to redo in a faster language to solve for 7+
import hashlib
import itertools
import tqdm
BLOCKS_SIZE = 5
sentence_prefix = "The SHA256 for this sentence begins with:"
itos = {0x00:"zero", 0x01:"one", 0x02:"two", 0x03:"three", 0x04:"four", 0x05:"five", 0x06:"six", 0x07:"seven", 0x08:"eight", 0x09:"nine",
0x0a:"a", 0x0b:"b", 0x0c:"c", 0x0d:"d", 0x0e:"e", 0x0f:"f"}
for nums in tqdm.tqdm(itertools.product(itos.keys(), repeat=BLOCKS_SIZE)):
sentence = f"{sentence_prefix} {', '.join(itos[num] for num in nums[:-1])}, and {itos[nums[-1]]}."
hash_true = hashlib.sha256(bytes(sentence, "utf8")).hexdigest()
guessed_prefix = "".join(f"{n:x}" for n in nums)
true_prefix = hash_true[:BLOCKS_SIZE]
if guessed_prefix == true_prefix:
print("collision")
print(sentence)
print(hash_true)
Indeed, this is how I did it. 2^28 is around 270 million. With little more than a handful options, it should be possible. Although I have to say, it turned out to be more difficult than I'd initially thought. Maybe it's better to think of it as 28 different boolean choices.
echo -n "Indeed. This is how I managed to do it. 2^28 is around 300 million. With only a handful options, it's possible. Although, I must say that it turned out to be more difficult than I'd initially thought. Perhaps it's better to think of it as 28 different alternatives." | sha256sum
Basically I had several substitutions around words, case, punctuation, etc. and just ran it until it found some hits. Quite easy with just four characters though but was only a proof of concept.
All we are demonstrating here is why Sha256 is 256 bits and not 32 bits. We have trivially identified collisions for the first 28 bits of the output, which is only 11% of the entire hash size.
Difficulty of collisions roughly doubles for each additional bit. Imagine we had a SHA32, that would be 16 times harder to achieve a collision. SHA256 is 43 with 67 zeroes behind it more difficult than the examples here.
If we don't vary the sentence ("begins with, starts with, is prefixed with" etc...) and only consider the final part, then the number of english sentences is (unsurprisingly) equal to the number of possible hashes.
So for each distinct sentence, we pick randomly from the n different hashes, and we attempt to brute force this n times. So the probability of not getting this is:
(1-1/n)^n
As n increases, this will yield e^-1, so we have about a 36.7% chance of this not happening for any given length. So this has a probability of happening of 63.3%.
So there is a decent chance that there exists a sentence "The sha256 of this sentence is ..." for even the full sha256. If you are allowed to modify the sentence to be something like "'Begins with', 'starts with', 'OMG guys, check this out':" you can get this up to almost 1. Finding it would be mildly hard though barring some novel discovery about sha256.
It's not too difficult. All you need is to generate many variations of potential words and check whether the sha256 hash matches the wanted leading characters. For example, check this text.
$ echo -n $'It\'s not too difficult. All you need is to generate many variations of potential words and check whether the sha256 hash matches the wanted leading characters. For example, check this text.' | sha256sum
182a7c9d2e99162688aaaf3f97638edd7d06f8d295e456c7bb1f16abf3a8f70c -
So, if my logic is right (is it? That seems awfully cheap to me), this is about 2^22 times as easy as mining a bitcoin. Bitcoin is at about $25k, so there are people who can find hits like this one for way less than a cent.
By the pigeonhole principle, there is a sentence that writes out its entire SHA256 representation this way. Alternatively, the map from these kinds of sentences with 256 terms to 2^256 given by SHA256 admits a fixed point.
I don't believe this is necessarily true. Unless I'm misunderstand you, each of the possible variants of spelling out 32 hexadecimal characters could theoretically SHA-256 into the spelled-out hash + 1 (looping around at ff…ff).
I don't see how pigeonhole principle applies to that situation. It could well be that "zero" hashes to 1, "one" hashes to 2... and "f" hashes to 0, extended out to the hash's length.
The pigeonhole principle does not say that. It can be used to show that there are two different sentences with the same hash as each other (among any collection of 2^256 + 1 sentences), but it tells you nothing about hashes that agree with the content of the sentence. The probability that a random hash function on a collection of 2^256 sentences has a fixed point is about 1 - 1/e, and it approaches 1 as you add more variations to grow the collection infinitely. But SHA-256 isn’t actually random, so the only way to know this for sure would be to find an example.
Bitcoin difficulty is not measured in bits but its own unit (some hashrate was defined as difficulty 1, and difficulty 10 means the hash rate is 10x that). The number you see on that website is also in trillions, so the current difficulty is about 50 trillion. Also, you get more than one Bitcoin per hash (currently 6.25, halving every few years).
To mine six BTC, you currently need almost 80 bits of zeroes, so 28 bits is basically trivial.
SHA256 is a one-way hashing function. Which means that feeding that sentence into SHA-256 and it starting with the characters in that sentence is very unlikely chance.
They probably wrote a script that tacked on a bunch of random letters and numbers to a sentence, then hashed it via brute force until it returned a hash that started with the exact same thing that the sentence said.
This is similar to how Bitcoin's proof of work algorithm.
It's self-referential and that makes it non-obvious how it's accomplished. Changing the sentence changes the hash, which also changes the sentence. So in any case it's an interesting construction.
No. The pigeonhole principle and the birthday attack both apply to situations where you’re looking for two inputs with the same hash as each other, not where you’re looking for one input that describes its own hash.
$ echo -n 'The SHA256 for this sentence begins with seven, seven, f, zero, a, b, b and five.' | sha256sum
77f0abb54cd09ad7b654bd5e762d7be58e7daffd1a0da6a56f5135bd667856a3 -
I saw this on HN years ago from the original that linked here.
2-3 days ago posted on 4chan's /g/ board that I remembered this sentence but didn't remember its source and the hash it contained.
Someone on /g/ found the post on HN and a large thread ensued that expired and auto-deleted 12 hours ago or so. And then this person posted it on Twitter and it got shared here.
Reposts do add value though. Think of it this way: there’s a pool of content you haven’t seen before and a subset of it which you’d enjoy seeing. If no one reposts anything ever, you won’t be able to see any of it.
In fact, some of the things you have seen before you would probably not mind seeing again. Maybe you didn’t think to save it at the time or maybe your circumstances have changed.
Anyways, I wouldn’t confuse low effort with low value.
Wrote up something in python that achieves similar, but for increasing numbers of characters. Found a few hits fairly quickly. pypy3 is pushing 420k evaluations a second on my laptop.
e.g.
"The SHA256 for this sentence begins with: five, two, and d"
"The SHA256 for this sentence begins with: seven, e, and nine"
"The SHA256 for this sentence begins with: one, five, e, and three"
My brain fart this morning was forgetting to account for the newline, so I started out spitting out bad options.
You can wrap tqdm around the "permutations(TOKENS, k)" if you want to measure progress. I haven't spent time trying to make this particularly optimised, for example that dict lookup is likely avoidable with a little bit of work via index lookup, and maybe cheaper. I've also not attempted to parallelise it, which would be fairly easy to do.
#!/usr/bin/env python
import string
import hashlib
from itertools import permutations
WORD_DIGIT = {
"one":1,
"two":2,
"three":3,
"four":4,
"five":5,
"six":6,
"seven":7,
"eight":8,
"nine":9}
TOKENS = [
"one",
"two",
"three",
"four",
"five",
"six",
"seven",
"eight",
"nine",
] + list(string.ascii_lowercase)
SEPARATOR = ", "
STARTING_TEXT = "The SHA256 for this sentence begins with: "
for k in range(2, 6):
for perm in permutations(TOKENS, k):
sha_start = ""
for char in perm:
if char in WORD_DIGIT:
sha_start += str(WORD_DIGIT[char])
else:
sha_start += char
test_string = STARTING_TEXT + SEPARATOR.join(perm[:-1]) + ", and " + ''.join(perm[-1:]) + "\n"
checksum = hashlib.new("sha256")
checksum.update(test_string.encode())
if checksum.hexdigest().startswith(sha_start):
print(test_string)
This is an interesting starting point for a python implementation, but it doesn't work correctly as far as I can tell. The list of tokens leaves out zero and includes a bunch of ascii characters that aren't valid hex. That second problem won't produce wrong results, but it'll spend a lot of time testing combinations that can't possibly appear in a SHA256 hex output. I also think the original tweet calculated without a newline.
More significantly, permutation in python is probably not the right tool for this. I believe it will not repeat token values at different positions, so for example you'll never end up testing "The SHA256 for this sentence begins with: f, f, and f", which is certainly a potentially valid result.
This means there's quite a lot of solutions. Running the entire 2^56 would take over 770 core-days if one core can achieve an impossible 1 giga-iterations per second.
another pretty easy optimization is swapping to https://github.com/minio/sha256-simd, particularly if you're on a process with the sha extensions.
versus just spawning a goroutine per attempt, it'll likely be much faster as well to just split the search space into number of cores and have one chugging away on each chunk of the search space. (I have a thing to do vanity git commit hashes and that's what I do for that; for 7 characters in the hash, it takes well under a second on my CPU on average)
While we're there, since the message has a fixed prefix, you can initiate the sha256 computation with it, and then repeatedly branch off of that for the test suffix.
Oh I didn’t mean per attempt. If you have <= 16 cores, just wrap the first level loop body in a goroutine; if you have >16 cores, wrap the second level to spawn 256 goroutines. Very little code change, big speedup.
There are N possible sequences, and you try N times with a success probability of 1/N each (because it is a good hash function). This means the expected number of hits is 1.
> Was just verifying your tweet's hash, and then...omg!!! I couldn't believe what I realised. The SHA256 of THIS tweet starts with exactly the same 7 characters as your tweet's hash. What are the chances of that?
I like little puzzles so I gave it a shot in Ruby.
#!/usr/bin/ruby
require 'digest'
charmap = %w{zero one two three four five six seven eight nine a b c d e f}
(0..0xf).map do |prefix|
Process.fork do
(0..0xffffff).each do |i|
hex = "%01x%06x" % [prefix, i] # "0123456"
digit_words = hex.chars.map { |c| charmap[c.to_i(16)] } # ["zero", "one", ...]
sentence = "The SHA256 for this sentence begins with: %s, %s, %s, %s, %s, %s and %s." % digit_words
sha = Digest::SHA256.hexdigest(sentence)
if sha[0,7] == hex
puts(sentence)
end
end
end
end
Process.waitall
8 minutes on an old quad-core. I don't expect there's much to optimize since all the heavy lifting is in the libraries. I didn't bother with synchronization so you might get a scrambled result if it somehow finds a flurry of hits. :)
It's way above my head mathematically as to if this is even possible, but it is hilarious how screwed so many things would be if sha256 was discovered to have a means to more quickly reverse at least a partial hash. Just off the top of my head:
- SSL
- Bitcoin (bonus: unlimited money hack if you can keep the discovery under wraps)
- Signed updates for devices
Goodness only knows what I am missing, but that first one along is enough to cause an unmitigated disaster.
I assume these tweets are effectively brute forced given the fairly short prefix though and we're all safe
Is brute forcing a hash not "more quickly reversing at least a partial hash"?
What do you have in mind for "more quickly", then?
Also even if you figured out a way to make sha256 a few orders of magnitude faster, that would not affect SSL or signing and bitcoin would adjust as soon as several people know the secret.
Heh at first i thought 'wait how did they get all 512bits in a collision!?'
Then i realized the program just calculates it's own hash and prints it. Simple as that. It'd be super interesting if the program had the hash as a string internally and printed that out but that's (within the realm of breaking cryptography) impossible to pull off.
Generating sequential Git short commits! It's so pleasant looking I'm tempted to try using it one of my projects, but deep down I know it's not worth the hassle.
Would you believe in God if sha256 of "I am God. My name is BOB " would be 4920616D20476F642E204D79206E616D6520697320424F4220202020202020 (the text in hex)?
That would be finding a invariant point (fixed point) in sha256 what would also be a text message. There is no reason to expect that kind of thing existing in any algorithm.
I did something similar once (with a bit of a twist) for my bio when I was a TA in college:
"Hi! I’m a senior studying CS. My hobbies include making semantic paradoxes and my bio includes eight a’s, seventeen e’s, fourteen i’s, eight o’s, six u’s, and one wrong number"
This is cool. Isn't finding these the same as minting a new block of bitcoin? So definitially hard using our best understanding of algorithms, math, etc.
bitcoin is relatively easy. you are just hashing/permuting the block header until you get the lowest hash of all miners. it isn't hard, just expensive.
Something that I'm not seeing mentioned in these comments (I may just have missed it) is that you can precompute the hash of the static part of the string and then extend it with the numbers in a loop, saving some cycles. This is because the full hex representation of a SHA hash gives you the entire internal state of the algorithm. This can lead to security vulnerabilities:
After picking some scheme to generate messages that predict n bits of their hash in some form, the chance of finding at least one message that correctly predicts its hash is 1 - (1 - 1/x)^x where x is 2^n. This approaches 1 - 1/e = 63.2 % for large n. So by trying a few different schemes, for example slightly varying the prefix »The SHA256 for this sentence begins with:«, it becomes quickly very likely to succeed. In the limit of large n, for example only 5 different schemes will yield at least one correct message with 99 %.
With 5 patterns, 24 bits and SHA-1.
The SHA-1 hash of this text starts with 051E35.
The hash of this text starts with A943BD.
The SHA-1 hash of this text starts with B6640C.
The SHA-1 hash of this message starts with C3B03D.
The SHA-1 hash of this message starts with D93717.
Or the same as before but as patterns just padding the 6 hex digits with zero zero to eight dots.
150 comments
[ 3.4 ms ] story [ 249 ms ] threadAs always, the real WTF is in the comments.
Source: https://twitter.com/benoconnor/status/1701057433131421935
Is it using substitute Unicode characters or something?
E: no, just hand typed it and got the same...
For each digit combination, you can try it with multiple variations of the sentence like "The SHA256 of this sentence begins with", "The SHA256 hash of this text starts with" and many more. That increases the search space without increasing the number of digits that have to match, making it more likely that a hit is found.
For instance, it could start with "Was", "I was", "verifying" could be "checking" or "computing" or "testing", etc.
A bit tight, but it seems feasible with some work.
Basically I had several substitutions around words, case, punctuation, etc. and just ran it until it found some hits. Quite easy with just four characters though but was only a proof of concept.
Difficulty of collisions roughly doubles for each additional bit. Imagine we had a SHA32, that would be 16 times harder to achieve a collision. SHA256 is 43 with 67 zeroes behind it more difficult than the examples here.
So for each distinct sentence, we pick randomly from the n different hashes, and we attempt to brute force this n times. So the probability of not getting this is:
(1-1/n)^n
As n increases, this will yield e^-1, so we have about a 36.7% chance of this not happening for any given length. So this has a probability of happening of 63.3%.
So there is a decent chance that there exists a sentence "The sha256 of this sentence is ..." for even the full sha256. If you are allowed to modify the sentence to be something like "'Begins with', 'starts with', 'OMG guys, check this out':" you can get this up to almost 1. Finding it would be mildly hard though barring some novel discovery about sha256.
More seriously, is there a really good, open source library that generates many slight variations of an input block of text?
https://news.ycombinator.com/item?id=19003644 (2019)
E: Ok, someone else in the tweet replies says it isn't that hard. I'm going to stop reading and start thinking more about how.
Bitcoin difficulty is at around 50 bits (https://ycharts.com/indicators/bitcoin_average_difficulty#:~....)
It also uses SHA256.
So, if my logic is right (is it? That seems awfully cheap to me), this is about 2^22 times as easy as mining a bitcoin. Bitcoin is at about $25k, so there are people who can find hits like this one for way less than a cent.
The minimum bitcoin difficulty of 1 corresponds to 2^32 double SHA256, so finding a block at difficulty 2^50 takes an insane 2^83 hashes...
To mine six BTC, you currently need almost 80 bits of zeroes, so 28 bits is basically trivial.
They probably wrote a script that tacked on a bunch of random letters and numbers to a sentence, then hashed it via brute force until it returned a hash that started with the exact same thing that the sentence said.
This is similar to how Bitcoin's proof of work algorithm.
$ echo -n 'The SHA256 for this sentence begins with seven, seven, f, zero, a, b, b and five.' | sha256sum 77f0abb54cd09ad7b654bd5e762d7be58e7daffd1a0da6a56f5135bd667856a3 -
I saw this on HN years ago from the original that linked here. 2-3 days ago posted on 4chan's /g/ board that I remembered this sentence but didn't remember its source and the hash it contained.
Someone on /g/ found the post on HN and a large thread ensued that expired and auto-deleted 12 hours ago or so. And then this person posted it on Twitter and it got shared here.
Actually fascinating.
In fact, some of the things you have seen before you would probably not mind seeing again. Maybe you didn’t think to save it at the time or maybe your circumstances have changed.
Anyways, I wouldn’t confuse low effort with low value.
https://desuarchive.org/g/thread/95910112
(Easiest optimization is wrapping the loop body in a goroutine. GOEXPERIMENT=loopvar really makes this nicer btw.)
The reply is obviously more interesting, need to come up with a lot of variations.
e.g.
"The SHA256 for this sentence begins with: five, two, and d"
"The SHA256 for this sentence begins with: seven, e, and nine"
"The SHA256 for this sentence begins with: one, five, e, and three"
My brain fart this morning was forgetting to account for the newline, so I started out spitting out bad options.
More significantly, permutation in python is probably not the right tool for this. I believe it will not repeat token values at different positions, so for example you'll never end up testing "The SHA256 for this sentence begins with: f, f, and f", which is certainly a potentially valid result.
I rewrote it in rust last night and realised that, yeah. Lots of wasted time on irrelevant characters.
>permutation in python is probably not the right tool for this.
Correct, missed that. I need `itertools.product(<iterable>, repeat=2)`
"SHA256" vs "SHA-256"
"begins" vs "starts"
":" vs ""
"%s," vs "%s"
"%s and" vs "%s, and"
"." vs ".\n"
I'd settle on a fixed prefix instead and try longer sequences to make it look more impressive.
The SHA256 for this sentence begins with: 1c0510f.
The SHA256 for this sentence begins with: 4, 5, b, a, a, 5 and f.
versus just spawning a goroutine per attempt, it'll likely be much faster as well to just split the search space into number of cores and have one chugging away on each chunk of the search space. (I have a thing to do vanity git commit hashes and that's what I do for that; for 7 characters in the hash, it takes well under a second on my CPU on average)
There are N possible sequences, and you try N times with a success probability of 1/N each (because it is a good hash function). This means the expected number of hits is 1.
Here is a slightly different version I wrote that only has 1 allocation per loop.
If you or anyone else can figure out how to get rid of the allocation in encoding/binary let me know!
I assume these tweets are effectively brute forced given the fairly short prefix though and we're all safe
What do you have in mind for "more quickly", then?
Also even if you figured out a way to make sha256 a few orders of magnitude faster, that would not affect SSL or signing and bitcoin would adjust as soon as several people know the secret.
https://www.ioccc.org/years.html#2019_diels-grabsch2
Then i realized the program just calculates it's own hash and prints it. Simple as that. It'd be super interesting if the program had the hash as a string internally and printed that out but that's (within the realm of breaking cryptography) impossible to pull off.
https://news.ycombinator.com/item?id=33704297
Generating sequential Git short commits! It's so pleasant looking I'm tempted to try using it one of my projects, but deep down I know it's not worth the hassle.
That would be finding a invariant point (fixed point) in sha256 what would also be a text message. There is no reason to expect that kind of thing existing in any algorithm.
"Hi! I’m a senior studying CS. My hobbies include making semantic paradoxes and my bio includes eight a’s, seventeen e’s, fourteen i’s, eight o’s, six u’s, and one wrong number"
https://www.mycryptopedia.com/bitcoin-algorithm-explained/
https://en.m.wikipedia.org/wiki/Length_extension_attack
With 5 patterns, 24 bits and SHA-1.
Or the same as before but as patterns just padding the 6 hex digits with zero zero to eight dots.https://crypto.stackexchange.com/questions/48580/fixed-point...