79

TL;DR at the bottom. The general ideas of timing attacks are the following: Secret data has influence on timing of software Attacker measures timing Attacker computes influence$^{-1}$ to obtain secret data A Basic weakness: if( secret ) The base of an exploitable code sensitive to a timing attack looks like this: if(secret) { do_A(); } else { do_B();...


28

C comparison operators (strictly relational < <= > >= and equality == !=) yield 1 if the condition is satisfied and 0 if not. On some implementations (compilers) depending on the CPU and sometimes options, this may be implemented by code something like: ; int a = ..., b = ...; ; int x = a > b; move a, r0 compare r0, b ; sometimes subtract ...


25

How to confirm my implementation is constant time? I'm in scala using bouncy castle from Java. This code is not constant time, for no platform is specified. Computing platforms that run in constant time or cycles are the exception. I don't know any device with internet and video currently for sale that does. That's actually contributing to make attacks ...


22

The theory is: don't try to write timing-safe code in JVM-languages or other essentially-interpreted-but-perhaps-sometime-compiled languages; rather Use timing-safe libraries called from the comfort of the JVM-language. Typical example: in a JavaCard that passed Common Criteria evaluation to EAL5+ with AVA_VAN.5 augmentation, it is a safe bet that AES (when ...


18

Writing constant-time cryptographic code is certainly possible in Java or similar languages (e.g. C#). However you have to do it properly. "Constant-time" here means that the observable time-related behaviour does not depend upon secret data. It does not mean that execution time is always the same, but only that the variations are not correlated with the ...


15

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


15

The following example is difficult to exploit in real life, and impossible over a network, but it is simple enough to understand and extrapolate from. Consider a piece of code on a server that checks a MAC for correctness. int compare_mac(unsigned char *mac1, unsigned char *mac2, size_t n) { for (; n--; mac1++, mac2++) { if (*mac1 != *mac2) { ...


14

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


14

Yes, you can; you can use Batcher's Merge Exchange algorithm, paired with a constant time/access compare-and-swap routine (which reads two elements from locations A and B, and writes the larger element into location A and the smaller element into location B). This takes $O(n (\log n)^2)$ time, which makes it not quite as fast as other sort algorithms; ...


13

It mostly has to do with the real world influence of memory caches. A cache is a small amount of fast memory; when you read from memory, the contents are placed in this fast memory (possibly along with adjacent locations); if you read from the location again, you read it from the fast memory (which, of course, proceeds much faster). Hence, if you read a ...


12

Would implementing a function this way run in constant time? This is not an implementation, it is an abstract description of the algorithm. You need an implementation of the function in an actual programming language (or actual hardware) to determine whether or not it executes in constant time. You can't determine this by the description of the abstract ...


11

"Constant-time" is about not leaking information through timing-based side-channels. If you assume that there is no side-channel, then, in particular, there is no side-channel attack. It is nevertheless a rather bold assumption. There is a large variety of possible side-channels, and lab demonstrations of attacks have been done exploiting, among others, ...


10

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


10

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

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


9

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


9

The typical cache line size of modern x86 machines is 64 bytes. This might not be true for all processors. You should retrieve that from system if you want to know that. Ideally you should split data further, in your example you can split it to a bit every 16 bytes, so you will support every machine with cache line size of 16 or bigger (and 16bytes is size ...


9

Not in the least. Forget it. This is written from my experience which is with Java, but all JVM languages will have similar insurmountable problems. There are issues with compile time and run time optimisations that make the byte code almost impossible to predict. And the optimisations majorly and subtly change with each major /minor release. You'd have ...


9

Unless the number of rounds is secret, this does indeed not represent a secret-dependent branch. (If the number of rounds is secret, a chap named Auguste would like to have a word with you. Hope you speak French or Dutch as they were spoken a century ago.)


8

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


8

As the comment you quote notes: On some platforms, including Intel, the [modulo] operation can take a smaller number of cycles if the input is "small". Is that really true, and what does that mean? A bit of Googling led me to the Intel® 64 and IA-32 Architectures Optimization Reference Manual, which in table C-16 lists the throughput of the DIV ...


8

Comparing hashes of strings does not fully defeat timing attacks. For example, if we try to find a password by timing attack of if (strcmp(sha256str(input),sha256str("honey7dew"))) ... where sha256str outputs the SHA-256 hash of its input as a 64-char C string in hexadecimal (4 bits per char), and we initially do not know "honey7dew" but suspect that ...


8

Yes, and no. Adding random jitter makes things harder, but since you cannot force the device to go faster then the minimum number of instructions it would take to perform the computation without interrupts, it would still be possible to perform a timing attack using a large number of traces and statistical tools such as low percentile filters, in a similar ...


8

Constant-time multiplication in software without constant-time multiplier is easy. In C, this working code to compute $x\cdot y$ for 8-bit inputs is typically¹ constant-time: unsigned mul(unsigned char x, unsigned char y) { unsigned r = x, s = x&-(y&1); s += (r += r)&-((y >>= 1)&1); s += (r += r)&-((y >>= 1)&1); s +...


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


7

I just wanted to extend poncho's answer as aspects of this question keep coming up. Generally speaking, you can write constant-time portions of software if you have privileged OS access, but it's not very practical. I also think it's impossible from userspace. Here's the crux of the problem: Everyone wants their computer to be "faster"; however, it doesn'...


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

No, cache timing attack is not the same thing as timing attack. The former is a subcategory of the later. Timing attacks are about inferring information about confidential data (key, plaintext..) from measurement of a computation's execution time. Obviously, timing attacks are only possible when the execution time varies for some reason, and that reason has ...


6

The comparison c == 0, like the rest of your code, will probably run in constant time. However, there's no guarantee that it will, and it's just barely conceivable that there might be some compiler and CPU combination out there where it might not. Of course, that's basically true of any code not written in assembly for a specific CPU model and version. ...


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