string1 = “string”
string2 = “strung”
a = []
if string1.length == string2.length then
string1.length.times do |i|
a += [string1[i] == string2[i]]
end
puts a.inject(:==)
end
I need a way to verify MAC that has timing characteristics that scale
exactly, proportional to the size of the MAC is okay constant rate is
not required. So for a input of two different sizes it can vary but for
the same size it needs to be constant rate. I probably explained that
poorly but hopefully people understand what I am trying to achieve.
One attack against a poorly implemented MAC system worked because python
returned false as soon as the compared strings had a mismatch, and an
attacker could use this information to determine how many correct bytes
they had guessed.
this is what I was using before, but people pointed out it has timing
side channel weakness:
def message_authentic?(ciphertext, key, mac)
OpenSSL::HMAC.digest(OpenSSL::Digest::SHA256.new,
OpenSSL::Digest::SHA256.new(“mac” + key).to_s, ciphertext) == mac
end
yuck the first example has issues I just realized, how about this way:
def message_authentic?(ciphertext, key, presented_mac)
computed_mac = OpenSSL::HMAC.digest(OpenSSL::Digest::SHA256.new,
OpenSSL::Digest::SHA256.new(“mac” + key).to_s, ciphertext)
a = [true]
if computed_mac.length == presented_mac.length then
computed_mac.length.times do |i|
a += [computed_mac[i] == presented_mac[i]]
end
end
mac_verifies = a.inject(:==)
end
and here it is with a bit less baggage
string1 = “string”
string2 = “strung”
a = [true]
if string1.length == string2.length then
string1.length.times do |i|
a += [string1[i] == string2[i]]
end
end
strings_match = a.inject(:==)
puts strings_match
so my question is…would this be safe to use for MAC verification with
Ruby? People have said they don’t think it is possible to do secure MAC
verification in Ruby because of timing leaks, but I can’t see what would
be wrong with this way.
In your example you simply testing two strings for equality, with
exception
that when strings have different lengths you return true.
So your example can be written as this:
def message_authentic?(ciphertext, key, presented_mac)
computed_mac = OpenSSL::HMAC.digest(OpenSSL::Digest::SHA256.new,
OpenSSL::Digest::SHA256.new(“mac” + key).to_s, ciphertext)
computed_mac.length != presented_mac.length or computed_mac ==
presented_mac
end
2012/5/29 rooby shoez [email protected]
Whoops, my mistake – your code behaves exactly like testing string for
equality. So you
can return computed_mac == presented_mac
Anyway I didn’t understand what you’re trying to achieve
2012/5/29 Dmitry S. Kravtsov [email protected]
Yes but I imagine that Ruby returns false on the first mismatch. So
abcdefg
abcd1ab
will return false when it compares f to a
but
1abcef
2acvbf
will return false when it compares 1 to 2, so an attacker who can
measure the time to compare the strings can tell how many correct
characters they guessed.
With Python this compare behavior has apparently led to attacks against
cryptographic systems that use it, and from what I hear it is likely
that Ruby also does not have a cryptographically secure compare method.
The way I attempt to solve this in the above code examples, is by
comparing stings on a byte by byte basis but not returning true or false
until all bytes of each string have been compared. But are there other
timing variations I am missing in the examples? I was told that Ruby
probably can not do timing side channel secure compares of strings, but
I would like to confirm that here. It seems like it would mean any MAC
system implemented with Ruby compares is insecure, and since openssl
doesn’t appear to have the compare part implemented in C, or Ruby has
not wrapped it, there are probably a lot of Ruby MAC systems that are
vulnerable.
On May 29, 2012 7:28 AM, “rooby shoez” [email protected] wrote:
1abcef
2acvbf
will return false when it compares 1 to 2, so it leaks how many correct
bytes an attacker who can measure the time to compare the length has
guessed to the attacker. With Python this compare behavior has
apparently led to attacks against cryptographic systems that use it, and
from what I hear it is likely that Ruby also does not have a
cryptographically secure compare method.
An easy way that works:
Compute a secure hash of both arguments and compare that instead. Timing
the hash won’t reveal any information about the original arguments.
-Martin
Ok, now I get it,
well I may only suggest to use high order functions, and write it like
this:
if computed_mac.length == presented_mac.length then
computed_mac.chars.zip(presented_mac.chars).map {|x,y| x == y}.all?
end
2012/5/29 rooby shoez [email protected]
Er, sorry, I misused the variable names. Obviously I meant
string1.chars… and string2…
On 29 May 2012 17:54, Matthew K. [email protected] wrote:
An alternative could be to transpose the strings from index=>char to
end
There might be a neater way to write it. And it’s much slower, but
should be more securerer.
–
Matthew K., B.Sc (CompSci) (Hons)
http://matthew.kerwin.net.au/
ABN: 59-013-727-651
“You’ll never find a programming language that frees
you from the burden of clarifying your ideas.” - xkcd
–
Matthew K., B.Sc (CompSci) (Hons)
http://matthew.kerwin.net.au/
ABN: 59-013-727-651
“You’ll never find a programming language that frees
you from the burden of clarifying your ideas.” - xkcd
I’d suggest something like:
if lengths match:
if checksums match:
char-by-char comparison
… although I can’t prove that it doesn’t have an equivalent weakness.
The char-by-char is just in case the two strings have the same
checksum, obviously.
An alternative could be to transpose the strings from index=>char to
char=>[indices], then check that each char’s indices are the same for
both strings:
allc = {}
in1 = Hash.new []
in2 = Hash.new []
in1.chars.each_with_index do |c, i|
allc[c] = true
in1[c] ||= []
in1[c] << i
end
in2.chars.each_with_index do |c, i|
allc[c] = true
in2[c] ||= []
in2[c] << i
end
allc.each do |c|
return false if in1[c] != in2[c]
end
true
There might be a neater way to write it. And it’s much slower, but
should be more securerer.
–
Matthew K., B.Sc (CompSci) (Hons)
http://matthew.kerwin.net.au/
ABN: 59-013-727-651
“You’ll never find a programming language that frees
you from the burden of clarifying your ideas.” - xkcd
Thanks for the advice I will probably go with your technique Martin. I
am considering using your technique as well as the original solution I
inquired about. I have a question though, will it work to compare every
character or will it also return false as soon as it detects that one is
not = ?
def message_authentic?(ciphertext, key, mac)
computed_mac =
OpenSSL::Digest::SHA256.new(OpenSSL::HMAC.digest(OpenSSL::Digest::SHA256.new,OpenSSL::Digest::SHA256.new(“mac”
provided_mac = OpenSSL::Digest::SHA256.new(mac)
comparisons = [true]
computed_mac.length.times do |i|
a += [string1[i] == string2[i]]
end
comparisons.inject(:==)
end
Is it at all beneficial to add the second way of comparison as well or
is it just as protected with == after the hash values have been
obtained? And you are pretty confident that this is no vulnerable to
timing side channels ?
2012/5/29 Dmitry S. Kravtsov [email protected]:
Ok, now I get it,
well I may only suggest to use high order functions, and write it like this:
if computed_mac.length == presented_mac.length then
computed_mac.chars.zip(presented_mac.chars).map {|x,y| x == y}.all?
end
all? will be most likely short-circuiting, too, so this has the same
problem as using ==.
There’s two ways I know that security folks have approved of:
-
As it is done in eql_time_cmp in [1].
-
sha = OpenSSL::Digest::SHA256.new
if sha.digest(computed_mac) == sha.digest(presented_mac)
…
end
Although some say that there is even a problem with the first method:
An extremely
optimized (byte code) compiler could figure out what we’re trying to
do there and “help”
us in short-circuiting again. This won’t apply to the second method,
though.
[1]
2012/5/29 rooby shoez [email protected]:
Thanks for the advice I will probably go with your technique Martin. I
am considering using your technique as well as the original solution I
inquired about. I have a question though, will it work to compare every
character or will it also return false as soon as it detects that one is
not = ?
I’m not sure I fully understand, where exactly in your code would that
be?
end
comparisons.inject(:==)
end
Is it at all beneficial to add the second way of comparison as well or
is it just as protected with == after the hash values have been
obtained? And you are pretty confident that this is no vulnerable to
timing side channels ?
Yes, it was also recommended by Dan Boneh during his online
cryptography course, and he can be trusted 
The comparison of the hashes can be done using plain ==, as there’s
nothing to be gained from timing this comparison. Even if you figure
out the hashes by timing them, it’s not possible to get to the original
value from there.
Then again computing the hash itself from the original value is also not
vulnerable because the algorithm for the hash will always take the same
time as it ideally doesn’t care about its underlying input and won’t
take
different code paths for different inputs.
-Martin
How did i missed it?
well then we can replace ‘all?’ with reducing here:
if computed_mac.length == presented_mac.length then
computed_mac.chars.zip(presented_mac.chars).map {|x,y| x ==
y}.reduce(:&)
end
But as everyone mentioned here, simply comparing hashes is better
option,
because good hashes (like SHA) changes significantly when original value
changes slightly.
2012/5/29 Martin Boßlet [email protected]
But if I use the inject to compare array values in addition to using the
hashing, will it make it more secure than just using the hashing with
==? I imagine it might help to hide the hash data, maybe that could
theoretically be beneficial if the attacker manages to break the hash
algorithm.
comparisons.inject(:==)
will it always keep comparing the entire array or will it quit once it
knows all of the objects don’t match? I am still a bit unsure about
inject.
2012/5/29 rooby shoez [email protected]:
But if I use the inject to compare array values in addition to using the
hashing, will it make it more secure than just using the hashing with
==? I imagine it might help to hide the hash data, maybe that could
theoretically be beneficial if the attacker manages to break the hash
algorithm.
It shouldn’t hurt if you do an additional byte-by-byte comparison of the
hashes
to hide their value, but being able to break SHA-2 on completely random
input (which a good MAC would provide) would require alien technology,
at least today