12

I came across the cryptography python package, and noticed it had the following about reporting security vulnerabilities:

Examples of things we wouldn’t consider security issues: Using a variable time comparison somewhere, if it’s not possible to articulate any particular program in which this would result in problematic information disclosure.

I thought having no variable time comparisons was one of the things cryptography implementations ensured to be secure. Should this be a goal of all secure cryptography libraries? If not, under what conditions does it not make a difference to security whether or not a constant time comparison is used?

Anders
  • 64,406
  • 24
  • 178
  • 215
curiousgeorge7
  • 121
  • 1
  • 4
  • About "variable time comparison" and "constant time comparison" algorithms: https://www.sjoerdlangkemper.nl/2017/11/08/comparing-securestrings-in-dotnet/ – bolov Apr 15 '19 at 11:40
  • TLS 1.3 dropped support for AES-CBC that was broken and then fixed many times as it was too hard to implement without timing attacks. Here is a paper about how hard it is to do all of the operations properly in constant time https://www.imperialviolet.org/2013/02/04/luckythirteen.html more discussion is at https://security.stackexchange.com/a/207414/45960 – simbo1905 Apr 16 '19 at 06:00

5 Answers5

12

No, they are not always a risk, and indeed, it is impossible to build a practical cryptographic library where every function is constant time.

Take, for instance, a decryption function. In a real-world cryptographic library, it is going to be faster to decrypt a 10 byte message than a 10 gigabyte message. You could theoretically create a library where decryption was constant time for any message of supported size, but that would be absurd, so you have a variable time function that leaks (useless) information about the size of the message being decrypted. One of the specific reasons that this isn't an issue is the assumption that the attacker may have information about the message size is built into the security proofs. Security properties are generally designed to only assume security for messages of a specific size, and since they don't apply to messages of different sizes, there is no impact to the designed security of a system if message size affects function completion timing.

In other cases, timing may be potentially sensitive, but a function may be designed to eliminate any information an attacker could use against the function. Double-MAC'ing is one example of this. Evaluation of a MAC is very definitely a function that is sensitive to timing attacks. In an (for example) encrypt then MAC scheme, you compare a MAC sent with a ciphertext with a MAC freshly computed against the ciphertext, a timing attack could allow an adversary to repeated submit modified ciphertext/MAC combinations and iteratively compute a valid MAC without knowing the correct secret key. If, however, on every comparison you re-MAC the MAC with an ephemeral key and re-compare, it doesn't matter if there are timing issues. The ephemeral key in the second MAC will prevent an adversary from being able to iteratively produce a correct MAC because the new ephemeral key produced for each subsequent evaluation will thwart the effort to discover valid bits.

Xander
  • 35,525
  • 27
  • 113
  • 141
  • 17
    I always assumed that constant time functions were in regards to the content of m, not the length of m. So for example, a comparison should not be faster if the first bit is unequal, than as if everything is identical. –  Apr 15 '19 at 09:21
  • I guess that's a question of context. Generally the size of the message is leaked by other means (e.g. by just counting the bytes sent), so a time constant function for ciphertext with different sizes would be useless. I'd at least indicate explicitly if the size of the ciphertext needs to be obfuscated by any constant time function; most cryptographers would not expect that to be the case. – Maarten Bodewes Apr 15 '19 at 13:15
  • @MechMK1 Exactly... The example does not sound convincing. It would be way more convincing when thinking about compression+encryption and the attacker having control over part of the plaintext since the timing can give an idea of the compression rate and that gives an idea of what is in the rest of the plaintext. – Bakuriu Apr 15 '19 at 21:23
6

Variable time comparisons will leak information. If there is no harm in revealing the data being compared, then there is no issue with using variable time comparisons. If it is crucial that it remain secret, then use constant time comparison.

Some variable time comparisons that are exploitable in theory might be hard to exploit in practice. The quality of timing data that a hacker is able to collect might not be good enough for a timing attack to succeed in certain real world contexts.

For example, a timing attack is more difficult if the software processing secret information is running on hardware that already has inconsistent, unpredictable run times (for identical inputs); even if someone has access to nanosecond precise timing data.

If the secret information also isn't that sensitive and has a short lifespan, then the risk associated with such a timing attack might be too small to worry about.

However, there are ways to work around noisy timing data. Maybe a hacker uses other side channels to supplement timing data. Maybe he sends your server specific requests that makes timing more predictable. And of course he can perform the attack many times and sort of average out the noise.

(As a developer, if you're not sure, then use constant time operations. Don't just assume it's too hard to exploit.)

Things that definitely should not be compared using a variable time algorithm:

  • Secret (symmetric) keys or private (asymmetric) keys
  • Message authentication tags
  • Messages (or hashes of messages) containing secrets
  • Hard-coded (or user configurable) secrets

Examples for which it may or may not matter:

  • Public keys
  • Ciphertext
  • Public IP addresses
  • Public identifiers (excluding personally identifiable information)

Remember that compromising user privacy can be a security issue. (Even if you don't personally think you need to keep some kinds of information private.) Therefore developers should still consider side channel attacks, even when working with data you might not think is that sensitive.

Future Security
  • 1,701
  • 6
  • 13
3

First, cryptography is a broad term and the Python cryptography library does not only include primitives but also X.509 handling etc.

The main question is if the timing issues can be used by an attacker to get secrets or reduce the complexity of the problem and thus the time to get secrets to a value which makes attacks realistic. This means for one that the attacker can measure the time with sufficient granularity in the first place. This is for example usually not the case with complex web applications where variations in network latency and execution time of SQL queries etc will likely make small timing differences in the cryptographic operations impossible to measure from remote. Note that early use of cryptography as in the TLS handshake still might be affected since in this early stage all the other overhead and variations in the application have not much affect yet.

It also means that the attacker can run enough experiments in order to finally extract the secrets. The details depends on how much information is actually leaked from the timing differences but it often practically unfeasible.

And then there might simply be less complex attacks possible. If it is a local application it might be cheaper to just reverse engineer it instead of treating it mostly as a black box. Of course if the application is for example included in some tamper resistant enclosure (like with smartcards) then timing attacks or other side channels (like radiation, variations in used power, ...) might actually be the only way.

In summary: resistance against timing attacks is relevant if a) the timing difference can be measured with sufficient granularity and b) enough experiments can be done and c) no obviously cheaper attacks are possible. Given that especially a) and b) depend a lot on the actual use case it is more important that the cryptographic primitives are resistant, since they might be used in a broad variety of use cases.

Steffen Ullrich
  • 184,332
  • 29
  • 363
  • 424
1

The primary purpose of avoiding variable time comparison was to prevent unintended information disclosure leading to timing based attacks on the application.

For example, take a look at Padding Oracle attack and Time based Blind SQL Injection attack. Clearing up all the variable time comparisons in the program comes at a certain cost which the cryptography python package is trying to avoid since they don't see any information disclosure due to those cases.

It is easy to miss such use cases for security relevant code, so I'd prefer to avoid variable time comparisons.

Maarten Bodewes
  • 4,562
  • 15
  • 29
Karan Bansal
  • 258
  • 1
  • 2
  • 7
  • "Clearing up all the variable time comparisons in the program comes at a certain cost which the cryptography python package is trying to avoid since they don't see any information disclosure due to those cases." Sorry, what is the cryptography python package trying to avoid? Costs? Please clarify that section as it is extremely hard to read. – Maarten Bodewes Apr 15 '19 at 13:21
0

The important thing about leaked information, is to identify what information is leaked, given a certain set of circumstances, and what the attacker would know, and/or control.

For example, lets take password checking. Old, plaintext passwords in the bad old days were often compared one character at a time, by a library with no thought about security. This means that if you got the first letter of the password right, it would take slightly longer than if you got the first letter wrong (since it would take the time to check the second letter). You could try every possible first letter, until you hit the right one, then that first letter plus every possible second letter, and so forth. This way, you could reduce the work needed from 64^6 to 64*6 (assuming 6 symbols from a set of 64 possible symbols).

Even if you hash the password before checking it, you could apply the same to precalculated rainbow tables - find a password with a hash starting with byte 00, if that takes longer to check than a password starting with 01, then you can eliminate all passwords with a hash not starting with 01.

In the example of encryption, if the message being decrypted is supplied by the attacker, then they know how big it is. If it takes twice as long to read a message twice as long, they don't learn anything new from that.

If, on the other hand, it takes longer to decrypt a message if the KEY is different, then the time it took to decrypt a message gives you information about the key, information not otherwise known by the attacker.

AMADANON Inc.
  • 1,481
  • 9
  • 9