Compression function cryptanalysis

A compression function converts a fixed-sized input into a smaller fixed size output. Suppose that one has a large collection of input-output pairs for an unknown compression function.

We can assume the following:

• That the pairs include some collisions.
• We don't know the function, we did not yet do any cryptanalysis to craft these collisions.
• Suppose that we witnessed them during the execution of some protocol to obtain the input-output pairs.

Are there any standard/general techniques for determining an unknown compression function, given the input-output pairs?

Are there any standard/general techniques for determining an unknown compression function, given the input-output pairs?

This appears to fall under the realm of reverse-engineering rather than cryptanalysis. Standard cryptanalyis techniques like linear and differential cryptanlysis usually require you to know the function that you are testing.

Documentation/Source code

It might seem obvious, but the first thing to do would be to look for the documentation/source code for whatever protocol you observed this data from. If the answer is written down somewhere, you want to look for that first, because the other methods are going to take an increasing amount of work and time.

• Search for source code repositories
• If it is a web application, examine the javascript

Try known functions

The second thing would be to try all known functions with the input-output pairs and see if you can find a match. One sign is to look at the output size. You can sometimes guess what hash was used judging by the size of the outputs. The number of such functions is relatively small, so this is probably the easiest/fastest technique.

• This will not work if the function is some obscure, home-rolled construction.
• Since you have many collisions, it probably is some obscure home-rolled construction

Reverse-Engineering/Debugging

If you have access to a compiled program that evaluates the function (but not the source), you can use a program like IDA to look at what it's doing. If you can locate the call to the function, IDA will list the instructions that are performed to evaluate it.

Machine Learning

If you have enough pairs, you could try using some kind of machine learning algorithm. From what I understand, finding (an approximation of) a function when given input-output pairs is something that machine learning can do. It usually requires a very large amount of training data to get useful result. I don't know enough about it to advise any further.

• Training the machine learning program will probably take a lot less time than learning how to configure/design such a machine learning program.
• This doesn't guarantee that your machine learning program will learn the actual function that was used, just some function that happens to work for the input/output pairs that you have.

Brute force

You could try to brute force the algorithm. You would write a program that generates all possible combinations of instructions on a given input. You would need to vary the parameters to the instructions, and try increasing depths.

• Due to the number of combinations of instructions, parameters, and number of words in the state, this will be very, very slow, and you can only hope it will work if the target function is very simple.

Hack the box

Warning: Unless you are being paid to do this by the person who owns the machine in question and it is explicitly in scope, this is illegal.

Find an exploit for the machine that is running the software, then look for the documentation/source code/compiled executable and use one of the first techniques from there.