Ubuntu Manpage: String::Compare::ConstantTime - Timing side-channel protected string compare

Provided by: libstring-compare-constanttime-perl_0.300-1build1_amd64

NAME

       String::Compare::ConstantTime - Timing side-channel protected string compare

SYNOPSIS

           use String::Compare::ConstantTime;
           use Digest::HMAC_SHA1; ## or whatever

           my $hmac_ctx = Digest::HMAC_SHA1->new($key);
           $hmac_ctx->add($data);
           my $digest = $hmac_ctx->digest;

           if (String::Compare::ConstantTime::equals($digest, $candidate_digest)) {
             ## The candidate digest is valid
           }

DESCRIPTION

       This module provides one function, "equals" (not exported by default).

       You should pass this function two strings of the same length. It will return true if they are string-wise
       identical and false otherwise, just like "eq". However, comparing any two differing strings will take a
       fixed amount of time, unlike "eq".

       NOTE: If the lengths of the strings are different, "equals" will return false right away. Also, comparing
       two identical strings will take a different amount of time than comparing two differing strings.

TIMING SIDE-CHANNEL

       Some programs take different amounts of time to run depending on the input values provided to them. When
       untrusted parties control input, they might be able to learn information you might otherwise not want
       them to know. This is called a "timing side-channel".

       Most routines that compare strings (like perl's "eq" and "cmp" and C's "strcmp" and "memcmp") start
       scanning from the start and terminate as soon as they determine the strings won't match. This is good for
       efficiency but bad because it opens a timing side-channel. If one of the strings being compared is a
       secret and the other is controlled by some untrusted party, it is sometimes possible for this untrusted
       party to learn the secret using a timing side-channel.

HMAC

HMACs are "Message Authentication Codes" built on top of cryptographic hashes. The HMAC algorithm
produces digests that are included along with a message in order to verify that whoever created the
message knows a particular secret password, and that this message hasn't been tampered with since.

To verify a candidate digest included with a message, you re-compute the digest using the message and the
secret password. If this computed digest is is the same as the candidate digest then the message is
considered authenticated.

A very common side-channel attack against services that verify unlimited numbers of messages
automatically is to create a forged message and then just send some random junk as the candidate digest.
Continue sending this message and the junk digest, varying the first character in the digest. Repeat many
times. If you find a particular digest that statistically takes a longer time to be rejected than the
other digests, it is probably because this particular digest has the first character correct and the
service's final string comparison is running a little longer.

At this point, you keep this first character fixed and start varying the second character. Repeat until
all the characters are solved or until the amount of remaining possibilities are so small you can brute
force it. At this point, your candidate digest is considered valid and you have forged a message.

Note that this particular attack doesn't allow the attacker to recover the secret input key, but the
attacker can still use the service itself to produce a valid digest for any message.

LOCK-PICKING ANALOGY

       Pin tumbler locks are susceptible to being picked in a similar way to an attacker forging HMAC digests
       using a timing side-channel.

       The most common way to pick cheap pin tumbler locks is to apply torque to the lock cylinder so that the
       pins are pressed against the cylinder. However, because of slight manufacturing discrepancies one
       particular pin will be the widest by a slight margin and will actually be the only pin pressed against
       the cylinder (the cheaper the lock, the higher the manufacturing "tolerances"). The attacker lifts this
       pin until the cylinder gives a little bit, indicating that this pin has been solved and the next widest
       pin is now the one being pressed against the cylinder. This process is repeated until all the pins are
       solved and the lock opens.

       Just like an attacker trying to solve HMAC digests can work on one character at a time, a lock pick can
       work on each pin in isolation. To protect against this, quality locks force all pins to be fixed into
       place before the cylinder rotation can begin just as secure HMAC verifiers force attackers to guess the
       entire digest on each attempt.

AUTHOR

       Doug Hoyte, "<doug@hcsw.org>"

COPYRIGHT & LICENSE

       Copyright 2012 Doug Hoyte.

       This module is licensed under the same terms as perl itself.