2
\$\begingroup\$

Explanation is in the function. Please point out any egregious errors:

create function api.ConstantTimeCompare (
    @x varbinary(8000) = 0x00
  , @y varbinary(8000) = 0x00
)
/*
    What? Compares two variable length binary strings byte by byte in constant time.

    When? Cryptography.   

    Why? Given the strings 0x1234 and 0x1213 a simple equality comparison will stop processing after
         it hits the first mismatch at byte position 3. An opponent who only knows @x can exploit this
         feature to guess @y by trying thousands of comparisons and gathering statistics on how long
         each one took.

         In other words, assuming that it takes 100 milliseconds to compare at 16 byte string an
         opponent can rely on the fact that string that only takes 15 milliseconds to process is a
         worse guess than ones that take more than 15 milliseconds. A 50 millisecond comparison in
         this scenario means that @x is a 50% match of @y (from byte 1-8).

    How? Set up a loop based on the length of @x and perform a byte by byte XOR. If @result is still 0
         after all iterations then @x is equal to @y. If the comparison is meant to be secure then the
         untrusted string should be @x and the trusted string should be @y.       
 */
returns bit
with schemabinding
as
begin;    
    declare @i int = 0;
    declare @l int = DataLength(@x);
    declare @result int = @l - DataLength(@y);    

    while (@i < @l)    
    begin;
        set @result = ((@result ^ Substring(@x, @i, 1)) ^ Substring(@y, @i, 1));
        set @i = @i + 1;        
    end;

    set @result = case @result when 0 then 1 else 0 end;

    return @result;
end;
\$\endgroup\$
  • \$\begingroup\$ Please don't update the code after receiving answers. It's confusing to read answers that don't match the code. You can ask a new follow up question if you wish, but I would also recommend explaining the what & why. That context is invaluable to reviewers, and there fore you. By leaving it out, you're robbing yourself of good answers. \$\endgroup\$ – RubberDuck Oct 22 '15 at 23:54
4
\$\begingroup\$

The general approach is sound, but the xor-ing is unnecessarily complex and actually causes it to give an incorrect answer in some cases. If I've worked through it correctly, it will report that the empty string is equal to the string with the single byte 1. The simple approach would be to just increment @result when the strings differ at position @i.

There's another concern that I'm not qualified to comment on for T-SQL, but that I know applies to C# or C++: the algorithm that you've specified should be constant-time, but that is before it gets run through any compilers or optimizers. If you switch to an algorithm that increments a counter, it's conceivable that an optimizer would realize that once @result is not zero the return value is 1, defeating your efforts.

\$\endgroup\$
  • \$\begingroup\$ I believe I have addressed all of your concerns regarding accuracy. As for the optimizer: wouldn't the way the loop is written (to depend exclusively on the length of @x) combined with the location of the @result's evaluation prevent any such optimization? Even in a C-style language? \$\endgroup\$ – Kittoes0124 Oct 22 '15 at 19:21
  • \$\begingroup\$ C++ implementations have very broad latitude in the code they are allowed to generate as long as the observable behavior is preserved: stackoverflow.com/questions/15718262/…. It would take a sophisticated optimizer to rewrite a loop like yours to one with an early exit, but I wouldn't say it's impossible. \$\endgroup\$ – Pierre Menard Oct 22 '15 at 20:43
  • \$\begingroup\$ See stackoverflow.com/questions/20448765 for an example of how C# handles this, and daemonology.net/blog/2014-09-04-how-to-zero-a-buffer.html for the challenges in C. \$\endgroup\$ – Pierre Menard Oct 23 '15 at 0:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.