# Tag Info

17

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 ...

16

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 ...

13

I believe that it is for two reasons: Nontable based implementations of AES are possible, but (assuming you don't have AES-NI or something similar) are significantly slower than table based implementations (perhaps $10\times$ to $20\times$ slower) For a lot of uses, timing attacks aren't particularly relevant (as either the attacker can't get the start/...

12

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)

9

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 ...

9

There is no timing attack possible on MD5 as practically implemented on most platforms. That's because MD5 uses only 32-bit addition, 32-bit bitwise boolean operators, and constant rotations/shifts, which exhibit no data-dependent timing for any reasonable implementation, even written without consideration for resistance to timing attacks. There is however ...

9

What makes crypto code vulnerable to timing attacks is data dependent timing variations. Branching according to a round counter, or to the key size, does not create a vulnerability. Most implementations of AES make no branch according to key or data value, and supressing other branches won't help. The main source of data-dependent timing variations in AES ...

8

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 ...

7

Yes, kind of. The encoding does depend on the individual bits so there could very well be timing differences. Note that the differences would be pretty small; encoding a byte is likely much faster than e.g. modular exponentiation. But as even block ciphers are vulnerable it may very well be possible, especially since table lookup may be implemented. The ...

7

The point in the question makes senses, especially if one restricts to portable software implementations. But: Small or moderately large constant-time RAM tables are reasonable, efficient, and (thus) common hardware building blocks. They are often used in DPA-protected DES and AES hardware coprocessors. Thus we can't dismiss key-dependent S-tables in ...

6

Towards the security of the signature scheme, no precaution against timing attack is necessary when verifying an asymmetric signature. That's because there is no secret involved, thus no information leak to fear. However it can happen that the message, or the signature itself, is intended to be secret; a leak by timing dependency (during computation of the ...

6

The obvious way of implementing ChaCha20 involves nothing but additions, fixed rotations, and XORs. All of these are constant time, so the obvious way of implementing ChaCha20 is secure against timing attacks. The main way that ChaCha20 is made faster -- SIMD -- does not change this. On the other hand, the obvious way of implementing AES uses table ...

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.

5

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 ...

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

No, because timing attacks don't really have anything to do with errors. A timing attack means analyzing the time it takes a cryptographic operation to complete leaks secret information. That actually has nothing to do with error messages; it's just as much a timing attack to look at how long it takes the server to decrypt something in a CTR mode (where the ...

5

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 ...

5

So how secure can non-assembly code truly ever be against timing attacks? First of all, let me state that this is a tricky subject. The simplest method is of course to do away with the lookup tables or and other components that are vulnerable to timing attacks. So when a cipher designed, it should require a minimum of vulnerable components. And during ...

4

Will this successfully prevent a timing attack? Strictly speaking you should be checking if openssl_random_pseudo_bytes happens to be returning cryptographically strong numbers or not. If not, an attacker could guess be able to launch a timing attack practically as easily as without the extra HMAC. (Got to love PHP... Even the function name: random "...

4

Actually, Maarten isn't quite correct; in most cases, the counter doesn't have to be updated in constant time (because it's not secret); however in one case it does: GCM with an IV size that's not 12 bytes. The reason the counter needs to be secret in this case is not because how it is used, but how it is generated. It is initialized to $GHASH_H(IV||0^{s+... 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 ... 4 At least for compiled languages it should also be possible to have tools that perform static analysis on machine code, shouldn't it? Indeed, such tools exist. There are companies specialized in this domain which provide this kind of tools (see this datasheet for example). But you should note that an only software tool will not be able to detect all ... 3 Functions often become timing resistant by not using short circuit evaluation. There is conceivably a small performance price to be paid by not using short circuit evaluation. In reality, this is probably not a bottleneck or serious concern. Edit: It also might be possible that libsodiums function is faster anyways. I would have commented with this, but ... 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 ... 2 Good blinding requires good randomness. Randomness is a hard requirement, especially for embedded systems. In a similar vein, the DSA and ECDSA signature algorithms require a strongly random integer (called k) for each signature, and several implementations have failed to use random enough values, with hilarious consequences; the most well-known case is Sony ... 2 No, in the end the private exponent$d$is just a number within$0..N$where$N$is the modulus. It depends on$N$what the chance is that the first bit is one, but in more likely to be valued$0$than$1$(given that it is well distributed, you would expect it to be$0$around$\frac23\$ of the time). If you generate enough private keys you'll even see ...

2

Yes, string algorithms can be vulnerable to timing attacks. A very common example is string comparison. The best performing way to implement it in general is to compare two strings one character (or memory word) at a time and return inequality as soon as they don't match. However, this kind of a routine is vulnerable to timing attacks that can find the (...

2

It will only help to a certain degree. If you want to protect against ciphertext attacks you cannot just add random time. The reason for that is that the random time you add is probably in a range. Or in your case, the period between calls will be in a certain range. This means that if you have a large enough sample set you can figure out the deviation of ...

2

Yes. As a thought experiment, let's not limit this to AES-GCM. Here's a very trivial example: M = {0, 1} (a one bit message) K = {0, 1} (a one bit key) E(m, k) = m xor k However, let's say with this implementation for some reason the timing attack is caused by the computation taking 100x as long if k = 1. Running this encryption only one time will give ...

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