A possible problem in the implementation of DGK?

[ilyaraz]

I have trouble using the implementation of the DGK encryption protocol. Here is a snippet that does not work:

#include <ENCRYPTO_utils/crypto/dgk.h>

#include <iostream>

int main() {
  dgk_pubkey_t *pub;
  dgk_prvkey_t *prv;
  mpz_t a, b, c;
  mpz_inits(a, b, c, NULL);
  mpz_set_ui(a, 1);
  for (;;) {
    dgk_keygen(1024, 32, &pub, &prv);
    dgk_encrypt_plain(b, pub, a);
    dgk_decrypt(c, pub, prv, b);
    if (mpz_cmp_ui(c, 1) != 0) {
      std::cerr << "ERROR: 1 expected, but ";
      mpz_out_str(stderr, 10, c);
      std::cerr << " found" << std::endl;
      break;
    }
    std::cout << "OK" << std::endl;
  }
  return 0;
}

A typical output (which, of course, depends on the randomness used for the key generation) is:

OK
ERROR: 1 expected, but 73786976294838206462 found

It seems that instead of outputting 1, the decryption algorithm outputs 2^66 - 2.

[dd23]

Thanks for reporting this issue and providing this example. I can confirm that there is a problem.

We will look into this soon and post updates here.

[dd23]

After having looked at the code again, I remembered that the dgk_keygen() does not guarantee that the generated keys work all the time and might create keys that fail in some cases.
For now I will add a note to the code that should make this clear. That was an oversight and should have been there already.

We have worked around that problem in createKeys() by running KEYTEST_ITERATIONS many test encryptions/decryption to verify if a keypair is good. You can simply do the same thing in your code for now.
Also, since key generation is rather complex we store good keypairs in files and later on simply read them from disk.
Have a look at dgk_storekey() and dgk_readkey() for this.

Eventually the testing for good keys will be moved to the dgk_keygen() method. Until then I will keep this issue open.

[ilyaraz]

OK, thanks!

As a temporary solution, I just encrypt/decrypt 1 and re-generate the key pair until it does it correctly.

[dd23]

I guess it's better to run this test with random values and several iterations and then testing an encryption of 1 on top.

Also, keep in mind that this code is definitely not intended for anything in production. There might be bugs and it's certainly not side-channel free.