We tried backslashing all the functions

Tech

When applications need to transfer cryptographic identifiers into other systems, for example within JSON, they often need to encode them into a safe format. This can however leak information about the secret, unless the encoding is done with a “constant time” algorithm, such as implemented by the paragonie/constant_time_encoding library.

Constant time algorithms are generally slower than the equivalent non-constant time algorithm due to the additional work that needs to be done. Nevertheless we should strive to make them as fast as possible as long as security is maintained.

This blog post discusses the pull request that makes the encoding algorithm quite a bit faster by relying on a simple PHP OPcache optimization.

Pure PHP vs Native Libsodium Implementation

The library is implemented in pure PHP for maximum compatibility across a wide range of web hosting services and PHP versions, which might not necessarily have all optional PHP extensions available. In version 3.1.0, the maintainers, however added optional support for the “sodium” extension, which includes constant time implementations for common encodings. This optional support is implemented by checking for the availability of the sodium extension whenever the encoding function is called and then either using the functions from sodium or the pure PHP implementation.

   // https://github.com/paragonie/constant_time_encoding/blob/master/src/Hex.php
    public static function encode(
        #[\SensitiveParameter]
        string $binString
    ): string {
        if (extension_loaded('sodium')) {
            try {
                return sodium_bin2hex($binString);
            } catch (SodiumException $ex) {
                throw new RangeException($ex->getMessage(), $ex->getCode(), $ex);
            }
        }
        $hex = '';
        $len = Binary::safeStrlen($binString);
        for ($i = 0; $i < $len; ++$i) {
            /** @var array $chunk */
            $chunk = \unpack('C', $binString[$i]);
            $c = $chunk[1] & 0xf;
            $b = $chunk[1] >> 4;

            $hex .= \pack(
                'CC',
                (87 + $b + ((($b - 10) >> 8) & ~38)),
                (87 + $c + ((($c - 10) >> 8) & ~38))
            );
        }
        return $hex;
    }

For a simple test script:


require('vendor/autoload.php');

$secret = random_bytes(16);
$length = 0;
for ($i = 0; $i < 1000000; $i++) {
        $length += strlen(\ParagonIE\ConstantTime\Hex::encode($secret));
}
var_dump($length);

This provided for an impressive 14× improvement in performance with libsodium vs the pure PHP variant:

Benchmark 1: php -d opcache.enable_cli=1 constant_time_encoding_pure_php/test.php
  Time (mean ± σ):      2.012 s ±  0.010 s    [User: 1.993 s, System: 0.018 s]
  Range (min … max):    2.000 s …  2.033 s    10 runs
 
Benchmark 2: php -d opcache.enable_cli=1 constant_time_encoding_sodium/test.php
  Time (mean ± σ):     143.5 ms ±   6.1 ms    [User: 125.6 ms, System: 17.4 ms]
  Range (min … max):   134.5 ms … 158.3 ms    21 runs
 
Summary
  php -d opcache.enable_cli=1 constant_time_encoding_sodium/test.php ran
   14.02 ± 0.60 times faster than php -d opcache.enable_cli=1 constant_time_encoding_pure_php/test.php

Adding Backslashes to All Function Calls

An astute observer might have noticed that some of the functions in the above snippet from the library have a leading backslash, whereas some do not. Adding the backslash is commonly done in security-sensitive code to make sure that a malicious library is not able to “sneak in” fake implementations into the namespace of the security-sensitive library. We should therefore add a leading backslash to the extension_loaded() and sodium_bin2hex() calls as well to make sure we are actually using the Sodium extension and nothing else. We will take a closer look at the following change which is an excerpt from our PR #64.

diff --git a/src/Hex.php b/src/Hex.php
index d4d5259..50f77d1 100644
--- a/src/Hex.php
+++ b/src/Hex.php
@@ -48,9 +48,9 @@ abstract class Hex implements EncoderInterface
         #[\SensitiveParameter]
         string $binString
     ): string {
-        if (extension_loaded('sodium')) {
+        if (\extension_loaded('sodium')) {
             try {
-                return sodium_bin2hex($binString);
+                return \sodium_bin2hex($binString);
             } catch (SodiumException $ex) {
                 throw new RangeException($ex->getMessage(), $ex->getCode(), $ex);
             }

It turns out this also further improves performance to 18× the baseline (1.3× the original sodium implementation):

Benchmark 1: php -d opcache.enable_cli=1 constant_time_encoding_pure_php/test.php
  Time (mean ± σ):      2.130 s ±  0.112 s    [User: 2.115 s, System: 0.014 s]
  Range (min … max):    1.998 s …  2.350 s    10 runs
 
Benchmark 2: php -d opcache.enable_cli=1 constant_time_encoding_sodium/test.php
  Time (mean ± σ):     149.8 ms ±   3.7 ms    [User: 131.4 ms, System: 18.1 ms]
  Range (min … max):   142.9 ms … 157.5 ms    20 runs
 
Benchmark 3: php -d opcache.enable_cli=1 constant_time_encoding_sodium_backslashes/test.php
  Time (mean ± σ):     115.6 ms ±   4.8 ms    [User: 97.5 ms, System: 17.8 ms]
  Range (min … max):   108.2 ms … 129.7 ms    25 runs
 
Summary
  php -d opcache.enable_cli=1 constant_time_encoding_sodium_backslashes/test.php ran
    1.30 ± 0.06 times faster than php -d opcache.enable_cli=1 constant_time_encoding_sodium/test.php
   18.43 ± 1.23 times faster than php -d opcache.enable_cli=1 constant_time_encoding_pure_php/test.php

How the code is optimized by PHP

There are two reasons why this code is much faster:

  1. Without the backslash, PHP will first need to check whether there’s a sodium_bin2hex() in the current namespace before falling back to the global function. This fallback is cached per call and thus only happens once, though.
  2. We wrote about “compiler optimized functions” before, which OPcache evaluates at compile-time. \extension_loaded() is among these functions.

This means that OPcache will replace the extension_loaded() check by just true :

 // Optimization after 1 Iteration
    public static function encode(
        #[\SensitiveParameter]
        string $binString
    ): string {
        if (true) {
            try {
                return \sodium_bin2hex($binString);
            } catch (SodiumException $ex) {
                throw new RangeException($ex->getMessage(), $ex->getCode(), $ex);
            }
        }
        $hex = '';
        $len = Binary::safeStrlen($binString);
        for ($i = 0; $i < $len; ++$i) {
            /** @var array $chunk */
            $chunk = \unpack('C', $binString[$i]);
            $c = $chunk[1] & 0xf;
            $b = $chunk[1] >> 4;

            $hex .= \pack(
                'CC',
                (87 + $b + ((($b - 10) >> 8) & ~38)),
                (87 + $c + ((($c - 10) >> 8) & ~38))
            );
        }
        return $hex;
    }

It will then notice that the if() is useless and remove it:

// Optimization after 2 Iterations
    public static function encode(
        #[\SensitiveParameter]
        string $binString
    ): string {
        try {
            return \sodium_bin2hex($binString);
        } catch (SodiumException $ex) {
            throw new RangeException($ex->getMessage(), $ex->getCode(), $ex);
        }
        $hex = '';
        $len = Binary::safeStrlen($binString);
        for ($i = 0; $i < $len; ++$i) {
            /** @var array $chunk */
            $chunk = \unpack('C', $binString[$i]);
            $c = $chunk[1] & 0xf;
            $b = $chunk[1] >> 4;

            $hex .= \pack(
                'CC',
                (87 + $b + ((($b - 10) >> 8) & ~38)),
                (87 + $c + ((($c - 10) >> 8) & ~38))
            );
        }
        return $hex;
    }

And then the entire code after the try-catch becomes unreachable, since either a return statement will be hit or an Exception will be thrown:

 // Optimization after 3 Iterations
    public static function encode(
        #[\SensitiveParameter]
        string $binString
    ): string {
        try {
            return \sodium_bin2hex($binString);
        } catch (SodiumException $ex) {
            throw new RangeException($ex->getMessage(), $ex->getCode(), $ex);
        }
    }

In the end, the entire pure-PHP implementation is gone and the check whether or not to use it is as well. Instead the Hex::encode() method has become a thin wrapper around \sodium_bin2hex(). This is also visible in the resulting OPcodes.

Before:

ParagonIE\ConstantTime\Hex::encode:
     ; (lines=61, args=1, vars=8, tmps=3)
     ; (after optimizer)
     ; constant_time_encoding_sodium/src/Hex.php:47-73
0000 CV0($binString) = RECV 1
0001 INIT_NS_FCALL_BY_NAME 1 string("ParagonIE\\ConstantTime\\extension_loaded")
0002 SEND_VAL_EX string("sodium") 1
0003 V8 = DO_FCALL_BY_NAME
0004 JMPZ V8 0021
0005 INIT_NS_FCALL_BY_NAME 1 string("ParagonIE\\ConstantTime\\sodium_bin2hex")
0006 SEND_VAR_EX CV0($binString) 1
0007 V8 = DO_FCALL_BY_NAME
0008 VERIFY_RETURN_TYPE V8
0009 RETURN V8
0010 CV1($ex) = CATCH string("SodiumException")
0011 V8 = NEW 3 string("RangeException")
0012 INIT_METHOD_CALL 0 CV1($ex) string("getMessage")
0013 V9 = DO_FCALL
0014 SEND_VAR_NO_REF_EX V9 1
0015 INIT_METHOD_CALL 0 CV1($ex) string("getCode")
0016 V9 = DO_FCALL
0017 SEND_VAR_NO_REF_EX V9 2
0018 SEND_VAR_EX CV1($ex) 3
0019 DO_FCALL
0020 THROW V8
0021 ASSIGN CV2($hex) string("")
0022 INIT_STATIC_METHOD_CALL 1 string("ParagonIE\\ConstantTime\\Binary") string("safeStrlen")
0023 SEND_VAR_EX CV0($binString) 1
0024 V8 = DO_FCALL
0025 ASSIGN CV3($len) V8
0026 ASSIGN CV4($i) int(0)
0027 JMP 0057
0028 INIT_FCALL 2 112 string("unpack")
0029 SEND_VAL string("C") 1
0030 T8 = FETCH_DIM_R CV0($binString) CV4($i)
0031 SEND_VAL T8 2
0032 V8 = DO_ICALL
0033 ASSIGN CV5($chunk) V8
0034 T9 = FETCH_DIM_R CV5($chunk) int(1)
0035 T8 = BW_AND T9 int(15)
0036 ASSIGN CV6($c) T8
0037 T9 = FETCH_DIM_R CV5($chunk) int(1)
0038 T8 = SR T9 int(4)
0039 ASSIGN CV7($b) T8
0040 INIT_FCALL 3 128 string("pack")
0041 SEND_VAL string("CC") 1
0042 T9 = ADD int(87) CV7($b)
0043 T10 = SUB CV7($b) int(10)
0044 T8 = SR T10 int(8)
0045 T10 = BW_AND T8 int(-39)
0046 T8 = ADD T9 T10
0047 SEND_VAL T8 2
0048 T9 = ADD int(87) CV6($c)
0049 T10 = SUB CV6($c) int(10)
0050 T8 = SR T10 int(8)
0051 T10 = BW_AND T8 int(-39)
0052 T8 = ADD T9 T10
0053 SEND_VAL T8 3
0054 V8 = DO_ICALL
0055 ASSIGN_OP (CONCAT) CV2($hex) V8
0056 PRE_INC CV4($i)
0057 T8 = IS_SMALLER CV4($i) CV3($len)
0058 JMPNZ T8 0028
0059 VERIFY_RETURN_TYPE CV2($hex)
0060 RETURN CV2($hex)
LIVE RANGES:
     8: 0008 - 0009 (tmp/var)
     8: 0012 - 0020 (new)
     9: 0043 - 0046 (tmp/var)
     9: 0049 - 0052 (tmp/var)
EXCEPTION TABLE:
     0005, 0010, -, -

After:

ParagonIE\ConstantTime\Hex::encode:
     ; (lines=17, args=1, vars=2, tmps=2)
     ; (after optimizer)
     ; constant_time_encoding_sodium_backslashes/src/Hex.php:47-73
0000 CV0($binString) = RECV 1
0001 INIT_FCALL 1 96 string("sodium_bin2hex")
0002 SEND_VAR CV0($binString) 1
0003 V2 = DO_ICALL
0004 VERIFY_RETURN_TYPE V2
0005 RETURN V2
0006 CV1($ex) = CATCH string("SodiumException")
0007 V2 = NEW 3 string("RangeException")
0008 INIT_METHOD_CALL 0 CV1($ex) string("getMessage")
0009 V3 = DO_FCALL
0010 SEND_VAR_NO_REF_EX V3 1
0011 INIT_METHOD_CALL 0 CV1($ex) string("getCode")
0012 V3 = DO_FCALL
0013 SEND_VAR_NO_REF_EX V3 2
0014 SEND_VAR_EX CV1($ex) 3
0015 DO_FCALL
0016 THROW V2
LIVE RANGES:
     2: 0004 - 0005 (tmp/var)
     2: 0008 - 0016 (new)
EXCEPTION TABLE:
     0001, 0006, -, -

After all the optimizations—both the Sodium support added by the maintainer and the backslashes added by the featured PR #64—, the hexadecimal encoder now only has a roughly 2.1× overhead over the non-constant-time bin2hex() when the Sodium extension is installed. This makes it feasible to err on the side of caution and use the constant time encoder as the default choice, falling back to the insecure alternatives only when best performance is required for a confirmed non-security-sensitive use case.

Benchmark 1: php -d opcache.enable_cli=1 constant_time_encoding_pure_php/test.php
  Time (mean ± σ):      2.010 s ±  0.009 s    [User: 1.993 s, System: 0.016 s]
  Range (min … max):    1.995 s …  2.025 s    10 runs
 
Benchmark 2: php -d opcache.enable_cli=1 constant_time_encoding_sodium/test.php
  Time (mean ± σ):     143.5 ms ±   6.8 ms    [User: 126.6 ms, System: 16.7 ms]
  Range (min … max):   133.4 ms … 159.4 ms    20 runs
 
Benchmark 3: php -d opcache.enable_cli=1 constant_time_encoding_sodium_backslashes/test.php
  Time (mean ± σ):     107.8 ms ±   3.4 ms    [User: 90.5 ms, System: 17.0 ms]
  Range (min … max):   102.6 ms … 115.3 ms    28 runs
 
Benchmark 4: php -d opcache.enable_cli=1 bin2hex/test.php
  Time (mean ± σ):      52.0 ms ±   3.4 ms    [User: 38.1 ms, System: 13.6 ms]
  Range (min … max):    46.6 ms …  63.9 ms    60 runs
 
Summary
  php -d opcache.enable_cli=1 bin2hex/test.php ran
    2.07 ± 0.15 times faster than php -d opcache.enable_cli=1 constant_time_encoding_sodium_backslashes/test.php
    2.76 ± 0.22 times faster than php -d opcache.enable_cli=1 constant_time_encoding_sodium/test.php
   38.62 ± 2.53 times faster than php -d opcache.enable_cli=1 constant_time_encoding_pure_php/test.php

The same optimization is applicable not just to functions, but also to constants. If the constant is provided by an extension and the name is fully-qualified, this allows OPcache to insert the constant’s value at compile time, which then might allow to fully evaluate individual expressions. A PHP version-compatibility check using if (\PHP_VERSION_ID < 80500) { /* … */ } would be an example. The compatibility code within the if() will only exist for PHP versions below PHP 8.5, and the if() will be fully removed at runtime when upgrading to PHP 8.5.

Time to get started with Profiling! With our free trial.

About the author

Tim Düsterhus

I’m a Software Engineer at Tideways, where I work on the PHP extension. My focus is on helping developers gain accurate insights into the runtime behavior of their applications with minimal overhead.

I’m interested in PHP internals and regularly contribute performance improvements to the PHP engine. I enjoy working on problems where small changes can have a measurable impact on the performance and efficiency of PHP applications. Several of my performance optimizations have become part of PHP itself, helping improve the language for developers worldwide.