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:
- determine the length by trying random password of different lengths and timing the time your program will take to return
- 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.