0
$\begingroup$

I’ve been tinkering with SHA-3 for a little bit, and I have some questions regarding the applicability of cache timing attacks on this particular hash function. The two sub functions that I believe are susceptible to this particular attack are THETA and CHI. I think I can prove that THETA does not run in constant time, depending on the particular method with which the algorithm is implemented, and I believe CHI does not run in constant time either. To prove that statement with CHI would require the addition of break statements in some implementations of that function. Something that I have yet to complete.

Now assuming that the attacker only has access to a static SHA-3 hash output, I doubt that any information can be gained about the input. However assuming the attacker is able to monitor the execution time of the hash function things get more interesting. Although I'm not sure how prevalent this second scenario is in real life. All that would be gained is the total execution time of all 24 rounds of THETA, but would it be possible from this value to determine the execution time of individual rounds of THETA? Or then be able to approximate inputs based on execution time?

Does anyone know of any references/articles related to SHA-3 and cache timing attacks?

$\endgroup$
  • 4
    $\begingroup$ Python is riddled with variable-time everything, including small integer arithmetic. $\endgroup$ – Squeamish Ossifrage Dec 15 '17 at 0:11
  • $\begingroup$ @SqueamishOssifrage SHA-3 is a minefield, $\endgroup$ – Q-Club Dec 15 '17 at 7:15
  • $\begingroup$ @ColinO'Neil Python just isn't the right choice for implementing production crypto primitives. You'll have similar problems with practically all algorithms. In languages with fixed-size integers, SHA-3 will naturally end up with a constant time implementation. $\endgroup$ – CodesInChaos Dec 15 '17 at 12:47
5
$\begingroup$

SHA-3 is not vulnerable to cache timing attack.

Only implementations could be vulnerable to timing attacks.

Also it is to be noted that cache timing attacks relate secret data and cache lines refreshed. This is again implementation dependent and could not be observed through Python script.

$\endgroup$
  • 2
    $\begingroup$ Wasn't potential vulnerability against side channel attacks part of the SHA-3 competition? I mean, there are definitely design decisions on the algo itself that influence how vulnerable an algorithm will be when implemented. $\endgroup$ – Maarten Bodewes Dec 15 '17 at 15:46
  • $\begingroup$ In the case of Keccak, no operations depends on secret, even the 5-bit S-box (Chi) is defined as bit-sliced. $\endgroup$ – Biv Dec 15 '17 at 15:56
  • 4
    $\begingroup$ This is a little misleading. It's true that side channel attacks are, strictly speaking, properties of implementations, not of algorithms—but one of the critical lessons in cryptography design the world has learned in the past decade is that some algorithms naturally invite side channel attacks, like AES, and others do not lead to that temptation without sacrificing performance. SHA-3 does not even invite side channel attacks, except in completely hopeless implementation strategies like Python integers. $\endgroup$ – Squeamish Ossifrage Dec 15 '17 at 16:44
  • 3
    $\begingroup$ A little more to the point: A naive C implementation of AES will leak secrets through cache timing, but a naive C implementation of SHA-3 probably won't, whereas a naive Python implementation of anything will leak like a sieve unless you do everything in extraordinarily carefully crafted floating-point arithmetic or something absurd like that. (I'm saying this not because I think you don't understand it—obviously you're neck deep in modern cryptography design—but because I don't think your answer adequately explains that to the asker.) $\endgroup$ – Squeamish Ossifrage Dec 15 '17 at 16:48
  • 2
    $\begingroup$ @ColinO'Neil Here's the standard reference: cr.yp.to/papers.html#hash127 Although it naturally enables shifts and addition modulo $2^k$ for $k \leq 53$, it does not naturally enable the bitwise operations that SHA-3 uses, so it's not likely to be useful for SHA-3 implementation without obscene contortions. Your time would be far better spent just wrapping a C implementation in Python—or finding one someone else has already made. $\endgroup$ – Squeamish Ossifrage Dec 16 '17 at 2: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.