# Why is encrypting a key under itself dangerous?

I'm currently self-studying to try and understand more about cryptography for work. I'm on question 2.16 on A Graduate Course in Applied Cryptography .

For part a), we're given a cipher $$E$$ that's semantically secure and asked to create $$\hat{E}$$ where $$\hat{E}$$ becomes insecure when the adversary is given $$\hat{E}(k, k)$$. Since I can't control the details of $$E$$, I figure $$\hat{E}(k, k)$$ must somehow reveal the key or some key generation algorithm to the adversary, since anything else should be public already (and yet still semantically secure).

At the same time, any $$k$$ seems like it should be a valid message, so we have to explicitly know the answer to $$\hat{E}(k, k)$$ (and can't just stumble upon it when trying $$\hat{E}(k, m)$$).

To me, this seems to contradict and thus I'm stuck. What am I missing?

Update: I've thought this a little more through and may have some further ideas.

1. The definition I'm using to verify "semantic security" is that where an adversary submits $$m_1, m_2$$ and receives $$c_x$$. At this point, they should have no advantage in guessing which message was encrypted. However, when given $$E'(k,k)$$, they gain an advantage.

2. To me, this says that $$E'(k,k)$$ must somehow reveal information about k, since the scheme should be public by default (Kirchoff's Principle).

3. Suppose $$E'(k, m) = E(k \oplus m, m)$$

4. Therefore, $$E'(k,k) = E(0, k)$$. Since the decryption alg D should be public, I can decrypt $$D(0, E(0, k)) = k$$, and thus by giving the adversary $$E'(k, k)$$ I have given the key.

5. The adversary submits $$m_1, m_2$$. Upon receiving $$c_1$$, they know $$k$$, and trivially calculates which message was encrypted.

6. To adjust for the keyspace being smaller than the message space, allow for any excess bits in $$k \oplus m$$ to be truncated to $$|k|$$.

Thoughts? Does this work?

• Any key $k$ is not automatically a valid message. This won't answer your semantic security question, but you could make the same argument for the One-Time Pad, but it will be (trivially) dead wrong. – Mark Apr 16 '20 at 5:24
• – kelalaka Apr 16 '20 at 7:34
• This can be the 0 class for someone thinking in a Perfert Foward Secrecy scheme. We need more than just a $E_k(payldoad,k)$. – Crypto Learner Apr 16 '20 at 17:34

Let $$E$$ be your cipher. Consider the following cipher: $$E_{k}'(m) = \begin{cases} k & m =k\\ E_k(m) & \text{else} \end{cases}$$ I believe you should be able to reduce the security of $$E'$$ to the security of $$E$$ in a rather straightforward manner.
• There's an issue with that construction $E'$: for key $k$, there are two inputs with output $k$, thus that's no longer a block cipher with the same key and message space. After some back and forth, I see no local fix working in polynomial time. It seems that we need to construct $E'$ from $E$ in quite a different manner. One is $E'_k(m)=E_k(m)\oplus(E_k(k)\oplus k)$ – fgrieu Apr 16 '20 at 6:08
• @fgrieu $E$ was never supposed to be a block cipher. It's a generic encryption scheme. The clue is that it's supposed to be semantically secure, which a block-cipher (not being an encryption scheme and being deterministic) is not. – Maeher Apr 16 '20 at 7:13
• @Mahear: I see. Then the probability that that two inputs encipher to $k$ becomes negligible with the construction $E_{k}'(m) = \begin{cases} k &\text{if }m =k\\ E_k(m) & \text{otherwise} \end{cases}$ and what I pointed is moot. – fgrieu Apr 16 '20 at 7:24
• @fgrieu You can avoid even that by just separating the co-domains by, e.g., prefixing $0$ in the former case and $1$ in the latter. (For most common encryption schemes the ciphertext space and the key space are already disjoint, so there would be no need.) – Maeher Apr 16 '20 at 11:17