search

cfrg / draft-irtf-cfrg-opaque

The OPAQUE Asymmetric PAKE Protocol
https://cfrg.github.io/draft-irtf-cfrg-opaque/draft-irtf-cfrg-opaque.html
Other
99 stars 21 forks source link

Curve25519 support #238

Closed daxpedda closed 1 year ago

daxpedda commented 3 years ago

We have a use case where a HSM is used to store the server private key. Currently almost all HSMs use the PKCS#11 standard, which doesn't have support for ristretto255 + DH. It is my understanding that OPAQUE had official support for X25519 in the past but dropped it in favor of ristretto255.

Is it possible to elaborate on the reasons for that decision? Is it still in scope to re-introduce it and provide test vectors?

I believe that OPAQUE already does support using any algorithm as long as it does fulfill the stated security requirements, but official support would still be very favorable.

It should be noted that HSMs can use P256 instead, which is already officially supported by OPAQUE, but many, including us, would like to use Curve25519 when possible.

stef commented 3 years ago

you need a modulo inverse function to implement opaque, no x25519 implementation i know of supports this. As the the co-author of the pkcs#11 v3.0 i'm sure we did not add neither ristretto, nor support for modulo inverse to it.

stef commented 3 years ago

this post explains why curve25519 cannot be used: https://moderncrypto.org/mail-archive/curves/2017/000906.html

daxpedda commented 3 years ago

I'm a bit confused, maybe there is a misunderstanding here. It is my understanding that the inverse function is only needed on the client for unblinding, the only thing the HSM protects is the server private key, nothing else, PKCS#11 support isn't needed.

I'm no cryptographer, so please forgive my naivety here, I was simply using scalars for OPRF, I didn't realize that using X25519 has any connection to the OPRF part and therefore requires the use of field elements.

EDIT: Apparently I didn't properly understand what OPRF is, now that I looked at it closer, I believe what I have done was some kind of hybrid approach, where I was using ristretto255 for OPRF, but X25519 for the DH key exchange. I can understand if something like this might not be in scope for official support by OPAQUE, if that is the case, this can be closed.

bytemare commented 3 years ago

FTR, OPRF in a nutshell:

Even though the modular inverse operation is only needed for the OPRF client, the whole operation needs to happen in the same group. That's why you also need it on the server.

That said, using the external mode, allowing the OPRF and AKE to have different algorithms, you can still use the HSM to store the server's AKE private key. This spec, though, defines OPAQUE-3DH, which uses the same group in both.

daxpedda commented 3 years ago

Even though the modular inverse operation is only needed for the OPRF client, the whole operation needs to happen in the same group. That's why you also need it on the server.

I am assuming the reason why it has to happen in the same group is because the spec says so, I can't see where the connection is otherwise. But, why does "the whole operation needs to happen in the same group" imply that the modular inverse operation is needed on the server? The only operation I can see the server needs is the evaluation, but the secret scalar used here isn't the private key, as far as I understand. Did I misunderstand something?

That said, using the external mode, allowing the OPRF and AKE to have different algorithms, you can still use the HSM to store the server's AKE private key. This spec, though, defines OPAQUE-3DH, which uses the same group in both.

I'm still confused about how the OPRF and AKE in internal mode don't allow different algorithms, I still can't see any connection. I guess, if what I'm proposing turns out to be possible in the first place, my proposal would include using different algorithms for OPRF and AKE to be supported in internal mode.

My understanding of all this is very surface-level, I might be missing something very obvious here, thank you for all the explanations.

bytemare commented 3 years ago

But, why does "the whole operation needs to happen in the same group" imply that the modular inverse operation is needed on the server?

The modular inverse is not needed on the server. Regarding "the whole operation needs to happen in the same group", I was a bit hasty: do you think you can use Ristretto255 on the client, and Curve25519 on the server? Or run the whole on the prime order subgroup of Curve25519?

The only operation I can see the server needs is the evaluation, but the secret scalar used here isn't the private key, as far as I understand.

We call the OPRF server key a "private key" as well (but it's not the same as the one of the AKE). That's the one you'd like to use within the HSM, correct?

I'm still confused about how the OPRF and AKE in internal mode don't allow different algorithms, I still can't see any connection. I guess, if what I'm proposing turns out to be possible in the first place, my proposal would include using different algorithms for OPRF and AKE to be supported in internal mode.

I don't know why I thought it had to. The spec says it should, and recommends using the VOPRF suites. Of course, you are free to use any curve for the AKE, regardless of what the OPRF uses. You are right, my apologies 🙏

My understanding of all this is very surface-level, I might be missing something very obvious here, thank you for all the explanations.

Your questions and observations are totally valid and interesting :) please continue! We have tunnel vision, so external input is very helpful!

daxpedda commented 3 years ago

do you think you can use Ristretto255 on the client, and Curve25519 on the server? Or run the whole on the prime order subgroup of Curve25519?

What I am proposing is to run the AKE with X25519 on both sides and the OPRF with ristretto255 on both sides, at least after your input :smile:.

We call the OPRF server key a "private key" as well (but it's not the same as the one of the AKE). That's the one you'd like to use within the HSM, correct?

I believe this is the source of all misunderstandings here, I didn't realize that the OPRF server key may also be called "private key", this explains @stef's answer. I was actually planning to store the AKE key on the HSM, not the OPRF key, but that's only because it seems impossible to use OPRF with HSMs right now, otherwise I would store both.

Your questions and observations are totally valid and interesting :) please continue!

I appreciate it, very encouraging :smiley:.

I'm drawing a lot of conclusions here that might be incorrect, so I would like to elaborate on the goal of what I am trying to do here instead of possibly focusing on the wrong solution.

The final goal is to secure OPAQUE with the help of an HSM and Curve25519. Currently HSMs don't support ristretto255, for both DH or scalar multiplication for OPRF. This leads me to my first assumption:

As far as I understand now, this isn't something the OPAQUE spec disallows:

The spec says it should, and recommends using the VOPRF suites. Of course, you are free to use any curve for the AKE, regardless of what the OPRF uses.

What this issue is about is to confirm my assumptions and to ask for official support in the OPAQUE spec.

stef commented 3 years ago
  • Storing the AKE private key on an HSM does provide additional security to OPAQUE, even though the OPRF secret key isn't secured through the HSM
  • X25519 can be used for AKE
  • (?) X25519 can still be used with 3DH
  • ristretto255 can still be used for OPRF

yes to all. actually i did add 3dh to pkcs#11 back in v3.0 (and also the double ratchet). i'm not a member of the pkcs#11 wg anymore, but i can ping them to consider adding ristretto255 to a next revision (but that might take some time...)

stef commented 3 years ago

btw even i was confused back then when i first read one of the early drafts about this - to me - strange terminology of the oprf having a keypair: https://github.com/cfrg/draft-irtf-cfrg-opaque/issues/54 - turns out this is a thing for voprfs.

daxpedda commented 3 years ago

i'm not a member of the pkcs#11 wg anymore, but i can ping them to consider adding ristretto255 to a next revision (but that might take some time...)

That would be great nonetheless! Even though it is unlikely that HSMs will implement it, even if it is in the PKCS#11 spec, unless ristretto255 becomes more popular.

bytemare commented 3 years ago

Ha ! I understand the confusion better now :)

Indeed: the "server's OPRF private key" is the secret part of the VOPRF keypair, and is totally unrelated to the server's AKE key pair.

I was actually planning to store the AKE key on the HSM, not the OPRF key, but that's only because it seems impossible to use OPRF with HSMs right now, otherwise, I would store both.

A different OPRF key is used for every client. Currently, the spec derives these individual keys using a stored secret seed, common to all, and the user id, thrown into hash-to-scalar. I don't know how nicely HSM play with lots of keys to store to support a very large user pool.

I appreciate it, very encouraging 😃.

🙌

Storing the AKE private key on an HSM does provide additional security to OPAQUE, even though the OPRF secret key isn't secured through the HSM X25519 can be used for AKE (?) X25519 can still be used with 3DH ristretto255 can still be used for OPRF

Yes to all, as well :)

What this issue is about is to confirm my assumptions and to ask for official support in the OPAQUE spec.

It's not because curves are not in the list that they are not supported. No spec says that they are not supported. Re-reading the specs, though, I understand that they might be misleading, and could indeed need some text to make it clearer. Any idea for wording that would make that more clear?

i'm not a member of the pkcs#11 wg anymore, but i can ping them to consider adding ristretto255 to a next revision (but that might take some time...)

Oh, that would be sweet! Given the growing popularity of r255 and d448, this is definitely a nice thing to consider for the next version :)

daxpedda commented 3 years ago

A different OPRF key is used for every client. Currently, the spec derives these individual keys using a stored secret seed, common to all, and the user id, thrown into hash-to-scalar. I don't know how nicely HSM play with lots of keys to store to support a very large user pool.

They don't, I was actually talking about storing the secret seed. Another misuse of terms from my side here. In any case, I don't believe that HSMs will support VOPRF key deriviation from a stored seed anytime soon and I don't even know if that actually increases security when the AKE private key is already stored.

It's not because curves are not in the list that they are not supported. No spec says that they are not supported. Re-reading the specs, though, I understand that they might be misleading, and could indeed need some text to make it clearer. Any idea for wording that would make that more clear?

To me it was actually clear enough, I just got a bit unsure through the misunderstandings in this issue. It would be great of course if OPAQUE specifically mentions the use-case of HSMs:

I understand if this isn't really in scope for OPAQUE. I'm willing to go into more detail about wording of course if it is in scope.

bytemare commented 3 years ago

It would be great of course if OPAQUE specifically mentions the use-case of HSMs

What would you like to see in the spec? It's intentionally high-level enough so implementors use the keys however they want.

The Group mode identifies the group used in the OPAQUE-3DH AKE. This SHOULD match that of the OPRF. For example, if the OPRF is OPRF(ristretto255, SHA-512), then Group SHOULD be ristretto255.

This may need some sort of exception.

SHOULD is not a mandatory statement. Strictly speaking, an exception is relative to a rule, but there's no rule imposed here. Implementors are free to compose their cipher suite :)

Test vectors for X25519 AKE + ristretto255 OPRF would be nice

@chris-wood @kevinlewi: here's a request to have Test vectors for X25519 AKE + ristretto255 OPRF. What do you think?

I understand if this isn't really in scope for OPAQUE. I'm willing to go into more detail about wording of course if it is in scope.

Any ideas are welcome :)

daxpedda commented 3 years ago

It would be great of course if OPAQUE specifically mentions the use-case of HSMs

What would you like to see in the spec? It's intentionally high-level enough so implementors use the keys however they want.

The spec already recommends specific configurations, it would be helpful if the use-case for HSMs is covered in the spec. Adding an additional recommended configuration in the case of HSMs would help people like me find a correct approach and encourage implementors to cover this use-case.

If a recommendation under "Configuration" seems to much, I believe a mention in "Security Considerations" seems appropriate.

I'm gonna attempt to write down some wording I have in mind, I'm willing of course to make a PR, keep in mind I'm very new to this, IETF and cryptography in general, and english is my second language.

# AKE Private Key Storage

The AKE private key can be securely stored in a HSM or similar. Upon compromise of the OPRF seed and client
envelopes, this would prevent an attacker from using this data to mount a server spoofing attack (someone more
knowledgeable can insert actual security benefits here). The following configurations are RECOMMENDED for a
scenario like this:
- OPRF(ristretto255, SHA-512), HKDF-SHA-512, HMAC-SHA-512, SHA-512, Scrypt(32768,8,1), internal, X25519
- OPRF(P-256, SHA-256), HKDF-SHA-256, HMAC-SHA-256, SHA-256, Scrypt(32768,8,1), internal, P-256

Supporting implementations need to consider allowing separate AKE and OPRF algorithms and not requiring access
to the AKE private key bytes, only support for generating shared keys for 3DH is necessary.
chris-wood commented 3 years ago

Sorry for chiming in late here! Test vectors with a configuration where the OPRF and AKE groups are different would be great. I'm happy to add this. Shall we use this issue to track adding that, along with some discussion around the AKE-key-in-HSM use case?

bytemare commented 3 years ago

Let's separate tracking the HSM thing in a separate issue

bytemare commented 3 years ago

@daxpedda #279 adds your suggestion, I reworded it a bit. I'd be glad to have your feedback :)

daxpedda commented 3 years ago

Just saw it, thank you!

bytemare commented 2 years ago

@daxpedda for clarification: is X25519 desired solely as a group within 3DH, or as a different AKE?

daxpedda commented 2 years ago

Isn't the AKE the group used within 3DH?

daxpedda commented 2 years ago

Specifically the point is to protect the server_private_key, which as far as I know is used in 3DH. The one mentioned here: https://www.ietf.org/archive/id/draft-irtf-cfrg-opaque-07.html#section-5-1

bytemare commented 2 years ago

The AKE is the authenticated key exchange protocol in OPAQUE (chich is OPRF + AKE). Different protocols can be used as AKE, such as HMQV, 3DH, and SIGMA, as long as they are compatible with the protocol flow (3-messages, client-initiated, etc.).

This spec focuses on 3DH as an AKE.

You can use a bunch of different elliptic curve groups for 3DH (like ristretto255, p-256, etc.).

X25519 is an ECDH key exchange atop Curve25519. I just want to make sure we're talking about the same thing, as I see that you and Kevin used that group within 3DH, and not an authenticated version of it in place of 3DH.

daxpedda commented 2 years ago

Ah! I see the confusion, forgive me, I'm not that good with all the terminology. I didn't mean X25519 in the sense of the ECDH key exchange, I just meant Curve25519!

@daxpedda for clarification: is X25519 desired solely as a group within 3DH, or as a different AKE?

Desired solely as the group within 3DH!

bytemare commented 2 years ago

Thanks for the clarification :)

On a side note, do you suggest we should make the document clearer regarding the terminology?

daxpedda commented 2 years ago

I don't believe so, I think the document can be clearer in some places which group is actually meant, the AKE or OPRF, even if it can be derived.

I can spend some time later on and find some places where it wasn't perfectly clear to me.

bytemare commented 2 years ago

That would be great, thanks!

daxpedda commented 2 years ago

I tried to re-read the spec a bit and be as skeptical as possible. I'm already much more comfortable with it then in the past, so it's hard to judge what I remember was confusing. The thing I remember was that every time I read private_key or public_key somewhere I wasn't sure which group it was talking about. For example: https://www.ietf.org/archive/id/draft-irtf-cfrg-opaque-07.html#section-5.1-3 Looking at the vicinity of that part of the text, there is no mention of AKE, so I think for newcomers it might take extra effort to keep track of all of it.

https://www.ietf.org/archive/id/draft-irtf-cfrg-opaque-07.html#section-4-8 Is a good example, it says everywhere what key it means. https://www.ietf.org/archive/id/draft-irtf-cfrg-opaque-07.html#section-6.1 6.2 & 6.3 also are missing direct descriptions.

armfazh commented 2 years ago

One central question is whether we can instantiate a 3DH AKE using either directly X25519 DH, or safely using the x-only arithmetic of Curve25519?

As a side note, the 3DH with P-256 can use only the x-coord of points.

Also, it seems that instantiating an OPRF with Curve25519 is possible too.

kevinlewi commented 1 year ago

Hey all, just to check back in here. Had an offline discussion with @chris-wood, and we are thinking of closing this issue without addressing it (without adding X25519 test vector support), unless there is still interest in keeping this in scope of the spec.

Curious to hear what your thoughts are @daxpedda !

daxpedda commented 1 year ago

Not much has changed on the HSM side of things since then: Ristretto255 support does not exist.

So I think there are two use-cases for adding test-vectors for Curve25519:

If it's decided that adding Curve25519 is still not in scope, I think adding at least a test vector mixing a NIST curve with Ristretto would at least cover the second point.

(I stopped using "X25519" to avoid any confusion about the key-exchange algorithm, which is not the topic here. Also changed the title.)

chris-wood commented 1 year ago

@daxpedda just to clarify, do you still have a use case for this? The original issue was filed with the statement that there did exist a use case to drive this. If that's still the case, we'll get this done.

daxpedda commented 1 year ago

Oh yes, absolutely. When OPAQUE is accepted by the IETF it is still our intention to use this with HSMs. We have a lot of clients who prefer Curve25519/448 over the NIST prime ones.

EDIT: just for clarification, HSMs are perfectly usable with P-256/384/521.

kevinlewi commented 1 year ago

Hi folks, I wanted to bring up this issue again after some more consideration. If we do decide to include test vectors for this, then another related question is, should we add the ristretto255+x25519 setting to the list of "recommended" configurations for OPAQUE?

I think it is too niche to be considered on the list of recommended configurations. But if we don't recommend it, then it seems odd to me that we would have a set of test vectors for it.

Therefore, I think it would be cleaner if we just omitted the test vectors for this, and we closed this issue + associated PR.

Separately, @daxpedda, we can certainly still support the x25519 implementation in the opaque-ke library, and will continue with the PR on that repo. I originally felt that we should not include it because it would not be part of the spec, but I've come around to and changed my mind on that, since I see the value in supporting more configurations beyond what the spec recommends. But do let me know what your thoughts are on this, as I think it would be a relief for me at least to not have to support the x25519 test vectors in the spec.

Thanks!

chris-wood commented 1 year ago

I think it is too niche to be considered on the list of recommended configurations. But if we don't recommend it, then it seems odd to me that we would have a set of test vectors for it.

I don't agree with this. It's fine to include test vectors for things that aren't recommended.

Therefore, I think it would be cleaner if we just omitted the test vectors for this, and we closed this issue + associated PR.

I don't think this is the best outcome. Work on this issue revealed what I consider to be an editorial bug in the spec, in that we define 3DH -- literally three Diffie Hellman operations -- using prime-order groups, rather than Diffie Hellman operations! I think it would be much cleaner if, for example, we were to replace the prime-order group-based AKE description with one that's based on DH. X25519 would then fit naturally right in, as would ristretto255 and all the other prime-order groups.

daxpedda commented 1 year ago

As an implementor, I appreciate any help the specification can provide, test vectors are one of those things. Though I completely understand that the specifications job is not to cover everything an implementor might want. So this is an issue of scope, which I will squarely leave in your very capable hands.

I think it is too niche to be considered on the list of recommended configurations.

As far as I'm aware, the only use-case for this configuration is using an HSM with a non-NIST curve. Using HSMs in general is already pretty niche I would say.

kevinlewi commented 1 year ago

Thanks for chiming in @daxpedda and @chris-wood with your comments -- I've updated #404 with a couple of changes which should be compatible with the opaque-ke implementation. Should be ready for review!