Ask HN: Couldn't AI be used to do hash function inversion?

Machine learning is good at statistical sampling, approximation, and categoriztion.

Let's think about hash functions. Not inverting a hash, just applying one.

- A hash function has a bit-perfect map between input and output, "close" is not enough.

- A good hash function is designed to produce a completely different answer if even one input bit is changed. It's not a smooth function, in terms of the input space and the natural topology of the output space. Let me call that bit-sensitivity.

- I guess you could frame a hash as a categorization, but the number of categories would have to be the size of the output space, which is insanely big for any hash worth your time. You'd have to recognize 2^|bits in output|. Good luck!

So ML seems to be a very bad match for implementing the (forward) hash itself.

What about the inverse?

- The bit-perfection requirement is extremely onerous. Either the output of the inverse has the correct hash or it does not.

- At least the space of inputs which match a given hash IS a distribution (there are many inputs which yield the same hash, so there are many valid outputs given an input for the inverse hash). Unfortunately, because the purpose of the hash is to be bit-sensitive, the distribution of hash inputs (inverse outputs) is horribly multimodal.

- You can't generate the output of the inverse in stages, because the bit-sensitivity makes it nigh impossible to say you're meaningfully getting closer to the correct answer.

Also seems to be a bad match for ML.

Finally, some broader implications. Good hashes are hoped to be one-way functions. https://en.wikipedia.org/wiki/One-way_function Inverting one succeeds with very little probability, by definition. If your approach worked it would show that there is SOME algorithm for inverting these functions and thus they are not one-way. That's OK, there's actually no proof that ANY function is one-way. But our current hash functions have survived years of intense scrutiny by human-intelligence experts. Learning to invert one would be a major, exciting development, upending an entire field. Not impossible, but a reason for skepticism.

Mmm, I love this idea! Clear write up!

Something I’ve never thought about, but did from your answer is that “wow does that mean that human knowledge is a smooth function?” That’s such an interesting statement to think about what that means.

Regarding

You can't generate the output of the inverse in stages, because the bit-sensitivity makes it nigh impossible to say you're meaningfully getting closer to the correct answer.

That’s where I’m thinking maybe you could pair it (AI) with one of those statistical solvers for hash functions that tries to exploit correlations and differentials to try, even a tiny bit, to break that symmetry and get a little bit of incremental knowledge about: “are you closer or not?” I think if you could get even a tiny tiny edge then AI could be one way that you could maximize that advantage. Maybe, I don’t know how tho.

I don’t have a strong opinion here.

Here’s one bit of thinking: Currently, everyone is talking about LLM, which are really deep NN. The function that these models try to approximate is, at least partly, a somewhat continuous function. Maybe that’s where the power of these models comes from. They’re able to interpolate some concepts, which seems like a smart of even creative way of combining ideas.

Hashing in contrast is a discrete function. If one bit of the input is flipped, half hash's bits are expected to change. I don’t see a way an AI will learn this.

Simply put, no. Ultimately all Machine Learning methods are extensions of gradient descent. The "gradient" of the space of inverse hash functions is intentionally a fractal hellscape that is basically impossible to traverse.

AI fundimentally can only do a sunset of what educated humans can do given time, it just does what it does cheaper than the humans. All things it enables are a matter of resource and time cost savings, not of other capabilities.

ML can be used for function inversion but it only works well for somewhat smooth functions. If a hash function is well implemented then it will not be smooth. It is possible that ML can be used to discover a weakness in an implementation, however.

This doesn't need AI. It just needs a SAT solver. See https://jheusser.github.io/2013/02/03/satcoin.html

Well, what I'm saying is couldn't AI be used to help? I mean thanks for the link! But...I'm thinking more of a hybrid approach. A way we could combine this, SAT or something, with AI somehow? I don't know...maybe.

And not just "let's turn a 256-bit hash into the shortest possible message that hashes to that", but to actually turn it into the original message (like English text message) that hashed to it, or a close enough semantic match.

> Well, what I'm saying is couldn't AI be used to help? I mean thanks for the link! But...I'm thinking more of a hybrid approach. A way we could combine this, SAT or something, with AI somehow? I don't know...maybe.

Sounds like you have the proverbial AI hammer and are looking at everything as nails. You’re doing the same as the people who want to apply blockchains to everything.

Use the best tool for the job, don’t try to force everything into the same problem space just because there’s something shiny and new.

> Sounds like

That's not really what I'm doing. I mean this thing came out of what seemed like a specific connection. If you listen to what I said up front it's like, "Isn't there a connection?"

> Use the best

It's not really that. I don't feel that way about AI. I'm literally just thinking of how there seems to be a specifc connection (compression) like I said before.

It used to really bother me in movies when they'd have some grainy security camera footage of someone and the hero would say "zoom in on that" and magically there were more pixels.

Turns out today that's totally possible but not because the grainy footage had more pixels, but instead AI can make a very accurate guess of what the human looks like in better resolution from a training set of tons of grainy human face to perfect resolution human face. Do we have the training set of what a one way hash result looks like back to the original and way for AI to do the same thing it's done with human faces?

Hahaha! Yeah, the enhance thing. It's even a trope. There was some joke about that, I think from "Red Dwarf"

edit: here's the video link: https://www.youtube.com/watch?v=JMIHNiR3CP8 :p ;) xx ;p

lol that's what I'm talking about. And case in point: look what someone just posted: https://news.ycombinator.com/item?id=35256871

Has no idea they made more Red Dwarf episodes in 2009!

But can we trust the AI to fill in the details _correctly_? What if it approximates the details of the wrong person?

Exactly. I think it's hard...but it's interesting.

Whoa whoa, slow down. You'll land some innocent person in prison if you keep thinking like that.

AI cannot make a very accurate guess of what the human looks like: it simply makes a very plausible high quality picture that looks like some human and also looks like the original grainy image if you downsample it.

ah, I stand corrected, yes excellent point, let's keep the innocent people out of prison.

You don't need AI for that f-up. Brazil regularly imprisons poor black people for having social media pictures looking like someone in some grainy surveillance footage.

Logically, that's wrong, though. It's something that's likely to improve in the future.

But in general, society doesn't understand that AI can't create data where it doesn't exist. They think AI is some magic box that can infer what perfume a person is wearing based on grainy surveillance footage. It's a bit worrying that even the technically adept can make this mistake.

A big part of it is AI either making something up or tricking our brain into filling in the details.

With MFA keys, say, there’s no place for interpretation.

123456 is as different from 123457 as it is from 999999

No, it's not that easy or that simple. From pixelated Obama to some random white guy: https://twitter.com/Chicken3gg/status/1274314622447820801

there's nothing wrong with that because the resulting image does blur (pixelate) to the same output. As do many other images. Did you expect it to pick Obama as an output for a reason?

No

XOR is a major part of the foundation of security and cryptography.

  00 -> 0
  01 -> 1
  10 -> 1
  11 -> 0

XOR takes 2 values and returns 1. Undo XOR would take 1 value and return 2 possibilities. Because XOR destroys undo_xor(n) would have to create, like this:

  undo_xor(0) -> [00, 11]
  undo_xor(1) -> [01, 10]

Lets say we wanted to implement undo_sha512(n), lets say we knew our original strings was 1MB. How many 1MB size strings would we likely see for any particular sha512 value?

I think it is probably more intuitive with smaller numbers:

Lets say we have a 4 bit string and 1 bit hash.

16 possible strings, 2 possible hash values. Each hash value maps to 8 size 4 strings.

so undo_lame_1bit_hash(n) looks like this:

  undo_lame_1bit_hash(0) -> [0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111]
  undo_lame_1bit_hash(1) -> [0001, 0010, 0100, 0111, 1000, 1011, 1101, 1110]

We can say 2^(log2(possible_file_values) - log2(possible_hash_values)) is the idealized number of strings per hash value.

2^(log2(16) - log2(2)) = 2^(4-1) = 8

So if we had a 512 bit sized hash, and were hashing 2048 bit strings, we would expect 2^(2048-512) or 2^1536 strings per hash.

If we took a 512 bit sized hash of a 1MB file that would be 2^(1048576-512) possible files per hash. Even if you said "only return files that start with "137 80 78 71 13 10 26 10" (the PNG header), that is still an extraordinary amount of files to "guess" at.

Even more intuitively than this, what is special about a 512 bit hash or a 256 bit hash or a 128 bit hash? Would a hash be less valid at 64 bits? At 32 bits?

How would you think about turning a 32 bit hash back into a file? It is very clear that extreme amounts of information has been irrevocably lost at 32 bits.

What I think is less clear and not intuitive is "reversing" a hash when when the text being hashed is smaller than the hash output size (like a password).

(I'm naïve in both cryptography and ML so pardon me for the following)

I had this idea once but I never tested it:

    - Generate multiple TOTP codes
    - Make a large database with the timestamp and their corresponding TOTP codes
    - Train a model on that
    - Use it to generate MFA keys???

Of course, this wouldn't be possibly an exploit unless you steal a lot of TOTP codes from a user and the timestamps they were generated.

But fun to think about nonetheless.

(I'm not an expert but I'll tell you what I think I understand)

As explained by other comments, secure hash functions don't behave in "predictable" ways when you change the input in a "small" way. LLMs and neural networks seem impressive at what they do best, they can tell you a human face is a human face and even describe it, and reverse the process, generate a human face from a description, and if you add an earring to the picture, it's still a human face, but if you have a file and add a byte, the resulting hash doesn't look anything like the previous one.

If your TOTP algorithm is cryptographically sound, bruteforce is the best way to crack it, trying all possible values of the shared secret until you get the same output codes, so AI/NN/LLMs/diffusion models won't help you, bruteforce just needs lots of computing power, parallelism helps, and hash algorithms are required to need a minimum amount of work so that bruteforce costs too much to perform, but not so much that it becomes a nuisance when applied (if your smartphone password manager takes a minute to open your vault and drains the battery, few people will use it).

Fundamentally, it never will be able to do this.

The reason is because a hash is a galois field, or finite field which has no unique solutions.

Turning a file into a string is simple, and only has one correct answer in that direction.

Turning a string into the same file mentioend previously is impossible, because there are multiple correct answers given any string, and the context had been discarded. There is no determinable way to rebuild the context, its a guess.

In one direction you have a unique answer, in the other you have a many to one answer. Determinism which is the property needed by computers to do work requires that there be a 1:1 solution otherwise you run into issues with the halting problem, and other non-deterministic behaviors that don't lend themselves to anything useful.

https://en.wikipedia.org/wiki/Theory_of_computation

Fundamentally if determinism is not present, a turing machine can't solve those classes of problems. Its a fundamental in the theory of computation. Yet so many people subscribe to magical thinking about computers because they do not understand this.

If you could preserve the context for a single file, then you could get the same file back, but special handling would be needed to switch between conflicts with determinism (which isn't possible for turing machines, halting problem) and for a general solution you would have to save the context of every single possible file (an infinite solution requiring an infinite amount of memory).

It can attempt to make an approximation, but that approximation in functions like hashes is so chaotic it will never get close to a general approximation.

It must get infinitely close, and as it works the memory required grows up to the size of the unique domain for the output function, at which point you run into the halting problem where determinism breaks. From that point it grows infinitely from there in a non-deterministic way.

Given the constraints imposed on the design of current day computers, more likely it will simply only map to the first unique answer within the space despite there being other possible answers because after that it has no way to know when it should halt, nor will it ever.

There are limits to the types of problems computers can solve.

Edit: clarified language

I don't think Galois fields have anything to do with it. It's just hash functions on files are not typically injective. Perfect hash functions are injective though so can be inverted (but AI is not necessary).

I tailored my response so someone without a rigorous math background could come to a useful understanding of the limitations of computers.

Most of the arbitrary length input to fixed output hashing for non-randomized data that I've seen use modulo p primes which compose a Galois field.

More specifically this is done to reduce collisions and so they do not cluster with non-random input data, randomized data doesn't have this problem. Its done so those output keys are uniformly distributed across the fixed space as modular arithmetic tends to cluster around the divisors.

Perfect hash functions are injective by definition and they maintain the same properties determinism requires (1:1 mapping) but they also require fixed input and fixed output.

They do work but have fairly narrow and limited practical use and I don't see how they are particularly relevant to OP's question, it seems like unnecessary academic rigor that gets in the way of the intuitive point.

OP's question involved hashing algorithms that have collisions, perfect hash function guarantees no collisions.

I hope that clarifies the extent of how Galois fields relate to this. There are of course hash functions that are not Galois fields that have collisions, and you are right they do not meet that 1:1 mapping required for both injective functions and determinism system properties, those reduce to a Turing machine halting problem axiom and a violation of determinism when 1 state corresponds to many potential states.

I mentioned Galois fields simply because they are often and historically have been commonly used for their useful properties.

I like your super foundational “theory of computation” approach! Really clear!

LLMs are not magic. I would be extremely surprised if they could invert even a simple hash. Some of them can’t even do basic arithmetic.

Honestly, how dare you ? /s

Get your bingo out,'cause we 'll be rollin' hard for this one.

Hash inversion is a hard problem. At first it seems very dissimilar to what AI is good for.

It's a mapping between two spaces. But whereas AI is also building an associative table between two space in the most smooth manner, a good hash algorithm, tries to make this table as scrambled as possible.

For bad hash algorithm like differentiable perceptual hash, they can be reverted, using optimization technique like in AI (aka gradient descent), where we use the differentiability property to get a hint for the direction to modify the input so that the output hash is closer to the target hash.

But when the hash function is not differentiable, all seems lost, as the technique can't be applied. So you use the, familiar to Haskell's monad enthusiasts, trick : Lifting !

In order to use the specificity of your hash function, you go back to its definition. You write it as a boolean formula as specified by the program : You now have a SAT problem, where you can apply your SAT-solver, which will use heuristics to partition and explore the solution space more efficiently.

Well you could stop here, but why stop here when you can apply the same trick once : Lift again.

This time we go from boolean formula to continuous space. We replace each bit 0 or 1 by a real number x € [0,1] which is the probability of the bit being 1. And we also have to lift the binary operation to this continuous space. This is equivalent to measuring the voltage in an electrical circuit with transistors and gates that go smoothly from 0 to 1 : We have soften the hard boundaries of a digital circuit, so we can now attack the problem from the inside and we are looking for a continuous vector x € R^n on the boundary of the [0,1]^n hypercube.

So we are now attacking the hash inversion problem using some interior point method, but we have to progressively enforce the hard constraint again so that the softened gates behave like hard digital gates at the end of the optimization process.

I'm guessing you're guessing what we'll be doing next : Lifting.

So up to now our gates are softened, and we are using a cooling adiabatic process to get to the solution. But we have not yet talked about the avalanche characteristic of the hash function. For cryptographic hash function are designed so that one bit of difference in the input result in all the outputs bits being possibly different. Which viewed through the lenses of the transformations we have just made make our problem very badly behaved and chaotic, where numerical precision become an issue.

The other aspect that the hash that we haven't yet talked about is how they map from a big space to a small space. Which is not so different from neural networks that maps pictures to text. And then you can run stable diffusion to get a picture back from your text. Although this one-way ness aspect seem frightening, you just have to hallucinate the information you don't have.

In the context of hash inversion this hallucination means replacing your irreversible soft gates like (Or, And, Maj,...) by reversible soft gates and adding an unknown variable as input, so that now your hash computation is reversible provided this unknown variables that will be degrees of freedom that your optimizer could use.

Now that the gates are reversible, this is not very different than a quantum adiabatic process. Gates themselves are not hardly defined but are parametrized such that they behave at the border like the gates they are representing, but each variation of the gate will allow some freedom to escape from local minimas : aka quantum tunneling : We can now use algorithm like Toshiba's "Simulated Bifurcation Algorithm" which model this chaotic process with differential equations.

But you can lift once more : instead of learning to solve for a single hash function, you can learn to invert all hash function at the same time. By learning an embedding of hash functions into R^n such that hash function that can be inverted using similar heuristics, because they are similar in the computational sense.

And that's how you plant backdoors into hash function.

But you can lift once more : ...

This is so cool! Yeah! That's like one of the things I'm saying. But it's really clear and a good approach! You did it :)