mjhjmtu

This isn't really a stats answer, but:

No, you can't determine the first character of the plaintext from the hash, because there's no such thing as "the plaintext" for a given hash.

SHA-256 is a hashing algorithm. No matter what your plaintext, you get out a 32-byte signature, often expressed as a 64-character hex string. There are far more possible plaintexts than there are possible 64 character hex strings - the same hash can be generated from any number of different plaintexts. There's no reason to believe that the first character being/not being a '1' is uniform across all plaintexts producing a given hash.

SHA256 is designed to be as random as possible, so it is unlikely you would be able to separate hashes that came from 1-prefixed plaintext from those that do not; there should simply be no feature of the hash string that would give that information away.

Regardless if this is "Possible", what algorithm would be the best approach?

Sorry, but that's a nonsensical question. If something is impossible, then you can't search for the best approach to the problem.

In this case, this definitely should be impossible because hashing is a one-way function: several inputs (infinite, in fact) can produce the same output. If the first bit of input on its own would somehow influence the probability of a specific hash value, this would mean that the hash algorithm is completely flawed.

You certainly can train a neural network, linear classifier, SVM and whatnot to attempt prediction. And if you will be able to reliably predict the input from output for a certain hashing algorithm, this would prove that this algorithm is worthless. I'd say that for a widely used algorithm like SHA256 such a possibility is vanishingly low. However, it's a reasonable approach to quickly rule out new, unproven and untested hashing algorithms.

While one can't prove a negative with an example.
Still I feel an example would be suggestive; and perhaps useful.
And it does show how one would (attempt to) solve similar problems.

In the case of
I want to make binary predictions, using features that are binary vectors,
a Random Forest is a solid choice.
I guess this kind of answers the second part of your question: what is a good algorithm.

We well want to preprocess the SHA256 strings, into binary (Boolean) vectors,
as each bit is statistically independent, thus each bit is a good feature.
So that will make our inputs 256 element boolean vectors.

Demo

Here is a demonstration of how the whole thing can be done using the Julia DecisionTree.jl library.

You can copy paste the below into the julia prompt.

using SHA
using DecisionTree
using Statistics: mean
using Random: randstring

const maxlen=10_000 # longest string (document) to be hashed.

gen_plaintext(x) = gen_plaintext(Valx())
gen_plaintext(::Valtrue) = "1" * randstring(rand(0:maxlen-1))
gen_plaintext(::Valfalse) = randstring(rand(1:maxlen))


bitvector(x) = BitVector(digits(x, base=2, pad=8sizeof(x)))
bitvector(x::AbstractVector) = reduce(vcat, bitvector.(x))

function gen_observation(class)
 plaintext = gen_plaintext(class)
 obs = bitvector(sha256(plaintext))
 obs
end

function feature_mat(obs)
 convert(Array, reduce(hcat, obs)')
end

########################################

const train_labels = rand(Bool, 100_000)
const train_obs = gen_observation.(train_labels)
const train_feature_mat = feature_mat(train_obs)

const test_labels = rand(Bool, 100_000)
const test_obs = gen_observation.(test_labels)
const test_feature_mat = feature_mat(test_obs)


# Train the model
const model = build_forest(train_labels, train_feature_mat)
@show model


#Training Set accuracy:
@show mean(apply_forest(model, train_feature_mat) .== train_labels)

#Test Set accuracy:
@show mean(apply_forest(model, test_feature_mat) .== test_labels)

Results

When I did this,
training on 100,000 random ASCII strings of length up to 10,000.
Here are the results I saw:

Train the model

julia> const model = build_forest(train_labels, train_feature_mat)
Ensemble of Decision Trees
Trees: 10
Avg Leaves: 16124.7
Avg Depth: 17.9

Training Set accuracy:

julia> mean(apply_forest(model, train_feature_mat) .== train_labels)
0.95162

Test Set accuracy:

julia> mean(apply_forest(model, test_feature_mat) .== test_labels)
0.5016

Discussion

So that is basically nothing.
We went from 95% on the training set, to barely over 50% on the test set.
Someone could apply proper hypothesis tests, to see if we can reject the null

hypothesis, but I am pretty certain we can't.
It is a tiny improvement over the guess rate.

That suggests that it can't be learned.
If a Random Forest, can go from well fitted to hitting just the guess rate.
Random Forests are pretty capable of learning difficult inputs.
If there was something to learn, I would expect at least a few percent.

You can play around with different hash functions by changing the code.
Which could be interesting
I got basically same results when using the julia in built hash function (which is not a cryptographically secure hsah, but still is a good hash so should indeed send similar strings apart).
I also got basically the same results for CRC32c.

Hash functions are (by design) extremely badly suited for doing anything machine learning with them.

ML is essentially a family of methods for modelling / estimating locally continuous functions. I.e., you're trying to describe some physical system that, while it may have certain discontinuities, is in some sense in most of the parameter space smooth enough so that only a scattered sample of test data can be used to predict the result for other input. To do that, the AI algorithms need to somehow decompose the data into a clever basis representation, for which the training has suggested that e.g. if you see such and such shape (which appears to correlate with the result of such and such convolution) then there's a good chance that the output should have in the corresponding region such and such structure (which can again be described by a convolution or something).

(I know, many ML approaches aren't like convolution at all, but the general idea is always the same: you have some input space that's so high dimensional it's impossible to sample exhaustively, so you find a clever decomposition that allows you to extrapolate results from a comparatively sparse sample.)

The idea behind a cryptographic hash function however is that any change to the plaintext should result in a completely different digest. So no matter how you decompose the function, local estimators will not allow you to extrapolate how small fluctuations around that part influence the result. Unless of course you actually process all of the information of a limited set, but this wouldn't be called machine learning: you'd just be building a rainbow table.

This is an interesting question because it raises issues about what counts as "machine learning." There is certainly an algorithm that will eventually solve this problem if it can be solved. It goes like this:

1. Pick your favorite programming language, and decide on an encoding that maps every string to a (potentially very large) integer.




2. Pick a random number and convert it into a string. Check to see if it's a valid program in your language. If it's not, pick another number and try again. If it is, start it, immediately pause it, and add it to a list of paused programs.




3. Run all the paused programs for a little while. If any of them halt without producing an adequate solution, remove them from the list. If one produces an adequate solution, you're done! Otherwise, return to 2 after letting them all run for a bit.

There's no question that if you have infinite storage and infinite time, the above algorithm will eventually find a good solution. But that's probably not what you mean by "machine learning."

Here's the rub: if you consider all possible problems, no machine learning algorithm can do better on average! This is known as the no free lunch theorem. It proves that among all the possible problems you could throw at any given machine learning algorithm, the number that it can solve quickly is vanishingly small.

It can solve those problems quickly only because they are governed by patterns that the algorithm can anticipate. For example, many successful algorithms assume the following:

1. Solutions can be described by some complex series of matrix multiplications and nonlinear distortions, governed by a set of parameters.




2. Good solutions will be clustered together in parameter space, so that all you have to do is pick a search neighborhood, find the best solution there, shift your search neighborhood so that the best solution is in the center, and repeat.

Obviously neither of these assumptions hold in general. The second is particularly suspect. And the no free lunch tells us that these assumptions don't even hold most of the time. In fact they almost never hold! It's just our good fortune that they do hold for certain problems that actually matter.

The problem you've chosen is designed from the beginning to violate assumption 2. Hash functions are specifically designed so that similar inputs give completely different outputs.

So your question—what is the best machine learning algorithm for solving this problem?—probably has a very straightforward answer: random search.

It is next to impossible. However, people observed some patterns in SHA256 which might suggest its non-randomness A distinguisher for SHA256 using Bitcoin (mining faster along the way). Their tldr:

"To distinguish between an ideal random permutation hash and SHA256, hash a large amount (~2^80) of candidate 1024 bit blocks twice, as done in Bitcoin. Ensure that the bits of the candidate blocks are sparsely set (much fewer than the 512 mean expected), according to the Bitcoin protocol, discarding candidate blocks that do not meet the Bitcoin “difficulty” standard (where the resultant hashes start with a the large number of 0’s). With the remaining set of valid input candidates (467369 when this analysis was done), observe a particular set of 32 bits in the input block (located where Bitcoin has the nonce, input bits 607-639). Note that the mean number of bits set in the nonce field is skewed to the left, i.e. fewer than the expected value of 16 bits set (estimated mean 15.428)."

See a discussion on lobste.rs. One possible explanation is a bias introduced by the miners.

I'll answer with a program. To reduce computational requirements I'll use a variant of sha256 I call sha16, which is just the first 16 bits of sha256.

#!/usr/bin/python3

import hashlib
from itertools import count

def sha16(plaintext):
 h = hashlib.sha256()
 h.update(plaintext)
 return h.hexdigest()[:4]

def has_plaintext_start_with_1(digest):
 """Return True if and only if the given digest can be generated from a
 plaintext starting with "1" first bit."""
 return True

def plaintext_starting_with_1(digest):
 """Return a plaintext starting with '1' matching the given digest."""
 for c in count():
 plaintext = (b'x80' + str(c).encode('ascii'))
 d = sha16(plaintext)
 if d == digest:
 return plaintext

for digest in range(0x10000):
 digest = "%04x" % (digest,)
 plain = plaintext_starting_with_1(digest)
 print("%s hashes to %s" % (plain, digest))

This produces the output:

b'x8094207' hashes to 0000
b'x8047770' hashes to 0001
b'x8078597' hashes to 0002
b'x8025129' hashes to 0003
b'x8055307' hashes to 0004
b'x80120019' hashes to 0005
b'x8062700' hashes to 0006
b'x8036411' hashes to 0007
b'x80135953' hashes to 0008
b'x8044091' hashes to 0009
b'x808968' hashes to 000a
b'x8039318' hashes to 000b
[...]

I'll leave the full proof as an exercise for the reader, but take my word for it: there's an input that starts with a "1" for each possible digest from 0000 to ffff.

There's also an input that doesn't start with "1". And there's one that starts with the complete works of Shakespeare, too.

This holds for any reasonably good hash function, although my brute force proof may become computationally infeasible.

What you describe is basically a pre-image attack. You're trying to find an input such that, when it is hashed, the output has some property like "a leading 1".*

It is an explicit goal of cryptographic hashes to prevent such pre-image attacks. If you can make such an attack, we tend to consider that algorithm to be insecure and stop using it.

So while that means it's not impossible, it means your machine learning algorithm would have to simultaneously outwit a large fraction of the mathematicians in the world, and their super computers. It is unlikely that you will do so.

However, if you did, you would become known as someone who broke a major cryptographic hash algorithm. That fame is worth something!

^{*Technically a "first preimage attack" tries to find a match for a specific hash. However, to show that a hash algorithm has first preimage attack resistence, they typically show that you can't find any meaningful information about the input from the hash.}

Most all the answers here are telling you why you can't do this but here's the direct answer to:

Regardless if this is "Possible", what algorithm would be the best approach?

Assuming the input is sufficiently large:

1. Take the count of the set of valid characters.


2. Take the reciprocal of the number from step 1.

That's the probability that the input string starts with '1'. You don't even need to look at the input. If you can do better than that, it would mean the hash is very broken. You can save a lot of CPU cycles over trying to train an algorithm to pick random numbers.

You could train an algorithm and it might come up with a different answer because of overfitting. That is unless there's something really wrong with the hash algorithm. Using this algorithm is then going wrong more often than if you simply pick a random value.

Hashing functions are purposefully designed to be difficult to model, so (as pointed out already) this is likely to be very difficult. Nevertheless, any weakness in the hashing function will reduce its entropy, making it more predictable.

Regardless if this is "Possible", what algorithm would be the best approach?

A useful example is the Physically Unclonable Function, or PUF - which is analogous to a hardware hashing function. Typically, manufacturing variations are purposefully used to give each PUF a slightly different response so that their 'hashed' output is different for a given input. Design weaknesses limit the entropy, however, and given enough challenge-response pairs it is often possible to build a black-box model of the PUF so that the response for a new, previously unseen challenge can be predicted.

Logistic regression is the most commonly used approach for these modelling attacks, such as in this paper by Rührmair.

Genetic algorithms (or more generally evolutionary strategies) may be an alternative approach, as they are applicable to problems that are not differentiable and/or linearly separable. They are also discussed in the above paper.

Lets say that your plaintext/input is exactly one block long (512bits=1block for SHA256). The input space for it is $2^512$ and hash space is $2^256$. For simplicity, lets take the first $2^256$ inputs into consideration.


Now you train a machine learning algorithm (Any algorithm of your choice), with a training set of size $2^64$ by hashing every number from $0$ to $2^64-1$ (This itself would take alot of time and gargantuan amount of space to store, but lets put that aside for a moment).


After training over such a massive training set, you would expect the model to work accurately but no. The remaining $2^256-2^64$ input-hash pairs could be mapped in $(2^256-2^64)!$ ways. Out of those many ways to arrange, only one arrangement would be our SHA256.

Let $S=(2^256-2^64)$ (Total number of mappings) and
$C=frac90100*S$ (Number of correct mappings for 90% accuracy)

The probably to achieve even 90% accuracy with our model would be (probability of $C$ correct mappings)*(probability of ($S-C$) incorrect mappings) =
$$(frac1S*frac1S-1*frac1S-2...*frac1S-(C-1) ) * (fracS-C-1S-C*fracS-C-2S-C-1*fracS-C-3S-C-2...*frac12) = frac(S-C-1)!S!$$

Plugging in the values, probability that our model would achieve 90% accuracy is$$= frac(frac110*(2^256-2^64)-1)!(2^256-2^64)!$$
Taking logarithms and using Sterling's approximation for factorials, the probability is $$approx 2^-(2^263.9918466566-2^260.6509677217)$$
$$approx2^-10.1322237391*2^260.6509677217$$

Phew, thats a really small number. And this is an overestimation, since we have considered only the first $2^256$ inputs instead of the total $2^512$. The actually probability will be still lower.

The problem is that "machine learning" isn't intelligent. It just tries to find patterns. In SHA-256, there are no patterns. There is nothing to find. Machine learning hasn't got any chance that is better than brute force.

If you want to crack SHA-256 by computer, the only possibility is to create real intelligence, and since lots of clever humans haven't found a way to create SHA-256, you need to create artificial intelligence that is a lot higher than that of many clever humans. At that point, we don't know if such a super-human intelligence would crack SHA-256, prove that it cannot be cracked, or would decide that it is not clever enough to do either (just as humans). The fourth possibibility is of course that such a super-human artificial intelligence would not even bother but think about problems that are more important (to it).