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


16

The book Cryptography Engineering devotes part of a chapter to this topic. Overwriting sensitive data with zeroes is a good start, but there are lots of other considerations. If you rely on a language's default object destruction behavior to zero the memory, it's possible for an unexpected error to prematurely halt the program's execution without it ...


16

In comparison against CBC mode and HMAC, GCM mode is quite commonly better alternative. But, I'll go to detail where it neccessarily is not. Just like Richie Frame, I also do not agree that CBC + HMAC is always the best comparison target. I've added few other details. Hope you find them useful. Against CBC and HMAC I'll discuss downsides first. The ...


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


15

Yes, side-channel attacks are practical and a real concern, if the past is indicative of the future. I've been professionally involved with Smart Cards since the mid eighties, and have repeatedly witnessed deployed systems vulnerable to many forms of side-channel attacks; examples: RAM buffer not cleared at reset, readable (with standard command Get ...


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


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


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)


7

A cryptographical algorithm can't be immune or not immune to side channel attacks; this is because a side channel attack attacks the implementation and not the actual algorithm. Any algorithm that uses secret data can be implemented in a way that has side channel attacks, and any algorithm can be implemented in a way that may be resistant (the hard-core ...


7

A common method for constant-time comparison goes $r←0$ for each bit/byte/word $x_i$ and $y_i$ to compare $r←r ∨ (x_i⊕y_i)$   where $∨$ stands for bitwise OR and $⊕$ stands for bitwise XOR all the $x_i$ match the corresponding $y_i$ if and only if $r$ is now $0$ The point is that the duration is independent of the data compared, thus measuring ...


6

I'm not sure which post you're referring to, but one possible source of leakage results from using a variable-bit rate codec. If different sounds compress at different rates, than this will be reflected in the lengths of outgoing encrypted packets. By examining those sequences of lengths, it can sometimes be possible to accurately guess what phrases are ...


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

Actually, those two algorithms are surprisingly close; I'll write both of them up to show how close they are. They both can be written as a combination of three substeps: A := Add( B, C ) This takes the two points B and C, and adds them together (I'll be writing things in additive notation; in RSA, with would be a modular multiplication) A := Double( B ...


5

Because the time that the Extended Euclidean algorithm depends on the inputs (and, in particular, is a complex function of the two, depending on the ratio expressed as a continguous fraction), there may be some leakage there. It occurs to me, however, that there is a very simple countermeasure; assuming that the secret modulus you are inverting is $p$, and ...


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

Timing attacks against a function $f_k$ generally require two things: The attacker might observe the target perform $f_k(x)$ for a large number of sufficiently diversified known inputs $x$. For each $k$, there are inputs $x$ and $x'$ such that $f_k(x)$ and $f_k(x')$ are expected to execute at different speed. Now, let's assume $f_k$ is the private key ...


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

Often people build hardware that contains cryptographic algorithms, and they are worried about what happens if that hardware falls into the hands of an attacker. Historically, there have been several approaches to making it harder for the attacker, often used in some combination: Hardware and cryptographic algorithms specifically chosen or designed to ...


4

Their attack does not recover the private key. Instead, it gives the attacker a way to decrypt an arbitrary ciphertext of the attacker's choosing. (This is not the same thing.) If the attacker has a ciphertext $c$, the attacker can query the hardware device tens of thousands of times and then based upon the responses, deduce what the decryption of $c$ is. ...


4

As @CodesInChaos explains: It might refer to blind signatures. It also might refer to a method to harden (typically) RSA implementations against timing/side-channel attacks, by blinding the data before operating on it. Example: suppose you are writing code to decrypt data, i.e., to compute $y=x^d \bmod n$, given the input $x$. The naive way to do is just ...


4

There exists a case where developers implemented a new version of the GHASH algorithm that used the new PCLMULQDQ instruction found in Intel processors, and a bug in the implementation allowed message forgery. The code change appeared to improve the performance of AES-GCM on newer processors as well as processors with additional cores that do not support ...


4

Here's the next step in the iteration, which should be easy to understand: Let's call the oracle on 2P and 4P: Answer (even,even) means, that $P<N/4$ (this is still easy: Otherwise either 2P or 4P would be greater than N). Answer (even,odd) means $N/4<P<N/2$. (odd,even) means $N/2<P<3N/4$ and (odd,odd) means $3/4N<P<N$. Actually, ...


4

Power Analysis attacks rely on the attacker being able to analyse the power used by the computing device, so such attacks work best on platforms where the attacker can analyse the power drawn by the device with cycle accuracy. This points at smart cards, which: use an external source of power; have very little room for some isolation circuitry which would ...


4

There are two papers on conventional differential cryptanalysis of SEED. The last one penetrates only half of the cipher. Even though there are few third-party cryptanalysis papers, there is no indication that the cipher is weak. Fault attacks are quite irrelevant in the SSL setting. I would be more concerned with BEAST-like attacks, as SEED is a ...


4

A fault injection attack is based on the fact that you have a healthy black box on which you can do queries, but you can mess with the black box, for example flipping random bits. In real life this could for example be a RFID chip which can be messed with using strong electronic fields. Attacks like these are generally: Very sophisticated in theory and ...


4

How did they jump from the spectrogram showing the RSA exponentiation timings straight to the secret bits? Actually, they're jumping to secret bits; however those aren't the secret bits you're thinking of. The bits displayed above are not the actual bits of $p$ and $q$. Instead, those are the bits from the secret exponent; because GnuPG uses CRT (and ...


4

$q$ does not divide $s^e-h(m)$, but $p$ does, so since the gcd must divide both $s^e-h(m)$ and $n$ it's $p$. To be even more explicit, we know that $p$ divides both $s^e-h(m)$ and $n$. The only larger divisor of $n$ that is also divisible by $p$ is $n$ itself, but if $n$ would divide $s^e-h(m)$, then $q$ would also divide $s^e-h(m)$, which we already assumed ...


4

You can (and should) do the reduction in constant time using masking. That is, instead of using the following (non-bitsliced) pseudo-C code to do the reduction: if ((result >> 8) & 1) { /* bit 8 is set: clear it and flip bits 0, 1, 3 and 4 */ result ^= 0x11b; } you can simply do: result ^= 0x11b * ((result >> 8) & 1); ...


4

Can a variable that is not explicitly computed correlate with the power consumption? Yes, and this can happen in several ways. When you say "not computed explicitly", I assume you mean that the computation is performed on a masked value or share instead. That is, the secret inputs (referred to as the key by the paper you link to) themselves do not ...



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