4
\$\begingroup\$

The previous version of my function was scalar-valued and employed a WHILE loop to do the comparison, this is SLOW. This new version is tabled-valued and uses a typical tally table in place of the loop. The result is an implementation that is MUCH more efficient while being slightly easier to comprenhend (IMHO).

There is a slight drawback to the new version however: it fails on strings longer than 2GB in size.

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

    When? Cryptography, Gaming.

    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 a 16 byte string, an
         opponent can rely on the fact that strings that take more than 50 milliseconds to process are
         better guesses than ones that take less than 50 milliseconds. Thus, if a comparison takes 50
         milliseconds then @x is a 50% match of @y (from byte positions 1 through 8).

    How? 1. cache the length of @x into [@xLength] (n)
         2. cache a range of integers from 1 to XLength.n into [Iterator] (n)
         3. bail early if the lengths of @x and @y are not equal
         4. XOR nth byte of @x with nth byte of @y
         5. SUM all XOR results, cast result to bit (0 will stay 0, any other number will become 1)
         6. flip the final bit to retain "IsEqual" semantics
 */
returns table
with schemabinding as
return (
    select Cast(Sum(Substring(@x, [Iterator].n, 1) ^ Cast(Substring(@y, [Iterator].n, 1) as tinyint) /* 4 */) as bit /* 5 */) ^ 1 /* 6 */ as b
    from (values(DataLength(@x))) as [@xLength] (n) /* 1 */
    cross apply math.RangeInt(1, [@xLength].n) as [Iterator] /* 2 */
    where Abs([@xLength].n - DataLength(@y)) = 0 /* 3 */
);
\$\endgroup\$
6
  • \$\begingroup\$ Wow, I wish all the SQL code I see at work each day had this good of documentation... Kudos! \$\endgroup\$
    – Phrancis
    Mar 4 '16 at 1:24
  • 1
    \$\begingroup\$ Thank you. When writing up my first implementation/review I had the thought that it would be sinful to explain my code to the community without having any actual documentation to speak of for my future self/peers. Two birds... \$\endgroup\$ Mar 4 '16 at 1:35
  • 1
    \$\begingroup\$ Out of curiosity, under what context would you actually get a string that's > 2 GB? That seems like a really, really large string. I'm assuming at that point it fails because it exceeds the maximum size allowed by SQL Server, right? \$\endgroup\$
    – Phrancis
    Mar 4 '16 at 1:39
  • \$\begingroup\$ Personally, I can't think of a situation where you'd want to use this on strings larger than maximum practical cryto key size (but who am I to judge?). The failure is actually due to two reasons: 1) what you said. 2) my RangeInt func has a maximum size of Int32 which leads to a maximum working space of ~4 billion bytes. \$\endgroup\$ Mar 4 '16 at 1:47
  • 1
    \$\begingroup\$ Doesn't bailing early expose information as well? A dedicated attacker could establish the target length by playing around with that. \$\endgroup\$ Aug 28 '19 at 20:51
2
\$\begingroup\$

As discussed in the comments, this isn't cryptographically secure. The most obvious reason is that the optimizer may choose to do any number of things. The most likely to be concerning are a change in order of operations, or a change in join methodology. If math.RangeInt does any kind of table access (I assume this gives you a numbers table equivalent) then table access type could affect it as well.

Additionally, the bail-early for inequal length exposes information if this assumption isn't met (from comments):

[I] wrote the code under an assumption that doesn't hold in general: that the strings being compared are hashes and thus the length is public knowledge

Ignoring comments regarding cryptographic security, I think the implementation is straightforward and makes sense. To try and address the cryptography I have a few ideas, but I am not an expert and do not endorse rolling your own security and cryptography algorithms/libraries (or using my suggestions, ever, in production).

http://www.moserware.com/2009/09/stick-figure-guide-to-advanced.html (click here to see the image on imgur, otherwise click the image to read the original informative and entertaining comic).

Now that we have that out of the way, I think to even come close to accomplishing this, we would need to do the following:

  1. Stop using a table valued function - we're going to need several hints to ensure that this performs consistently, which we can't add to a TVF and auditing all uses of this would be too difficult. In particular, OPTION( FORCE ORDER, RECOMPILE, MAXDOP 1, OPTIMIZE FOR @x = 0x00, @y = 0x00 ) will be necessary.
  2. Instead of CROSS APPLY math.RangeInt, I think you'll need to join to a materialized numbers table (see below)
  3. You're going to have to remove the length check, and pad the two values to an even 8000 (this is tedious but not hard, and I think should be doable in constant time)

I picked those hints because we want to ensure that it always joins in the order we specify, and doesn't get clever. We want to prohibit parallelism as well so it behaves consistently. Optimizing for those constant values prevents it from getting smart with parameter sniffing. We may not need to recompile; in my gut I think we want it, but I don't have a great reason for this. We may want to set a min/max grant percentage to be the same, so we get consistent behavior based on memory grant. It might also be valuable to use the USE PLAN hint, which lets you hardcode the plan to use. This might be the best way to get a consistent execution.

We're also going to have to add join and table access hints; assuming that dbo.Numbers exists with a clustered index on the first (and only) column, we might be able to do this:

FULL OUTER LOOP JOIN dbo.Numbers WITH ( INDEX(0), FORCESCAN )
  ON Numbers.Number = [@xLength].n

This should run in the same amount of time no matter the length of the string, and the query will always use the same join and table access pattern.

Overall, I think this is a lot of reasons why implementing something cryptographically secure in SQL is a bad idea; I would guess there are a lot of things I'm missing that still prevent this from being "safe".

\$\endgroup\$

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.