2
$\begingroup$

Update: The question below was asked before I realized that this is being done to prevent a side channel attack: https://github.com/advisories/GHSA-5p8v-2xvp-pwmc

What I am still curious about, is the math behind why this solution still works to decrypt Elgamal ciphertext.

Original Question:

libgcrypt elgamal decryption introduces a random number to perform decryption. Can anyone explain to my how this is working? I have posted the edited source code showing just the relevant operations. skey->p is the prime modulus, skey->x is the secret key of the receiver, and the encrypted message is (a,b). I don't understand the introduction of r to perform the decryption here. I would have thought t1=a^x mod p would have been sufficient. then the message could be calculated as b*t1^-1 mod p

/* We need a random number of about the prime size.  The random
     number merely needs to be unpredictable; thus we use level 0.  */
  _gcry_mpi_randomize (r, nbits, GCRY_WEAK_RANDOM);

  /* t1 = r^x mod p */
  mpi_powm (t1, r, skey->x, skey->p);

  /* t2 = (a * r)^-x mod p */
  mpi_mulm (t2, a, r, skey->p);

  mpi_powm (t2, t2, skey->x, skey->p);

  mpi_invm (t2, t2, skey->p);

  /* t1 = (t1 * t2) mod p*/
  mpi_mulm (t1, t1, t2, skey->p);


  mpi_mulm (output, b, t1, skey->p);

It is from this commit: https://github.com/gpg/libgcrypt/blob/410d70bad9a650e3837055e36f157894ae49a57d/cipher/elgamal.c

The source code starts at line 523

Update:

The most recent 1.9 release version of the file is here: https://github.com/gpg/libgcrypt/blob/LIBGCRYPT-1.9-BRANCH/cipher/elgamal.c

Starting at line 511, I can now see that there are additional lines to provide exponent blinding. What is blinding, how does it work, and why does this still provide a valid solution?

  /* We need a random number of about the prime size.  The random
     number merely needs to be unpredictable; thus we use level 0.  */
  _gcry_mpi_randomize (r, nbits, GCRY_WEAK_RANDOM);

  /* Also, exponent blinding: x_blind = x + (p-1)*r1 */
  _gcry_mpi_randomize (r1, nbits, GCRY_WEAK_RANDOM);
  mpi_set_highbit (r1, nbits - 1);
  mpi_sub_ui (h, skey->p, 1);
  mpi_mul (x_blind, h, r1);
  mpi_add (x_blind, skey->x, x_blind);

  /* t1 = r^x mod p */
  mpi_powm (t1, r, x_blind, skey->p);
  /* t2 = (a * r)^-x mod p */
  mpi_mulm (t2, a, r, skey->p);
  mpi_powm (t2, t2, x_blind, skey->p);
  mpi_invm (t2, t2, skey->p);
  /* t1 = (t1 * t2) mod p*/
  mpi_mulm (t1, t1, t2, skey->p);

  mpi_free (x_blind);
  mpi_free (h);
  mpi_free (r1);
  mpi_free (r);
  mpi_free (t2);

#else /*!USE_BLINDING*/

  /* output = b/(a^x) mod p */
  mpi_powm (t1, a, skey->x, skey->p);
  mpi_invm (t1, t1, skey->p);

#endif /*!USE_BLINDING*/

  mpi_mulm (output, b, t1, skey->p);
$\endgroup$
6
  • $\begingroup$ Deleted my previous comment because the source I linked doesnt match my pulled version. Let me track that down and I'll add to the question. $\endgroup$
    – Derek
    Sep 23 at 18:53
  • $\begingroup$ Added the specific commit. Your comment actually made me look at the git commit notes, and I see that they appear to have been trying to address an attack vector github.com/advisories/GHSA-5p8v-2xvp-pwmc but I would still like to understand how it works $\endgroup$
    – Derek
    Sep 23 at 18:57
  • 1
    $\begingroup$ It explains on line 36: "Blinding is used to mitigate side-channel attacks. You may undef this to speed up the operation in case the system is secured against physical and network mounted side-channel attacks." $\endgroup$
    – knaccc
    Sep 23 at 18:57
  • $\begingroup$ Yes, I guess I am more referring to the math that is being performed and showing why this works when there is a random r value being chosen $\endgroup$
    – Derek
    Sep 23 at 18:59
  • $\begingroup$ It's easy to see that in the blinding block of code, the $r$ value cancels out. There is a side-channel attack possible when raising $a$ to the private key $x$ which may help disclose something about $x$. Introducing a random value $r$ which is unknown to the attacker will mitigate this attack. The attack is explained here: cs.tau.ac.il/~tromer/radioexp $\endgroup$
    – knaccc
    Sep 23 at 19:20

1 Answer 1

3
$\begingroup$

The recipient has private key $x$ with the corresponding public key $Y=G^x$. To encrypt $M$ for the recipient, pick a uniformly random private key $k$, and calculate the ciphertext $(A,B) = (G^k, Y^k\cdot M)$.

Regular (non-blinded) decryption calculates $M=\frac{B}{A^x}=\frac{(G^x)^k\cdot M}{(G^k)^x}$. This works because $(G^x)^k = (G^k)^x$.

However, a side-channel attack exists where electromagnetic emanations from the exponentiation $A^x$ can leak information about the private key $x$.

In order to avoid directly performing the $A^x$ exponentiation, the blinded variant of the decryption first picks a uniformly random value $R$.

Now, we calculate $M=\frac{B\cdot R^x}{(A\cdot R)^x}=\frac{B\cdot R^x}{A^x\cdot R^x}=\frac{B}{A^x}$.

Note that we are now only ever exponentiating blinded values with our private key $x$. Since $R$ is unknown to an attacker, useful information is harder to extract by monitoring the electromagnetic emanations.

In the newer version of the code you've linked to, we use a blinded version of $x$. It is calculated as $x'=x+(p-1)r'$, where $r'$ is a uniformly random value.

This means that we end up calculating $M=\frac{B}{A^{x'}}$ instead of $M=\frac{B}{A^{x}}$ .

This works because $(p-1)$ is the size of the group generated by exponentiating group elements such as $A$. Due to the cyclic nature of the group, any multiple of the group size added to scalars (such as the private key $x$) will result in the same resulting group element value after exponentiation.

If we define $\ell=(p-1)$, then $A^x=A^{(x+\ell)}=A^{(x+\ell r')}$ for any values of $x$, $A$ and $r'$. (Note: all exponentiations in this answer are $\operatorname{mod} p$).

Therefore, when using the blinded value $x'$ instead of $x$, the result is the same even though the calculations performed by the CPU (and the resulting electromagnetic emanations) will be different.

$\endgroup$
1
  • $\begingroup$ Thank you very much for the thorough explanation. I understand it now. $\endgroup$
    – Derek
    Sep 26 at 19:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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