ECDH encryption/decryption support

[zapu]

This pull request introduces encryption and decryption using ECDH keys (no cv25519 yet though, read below). Most of new code is in openpgp/packet/ecdh.go and openpgp/ecdh/ecdh.go. Package ecdh got all the functions that were independent enough not to need to import anything from package packet (which would create circular dependency) - random scalars, KDF (but creating "KDFparams" buffer is in packet), rfc3394 key wrapping, padding.

Encryption is done mostly in ecdh package, but a lot of things have to be passed as arguments. Decryption is mostly in packet package (ecdh.go file). Let me know which is better - I'll either rewrite Decryption in similar fashion, or move encryption to the packet package.

There are new functions for reading MPI coords for ECDH in openpgp/packet/packet.go. EncryptedKey has new ecdh_C []byte field, because ECDH encryption serializes curve coordinates and AES-keywrapped buffer.

ecdh_test.go now also tests encryption/decryption. The test that was already there was "completed" to decrypt message, and also there is a new test that does roundtrip encryption/decryption with test additional two keys with two different curves, created with gpg.

CV25519 needs EdDSA support. There is some ground work being done, but it's very far from being able to actually sign anything. Also there is no ECDH key generation - I haven't gotten that far in understanding go-crypto yet.

The question is, where to go with this. I've found a fork [1] that also implements ECDH and has better go code that I was able to write. It also does some much needed cleanup in other places. I can try to bring that code in, instead. I wish I had found it sooner :wink:

[1] https://github.com/benburkert/openpgp

[maxtaco]

I didn't know about @benburkert's fork either. It might be hard to switch to his fork, since much of the work we have here is be more lenient with weird keys and weird signatures that we have seen in the wild. However, the GNU extensions like smart card support seem very useful. Probably the best bet is to go forward with the current plan.

In what ways do you think that the other fork is better code than what you have here, and where is the cleanup?

Many thanks

[zapu]

I like this change: https://github.com/benburkert/crypto/commit/da0a1e107491813ef0ae4029cfe03e1c1844b6a8

But with ECDH it seems like it assumes all encrypted key will consist of encoded X coord and AES ciphertext, which is only correct for cv25519 keys. I have not actually ran their code though, maybe I missed something.

I don't think switching is an option. But I'd like to look at their code while implementing rest of eddsa/cv25510, if it's fine from legal point of view.

[maxtaco]

I read through those changes too, they are very well done. My understanding is that the fork inherits the original license from go-crypto, which is permissive.

If you want to try to cherry-pick some of these changes, that might be very nice. I think they are orthogonal, largely, to the stuff that we've done to be more permissive of whacky PGP keys.

[zapu]

I'm going to try to add missing EdDSA support and get cv25519 working now.

[zapu]

Curve 25519 support is now in. For this I needed to add a cv25519Curve type that would conform to curve interface in elliptic package. I kind of copied what https://golang.org/src/crypto/elliptic/p224.go to implement specific curves.

After adding the curve, everything more or less worked, but it exposed a bug in key wrapping that I had to fix ("fix input trimming" commit). There was also an issue with randomScalar byte length calculation which would take a few bits away from the random output. I changed it but I'm still not sure if it's correct. But I plan to swap the entire key generation with the one in elliptic package anyway - while working on 25519 I discovered that they have key generation along with generating random scalars already.

[zapu]

Also I'm not sure about EdDSA and how much of it is implemented. I was actually surprised that I got cv25519 to work without more EdDSA changes - it was either in much more complete state than I thought or the code does not verify signatures of ecdh keys while reading them. I will look into it more to verify what's left to be done there.

[zapu]

I verified that the eddsa key signatures work as well.

@maxtaco Any way we can move forward with this? It's been quite a long time now :)

[zapu]

I've ran golint and fixed what was "mine". It complains a bit about other code, though.

[maxtaco]

Looking really good -- can you eliminate any commented-out code?

[zapu]

I will - I want to add a test case for invalid coordinates in encrypted key.

[zapu]

Researched and added a test regarding the mpi length checking. GPG doesn't care and neither should we - different implementation may round the number of bits there or not, and both are fine. I created an encrypted message where the coordinates serialized are unnecessarily big, where the bit size is not even different by rounding margin, and they still work fine in GPG.

[zapu]

Aaaand it fails in KBPGP

Error: Need 1059 bits for this curve; got 1459
  at Curve.exports.Curve.Curve._mpi_point_from_slicer_buffer (/home/zapu/pgp/kbpgp/lib/ecc/curves.js:64:15)

again, this weird payload works fine in GPG (notice the AAAAAAAAAAAAAAAAAA... in armored msg) :

~/pgp » gpg2
gpg: Go ahead and type your message ...
-----BEGIN PGP MESSAGE-----
Version: Keybase OpenPGP v2.0.58
Comment: https://keybase.io/crypto

wcA0A6pi0WoSlxTXEgWzBAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA/ZTuFZa3
go5bAv8SLZd5vTQzjQiqiXfaQUX3dQu+zytgEeiugIshlJ7JykTPGhdQFVSiKQYe
a4RKpgbn8SkNhyIAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAaR1kL+5vnf9E0wv
vGDKg1jo0uEGYVodxTwk8QuqbxWiCT/jOH9kybjECSPlkDkbUIOezOfaTlwde0Wo
XUNWZ/WrMOJHerpQvMvPNjEwMSGnsIZPh8/Hafj7j8OauMG5EWgCrzsxv1mgsRXP
QkNog/5dM9JIAcT8RpDaFecdhRag6ZPuRKmNuhiFtR7o0spcqX2UkJ3FPB7UydX3
ch9PkTNL1BVD++JqYQE9eaIqlCTAsHwCgO6pQkQqPUvB
=y7cW
-----END PGP MESSAGE-----

gpg: encrypted with 521-bit ECDH key, ID AA62D16A129714D7, created 2016-10-15
      "nist key tester <m+testing@zapu.net>"
purpleschala
^C
gpg: signal Interrupt caught ... exiting

[maxtaco]

you know i recently got a complaint about something similar on EdDSA in kbpgp. We can change that check if needs be

On Thu, Jan 26, 2017 at 9:21 AM, Michał Zochniak notifications@github.com wrote:

Aaaand it fails in KBPGP

Error: Need 1059 bits for this curve; got 1459 at Curve.exports.Curve.Curve._mpi_point_from_slicer_buffer (/home/zapu/pgp/kbpgp/lib/ecc/curves.js:64:15)

again, this weird payload works fine in GPG (notice the AAAAAAAAAAAAAAAAAA... in armored msg) :

~/pgp » gpg2 gpg: Go ahead and type your message ... -----BEGIN PGP MESSAGE----- Version: Keybase OpenPGP v2.0.58 Comment: https://keybase.io/crypto

wcA0A6pi0WoSlxTXEgWzBAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA/ZTuFZa3 go5bAv8SLZd5vTQzjQiqiXfaQUX3dQu+zytgEeiugIshlJ7JykTPGhdQFVSiKQYe a4RKpgbn8SkNhyIAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAaR1kL+5vnf9E0wv vGDKg1jo0uEGYVodxTwk8QuqbxWiCT/jOH9kybjECSPlkDkbUIOezOfaTlwde0Wo XUNWZ/WrMOJHerpQvMvPNjEwMSGnsIZPh8/Hafj7j8OauMG5EWgCrzsxv1mgsRXP QkNog/5dM9JIAcT8RpDaFecdhRag6ZPuRKmNuhiFtR7o0spcqX2UkJ3FPB7UydX3 ch9PkTNL1BVD++JqYQE9eaIqlCTAsHwCgO6pQkQqPUvB =y7cW -----END PGP MESSAGE-----

gpg: encrypted with 521-bit ECDH key, ID AA62D16A129714D7, created 2016-10-15 "nist key tester m+testing@zapu.net" purpleschala ^C gpg: signal Interrupt caught ... exiting

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/keybase/go-crypto/pull/40#issuecomment-275399401, or mute the thread https://github.com/notifications/unsubscribe-auth/AA05_4iLYwgpnTscLTeNxHbUhNbXmIBJks5rWKwAgaJpZM4LHSlG .

[zapu]

Encrypted messages generated with my go-crypto ecdh code will probably fail in similar way because they round to the number of bits (or rather they receive a buffer and save it with length of len(buffer)*8). I'll try to dig up some standard and investigate this more. But KBPGP should probably emulate GPG in this case.

[zapu]

Does it look right here, though? If so, should I make a fix for KBPGP?

[maxtaco]

Well, it wouldn't be buggy now if we didn't check for IsOnCurve in DecryptShared. But, what if some future version of elliptic decides to drop the check? It might be worth an abundance of caution here and just check it twice.

[zapu]

But Unmarshal is not used for reading encryption key; only for public key. That being said, I think we could grab entire MPI buffer in (e *EncryptedKey) parse instead of decoding numbers; and then use Unmarshal somewhere where we have the curve. This way we could remove readPointMPI (which was introduced by this PR).

[maxtaco]

The attacks I've read about use a malicious public key.

[zapu]

Oh, I didn't disagree about the need for this check. I was going through the curve checking before (when I left the // Note: Unmarshal already checks if point is on curve. comment in public_key.go). Adding more checks sounds like a good idea, though.

So what do you think about getting rid of readPointMPI in favor of less flexible Unmarshal? I'm big fan of having less code :)

[maxtaco]

How will you read ecdh_C in EncryptedKey#parse without parsing the two MPIs?

[zapu]

The point buffer starts with 2-byte integer which is a bit-size of the rest of the buffer; so it's not needed to parse actual numbers to know how long it will be. I think that's how the public key is read - func readMPI in packet.go seems to read the size in bits and then read rest of the bytes; actual Unmarshaling is a bit later.

[zapu]

It's a bit confusing, there is nothing about multi-precision integers in readMPI to justify the function name. I would need to take a better look, maybe I'm wrong about how this works.

[maxtaco]

Ok, great. Then I favor this method if at all possible. If we're always using curve.Unmarshal, then it's OK to not check for the point being on the curve explicitly.

[zapu]

The point-on-curve checking is documented: https://golang.org/pkg/crypto/elliptic/#Unmarshal so hopefully this will not change.

[maxtaco]

OK, great

[zapu]

This pushed back the effort to be compatible with GnuPG loose MPI deserializing. So maybe KBPGP should behave in the same way? It would be strict about the total number of bytes for encoded MPI, but not to number of bits (which is not very useful since we are always byte-aligned).

[maxtaco]

@zapu good with me. Should I merge?

[zapu]

I'll take another good look through the changes and let you know, ok? Thank you.

PS. Should we copy similar Unmarshal behavior to KBPGP, for this change: https://github.com/keybase/kbpgp/pull/134 ?

[zapu]

I think this looks ready. go-crypt -> KBPGP will faill with things like Error: Need 263 bits for this curve; got 264 though, but go-crypt -> GnuPG works fine. KBPGP -> go-crypt does as well. There are few things I'm not happy with but let's leave it for future, it's been forever already :)

[maxtaco]

Will it fail in all cases, or only with weird keys? And are they weird keys or just unlikely keys?

Yeah, sorry to be slow here, can you describe in more detail the case that won't work? Where does the key originate? Does it have to be imported/exported? Will it be uploaded to the Website, etc?

[zapu]

All ECDH messages encrypted with go-crypto would fail in KBPGP (but they work in GnuPG). It's because of that "3 bits for 0x4 header" or "7 bits for 0x40 header" thing.

I'm not sure how to save exact value there (like GnuPG does or KBPGP does) without changing elliptic.Marshal. Marshal returns a byte buffer so I serialize this as [ len(buffer), buffer... ]. If Marshal returned (buf []byte, bitSize int), we could improve this.

[maxtaco]

And does keybase/kbpgp#134 fix this problem?

[zapu]

Yes, using code from that PR makes it work.

But I'm not sure if allowing arbitrarily sized MPIs is way to go there, I'm wondering if there's some clever attack based on that. Maybe a DoS if you repeatedly pass really huge numbers to some service.

[maxtaco]

We can obviously put some bound on it if we're afraid of DoS

[maxtaco]

Let's merge and deploy keybase/kbpgp#134 first then

[zapu]

Sure, let me put few more hours into it though. Thanks!

[zapu]

What do you think about something like this: https://gist.github.com/zapu/c60fe9400d79403226ffaf72c3565314

I just realized we don't even need to count bits, because it will always start with 0x4 or 0x40 header. Resulting payloads are readable by current KBPGP master.

[maxtaco]

👍

[zapu]

@maxtaco do you happen to remember the EdDSA issue in KBPGP that was reported? I have an alternative branch for KBPGP that only accept coordinates of good length, but is not strict to the number of bits.

The standard says that the bitSize header has to be set correctly:

   The length field of an MPI describes the length starting from its
   most significant non-zero bit.  Thus, the MPI [00 02 01] is not
   formed correctly.  It should be [00 01 01].

https://tools.ietf.org/html/rfc4880#section-3.2

And also that the coordinates for ECDH should have a specific length and no other:

      B = 04 || x || y

   where x and y are coordinates of the point P = (x, y), each encoded
   in the big-endian format and zero-padded to the adjusted underlying
   field size.  The adjusted underlying field size is the underlying
   field size that is rounded up to the nearest 8-bit boundary.

   Therefore, the exact size of the MPI payload is 515 bits for "Curve
   P-256", 771 for "Curve P-384", and 1059 for "Curve P-521".

https://tools.ietf.org/html/rfc6637#section-6

So this pull request sort of follows it but allows for invalid header that's rounded up to the number of bytes. My KBPGP code is here: https://github.com/zapu/kbpgp/blob/8915ff84cc67238254860fc0ca9fbff805b52723/src/ecc/curves.iced#L55-L68

[maxtaco]

Sadly can't find that issue, I checked a bit in keybase/clients and keybase/keybase-issues, but the simple queries I though of didn't yield anything. Hmf.

[zapu]

Almost 3 month-long journey :) thank you for the merge

[maxtaco]

Great work @zapu! Thanks for this excellent PR.