lamport.rb

# A password hashing function insipred by Lamport OTP (a.k.a. hash chains)
# Memory factor: length of the Lamport OTP sequence
# Compute factor: number of independent Lamport OTP sequences to compute
# Hash: a keyed hash function
#
# Finally, all of the Lamport OTP chains calculated are concatenated and hashed
# to produce the resulting digest
#
# Just for fun, this has been implemented with threads to demonstrate how easily
# it can be parallelized, much like CTR mode (NOTE: you will need JRuby or Rubinius
# for multicore parallelism to actually work with this example)
#

def phs(hash, pwd, salt, ptime, pmem)
  threads = []
  ptime.times do |n|
    threads << Thread.new do
      # The initial link in the chain is computed by hashing a counter
      link  = hash.call(pwd, n.to_s)
      chain = ""
      pmem.times do
        chain.prepend(link)
        link = hash.call(salt, link)
      end
      
      # return the reversed chain as the thread's value
      chain
    end
  end
  
  # consume the computed chains from all threads
  chains = threads.map(&:value) 
 
  # compute the digest of all the reversed chains concatenated
  digest = hash.call(salt, chains.join)
  
  # return the digest in hex format
  digest.unpack("H*").first 
end
 
require 'openssl'
 
if __FILE__ == $0 # if this file is executed directly...
  hash = lambda { |key, text| OpenSSL::HMAC.digest('sha256', key, text) }
  p phs(hash, "correct horse battery staple", "salt", 256, 256)
end