Recover Hashicorp Vault recovery key

TL;DR

• Generate recovery key
• Encrypt recovery key with random generated DEK key
• Encrypt DEK key with KMS service
• Serialize encrypted recovery key + encrypted DEK key + IV + KMS Key Info
• Persist binary data into storage backend

Motivation

I have worked with Vault in the last few couple of weeks, I stumped up-on major topics of a production Vault system such as SSO with Google Workspace, AWS authentication, identity management, dynamic ACL, dynamic secrets, and auto-unseal to make it work in our Kubernetes cluster. Thanks to Vault population with the great community and documentations, I could get it run as expected in our test cluster for evaluation.

As you may know that when Vault configured with auto-unseal, when you init Vault by running vault operator init the first time, it will generate recovery key & root token, you should saving/backup these secrets somewhere. Root token is a Vault token with super privileges & can do anything within Vault system and recovery key will be used for features that require a quorum of users to perform (such as re-generate root token). And I was wonder

If I lost recovery key and root token, how can I access my Vault with highest privileges?

As mentioned before, the recovery key could be use to re-generate root token. So if we can somehow recover the recovery key, we could then use the recovery key to re-generate root token. In this blog post, I will walk through the process of recover recovery key by looking at the Vault source code. Let's begin

The life of recovery key begin with

if recoveryConfig.SecretShares > 0 {
    recoveryKey, recoveryUnsealKeys, err := c.generateShares(recoveryConfig)
    if err != nil {
        c.logger.Error("failed to generate recovery shares", "error", err)
        return nil, err
    }

    err = c.seal.SetRecoveryKey(ctx, recoveryKey)
    if err != nil {
        return nil, err
    }

    results.RecoveryShares = recoveryUnsealKeys
}

It was generated by *Core.generateShares and passed into *Core.seal.SetRecoveryKey for encryption and long-term storage. Looking at further, we see that *Core.seal is a variable of type Seal which in turn is an Interface. For auto-unseal feature, the implementation be like

 func (d *autoSeal) SetRecoveryKey(ctx context.Context, key []byte) error {
    if err := d.checkCore(); err != nil {
      return err
    }

    if key == nil {
      return fmt.Errorf("recovery key to store is nil")
    }

    // Encrypt and marshal the keys
    blobInfo, err := d.Encrypt(ctx, key, nil)
    if err != nil {
      return errwrap.Wrapf("failed to encrypt keys for storage: {{err}}", err)
    }

    value, err := proto.Marshal(blobInfo)
    if err != nil {
      return errwrap.Wrapf("failed to marshal value for storage: {{err}}", err)
    }

    be := &physical.Entry{
      Key:   recoveryKeyPath,
      Value: value,
    }

    if err := d.core.physical.Put(ctx, be); err != nil {
      d.logger.Error("failed to write recovery key", "error", err)
      return errwrap.Wrapf("failed to write recovery key: {{err}}", err)
    }

    return nil
  }

I will not talk so much about generation process but will dive deeper into the later. From the code snippet, we can see that main functions tasks are:

Encrypt recovery key with *autoSeal.Encrypt

This function will set some internal metrics and then call to wrapping.Wrapper.Encrypt for actual encryption. Package wrapping a library support encrypt things through various KMS providers.

From README.md we have some notes

For KMS providers that do not support encrypting arbitrarily large values, the library will generate an envelope data encryption key (DEK), encrypt the value with it using an authenticated cipher, and use the KMS to encrypt the DEK.
....
Supports many KMSes:
  AEAD using AES-GCM and a provided key
  Alibaba Cloud KMS (uses envelopes)
  AWS KMS (uses envelopes)
  Azure KeyVault (uses envelopes)
  GCP CKMS (uses envelopes)
  Huawei Cloud KMS (uses envelopes)
  OCI KMS (uses envelopes)
  Tencent Cloud KMS (uses envelopes)
  Vault Transit mount
  Yandex.Cloud KMS (uses envelopes)
Transparently supports multiple decryption targets, allowing for key rotation
Supports Additional Authenticated Data (AAD) for all KMSes except Vault Transit.

We will talk more about Envelopes later in Protocol Buffer section. Now back to the encryption wrapper function. Its implementation is:

// https://github.com/hashicorp/go-kms-wrapping/blob/master/wrapper.go#L47

type Wrapper interface {
    // Type is the type of Wrapper
    Type() string

    // KeyID is the ID of the key currently used for encryption
    KeyID() string
    // HMACKeyID is the ID of the key currently used for HMACing (if any)
    HMACKeyID() string

    // Init allows performing any necessary setup calls before using this Wrapper
    Init(context.Context) error
    // Finalize should be called when all usage of this Wrapper is done
    Finalize(context.Context) error

    // Encrypt encrypts the given byte slice and puts information about the final result in the returned value. The second byte slice is to pass any additional authenticated data; this may or may not be used depending on the particular implementation.
    Encrypt(context.Context, []byte, []byte) (*EncryptedBlobInfo, error)
    // Decrypt takes in the value and decrypts it into the byte slice.  The byte slice is to pass any additional authenticated data; this may or may not be used depending on the particular implementation.
    Decrypt(context.Context, *EncryptedBlobInfo, []byte) ([]byte, error)
}

Wrapper is an interface type (some thing link abstraction function), so each KMS will implement those methods differently (but with the specify function signature). For the sake of my knowledge, I will pick AWS KMS for explanation.

AWS KMS implementation looks something like this

// Encrypt is used to encrypt the master key using the the AWS CMK.
// This returns the ciphertext, and/or any errors from this
// call. This should be called after the KMS client has been instantiated.
func (k *Wrapper) Encrypt(_ context.Context, plaintext, aad []byte) (blob *wrapping.EncryptedBlobInfo, err error) {
    if plaintext == nil {
        return nil, fmt.Errorf("given plaintext for encryption is nil")
    }

    env, err := wrapping.NewEnvelope(nil).Encrypt(plaintext, aad)
    if err != nil {
        return nil, fmt.Errorf("error wrapping data: %w", err)
    }

    if k.client == nil {
        return nil, fmt.Errorf("nil client")
    }

    input := &kms.EncryptInput{
        KeyId:     aws.String(k.keyID),
        Plaintext: env.Key,
    }
    output, err := k.client.Encrypt(input)
    if err != nil {
        return nil, fmt.Errorf("error encrypting data: %w", err)
    }

    // Store the current key id
    //
    // When using a key alias, this will return the actual underlying key id
    // used for encryption.  This is helpful if you are looking to reencyrpt
    // your data when it is not using the latest key id. See these docs relating
    // to key rotation https://docs.aws.amazon.com/kms/latest/developerguide/rotate-keys.html
    keyID := aws.StringValue(output.KeyId)
    k.currentKeyID.Store(keyID)

    ret := &wrapping.EncryptedBlobInfo{
        Ciphertext: env.Ciphertext,
        IV:         env.IV,
        KeyInfo: &wrapping.KeyInfo{
            Mechanism: AWSKMSEnvelopeAESGCMEncrypt,
            // Even though we do not use the key id during decryption, store it
            // to know exactly the specific key used in encryption in case we
            // want to rewrap older entries
            KeyID:      keyID,
            WrappedKey: output.CiphertextBlob,
        },
    }

    return ret, nil
}

This function do 3 main things

• Encrypt plaintext with a (generated randomly) Data Encryption Key (DEK)
• Encrypt above DEK key with KMS
• Put everything into a wrapping.EncryptedBlobInfo for storage & decryption later

2 later steps are straightforward when we look at the source. The encryption step is passed into another function

func (e *Envelope) Encrypt(plaintext []byte, aad []byte) (*EnvelopeInfo, error) {
    // Generate DEK
    key, err := uuid.GenerateRandomBytes(32)
    if err != nil {
        return nil, err
    }
    iv, err := uuid.GenerateRandomBytes(12)
    if err != nil {
        return nil, err
    }
    aead, err := e.aeadEncrypter(key)
    if err != nil {
        return nil, err
    }

    return &EnvelopeInfo{
        Ciphertext: aead.Seal(nil, iv, plaintext, aad),
        Key:        key,
        IV:         iv,
    }, nil
}

This function will:

• Generate random DEK for encryption
• Generate random nonce (Initalization Vector) for block cipher (eas in this case)
• Encrypt plaintext with the key

So now we have all the things needed to put it into persistent storage. Head up to the next.

Serialize encrypted data into binary re-presentation

Vault store data in the protobuf binary format. To make it work, we need to have a .proto file that specify structural messages, the we use protoc to compile that file to the programming language structures/helper functions. Those code will help in serialize/deserialize between language object and binary data. We will look at the compiled version for Go

// EncryptedBlobInfo contains information about the encrypted value along with
// information about the key used to encrypt it
type EncryptedBlobInfo struct {
    state         protoimpl.MessageState
    sizeCache     protoimpl.SizeCache
    unknownFields protoimpl.UnknownFields

    // Ciphertext is the encrypted bytes
    Ciphertext []byte `protobuf:"bytes,1,opt,name=ciphertext,proto3" json:"ciphertext,omitempty"`
    // IV is the initialization value used during encryption
    Iv []byte `protobuf:"bytes,2,opt,name=iv,proto3" json:"iv,omitempty"`
    // HMAC is the bytes of the HMAC, if any
    Hmac []byte `protobuf:"bytes,3,opt,name=hmac,proto3" json:"hmac,omitempty"`
    // Wrapped can be used by the client to indicate whether Ciphertext
    // actually contains wrapped data or not. This can be useful if you want to
    // reuse the same struct to pass data along before and after wrapping.
    Wrapped bool `protobuf:"varint,4,opt,name=wrapped,proto3" json:"wrapped,omitempty"`
    // KeyInfo contains information about the key that was used to create this value
    KeyInfo *KeyInfo `protobuf:"bytes,5,opt,name=key_info,json=keyInfo,proto3" json:"key_info,omitempty"`
    // ValuePath can be used by the client to store information about where the
    // value came from
    ValuePath string `protobuf:"bytes,6,opt,name=ValuePath,proto3" json:"ValuePath,omitempty"`
}

// KeyInfo contains information regarding which Wrapper key was used to
// encrypt the entry
type KeyInfo struct {
    state         protoimpl.MessageState
    sizeCache     protoimpl.SizeCache
    unknownFields protoimpl.UnknownFields

    // Mechanism is the method used by the wrapper to encrypt and sign the
    // data as defined by the wrapper.
    Mechanism     uint64 `protobuf:"varint,1,opt,name=Mechanism,proto3" json:"Mechanism,omitempty"`
    HMACMechanism uint64 `protobuf:"varint,2,opt,name=HMACMechanism,proto3" json:"HMACMechanism,omitempty"`
    // This is an opaque ID used by the wrapper to identify the specific key to
    // use as defined by the wrapper. This could be a version, key label, or
    // something else.
    KeyID     string `protobuf:"bytes,3,opt,name=KeyID,proto3" json:"KeyID,omitempty"`
    HMACKeyID string `protobuf:"bytes,4,opt,name=HMACKeyID,proto3" json:"HMACKeyID,omitempty"`
    // These value are used when generating our own data encryption keys
    // and encrypting them using the wrapper
    WrappedKey []byte `protobuf:"bytes,5,opt,name=WrappedKey,proto3" json:"WrappedKey,omitempty"`
    // Mechanism specific flags
    Flags uint64 `protobuf:"varint,6,opt,name=Flags,proto3" json:"Flags,omitempty"`
}

After encrypt, we should have encrypted key in form of
wrapping.EncryptedBlobInfo, we should take care about fields

EncryptedBlobInfo.Ciphertext : Contain encrypted recovery key value
EncryptedBlobInfo.KeyInfo: Contain information about DEK key

EncryptedBlobInfo.KeyInfo.KeyID: (KMS) Key ID used to encrypte DEK
EncryptedBlobInfo.KeyInfo.WrappedKey: The encrypted value of DEK

Understand those above fields could help us on decryption process later. For those using different languages, you could down load the definition and adjust base on your languages

Write binary data into storage backend

After above steps, we're ready to store the encrypted recovery key into our backend of choice by d.core.physical.Put(ctx, be)

Again, this is an interface that will specific to the backend storage implementation. I will use consul for the explanation.

// Put is used to insert or update an entry
func (c *ConsulBackend) Put(ctx context.Context, entry *physical.Entry) error {
    defer metrics.MeasureSince([]string{"consul", "put"}, time.Now())

    c.permitPool.Acquire()
    defer c.permitPool.Release()

    pair := &api.KVPair{
        Key:   c.path + entry.Key,
        Value: entry.Value,
    }

    writeOpts := &api.WriteOptions{}
    writeOpts = writeOpts.WithContext(ctx)

    _, err := c.kv.Put(pair, writeOpts)
    if err != nil {
        if strings.Contains(err.Error(), "Value exceeds") {
            return errwrap.Wrapf(fmt.Sprintf("%s: {{err}}", physical.ErrValueTooLarge), err)
        }
        return err
    }
    return nil
}

The function just do 1 thing is write the key/value pair into consul system using Consul KV API Client.

Closing

For the above knowledge, I wanted to see if we could do the reverse process to get the recovery key from the storage object on my own. So I write a small program to do it. It now support AWS KMS and Consul backend only. Any contribution is always be welcomed