1
$\begingroup$

This is most likely a dumb question. I'm doing a mathematical research project that overflowed a bit into cryptography. It got me thinking about something. Can the following cryptosystem work?

Let Alice and Bob share a private key $d$ using the Diffie Hellman key exchange, where $d\in \mathbb{F}_p$ for some prime $p$. If Alice wants to send Bob a message $x$, then Alice sends Bob the encrypted message $x+d$. Bob decrypts this message by subtracting $d$ (all while in $\mathbb{F}_p$, of course).

If a hacker was to crack this cryptosystem, it would essentially be the same difficulty as cracking Diffie-Hellman, right? The encryption/decryption is incredibly fast, it's just an addition/subtraction modulo $p$, and the cracking is hard. It seems that the rate of information transfer is a lot faster with this cryptosystem as opposed to RSA.

My main question is: What's the catch, if there is any? Is this a known cryptosystem?

$\endgroup$
3
  • 2
    $\begingroup$ "Is this a known cryptosystem?" --> it is one-time pad $\endgroup$
    – Mikero
    Jul 19, 2023 at 6:57
  • 1
    $\begingroup$ Well, the final modulo addition would be akin to a one time pad. The DH doesn't quite randomize the end result fully, which is why usually the DH is followed by a KDF. Also, modulo addition / subtraction is probably not as fast as XOR and might leak more information. Personally, I'd have a look if IES would not do what's required, to avoid common practical / implementation issues. $\endgroup$
    – Maarten Bodewes
    Jul 19, 2023 at 7:39
  • 1
    $\begingroup$ Well, if you do a separate DH exchange for every message, it can be viewed as a variant of El Gamal (which does multiplication rather than addition to stir in the message). In any case, there are some subtle security issues here; one nice thing about IES is that something thought through the issues and came up with ways to address them... $\endgroup$
    – poncho
    Jul 19, 2023 at 12:47

2 Answers 2

4
$\begingroup$

If a hacker was to crack this cryptosystem, it would essentially be the same difficulty as cracking Diffie-Hellman, right?

Well, the answer to that comes down to the meaning of "crack"; cryptographers give a different meaning to that then lay people do.

What a cryptographer means by "crack" an encryption system includes "find any information about the plaintext"; one such piece of information is "does this ciphertext encrypt the specific plaintext $x'$"?

Well, it turns out that, with your system, if $x \ne x'$ (that is, his guess wasn't the actual encrypted plaintext), an adversary as about a 50% chance of being able to prove it, and to a cryptography, that would constitute a "break".

How he would do that would rely on quadratic residues [1]; by observing the DH exchange (and testing whether the exchanged values are quadratic residues), the adversary can determine whether $x$ is a quadratic residue (even though he doesn't know that value). Then, when he sees the ciphertext $x+d$, he can subtract $x'$ from it (giving $d+(x-x')$), and test whether that is a quadratic residue. If $x \ne x'$, then whether that value is a quadratic residue has a 50% change of not agreeing with $x$ being a quadratic residue, and if those two things disagree, he then knows $x \ne x'$

And, for a cryptographer, that is enough to say the system is "cracked".

And, even if you use the definition of "cracked" as full message recovery:

The encryption/decryption is incredibly fast, it's just an addition/subtraction modulo $p$, and the cracking is hard.

That sounds like you are proposing to use the shared secret from a single DH exchange to encrypt multiple messages. That can be easily 'cracked' (that is, fully decrypted) depending on the contents of the message; for example, it would be straight-forward to recover both messages if they were ASCII-encoded english (with the attacker knowing nothing about the messages beyond that. He would do this by looking for the relationships between the two ciphertexts - the attack would be similar to breaking a "two-times pad".

[1]: Background: a value $x$ is a quadratic residue modulo $p$ if there exists an integer $y$ such that $x = y^2 \pmod p$. It is easy to tell, given $x$, whether it is a quadratic residue (for prime $p$).

$\endgroup$
2
  • $\begingroup$ Sorry, I should have been more clear. In my context, "crack" means to discover the original message. $\endgroup$ Jul 19, 2023 at 19:13
  • $\begingroup$ @TheBestMagician: see my additions about encrypting two different messages with the same DH shared secret $\endgroup$
    – poncho
    Jul 19, 2023 at 19:24
1
$\begingroup$

It's studied Diffie-Hellman in the multiplicative subgroup of the finite field $\mathbb F_p$, followed by encryption in $\mathbb F_p$. That is, appropriate prime $p$ and some $g\in\mathbb F_p$ are publicly agreed upon, e.g. the 3072-bit MODP Group of RFC 3526. Then sending a confidential message $x\in[0,p)$ from $A$ to $B$ goes:

  • A chooses random $s_A\in[1,p)$, computes and sends $t_A=g^{s_A}\bmod p$
  • B chooses random $s_B\in[1,p)$, computes and sends $t_B=g^{s_B}\bmod p$
  • A computes $d={t_B}^{s_A}\bmod p$, computes and sends $c=d+x\bmod p$
  • B computes $d={t_A}^{s_B}\bmod p$, computes $x=c-d\bmod p$

Absent alterations, $d$ and $x$ are the same on both sides. But there are serious security issues:

  1. The system is totally vulnerable to a Man in the Middle attack, where an active adversary $E$ impersonates $B$ w.r.t. $A$, and $A$ w.r.t. $B$, which allows to intercept $x$ unknown to $A$ and $B$, or/and alter $x$ in transit as desired.
  2. An integer $x$ can carry a limited amount of information (383 bytes for the parameters considered). For larger messages the protocol needs to be redone. If instead we reused $d$ for multiple distinct $x$, the protocol would be very insecure: if e.g. we cut a 384-byte message into a 383-byte segment and a 1-byte segment, the later can take only a few (at most 256) values, leading to 256 possible values for $d$ given the second $c$, which allows to decipher most of the first segment of the message; and for messages with some redundancy, probably the whole message.
  3. In circumstances where the adversary knows that $x$ is one of two distinct known values $x_0$ or $x_1$ (e.g. because $x$ is the name of one of two candidates in an election), an adversary merely capturing a copy of the communications can find $x$ and be sure of that for about at half of the uses of the protocol (so gets at least 75% probability of correct guess of $x$), based on quadratic residuosity. The attack goes as follows.
    • Acquire $t_A$, $t_B$ and $c$ as they are transmitted.

    • Compute $d_0=c-x_0\bmod p$ and $d_1=c-x_1\bmod p$, which are the two possible values of $d$. In the rare event that one of these $d_i$ is $0$, that can't be the correct $d$, thus we get $x=x_{1-i}$.

    • Otherwise compute the Legendre symbol for $d_0$, that is $\left(\frac{d_0}p\right)=({d_0}^{(p-1)/2}+1\bmod p)-1$, and similarly $\left(\frac{d_1}p\right)$. If they are equal (that is both $+1$ or both $-1$), we can't learn $x$, stop.

    • Otherwise, compute the Legendre symbol $\left(\frac d p\right)$ for the real $d$, using that

      • if $\left(\frac{t_A}p\right)=+1$ or $\left(\frac{t_B}p\right)=+1$ then $\left(\frac d p\right)=+1$
      • otherwise $\left(\frac d p\right)=-1$.

      [Note: if $\left(\frac g p\right)=+1$, then $\left(\frac d p\right)=+1$ and it's not necessary to intercept $t_A$ or $t_B$]

    • This $\left(\frac d p\right)$ will match one of the two $\left(\frac{d_i}p\right)$, and we get $x=x_i$.

As in any cryptosystem there are possible implementation issues, on top of the above theoretical ones.

Note: contrary to the question's claim, the system is slower than RSA at equal size of the public modulus, ignoring establishment of the public/private key pair (which in RSA is reused): it's hundreds times slower for encryption (because it uses thousands of modular multiplications rather than 17 typically in RSA), and over 3 times slower for decryption (because the Chinese Remainder Theorem can't be used with of a prime public modulus, as typically in RSA).

$\endgroup$

Your Answer

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

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