Hot answers tagged

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


15

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


12

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


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

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

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


8

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


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

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

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

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


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

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

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

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


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

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


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

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

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


2

Two answers to the question: It is about principles and reusability of the cryptographic primitives. Once there are implemented by insecure manner, nothing prevents reusing or misusing the insecure functionality later. TLS validation (during the SSL handshake) involves a secret as well - during the SSL handshake a piece of data is encrypted and sent over ...


1

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


1

No, the counter does not have to be near constant time as the counter does not have to be secret. Block ciphers are generally resistant against known plain text attacks. Generating a key stream doesn't change that. As you already indicated yourself, the IV does not need to be secret. This means that the counter values won't be secret either. That some ...


1

Your questions are 1) is there any research in this area? and 2) is this worth researching? which are still mostly unanswered. Even though there is an accepted answer, i'll take a shot at answering your questions. 1) Yes, there is a lot of research in this area. Here are the talks I'd recommend: Blackhat 2010 https://www.youtube.com/watch?v=idjDiBtu93Y ...



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