Subject: [Curdle] Encryption in CFRG curves, RFC 8037 not sufficient

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 30 Aug 2017 13:22:38 -0400

I am currently working on making Mesh/Recrypt work. This is basically three
key public key cryptography. Instead of having one key to encrypt and one
to decrypt, we have one to encrypt and the decryption key is split into two
that have to BOTH be applied for decryption.

OK so for the purposes of this issue, the encryption is exactly the same as
for two key DH.

Since the world is moving to ECDH, I am writing my code using
Diffie-Hellman key agreement which RFC7516 doesn't really support. So I
extended the format as follows:

Sender:

* Generates a random session key
* Encrypts message under the session key

* jwk = a new ephemeral generated per key exchange.
* kid = identifier of group public key which is the UDF fingerprint of the
key itself.
* Performs a key exchange against the group public key to create the key
agreement value.
* Performs HKDF as specified in RFC 5869 to obtain an encryption key
* encrypted_key =  Key wrapping as specified in RFC 3394 to encrypt the
session key

This produces the following JSON package:

{
  "protected": "
ewogICJlbmMiOiAiQTI1NkNCQyJ9",
  "iv": "
zLuTMmoOJHUp68hl8eB6Fw",
  "recipients": [{
      "Header": {
        "kid": "MDQIW-GSFHP-YFE5E-O6ITK-3EUGH-45BX7",
        "jwk": {
          "PublicKeyDH": {
            "kid": "MAQ74-DJJMN-Y4GJ6-ZDXR5-A2SV7-5JGEB",
            "Domain": "YE6bnq1MlX5ojaJto6PLP_PEwA",
            "Public": "
hO-l2oeNCKGubSGpSjcwA9j1VmsF_CboNMEwqhzv4PlByfraUGTMrYdZxbrpVIpP
5-60Jysf5VXTdURyviEOu-dDjVVpOddAjB6jZSVSzxIiqb8mcbCnpvJRGMDGx6WV
tOE6yF7MX-2pXPO5Jp7c-vaKYcV0gVOTmO4FhGC757xncmASBJWqxRZJErfCkWku
HCb1sFXXJX0IbvxJR6-GF-azFuSufcj7j1ACuFNR5Ejvyn_kVgm6YcckdYM4lw6d
TndMNjb8fQn0_giaK4USRo6B27WsNx6wjNiKD3OIA05NgpM2HPB4RZ1rvJaugH0J
bgWEalUCQDS3ME4THMiMxgA"}}},
      "encrypted_key": "
NfsohR3nHvwlopACABCQIdDIU1mZf5BLwWRThdDTSA0UIzST3NPyuA"}],
  "ciphertext": "
-p2gBUNot_ecZQalDmkyS-I1M5UxB4_6X0pPlojPM58"}

OK so what is wrong?

Well jwk is supposed to be the key identifier of the recipient key for a
start. There is no way to express the DH key exchange properly in JOSE
because it assumes that the Key Exchange is performed using symmetric or
public key encryption. DH is neither, it is a key exchange.

RFC 7818 is no help:
https://tools.ietf.org/html/rfc7518#section-4.6

So as I was looking into this, I had the idea of looking at RFC 8037 to see
how the problems are solved there and, well they aren't as far as I can
see. In fact things look worse as the Edwards and Montgomery forms are
treated as if they are the same and they are not.

It looks to me as if we actually do need to do quite a bit of work to
specify how to do encryption with ECDH in Jose. Unless of course I am
reading the spec wrong which is quite possible. But my impression is that
nobody implemented these options in running code or if they did, their work
didn't make it back to the spec as it should.

I need a package that contains exactly enough information to be able to
decrypt the message. Which means that I need both keys to be specified in
the recipients entry.

I don't want to mix the ephemeral key data into the encrypted_key blob
which would be the other way to do things.

It is not clear to me which way is the best way forward here. I am going to
be writing up a draft to describe the format for recryption which is going
to be rather different to JOSE work anyway because my format is designed to
allow efficient encryption of entire files. So my eventual format is going
to be something like:

{JSON stuff}
<RS><WrappedKey><IV><Ciphertext><MAC>

If we are doing end-to-end encrypted Web, we might not want to do a Key
Exchange mediated by the recryption service on every file encrypted. So it
is likely that multiple data items will share a set of key exchange
parameters. So I am going to have some identification information to allow
those results to be cached.

One option is to add the additional pieces I need into an extension draft
covering my additional tags. Another is to produce two drafts.

My feeling is that right now, I am probably the only person using JSON as a
replacement for PKCS#7 / CMS so it is quite likely I am the only person who
is going to be using Ed25518 or X25519 to encrypt large chunks of data.

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 30 Aug 2017 21:54:36 +0300

> treated as if they are the same and they are not.

RFC 8037 doesn't do anything really new, it just does the JWE ECDH-ES
and JWS with CFRG curves.

So if you are looking at some operational mode that base JOSE doesn't
support, RFC 8037 is not going to support it either.
 
> didn't make it back to the spec as it should.

It seems like ECDH-ES in JWE was designed for the usual method of
encrypting data using ECC, not to do anything exotic (like you seem to
be doing).

> decrypt the message. Which means that I need both keys to be specified in

There are two logical recipients but one encryption key, that sounds
exotic, yes.

I presume the actual encryption key is a point sum of the two public
keys? If so, be careful: To compute point sums on X25519 correctly, you
need to know the y coordinate signs of the points, as the resulting
point will be different depending on if the signs are the same or
the opposite.

> <RS><WrappedKey><IV><Ciphertext><MAC>

Be careful: Encrypting entiere files is not as easy as it seems.

For some ideas, maybe look at HTTP encrypted content-coding, as that
also has the problem of encrypting possibly very large files.

Neither AES-GCM nor Chacha20-Poly1305-AEAD can encrypt a 500GB file in
one shot, even if you had enough memory.

-Ilari

---

From: Jim Schaad <[email-masked]>
Date: Wed, 30 Aug 2017 12:02:48 -0700

Start by looking at section 5.4 of RFC 7520 – which is doing what you are looking for.

Jim

From: Curdle [mailto:[email-masked]] On Behalf Of Phillip Hallam-Baker
Sent: Wednesday, August 30, 2017 10:23 AM
To: Curdle <[email-masked]>
Subject: [Curdle] Encryption in CFRG curves, RFC 8037 not sufficient

I am currently working on making Mesh/Recrypt work. This is basically three key public key cryptography. Instead of having one key to encrypt and one to decrypt, we have one to encrypt and the decryption key is split into two that have to BOTH be applied for decryption.

OK so for the purposes of this issue, the encryption is exactly the same as for two key DH.

Since the world is moving to ECDH, I am writing my code using Diffie-Hellman key agreement which RFC7516 doesn't really support. So I extended the format as follows:

Sender:

* kid = identifier of group public key which is the UDF fingerprint of the key itself.

* Performs a key exchange against the group public key to create the key agreement value.

* encrypted_key =  Key wrapping as specified in RFC 3394 to encrypt the session key 

{

  "protected": "

  "iv": "

zLuTMmoOJHUp68hl8eB6Fw",

  "recipients": [{

      "Header": {

        "jwk": {

          "PublicKeyDH": {

            "Public": "

      "encrypted_key": "

  "ciphertext": "

OK so what is wrong?

Well jwk is supposed to be the key identifier of the recipient key for a start. There is no way to express the DH key exchange properly in JOSE because it assumes that the Key Exchange is performed using symmetric or public key encryption. DH is neither, it is a key exchange.

RFC 7818 is no help:

So as I was looking into this, I had the idea of looking at RFC 8037 to see how the problems are solved there and, well they aren't as far as I can see. In fact things look worse as the Edwards and Montgomery forms are treated as if they are the same and they are not.

It looks to me as if we actually do need to do quite a bit of work to specify how to do encryption with ECDH in Jose. Unless of course I am reading the spec wrong which is quite possible. But my impression is that nobody implemented these options in running code or if they did, their work didn't make it back to the spec as it should.

I need a package that contains exactly enough information to be able to decrypt the message. Which means that I need both keys to be specified in the recipients entry.

I don't want to mix the ephemeral key data into the encrypted_key blob which would be the other way to do things.

It is not clear to me which way is the best way forward here. I am going to be writing up a draft to describe the format for recryption which is going to be rather different to JOSE work anyway because my format is designed to allow efficient encryption of entire files. So my eventual format is going to be something like: 

{JSON stuff}

If we are doing end-to-end encrypted Web, we might not want to do a Key Exchange mediated by the recryption service on every file encrypted. So it is likely that multiple data items will share a set of key exchange parameters. So I am going to have some identification information to allow those results to be cached.

One option is to add the additional pieces I need into an extension draft covering my additional tags. Another is to produce two drafts.

My feeling is that right now, I am probably the only person using JSON as a replacement for PKCS#7 / CMS so it is quite likely I am the only person who is going to be using Ed25518 or X25519 to encrypt large chunks of data.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 30 Aug 2017 15:26:47 -0400

Ah, the epk parameter is defined in RFC7518 (JSON Web Algorithms) and not
RFC 7516 (JSON Web Encryption)

​​4.6.1.1.

I think that deserves an errata as it is entirely reasonable for the
encryption mechanism to be specified in the RFC titled 'encryption'.

On Wed, Aug 30, 2017 at 3:02 PM, Jim Schaad <[email-masked]> wrote:

> *From:* Curdle [mailto:[email-masked]] *On Behalf Of *Phillip
> Hallam-Baker
> *Sent:* Wednesday, August 30, 2017 10:23 AM
> *To:* Curdle <[email-masked]>
> *Subject:* [Curdle] Encryption in CFRG curves, RFC 8037 not sufficient
>
>
>
> I am currently working on making Mesh/Recrypt work. This is basically
> three key public key cryptography. Instead of having one key to encrypt and
> one to decrypt, we have one to encrypt and the decryption key is split into
> two that have to BOTH be applied for decryption.
>
>
>
> So as I was looking into this, I had the idea of looking at RFC 8037 to
> see how the problems are solved there and, well they aren't as far as I can
> It is not clear to me which way is the best way forward here. I am going
> to be writing up a draft to describe the format for recryption which is
> going to be rather different to JOSE work anyway because my format is
> designed to allow efficient encryption of entire files. So my eventual
> format is going to be something like:
>
>
>
> {JSON stuff}
>
> My feeling is that right now, I am probably the only person using JSON as
> a replacement for PKCS#7 / CMS so it is quite likely I am the only person
> who is going to be using Ed25518 or X25519 to encrypt large chunks of data.
>
>
>
>
>
>
>
>
>
>
>

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 30 Aug 2017 16:11:07 -0400

> support, RFC 8037 is not going to support it either.

​As I pointed out to Jim, the problem is that the epk field is defined in
RFC 7518 as a field specific to Diffie-Hellman whereas it should be
specified in RFC 7516 as a JWE header. Making sense of RFC 8037 is hard
unless you know where to look.

I think this can probably be fixed by a minor revision to 8037 section 3.2.

> There are two logical recipients but one encryption key, that sounds

​No, there is one recipient entry that maps to one encryption key. The
corresponding decryption keys are split. Each recipient has a different
split.

So if the encryption key is x

Alice has Recryption key x-a, Decryption key a
​Bob has Recryption key x-b, Decryption key b
​..
​Zaphod has Recryption key x-z, Decryption key z

​Encryption is exactly as usual. Here is the revised version:

{
  "protected": "
ewogICJlbmMiOiAiQTI1NkNCQyJ9",
  "iv": "
XprRRLxypOEdc8e6Sfzeuw",
  "recipients": [{
      "Header": {
        "kid": "[email-masked]
",
        "epk": {
          "PublicKeyDH": {
            "kid": "MAFWJ-EITV3-YYCTK-VBYMH-QISR2-AB4XR",
            "Domain": "
YE6bnq1MlX5ojaJto6PLP_PEwA",
            "Public": "
ly6Ly2hTOA7LiyNOzFeza9NdP2YWONYDfPRryU7iA4UJ0XR89DeoCYyirkKwo-Dy
_R13gBS8ssUIPAlbLw9ZG2TMUQXsDXOfm_C4NuUyGSOKDZXmFVpGs6a1ZDZUHgXK
JbmcVmOuc0fPuHeupnHab4xKMrcN1JnLb25NYLLP38BMNHgwzsHW86_amQkJfkcP
GE06ftDSLx58hM3GMIBPzs1CaPxlRQq-Z-XUa-PphpluiBPUyY59WZp7_VQiFeJL
KCqVE6RAemPUpB0L4KJN986NH-UKOg1oMqmLI_OBRHct4ReUIHgj20BGNvgLkee9
RaPYcnjpGO39C6POMsc1vwA"}}},
      "encrypted_key": "
jp0wv-ScBiM8C51p9Whiw8JRM_8z91KO7JLJJknWMfrHMbGabSdqnA"}],
  "ciphertext": "
rLbzveATVYv2jaMnsKz0LkVzz6O5DNrN5B-ZtSOoODY"}

​(yes, I know epk is not standard yet).

> point will be different depending on if the signs are the same or

​Which is why I plan to use the Edwards curves for encryption, not the
Montgomery.​ Yes, I know it is possible to do point sums on X25519 but why
go through the covfefe when you need Edwards anyway?

> to
> ​​

​​Yes, particularly when you have to support modes like streaming. The
question I have been asking myself is whether to have a 'simple' format
which is unchunked and an advanced format which is chunked.

Now that you point out that the 'simple' mode also gets complex for very
large files, I am thinking of just making chunking a requirement.

The corner case would be to support random access efficiently. Which could
be done by fixing the chunk size in advance. If you know the chunk size is
fixed at 1MB, and the framing records are also fixed size (always rekey,
always drop the MAC tag), you can do random access provided that your
encryption mode allows a block to be changed in the middle of the cipher
stream without causing changes to any blocks other than the next one.

For some ideas, maybe look at
> ​​
> HTTP encrypted content-coding, as that
> Neither
> ​​
> AES-GCM nor
> ​​
> Chacha20-Poly1305-AEAD can encrypt a 500GB file in

​256GB seems to be the limit...

Given that the framing overhead is going to be a 256 bit key + 128 bit
wrap+ 128 bit tag + 128 bit IV = 80 bytes, I don't see having to introduce
framing every 1GB or so would be an imposition.

It is probably prudent to have a checksum every GB or so anyway.

​So I think I will make the framing mandatory​

{JSON stuff}
<RS>
​ Frame [​
<WrappedKey>
​ ​
<IV><Ciphertext><MAC>
​ ]​

I will probably mandate that the header be in JSON and use JSON-B  for the
rest. That allows me to avoid the overhead of BASE64 encoding everything
without introducing a new encoding data model.

---

From: Jim Schaad <[email-masked]>
Date: Wed, 30 Aug 2017 14:36:29 -0700

I don’t understand you position here.  

Either you are using the existing algorithm, and the field is therefore defined or

You are creating a new algorithm, and are therefore free to define the use of the field for your algorithm

Jim

From: [email-masked] [mailto:[email-masked]] On Behalf Of Phillip Hallam-Baker
Sent: Wednesday, August 30, 2017 12:27 PM
To: Jim Schaad <[email-masked]>
Cc: Curdle <[email-masked]>
Subject: Re: [Curdle] Encryption in CFRG curves, RFC 8037 not sufficient

Ah, the epk parameter is defined in RFC7518 (JSON Web Algorithms) and not RFC 7516 (JSON Web Encryption)

​​4.6.1.1.

I think that deserves an errata as it is entirely reasonable for the encryption mechanism to be specified in the RFC titled 'encryption'.

On Wed, Aug 30, 2017 at 3:02 PM, Jim Schaad <[email-masked] <mailto:[email-masked]> > wrote:

Jim

From: Curdle [mailto:[email-masked] <mailto:[email-masked]> ] On Behalf Of Phillip Hallam-Baker
Sent: Wednesday, August 30, 2017 10:23 AM
To: Curdle <[email-masked] <mailto:[email-masked]> >
Subject: [Curdle] Encryption in CFRG curves, RFC 8037 not sufficient

Sender:

{

  "protected": "

  "iv": "

zLuTMmoOJHUp68hl8eB6Fw",

  "recipients": [{

      "Header": {

        "jwk": {

          "PublicKeyDH": {

            "Public": "

      "encrypted_key": "

  "ciphertext": "

OK so what is wrong?

RFC 7818 is no help:

 

 

{JSON stuff}

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 30 Aug 2017 18:01:25 -0400

On Wed, Aug 30, 2017 at 5:36 PM, Jim Schaad <[email-masked]> wrote:

> Ji
> ​m
​epk looks to me to be a field to specify an ephemeral key for use in any
key agreement based encryption rather than a ​field that is specific to
just one key agreement.

When the JOSE docs were created, there was only one key agreement mechanism
specified. Now 8037 adds a second. The problem is that 8037 does not
actually define a epk field, it assumes that it is already specified for
JWE where it is actually only specified for one EC curve on JWE.

This is going to get even more confusing if someone comes along and
specifies a new key agreement, even more so if they used a different field.

---

From: Jim Schaad <[email-masked]>
Date: Wed, 30 Aug 2017 15:35:47 -0700

Sent: Wednesday, August 30, 2017 3:01 PM

On Wed, Aug 30, 2017 at 5:36 PM, Jim Schaad <[email-masked] <mailto:[email-masked]> > wrote:

Ji

​m

​epk looks to me to be a field to specify an ephemeral key for use in any key agreement based encryption rather than a ​field that is specific to just one key agreement.

When the JOSE docs were created, there was only one key agreement mechanism specified. Now 8037 adds a second. The problem is that 8037 does not actually define a epk field, it assumes that it is already specified for JWE where it is actually only specified for one EC curve on JWE.

This is going to get even more confusing if someone comes along and specifies a new key agreement, even more so if they used a different field.

[JLS]  RFC 8037 does define a new key type, however it does not define a new key agreement algorithm.  It uses the same set of algorithms that are defined in the JWA document.  This can be seen in the text of section 3.2 where it points to section 4.6 of 7518 to say that these are the algorithms that are being used.   This is different than the signature algorithm, where a new algorithm is defined.    This is also reflected in the IANA considerations where only one algorithm (EdDSA) has been defined.

This is exactly the same approach that is used or both COSE and CMS.

Jim