Encryption scheme with equivalent keys?

Question

I've long been looking for a symmetric encryption scheme (or algorithm) with equivalent keys. Let me define what I want:

1. Symmetric encryption algorithm with encryption function $E_k$ and inverse decryption function $D_k$.

2. Existence of equivalent keys. Keys $k_i \neq k_j$ will be called equivalent if $E_{k_i}(\cdot) \equiv E_{k_j}(\cdot)$ as functions and the same for the decryption operation $D_{k_i}(\cdot) \equiv D_{k_j}(\cdot)$.

3. Without knowledge of some master secret, it would be computationally infeasible to derive an equivalent key $k' \neq k$ from a key $k$.

4. With knowledge of some master secret, it would be straightforward to derive at least "many" equivalent keys (let's just say that the equivalent keys should not be scarce compared to the size of the entire keyspace, e.g. 4 equivalent keys in the entire keyspace are not enough).

5. No trivial intermediate value: of course it's trivial to come up with a scheme satisfying all of the above in which all equivalent keys map to one intermediate value (for example take 128 bit keys with an additional 16 bits at the end, then discard these as a first step before applying standard AES-128). This is perhaps the most important feature and the hardest to define. Let's say then that it requires knowledge of some master secret or some special trapdoor to reduce equivalent keys to an intermediate value.

Does anyone know of existing schemes/algorithms satisfying at least most of the requirements above, or any interesting papers on the subject, or just have some bright idea to share with us?

Answer 1

I don't know of any scheme that provides this, and it sounds tricky to build one.

Here's the closest I can come up with. Let $n=pq$ be a 2048-bit RSA modulus, $d$ be a random 2048-bit number that is relatively prime to $(p-1)(q-1)$, and $e = d^{-1} \bmod (p-1)(q-1)$. The master secret is $d$; $n$ will be baked into the description of the encryption algorithm $E$. Let $\text{truncate}(z)$ be the result of truncating $z$ to 128 bits: say, deleting the low 1920 bits and keeping the high 128 bits. Then, define $$E_k(x) = AES(\text{truncate}(k^e \bmod n), x),$$ and similarly for $D_k(x)$. In other words, the key $k$ is a 2048-bit string. To encrypt under $k$, we raise the key $k$ to the power $e$ modulo $n$ (a textbook-RSA encryption of $k$), keep the first 128 bits, and use that as an AES key to encrypt the message $x$.

Given a key $k$ and knowledge of the master secret, it is easy to derive many other keys that will be equivalent (just tweak the low bits of $k^e \bmod n$ randomly, then raise that to the $d$th power modulo $n$, and you've got an equivalent key).

This satisfies your requirements 1-4, but not requirement 5. Why do you need your requirement 5? I wonder if we might be able to weaken the requirement somehow and still get something that is sufficient for your application.

Answer 2

I think your problem might be solved by the Derived Unique Key Per Transaction (DUKPT) key generation algorithm. It doesn't work exactly the way you describe, but the keys might have the properties you're looking for.

DUKPT is used in banking terminals to generate a unique key per message. It starts with a Base Derivation Key, which is the super secret master key for the whole system. When a PIN pad terminal is to have a new key injected, the BDK is transformed using the terminal number and the encryption algorithm (generally 3DES) in a non-reversible fashion. This generates a new key called the Initial PIN Encryption Key (IPEK). The IPEK is injected into the PIN pad (along with the key's ID), which immediately runs the transformation algorithm again, creating a set of (up to) 21 keys called Future Keys (FKs), and the injected IPEK is then discarded by both the terminal and the injection machine. Each FK is used only once to encrypt a single message (containing the customer's account number and PIN), and a transaction counter is increased. That FK is then discarded by the terminal. Once the set of 21 FKs is depleted, the algorithm is run again to generate a new set of FKs.

The message sent to the host contains the key ID, the terminal number, the transaction counter, and the 3DES encrypted data. At the decrypting end, the key generation process is run however many times are indicated by the transaction counter, and the resultant FK is then used to decrypt the message.

The strength comes from the non-reversible translation step. A successful attack on the encryption algorithm is required to recover the previous set of keys. As each older set of FKs is discarded, a terminal progressively drifts farther and farther from the BDK.

Because the IPEKs are individually created for each terminal, no terminal's keys bear any relationship to any other terminal's keys. The compromise of one terminal will not yield a secret that can be used to break any other terminal's message. The compromise of one message will not yield information about any prior keys generated by that terminal. Because IPEKs are destroyed when they are turned into FKs during the initialization of the terminal, no terminal leaves the initialization facility without being at least twice removed from the BDK.

The drawback is decryption effort. The decrypting host must run through the algorithm for every set of FKs generated in the lifetime of the machine. The HSMs used in the financial industry are purpose built to run the DUKPT protocol, and will handle thousands of transactions per second.