Speeding up partially known plaintext preimage recovery attack on MD5

Question

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.

Answer 1

Your idea is equivalent to doing "constant folding" or "partial compilation". It's not likely to make much difference (see below for detailed explanation).

But, even setting that aside, there's a more significant reason why you're not gonna be able to find B. In your situation, the unknown part (B) is 4 DWORDs long, i.e., 128 bits long. This means that you'd have to iteratively try all $2^{128}$ possibilities for B, and no matter how much optimization you do, it'll still take forever. Even if it only takes on clock cycle to try a guess at B, $2^{128}$ clock cycles is approximately forever. So, your problem is hopeless, even once we take into account your ideas for optimization.

---

An explanation of why your idea won't provide much of a speedup: Basically, your idea is equivalent to the following:

• Write down the full MD5 computation, as a set of straight-line code.

• Next you can fix some of the inputs (the parts corresponding to A and C) to particular compile-time constants.

• Now traverse the computation graph. Any time you see an operation on two variables whose values are both known to be compile-time constants, you can replace that expression with its precomputed value.

  For instance, if you see the expression x+y where both x and y are compile-time constants -- say, 5 and 7, respectively -- you can replace x+y with its value, namely, 12. If you see an assignment z = 12, then thereafter the value of z is known to be a compile-time constant and can be used to trigger further optimizations.

• Repeat this simplification process until no further simplifications are possible.

What remains is an optimized version of the computation, with only the operations that are needed (whose value cannot be predicted in advance). In the compiler community, this optimization is known as "constant folding". It is equivalent to what you are proposing.

Unfortunately, this is not likely to help very much. If you try it on an example, you'll find that most of the intermediate values computed during the MD5 computation do in fact depend upon B and thus cannot be constant-folded (optimized) away. Consequently, your idea is not going to lead to much of a speedup.

If B was shorter, there might be other ways to speed up exhaustive search a bit. You could look at standard methods for optimizing MD5 brute-force search. For instance, you might look at how password cracking tools optimize the process. I think the #1 most important technique is to use a GPU, and perform the MD5 computations on your GPU -- this yields major speedups. But read more about the techniques that the password-cracking tools use. They should all carry over to your situation as well.

However, with a 128-bit value of B, this is all moot. It doesn't matter how many GPUs you have, or how much optimization you do: you're not going to be able to find B through exhaustive search over all possibilities.

Answer 2

It sounds like you're pretty much out of luck.

Yes, there are a few tricks you could use to speed up a brute force search; for example, if we fix everything other than DWORD 3 of B, we can precompute everything up to round 10 of MD5, and compute what the value of the internal 'b' variable of round 52 of MD5 must be to generate the expected hash; this reduces the total number of rounds we compute to 42 (plus a few extra checks that we occasionally do if 'b' happens to be the value we expect, plus redoing the precomputation when we've gone through all possible values of DWORD 3 of B, and we need to try another value for DWORD 1,2,4).

However, such tricks don't come anywhere close to giving you a practical solution. In fact, even if we were to optimize the time to test a value of 'B' to one CPU clock cycle, and ran the test on one billion CPUs, find a value of B that gives the specified hash would take an expected time considerably longer than the age of the universe.

What you would need is to have a cryptographical weakness in MD5 which would allow you to find such a value without doing an exhaustive search. Yes, there are a number of weaknesses known with MD5; there's none that gives you this.