# Tag Info

14

Generally speaking, a lookup-table can be implemented in constant time by doing it as if it was a hardware circuit. Consider a multiplexer: this is a circuit which accepts three inputs a, b and c, and yields one output d which is equal to a if c = 0, to b otherwise (I am talking about single-bit values here). A multiplexer can be used to implement a 1→1 ...

9

The paper explains why. Preventing the OS from interrupting the AES computation is part of Bernstein's proposed method of defense against cache-based timing attacks. Let me sketch the argument for you: The early part of the paper explains that if the time is variable, then it introduces a risk of timing attacks. Sections 3-6 demonstrate that such an ...

9

Timing attacks rely on operations which do not always take the same time to execute, depending on the processed data. For instance, on a typical software platform (say, a PC) implementing SHA-256, all operations are 32-bit additions or rotations or bitwise combinations which take a constant time to execute, regardless of the actual operand values. SHA-256 is ...

9

Just to complement Thomas's reply, here are a couple of papers that do not rely on SIMD registers to implement bitsliced AES: How Far Can We Go on the x64 Processors? (source in appendix) A Fast and Cache-Timing Resistant Implementation of the AES (source code)

6

No, it's not possible to recover the private RSA key; not with a timing attack, not with a debugger, not with any technical means. There isn't enough information on the victim's computer. The timing attack you describe requires timing the decryption operation, which could reveal the decryption key. But the malware isn't ever decrypting anything, it's just ...

6

The attack which you link to, on ECDSA, is related to the following: the signer computes several values $kG$, for random $k$ values chosen uniformly modulo $n$ ($n$ is the size of the subgroup generated by $G$). One such value is generated for each signature. It is important that the selection is uniform: even small biases can be exploited in order to make a ...

5

If an implementation uses a poor PRNG, there will always be vulnerabilities in that implementation. However, if you replace Random for a cryptographically secure PRNG, the method you describe for generating private exponents is fine. In such case the timings will only reveal information about: The public modulus $p$, which may be presumed to be known ...

5

Adding to Thomas's answer: in A depth-16 circuit for the AES S-box, Joan Boyar and Rene Peralta give a compact representation of AES tables as boolean operations, that are useful for a bitslice/SIMD implementation.

4

Yes, timing attacks are relevant to real-world implementations of crypto. Yes, as that paper demonstrates, these attacks can be carried out in real life: real networks are fast enough to allow these attacks. It is also important to understand that some network services do provide timestamps that leak information about how long the operation took on the ...

4

Actually the authors used both OpenSSL 0.9.7 and 1.0.1; they detail the differences between the versions, what changed in the implementations, and what they can do from other VM. They refer to 0.9.7 because that was the version used by Bernstein in 2003 when he worked on cache-timing attacks on AES. This allows to highlight how much (or how little) the ...

3

Elliptic Curves over binary fields In naive implementation of Elliptic Curves, either $GF(p)$ or $GF(2^{n})$ will be vulnerable to some timing attacks. The paper you provided is on OpenSSL's implementation of EC with $GF(2^{n})$. This implementation uses Montgomery's ladder scalar multiplication, which is in fact very good for making sure that most of the ...

2

If I recall correctly the idea is to deduce key bits via the uneven S_BOX lookup timings. Since the time for a lookup varies widly depending wether or not a given variable is in cache or not a solution might be to make sure to have all S_BOXes in cache for the entire computation. Unfortunately even if that was possible an interrupt could cause the cache to ...

1

There is vast literature on timing attacks on AES, but to the best of my knowledge no such attack on SHA-2 or any construction that uses SHA-2 (e.g., HMAC-SHA256).

1

Not something I have a real life example of, just an idea. Certain computationally intensive tasks can be done much faster using memoization. Now if the compiler manages to automatically use memoization for some piece of code that code might run much faster than what the language notation suggests. In C++, for example, any optimization is allowed as long ...

Only top voted, non community-wiki answers of a minimum length are eligible