Tag Info

0

This isn't an answer, but is too long for a comment. I pray the Stackexchange Purity Gods will forgive me. Imagine a simple hash function. Like take one I've seen used to hash strings when building a dictionary: add up the ASCII or Unicode values of all the characters and take the remainder modulo some fairly large n, usually the maximum value that will fit ...

2

Your error is here: An OR gate cannot be reversed, since it fundamentally losses information. However, a possible input can be derived from any given output. A set of possible inputs can be derived from any given output. For each output that is a 1, there are three possible combinations of input (01, 10, and 11). If you add enough gates in sequence, ...

1

Why can't I reverse a hash to a possible input? Actually, depending on the individual hash and explicitly ignoring all computational feasibility issues, you could. Just don’t expect the result of your reversal to be the same as the “original input”. Furthermore you should be aware of the fact that, depending on the type of hash and depending on the ...

4

Because a hash function essentially destroys the inputs, or information. For example, a common operation in hashing is modular math, which is basically the remainder after the division. 9 mod 2 = 1 (9 / 2 = 4, remainder 1). The 1 moves on in the hashing function. But the modular operation is irreversible - all that is left is the output of 1, but there ...

33

It is correct that any hash function used in cryptography, restricted to fixed (or bounded) input size, can be implemented as a finite number of NOT and OR gates. What's more: the gates can be given an index such that the input of any gate consists of either an input of the hash function, or an output of a gate with lower index; this insures the construction ...

24

What you're missing is the fact that multiple logic gates can share the same input(s). So you can't look at each logic gate individually and "reverse" the entire circuit that way, because choosing the inputs of a logic gate may constrain the outputs of other logic gates (so not all possible choices of input for any logic gate will work, only some will). So ...

1

You try to dis-prove something that is not a feature of a hash function. You can always brute-force a hash function by trying all possible inputs upto a given length until you find a preimage of a given hash. The claim for a cryptographic hash function is that it is computationally difficult to find such a preimage. In fact, this claim is not proven for any ...

Top 50 recent answers are included