Tag Info

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();...

30

Unfortunately in the absence of documentation from the CPU vendor you can't be 100% sure what algorithms will or will not be constant time. That said, there are certainly rules of thumb that can be used to reduce the risk of problems. Anything that involves branching control flow or conditional execution of code is obviously a problem. Comparison operations ...

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

16

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

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

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

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

12

Note that this excellent answer is belongs to Squeamish Ossifrage that they stopped contribution! I made a copy and paste then made community. Voting this answer doesn't produce anything to, me. If you can, vote them on Infosec. From the code example provided, it is possible to determine the correct password by timing the code when given various inputs. ...

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

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

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

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

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

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

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

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

7

Here's my two cents: A timing-attack uses the time that it takes to execute an algorithm based on different inputs. Take a simpler problem, such as finding if a single character exists in a secret string. In a traditional algorithm, you would iterate over the string, and return a boolean once you find the character. This would take more time the further a ...

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

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