take the data you want to hide and use it to seed some large but manageable number of Turing Machines with random rulesets.

 

You let them run for up to 𝑡 steps, and then see which ones have halted by that point. [...] Say you ran 1024 TMs; if you give each an index, and then toggle the corresponding bit depending on whether each one halts, you get a 1024-bit number [...]

I think I may be misunderstanding your idea here. Let me paraphrase:

The user inputs a string; let's say "password". We seed 8 Turing machines with the user's input: one with p, one with a, one with s, another one with s, and so on. Then we run each machine for 1000 steps. Let's say that machines p, s, and r halted in that time, and the rest didn't halt. So now you have an 8-bit string 10110010. And somehow you're claiming that this is hard to invert?

It seems trivial to invert. As an attacker, I can easily find a preimage that gives me 10110010. I just put random inputs through the 1000-step process until I find one that halts and one that doesn't; let's say, p halts and q doesn't. Then a valid preimage of 10110010 is pqppqqpq.

Remember, it doesn't matter if I can't invert your hash function. What matters is whether I can produce a collision. If you just want a function that's not invertible, you should use f(x) = 0 for all x — using that hash function, there's clearly no way I could ever figure out your password just from knowing that its hash value was 0! But "non-invertibility" is not the important thing, in a hash function. What's important is resistance to collision attacks.

Now, you did say that somehow we've got to take the user's 8-character password and expand it out to 1024 random Turing machines. You didn't describe how to do this non-trivial operation. The operation is technically known as key stretching. Sounds like you're relying on the key-stretching operation (which you did not specify) for literally all of the security properties of your algorithm. Which means that all this stuff about Turing machines and running for 1000 steps is completely superfluous.

take the data you want to hide and use it to seed some large but manageable number of Turing Machines with random rulesets.

You let them run for up to 𝑡 steps, and then see which ones have halted by that point. [...] Say you ran 1024 TMs; if you give each an index, and then toggle the corresponding bit depending on whether each one halts, you get a 1024-bit number [...]

I think I may be misunderstanding your idea here. Let me paraphrase:

The user inputs a string; let's say "password". We seed 8 Turing machines with the user's input: one with p, one with a, one with s, another one with s, and so on. Then we run each machine for 1000 steps. Let's say that machines p, s, and r halted in that time, and the rest didn't halt. So now you have an 8-bit string 10110010. And somehow you're claiming that this is hard to invert?

It seems trivial to invert. As an attacker, I can easily find a preimage that gives me 10110010. I just put random inputs through the 1000-step process until I find one that halts and one that doesn't; let's say, p halts and q doesn't. Then a valid preimage of 10110010 is pqppqqpq.

Remember, it doesn't matter if I can't invert your hash function. What matters is whether I can produce a collision. If you just want a function that's not invertible, you should use f(x) = 0 for all x — using that hash function, there's clearly no way I could ever figure out your password just from knowing that its hash value was 0! But "non-invertibility" is not the important thing, in a hash function. What's important is resistance to collision attacks.

Now, you did say that somehow we've got to take the user's 8-character password and expand it out to 1024 random Turing machines. You didn't describe how to do this non-trivial operation. The operation is technically known as key stretching. Sounds like you're relying on the key-stretching operation (which you did not specify) for literally all of the security properties of your algorithm. Which means that all this stuff about Turing machines and running for 1000 steps is completely superfluous.