Skip to content

Instantly share code, notes, and snippets.

@tarcieri
Last active Dec 20, 2015
Embed
What would you like to do?
A Lamport OTP (a.k.a. hash chain)-based password hashing function
# 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
@CodesInChaos

This comment has been minimized.

Copy link

@CodesInChaos CodesInChaos commented Aug 7, 2013

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 pmem1/2 memory which stores every _pmem1/2_th value. This runs in pmem time and uses pmem1/2 memory for a total cost of pmem3/2.

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

    Combined cost of these machines is ptime_pmem3/2. A defender with a standard computer has cost *ptime_pmem2* instead.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment