A Lamport OTP (a.k.a. hash chain)-based password hashing function

pchain.rb

# A password hashing function insipred by Lamport OTP (a.k.a. hash chains)
# EXPERIMENTAL! FOR THE LOVE OF GOD DON'T ACTUALLY USE THIS
#
# This scheme tries to be as simple as possible and works by computing a
# Lamport OTP sequence using the supplied hash function, then hashing
# the reverse of the resulting chain.
#
# Inspired by Trevor Perrin's comments that the function should be
# parallelizable so the good guys can benefit from parallelism, the
# compute factor is treated as a parallelism threshhold, in that the
# good guy will be able to compute at least ptime chains in parallel
# (whereas an attacker wants to do a parallel brute force search of the entire
# password space, so increased parallelism benefits them less)
#
# 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

Not a good algorithm. Some issues:

1. SHA-256 is very slow at producing a chain, so it takes a long time until you reach a significant amount of memory. There is a reason why scrypt uses round reduced Salsa.

2. hash.call(salt, chains.join) isn't parallelizable but takes a significant amount of time (A third with SHA-256).

3. Your memory access is predictable, so the usual square-root trade-off breaks it:

   For the first step a machine with pmem^1/2 memory which stores every _pmem^1/2_th value. This runs in pmem time and uses pmem^1/2 memory for a total cost of pmem^3/2.

   For the second step use a machine with _2_pmem^1/2* memory, initialized to the data produced in step 1. Then regenerate pmem^1/2 values for each step in time pmem^1/2 and pmem^1/2 memory. Since there are pmem^1/2 steps, the total time is pmem, and thus the total cost for this step is pmem^3/2.

   Combined cost of these machines is ptime_pmem^3/2. A defender with a standard computer has cost *ptime_pmem²* instead.