[Cryptography] Newbie cryptoanalysis question

[Jerry Leichter]

> I am auditing some code that I think that is crap and I have to demonstrate it without access to it, it is black box testing.
> 
> The data is something like this and I have ten rows
> 
> Variable  Variable TS                   Signature
> ID1       ID2                              
> 
> 
> 3242424   34      2015-10-31 23:59:59   a1a2b3A4A
> 3242425   34      2015-10-31 23:59:59   123456Aab
> 3242426   34      2015-10-31 23:59:59   abcdefABC
> 
> I bet on that Signature is a function of ID1, ID2 and TS without any additional secret.
> 
> I think that there is a process that could help me deduce that function. Could some one hint me some keywords?
Unless the function is very simple-minded, determining it strictly from a black-box implementation is a very challenging proposition.  There are just so many possible quite simple transformations.

If all you want to prove is that no secret is involved, there's a fairly straightforward procedure:  Take two different instantiations of the same code (which should presumably have different secrets) and show that they produce the same output for different inputs.

If you're not in a position to do that, the notion of a "secret" in the algorithm makes little sense:  The "secret" *is simply part of the algorithm".

If you want to go further:  A good signature should have the property that, on average, flipping an single bit of the input flips about half the bits in the output.  That isn't hard for fairly simple functions to achieve, but it takes a designer with at least a bit of understanding of the situation to decide to try it.  Similarly, runs of increasing values in the input should produce a random collection of increasing/decreasing values in the output.  Other simple transformations of the input - e.g., exchanging pairs of bytes - should similarly result in no obvious patterns of changes in the output.

All of these are heuristic tests.  Again, it isn't particularly difficult to write a function that's completely insecure against anyone who doesn't know the algorithm, but that will pass all these tests.  For example:  Suppose the code is in Java.  Appending all the inputs into a string, adding some constant value to the end, and taking the hash, will *look* quite strong.  (OK, the result is only 32 bits, which is too short.  So generate a couple of different strings with slightly different constants, hash, and combine the results.)

The constant value(s) can vary per installation - perhaps the date and time of installation is already being recorded somewhere, or maybe a license number is available - in which case the result will even appear, from the outside, to be based on a "secret".  Against someone who has no access to the implementation, this would be very difficult to reverse engineer.  Of course, to someone who has access to the compiled code and a Java disassembler, it's at most a few hour's work....
                                                        -- Jerry