use kyber keys with different libraries

[jonathanMweiss]

I use kyber's DKG and attempted to reconstruct the secret key such that I'll be able to use it with NaCl/box.
Is there a proper way to convert kyber's keys to be able to work with other libraries?

What I've tried:
I've attempted to marshal keys generated by DKG with the followings suite: NewBlakeSHA256Curve25519. but this didn't work. Then I've made an attempt to use NewBlakeSHA256Ed25519 and convert the keys. After many attempts I've managed to use keys generated by NewBlakeSHA256Ed25519().NewKey() with nacl/box, but when reconstructing a secret key gained by the DKG algorithm, the keys would not convert correctly, that is I wasn't able to use them with nacl/box.

[ineiti]

This is a known problem. See also the diagram in here:

https://blog.mozilla.org/warner/2011/11/29/ed25519-keys/

You can try the EdDSA package from kyber, which stores the seed, so you should be able to create the a and RH for NaCl.

[gnarula]

Another thing I noticed is NaCl/Box expects the Montgomery representation of the curve points. There is a mapping between the Twisted Edward Curve Points and the Montgomery representation defined in RFC 7748. Might be worth looking at https://blog.filippo.io/using-ed25519-keys-for-encryption/ and https://libsodium.gitbook.io/doc/advanced/ed25519-curve25519.

[jonathanMweiss]

Thank you both for the quick response! I really appreciate it.

@gnarula I've tried that previously and forgot to mention, sorry. to go from kyber/curve25519 through the formula described in filipo's blog that is. it didn't seem to work with NaCl/box, even though I managed to convert kyber's base point to the exact base point used in NaCl/box. I think it has to do with with the byte representation of the marshalled scalar. but I didn't managed to understand what.
The libsodium solution is what gave me the idea to try working through kyber's ed25519, which seemed really promising, but ultimately failed (im stating what I've done below)

@ineiti I managed to ignore the fact that I don't have the seed, because I've found out that converting the secret key is expanding the seed into the scalar, and take it as the converted secret key: newSecertKey = (hash(seed))[:32]
So I managed to to convert kyber's ed25519 to a key that I can use in NaCl/box (by grabbing the []bytes of scalar.v), but this doesn't seem to work with share/dkg/pedersen reconstructed scalar. Do you perhaps know why the scalars reconstructed are different somehow than the scalars outputted by suite.NewKey? I thought something about clamping, but I don't really know.

[ineiti]

One thing I saw is that kyber always calculates the modulo of the scalar and points, whereas some libraries do not do that. I remember vaguely that BouncyCastle from Java didn't do it (might be wrong).

You can create two scalars, zero and one, then subtract one from zero and see what you get. In Kyber you will get the (something something, always forget which constant it is), while in BouncyCastle you'll get 0xffff.... Is that what you mean by clamping?

And, yes, I think curve25519 and ed25519 use different representations.

[jonathanMweiss]

as far as I understood: curve25519, and ed25519 have different representation, but both of them expect to work with a scalar, and a point over a curve.
I've managed to translate between the two, and work with a converted ed25519 key pair in curve25519 (I can share the code I used too if it helps).

by clamping I mean what is done in the function NewKeyAndSeedWithInput in file group/edwards25519/curve.go:

func (c *Curve) NewKeyAndSeedWithInput(buffer []byte) (kyber.Scalar, []byte, []byte) {
...
digest[0] &= 0xf8
digest[31] &= 0x7f
digest[31] |= 0x40
...

( the name I found here: https://neilmadden.blog/2020/05/28/whats-the-curve25519-clamping-all-about/ )
I don't think clamping happens in the dkg package ( when creating VSS dealers). I thought this might be the issue because suite.scalar().Pick(suite.RandomStream()) doesn't seem to convert well, in contrast to suite.NewKey() which converts well.
that is suite.NewKey() converts, and suite.scalar().Pick(suite.RandomStream()) doesn't have clamping and doesn't convert.

[gnarula]

So I managed to to convert kyber's ed25519 to a key that I can use in NaCl/box (by grabbing the []bytes of scalar.v), but this doesn't seem to work with share/dkg/pedersen reconstructed scalar

Hmm, what if you try grabbing the []byte by using scalar.MarshalBinary() instead? IIRC, that method ensures the buffer contains the reduced value after taking the modulo. It's a shot in the dark though but my guess is NaCl/Box expects the scalar to be in the right range and errors out otherwise. Now this might not protect against small sub group attacks that clamping is used for and I'll leave that for others to share their thoughts on.

PS: curve25519 and edwards25519 in kyber use the same Twisted Edwards Curve representation (refer to #384) though as the the issue remarks, Curve25519 usually refers to the Montgomery representation everywhere else.

[jonathanMweiss]

@gnarula

Hmm, what if you try grabbing the []byte by using scalar.MarshalBinary() instead

I don't think this is it: When converting the ed25519 key, if I take the []byte from scalar.MarshalBinary() the conversion stops working.

I chose to grab specifically scalar.v because I understood from group/edwards25519/fe.go that it should be a similar/exact representation of golang.org/x/crypto/ed25519/ed25519/internal/edwards25519 which I have a way to convert from.
So using scalar.v can be converted correctly when scalar is specifically made to be a key using Suite.NewKey(). but if scalar = Suite.Scalar.Pick(Suite.RandomStream()) conversion doesn't work.

curve25519 and edwards25519 in kyber use the same Twisted Edwards Curve representation (refer to #384) though as the the issue remarks, Curve25519 usually refers to the Montgomery representation everywhere else.

I see, to be honest I started with curve25519, and when I didn't manage to convert i thought about just asking here, then I saw that ed25519 internal representation is similar to the code I saw in golang.org/x/crypto, so I kept on investigating until I managed to make a conversion, but then got stuck with converting keys from any function that is not Suite.NewKey()..

[gnarula]

Do you mind sharing the code you're using for conversion? And possibly an example of the conversion succeeding/failing as well?

[jonathanMweiss]

Yes of course, https://play.golang.org/p/DrLXf9INeV_W
I've made an example of the the code generating a key pair, and converting them.
then the keys are used with box.Seal and box.Open and a simple message.

Hopefully I didn't do anything foolish there.

EDIT: it might fail while running on the website, because there are a lot of imports, and it timeout the running.

[gnarula]

I think it's got to do with curve25519.ScalarMult (called by box.Precompute) expecting a clamped scalar. As a small proof of concept, have a look at:
https://play.golang.org/p/Z-9Bq6H-mmO

Here's the output for a sample run:

s1x: f02f28e3326b6760f38cf1aac0be36ebe72587515218d3d6d4eae5b32e92c461 p1x: 392808c0c3c1f443c70497097295936a4509a612c51a85a7f241e6fd3e5ad009
s2x: e0b0ea90ac175070efdce0ada50b0dbfc2316efd5e146c7b18351fb71a7cb05e p2x: 3735aab57d285f80d42720686109e40a91b2426c57d4355bdc4493cf7b3bd25e
boxSharedKey: 0eab901141fc143b75b25bdf78c94a9fe465523c1ee70693ef5af871642ffc15
ourSharedKey: 0eab901141fc143b75b25bdf78c94a9fe465523c1ee70693ef5af871642ffc15
2020/10/30 14:27:33 Alice Send Encrypted Message 8a58dcbb49b1629c88bec681ee7cc32ddb2cb5d2335811b2e9dcdf1c4834ee929b7d3ed9aed003db26170a238ffc350fb34601446aaa99
boxSharedKey: 0eab901141fc143b75b25bdf78c94a9fe465523c1ee70693ef5af871642ffc15
ourSharedKey: 0eab901141fc143b75b25bdf78c94a9fe465523c1ee70693ef5af871642ffc15
2020/10/30 14:27:33 Bob receives Message [encryption test]
s1x: 44d9deaadf0b8a85ba8f8e9dcc84e5c6a02d88844a6d024c331bb778fec78906 p1x: 2d78df00f41da317e2a4c0777a0a49e083d68ee62a957cbe81548de18df76d75
s2x: 7ba71150b533604162c4f6c62da8fcad20f32a5a3956b6db48d8ce1a2aff0606 p2x: 3eadd110930f44b5ff874d5c251889fe16c31828d958aaa3c253fcf6c5a12257
boxSharedKey: 747795d8b47ecab14e89cf9dd65216012c20d53efd8e1e7bd94182af78993f65
ourSharedKey: c530aef7b2d6ff926cc1e8f0d6b7f16b3c0a509e4a6b01d94fc5f67322bd546a
2020/10/30 14:27:33 Alice Send Encrypted Message 631cf1899c10faa62ae10c42fdaf4d2b523a5b5845001b3c10975510ebe2939e6cbd3275c8679b7c9a5a84f88dd6abc40ad7feda2d9b20
boxSharedKey: 8134f9dd686097896b5552efe7bb88120103a8d94379042f3917e64c5fcfa967
ourSharedKey: c530aef7b2d6ff926cc1e8f0d6b7f16b3c0a509e4a6b01d94fc5f67322bd546a
2020/10/30 14:27:33 Bob receives Message [encryption test]

You can see boxSharedKey != ourSharedKey where both represent the common secret s1*P2 = s1*s2*G for shouldSucceed=false. I tried validating my claim by carrying out the multiplication in another implementation. Apologies for the not so pretty Rust code - I've barely used the language.

use std::convert::TryInto;
use curve25519_dalek::scalar::Scalar;
use curve25519_dalek::montgomery::MontgomeryPoint;
use curve25519_dalek::constants;
use hex;
use bincode;

fn main() {
    let s1xhex = hex::decode("44d9deaadf0b8a85ba8f8e9dcc84e5c6a02d88844a6d024c331bb778fec78906").unwrap();
    let s1x = Scalar::from_canonical_bytes(buf(&s1xhex)).unwrap();
    let p2xhex = hex::decode("3eadd110930f44b5ff874d5c251889fe16c31828d958aaa3c253fcf6c5a12257").unwrap();
    let p2x: MontgomeryPoint = bincode::deserialize(&buf(&p2xhex)).unwrap();

    let product = s1x * p2x;
    let product_buf = bincode::serialize(&product).unwrap();
    let product_buf_hex = hex::encode(product_buf);
    println!("product: {}", product_buf_hex);
}

fn buf(vec: &[u8]) -> [u8; 32] {
    vec.try_into().expect("invalid length")
}

and indeed, the product is product: c530aef7b2d6ff926cc1e8f0d6b7f16b3c0a509e4a6b01d94fc5f67322bd546a which is the same as ourSharedKey.

I didn't dig much deep into curve25519.ScalarMult but it does clamp the secret key buffer after copying it.

[jonathanMweiss]

I think I understand, thank you for the thorough inspection and explanation.
I'll think about how to handle conversion.

a small question though: is it an issue that kyber isn't always clamping the scalar?

[ineiti]

a small question though: is it an issue that kyber isn't always clamping the scalar?

Depends on whom you ask ;) The original kyber source has been created for people who don't care if they shoot themselves in the foot. So the code was as 'plain' as possible to the mathematical constructs. Clamping introduces some restrictions in what kind of scalars you can have. Which is good for security, but bad for some kind of experiments you might want to do.

So there is the NewKey method that returns clamped scalars. But once you start using NewKey, you're getting into territory (=software used by non-experts) where you might not want to go when using kyber. Because now, if you shoot yourself in the foot, it might be somebody else's foot...

[jonathanMweiss]

I see, I'm a non-expert so I'll tread with care :)
Thank you both for the help!