Mojo::Util secure_compare still leaks timing information

[robrwo]

• Mojolicious version: 8.63
• Perl version: 5.28.1
• Operating system: Linux 4.15.0-122-generic 124-Ubuntu

Steps to reproduce the behavior

I would expect the cumulative or code to short-circuit comparisons once r is true.

$r |= ord(substr $one, $_) ^ ord(substr $two, $_)

I wrote a rudimentary benchmark:

use strict;
use warnings;

use Benchmark;

sub secure_compare {
  my ($one, $two) = @_;
  return undef if length $one != length $two;
  my $r = 0;
  $r |= ord(substr $one, $_) ^ ord(substr $two, $_) for 0 .. length($one) - 1;
  return $r == 0;
}

timethese( 5_000_000, {
    diff1 => sub { secure_compare("aaaaaaaaaa", "baaaaaaaaa") },
    diff5 => sub { secure_compare("aaaaaaaaaa", "aaaaabaaaa") },
    diff9 => sub { secure_compare("aaaaaaaaaa", "aaaaaaaaab") },
    same  => sub { secure_compare("aaaaaaaaaa", "aaaaaaaaaa") },
});

It seems that the latter a difference occurs in a string, the longer the comparison takes:

Benchmark: timing 5000000 iterations of diff1, diff5, diff9, same...
     diff1:  9 wallclock secs ( 8.50 usr +  0.00 sys =  8.50 CPU) @ 588235.29/s (n=5000000)
     diff5:  9 wallclock secs ( 8.57 usr +  0.00 sys =  8.57 CPU) @ 583430.57/s (n=5000000)
     diff9:  8 wallclock secs ( 8.80 usr +  0.00 sys =  8.80 CPU) @ 568181.82/s (n=5000000)
      same: 10 wallclock secs ( 8.84 usr +  0.00 sys =  8.84 CPU) @ 565610.86/s (n=5000000)

So this does leak information about the strings.

Expected behavior

There should be no difference in the timing.

Actual behavior

The latter a difference occurs in a string, the longer the check takes.

[robrwo]

Note running tests on different machines (different Linux versions) and different versions of Perl, the timings are less consistent, but generally diff1 takes less time than diff5 or diff9 or same.

[robrwo]

Actually, this is bitwise or so it shouldn't short-circuit. Closing this as invalid, although I suspect there's something else going on that leads this to leak information about where the difference is.

[jberger]

Running it locally here I don't get a meaningful difference. I wonder if you happened to have a lucky run. (By this I mean my results weren't ordered at all).

[robrwo]

I've run it many times on numerous machines, Perl 5.22.2, 5.28.1 and 5.30.3. I've found the following: diff1 is consistently less time than all others. Anyhow, I closed this when I realised that the ordering was not as consistent as it first appeared.

Also, because it immediately returns when the two strings do not have equal length, then it is possible to guess how long the string is. (Keep adding a character to string, and time the compare, then look for the comparison that took the most time.)

[jberger]

If the lengths are unequal, you could pad them and run them through the bitwise checker, problem is then unequal length strings will take more time rather than less.

[robrwo]

The purpose of the function is to avoid leaking information about a secret string to an attacker who is using the time it takes for the method to run.

Because the function exits quickly when the string lengths are unequal, it makes it easy to for the attacker to guess how long the secret string is.

[kraih]

If you appended a random length string to both values the problem would be mitigated, no?

[kraih]

Isn't there a standard implementation for the function we can steal?

[jberger]

I don't know who this is but a quick search found this and it seems sane: https://github.com/vadimdemedes/secure-compare/blob/master/index.js

[jberger]

diff --git a/lib/Mojo/Util.pm b/lib/Mojo/Util.pm
index 630607490..4ee82b5e8 100644
--- a/lib/Mojo/Util.pm
+++ b/lib/Mojo/Util.pm
@@ -276,8 +276,8 @@ sub scope_guard { Mojo::Util::_Guard->new(cb => shift) }

 sub secure_compare {
   my ($one, $two) = @_;
-  return undef if length $one != length $two;
-  my $r = 0;
+  my $r = length $one != length $two;
+  $two = $one if $r;
   $r |= ord(substr $one, $_) ^ ord(substr $two, $_) for 0 .. length($one) - 1;
   return $r == 0;
 }

[robrwo]

That looks alright. In the POD you should not that the "secret" should be the second argument.

[robrwo]

I'll create a PR if you'd like.