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.
