2
$\begingroup$

I have a need for the following encryption properties: $f(g(v_\text{plaintext}) = v_\text{ciphertext}$ needs to be decryptable by $f^{-1}(g^{-1}(v_\text{ciphertext}))$ and $f$ and $g$ need to be different. The idea goes like this.

  1. A user is going to encrypt some plaintext (DB credentials) with a private key they control. $g(v_\text{plaintext})$

  2. A server is going to encrypt $g(v_\text{plaintext})$ with a private key that it controls. $f(g(v_\text{plaintext})) = v_\text{ciphertext}$.

  3. Sometime in the future the server will ask the user to decrypt using their private key and send the result back to the server. $g^{-1}(v_\text{ciphertext})$.

  4. Server will take the result from the previous step and decrypt the ciphertext: $f^{-1}(g^{-1}(v_\text{ciphertext})) = v_\text{plaintext}$.

The reason that I find this procedure desirable is that:

  1. the DB credentials ($v_\text{plaintext}$) are never sent over the wire unencrypted
  2. the owner of the DB credentials is able to encrypt on their side (client-side using $g$).

Anyone know of a set of cryptographic primatives that would get me there?

$\endgroup$
5
  • $\begingroup$ Note that the first sentence and (4) differ in order, please fix (I presume that (4) is correct?). $\endgroup$
    – Maarten Bodewes
    Aug 19 at 12:39
  • $\begingroup$ Say that you derive 2 separate symmetric keys, then you can use those to create two key streams and XOR the ciphertext together. You can then decrypt in any order. Would that suffice? $\endgroup$
    – Maarten Bodewes
    Aug 19 at 12:43
  • 1
    $\begingroup$ @MaartenBodewes: no, XOR would not suffice - someone listening in to all three exchanges would be able to recover the secret $\endgroup$
    – poncho
    Aug 19 at 12:48
  • $\begingroup$ @MaartenBodewes Re the wrong order in the first sentence. You were exactly right! I have edited, now. Sorry for the confusion! $\endgroup$ Aug 19 at 13:05
  • $\begingroup$ @MaartenBodewes If I understand your initial suggestion then it implies that person who control's the server's symmetric key (for $f$) would have the ability to encrypt the plaintext. But, I don't want to hand the administrator of the server the plaintext. I want to provide him with an encrypted copy of this plaintext using a key that I control (for $g$). Now, the server application will have the plaintext on decryption at runtime. Let's assume that the encryption operation is performed manually - we don't want to share plaintext with 3rd parties - also assume the decryption is uninspectable. $\endgroup$ Aug 19 at 13:07

1 Answer 1

2
$\begingroup$

Anyone know of a set of cryptographic primatives that would get me there?

The Pohlig-Hellman cipher [1] would appear to be the right general direction.

This algorithm is a secret key algorithm, and is done as follows: there is a public prime $p$, and each side has a secret key $a$ (or $b$ for another secret key held by a second party).

Encryption is simple, $E_a(m) = m^a \bmod p$, to decrypt, you compute $a^{-1} \bmod {p-1}$ and then compute $D_a(c) = c^{a^{-1}} \bmod p$

This encryption has the property that $E_a(E_b(m)) = E_b(E_a(m))$ (because they're both $m^{ab} \bmod p$), and so you can decrypt in any order (just like you asked for).

And, it also has the property that someone who hears $E_a(m), E_b(m), E_a(E_b(m))$ cannot recover $m$; I suspect this is an important property in your scenario.

Your protocol design would appear to work with a symmetric cipher such as Pohlig-Hellman (because in your protocol, the user does all the $g$ operations and the server does all the $f$ operations). If you decide you need an asymmetric one (that is, one where someone can encrypt with a public key, and decrypt with a private one), the obvious way to do this would be to extend Pohlig-Hellman with an Integrated Encrypted System approach; also have a public generator $g$, and have a private key be a value $x$, and the public key $g^x \bmod p$. To encrypt a value $m$, the encryptor:

  • selects a random value $y$
  • computes $g^y \bmod p$ and $(g^x)^y \bmod p$
  • computes $z = \text{kdf}( (g^x)^y \bmod p )$ (using a key derivation function with a long output, such as SHAKE)
  • outputs the ciphertext $g^y \bmod p, m^z \bmod p$

The decryption algorithm is obvious. And, if the later Pohlig-Hellman operations (either symmetric or asymmetric) only modify the second component and leave the first component untouched, you retain the commutativity property.


[1]: Actually, it appears to be rather hard to find papers on this - all searches on Pohlig-Hellman tend to point you to the discrete log algorithm by the same inventors. You could search on the 'Shamir Three Pass' algorithm, which is based on essentially the same idea...

$\endgroup$
9
  • $\begingroup$ I'm studying this response, now. It will take me some time to digest. I'll default to accepting if I don't think this is wrong after mulling it over for an hour or two (that is, if I don't understand but don't doubt that it's true then I'll accept). But, on its surface this looks like the right approach. The security of this approach relative to the XOR approach suggested in my question's comments is due to the hardness of solving the discrete log problem relative to the hardness of inverting XOR operations. Is that right? $\endgroup$ Aug 19 at 13:13
  • 1
    $\begingroup$ @fuzzybear3965: actually, it's the Diffie-Hellman problem, not the discrete log - otherwise, yes, that's right $\endgroup$
    – poncho
    Aug 19 at 13:14
  • $\begingroup$ All "sides" (owners of a and b) have access to Ed25519 private keys. Is it possible to use these for a and b? I ask because Ed25519 are "signature keys" and we use these for verifying identity but not encrypting data. We have an SDK which uses these keys but it exposes no "encryptData" method only "sign" methods. $\endgroup$ Aug 19 at 13:19
  • $\begingroup$ Considering your edit: The "Pohlig-Hellman cipher" is not the same as en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm ? $\endgroup$ Aug 19 at 13:26
  • 1
    $\begingroup$ @fuzzybear3965: it's not the same - the Wikipedia page talks about the discrete log algorithm... $\endgroup$
    – poncho
    Aug 19 at 13:27

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.