Crystal: Crypto::Subtle.constant_time_compare leaks whether size is equal

[madblobfish]

I looked at the source of Crypto::Subtle.constant_time_compare and the early return jumped into my eyes. This potentially leaks whether the strings are equal length.
If this is wanted then not advertising the method as constant time would be good.

require "benchmark"
require "crypto/subtle"
Benchmark.bm do |x|
  x.report("length equal"){ Crypto::Subtle.constant_time_compare("foo","bar") }
  x.report("length unequal"){ Crypto::Subtle.constant_time_compare("fo","bar") }
end
# returns
#                      user     system      total        real
# length equal     0.000000   0.000000   0.000000 (  0.000088)
# length unequal   0.000000   0.000000   0.000000 (  0.000005)

Best Regards

[RX14]

I would generally distrust anything "constant time" that is run through an optimiser.

[madblobfish]

It gives at least the impression of constant time runtime which I think is bad, what if some user of crystal depends on this feature.
I searched for uses and only found one in Crypto::Bcrypt::Password#== which compares hashes so this seems fine.

@RX14 true, is there something one could do in this case? I'd love to see a constant_time keyword for methods which fails the build when something is not constant time (after being optimized).

[RX14]

@madblobfish that isn't really feasible, considering that sometimes even assembly hand-crafted by experts is affected by the internals of different CPU architectures.

[ysbaddaden]

I looked at the libsodium equivalent function (sodium_memcmp) and both buffers must have the same length, by design. Since we accept slices/strings, they may both have a different length.

I think we should enhance the documentation to state that both arguments must have the exact same size. Maybe we should raise too, instead of returning false?

[madblobfish]

I thought some more about Crypto::Bcrypt::Password#== and got to the point that for hash functions the change in the output should be as large a possible for even small input changes.
This makes constant time comparing obsolete (There is no information gained from early finishing the compare, as long as the hash function is strong).
So the method could also be removed if not needed any more (I don't know if there are other plans for this function).

[ysbaddaden]

Huh... no? AFAIK comparing hashes for Bcrypt and similar code, requires a constant time compare function. Otherwise, this is an attack vector.

Can you point us to any literature that would say otherwise?

[madblobfish]

I'm happy to try to verify my claim, so I looked at some implementations:

• JBCrypt: constant time
• OpenBSD: constant time
• PasswordStorage: constant time (in multiple languages)
• twin-bcrypt.js: L783 & L805: non constant time
• crypt_blowfish: non constant time (original source)
• bcrypt-ruby: non constant time (see this issue)

OpenBSD does constant time compare. crypt_blowfish is extracted from the Jack The Ripper password cracking software and it makes sense to exit as early as possible there (no security problem).

Additionally I have looked through the original paper and found nothing indicating need for constant time compare. Also I didn't find a reference implementation. What I know is that cryptographic hash functions should exhibit the behaviour of big unpredictable change on small input changes (I derived this property from the pre-image resistance).

My conclusion: when unsure stay with the safer variant. This could protect against successful timing attacks when bcrypt is partly broken. I'm sorry for all the off-topic talk.

Edit: there is a security.stackexchange answer making the same argument as me while being a better explainer.

[ysbaddaden]

Thanks! I found a few sources that claim the same as you too, but still say that constant time compare is a good practice, and since both libsodium and OpenBSD use it, let's keep it :-)

I would still implement my above suggestions: document that the compared strings/slices must be of equal length, and raise if they're not.

[madblobfish]

This was already resolved with #3752 in 2016.

[jhass]

Uh, #3752 was never merged...

[madblobfish]

@jhass Whops I misread the icon :+1: thanks for catching