The Long-Short-Key Primitive and Its Applications to Key Security

On today’s open computing platforms, attackers can often
extract sensitive data from a program’s stack, heap, or files. To address
this problem, we designed and implemented a new primitive that helps
provide better security for ciphers that use keys stored in easily accessible
locations. Given a particular symmetric key, our approach generates two
functions for encryption and decryption: The short-key function uses the
original key, while the functionally equivalent long-key version works with
an arbitrarily long key derived from the short key. On common PC architectures,
such a long key normally does not fit in stack frames or cache
blocks, forcing an attacker to search memory space. Even if extracted
from memory, the long key is neither easily compressible nor useful in
recovering the short key. Using a pseudorandom generator and additional
novel software-protection techniques, we show how to implement
this construction securely for AES. Potential applications include whitebox
ciphers, DRM schemes, software smartcards, and challenge-response
authentication, as well as any scenario where a key of controllable length
is useful to enforce desired security properties.