3
$\begingroup$

If we were define such a cipher:

  • A reversible function that would accept a message $M$ and an initialization vector $\text{IV}_1$ $\operatorname{map}(\text{IV}_1, M)$ which can map an input $M$ to a random prime $p_1$
  • A key derivation function $\operatorname{kdf}$ with a similar blueprint, with key $k$ and initialization vector $\text{IV}_2$ where $\operatorname{kdf}(\text{IV}_2, k) = p_2$
  • The encryption can then be defined simply as $p_1 . p_2 = C$
  • Decryption would then be $C / \operatorname{kdf}(\text{IV}_2, k) = C / p_2 = p_1$ and $M = \operatorname{map}^{'}(\text{IV}_1, p_1)$

I see this would be very similar to OTP; and can it be seen secure considering the idea is almost the same (and assuming factorization is hard)

Intuitively I can speculate, it might pave some way for some commutative and homomorphic properties as well...

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ I think "initialization vector" is more accurate than "salt" in this context $\endgroup$
    – Ella Rose
    Jul 29, 2018 at 20:47
  • $\begingroup$ @EllaRose you're absolutely right. I've edited it (not sure if $\text{IV}_2$ should have been a $\text{salt}$ in the context of $\operatorname{kdf}$ though) $\endgroup$
    – zetaprime
    Jul 29, 2018 at 20:57

3 Answers 3

Reset to default
5
$\begingroup$

This method of encryption is described in Section 9.5.1 of Mathematics for Computer Science by Lehman, Leighton & Meyer. They attribute this encryption technique to Alan Turing, but they say that they are working from just a textual description and are not sure exactly how to interpret the specific algorithm he had in mind. I don't know what their source is, and they don't mention a reference.

Unfortunately it is totally insecure. If the adversary ever sees two ciphertexts $c_1, c_2$ that were encrypted under the same key, then that key can be recovered as $\gcd(c_1,c_2)$. Security is not obviously broken if the key is used to encrypt only one message, but I don't think the scheme offers any advantage over one-time pad (it has large ciphertext expansion and only computational security).

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ If the $p_1$ and $p_2$ values are randomized (which the misnamed $\text{salt}$ values indicate that they are supposed to be), then taking gcd will not work. Granted, $\operatorname{kdf}$ or $\operatorname{map}$ could be designed in such a way that it might still be broken. $\endgroup$
    – Ella Rose
    Jul 29, 2018 at 20:44
  • $\begingroup$ I totally agree, the same prime would never be used for encrypting again. That's the reason why I also thought of randomizing it, maybe that's what Turing had in his mind ;) $\endgroup$
    – zetaprime
    Jul 29, 2018 at 21:02
6
$\begingroup$

This answer is supplementary to the one provided by Mikero.

Assuming that the $\operatorname{map}$ and $\operatorname{kdf}$ functions are properly randomized and provide appropriate output (e.g. large enough to be non-repeating), then no two ciphertexts will share common factors. So being able to use $\operatorname{gcd}$ to break ciphertexts is not applicable in the basic form of the proposal.

I see this would be very similar to OTP; and can it be seen secure considering the idea is almost the same (and assuming factorization is hard)

Emphasizing the point raised by Mikero: This is not a one-time pad, as it lacks information-theoretic security.

An efficient algorithm for factoring can recover $p_1$ from $p_1 p_2$ and compute $M$ by inverting the $\operatorname{map}$ function.

An adversary that knows or can guess $M$ can recover $p_2$ from the ciphertext by computing $p_1 = \operatorname{kdf}(\text{IV}_1, M)$ and then $p_2 = \frac{p_1 p_2}{p_1}$. Since each $p_2$ is randomized, this should not help them to decrypt other ciphertexts that they do not already know the plaintext of. However, it would allow them to mount an attack on $\operatorname{kdf}$.

Intuitively I can speculate, it might pave some way for some commutative and homomorphic properties as well...

It is conceivable that the ability to meaningfully multiply ciphertexts could be worked into the scheme. However, it would require a very clever $\operatorname{map}$ function - one which would also need to preserve the multiplication operator on it's own outputs.

The ability to add ciphertexts together appears to be barred by the requirement for each "key factor" ($p_2$) to be different. Something like $p_1 p_2 + p_3 p_4$ will not let you decrypt to $p_1 + p_3$ by dividing by $p_2$ and/or $p_4$

As for commutativity, decryption could be commutative, but encryption can't successfully be performed as such.

For decryption: $$\frac{p_1 p_2 p_3}{p_2} = p_1 p_3\\\frac{p_1 p_3}{p_3} = p_1\\\frac{p_1 p_2 p_3}{p_3} = p_1 p_2\\\frac{p_1 p_2}{p_2} = p_1$$

Clearly, the sequence of factors that you divide by has no influence on the output.

However, for encryption, let's try the Three-pass Protocol (one of the things you might want a commutative cipher for): $$c_0 = p_1 p_2\\c_1 = c_0 p_3 = p_1 p_2 p_3\\c_2 = \frac{c_1}{p_2} = \frac{p_1 p_2 p_3}{p_2} = p_1 p_3\\p^{'}_1 = \frac{c_2}{p_3} = \frac{p_1 p_3}{p_3}$$

An attacker who has seen $c_0$ and $c_1$ can compute $\operatorname{gcd}(c_0, c_1)$ to recover $p_3$. When they obtain $c_2$, they can then recover $p_1$ by dividing by $p_3$.

This demonstrates that the proposal does not provide a secure commutative cipher.

Improve this answer
$\endgroup$
2
$\begingroup$

This isn't a direct answer to the question, because the other answers have that well in hand. However, I thought it may be helpful to add a note about why one time pads work, and why this isn't one.

There is a common perception that a OTP is just a function where the key is as long as the plaintext. However, that doesn't work. For a very easy scheme to see why, consider just concatenating the plaintext and key to make the ciphertext.

Instead, while it's true that the key must be at least that long†, it's more helpful to think of it as a function where the key is as long as the ciphertext. The security comes from the fact that, if you have a ciphertext, there is a key available which takes you back to any possible plaintext. Therefore you can't learn anything about which plaintext it came from without the key. Suppose that you know your adversary is going to send one of two things: "agree" or "never". Under a OTP even with the ciphertext, you still know it's one of those two things but you still can't tell which.

In this proposal, since the multiplication of two n bit numbers produces a 2n bit number, the ciphertext is clearly significantly longer than the key. It's not so obviously broken as concatenating the two, but the property of being able to get back to any possible plaintext is missing. In particular even if you only send one message under this key, it becomes possible to check essentially "Is this a multiple of 'agree'?". Factorisation may be a moderately hard problem, but checking a single‡ candidate factor definitely isn't!

† It's more a case of the ciphertext must be at least as long as the plaintext to be long enough to hold the message, and so of course so must the key!

‡ There is some confusion introduced by the unstated details of your KDF and the IVs and such. In the worst case this would require exhausting over the IVs, but the substance of the attack is the same.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.