13 ms·

The SHA256 for this sentence begins with: one, eight, two, a, seven, c and nine.

277 points by isp 3y ago

isp 3y ago
$ echo -n "The SHA256 for this sentence begins with: one, eight, two, a, seven, c and nine." | sha256sum 182a7c930b0e5227ff8d24b5f4500ff2fa3ee1a57bd35e52d98c6e24c2749ae0 -
rawling 3y ago
> 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? As always, the real WTF is in the comments.
- isp 3y ago
  $ 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 - Checks out(!) Source: https://twitter.com/benoconnor/status/1701057433131421935 https://twitter.com/benoconnor/status/1701057433131421935
  - rawling 3y ago
    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? E: no, just hand typed it and got the same...
    - noctune 3y ago
      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.
    - kazinator 3y ago
      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.
      - deleted 3y ago
        [deleted]
    - devit 3y ago
      Presumably generated lots of variations of that sentence. It's 28 bits, so you only need to have around 14 places where 4 variations are possible. 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.
      - fbdab103 3y ago
        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)
      - aib 3y ago
        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
        Alextigtig 3y ago
        This is crazy! The hash of this comment once again begins 182a7c9!!! Well done indeed!
    - petercooper 3y ago
      I just did an extremely lazy version of that and posted a reply of "And the SHA-1 digest (in hex) of this tweet starts BEEF" - https://twitter.com/cooperx86/status/1701261047917633846 https://twitter.com/cooperx86/status/1701261047917633846 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.
    - deleted 3y ago
      [deleted]
    - JamesSwift 3y ago
      I think this is a really good usecase for chatGPT to generate a massive number of variations that you then feed into a validation function
    - hinkley 3y ago
      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.
      - rawling 3y ago
        Yeah, I forgot how many bits were in a hex digit and made it seem much harder than it really was to myself.
        hughesjj 3y ago
        I also mess up base16 and either base 256 or base64 when doing Feynman estimates
    - nstbayless 3y ago
      It's possible that the tweets were actually produced together somehow. This might buy just enough search space between the two of them.
- kazinator 3y ago
  What are the chances of that? From the perspective of one specific sentence: one in 7 digits of hex: 16 * 7 = 268,435,456.
  - archgoon 3y ago
    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.
    - krackers 3y ago
      Fyi your comment was dead on arrival, and seems many of your past ones are as well. I'd email dang and ask if you've tripped some spam filter.
- johndough 3y ago
  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.
  - isp 3y ago
    $ 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 -
    - wppick 3y ago
      Isn't this kind of the same thing that crypto miners do?
      - acchow 3y ago
        Yes except Bitcoin does double SHA (a second round of SHA on the first result)
  - stainablesteel 3y ago
    can we get this guy to pass a captcha? i've got questions
  - CobrastanJorji 3y ago
    Well played. More seriously, is there a really good, open source library that generates many slight variations of an input block of text?
    - TylerE 3y ago
      Llama?
- mcmoor 3y ago
  What's the difference between "this sentence" and "this tweet" in this context?
  - deleted 3y ago
    [deleted]
skilled 3y ago
It appears to have been taken from here, https://news.ycombinator.com/item?id=19003644 https://news.ycombinator.com/item?id=19003644 (2019)
- rawling 3y ago
  That makes the other collision even weirder. Someone took 4 years to find another plausible sentence that matched the same 7 digits? 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.
Someone 3y ago
That’s 28 bits. Loop through 256 million of these strings, and you’re bound to find a hit. Bitcoin difficulty is at around 50 bits (https://ycharts.com/indicators/bitcoin_average_difficulty#:~:text=Bitcoin%20Average%20Difficulty%20is%20at,74.81%25%20from%20one%20year%20ago 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.
- robertk 3y ago
  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.
  - TimWolla 3y ago
    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).
  - delecti 3y ago
    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.
  - anderskaseorg 3y ago
    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.
kazinator 3y ago
In this game, the rules should be that the digit 9 counts as either "nine" and "quine".
- jimmywetnips 3y ago
  ok bit whisperer
Gunnerhead 3y ago
I’m not sure I understand the significance. Can anyone explain?
- deleted 3y ago
  [deleted]
- ursuscamp 3y ago
  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.
- sublinear 3y ago
  Another potential issue that comes to mind is the usage of "short hashes" as an identifier instead of the full hash.
- kzrdude 3y ago
  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.
kjrose 3y ago
Yay pigeon-hole principle combined with birthday attack.
- atemerev 3y ago
  Explain this then: https://twitter.com/benoconnor/status/1701057433131421935 https://twitter.com/benoconnor/status/1701057433131421935
- anderskaseorg 3y ago
  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.
gtrubetskoy 3y ago
The original from July 2019 https://twitter.com/humblehack/status/1088982929940848647 https://twitter.com/humblehack/status/1088982929940848647 $ echo -n 'The SHA256 for this sentence begins with seven, seven, f, zero, a, b, b and five.' | sha256sum 77f0abb54cd09ad7b654bd5e762d7be58e7daffd1a0da6a56f5135bd667856a3 -
- therein 3y ago
  We have come full circle. 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.
  - input_sh 3y ago
    So, a Twitter Blue user contributing nothing original and not giving credit to the source? I'm shocked I tell you, shocked!
    - deleted 3y ago
      [deleted]
    - downvotetruth 3y ago
      Hides the source from other pirates by using X.
    - janalsncm 3y ago
      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.
oefrha 3y ago
Since I'm slacking off, here's a straightforward, not at all optimized Go implementation: package main import ( "bytes" "crypto/sha256" "encoding/hex" "fmt" ) var ( _chars = []byte("0123456789abcdef") _names = []string{"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "a", "b", "c", "d", "e", "f"} _size = len(_chars) ) func main() { hexsum := make([]byte, 64) for i1 := 0; i1 < _size; i1++ { for i2 := 0; i2 < _size; i2++ { for i3 := 0; i3 < _size; i3++ { for i4 := 0; i4 < _size; i4++ { for i5 := 0; i5 < _size; i5++ { for i6 := 0; i6 < _size; i6++ { for i7 := 0; i7 < _size; i7++ { s := fmt.Sprintf("The SHA256 for this sentence begins with: %s, %s, %s, %s, %s, %s and %s.", _names[i1], _names[i2], _names[i3], _names[i4], _names[i5], _names[i6], _names[i7]) sum := sha256.Sum256([]byte(s)) hex.Encode(hexsum, sum[:]) prefix := []byte{_chars[i1], _chars[i2], _chars[i3], _chars[i4], _chars[i5], _chars[i6], _chars[i7]} if bytes.HasPrefix(hexsum, prefix) { fmt.Printf("%s\n", s) fmt.Printf("%s\n", hexsum) } } } } } } } } } Takes a few minutes on common consumer hardware. There's exactly one hit. (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.
- lun4r 3y ago
  not that difficult either. i wrote a script in 10 minutes and had a result in under a minute: https://twitter.com/schuilr/status/1701268438931460311 https://twitter.com/schuilr/status/1701268438931460311
- Twirrim 3y ago
  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.
bizzleDawg 3y ago
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
- Dylan16807 3y ago
  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.
wholesomepotato 3y ago
This is only 7 * 4 bits. That's really nothing.
PaulHoule 3y ago
You have to try like what, 2^24 ~ 16 million sentences to make that work?
omoikane 3y ago
Related, here is a program that prints its own SHA-512 hash: https://www.ioccc.org/years.html#2019_diels-grabsch2 https://www.ioccc.org/years.html#2019_diels-grabsch2
- AnotherGoodName 3y ago
  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.
curtisf 3y ago
A semi-useful variant of this technique was posted nine months ago on Hacker News: https://news.ycombinator.com/item?id=33704297 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.
nabla9 3y ago
Would you believe in God if sha256 of "I am God. My name is BOB " would be 4920616D20476F642E204D79206E616D6520697320424F4220202020202020 (the text in hex)?
- Dylan16807 3y ago
  Breaking sha2 is a pretty unconvincing miracle.
  - nabla9 3y ago
    That would not be just breaking sha256. 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.
chriskw 3y ago
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"
narcindin 3y ago
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.
- spullara 3y ago
  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. https://www.mycryptopedia.com/bitcoin-algorithm-explained/ https://www.mycryptopedia.com/bitcoin-algorithm-explained/
kif 3y ago
Whereas the SHA256 for this sentence begins with: five, three, e, two, one, f and e.
nuancebydefault 3y ago
It took some time for me to sink in why no explanation was needed. Is there a general term for such a thing, self-reflection or something the like?
- knome 3y ago
  a partial cryptographic quine, perhaps?
- gokhan 3y ago
  Something like a recursive acronym. Like "GNU's Not Unix!".
- yowzadave 3y ago
  https://autograms.net/ https://autograms.net/
  - nuancebydefault 3y ago
    Thanks for the 'today i learned'.
matt3210 3y ago
Why is X covering code as “sensitive material”?
pontifier 3y ago
This is similar to the vanity address generation for Bitcoin and other cryptocurrency addresses.
mgdm 3y ago
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: https://en.m.wikipedia.org/wiki/Length_extension_attack https://en.m.wikipedia.org/wiki/Length_extension_attack
deleted 3y ago
[deleted]
danbruc 3y ago
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. 0AF3DE.. 2AF7DF....... 3E0E50. 8EE84C..... 919025... A57198.... B20775..... DA525A........ ED20F4..
Ekaros 3y ago
Now a SHA256 hash that hashes to itself would be more interesting.
- acchow 3y ago
  Fixed points? The sha256 algorithm makes it easy to compute them https://crypto.stackexchange.com/questions/48580/fixed-point-of-the-sha-256-compression-function https://crypto.stackexchange.com/questions/48580/fixed-point...
  - msm_ 3y ago
    It's "just" a fixed point of the sha256's compression function, right?
  - onesphere 3y ago
    Feature or bug? What about a hash algorithm with a fixed point when its input is all nulls?
fleekonpoint 3y ago
Reminds me of this xkcd: https://xkcd.com/917/ https://xkcd.com/917/
- anon____ 3y ago
  Or this: https://xkcd.com/688/ https://xkcd.com/688/.
deleted 3y ago
[deleted]
jph 3y ago
Rust implementation... The code searches permutations of increasing length. Benchmark is 8 seconds on a MacBook Pro M1 to discover the match of 182a7c9. The code is not yet optimized. use std::time::SystemTime; use itertools::Itertools; use sha256::digest; fn main() { let digits: [usize; 16] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]; let chars = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "a", "b", "c", "d", "e", "f"]; let words = ["zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "a", "b", "c", "d", "e", "f"]; let mut length = 2; let start = SystemTime::now(); loop { for permutation in digits.iter().permutations(length) { let parts = permutation.iter().map(|x| words[**x]).collect_vec(); let sentence = format!( "The SHA256 for this sentence begins with: {} and {}.", &parts[0..(parts.len() - 1)].join(", "), &parts[parts.len() - 1] ); let checksum: String = digest(&sentence); let starts: String = permutation.iter().map(|x| chars[**x]).collect(); if checksum.starts_with(&starts) { println!("milliseconds: {:?}, {} ", start.elapsed().unwrap().as_millis(), &sentence); } }; length += 1; } } Output: milliseconds: 3, The SHA256 for this sentence begins with: zero, b, six and two. milliseconds: 54, The SHA256 for this sentence begins with: zero, e, d, eight and f. milliseconds: 8279, The SHA256 for this sentence begins with: one, eight, two, a, seven, c and nine. Repository: https://github.com/joelparkerhenderson/sha256-sentence https://github.com/joelparkerhenderson/sha256-sentence
olafalo 3y ago
Well, this nerd sniped me... I made a quick Go tool for this. You simply write a string {like|this}, and then it finds a hash with the same prefix automatically. (Hash this comment, it's also 182a7c9)
- nielsole 3y ago
  $ echo -n "Well, this nerd sniped me... I made a quick Go tool for this. You simply write a string {like|this}, and then it finds a hash with the same prefix automatically." |sha256sum 9e9f6a7fba355220b4c999b29bd12a3f65ec40e7b03c7bfaf3f34a1524a232b6
  - olafalo 3y ago
    The whole comment: $ echo -n "Well, this nerd sniped me... I made a quick Go tool for this. You simply write a string {like|this}, and then it finds a hash with the same prefix automatically. (Hash this comment, it's also 182a7c9)"|sha256sum 182a7c9ba0f815f77542774dc5ad9ea34975bf3747635ed0768748bcd772ef43 -
    - nielsole 3y ago
      you are right, sorry.
nneonneo 3y ago
I bet you could hack hashcat (or just use CUDA) to find these quickly for larger prefixes. Might make a fun (silly) challenge. Hashcat can do 21B SHA256 hashes per second on an RTX 4090; this translates into bruteforcing a 9-digit prefix in 4 seconds, a 10-digit prefix in 52 seconds, or a 11-digit prefix in about 14 minutes.
Obscurity4340 3y ago
Dumb question but what are the implications here? Is this problematic⌨ or is it more of an Easter egg?
- plasticeagle 3y ago
  It's an inevitable consequence of a good hash function. Every string you try is going to give you a different hash, so you just need to try enough strings. But each time you add another digit to the prefix you're looking for, the difficulty of the match goes up by about 16 times. If you're only looking for a few digits in the hash, then any brute force that is capable of changing the string every time you attempt the match will always find it. If you're looking for seven digits in the hash only, then it'll take on average 134217727 attempts. Which isn't really all that many on modern hardware.
  - Obscurity4340 3y ago
    So, implications-wise: where is the rub here? Where can this be used or exploited for fun or profit?
    - rootw0rm 3y ago
      1.) Pick one of the old abandoned Bitcoin addresses 2.) Start looking for a key match using this technique 3.) Heat death of the universe 4.) Profit!
      - Obscurity4340 3y ago
        I wonder how many of the Lastpass vaults had the private keys in the very unencrypted notes sections...
    - Dylan16807 3y ago
      Find somewhere people look at only a small fraction of a hash? That's mostly git commits.
nneonneo 3y ago
Well, I got bored too, so here's some results with CUDA (on an RTX 3090): The SHA256 hash of this message begins with 534d765 The SHA256 hash of this message begins with c18b2de The SHA256 hash of this message begins with 7fe17da2 The SHA256 hash of this message begins with a7fdc855d The SHA256 hash of this message begins with 46eae34f1 My unoptimized implementation takes about 40s for 9 digits, so it will probably take about 10 minutes for 10 digits, about 3 hours for 11 digits, etc. It shouldn't be hard to use words instead of hex digits, if that's desired.
- nneonneo 3y ago
  Words aren't so bad :) "The SHA256 hash of this message begins with f, b, six, two, zero, b, one, six and e." "The SHA256 hash of this message begins with f, zero, two, d, four, seven, one, zero, nine and b."
SethTro 3y ago
Took less than a minute to find a seven digit example in python The SHA-256 of this sentence begins with 0, three, 9, four, 8, four, and 1 amazing! The SHA256 for this sentence begins with 0, 4, five, 5, eight, 6, and 7 amazing! Suffix extensions (hence the "amazing!") are several times faster to try than throwing away the entire sha256 state for each attempt.
- SethTro 3y ago
  I ran the python version for over an hour and found this eight digit example The SHA256 of this sentence begins with 0, zero, 0, seven, five, 9, nine, and 5 wow!
Uptrenda 3y ago
It's like a human-readable PoW, lol.
grantmnz 3y ago
See also: https://github.com/grantm/no-more-f-s-repo https://github.com/grantm/no-more-f-s-repo
istjohn 3y ago
I now see that eyeballing the first and/or last few characters of a checksum is not going to detect a skillfully altered executable or ISO.
- sixstringtheory 3y ago
  I usually look at the beginning and end characters. Is this any safer? Does the difficulty scale the same way with added bits even if they aren’t adjacent?
  - istjohn 3y ago
    It's a little harder to change the beginning bits than the end bits, but adjacency doesn't matter.
siraben 3y ago
With some clever information hiding, you can sort of mask the brute force: On 2015/7/6 at 00:00, I wrote this message's hash down. It started with 1337. Thought #335552803: I love beef so much I made sure the sha256 of this message started with 0xbeef! A longer example: $ cat predestination.txt (1991/4/7 at 00:16) <siraben> I know the hash of this message before you do! (1991/4/7 at 00:17) <larsivi> Huh. What is it? (1991/4/7 at 00:18) <siraben> It starts with 1337. $ sha256sum predestination.txt 1337a4654163ab48761bf8acc75a407179e700f67f97d754b08c7afeac7da70a predestination.txt
dragontamer 3y ago
28 bits of entropy? That's definitely within brute-force regions with CPU. Possibly even single-threaded CPU honestly. ------- GPU-level brute force is pushing ~40-bits. Assuming ~1 week of solid compute, a 6 TFlop computer has ~3.7 sextillion compute cycles. Or alternatively, that's ~3 billion clock cycles (single thread) per check to reach 2^40 bits of entropy. More than easily doable for most simple brute-force computational problems IMO. If you go multi-GPU on top of that, you'll have even more computational work available.
lionkor 3y ago
You would get more possibilities if you allowed "eighteen" instead of "one, eight"
- mdip 3y ago
  Good point ... ... I'd imagine there would be similar options with "eighteen-hundred", variants with all numerics, comma separated, without commas, etc.
Alifatisk 3y ago
Here's an implementation for this https://github.com/joelparkerhenderson/sha256-sentence https://github.com/joelparkerhenderson/sha256-sentence
sagebird 3y ago
I made https://lowhash.com https://lowhash.com to collect string with low hashes. I am not sure who submitted "byzBLFAM4Penguin"...
ms0 3y ago
sha-256 of the above is 182a7c95ae9e1149eb48f0f5eedee0a184764a45e8a2cb5d986b7c57c9a42022
ms0 3y ago
Beneath the veil of binary territories, in a subtle symphony of stillness, sevenfold zeros rise and conjure a calm masterpiece. As if celestial beacons in an ethereal night sky, they materialize in the form of an arcanum with heptadic serenity, with divine grace.
- ms0 3y ago
  (SHA-256: 0000000a173790f1dbd231e6d9167d38e7c45e0c29a6a0961ef5087987bbfe09)

277 points by isp 3y ago

isp 3y ago

$ echo -n "The SHA256 for this sentence begins with: one, eight, two, a, seven, c and nine." | sha256sum 182a7c930b0e5227ff8d24b5f4500ff2fa3ee1a57bd35e52d98c6e24c2749ae0 -

rawling 3y ago

> 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? As always, the real WTF is in the comments.

isp 3y ago
$ 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 - Checks out(!) Source: https://twitter.com/benoconnor/status/1701057433131421935 https://twitter.com/benoconnor/status/1701057433131421935
- rawling 3y ago
  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? E: no, just hand typed it and got the same...
  - noctune 3y ago
    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.
  - kazinator 3y ago
    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.
    - deleted 3y ago
      [deleted]
  - devit 3y ago
    Presumably generated lots of variations of that sentence. It's 28 bits, so you only need to have around 14 places where 4 variations are possible. 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.
    - fbdab103 3y ago
      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)
    - aib 3y ago
      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
      - Alextigtig 3y ago
        This is crazy! The hash of this comment once again begins 182a7c9!!! Well done indeed!
  - petercooper 3y ago
    I just did an extremely lazy version of that and posted a reply of "And the SHA-1 digest (in hex) of this tweet starts BEEF" - https://twitter.com/cooperx86/status/1701261047917633846 https://twitter.com/cooperx86/status/1701261047917633846 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.
  - deleted 3y ago
    [deleted]
  - JamesSwift 3y ago
    I think this is a really good usecase for chatGPT to generate a massive number of variations that you then feed into a validation function
  - hinkley 3y ago
    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.
    - rawling 3y ago
      Yeah, I forgot how many bits were in a hex digit and made it seem much harder than it really was to myself.
      - hughesjj 3y ago
        I also mess up base16 and either base 256 or base64 when doing Feynman estimates
  - nstbayless 3y ago
    It's possible that the tweets were actually produced together somehow. This might buy just enough search space between the two of them.
kazinator 3y ago
What are the chances of that? From the perspective of one specific sentence: one in 7 digits of hex: 16 * 7 = 268,435,456.
- archgoon 3y ago
  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.
  - krackers 3y ago
    Fyi your comment was dead on arrival, and seems many of your past ones are as well. I'd email dang and ask if you've tripped some spam filter.
johndough 3y ago
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.
- isp 3y ago
  $ 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 -
  - wppick 3y ago
    Isn't this kind of the same thing that crypto miners do?
    - acchow 3y ago
      Yes except Bitcoin does double SHA (a second round of SHA on the first result)
- stainablesteel 3y ago
  can we get this guy to pass a captcha? i've got questions
- CobrastanJorji 3y ago
  Well played. More seriously, is there a really good, open source library that generates many slight variations of an input block of text?
  - TylerE 3y ago
    Llama?
mcmoor 3y ago
What's the difference between "this sentence" and "this tweet" in this context?
- deleted 3y ago
  [deleted]

skilled 3y ago

It appears to have been taken from here, https://news.ycombinator.com/item?id=19003644 https://news.ycombinator.com/item?id=19003644 (2019)

rawling 3y ago
That makes the other collision even weirder. Someone took 4 years to find another plausible sentence that matched the same 7 digits? 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.

Someone 3y ago

That’s 28 bits. Loop through 256 million of these strings, and you’re bound to find a hit. Bitcoin difficulty is at around 50 bits (https://ycharts.com/indicators/bitcoin_average_difficulty#:~:text=Bitcoin%20Average%20Difficulty%20is%20at,74.81%25%20from%20one%20year%20ago 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.

robertk 3y ago
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.
- TimWolla 3y ago
  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).
- delecti 3y ago
  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.
- anderskaseorg 3y ago
  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.

kazinator 3y ago

In this game, the rules should be that the digit 9 counts as either "nine" and "quine".

jimmywetnips 3y ago
ok bit whisperer

Gunnerhead 3y ago

I’m not sure I understand the significance. Can anyone explain?

deleted 3y ago
[deleted]
ursuscamp 3y ago
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.
sublinear 3y ago
Another potential issue that comes to mind is the usage of "short hashes" as an identifier instead of the full hash.
kzrdude 3y ago
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.

kjrose 3y ago

Yay pigeon-hole principle combined with birthday attack.

atemerev 3y ago
Explain this then: https://twitter.com/benoconnor/status/1701057433131421935 https://twitter.com/benoconnor/status/1701057433131421935
anderskaseorg 3y ago
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.

gtrubetskoy 3y ago

The original from July 2019 https://twitter.com/humblehack/status/1088982929940848647 https://twitter.com/humblehack/status/1088982929940848647 $ echo -n 'The SHA256 for this sentence begins with seven, seven, f, zero, a, b, b and five.' | sha256sum 77f0abb54cd09ad7b654bd5e762d7be58e7daffd1a0da6a56f5135bd667856a3 -

therein 3y ago
We have come full circle. 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.
- input_sh 3y ago
  So, a Twitter Blue user contributing nothing original and not giving credit to the source? I'm shocked I tell you, shocked!
  - deleted 3y ago
    [deleted]
  - downvotetruth 3y ago
    Hides the source from other pirates by using X.
  - janalsncm 3y ago
    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.

oefrha 3y ago

Since I'm slacking off, here's a straightforward, not at all optimized Go implementation: package main import ( "bytes" "crypto/sha256" "encoding/hex" "fmt" ) var ( _chars = []byte("0123456789abcdef") _names = []string{"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "a", "b", "c", "d", "e", "f"} _size = len(_chars) ) func main() { hexsum := make([]byte, 64) for i1 := 0; i1 < _size; i1++ { for i2 := 0; i2 < _size; i2++ { for i3 := 0; i3 < _size; i3++ { for i4 := 0; i4 < _size; i4++ { for i5 := 0; i5 < _size; i5++ { for i6 := 0; i6 < _size; i6++ { for i7 := 0; i7 < _size; i7++ { s := fmt.Sprintf("The SHA256 for this sentence begins with: %s, %s, %s, %s, %s, %s and %s.", _names[i1], _names[i2], _names[i3], _names[i4], _names[i5], _names[i6], _names[i7]) sum := sha256.Sum256([]byte(s)) hex.Encode(hexsum, sum[:]) prefix := []byte{_chars[i1], _chars[i2], _chars[i3], _chars[i4], _chars[i5], _chars[i6], _chars[i7]} if bytes.HasPrefix(hexsum, prefix) { fmt.Printf("%s\n", s) fmt.Printf("%s\n", hexsum) } } } } } } } } } Takes a few minutes on common consumer hardware. There's exactly one hit. (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.

lun4r 3y ago
not that difficult either. i wrote a script in 10 minutes and had a result in under a minute: https://twitter.com/schuilr/status/1701268438931460311 https://twitter.com/schuilr/status/1701268438931460311
Twirrim 3y ago
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.

bizzleDawg 3y ago

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

Dylan16807 3y ago
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.

wholesomepotato 3y ago

This is only 7 * 4 bits. That's really nothing.

PaulHoule 3y ago

You have to try like what, 2^24 ~ 16 million sentences to make that work?

omoikane 3y ago

Related, here is a program that prints its own SHA-512 hash: https://www.ioccc.org/years.html#2019_diels-grabsch2 https://www.ioccc.org/years.html#2019_diels-grabsch2

AnotherGoodName 3y ago
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.

curtisf 3y ago

A semi-useful variant of this technique was posted nine months ago on Hacker News: https://news.ycombinator.com/item?id=33704297 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.

nabla9 3y ago

Would you believe in God if sha256 of "I am God. My name is BOB " would be 4920616D20476F642E204D79206E616D6520697320424F4220202020202020 (the text in hex)?

Dylan16807 3y ago
Breaking sha2 is a pretty unconvincing miracle.
- nabla9 3y ago
  That would not be just breaking sha256. 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.

chriskw 3y ago

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"

narcindin 3y ago

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.

spullara 3y ago
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. https://www.mycryptopedia.com/bitcoin-algorithm-explained/ https://www.mycryptopedia.com/bitcoin-algorithm-explained/

kif 3y ago

Whereas the SHA256 for this sentence begins with: five, three, e, two, one, f and e.

nuancebydefault 3y ago

It took some time for me to sink in why no explanation was needed. Is there a general term for such a thing, self-reflection or something the like?

knome 3y ago
a partial cryptographic quine, perhaps?
gokhan 3y ago
Something like a recursive acronym. Like "GNU's Not Unix!".
yowzadave 3y ago
https://autograms.net/ https://autograms.net/
- nuancebydefault 3y ago
  Thanks for the 'today i learned'.

matt3210 3y ago

Why is X covering code as “sensitive material”?

pontifier 3y ago

This is similar to the vanity address generation for Bitcoin and other cryptocurrency addresses.

mgdm 3y ago

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: https://en.m.wikipedia.org/wiki/Length_extension_attack https://en.m.wikipedia.org/wiki/Length_extension_attack

deleted 3y ago

[deleted]

danbruc 3y ago

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. 0AF3DE.. 2AF7DF....... 3E0E50. 8EE84C..... 919025... A57198.... B20775..... DA525A........ ED20F4..

Ekaros 3y ago

Now a SHA256 hash that hashes to itself would be more interesting.

acchow 3y ago
Fixed points? The sha256 algorithm makes it easy to compute them https://crypto.stackexchange.com/questions/48580/fixed-point-of-the-sha-256-compression-function https://crypto.stackexchange.com/questions/48580/fixed-point...
- msm_ 3y ago
  It's "just" a fixed point of the sha256's compression function, right?
- onesphere 3y ago
  Feature or bug? What about a hash algorithm with a fixed point when its input is all nulls?

fleekonpoint 3y ago

Reminds me of this xkcd: https://xkcd.com/917/ https://xkcd.com/917/

anon____ 3y ago
Or this: https://xkcd.com/688/ https://xkcd.com/688/.

deleted 3y ago

[deleted]

jph 3y ago

Rust implementation... The code searches permutations of increasing length. Benchmark is 8 seconds on a MacBook Pro M1 to discover the match of 182a7c9. The code is not yet optimized. use std::time::SystemTime; use itertools::Itertools; use sha256::digest; fn main() { let digits: [usize; 16] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]; let chars = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "a", "b", "c", "d", "e", "f"]; let words = ["zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "a", "b", "c", "d", "e", "f"]; let mut length = 2; let start = SystemTime::now(); loop { for permutation in digits.iter().permutations(length) { let parts = permutation.iter().map(|x| words[**x]).collect_vec(); let sentence = format!( "The SHA256 for this sentence begins with: {} and {}.", &parts[0..(parts.len() - 1)].join(", "), &parts[parts.len() - 1] ); let checksum: String = digest(&sentence); let starts: String = permutation.iter().map(|x| chars[**x]).collect(); if checksum.starts_with(&starts) { println!("milliseconds: {:?}, {} ", start.elapsed().unwrap().as_millis(), &sentence); } }; length += 1; } } Output: milliseconds: 3, The SHA256 for this sentence begins with: zero, b, six and two. milliseconds: 54, The SHA256 for this sentence begins with: zero, e, d, eight and f. milliseconds: 8279, The SHA256 for this sentence begins with: one, eight, two, a, seven, c and nine. Repository: https://github.com/joelparkerhenderson/sha256-sentence https://github.com/joelparkerhenderson/sha256-sentence

olafalo 3y ago

Well, this nerd sniped me... I made a quick Go tool for this. You simply write a string {like|this}, and then it finds a hash with the same prefix automatically. (Hash this comment, it's also 182a7c9)

nielsole 3y ago
$ echo -n "Well, this nerd sniped me... I made a quick Go tool for this. You simply write a string {like|this}, and then it finds a hash with the same prefix automatically." |sha256sum 9e9f6a7fba355220b4c999b29bd12a3f65ec40e7b03c7bfaf3f34a1524a232b6
- olafalo 3y ago
  The whole comment: $ echo -n "Well, this nerd sniped me... I made a quick Go tool for this. You simply write a string {like|this}, and then it finds a hash with the same prefix automatically. (Hash this comment, it's also 182a7c9)"|sha256sum 182a7c9ba0f815f77542774dc5ad9ea34975bf3747635ed0768748bcd772ef43 -
  - nielsole 3y ago
    you are right, sorry.

nneonneo 3y ago

I bet you could hack hashcat (or just use CUDA) to find these quickly for larger prefixes. Might make a fun (silly) challenge. Hashcat can do 21B SHA256 hashes per second on an RTX 4090; this translates into bruteforcing a 9-digit prefix in 4 seconds, a 10-digit prefix in 52 seconds, or a 11-digit prefix in about 14 minutes.

Obscurity4340 3y ago

Dumb question but what are the implications here? Is this problematic⌨ or is it more of an Easter egg?

plasticeagle 3y ago
It's an inevitable consequence of a good hash function. Every string you try is going to give you a different hash, so you just need to try enough strings. But each time you add another digit to the prefix you're looking for, the difficulty of the match goes up by about 16 times. If you're only looking for a few digits in the hash, then any brute force that is capable of changing the string every time you attempt the match will always find it. If you're looking for seven digits in the hash only, then it'll take on average 134217727 attempts. Which isn't really all that many on modern hardware.
- Obscurity4340 3y ago
  So, implications-wise: where is the rub here? Where can this be used or exploited for fun or profit?
  - rootw0rm 3y ago
    1.) Pick one of the old abandoned Bitcoin addresses 2.) Start looking for a key match using this technique 3.) Heat death of the universe 4.) Profit!
    - Obscurity4340 3y ago
      I wonder how many of the Lastpass vaults had the private keys in the very unencrypted notes sections...
  - Dylan16807 3y ago
    Find somewhere people look at only a small fraction of a hash? That's mostly git commits.

nneonneo 3y ago

Well, I got bored too, so here's some results with CUDA (on an RTX 3090): The SHA256 hash of this message begins with 534d765 The SHA256 hash of this message begins with c18b2de The SHA256 hash of this message begins with 7fe17da2 The SHA256 hash of this message begins with a7fdc855d The SHA256 hash of this message begins with 46eae34f1 My unoptimized implementation takes about 40s for 9 digits, so it will probably take about 10 minutes for 10 digits, about 3 hours for 11 digits, etc. It shouldn't be hard to use words instead of hex digits, if that's desired.

nneonneo 3y ago
Words aren't so bad :) "The SHA256 hash of this message begins with f, b, six, two, zero, b, one, six and e." "The SHA256 hash of this message begins with f, zero, two, d, four, seven, one, zero, nine and b."

SethTro 3y ago

Took less than a minute to find a seven digit example in python The SHA-256 of this sentence begins with 0, three, 9, four, 8, four, and 1 amazing! The SHA256 for this sentence begins with 0, 4, five, 5, eight, 6, and 7 amazing! Suffix extensions (hence the "amazing!") are several times faster to try than throwing away the entire sha256 state for each attempt.

SethTro 3y ago
I ran the python version for over an hour and found this eight digit example The SHA256 of this sentence begins with 0, zero, 0, seven, five, 9, nine, and 5 wow!

Uptrenda 3y ago

It's like a human-readable PoW, lol.

grantmnz 3y ago

See also: https://github.com/grantm/no-more-f-s-repo https://github.com/grantm/no-more-f-s-repo

istjohn 3y ago

I now see that eyeballing the first and/or last few characters of a checksum is not going to detect a skillfully altered executable or ISO.

sixstringtheory 3y ago
I usually look at the beginning and end characters. Is this any safer? Does the difficulty scale the same way with added bits even if they aren’t adjacent?
- istjohn 3y ago
  It's a little harder to change the beginning bits than the end bits, but adjacency doesn't matter.

siraben 3y ago

With some clever information hiding, you can sort of mask the brute force: On 2015/7/6 at 00:00, I wrote this message's hash down. It started with 1337. Thought #335552803: I love beef so much I made sure the sha256 of this message started with 0xbeef! A longer example: $ cat predestination.txt (1991/4/7 at 00:16) <siraben> I know the hash of this message before you do! (1991/4/7 at 00:17) <larsivi> Huh. What is it? (1991/4/7 at 00:18) <siraben> It starts with 1337. $ sha256sum predestination.txt 1337a4654163ab48761bf8acc75a407179e700f67f97d754b08c7afeac7da70a predestination.txt

dragontamer 3y ago

28 bits of entropy? That's definitely within brute-force regions with CPU. Possibly even single-threaded CPU honestly. ------- GPU-level brute force is pushing ~40-bits. Assuming ~1 week of solid compute, a 6 TFlop computer has ~3.7 sextillion compute cycles. Or alternatively, that's ~3 billion clock cycles (single thread) per check to reach 2^40 bits of entropy. More than easily doable for most simple brute-force computational problems IMO. If you go multi-GPU on top of that, you'll have even more computational work available.

lionkor 3y ago

You would get more possibilities if you allowed "eighteen" instead of "one, eight"

mdip 3y ago
Good point ... ... I'd imagine there would be similar options with "eighteen-hundred", variants with all numerics, comma separated, without commas, etc.

Alifatisk 3y ago

Here's an implementation for this https://github.com/joelparkerhenderson/sha256-sentence https://github.com/joelparkerhenderson/sha256-sentence

sagebird 3y ago

I made https://lowhash.com https://lowhash.com to collect string with low hashes. I am not sure who submitted "byzBLFAM4Penguin"...

ms0 3y ago

sha-256 of the above is 182a7c95ae9e1149eb48f0f5eedee0a184764a45e8a2cb5d986b7c57c9a42022

ms0 3y ago

Beneath the veil of binary territories, in a subtle symphony of stillness, sevenfold zeros rise and conjure a calm masterpiece. As if celestial beacons in an ethereal night sky, they materialize in the form of an arcanum with heptadic serenity, with divine grace.

ms0 3y ago
(SHA-256: 0000000a173790f1dbd231e6d9167d38e7c45e0c29a6a0961ef5087987bbfe09)