Articles

learn more about encryption

Yubikey Implementation Notes

The purpose of this article is to provide information on Kryptel implementation for public scrutiny. At least a basic understanding of programming is required.

How Does Yubikey Work

Yubikey implements HMAC (FIPS PUB 198) based on SHA-1 (FIPS PUB 180-2). It accepts a 64-byte 'challenge' and returns 20-byte 'response' based on a secret internally stored key.

Kryptel and Silver Key use Yubikey response as a key for encryption of the session key. In order to decrypt the data back we need the challenge and the encrypted session key. Note that it is safe to keep the challenge in the open as the right response can't be guessed without knowing Yubikey's internal secret key.

Encryption with Yubikey consists of the following steps:

  1. Generate a random session key and use it for data encryption,
  2. Generate a random 64-byte challenge,
  3. Send the challenge to Yubikey and receive 20-byte response,
  4. Set the received response as encryption key and encrypt the session key.
  5. Store the challenge and the encrypted session key.

In order to decrypt the data, we need the saved challenge and the encrypted session key (and of course, the right Yubikey). Decryption is performed as follows:

  1. Send the stored challenge to Yubikey and receive 20-byte response,
  2. Set the received response as the cipher key and decrypt the session key.
  3. Use the session key to decrypt the data.

We also need some way to determine if the session key we have obtained is the right one. Kryptel and Silver Key provide a ready HMAC-based mechanism called 'key verificator', which fits the task perfectly.

Note that there is no way to determine if Yubikey is the right one. Yubikey serial number can't be used for that, as Yubikey may be reprogrammed (right serial number, wrong Yubikey) or replaced (wrong serial number, right Yubikey). We can only determine that a given Yubikey produces the right session key (i.e. a session key that passes key verification).

Yubikey List Format

The technique described above can easily be extended to a set of Yubikeys. We can encrypt the session key with several responses, and store a list of pairs 'challenge / encrypted session key'. During decryption, we need to try the inserted Yubikey against each record until we get the right session key (or until the list ends).

The Yubikey records are stored the in container/parcel header, in the field named 'key associated data'. The list may be either plain (if KeyID is IDENT_YUBIKEY) or encrypted (if KeyID is IDENT_YUBIKEY_PASSWORD).

Yubikey Record

Each record in the list is of the same length and has the following structure:

Size Description
4 Yubikey serial number (0 if unknown)
64 Challenge
n * BlockSize Encrypted session key

The size of the key field is the minimal number of cipher blocks that is greater or equal to the cipher key size. For example, if the key size is 48 bytes (384 bits), and the cipher block is 32 bytes (256 bits), then the size of the key field will be 64 (2 * 32) bytes. The key is stored from the beginning of the field, the rest (if present) is not used and is filled with random data. After that the field is encrypted in the CBC mode with Yubikey 20-byte response as the key.

Plain Yubikey List (KeyID is IDENT_YUBIKEY)

Size Description
2 Number of Yubikey records
. . . Yubikey record 1
. . . Yubikey record 2
. . . . . .
. . . Yubikey record N

Encrypted Yubikey List (KeyID is IDENT_YUBIKEY_PASSWORD)

Size Description
2 Number of Yubikey records
[Start of encrypted part]  
HashSize Session key verificator
. . . Yubikey record 1
. . . Yubikey record 2
. . . . . .
. . . Yubikey record N

In case of encrypted list the key verification block in the header is used for password verification. The session key verificator is in the encrypted part of the list. The verification block and the array of Yubikey records are encrypted as a single block using ICipher (that is, as basic encrypted stream).

Special Bits in Challenge String

Two lowest bits of the first byte of the challenge has special meaning. Bit 0 (mask 0x01) designates Yubikey slot (0 - slot 1, 1- slot 2). Bit 1 (mask 0x02) is read-only bit. If it is set to 1, Kryptel opens the container in read-only mode. This bit does not have any specific meaning for Silver Key as its parcels can't be modified.

Embedding these bits into the challenge (specifically, the read-only bit) makes impossible changing them by editing the header. Challenge can't be edited as a modified challenge will produce a completely different response.

Maximal size of Yubikey list

The header size field is two-byte long, so the header cannot be larger than 65535 bytes. The size of key associated data is limited to 64096 bytes. For a very typical case of 256-bit AES, the size of each Yubikey record will be 4 + 64 + 32 = 100 bytes, so the maximal number of Yubikeys in the list is 640. The limit seems to be sufficient, as Yubikey is a slow device, and matching even this number of records will take unacceptable time (up to 3 minutes).

Yubikey Matching

Yubikey record matching is performed as follows:

  1. Fetch 64-byte challenge from the record and send it to Yubikey,
  2. Get 20-byte response and set it as the decryption key,
  3. Decrypt the session key field,
  4. Use the key verificator to determine if it indeed is the session key.
Note about Yubikey serial number

If present, it greatly speeds key matching for large Yubikey lists. A Yubikey challenge-response request takes around 0.15s. With hashing and encryption time added, matching a single key may take as much as 0.2s. For example, if the Yubikey list contains 100 Yubikeys, the key matching part may take up to 20 seconds. Serial number helps to locate the particular key record without trying each and every one of them.

However Yubikey can easily be re-programmed so don't rely on serial number. The list may contain several different Yubikeys with the same serial number (as a result of re-programming), or the right Yubikey with a wrong serial number (as a result of Yubikey replication). Consider serial number as a hint, which may (or may not) help to locate the right record.

Recommended Yubikey matching sequence

Key matching should be performed in three stages.

Stage 1. Get the serial number of the inserted Yubikey. Perform matching for all records with that serial number (there may be several records with the same serial number).

Stage 2. If record not found, perform matching with all records that have zero in the serial number field.

Stage 3. If not found, perform matching for the records with a wrong serial number. This stage is necessary as a replacement Yubikey will have a different serial number.

Yubikey Storage

Yubikey lists are stored securely. Yubikey storage is a Kryptel container that has CID_YUBIKEY_STORAGE as agent component ID. This ID does not correspond to any component (no agent is used), just indicates Yubikey storage.

Yubikey record is represented by root's child object. There is no tree structure, just an empty root object and a set of its children, each representing a Yubikey. All key info is stored in object's attrubute block, there is no attached stream. The first byte of the attribute block specifies the type of the block:

0 - Challenge-response set
1 or 2 - HMAC key, the value indicates Yubikey slot
Challenge-Response Block

Challenge-response block is created from a USB-inserted Yubikey. The internal secret key can't be read, so we generate several challenge-response pairs (16 read/write and 8 read-only pairs). During encryption a randomly selected pair is used.

Size Description
1 Always 0: Challenge-response block
1 Not zero if read-only (default setting, not forced)
4 Key serial number
STR Key name
2 Number of R/W challenge-response records (must be power of 2)
. . . R/W challenge-response records, each is 84 byts long (64 chal, 20 resp)
2 Number of R/O challenge-response records (must be power of 2)
. . . R/O challenge-response records, each is 84 byts long (64 chal, 20 resp)

Note that we don't need to store the slot number as it is hardwired in the challenges (see "Special Bits in Challenge String" above).

HMAC Key Block

HMAC key block is created from a .csv setup log file. The secret key is known, no need to store pre-generated pairs.

Size Description
1 1 or 2: HMAC key block, the value indicates Yubikey slot
1 Not zero if read-only (default setting, not forced)
STR Key name
STR Key source (path to the .csv file)
20 HMAC key

STR represents a UNICODE string; first word (2 bytes) contains the string length in characters. The string does not contain trailing zero. Each UNICODE character occupies 2 bytes.

Key Dump

Key dump file is used to move keys between storage files (and can also be used for decryption). It is just a sequence of storage attribute blocks, each containing either challenge-response block or HMAC key block.

Size Description
4 Dump file tag 0x113BF001
4 Number of attribute blocks
2 Size of attribute block 1
. . . Attribute block 1
2 Size of attribute block 2
. . . Attribute block 2
. . . . . .
2 Size of attribute block N
. . . Attribute block N
16 MD5 hash of previous data