Encrypted content with an extensible credential set

Many password managers suffer from a problem in professional, corporate environments, perceived by managers and administrators. Most only support a single set of credentials for read and write access which makes it impossible for employees to choose a unique, secret passphrase themselves while keeping access for higher-ups or service personel. This sometimes (often?) leads to one of two undesirable outcomes: the passwords follow a simple and insecure scheme to make them memorable for all employees, to reduce the need for individually chose credentials; or the passwords are secure, randomly chosen but hard to remember and lead to frequent support tickets for password reset, reducing productivity as well as motivation.

Proposal outline

Our system is built on top of two key components: A password based key derivation function and an key agreement scheme which allows a single party to modify and republish their contribution (private key) such that the agreed-upon key can be changed without the other parties involvement (while the other party can then derive the new key as well from the new public data).

We believe Diffie-Hellman to be one such system, this problem is known as the static Diffie-Hellman problem (added ) .

Structure definitions

We'll use two basic structures as building blocks, one for safely storing the initial, password based entry points and one for consolidating two routes towards the common shared key, reachable from all valid passphrase inputs.

We express these with the same syntax used in many rfc documents, whose description may be found in rfc 5246 - TLS 1.2. The design is also uses primitives and construction principles borrowed from the design of the PwSafe Format v3 and v4, which can be found here and here respectively, although this document can be understood without knowledge about either of those.

Design goals

Explicit goals are as follows:

  • Usable for password managers:

    The proposed algorithm and datastructures should be usable to derive and/or encrypt secrets commonly found in password managers. In particular, one should be able to securely derive a secret master encryption and master authentication key, used for hash based integrity checks.

    Additionally, it must be possible for any user to reencrypt the database under a new master passphrase, such that any information which could have been recovered with the old passphrase does not compromise the security of the new database file. In practice, this implies that it is possible to change all encryption keys without coordination with involvement of other password credentials. For more remarks on the security concerns of this property, see On The Security of Password Manager Database Formats page 12/13.

  • Support for Multiple Independent Master Passwords:

    Multiple parties should be able to create passphrases, such that each is able to recover the shared secret.

  • Supports Multiple Encryption Algorithms:

    Different use cases might require specific algorithms, e.g. for certification. In order to be as universal as possible, the structures should not rely on implementation details but rather on high-level cryptographic security assertions which can be found in several cryptographic algorithms.

  • Platform independent:

    There should not be any hardware requirement, including trusted computing modules or special purpose encryption circuits. This goes hand-in-hand with the support of multiple encryption algorithms.

Password Block

Without further ado, here's the structure of a password block:

/* Future extensions or changes may require different derivation functions */
enum { argon2(1) } PwHashFn;

enum { twofish(1), aes(2), } KeyWrapFn;

struct {
    PwHashFn pw_hash_function;
        /* Equal to argon2, for simplicity */
    Argon2Params pw_hash_params; 
        /* Public parameters */

    KeyWrapFn key_wrap_function;
    opaque wrapped_key[320];
        /* As described in rfc3394, using the selected encryption function
           and the password derived key */
} PasswordBlock;

This construction uses the key wrap function as described for AES in rfc3394. To calculate a block, use the following algorithm:

Function: ConstructPasswordBlock
Input: password P, argon2 parameters A2P, and key wrap function WF
Output: PasswordBlock

1. Calculate Pa, the argon2 hashed password
    Pa = argon2(P, A2P)
2. Choose a random key K, with 256 bit length
3. Calculate the wrapped key K', using the chosen encryption function WF
   (Twofish, AES)
    K' = KW_WF(Pa, K)
4. Output 
    PasswordBlock {
        pw_hash_function := PwHashFn::argon2,
        pw_hash_params := A2P,
        key_wrap_function := WF,
        wrapped_key := K',

To unwrap the key from a PasswordBlock, use the following straightforward algorithm:

Function: UnwrapPasswordBlock
Input: PasswordBlock B, password P
Output: unwrapped key K
1. Calculate Pa, the argon2 hashed password
    Pa = argon2(P, B::pw_hash_params)
2. Lookup the chosen encryption function WF
    WF = B::key_wrap_function
3. Unwrap the key with the specified encryption function
    K' = KU_WF(Pa, P::wrapped_key)
4. Output

Consolidation Block

Each Consolidation Block is based on two prior blocks, each with a corresponding, secret wrapped key. These blocks are called branches a and b. The structure of a Consolidation Block is as follows:

enum { } KeyDerivationFunction;
    /* KDF for deriving the block pre-key from DH key */

struct {
    opaque dh_p<1..2^16-1>; 
    opaque dh_g<1..2^16-1>; 

    KeyWrapFn dh_wrap_function_a;
    opaque dh_private_wrapped_a<64..2^16>;
        /* Private exponent of child branch a (Xa), wrapped with the encryption
           function dh_wrap_function_a and the unwrapped key of branch a */
    KeyWrapFn dh_wrap_function_b;
    KeyWrapFn key_wrap_function;
    opaque dh_private_wrapped_b<64..d^16>;
        /* Private exponent of child branch b (Xb), wrapped with the encryption
           function dh_wrap_function_b and the unwrapped key of branch b */
    opaque dh_public_a<1..2^16-1>;
        /* Public power of child branch a (g^Xa) */
    opaque dh_public_b<1..2^16-1>;
        /* Public power of child branch b (g^Xb) */

    KeyWrapFn key_wrap_function;
    KeyDerivationFunction key_derivation_function;
    opaque wrapped_key[320];
        /* A randomly chosen key, wrapped with the selected encryption function
           and the agreed upon key, (g^(Xa*Xb))*/
} ConsolidationBlock;

The following algorithm is used to construct a Consoliation block:

Function: ConstructConsolidationBlock
Input: Unwrapped key Ka, Unwrapped key Kb, Diffie-Hellman parameters p and g,
       Wrap function choices WFa, WFb, WFc, A key deriviation function DF
Output: ConsolidationBlock

1. Choose, randomly and unrelated, exponents for DH:
    Xa := /* random DH exponent */
    Xb := /* random DH exponent */
2. Calculate the public powers used in DH, and the key wrapped private data,
   using the wrapping function choices and keys, Ka and WFa, Kb and WFb
    Ya := (g^Xa) mod p
    Yb := (g^Xb) mod p
    Xa' := KW_WFa(Ka, Xa)
    Xb' := KW_WFb(Kb, Xb)
3. Calculate the shared Diffie-Hellman key
    DH := (g^(Xa*Xb)) mod p
4. Use the key derivation function DF to derive the encryption key DH' from the
   shared secret DH
    DH' := KDF_DF(DH)
5. Choose, randomly, the consolidation block private key K, with 256 bit length 
6. Calculate the wrapped key K', using the wrapping function choice WFc
    K' := KW_WFc(DH', K)
7. Output
    ConsolidationBlock {
        dh_p := p,
        dh_g := g,
        dh_wrap_function_a := WFa,
        dh_private_wrapped_a := Xa',
        dh_wrap_function_b := WFb,
        dh_private_wrapped_b := Xb',
        dh_public_a := Ya,
        dh_public_b := Yb,
        key_wrap_function := WFc,
        key_derivation_function := DF,
        wrapped_key := K',

(edited )

It is possible to construct a Consolidation Block from for any given pair of Consolidation or Password Blocks, given that you can unwrap one of its keys, either by knowledge of the Passphrase or by recursive knowledge of a consolidation blocks child key. Use the following algorithm (given for knowledge of branch a, but symetric for branch b)

Function: UnwrapConsolidationBlock
Input: Unwrapped key Ka, Consolidation Block B
Output: Unwrapped key K

1. Retrieve the key wrapping function WFa, WFc and the KDF DF
    WFa := B::dh_wrap_function
    WFc := B::key_wrap_function
    DF := B::key_derivation_function
2. Unwrap the private Diffie-Hellman exponent
    Xa := KU_WFa(Ka, B::dh_private_wrapped_a)
3. Calculate the shared Diffie-Hellman key
    DH := B::dh_public_b^(Xa) (=(g^Xb)^Xa = g^(Xb*Xa))
4. Calculate the key-wrapping key DH' with the key derivation fuctnion and DH
    DH' := KDF_DF(DH)
5. Unwrap the wrapped key, using the key unwrapping function
    K = KU_WFc(DH', B::wrapped_key)
6. Output

(edited )

Common Key construction

Knowing a password and decrypting its wrapped key, one should be able to calculate a common shared key. This is achieved via the key agreement scheme. In each step we take two branches, i.e. either a Password Block or a Consolidation Block for which we can derive the wrapped keys, and perform the key agreement scheme to form a new Consolidation Block. This new block also holds a key, whose value can be unwrapped with either of the keys of the blocks used to form the new block. In this sense, the Password Blocks are leaves in a tree whose internal nodes are Consolidation Blocks. The trees root node then holds a common shared key, which can be unwrapped by following the branch from a single Password Block upwards, unwrapping keys along the way.

In its simplest form, the tree is merely a chain. This removes the need to store any kind of parent/child information which might be necessary for a tree. Simply interleave Password and Consolidation Blocks, with an additional Password Block in the beginning, such that the order gives the order of the chain. In each consolidation step, a new Password Block is joined with the previous chained with a new Consolidation Block.

Credential addition and rekeying, and credential removal

With the above chain construction, it is possible to add additional credentials and remove credentials appearing higher-up in the chain while keeping intact the access to the shared key for all other parties. Additionally, one can rekey the entire structure, changing all encryption keys appearing in blocks which are part of ones branch.

The following algorithm can be used to add an additional credentials block to the top of the chain, using any valid passphrase which is already contained in the chain:

Function: AddCredentials
Input: Unwrapped Key Kr of the current root block,
       New passphrase P, argon2 parameters A2P, and key wrap function WF
       Diffie-Hellman parameters p and g, Wrap function choices WFa, WFb, WFc
Output: New root Consolidation Block, New Password Block

1. Construct the new Password Block Bp
    Bp = ConstructPasswordBlock(P, A2P, WF)
2. Unwrap the password blocks key Kb (technically, this could also be a second
   result of ConstructPasswordblock but this makes the specification less
    Kb = UnwrapPasswordBlock(Bp, P)
3. Construct the new root block Brn
    Brn = ConstructConsolidationBlock(Kr, Kb, (p, g), (WFa, WFb, WFc))
4. Output
    (Brn, Bp)

Removal of any party can be achieved by changing the wrapped key of a consolidation block B* to the wrapped key of another block, then dropping that block (and its other child, the password block) from the chain. Any branch below B* will not have any trouble unwrapping all the keys on its branch. When it encounters B*, the wrapped key of the dropped block will be unwrapped. The next block in the chain will exactly require the key from the dropped block, as it originally followed the dropped block. No other changes to the chain have been made, so everything else will still unwrap fine.

Rekeying makes it possible for any party to change the root key (or any key along its branch) without disrupting access for other parties with valid credentials. After removing some party from the chain, it is recommended to rekey all blocks from the dropped block onwards, as decryption is possible with any intermediate key.

Here's how rekeying of a Consolidation Block can be done, again symetric for branch b:

Function: RekeyConsolidationBlock
Input: ConsolidationBlock B, New Key Ka'
Output: New ConsolidationBlock

1. Retrieve the key wrapping function choices, and DH parameters as well as the
   public key data from branch b, and the key derivation function DF
    WFa := B::dh_wrap_function_a
    WFc := B::key_wrap_function
    p := B::dh_p
    g := B::dh_g
    Yb := B::dh_public_b
    DF := B::key_derivation_function
2. Choose, randomly, a new exponent for DH
    Xa := /* random DH exponent */
3. Calculate the new key wrapped private data and public key
    Ya := (g^Xa) mod p
    Xa' := KW_WFa(Ka', Xa)
4. Calculate the new shared Diffie-Hellman key
    DH := (Yb^Xa) mod p (=g^(Xb*Xa) mod p)
5. Derive the Key encryption key with DF and DH
    DH' := KDF_DF(DH)
6. Choose, randomly, a new consolidation block private key K, 256 bit length
7. Calculate the new wrapped key K', using function choice WFc
    K' := KW_WFc(DH', K)
8. Output
    ConsolidationBlock {
        dh_p := p,
        dh_g := g,
        dh_wrap_function_a := WFa,
        dh_private_wrapped_a := Xa',
        dh_wrap_function_b := B::dh_wrap_function_b,
        dh_private_wrapped_b := B::dh_private_wrapped_b,
        dh_public_a := Ya,
        dh_public_b := B::dh_public_b,
        key_wrap_function := B::key_wrap_function,
        key_derivation_function := B::key_derivation_function,
        wrapped_key := K'

(edited )

Notice how rekeying can be done without knowledge of the prior encryption key Ka but it also does reveal information without that knowledge. See notes and discussion for some thoughts about this being a weakness or not and what could be done to force knowledge of the previous key.

If this Consolidation Block B is not the root block, then you must either reencrypt the private DH information of its parent, which requires knowledge of both the old block key K as well as the new key K'; or you must rekey the parent block as well. If the root consolidation key, the common key, has been used to encrypt any data then the root key has to be recovered before the rekeying to be able to reencrypt this data with the new root key. Hence, any block key along the branch must have been known in order to recover the root key prior to rekeying.

Notes and discussion

Attestation in rekeying (rewritten )

The threat model of the above considers an attacker trying to read the shared resource but does not yet consider forgery. Specifically, an attack may exploit the data structure to create a new shared resource accessible by the previous parties but also by him. This could trick the previous parties into storing sensitive information in this new resource which could then be read by the attacker.

The attack vector is the ability to modify and rekey a consolidation block without having access to either of the creating branches. To prevent arbitrary parties from rekeying a consolidation block, we must involve a proof of access which is established at creation time and can only be change with knowledge of the blocks consolidated key.

The following is sketch outlines an additional idea on how to achieve this. It might still be broken, but hopefully it prevents the previous attack:

struct {
    /* [ .. ] All previously established fields */
    opaque attestation_iv[32];
} PasswordBlock;

struct {
    /* [ .. ] All previously established fields */
    opaque encrypted_attestation_a[32];
    opaque encrypted_attestation_b[32];
} ConsolidationBlock;

Function: ConstructPasswordBlock
3.1 Choose, randomly, an initial attestation value Vi
4. Output
        attestation_iv := Vi,

Function: CalculatePasswordAttestation
Input: PasswordBlock B, Password P
Output: The password blocks attestation value V

1. Recover the secret key K
    K := UnwrapPasswordBlock(B, P)
2. Calculate the signed value V of of the iv with K
    V := HMAC(K, B::attestation_iv)
3. Output

Function: ConstructConsolidationBlock
Input: [..], attestations values Va, Vb

4.1 Encrypt the previous attestation values with the private block key K
    Va' := KW(K, Va)
    Vb' := KW(K, Vb)
6. Output
        encrypted_attestation_a := Va',
        encrypted_attestation_b := Vb',
        attestation_iv := Vi,

Function: CalculateConsolidationAttestation
Input: Unwrapped key Ka, Consolidation Block B
Output: Attestation value V

1. Recover the secret key K, and public dh keys
    K := UnwrapConsolidationBlock(Ka, B)
    Ya := B::dh_public_a
    Yb := B::dh_public_b
2. Unwrap the preceding attestation values
    Va := KU(K, Va')
    Vb := KU(K, Vb')
3. Calculate attestation as the signature of dh public keys, and the
   branches attestation values with K
    V := HMAC(K, Ya || Yb || Va || Vb )
4. Output

To insert a consolidation block in this construction, one would have to update the parent block in the chain. During unwrapping, one would check the attestation of the known branch as well as recalculate the blocks attestation value.

The attestation value in this chain construction presents a party trying to construct a consolidation block with one of two challenges:

  1. Know the secret key K to a previously constructed consolidation block, to be able to unwrap the attestation value from the previously encrypted value.
  2. Know the secret key of the child block, password or consolidated, to recalculate the signed value.

Note that this model does not prevent an attacker who has credentials to the shared resource from making changes to the block structure. In detail, the attestation and construction of a new block could be performed for any block in the attackers branch. Therefore, in case even one password is compromised, you need to change rekey all consolidated block of the branch, to change all compromised attestation values. This is inherently necessary, since an attacker capable of changing data would be able to replay the compromised file to anyone who has not yet changed their credentials, regardless of the underlying file structure.

We only need to consider the case where all passwords have been changed and make the attacker unable to read or stealthily modify any data in this case. Since rekeying will change all attestation values, and all internal keys are changed by this as well, this should be safe.

What does all of this get us then? An attacker who has only read access and compromised a password can be shut out of the system by changing that single password, instead of having to reenter all passwords, at least we hope that this can be guaranteed. And with attestation, even an attacker with write access can only get so far without passwords.

No formal proof is provided in this document, so don't take anything at face value.

Alternative tree structures

A chain of consolidation blocks and password blocks might be the most straighforward structure but this requires a decryption time which scales linearly with the number of credentials. While this still seeems fairly reasonable, in some settings other structures are preferable. In particular, any set of credentials can modify any blocks in its branch. More complex trees could therefore better model hierarchies much better, especially when incorporating the attestation idea above, which, if it fulfills its goal, makes it harder to reshape the tree without being detected. The hierarchy might then also be part of the attestation.

Usage in password managers

As mentioned in the introduction, a major use case for this construction would be password managers. This will be exemplified with the PwSafe format v3/v4. In this case, the chain would protect a secret database encryption key K, an integrity verification key L. In this case, the integrity verification key protects both the integrity of the main database as well as the header, containing the chain, with an HMAC checksum. In case the attestation proposal has any bearings, the latter would also involve the attestation of the chains root block.

The specification for format v4 introduces a potential weakness which had not been present in version v3 but appears in the more recent version when multiple master passwords are in use. This has been noted as a format weakness in academics:

The PasswordSafe v3 database format stores both the encryption key and the MAC key used to secure the database content in the file header. [..] this specification detail opens the door to an attack. Assume that an adversary is able to obtain the master password for an encrypted database. Using the master password, the adversary would also be able to retrieve (and store) K and L. Subsequently, even if the user changes her master password, the adversary can still decrypt and/or modify any new version of the database. [..] i.e., changing the master password serves no purpose. pwsafe-security

While this is remedied in v3 by simply changing K and L each time the file is saved, the current specification v4 wraps the parameters separately for each password. This makes changing them impossible without entering all credentials, hence giving the illusion of security when a single password is changed only, as critiqued above.

The construction suggested here would make it possible to change K and L with any single password, through the rekeying algorithm.

Published on
Last updated