Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

ed25519::GE fails in serialization and deserialization #156

Open
HRezaei opened this issue Dec 2, 2021 · 10 comments
Open

ed25519::GE fails in serialization and deserialization #156

HRezaei opened this issue Dec 2, 2021 · 10 comments

Comments

@HRezaei
Copy link

HRezaei commented Dec 2, 2021

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
Copy link
Author

HRezaei commented Dec 2, 2021

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

@survived
Copy link
Contributor

survived commented Dec 3, 2021

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
Copy link
Author

HRezaei commented Dec 3, 2021

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
Copy link
Contributor

survived commented Dec 7, 2021

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 ZenGo-X/multi-party-ecdsa#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 added a commit to HRezaei/multi-party-eddsa that referenced this issue Dec 9, 2021
@HRezaei
Copy link
Author

HRezaei commented Dec 9, 2021

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
Copy link
Contributor

survived commented Dec 9, 2021

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
Copy link
Author

HRezaei commented Dec 20, 2021

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
Copy link
Contributor

survived commented Dec 21, 2021

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
Copy link
Contributor

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

@HRezaei
Copy link
Author

HRezaei commented Mar 24, 2024

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants