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?

Improve this question
$\endgroup$
6
  • 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
    Commented Nov 19, 2016 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 ♦
    Commented Nov 19, 2016 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
    Commented Nov 19, 2016 at 12:11
  • $\begingroup$ Isn't that the the four times the average per byte, i.e. the 512 I calculated? $\endgroup$
    – Maarten Bodewes ♦
    Commented Nov 19, 2016 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
    Commented Nov 19, 2016 at 12:45

1 Answer 1

Reset to default
2
$\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).

Improve this answer
$\endgroup$
5
  • $\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 ♦
    Commented Nov 19, 2016 at 12:02
  • $\begingroup$ Why are the following bytes a higher probability, isn't it always 1/256 for each byte? $\endgroup$
    – NoDirection
    Commented Nov 19, 2016 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 ♦
    Commented Nov 19, 2016 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 ♦
    Commented Nov 19, 2016 at 12:23
  • $\begingroup$ Thanks for the tip, happy with your response though, been helpful $\endgroup$
    – NoDirection
    Commented Nov 19, 2016 at 12:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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