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

Provided by: libstring-compare-constanttime-perl_0.321-2build1_amd64

NAME

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

SYNOPSIS

           use String::Compare::ConstantTime;

           if (String::Compare::ConstantTime::equals($secret_data, $user_supplied_data)) {
             ## The strings are eq
           }

       An example with HMACs:

           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. Just like perl's "eq", it
       will return true if they are string-wise identical and false otherwise. However, comparing
       any two differing strings of the same length will take a fixed amount of time. If the
       lengths of the strings are different, "equals" will return false right away.

       NOTE: This does byte-wise comparison of the underlying string storage, meaning that
       comparing strings with non-ASCII data with different states of the internal UTF-8 flag is
       not reliable.  You should always encode your data to bytes before comparing.

TIMING SIDE-CHANNEL

       Some programs take different amounts of time to run depending on the input values provided
       to them. Untrusted parties can sometimes learn information you might not want them to know
       by measuring this time. 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 of the strings 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.

       If the lengths of the strings are different, because "equals" returns false right away the
       size of the secret string may be leaked (but not its contents).

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 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 junk digests that vary by the first
character. 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 slightly longer.

At this point, you keep this first character fixed and start varying the second character
until it is solved. 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 to the HMAC but nevertheless can produce a valid digest for any message given enough
time because the service that validates the HMAC is acting as an "oracle".

NOTE: Although this module protects against a common attack against applications that
store state in browser cookies, it is in no way an endorsement of this practise.

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 traditional 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 be pressed against the cylinder tighter than the others (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 the tightest. 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 be attempted, 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-2018 Doug Hoyte.

       Contributions from Paul Cochrane.

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