[Cryptography] Elgamal Variant

[Nathaniel McCallum]

On Tue, 2015-09-08 at 10:50 -0700, Robert Relyea wrote:
> On 09/08/2015 06:15 AM, Nathaniel McCallum wrote:
> > Hi everyone!
> > 
> > I'd like some review on a small variant of Elgamal (attached).
> > Encryption should just be standard Elgamal (no modifications).
> > During
> > the decryption step, the only modification to Elgamal is using an
> > ephemeral key (X) to provide PFS (even from the server).
> Just to understand what you are trying to do... You are encrypting a 
> value on the client that the client wants to get back in the future.
> You 
> want to mask that the value from the server which is used to decrypt
> the 
> value for the client.
> 
> Normally Elgamal is used for the client to securely send data to the 
> server without who can see the data between them getting the actual
> data.
> 
> In your case it looks like you want to have the client recover an 
> encrypted key that it has stored with help from the server. I'm 
> presuming the client as discarded b^A and A, otherwise the client
> can 
> simply get K back with k=Kb^A. So... here's my comments:

Correct. The client discards b^A and A.

> 1) Under this scheme k has to say private, otherwise another
> attacker 
> could send a,k to the server and everyone will know the secret K.

Correct.

> To 
> prevent that we would need some sort of authentication, where the
> server 
> will only operate on data sent from authenticated clients, with 
> authenticated public keys.

Cryptographically, yes. This could be merged with something like SPAKE.

Alternatively, (a,k) could be encrypted to TPM or physically isolated,
etc. It would not provide the same strength, but it could be automated.

But yes, presume that the state of (a,k) between encryption and
decryption is secure.

> I think this is what you are looking at with 
> ZKPs?

Actually, the ZKPs question emerged from my reading of JPAKE. I'm not
quite sure what they prevent in that case, but I wondered if there was
benefit in either party validating that the remote party possesses the
private key for the public key.

> 2) The scheme isn't PFS, it can't be because it's a scheme for 
> recovering a key by the client in the future (which is the
> antithesis of 
> PFS. PFS only applies to stream protocols like ssh or ssl where you
> are 
> transporting data through an encrypted channel. Schemes like S/MIME
> or 
> disk encryption can't carry that burden. What your scheme does
> provide 
> is a server assisted decryption in which the server doesn't have
> access 
> to the actual secret you are trying to protect and the client can't
> get 
> the secret without aid of the server.

Sure. I was thinking PFS in regards to a passive attacker who observes
a, b, k' and k''. I'm probably using the term incorrectly.

> It doesn't matter for analysis, but are you planing on using
> discrete 
> power groups (a.la. DH/DSA), or EC groups?

EC groups.

> > On a practical level, should a and b be accompanied by ZKPs?
> > Besides
> > confirming group membership of all transferred items (and possibly
> > validating ZKPs), what other defensive checks should I perform?
> 
> The main thing is 1) if the server ever gets both a and k, game over
> for 
> secrecy from the server.

Agreed.

> and 2) if the attacker ever gets both a and k, 
> we need to make sure that the attacker can't use the server as an
> oracle 
> to recover K.
> This is tricky as the attacker can transform a into
> something else that still allows him to get b^A without the server
> knowing.
> 
> Attacker has 'a', but doesn't know A, b^A or B.
> Attacker chooses X and calculates g^X and a^X.
> Attacker sends the server a^X, k
> Server returns k'' = K/(g^X).
> Attacker multiplies g^X to recover K.
> 
> The biggest challenge here is making sure the server can prove the 
> client is who the client says it is (which probably means
> authenticating 
> the client while the client still has access to A, and then
> remembering 
> the client's public key and refusing to do any operation on a 
> non-authenticated public key.

The problem is that the authentication requires a third piece of state
along with (a, k); we'll call it S. If the state of (a, k) is
insecure, storing S in that same way doesn't add any security. You can
gain security by storing S in a different way than (a, k); but this
provides no additional security from simply storing a and k in
different ways. Since all three (a, k and S) are group members, S just
adds needless complexity.

> bob
> 
> NOTE: I'm wondering if there's a way to have the server help the
> client 
> recover b^A without exposing k at all. I can think of some options,
> but 
> I'm worried they make the job of authenticating the client harder.

I'm all ears.

Nathaniel