From: Matthew Kerwin <matthew@...>
Date: 2012-05-29T16:54:03+09:00
Subject: Re: does this leak more than the size of the string via timing side channels

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 Kerwin, 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