Thursday, September 30, 2021

[qqsojkvx] format-preserving encryption for nonce generation

Galois Counter Mode (GCM) is a popular mode of operation for AES, providing authenticated encryption.  in typical use, it has a 96 bit initialization vector (nonce) and 32 bit block counter.  security fails catastrophically if you use the same initialization vector more than once.

one way to choose the IV is randomly.  unfortunately the birthday pardox means there will likely be a collision, reuse of the same IV, within 2^48 (281 trillion) messages with the same key, which is a disturbingly small number with catastrophic security degradation on the line.

better is to put some engineering into the IV: incorporate time, sequence number, sender device identifiers.  encode time with only enough precision to separate the fastest that consecutive messages will ever be encrypted, though this might be hard to predict in advance.

however, because IV is transmitted in the clear, the data in an engineered IV leaks information about what time the messages were encrypted, how many messages have been sent, the number and organization of devices which have access to the encryption key.  these may be information you don't want an adversary to know.

therefore, encrypt the IV.  only the sender needs to know the IV encryption key (the recipient can use the encrypted IV as is).  all devices sending using the same payload encryption key must use the same IV encryption key.

note that we need to encrypt the IV, not hash it,  because hashing (to 96 bits) would result in the same problem with collisions as a random IV.

we need to encrypt 96 bits to 96 bits with no collisions.  this is a job for format-preserving encryption, e.g., NIST SP 800-38G which is built on AES.  reducing from 128 bits (AES block size) to 96 is a little bit onerous for just cycle-walking, so we do need to do the whole Luby-Rackoff Feistel network construction.

having constructed a 96-bit block cipher, use ECB mode to encrypt the engineered IV.  this encryption does not need its own IV.

is it dangerous to use the same key for encrypting payload and IV?  if an adversary correctly guesses how an IV was constructed, he or she gains a known ciphertext-plaintext pair.  however, i don't think this aids in key recovery.  perhaps you don't want to reveal to the recipient the metadata that went into constructing the IV.

No comments :