Hot answers tagged

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

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


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


8

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


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


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

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

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


4

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


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


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

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


2

So first we'll assume the end-game is to perform a dictionary attack on the not-yet-known hash. In that case you also have a dictionary. First, store the dictionary it's md5 hashes in a database, with a sort index on the md5 hashes. Now, for each character of the hash: Select an md5 hash starting with what you know so far plus 1 extra character for each ...


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


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

I am not sure if this is what you are looking for, however, the information theoretic capacity of a timing channel, where delays are manipulated, has been defined and analyzed in a number of papers, by using the Shannon formalism of maximizing the common information between the input and output to obtain/bound the capacity. There is a tutorial which can get ...


1

The opcode 15 49 (0F 31 - Intel opcodes are more typically listed in hexidecimal) is the RDTSC instruction; this loads the number of cycles since the last rest into EDX:EAX. By running this function, running some code, and then running this function again, and subtracting the results, you get precisely how long the code takes (in number of CPU cycles).


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

Let's make things slightly more abstract at first. The attacker knows $n$ salts $s_i$. Passwords have $e$ bits of entropy and are hashed to $h_i = H(s_i, p_i)$. The attacker can calculate $2^c$ hashes $H(s_i, p)$ per second and can query some kind of an oracle $2^q$ times per second for the prefix length shared by $H(s_i, p)$ and the target $h_i$. Simplest ...



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