Suppose there are three messages A
, B
and C
of different length, that are 16 DWORDs in length when combined. I know the plaintext and length of A
and C
, and only length of B
. Is it possible to take any advantage of this knowledge when trying to recover a preimage of MD5(A || B || C)
? I'm targeting "raw" MD5 transform, as C
is in fact padding and bitlength, so I feed it with 16 DWORDs of input and expect to get 4 DWORDs of digest back.
A
is 8 DWORDs in length, and B
and C
are 4 DWORDs in length each.
I can only think of precomputing first round as much as possible as long A
message is used, but that does not give that much speedup. Any metacompilation techniques?
UPD1: I have the following idea, but I'm unsure if it has any value in this context and in general. I would greatly appreciate review of it.
It's possible to express each DWORD as collection of independent bits, each possibly being in three states - set (0), unset (1) and upset unknown. All unknown bits have their unique ID, and hold up their creation history - as result of XORing two unknown bits is also unknown, we spawn more unique unknown bits when necessary. It's possible for unknown bit to be "determined" by ANDing it to 0 or ORing to 1, so the outcome is no longer unknown. Also XORing it to itself would make it 0, while XORing unknown bit to it's inverted counterpart will make it 1, and so on.
Rotation has no effect on bits themselves, only on their order in the "DWORD collection". Bitwise operations for DWORDs scale down to bits in obvious manner, and addition is expressed through ADD operation, which returns result and carry bit, which is in turn ignored when adder's result is the MSB.
After such tracing or 'metacomputation' we will end up in directed graph having 128 unknown input bits (message B) and 128 output bits of digest hardly twisted and entangled with input bits. Each node of graph is operation (XOR, AND, OR, NAND, NOR, NOT, ADD etc), incoming edges will be arguments to these functions, outgoing edges are results. Symmetrical transitive binary operations can be extended to arbitrary arity using behavioral definition like 'if any of the arguments is set, result is also set' for OR, or 'invert result of XORing all the unknown argument bits if XORing known bits together produces 1' for XOR.
So first idea is to try to simplify this graph using rules expressed above as much as possible, then unwind each bit's history, revealing long expression of AND/OR/XORs making use of initial unknown bits from B
message, and try to find common chains of operations that may be computed at once. Problem with this approach is that I overcomplexify calculations 32 times, as DWORDs are breaked down into bits... Maybe there is way to somehow bond them back, producing some function taking B
message candidate and returning single DWORD in most compact way? I don't know. Also I don't know if I can use the same approach but with DWORDs instead of bits at the lowest level.
Second idea is to try to reverse this graph, feeding desired MD5 output into "output unknown bits" and trying to figure out what arguments were to produce such results - for example, if OR(A, B, C, ...) == X
, while X being unknown bit revealed to be zero, it's impossible for A, B and C (and others) to be anything but zero, so propagation can proceed. Same applies to AND(A, B, C, ...) == X
, where X is set - A, B and C have to be all set. For ambigous cases branching should occur, pushing current graph state into stack, selecting one of possible argument layouts and proceeding until first conflict - e.g. for example according to one expression unknown bit should be unset, and according to other expression same bit should be set, this means one of possible paths previously selected was wrong and next should be tried.
So, as this hadn't implemented already, something is wrong with it. What exactly is wrong? I think it may figure out that time needed for walking through all the branches exceed bruteforce time, but I'm not sure.