0

What are the possible ways of reversing a key diversification algorithm? This is used to generate a different key for each user.

I know the operands involved (three 4 bytes values) and the result (the key, also 4 bytes long), but I don't know the function that given the operands generates the key.

I have read something about MIFARE key diversification but my case is different and it should be easier:

I know there is no master/secret key involved and that the final key is based only on these 3 values I have so I just miss the arithmetic/logical operations between these values.

Any suggeston?

  • 1
    For that kind of question, you NEED to specify what you're having to work with. Here, you don't specify if you have the binary available, the kind of performance involved, the size of your sample dataset. Also, you need to understand that the function will HAVE to be a reduction: the best you can do is get one valid set of input that gives you a given output but you can't guarantee that it was the same one as initially used. – Stephane Nov 22 '17 at 10:58
  • @Stephane i wrote everything i know: the 3 input values and the output key. I can get more inputs and more corresponding output keys to verify if the function is correct. There is a piece of hardware which i cannot touch that does the computation so I'm blind. Please note that i'm not asking for a solution (that's why I didn't write the values and the key) but for a "way of thinking" in this situations – sguerrini97 Nov 22 '17 at 11:31
  • 1
    the devil is in the details: we have no idea what you're working with so the only answer given what you've revealed is Steffen's "it's impossible". That is because there is an infinity of mapping function between the two key spaces and you have not provided ANY distinguishing factor. So, if you want ideas of how to progress, you really NEED to give sufficient information about what you have that simplify that impossible problem into a possible one. – Stephane Nov 22 '17 at 12:19
2

You are essentially asking if it is easy to reverse engineer the function which is used to map 96 bits (3x4 bytes) input to 32 bit (1x4 bytes) output, without having any further information about this function.

Given of how many different functions exist which do such a mapping I don't think this is possible. You might try to make some guesses for trivial combinations of various hash functions, shifting, XORing or similar but if anything more complex is involved this black box approach with not having any information about the internals will fail.

  • Depending on the speed of the function and assuming a working sample is available, it should be possible to build a full reverse map in a reasonable amount of time reasonable time as well. And given that the output is 32 bits, the resulting map should use up a bit under 400 GB of space which is manageable. – Stephane Nov 22 '17 at 10:16
  • I'm not saying it's easy, i'm looking for some ideas on how to approach this kind of situations. In my particular case I know the hardware that computes the function is very low cost and that the function is very simple (there are some users who successfully found out what the function is). But I'm curious about what a general case approach would be – sguerrini97 Nov 22 '17 at 10:32
  • @Stephane can you suggest any document I can read about building a reverse map? – sguerrini97 Nov 22 '17 at 10:36
  • @sguerrini97 No but the concept is easy: for each possible input, pre-calculate the corresponding output. Store that output and the corresponding input into something you can easily lookup by output. Since your output is limited to 32 bits, the size of your dataset will only be of 96*2^33 bits (or you can simple create one big file of 96*2^32 bits=384GB and store the input in the offset (output)*96 inside the file). You'll have to invest a bit of time into building this file but you will have to do it only once and then reversing your output will be instantaneous – Stephane Nov 22 '17 at 10:53
  • I want to add that Steffen is generally right: outside code decompilation, it is most likely impossible to figure out exactly what algorithm was used – Stephane Nov 22 '17 at 11:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.