39

From man 3 memcmp:

Do not use memcmp() to compare security critical data, such as cryptographic secrets, because the required CPU time depends on the number of equal bytes. Instead, a function that performs comparisons in constant time is required.

Why is that so? My thinking is that if someone has access to the machine that processes this "security critical data," then these secrets are already compromised because that person can extract them from RAM. Or, if that person has no access to the machine, then they cannot accurately measure CPU time anyway.

Michael
  • 2,391
  • 2
  • 19
  • 36
gaazkam
  • 5,607
  • 11
  • 24
  • 37
  • 10
    "if that person has no access to the machine, then they cannot accurately measure CPU time anyway" low privilege processes, untrusted VMs or networked machines in the same LAN can measure time pretty accurately. – CodesInChaos May 30 '17 at 19:56
  • 15
    To elaborate on @CodesInChaos' point, it's very possible to, for example, measure timing differences in calls to `memcmp` from one host to another in AWS. You might think the timing differences are too minuscule to measure given the amount of noise: other VMs running on the same physical host as the target and network traffic between the two hosts being obvious contenders. But all you need in order to filter those sources of noise out is more measurements. – Stephen Touset May 30 '17 at 20:28
  • 2
    It need not even be that close. Side channel attacks across the Internet are entirely possible. The jitter in latency can be compensated for with a bit of statistics. – otakucode May 31 '17 at 09:26
  • because the required CPU time depends on the number of equal bytes. – user253751 Jun 01 '17 at 08:11

3 Answers3

47

Exploiting timing information is one possible attack against things like password authentication systems.

Conceptually memcmp() works by comparing two sets of binary data on a byte-by-byte basis (in reality processors can compare multiple bytes at a time, depending on optimizations, but the same principles below will apply). The function starts at the beginning of the data, compares each byte sequentially, and exits as soon as it finds a difference. If no difference is found then the function returns a code indicating that the data matches.

Because the function returns as soon as it finds a difference, an attacker with a sufficiently accurate clock can deduce secret information. They can induce calls to memcmp() with different inputs and by measuring which inputs take longer they can deduce what a stored secret might be.

Example:

Consider a classical password hashing system. Suppose your password is stored as a secret hash, say for example Ek8fAMjPhBo. (That hash was generated using the DES scheme provided by the Linux crypt() function with a salt of na and a password of secret. Note that this function is insecure and you should not use it in real systems.)

In a strong password system your hash Ek8fAMjPhBo is stored, but your password is not stored. When you are asked to authenticate the system will take your password, hash it, and then compare the two hashes to one another. If the resultant hashes match then you are granted access to the system, if the hashes do not match then your password is rejected. This allows the system to check to see whether or not you know your password without actually storing the password itself.

How an attacker can use timing to attack this system:

In order to attack this system an adversary really just needs to figure out what password hashes to the stored hash. Normally the stored hash is kept secret, but the adversary can use timing information to deduce what the stored hash could be. Once the adversary deduces the stored hash it is vulnerable to much faster and off-line rainbow table attacks, as well as circumventing on-line security measures like password retry limits.

The password system above has to compare a candidate hash against the stored hash in order to function properly. Suppose it takes 10 nanoseconds to compare each byte of the candidate hash to the secret stored hash. If no bytes match (one comparison) then memcmp() will take about 10ns. If one byte matches (two comparisons) then memcmp() will take about 20ns. Your attacker generates a few passwords and runs them through the system, recording how long each one takes. Suppose the first few hash comparisons take about 10ns each and then return, indicating that none of the bytes of the candidate hash match the stored hash. After a few tries one of the hash comparisons takes 20ns- which indicates that the first byte of the candidate hash matches the stored hash. In the example above this indicates that the attacker has deduced that the first byte of the hash Ek8fAMjPhBo is E.

Hashes by design have the property that you can't predict what hash will correspond to what password, so for example this does not tell the attacker that the password starts with s. However, the attacker could have a large table of pre-computed hashes (a rainbow table) so they can look up other passwords that hash to a string starting with E. After they try enough hashes they'll eventually get an input that causes memcmp() to take 30ns, which indicates that the first two bytes match, and they have deduced that the first two bytes of the hash are Ek. They repeat this process over and over until they deduce all or most of the hash. At that point they either know the password or can brute force it with a traditional rainbow table attack.

This is a little hypothetical, but you can find lots of practical information about timing attacks elsewhere on the net, for example:

https://research.kudelskisecurity.com/2013/12/13/timing-attacks-part-1/

David
  • 1,386
  • 8
  • 8
  • 1
    The thing I've never understood about timing attacks is, how are they even possible at all? We're necessarily talking about an attack over a network (because if the attacker's running on his own hardware he can choose his own implementation of the hash algorithm) so wouldn't random variations in network latency drown out the minuscule differences in timing so thoroughly that the signal-to-noise ratio is effectively zero? – Mason Wheeler May 30 '17 at 20:27
  • 22
    Random noise can always be removed by having very accurate timers and simply taking more measurements. Researchers have demonstrated successful timing attacks between hosts in the same datacenter (think AWS EC2). – Stephen Touset May 30 '17 at 20:30
  • 7
    Attacks aren't necessarily running over a network. I can get remote access to a server and run stuff there locally, for example on a shared Linux server I could time the execution of the "su" command. – David May 30 '17 at 20:44
  • Comments are not for extended discussion; this conversation has been [moved to chat](http://chat.stackexchange.com/rooms/59707/discussion-on-answer-by-david-why-should-memcmp-not-be-used-to-compare-security). – Jeff Ferland Jun 01 '17 at 18:22
13

The matter is not really to argue that a side-channel attack is practical in whichever application you have in mind for your system.

A better point to make is that

  1. Side-channel attacks tend to be possible in more situations than most developers will be able to think of offhand.

  2. In any given situation, reliably convincing oneself that there is no opportunity for timing attacks is vastly more work at development time than simply using a secure comparison method as SOP. More work means both more cost and a higher risk of getting it wrong.

Simply put, it's low-hanging fruit. Having a policy of "never use memcmp on security-critical data", is superior to a policy of "okay to use memcmp when that is safe" on almost every parameter I can imagine.

If, extraordinarily, you are in a situation where shaving a fraction of a microsecond of CPU time off each non-matching comparison (which is usually the non-common case in the first place!) will save you enough money that it's worth spending effort on a proper security analysis, then you will have plenty of business documents proving that fact.

(And even so, just reading comics for the time it would take you to do that analysis while you let Moore's Law do the work for you will probably save you those CPU microseconds for you equally well).

hmakholm left over Monica
  • 279
  • 1
  • 8
9

It falls into a category of the side channel attacks (same requirements as for RSA, execution time with private key should be constant). Also it's not necessarily that RAM is compromised, the operations can be executes on TEE (trusted execute environment).

VovCA
  • 291
  • 2
  • 4