Openwall GNU/*/Linux - a small security-enhanced Linux distro for servers
[<prev] [next>] [day] [month] [year] [list]
Date: Sun, 3 Jan 2016 17:54:35 -0500
From: Paragon Initiative Enterprises Security Team <security@...agonie.com>
To: oss-security@...ts.openwall.com
Subject: phpecc/phpecc - Timing side-channel in ECDSA signature verification

Happy new year, OSS-Sec!

We've got something we hope you find interesting.

In the process of auditing a PHP JWT library, we took a look at one of
its dependencies, phpecc. https://github.com/phpecc/phpecc

Phpecc describes itself as "Pure PHP Elliptic Curve DSA and DH", and
the JWT library was using it to facilitate ECDSA (over NIST P-256 with
a SHA2-family hash function, of course).

We quickly discovered that the method they were using for signature
verification was not implemented in constant-time.

Our analysis: https://github.com/phpecc/phpecc/issues/113
Our proposed patch: https://github.com/phpecc/phpecc/pull/114

The takeaway, for anyone who ever needs to touch PHP and is thinking
of implementing their own crypto:

> gmp_cmp() is not suitable for cryptography, you want hash_equals()

On a related note, we opened
https://github.com/phpecc/phpecc/issues/115 to address a common
problem in projects that aim to implement cryptography primitives in
PHP: Function overloading.

"What is function overloading?" you might ask. It's one of the
unresolved PHP design warts from a related school of thought that
brought us magic_quotes in PHP 4.

If you set mbstring.func_overload = 2 in your PHP configuration,
strlen() and substr() no longer operate over binary strings (the
default behavior). Instead, they assume that they're being given
Unicode text, which can fit more bytes into each character.

To test this, run:

    var_dump(strlen("\xF0\x9D\x92\xB3"));

Without mbstring.func_overload, you get int(4). With it set to 2, and
your locale set to UTF-8, you get int(1) instead.

"What does this have to do with cryptography?"

A typical hash_equals() polyfill, e.g. for verifying the HMAC in a
cryptography protocol, looks like this:

    function hash_equals($a, $b)
    {
        $d = 0;
        $lenA = strlen($a);
        $lenB = strlen($b);
        if ($lenA !== $lenB) {
            return false;
        }
        for ($i = 0; $i < $lenA; ++$i) {
            $d |= ord($a[$i]) ^ ord($b[$i]);
        }
        return $d === 0;
    }

But with mbstring.func_overload, depending on the structure of the
expected HMAC output, strlen($a) could become 8.

It's much easier to brute force 2^64 possible values (especially if
you know the resulting hash must conform to a a sequence of eight
4-byte UTF-8 characters) than it is to brute force 2^256 possible
values.

The fix is to be explicit about operating over raw binary:

* strlen($x) -> mb_strlen($x, '8bit')
* substr($x, $y, $z) -> mb_substr($x, $y, $z, '8bit')

In sum:

* Don't use gmp_cmp() to compare hashes or signatures
* If you don't explicitly handle function overloading (like our patch
does), you're almost certainly weakening your protocol somewhere
* In fact, you should strongly consider NEVER writing cryptography
primitives in PHP

This last bit of advice is brought to you by one of the few teams
experienced enough to develop PHP cryptography features. We don't even
dare write primitives in PHP. It's a mistake that many make (we're
looking at you, php-gpg).

Further reading:

* https://secure.php.net/manual/en/mbstring.overload.php - Function overloading
* https://github.com/sarciszewski/php-future/blob/master/src/BaseFuture.php
- Mitigation for function overloading
* https://blog.ircmaxell.com/2014/11/its-all-about-time.html - All
about timing attacks
* https://paragonie.com/audit/UGCwpFmaIkQ085l7 - The audit for lcobucci/jwt
* https://github.com/jasonhinkle/php-gpg - An attempt to port GnuPG to PHP

Security Team
Paragon Initiative Enterprises <https://paragonie.com>

Powered by blists - more mailing lists

Your e-mail address:

Please check out the Open Source Software Security Wiki, which is counterpart to this mailing list.

Powered by Openwall GNU/*/Linux - Powered by OpenVZ