Speeding up partially known plaintext preimage recovery attack on MD5 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.
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.