ed25519::GE fails in serialization and deserialization

[HRezaei]

There seems to be an error in encoding/decoding of a GE (Ed25519Point) in version 0.7.0. In the example below, the base_point is serialized to JSON, and a new point is recreated from it. I expect the new point to contain the same x, y coordinates, but it isn't the case:

    let base_point: GE = GE::generator();
    println!("base_point.x:{:?}", base_point.x_coor().unwrap().to_hex());
    println!("base_point.y:{:?}", base_point.y_coor().unwrap().to_hex());
    //Prints:
    //base_point.x:"216936d3cd6e53fec0a4e231fdd6dc5c692cc7609525a7b2c9562d608f25d51a"
    //base_point.y:"6666666666666666666666666666666666666666666666666666666666666658"

    let base_point_json = serde_json::to_string(&base_point).unwrap();
    let new_point = serde_json::from_str::<GE>(&base_point_json).unwrap();

    println!("new_point.x:{:?}", new_point.x_coor().unwrap().to_hex());
    println!("new_point.y:{:?}", new_point.y_coor().unwrap().to_hex());
    //Prints:
    //new_point.x:"6742e15f97d771b642862d5cf84ecf93eb3ac67b80698b993b87fdbc08a584c8"
    //new_point.y:"21d30600c9e573796ead6f09668af38f81783cfc621ee4931e2f5ba9fc37b9b4"

    assert_eq!(base_point, new_point);//assertion failed

This causes the EdDSA thresholdsig to always fail with "invalid key" error in the stage: phase1_verify_com_phase2_distribute() because the y_vec: &Vec<GE> has to be collected from different parties, and this needs serialize/deserializing the GE's.

You have said that improving the v0.7 is no longer a priority(unless critical issues) so it would be great if you please consider this as a critical issue!

[HRezaei]

The real cause of the problem seems to be in from_bytes() where the encoded point is multiplied by 8.

[survived]

Hi @Hrezaei,

So you're right, we intentionally multiply decoded point by 8, it clears a small cofactor from the point. That might seem odd, but that's how it works. FYI since [email protected], we don't do multiplication by 8 anymore.

Nevertheless, multi-party-eddsa is tested to work, it takes into account that feature of curv library. Could you describe how you encountered "invalid key" error?

[HRezaei]

Hi @survived,

Thanks for your consideration.

Regarding the v0.8 we can't use it currently because upgrading to it, needs a lot of changes, not only in the eddsa project but also in many dependencies such as paillier's, centipede, bulletproofs, etc.

Nevertheless, multi-party-eddsa is tested to work, it takes into account that feature of curv library. Could you describe how you encountered "invalid key" error?

Yeah, tests in the multi-party-eddsa work without error because all parties are executed in the same machine. Consider for example, the test function keygen_t_n_parties(), in the line 153 you have collected y_vec by simply iterating over party_keys_vec. But in a real scenario, each y_i has to be collected from different parties, executed on separated machines. So they have to be serialized and deserialized in the communications between parties. I suggest changing the lines 153-155 from

let y_vec = (0..n.clone())
            .map(|i| party_keys_vec[i].y_i.clone())
            .collect::<Vec<GE>>();

to this snippet below, to mimic the real scenario.

let y_vec = (0..n.clone())
    .map(|i| party_keys_vec[i].y_i.clone())
    .map(|y_i| serde_json::to_string(&y_i).unwrap())//serialize y so to be broadcasted to other parties
    .map(|y_i_json| serde_json::from_str(&y_i_json).unwrap())//deserialize y, as it happens in each recipient party
    .collect::<Vec<GE>>();

You will see two tests will fail with the error "invalid key: InvalidKey".

[survived]

but also in many dependencies such as paillier's, centipede, bulletproofs, etc

All of these libraries are updated to use the latest curv, thanks to @tmpfs. multi-party-ecdsa is almost updated too, see https://github.com/ZenGo-X/multi-party-ecdsa/pull/144. It is possible to update eddsa library as well, if you want to contribute to the project 😉

Regarding deserialization, unless the library is updated to use latest curv, you can divide deserialized point by 8, it will yield the original point.

[HRezaei]

Updating the eddsa would be appealing if time limits permit. 😊

About division by eight, I followed your advice, but as you can see in the above commit, it needs many changes in many places as GE's are used inside vectors and more complex structs. It also would be a source of runtime errors, not easily discernible errors, because it's related to values, not data types. The developers should be careful to remedy the situation whenever a data structure containing GE is deserialized.

[survived]

Yeah that's frustrating. If it's applicable for your case — you can define a structure pub struct MyGE(GE); and define Serialization/Deserialization traits for it. Maybe that could help you to minify the changes?

Also, you can tag the wrapping structure with #[repr(transparent)] and this will allow you to define relatively safe zero-cost cast Vec<MyGE> -> Vec<GE>.

[HRezaei]

Thank you @survived for your advice.

But if I decided to define such a custom type in my own fork for my own use, why not remove that multiply by eight? What's the harm of removing that and adding a check for being on the curve?

[survived]

Multiplication by 8 is security related operation, it clears out small cofactor part from the point. Not doing this might leak some bits of your secrets, or affect the protocol in some unexpected way. Note that it's not related to checking whether a point is on curve: when we multiply point by 8, we already checked that the point is on curve.

New version of curv performs an expensive check instead of multiplying by 8. It's less efficient, but more clear.

[leontiadZen]

@HRezaei thanks for that, can you check again with v.0.10.0?

[HRezaei]

Hi @leontiadZen, Sorry for late reply! The initial issue was reported on v0.7.0, however I can confirm it is resolved in v0.9 and v0.10.0.