class OpenKey::KdfBCrypt

BCrypt is a Blowfish based Key Derivation Function (KDF) that exists to convert low entropy human created passwords into a high entropy key that is computationally infeasible to acquire through brute force.

As human generated passwords have a relatively small key space, key derivation functions must be slow to compute with any implementation.

BCrypt offers a cost parameter that determines (via the powers of two) the number of iterations performed.

If the cost parameter is 12, then 4096 iterations (two to the power of 12) will be enacted.

A Cost of 16 is 65,536 iterations

The minimum cost is 4 (16 iterations) and the maximum is 31.

A cost of 16 will result in 2^16 = 65,536 iterations and will slow the derivation time to about a second on a powerful 2020 laptop.

BCrypt Cost Iteration Timings on an Intel i-5 Laptop

The benchmark timings were incredibly consistent and took almost exactly twice as long for every step.

An IBM ThinkPad was used to generate the timings.

Memory RAM ~> 15GiB
Processors ~> Intel(R) Core(TM) i5-7200U CPU @ 2.50GHz

The timing results (for 2 steps) multiplied by four (4).

3.84 seconds for 2^16 (65,536) iterations
0.96 seconds for 2^14 (16,384) iterations
0.24 seconds for 2^12 ( 4,096) iterations
0.06 seconds for 2^10 ( 1,024) iterations

A double digit iteration cost must be provided to avoid an in-built failure trap. The default cost is now 10.

Constants

BCRYPT_ITERATION_INTEGER

The iteration count is determined using the powers of two so if the iteration integer is 12 there will be two to the power of 12 ( 2^12 ) giving 4096 iterations. The minimum number is 4 (16 iterations) and the max is 31.

@example

Configuring 16 into this directive results in
   2^16 = 65,536 iterations

BCrypt Cost Iteration Timings on an Intel i-5 Laptop

The benchmark timings were incredibly consistent and took almost exactly twice as long for every step.

An IBM ThinkPad was used to generate the timings.

Memory RAM ~> 15GiB
Processors ~> Intel(R) Core(TM) i5-7200U CPU @ 2.50GHz

The timing results (for 2 steps) multiplied by four (4).

3.84 seconds for 2^16 (65,536) iterations
0.96 seconds for 2^14 (16,384) iterations
0.24 seconds for 2^12 ( 4,096) iterations
0.06 seconds for 2^10 ( 1,024) iterations

A double digit iteration cost must be provided to avoid an in-built failure trap. The default cost is now 10.

BCRYPT_KEY_EXPORT_BIT_LENGTH

The BCrypt algorithm produces 181 raw binary bits which is just one bit more than a 30 character base64 string. Hence the algorithm puts out 31 characters.

We discard the 31st character because 5 of its 6 bits are 100% predictable. Thus the returned key will contribute 180 bits.

BCRYPT_KEY_LENGTH

The bcrypt algorithm produces a key that is 181 bits in length. The algorithm then converts the binary 181 bits into a (6-bit) Radix64 character.

181 / 6 = 30 remainder 1 (so 31 characters are needed).

BCRYPT_MAX_IN_TEXT_LENGTH

BCrypt key derivation (from text) implementations truncate the first 55 characters of the incoming text.

BCRYPT_OUTPUT_TEXT_PREFIX

BCrypt outputs a single line of text that holds the prefix then the Radix64 encoded salt and finally the Radix64 encoded hash key.

The prefix consists of two sections sandwiched within two dollar $ signs at the extremeties and a third dollar separating them.

The two sections are the

  • BCrypt algorithm version number (2a or 2b) and

  • a power of 2 integer defining the no. of interations

BCRYPT_SALT_LENGTH

The BCrypt algorithm salt string should be 22 characters and may include forward slashes and periods.

Public Class Methods

generate_bcrypt_salt() click to toggle source

Key generators should use this method to create a BCrypt salt string and then call the {generate_key} method passing in the salt together with a human generated password in order to derive a key.

The salt can be persisted and then resubmitted in order to regenerate the same key in the future.

For the BCrypt algorithm this method depends on the constant {BCRYPT_ITERATION_INTEGER} so that two to the power of the integer is the number of iterations.

A generated salt looks like this assuming the algorithm version is 2a and the interation integer is 16.

$2a$16$nkyYKCwljFRtcif6FCXn3e

This method removes the $2a$16$ preamble string and stores only the actual salt string whose length should be 22 characters.

Why do BCrypt salts always end with zero, e, u or period?

Two (2) leftover bits is the short answer.

This is because the salts are a random 16 bytes and must be stored in base64. The 16 bytes equals 128bits which when converted to base64 (6bits per character) results in 21 characters and only two leftover bits.

BCrypt Salt => t4bDqoJlHbb/k7bkt4/1Ku (22 characters)
BCrypt Salt => 9BjuJU67IG9Lz5tYUhOqeO (22 characters)
BCrypt Salt => grz.QREI35585Y3AaCoCTe (22 characters)
BCrypt Salt => zsxrVW2RGIltSu.AoS4E7e (22 characters)
BCrypt Salt => dTlRJZ6ijDDVk2cFoCQHPO (22 characters)
BCrypt Salt => S9B1azH7oD8L3.CQfxxzJO (22 characters)
BCrypt Salt => LoZh.q3NdnTIuOmR6gHJF. (22 characters)
BCrypt Salt => y6DKk23SmgNR863pTZ8nYe (22 characters)
BCrypt Salt => rokdUF6tg6wHV6F0ymKFme (22 characters)
BCrypt Salt => jrDpNgh.0OEIYaxsR7E7d. (22 characters)

Don't forget BCrypt uses Radix64 (from OpenBSD). So the two (2) leftover bits result in 4 possible values which effectively is

a period (.)
a zero   (0)
an e     (e)
or a u   (u)

@return [String]

the salt in a printable format like base64, hex or a string
of ones and zeroes. This salt should be submitted in the exact
same form to the {generate_key} method.
# File lib/keytools/kdf.bcrypt.rb, line 168
def self.generate_bcrypt_salt

  full_bcrypt_salt = BCrypt::Engine.generate_salt( BCRYPT_ITERATION_INTEGER )
  main_bcrypt_salt = full_bcrypt_salt[ BCRYPT_OUTPUT_TEXT_PREFIX.length .. -1 ]
  keep_bcrypt_salt = "#{BCRYPT_ITERATION_INTEGER}#{main_bcrypt_salt}"
  assert_bcrypt_salt( keep_bcrypt_salt )
  return keep_bcrypt_salt

end
generate_key(human_secret, bcrypt_salt) click to toggle source

Key generators should first use the {generate_salt} method to create a BCrypt salt string and then submit it to this method together with a human generated password in order to derive a key.

The salt can be persisted and then resubmitted again to this method in order to regenerate the same key at any time in the future.

Generate a binary key from the bcrypt password derivation function.

This differs from a server side password to hash usage in that we are interested in the 186bit key that bcrypt produces. This method returns this reproducible key for use during symmetric encryption and decryption.

@param human_secret [String]

a robust human generated password with as much entropy as can
be mustered. Remember that 40 characters spread randomly over
the key space of about 90 characters and not relating to any
dictionary word or name is the way to generate a powerful key
that has embedded a near 100% entropy rating.

@param bcrypt_salt [String]

the salt string that has either been recently generated via the
{generate_salt} method or read from a persistence store and
resubmitted here (in the future) to regenerate the same key.

@return [Key]

an {OpenKey::Key} that has been initialized from the 30 RADIX64
character output from the BCrypt algorithm.

The BCrypt algorithm produces 181 raw binary bits which is just
one bit more than a 30 character base64 string. Hence the algorithm
puts out 31 characters.

We discard the 31st character because 5 of its 6 bits are 100%
predictable. Thus the returned key will contribute 180 bits.
# File lib/keytools/kdf.bcrypt.rb, line 215
def self.generate_key human_secret, bcrypt_salt

  iteration_int = bcrypt_salt[ 0 .. 1 ]
  bcrypt_prefix = "$2x$#{iteration_int}$"
  full_salt_str = bcrypt_prefix + bcrypt_salt[ 2 .. -1 ]

  assert_bcrypt_salt( bcrypt_salt )

  hashed_secret = BCrypt::Engine.hash_secret( human_secret, full_salt_str )
  encoded64_key = BCrypt::Password.new( hashed_secret ).to_s
  key_begin_index = BCRYPT_OUTPUT_TEXT_PREFIX.length + BCRYPT_SALT_LENGTH
  radix64_key_str = encoded64_key[ key_begin_index .. -1 ]
  key_length_mesg = "The BCrypt key length should have #{BCRYPT_KEY_LENGTH} characters."
  raise RuntimeError, key_length_mesg unless radix64_key_str.length == BCRYPT_KEY_LENGTH
  chopped_radix64_key = radix64_key_str.chop()

  return Key.from_radix64( chopped_radix64_key )

end

Private Class Methods

assert_bcrypt_salt(the_salt) click to toggle source

— Timings Code


— chopped_radix64_key = NIL — require 'benchmark' — timings = Benchmark.measure {


— – wrapped up code block


— }


— log.info(x) { “BCrypt key generation timings ~> #{timings}” }


# File lib/keytools/kdf.bcrypt.rb, line 254
def self.assert_bcrypt_salt the_salt
  raise RuntimeError, "bcrypt salt not expected to be nil." if the_salt.nil?
  bcrypt_total_length = 2 + BCRYPT_SALT_LENGTH
  salt_length_msg = "BCrypt salt #{the_salt} is #{the_salt.length} and not #{bcrypt_total_length} characters."
  raise RuntimeError, salt_length_msg unless the_salt.length == bcrypt_total_length
end