Discussion of the new 256 bit key derivation sequence

A project log for Orthrus

SD card secure RAID USB storage

Nick SayerNick Sayer 10/30/2017 at 16:350 Comments

In going from AES-128 to AES-256 for the WDE in Orthrus, the key derivation sequence had to be revamped to result in twice as many bits of key. This was particularly complicated by the fact that the key size and cipher block size were no longer the same.

To recall, the new key derivation sequence is:

Each card has 256 bits of unique (private), random key seed material and 512 bits of common (public) key material. The two blocks of private material are shuffled together and an AES CMAC with a 256 bit zero key is performed on each half of the shuffled blocks. The two results are concatenated to form the intermediate key. The two halves of the public block are run through AES CMAC with the intermediate key to form the two halves of the final volume key.

In examining a cryptographic method, what you're looking for is any weak spots - any places where an input into a method unnaturally constrains a key to a smaller number of bits. If there are any such places, then that's where an adversary can gain foothold.

We start with the assumption that AES-CMAC is strong. We can prove that our implementation of AES-CMAC is interoperable, because there are test vectors available (and our code does produce matching results). I personally don't have the crypto chops to go into validating primitives like CMAC (or AES itself) and can only trust the lack of countervailing opinions in the literature.

We use AES-CMAC twice with 256 bits of random input to generate the intermediate key. Half of those bits come from each card, so the holder of one card must still search a 256 bit key space to obtain a 256 bit intermediate key. Even then, that intermediate key must also be run through another pair of CMAC operations before it can be tried on the encrypted material. That second set of CMAC operations require a 256 bit unknown key in addition to the 512 bits of public key information (256 bits each round).

So we can see that at every point, AES-CMAC is used with at least 256 bits of either random data or output from a previous CMAC for both the key and input (the one exception being the all-zero key for the first round). At no point is the CMAC performed on fewer than 256 bits - meaning there is no choke point where the strength is constrained.

The purpose for the second round is simply to further the diffusion of the key material for the first round, which makes it more difficult to be able to predict that a search for the missing key material in the first round has succeeded.