Skip to content

Password hashing

Jump to bottom
Frank Denis edited this page Dec 26, 2018 · 28 revisions

Password hashing

Example: create a master, long-term secret key

uint8_t master_key[hydro_pwhash_MASTERKEYBYTES];
hydro_pwhash_keygen(master_key);

Example: derive a high-entropy key from a password

#define CONTEXT "Examples"
#define OPSLIMIT 10000
#define MEMLIMIT 0
#define THREADS  1
#define PASSWORD "test"
#define PASSWORD_LEN 4

uint8_t derived_key[32];
hydro_pwhash_deterministic(derived_key, sizeof derived_key, PASSWORD, PASSWORD_LEN,
                           CONTEXT, master_key, OPSLIMIT, MEMLIMIT, THREADS);

Example: create a representative of the password, for database storage

uint8_t stored[hydro_pwhash_STOREDBYTES];
hydro_pwhash_create(stored, PASSWORD, PASSWORD_LEN, master_key,
                    OPSLIMIT, MEMLIMIT, THREADS);

Example: verify a password

#define OPSLIMIT_MAX 50000
#define MEMLIMIT_MAX 0
#define THREADS_MAX  1

if (hydro_pwhash_verify(stored, PASSWORD, PASSWORD_LEN, master_key,
                        OPSLIMIT_MAX, MEMLIMIT_MAX, THREADS_MAX) != 0) {
  /* incorrect password */
}

Example: generate a high-entropy, deterministic key from a stored representative

uint8_t derived_key[32];
if (hydro_pwhash_derive_static_key(
      derived_key, sizeof derived_key, stored, PASSWORD, PASSWORD_LEN,
      master_key, OPSLIMIT_MAX, MEMLIMIT_MAX, THREADS_MAX) != 0) {
  /* incorrect password */
} else {
  /* password verification passed; derived_key contains a derived key */
}

Example: reencrypt a stored representative with a new master key

uint8_t new_master_key[hydro_pwhash_MASTERKEYBYTES];
hydro_pwhash_keygen(new_master_key);
if (hydro_pwhash_reencrypt(stored, master_key, new_master_key) != 0) {
  /* master key is incorrect */
} else {
  /* stored has been reencrypted in-place using the new master key */
}

Example: update the parameters of an existing hash

#define OPSLIMIT_NEW (OPSLIMIT * 2)

hydro_pwhash_upgrade(stored, master_key, OPSLIMIT_NEW, MEMLIMIT, THREADS);

Purpose

Secret keys used to encrypt or sign confidential data have to be chosen from a very large keyspace.

However, passwords are usually short, human-generated strings, making dictionary attacks practical.

Password hashing functions derive a high-entropy secret key of any size from a password.

  • The generated key will have the size defined by the application, no matter what the password length is.
  • The same password hashed with same parameters will always produce the same output.
  • The function deriving a key from a password is CPU intensive, to mitigate brute-force attacks by requiring a significant effort to verify each password.

Common use cases:

  • Password storage, or rather: storing what it takes to verify a password without having to store the actual password.
  • Deriving a secret key from a password, for example for disk encryption.

Usage

Master keys

void hydro_pwhash_keygen(uint8_t master_key[hydro_pwhash_MASTERKEYBYTES]);

libhydrogen's password hashing API requires a master key. The main purpose of this key is to encrypt all hashed passwords, along with their parameters.

Hashed passwords and master keys should be stored in different places: hashed passwords are typically stored in a database, whereas the master key can be statically loaded or hardcoded in the application.

If the database ever gets breached, the list of hashed passwords will be completely useless without the master password.

The storage format supports reencryption and algorithm upgrades.

The hydro_pwhash_keygen() function creates a new master key. This operation is usually performed offline. For that feature to be valuable, always use that function to create the key; do not use a password instead.

Deriving a deterministic, high-entropy key from a password

int hydro_pwhash_deterministic(
    uint8_t      *h,      size_t h_len,
    const char   *passwd, size_t passwd_len,
    const char    ctx[hydro_pwhash_CONTEXTBYTES],
    const uint8_t master_key[hydro_pwhash_MASTERKEYBYTES],
    uint64_t opslimit, size_t memlimit, uint8_t threads);

The hydro_pwhash_deterministic() function derives a deterministic high-entropy key of any length (h_len bytes) from a password passwd of length passwd_len bytes, a context ctx, a master key master_key and a set of parameters for the hash function:

  • opslimit is the number of iterations. The higher the number, the slower the function will be, and the more secure the end result will be against brute-force attacks. This should be adjusted according to the hardware, and to application constraints.
  • memlimit is the maximum amount of memory to use. The current function use a fixed amount of memory, and ignores this parameter. It can be unconditionally set to 0.
  • threads is the number of threads. The current function ignores this parameter. It can be unconditionally set to 1.

The resulting key is put into h.

This function can be used to derive a key from a password if no other information has been stored. For example, it can be used to encrypt/decrypt a file using nothing but a password.

Storing and verifying passwords

int hydro_pwhash_create(uint8_t       stored[hydro_pwhash_STOREDBYTES],
                        const char   *passwd, size_t passwd_len,
                        const uint8_t master_key[hydro_pwhash_MASTERKEYBYTES],
                        uint64_t opslimit, size_t memlimit, uint8_t threads);

The hydro_pwhash_create() function computes a fixed-length (hydro_pwhash_STOREDBYTES bytes), hashed, encrypted, authenticated representative of the password passwd of length ``passwd_len`, that can be safely stored in a database.

This representative can be used to later check if a user provided password is likely to be the original one, without ever storing the password in the database.

The function encrypts and authenticates the representative and the parameters using the master key master_key. All passwords can safely be encrypted using the same, long-term master key. Applications can also choose to derive master_key from a master-master key, and a unique user identifier.

The representative includes opslimit, memlimit and threads: these do not have to be stored separately.

Note that the representative is not a string: this is binary data, that must be stored as a blob in a database, or encoded as a string (for example as a hex value or using a safe base64 variant).

int hydro_pwhash_verify(const uint8_t  stored[hydro_pwhash_STOREDBYTES],
                        const char    *passwd, size_t passwd_len,
                        const uint8_t  master_key[hydro_pwhash_MASTERKEYBYTES],
                        uint64_t opslimit_max, size_t memlimit_max, uint8_t threads_max);

The hydro_pwhash_verify() function verifies that the password passwd of length passwd_len bytes is valid for the stored representative stored, decrypted using master_key.

opslimit_max, memlimit_max and threads_max are maximum values, designed to prevent DoS attacks against applications if the input is untrusted. They should be set to the maximum values ever used in the hydro_pwhash_create() function.

If the encoded parameters in the representative exceed these values, the function returns -1.

If the representative cannot be decrypted, the function returns -1 without even trying to hash the password.

If the password doesn't appear to be valid for the stored representative, the function returns -1. If the password passes all the checks, the function returns 0.

Deriving a key from a password and stored data

int hydro_pwhash_derive_static_key(
    uint8_t       *static_key, size_t static_key_len,
    const uint8_t  stored[hydro_pwhash_STOREDBYTES],
    const char    *passwd,     size_t passwd_len,
    const char     ctx[hydro_pwhash_CONTEXTBYTES],
    const uint8_t  master_key[hydro_pwhash_MASTERKEYBYTES],
    uint64_t opslimit_max, size_t memlimit_max, uint8_t threads_max);

The hydro_pwhash_derive_static_key() function verifies that password is valid for the representative. If this is the case, it fills static_key with static_key_len bytes derived from that representative, and returns 0.

If the password doesn't appear to be valid for what was stored, the function returns -1.

This function can be used to derive a deterministic, high-entropy key from a password and user-specific data stored in a database.

Reencryption

int hydro_pwhash_reencrypt(
    uint8_t       stored[hydro_pwhash_STOREDBYTES],
    const uint8_t master_key[hydro_pwhash_MASTERKEYBYTES],
    const uint8_t new_master_key[hydro_pwhash_MASTERKEYBYTES]);

The hydro_pwhash_reencrypt() function reencrypts a representative stored using the current master key master_key and a new master key new_master_key.

It updates stored in-place and returns 0 on success. If the representative couldn't be decrypted using master_key, the function returns -1.

Updating the parameters

If previously passwords become too fast to verify after a hardware upgrade, stored representatives can be upgraded with new parameters without requiring the original passwords.

int hydro_pwhash_upgrade(uint8_t       stored[hydro_pwhash_STOREDBYTES],
                         const uint8_t master_key[hydro_pwhash_MASTERKEYBYTES],
                         uint64_t opslimit, size_t memlimit, uint8_t threads);

The hydro_pwhash_upgrade() function upgrades in-place a previously computed representative stored encrypted using the master key master_key, to the new parameters opslimit, memlimit and threads.

Note that parameters can only be increased. Trying to reduce the value of an existing parameter will not change the original value.

The function returns 0 on success, or -1 if the data couldn't be decrypted using the provided master password.

Constants

#define hydro_pwhash_CONTEXTBYTES 8
#define hydro_pwhash_MASTERKEYBYTES 32
#define hydro_pwhash_STOREDBYTES 128

Algorithm

Constants:

enc_alg = 0x01
hash_alg = 0x01
context = "hydro_pw"
F_RATE = 16

Password stretching:

h := H(context, passwd_len || passwd || salt || hash_alg || threads || memlimit || h_len)
s := F(h ^ 1)
for i in 0..opslimit:
  s[..F_RATE] := i || {0}
  s := F(s)
h := s[F_RATE..]

Encrypted representative format:

params := hash_alg || threads || opslimit || memlimit || salt || h
enc_rep := E(k=master_key, msg_id=enc_alg, context, enc_alg || params)

Notes

If multiple clients can simultaneously log in on a shared server, the computation requirements can exhaust the server's resources. In order to mitigate this, passwords can be pre-hashed on the client. A lower number of iterations on the server will then be acceptable.

Clone this wiki locally