3
$\begingroup$

I have a software program running on a piece of hardware. To access a specific functionality it runs a challenge-response-like authentication, that is it generates a numerical 4-digit PIN and expects a 4-digit numerical PIN in response. I'm now looking for whether it is possible to come up with the algorithm that is used to generate the response and if so how.

Right now I have one sample pair (7153 - 9533) to work with. Ideally there would be some utility or a formula that I could apply or tweak here. I'm confident that once I figure out what the underlying algorithm is to convert from one 4 digit challenge to the 4 digit response then I will be able to code me a little utility to always get the response.

Since the response is always a 4 digit number that is generated from another 4 digit number I assume that there is only 10,000 possible codes that relate to the 10,000 possible "seeds" so I don't think this should be very hard for me to reverse engineer or brute force, essentially I'm looking for a direction where to start.

So my question (in short):
How would I approach such a problem and can it even be done at all?

$\endgroup$
3
$\begingroup$

Ideally there would be some utility or a formula that I could apply or tweak here.

I have to say there is no such utility, no such formula. This problem has no solution.

There is 10000! = factorial(10000) different transformations of 4-digit numbers to 4-digit numbers. For instance, your input 7153 and result 9533 can be produced by any of the following functions:

f(x)=(2x+5227) MOD 10000

f(x)=(3x+8074) MOD 10000

f(x)=(x^3+8956) MOD 10000

Knowing a single pair is not sufficient to find out what transformation was used. If they use some simple function, then having more pairs might give (without guarantee) an insight about this function.

$\endgroup$
  • 1
    $\begingroup$ Really really not sure about that ten thousand factorial. If you were deeper devious and cryptographically perverse, (and this is a crypto forum), the output might be format_and truncate[Whirlpool(input || salt)]. $\endgroup$ – Paul Uszak Jun 16 '18 at 13:34
  • 2
    $\begingroup$ @PaulUszak: How many 1:1 mappings of N into N symbols are there? It is factorial(N). Simple math. If it is not 1:1, then as fgrieu said below, it is N^N. This has nothing to do with salt if you understand the math which is the base of cryptography :) $\endgroup$ – mentallurg Jun 16 '18 at 15:18
  • $\begingroup$ So 50% right then? The mappings aren't random though are they? See $ \downarrow $. $\endgroup$ – Paul Uszak Jun 16 '18 at 16:56
3
$\begingroup$

If the number "responded" is an arbitrary function of the number "supplied", there are $10000^{10000}=2^{132877.12\dots}$ possible functions. If it is a reversible function, there are $10000!=2^{118458.14\dots}$ (the problem statement does not allow to tell whether the function is reversible or not).
Note: There could even be some hidden input like the date/time with some tolerance on the verifier side; that's common in One Time Password generators used for banking, but I'll leave it aside.

The question tells us a sample pair. That allows to reduce the above numbers by a factor of $10000=2^{13.29\dots}$, but we still get two to a power well above a hundred thousands, which is hard to imagine. And there's nothing else in the question to chose among these many functions.

Cryptography has constructs for such functions, achieving the goal that, given example "supplied"/"responded" pairs, it is computationally infeasible to predict what's "responded" for a new "supplied" better than trying at random (and, if reversibility holds, making good use that different "supplied" yield different "responded"). This impossibility holds even when knowing the principle used to construct the function (a basic assumption in modern cryptography is that the only unknown is the key). These constructs are Pseudo-Random Functions or Pseudo-Random Permutations built per the principles of Format-Preserving Encryption.

For example, even is we knew that the function is $n\mapsto\operatorname{HMAC-MD5}(\text{key},n)\bmod10000$, with a 16-byte key hidden in the software, we would be unable to predict anything useful; or to recognize that from $n\mapsto\operatorname{HMAC-SHA-1}(\text{key},n)\bmod10000$.

Therefore, if cryptography is used properly, there is no way to achieve what's asked short of reverse-engineering the "software program" or somewhat access what "generates the response", both of which are off-topic.

$\endgroup$
  • $\begingroup$ Can't agree whatsoever with those numbers. Way too large. Consider, you are not predicting the output number. The choice is in no way a choice of arbitrary function. There is exactly one function they coded that has a known point at 7153/9533. The task is to identify it. There is only a handful of common crytpo hashes, and @mentallurg has already written three others down. And we can test. Plus music programmers are generally not crypto ninjas. And temporal factors can be ruled out as OP doesn't mention them. Odds may be low, but not your low. This is not a key space calculation. $\endgroup$ – Paul Uszak Jun 16 '18 at 16:54

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.