Creating an md5 hash of a number, string, array, or hash in Ruby

Question

I need to create a signature string for a variable in Ruby, where the variable can be a number, a string, a hash, or an array. The hash values and array elements can also be any of these types.

This string will be used to compare the values in a database (Mongo, in this case).

My first thought was to create an MD5 hash of a JSON encoded value, like so: (body is the variable referred to above)

def createsig(body)    
  Digest::MD5.hexdigest(JSON.generate(body))
end

This nearly works, but JSON.generate does not encode the keys of a hash in the same order each time, so createsig({:a=>'a',:b=>'b'}) does not always equal createsig({:b=>'b',:a=>'a'}).

What is the best way to create a signature string to fit this need?

Note: For the detail oriented among us, I know that you can't JSON.generate() a number or a string. In these cases, I would just call MD5.hexdigest() directly.

Solution 1

I coding up the following pretty quickly and don't have time to really test it here at work, but it ought to do the job. Let me know if you find any issues with it and I'll take a look.

This should properly flatten out and sort the arrays and hashes, and you'd need to have to some pretty strange looking strings for there to be any collisions.

def createsig(body)
  Digest::MD5.hexdigest( sigflat body )
end

def sigflat(body)
  if body.class == Hash
    arr = []
    body.each do |key, value|
      arr << "#{sigflat key}=>#{sigflat value}"
    end
    body = arr
  end
  if body.class == Array
    str = ''
    body.map! do |value|
      sigflat value
    end.sort!.each do |value|
      str << value
    end
  end
  if body.class != String
    body = body.to_s << body.class.to_s
  end
  body
end

> sigflat({:a => {:b => 'b', :c => 'c'}, :d => 'd'}) == sigflat({:d => 'd', :a => {:c => 'c', :b => 'b'}})
=> true

Solution 2

If you could only get a string representation of body and not have the Ruby 1.8 hash come back with different orders from one time to the other, you could reliably hash that string representation. Let's get our hands dirty with some monkey patches:

require 'digest/md5'

class Object
  def md5key
    to_s
  end
end

class Array
  def md5key
    map(&:md5key).join
  end
end

class Hash
  def md5key
    sort.map(&:md5key).join
  end
end

Now any object (of the types mentioned in the question) respond to md5key by returning a reliable key to use for creating a checksum, so:

def createsig(o)
  Digest::MD5.hexdigest(o.md5key)
end

Example:

body = [
  {
    'bar' => [
      345,
      "baz",
    ],
    'qux' => 7,
  },
  "foo",
  123,
]
p body.md5key        # => "bar345bazqux7foo123"
p createsig(body)    # => "3a92036374de88118faf19483fe2572e"

Note: This hash representation does not encode the structure, only the concatenation of the values. Therefore ["a", "b", "c"] will hash the same as ["abc"].

Solution 3

These days there is a formally defined method for canonicalizing JSON, for exactly this reason: https://datatracker.ietf.org/doc/html/draft-rundgren-json-canonicalization-scheme-16

There is a ruby implementation here: https://github.com/dryruby/json-canonicalization

Solution 4

Here's my solution. I walk the data structure and build up a list of pieces that get joined into a single string. In order to ensure that the class types seen affect the hash, I inject a single unicode character that encodes basic type information along the way. (For example, we want ["1", "2", "3"].objsum != [1,2,3].objsum)

I did this as a refinement on Object, it's easily ported to a monkey patch. To use it just require the file and run "using ObjSum".

module ObjSum
  refine Object do
    def objsum
      parts = []
      queue = [self]

      while queue.size > 0
        item = queue.shift

        if item.kind_of?(Hash)
          parts << "\\000"
          item.keys.sort.each do |k| 
            queue << k
            queue << item[k]
          end
        elsif item.kind_of?(Set)
          parts << "\\001"
          item.to_a.sort.each { |i| queue << i }
        elsif item.kind_of?(Enumerable)
          parts << "\\002"
          item.each { |i| queue << i }
        elsif item.kind_of?(Fixnum)
          parts << "\\003"
          parts << item.to_s
        elsif item.kind_of?(Float)
          parts << "\\004"
          parts << item.to_s
        else
          parts << item.to_s
        end
      end

      Digest::MD5.hexdigest(parts.join)
    end
  end
end

Solution 5

Just my 2 cents:

module Ext
  module Hash
    module InstanceMethods
      # Return a string suitable for generating content signature.
      # Signature image does not depend on order of keys.
      #
      #   {:a => 1, :b => 2}.signature_image == {:b => 2, :a => 1}.signature_image                  # => true
      #   {{:a => 1, :b => 2} => 3}.signature_image == {{:b => 2, :a => 1} => 3}.signature_image    # => true
      #   etc.
      #
      # NOTE: Signature images of identical content generated under different versions of Ruby are NOT GUARANTEED to be identical.
      def signature_image
        # Store normalized key-value pairs here.
        ar = []

        each do |k, v|
          ar << [
            k.is_a?(::Hash) ? k.signature_image : [k.class.to_s, k.inspect].join(":"),
            v.is_a?(::Hash) ? v.signature_image : [v.class.to_s, v.inspect].join(":"),
          ]
        end

        ar.sort.inspect
      end
    end
  end
end

class Hash    #:nodoc:
  include Ext::Hash::InstanceMethods
end

View more solutions

Comments

[Alan]

If this will be used for any sort of security purposes, please don't use MD5.

[TelegramSam]

It is not being used for security purposes, but as a simple comparison via string representation. I don't NEED md5, but it's the closest thing I could think of.

[mu is too short]

Do you need these values to be the same within a single process or across processes? You could use x.hash (or a combination of x.hash and x.class) if you don't need them to be consistent across processes.

[TelegramSam]

As mentioned in the question, I will be storing these values in a database for comparison. I need them to be portable between processes. The comparison needs to be made on the value of the variable, not the specific variable itself.

[superluminary]

Just to expand on Alan's comment, use bcrypt for security purposes. One way hashing with a time cost to prevent brute force attacks.

[Joe Edgar]

Just wanted to note that in Ruby 1.9.3+ this should not be a problem. See: stackoverflow.com/questions/31850741/…

[TelegramSam]

The strings are not created equal: ruby-1.9.2-p180 :001 > a = {:aa=>"aa",:bb=>"bb"} => {:aa=>"aa", :bb=>"bb"} ruby-1.9.2-p180 :002 > b = {:bb=>"bb",:aa=>"aa"} => {:bb=>"bb", :aa=>"aa"} ruby-1.9.2-p180 :003 > a.inspect => "{:aa=>\"aa\", :bb=>\"bb\"}" ruby-1.9.2-p180 :004 > b.inspect => "{:bb=>\"bb\", :aa=>\"aa\"}"

[Luke]

Changed answer to address the ordering issue. Let me know if you can think of any holes in it.

[TelegramSam]

This only handles the top Hash, and doesn't address the same issue with Hashes deeper in the structure. Is there a way to get those as well?

[TelegramSam]

as noted above, inspect does not predictably order the hash keys. to_yaml behaves the same way.

[Luke]

I see what you mean. I'll see what I can come up with and edit my answer.

[Luke]

@TelegramSam How does that look?

[Ganymede]

Warning: This mutates the original object graph

[brauliobo]

object#inspect is enough to get a string from any object type