0
$\begingroup$

How long would it take on average to perform a timing attack on HMAC over brute forcing a 32bit tag if the hash is good?

For example, let's take the hash: 79b7cdc3 to calculate the first byte you have to try:

00 000000
01 000000
02 000000
.........   n^256
FE 000000
FF 000000 

total number of guesses and thus 79 would be the 79th guess.

So would the probability of guessing the first byte be, n^256 ?

Or am I going about this wrong?

$\endgroup$
  • 1
    $\begingroup$ This seems to assume that you can detect when the comparison takes longer because the first byte is correct in exactly one attempt. As I understand it, you will need a large amount of attempts to average out any noise (and this is assuming the comparison is not constant-time of course) $\endgroup$ – Thomas Nov 19 '16 at 12:00
  • 1
    $\begingroup$ @Thomas Right you are, it's already in my answer :) NoDirection: first of all, probabilities are always values between 0 and 1 (or a percentage of course, same value times 100). Furthermore, if the probability would be $1\over2^{256}$ it would have the same probability as guessing a full AES-256 key in one go. Instead it is just $1\over{256}$ for the first guess. $\endgroup$ – Maarten Bodewes Nov 19 '16 at 12:04
  • $\begingroup$ Thanks both, probably a stupid question but is there a way to average the total amount of attempts required? Has there been any research into this? $\endgroup$ – NoDirection Nov 19 '16 at 12:11
  • $\begingroup$ Isn't that the the four times the average per byte, i.e. the 512 I calculated? $\endgroup$ – Maarten Bodewes Nov 19 '16 at 12:15
  • $\begingroup$ Sorry I meant with regards to using statistics rather than an oracle being able to tell if you are right or wrong. I assume this greatly depends on the scenario? $\endgroup$ – NoDirection Nov 19 '16 at 12:45
1
$\begingroup$

Yes, if you have a 100% certainty that you can measure each timing then this is the way to go about it, approximately.

You'd have 128 tries on average per byte, so you'd need 128 * 4 = 512 tries, or $2^9$ bits of security to break, that's next to nothing. This is of course an average, the attacker may be lucky or unlucky, the maximum amount of tries would indeed be 256 * 4 = 1024 tries (or 1020 really, as you don't need to test the last byte value due to the power of deduction) and 1 in case of extreme luck.

There are however a few things wrong in your question:

  • timing attacks often require a large number of retries to find just one correct value - timing attacks usually rely on statistic, instead of an oracle that immediately tells you if you're correct or not.

  • you don't need to bother with the exponentiation of 2; there are just a maximum number of tries per byte: 256 (or 255), so the probability of guessing the first byte is just $1/256$, next guesses however will have a higher probability (as the number of untested values goes down).

$\endgroup$
  • $\begingroup$ (I think actually ${127}{1\over2}$ tries, but I haven't had enough coffee yet - and yes, I watched Sherlock Holmes last night) $\endgroup$ – Maarten Bodewes Nov 19 '16 at 12:02
  • $\begingroup$ Why are the following bytes a higher probability, isn't it always 1/256 for each byte? $\endgroup$ – NoDirection Nov 19 '16 at 12:16
  • $\begingroup$ To answer your question: if you've already tried one byte, you've got 255 possibilities left, making for a probility of $1\over255$, then 254... You add them all together and divide by the number of tries. Now the fact that you don't have to guess the last one makes the calculation a bit trickier. I mean if you've already tried 255 values you certainly don't need to test #256, right? The probability would be 1. $\endgroup$ – Maarten Bodewes Nov 19 '16 at 12:22
  • $\begingroup$ Bit of a hint: it's usually better to wait a bit before accepting an answer, it creates a better chance of getting an answer from, e.g. somebody with more coffee in their body. $\endgroup$ – Maarten Bodewes Nov 19 '16 at 12:23
  • $\begingroup$ Thanks for the tip, happy with your response though, been helpful $\endgroup$ – NoDirection Nov 19 '16 at 12:47

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.