C version does not decode the representative correctly
Closed this issue · 6 comments
I have hardcoded the alternative to be true in the encode function, I pass the little endian uint8_t 32 byte public point, obtain the representative and decode it
Alice private octets
d0a4578533d8133ddde22fe697f14acb98ed5348732d585d7421b8075afe563
Alice Public octets
84954fc775822f1cc05fd3848c415ff095296f6c22fc14a60418af8ceafa56e
Representative
67857bc2a36bd63eedf3a3dd7d943f083355f93e853be6d5ad39714847dcc
Decoded
4954fc775822f1cc05fd3848c415ff095296f6c22fc14a60418af8ceafa581
Alt
1
Sometimes, alternative is not recovered correctly from the representative
Alice private octets
a83a52ad0133623e4db2bc2a4aeebdf5b52905467626185f6dabc283fed50
Alice Public octets
f164726c8c79c52b76282f48b761ef55d6dd643621050b739d23d6fdf53d34
Representative
adb1b67c1065caad927a46fec5a35c6e43194d5365544abca97b535c947e8
Decoded
e9b8d9373863afd489d7db7489e1aa29229bc9defaf48c62dc290f2355a0
Alt
0
I must be doing something wrong, but I couldn't even generate the same public keys from your private. All byte string you provided are shorter than 64 digits, I prepended them with zeroes, but it didn't help.
Anyway, now the library is completely rewritten using constant time GMP functions, maybe the problem disappeared.
Hi,
The problem did not disappear. I found a similar one while trying to compare your implementation to Monocypher's. While decoding seems to be fully compatible between the two, I ran into issues with encoding. Further investigation shows that the round trip doesn't seem to work, at least for the test vectors you showed. Here's the code I used to reproduce:
#include <stdio.h>
#include <elligator-2-curve25519.h>
void print_vector(const uint8_t v[32])
{
for (size_t i = 0; i < 32; i++) {
printf("%02x", v[i]);
}
printf(":\n");
}
int main()
{
Elligator_2_Curve25519_initialize();
const uint8_t p[32] = {
0x33, 0x95, 0x19, 0x64, 0x00, 0x3c, 0x94, 0x08,
0x78, 0x06, 0x3c, 0xcf, 0xd0, 0x34, 0x8a, 0xf4,
0x21, 0x50, 0xca, 0x16, 0xd2, 0x64, 0x6f, 0x2c,
0x58, 0x56, 0xe8, 0x33, 0x83, 0x77, 0xd8, 0x80,
};
uint8_t r[32];
uint8_t p2[32];
bool h;
Elligator_2_Curve25519_encode(r, p, 0); // p -> r
Elligator_2_Curve25519_decode(p2, &h, r); // r -> p2
print_vector(p);
print_vector(p2);
printf("\n");
Elligator_2_Curve25519_encode(r, p, 1); // p -> r
Elligator_2_Curve25519_decode(p2, &h, r); // r -> p2
print_vector(p);
print_vector(p2);
printf("\n");
return 0;
}
The output I got:
33951964003c940878063ccfd0348af42150ca16d2646f2c5856e8338377d880:
46951964003c940878063ccfd0348af42150ca16d2646f2c5856e8338377d800:
33951964003c940878063ccfd0348af42150ca16d2646f2c5856e8338377d880:
46951964003c940878063ccfd0348af42150ca16d2646f2c5856e8338377d800:
So there are slight differences between the input point (which I found in your test vectors), and the point we get back:
- The most significant bit has been flipped back to 0. Okay, so you ignore the MSB for the encoding, and when we decode back, it goes away. Perfectly normal, considering that the X-coordinate is encoded in 255 bits.
- The least significant byte went through a weird transformation, that I cannot explain.
The point we get back is only slightly different from the one we started from, so maybe some bit flipping is going on prior to the computation. Though if it's just that, that wouldn't explain one of @richardpeeters45's output, which is wildly different from the input.
One last thing: the problem is not the decoding, it's the encoding.
I have compared Monocypher and @Kleshni's decoding, they matched perfectly over 50 random positive representatives (<=2^254-10). (Monocypher chose not to decode negative representatives, and ignore the two most significant bits instead.)
This test vector is not a valid point on Curve25519, so the function's behaviour is undefined. If you feed the function from a public key generator, this situation should never happen.
So the actual issue was the presence of an invalid point in the test vectors, and it's now fixed.
The least significant byte went through a weird transformation, that I cannot explain.
The number gets reduced modulo 2 ^ 255 - 19.
Though if it's just that, that wouldn't explain one of @richardpeeters45's output, which is wildly different from the input.
I am still unable to reproduce it.
This test vector is not a valid point on Curve25519, so the function's behaviour is undefined.
Which test vector are you talking about? I've just checked with the following:
Err, I just checked, and to the best of my knowledge, the point I am testing is on the curve. Specifically, I have tested 2 points (defined by their u coordinate only):
u1 = 0x0x80d8778333e856582c6f64d216ca5021f48a34d0cf3c067808943c0064199533
u2 = 0x0x00d8778333e856582c6f64d216ca5021f48a34d0cf3c067808943c0064199533
And both are on the curve. I computed vs = u^3 + Au^2 + u (mod p):
vs1 = 0x48938378b30a25511a139be5394f8e73d592345f782957f1bbfb849c843ac7c7
vs2 = 0x23ba2a77eae8ee2dd0a403d4f0bc0665f63b27af2dc4e41bb3d020cbe1e1c21f
As far as I can tell, both are squares.
The number gets reduced modulo 2 ^ 255 - 19.
🤦 That explains it… lemme check… 46 - 33 = 13, which means 19 in base 10. Yep, The reduction checks out. My bad.
Okay, since my failing test case was bogus, I wrote a serious test case, where I test the round trip (from representative to itself), and compare to Monocypher. This time I was careful to clear the high bits, which Kleshni uses to reduce modulo p, but Monocypher ignores.
I'm happy to report that I found no bug. Kleshni works correctly as far as I can tell. Moreover, aside from how high bits are read, Monocypher and Kleshni are 100% compatible. The program that tests this is below.
Thank for pointing out the flaw in my test case above, and my apologies for assuming your implementation was buggy and unmaintained during the last 10 months.
#include <stdio.h>
#include <elligator-2-curve25519.h>
#include <bsd/stdlib.h>
#include <string.h>
#include <monocypher.h>
int main()
{
Elligator_2_Curve25519_initialize();
for (size_t i = 0; i < 1000; i++) {
uint8_t r [32];
uint8_t r2[32];
uint8_t rm[32];
uint8_t pk[32];
uint8_t pm[32];
arc4random_buf(r, 32);
r[31] &= 0x3f; // make sure we're under 2^254 - 10
bool high_y;
bool principal = Elligator_2_Curve25519_decode(pk, &high_y, r);
if (!principal) {
printf("Not a principal square root!!\n");
}
crypto_hidden_to_curve(pm, r);
if (memcmp(pk, pm, 32)) {
printf("Kleshni and Monocypher decode differ!!\n");
}
bool can_encode = Elligator_2_Curve25519_encode(r2, pk, high_y);
if (!can_encode) {
printf("Cannot encode the point back!!\n");
}
can_encode = crypto_curve_to_hidden(rm, pm, high_y ? 1 : 0);
if (memcmp(r2, rm, 32)) {
printf("Kleshni and Monocypher encode differ!!\n");
}
if (memcmp(r, r2, 32)) {
printf("Not the same representative!!");
}
}
for (size_t i = 0; i < 1000; i++) {
// Generate a random point on the whole curve
uint8_t sk[32]; arc4random_buf(sk, 32);
uint8_t pk[32]; crypto_x25519_dirty_fast(pk, sk);
// Try to encode the point (positive v coordinate)
uint8_t rk[32];
uint8_t rm[32];
bool can_encode_p = Elligator_2_Curve25519_encode(rk, pk, 0);
int encode_fail_p = crypto_curve_to_hidden(rm, pk, 0);
if (can_encode_p != encode_fail_p + 1) {
printf("Kleshni and Monocypher cannot encode at the same time!!");
}
if (can_encode_p && memcmp(rk, rm, 32)) {
printf("Kleshni and Monocypher encode differ!!\n");
}
// Encode the point again (negative v coordinate)
bool can_encode_n = Elligator_2_Curve25519_encode(rk, pk, 1);
int encode_fail_n = crypto_curve_to_hidden(rm, pk, 1);
if (can_encode_p != can_encode_n ||
encode_fail_p != encode_fail_n) {
printf("Changing v change encoding capability!!\n");
}
if (can_encode_n && memcmp(rk, rm, 32)) {
printf("Kleshni and Monocypher encode differ!!\n");
}
}
return 0;
}