Timing attack with PHP

Question

I'm trying to produce a timing attack in PHP and am using PHP 7.1 with the following script:

<?php
    $find = "hello";
    $length = array_combine(range(1, 10), array_fill(1, 10, 0));
    for ($i = 0; $i < 1000000; $i++) {
        for ($j = 1; $j <= 10; $j++) {
            $testValue = str_repeat('a', $j);
            $start = microtime(true);
            if ($find === $testValue) {
                // Do nothing
            }
            $end = microtime(true);
            $length[$j] += $end - $start;
        }
    }

    arsort($length);
    $length = key($length);
    var_dump($length . " found");

    $found = '';
    $alphabet = array_combine(range('a', 'z'), array_fill(1, 26, 0));
    for ($len = 0; $len < $length; $len++) {
        $currentIteration = $alphabet;
        $filler = str_repeat('a', $length - $len - 1);
        for ($i = 0; $i < 1000000; $i++) {
            foreach ($currentIteration as $letter => $time) {
                $testValue = $found . $letter . $filler;
                $start = microtime(true);
                if ($find === $testValue) {
                    // Do nothing
                }
                $end = microtime(true);
                $currentIteration[$letter] += $end - $start;
            }
        }
        arsort($currentIteration);
        $found .= key($currentIteration);
    }
    var_dump($found);

This is searching for a word with the following constraints

• a-z only
• up to 10 characters

The script finds the length of the word without any issue, but the value of the word never comes back as expected with a timing attack.

Is there something I am doing wrong?

The script loops though lengths, correctly identifies the length. It then loops though each letter (a-z) and checks the speed on these. In theory, 'haaaa' should be slightly slower than 'aaaaa' due to the first letter being a h. It then carries on for each of the five letters.

Running gives something like 'brhas' which is clearly wrong (it's different each time, but always wrong).

Answer 1

Is there something I am doing wrong?

I don't think so. I tried your code and I too, like you and the other people who tried in the comments, get completely random results for the second loop. The first one (the length) is mostly reliable, though not 100% of the times. By the way, the $argv[1] trick suggested didn't really improve the consistency of the results, and honestly I don't really see why it should.

Since I was curious I had a look at the PHP 7.1 source code. The string identity function (zend_is_identical) looks like this:

    case IS_STRING:
        return (Z_STR_P(op1) == Z_STR_P(op2) ||
            (Z_STRLEN_P(op1) == Z_STRLEN_P(op2) &&
             memcmp(Z_STRVAL_P(op1), Z_STRVAL_P(op2), Z_STRLEN_P(op1)) == 0));

Now it's easy to see why the first timing attack on the length works great. If the length is different then memcmp is never called and therefore it returns a lot faster. The difference is easily noticeable, even without too many iterations.

Once you have the length figured out, in your second loop you are basically trying to attack the underlying memcmp. The problem is that the difference in timing highly depends on:

1. the implementation of memcmp
2. the current load and interfering processes
3. the architecture of the machine.

I recommend this article titled "Benchmarking memcmp for timing attacks" for more detailed explanations. They did a much more precise benchmark and still were not able to get a clear noticeable difference in timing. I'm simply going to quote the conclusion of the article:

In conclusion, it highly depends on the circumstances if a memcmp() is subject to a timing attack.