1
$\begingroup$

As homework I need to find the password of a crackme in ascii-coded binary. We were also given a specific part of the crackme (in the image below), which we will need to use a side channel attack against, most probably a timing attack.

I know that, based on the function given, you can find out the right password length, since the program would take longer to compute when the length is right. I'm just not sure how I would implement the timing attack.

Could somebody please help?

$\endgroup$

closed as off-topic by e-sushi May 16 '17 at 18:59

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Programming questions are off-topic even if you are writing or debugging cryptographic code. Unless your question is specifically about how the cryptographic algorithm or protocol works, you should look into asking on Stack Overflow instead." – e-sushi
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ If the length is wrong it will return early. So you can easily find the password length. Then you have to notice the delay depends on the actual difference between the keys..... $\endgroup$ – Ruggero May 16 '17 at 11:36
  • $\begingroup$ Oh now I see it! But I'm still unsure how to implement a program that looks at the time it takes the crackme to compute and then find out the right password :/ $\endgroup$ – naspar May 16 '17 at 12:07
  • $\begingroup$ Since you ask for >implementation<, I'll vote to close this question as a programming question. $\endgroup$ – axapaxa May 16 '17 at 18:18
  • $\begingroup$ @axapaxa: Asking "how I would implement" something does not necessarily mean "gimme teh codez". While general programming questions (e.g. "my code crashes when I do this, help!") are off-topic here, even if they occur in the context of writing crypto code, questions about side-channel attacks and other such issues that come up when turning a mathematical description of a crypto algorithm into an actual implementation are on-topic, and we even have an implementation tag for them. IMO, this question falls firmly into the latter group, and I've voted to reopen it. $\endgroup$ – Ilmari Karonen May 18 '17 at 11:12
  • 2
    $\begingroup$ @IlmariKaronen Of course you are right, however I won't agree in this case, because all OP said what he wants is "implementation of" (title) and "Could somebody help?". This is far too unclear what he asks for, which to me indicated "gimme teh codez", but even if not, question isn't clear enough to give proper answer IMO. So it's not that I flagged just because it said "implementation", it's lack of any other question. $\endgroup$ – axapaxa May 18 '17 at 11:49
2
$\begingroup$

I wish I had such homeworks when I studied, mine implied pen and papers only, sadly.

You have to get your hands dirty there. This means that you have to code something which will, as said by Ruggero in his comment:

  1. determine the length by trying random password of different lengths and timing the time your program will take to return
  2. determine the actual password thanks to the fact that the time needed by the program to return is a direct function of the edit distance between the actual password and the string you used as input.

The difficult part for 2. is that there is some noise added to the computation because of that random_time variable. This means that the nearer to the actual password you'll get, the more noise you'll obtain.

In order to counter this, however, you may rely on statistical analysis since you may run that program many time with the same input. So you'll have a mean deviation of only 4.5, which means that when you run a few times the same input, you'll get a Gaussian repartition with a mean value equal to roughly 4.5 plus the actual value of the difference between the inputed characters and the actual characters.

This would be the theoretical approach, I guess...

In your case because the usleep will take 0.01 seconds times the differences plus the random_wait... On average, when provided with the valid password, it'll take around 0.045 seconds.

So you may want to try to do so: - determine the length - benchmark the mean time with a all-zero string of that length (running it a few times, like 20-30 times should be good enough given the resolution of the wait time) - benchmark the mean difference to the previous computed mean time when changing only one characters of the input string at a time, do so for each position in the input string - compute the actual password thanks to all of that information, by trying to minimize the edit distance between your input and the actual password. (Eventually this may just allow you to narrow down the range of possible password to an amount which is easily bruteforced... but I think you can manage the noise added by random_time easily thanks to only a few trials with the same input and should get the right result.)

Here are a few other thing you may also try to, if you dislike having to wait so long at each execution of your binary:

  • if you have a crackme and you can run it on your device, and can do whatever you want, you may try to tamper with the usleep to get it to simply print its current value (maybe using a custom usleep implementation through a LD_PRELOAD trick ?) and then use the above method.

  • if you cannot tamper with its execution, you may try to count the number of instruction it's running and kill it when it passes a threshold and try with another input, this may be the quickest way to recover the password, instead of using the time it takes, you can use the number of instructions executed. This is possible using for example pintools, they even provide an example of such a counter.

  • more generally, reverse engineering and/or patching the crackme may help you.

PS: In the end, I'm not sure this question is really about cryptography or side-channels... But I don't really know where it may belong to.

$\endgroup$
  • $\begingroup$ Actually, usleep(10) pauses for 10 microseconds, not 10 milliseconds... $\endgroup$ – poncho May 16 '17 at 13:54
  • $\begingroup$ Right, this changes the practicality of the whole timing attack then. Thanks. $\endgroup$ – Lery May 16 '17 at 13:59
  • $\begingroup$ May I ask how you came up with the 4.5? $\endgroup$ – naspar May 17 '17 at 12:16
  • $\begingroup$ It's roughly the mean value of rand() % 10, since the $\mod 10$ restricts it to random values from $0$ to $9$... Roughly because of this. $\endgroup$ – Lery May 17 '17 at 22:43

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