3 ms·
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 t
by hayst4ck 4y ago
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.
0000 -> 0
0001 -> 1
0010 -> 1
0011 -> 0
0100 -> 1
0101 -> 0
0110 -> 0
0111 -> 1
1000 -> 1
1001 -> 0
1010 -> 0
1011 -> 1
1100 -> 0
1101 -> 1
1110 -> 1
1111 -> 0
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).