Score:1

What's the catch with this Diffie-Hellman based cryptosystem?

bt flag

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?

us flag
"Is this a known cryptosystem?" --> it is one-time pad
Maarten Bodewes avatar
in flag
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](https://crypto.stackexchange.com/q/9418/1172). Also, modulo addition / subtraction is probably not as fast as XOR and might leak more information. Personally, I'd have a look if [IES](https://en.wikipedia.org/wiki/Integrated_Encryption_Scheme) would not do what's required, to avoid common practical / implementation issues.
poncho avatar
my flag
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...
Score:4
my flag

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$).

TheBestMagician avatar
bt flag
Sorry, I should have been more clear. In my context, "crack" means to discover the original message.
poncho avatar
my flag
@TheBestMagician: see my additions about encrypting two different messages with the same DH shared secret
Score:1
ng flag

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).

I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.