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)
}
}
}
}
}
}
}
}
}
(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.
#!/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)"SHA256" vs "SHA-256"
"begins" vs "starts"
":" vs ""
"%s," vs "%s"
"%s and" vs "%s, and"
"." vs ".\n"
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.
#!/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
Here is a slightly different version I wrote that has 0 allocations per loop.
Took about 26 seconds.
I'm welcome to suggestions on how to make it more readable! Its been a few years since I have written Go professionally
As always, the real WTF is in the comments.
$ 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 -More seriously, is there a really good, open source library that generates many slight variations of an input block of text?
$ 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 -
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...
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.
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.
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.
If you keep randomly changing letters or words in a sentence, you can eventually make sha256 spit out a hex string whose start matches any 7 digit hex sequence you want.
$ 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.
https://crypto.stackexchange.com/questions/48580/fixed-point...
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 "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 -
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.
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
"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."
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.
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.
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.
The SHA256 of this sentence begins with 0, zero, 0, seven, five, 9, nine, and 5 wow!
... I'd imagine there would be similar options with "eighteen-hundred", variants with all numerics, comma separated, without commas, etc.
- SSL
- Bitcoin (bonus: unlimited money hack if you can keep the discovery under wraps)
- Signed updates for devices
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://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.
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;
}
}
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.
"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"
$ echo -n "The SHA256 for this sentence begins with: one, eight, two, a, seven, c and nine." | sha256sum
182a7c930b0e5227ff8d24b5f4500ff2fa3ee1a57bd35e52d98c6e24c2749ae0 - 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!
$ 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.txtWith 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.
0AF3DE..
2AF7DF.......
3E0E50.
8EE84C.....
919025...
A57198....
B20775.....
DA525A........
ED20F4..-------
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.
I am not sure who submitted "byzBLFAM4Penguin"...