Projects/Encryption performance
Contents
Desired Changes
This project follows after Projects/Crypto modularity and intends to improve encryption performance by allowing cached information to be added to keys. It also creates API concepts which can be later used for supporting cryptographic tokens.
The current API uses an exposed structure, krb5_keyblock, to convey key information to the encryption functions. Because the keyblock type is not opaque, we cannot add fields to it without breaking the ABI. If encryption is performed repeatedly with the same key and usage, the derived key must be re-computed each time. If the encryption back end library associates a handle with the key, the handle must be re-initialized each time the key is used.
Keyblocks are used within several other exposed krb5 structures, including credentials and keytab entries, which would make it difficult to revise the entire API to use a new type. However, in most cases where keyblocks are used within other API structures, the key contents alone are sufficient; such keys are generally either being readied for transmission over the network, or will be used for only a single encryption with a particular key usage. Keys used for repeated encryptions are stored within auth context structures--either krb5_auth_context or krb5_gss_ctx_id_rec--which are opaque and can be modified.
API Proposal
The keyblock structure retains its current meaning as the exposed data of a cryptographic key. For keys which may be used repeatedly or which may be an external reference, we define a new opaque type krb5_key:
struct krb5_key_st; typedef struct krb5_key_st *krb5_key;
The prefix krb5_k_ will distinguish functions operating on keys from similar functions operating on keyblocks. Opaque keys have the following initializers and accessors:
krb5_error_code krb5_k_create_key(krb5_context context, krb5_keyblock *key_data,
krb5_key *out);
void krb5_k_free_key(krb5_context context, krb5_key key);
krb5_error_code krb5_k_key_keyblock(krb5_context context, krb5_key key,
krb5_keyblock **key_data);
krb5_enctype krb5_k_key_enctype(krb5_context context, krb5_key key);
The following new functions encrypt, decrypt, checksum, or verify data using opaque keys.
krb5_error_code krb5_k_encrypt(krb5_context context, krb5_key key,
krb5_keyusage usage,
const krb5_data *cipher_state,
const krb5_data *input, krb5_enc_data *output);
krb5_error_code krb5_k_encrypt_iov(krb5_context context, krb5_key key,
krb5_keyusage usage,
const krb5_data *cipher_state,
krb5_crypto_iov *data, size_t num_data);
krb5_error_code krb5_k_decrypt(krb5_context context, krb5_key key,
krb5_keyusage usage,
const krb5_data *cipher_state,
const krb5_enc_data *input, krb5_data *output);
krb5_error_code krb5_k_decrypt_iov(krb5_context context, krb5_key key,
krb5_keyusage usage,
const krb5_data *cipher_state,
krb5_crypto_iov *data, size_t num_data);
krb5_error_code krb5_k_make_checksum(krb5_context context,
krb5_cksumtype cksumtype, krb5_key key,
krb5_keyusage usage,
const krb5_data *input,
krb5_checksum *cksum);
krb5_error_code krb5_k_make_checksum_iov(krb5_context context,
krb5_cksumtype cksumtype,
krb5_key key, krb5_keyusage usage,
krb5_crypto_iov *data,
size_t num_data);
krb5_error_code krb5_k_verify_checksum(krb5_context context, krb5_key key,
krb5_keyusage usage,
const krb5_data *data,
const krb5_checksum *cksum,
krb5_boolean *valid);
krb5_error_code krb5_k_verify_checksum_iov(krb5_context context,
krb5_cksumtype cksumtype,
krb5_key key, krb5_keyusage usage,
const krb5_crypto_iov *data,
size_t num_data,
krb5_boolean *valid);
These functions do not define a new and complete crypto layer; there are other crypto functions which refer to keyblocks, such as krb5_c_prf and krb5_c_string_to_key, for which there will be no parallel function using krb5_key. Furthermore, the keyblock-using parallels to the above functions will not be deprecated, but they will be documented as being less efficient for repeated operations with the same key usage.
Implementation Design
The existing krb5_c versions of the new functions will be reimplemented in terms of the krb5_k functions. Internal functions and the enc_provider, hash_providers, and enctype vtables will be redefined using krb5_key so that back ends only need to implement one version of the interface. To avoid excessive conversions, a few internal interfaces will still use keyblocks, particularly many the interfaces which construct keys.
The krb5_key_st structure will initially contain a linked list of derived keys, mapping a derivation constant (krb5_data) to a krb5_key. krb5_derive_key will cache derived keys in this list. The krb5_key_st structure will contain a flag to disable caching so that we don't waste the time allocating and copying such information for keyblock-using functions like krb5_c_encrypt which wouldn't preserve the cache.
In krb5_auth_context and krb5_gss_ctx_id_rec, all keyblock fields will be replaced with krb5_keys, and all usages of those fields changed to use the krb5_k APIs.
Testing
The existing t_encrypt.c will be expanded to test the krb5_k APIs as well as the krb5_c APIs where applicable.
To help measure the performance improvement from caching derived keys, a testing harness will be written to encrypt and decrypt, or hash and verify, a specified number of blocks of a specified size with the same usage, using both the krb5_c and krb5_k APIs, and compare the time taken with each.
The existing test suite should adequately test the changes to the code paths associated with the auth_context and id_rec structures.
Some sample performance gains from derived key caching on a 64-bit Linux/x86 machine, with AES-128 keys:
- 1 million encryptions of 16 bytes: 6.4s -> 1.8s (72% reduction)
- Half a million encryptions of 1024 bytes: 8.4s -> 6.1s (27% reduction)
- 1 million checksums of 16 bytes: 3.6s -> 1.2s (67% reduction)
- Half a million checksums of 1024 bytes: 3.5s -> 2.4s (31% reduction)
Future Work
A follow-on project to support cryptographic tokens can define a new krb5_key initializer which creates an external reference, and a new error code for krb5_key_keyblock which indicates that the keyblock data is unavailable.
Milestones
Implementation work on this project will not begin until work on Projects/Crypto modularity is substantially completed, so no dates will be specified at this time. The probable order of work will be:
- Define the krb5_key type (without the derived key list) and its constructors, destructors, and accessors.
- Re-specify the internal crypto functions in terms of krb5_key and make the krb5_c APIs using keyblocks do the appropriate translation when necessary.
- Define the new krb5_k APIs.
- Write the expanded test cases in t_encrypt.c.
- Modify the auth_context and id_rec structures to use krb5_keys and change the relevant code appropriately.
- Implement derived key caching.
- Implement the test harness for measuring the performance improvement from derived key caching.
Rationale
Several other approaches were considered (see http://mailman.mit.edu/pipermail/krbdev/2009-June/007780.html). The most plausible was to create a cache within the krb5_context structure mapping keyblocks to derived key lists or other information. However, this might not have performed as well, and would have allowed for the possibility of subtle memory leaks if cache entries were not cleaned up properly.
The naming of the new APIs is problematic, since it is not possible to intuitively capture the notion of "encrypt using a new, different, opaque key type" within a concise name. The krb5_k names were chosen to be distinctive and consistent, if not immediately clear.
Review
This section documents the review of the project according to Project policy. It is divided into multiple sections. First, approvals should be listed. To list an approval type
- #~~~~
on its own line. The next section is for summarizing discussion, which should take place on krbdev@mit.edu. Provide links to the archive at http://mailman.mit.edu/pipermail/krbdev/ if appropriate. Blocking objections can be noted with {{project-block}}.
Approvals
- SamHartman 15:27, 5 August 2009 (EDT)
