Compressing (packing) a point to binary array does not comply with X9.62 standard

[haibren]

tl;dr
the first byte of output from ep_write_bin with flag pack=1 matches the X9.62 standard and other EC packages only 50% of the time.

details:

It seems that when writing an elliptic curve point to a binary array with the pack flag on, the result does not adhere to the X9.62 standard, sections 4.2.1 and 4.3.6.

The code in ep_write_bin does seem to get a single bit from y, and sets the first byte of array bin to either 0x02 or 0x03 according to this single bit, followed by the full value of x. But I believe that the value of the first byte (either 0x02 or 0x03) does not seem to match the chosen bit of y. (According to standard it should be the “rightmost” bit of y, which I read as the least significant bit. Even if not, it does not seem to match consistently any other bit in y, nor its opposite bits).

I wish to point out that I was not using the relic code directly, but I was using a C++ wrapper which appears in cryptoTools ( RCurve files in https://github.com/ladnir/cryptoTools ). Nevertheless, as far as I can tell cryptoTools simply uses the output of ep_write_bin() for its toBytes method, and printing the full point to the console does indeed simply show the values of x, y, z (where z is always finally 1).
Also, although I could not understand where the problem in the code is, it does seem to happen that the reverse operation fromBytes (which calls ep_read_bin) seems to be always successful.
This means that a protocol compressing communication between two parties will not fail if both use relic, but it definitely might fail if just one of them uses relic and the other uses another package.

I do not understand the relic code enough to understand what goes wrong. But I can give an example EC point on which writing it to buffer in a compressed manner seems to not yield the correct result:

Curve: secp256r1
x = C1BFA8D8AD0121D53D66D8288DEEE85F2962465ECD683AFEB1FBF0A9EFE1E8AE
y = 7B4F68EEF44484E5A093967576A36B9B542EA2D547071E9A5FB5BADB92DC9CA6 (rightmost bit is zero)
z = 1

writing it in packed fashion by relic yields:
03c1bfa8d8ad0121d53d66d8288deee85f2962465ecd683afeb1fbf0a9efe1e8ae

But as far as I can understand from the standard, the first byte should have been 0x02. Compressing the same point in java (bounty-castle) or go (the inherent crypto elliptic module) does indeed yield:
02c1bfa8d8ad0121d53d66d8288deee85f2962465ecd683afeb1fbf0a9efe1e8ae

(So only the lsb of the first byte is different).

This does not always happen. As far as I could see, the lsb of the first byte in relic is sometimes identical to the standard and sometimes not. It had 50% chance to be the correct bit (0x02 or 0x03) regardless of what the correct bit is, and regardless of any single specific bit in y. I compared these two bits in a loop randomizing 10000 points (again, using cryptoTools as a C++ wrapper, so not directly using the relic code). I really could not understand from the source code why that happens, nor how uncompressing the array back to a point is always successful regardless of it being inconsistent with the standard.

machine info: kabylake-apple-darwin20.2.0

I have built relic by executing:
tar xzvf relic-relic-toolkit-0.5.0.tar.gz
mkdir relic-target
cd relic-target
cmake -DMULTI=PTHREAD ../relic-relic-toolkit-0.5.0
make
ctest # (passed all 18 tests)
sudo make install

[dfaranha]

Thank you for the notification! I think I understand the issue, the compression method was changed to match a tentative standard for pairing-friendly curves: https://tools.ietf.org/html/draft-irtf-cfrg-pairing-friendly-curves-09

The easiest solution is to pick the compression method depending on the type of curve. Would that work for you?

[haibren]

Ha.. OK
Thanks for the response, and for looking at it!
My team and I just wanted to report this because we thought it was unintentional, and therefore a bug.

[dfaranha]

At the same time it was not necessarily intentional, I just thought no one would bother with older standards these days. :)

[haibren]

Oh... I was not aware that the standard we referred to is considered an old one.
I do not know much about EC and learn these stuff as our project advances. Two weeks ago I did not even know there were standards for these serializations.
If the standard is replaced by a new one (Is this a new NIST standard?), then indeed this is a non-issue. Our project does not require a specific standard (currently, for now).

I just point out that both GO and bouncy-castle use different standards, and I am in no way educated enough to point out if any of them is "better" or "correct". They just claim to implement "the standard".
So it seems that although "standards" exist, interaction between clients using different packages might fail....

I close this issue for now, because our team (currently) does not need a specific change, and also because I really cannot tell which is the "correct" standard.

[dfaranha]

I just updated the code to use the "old" standard for the "old" curves and the "new" standard for the pairing-friendly ones.
That is much more consistent, hope it fixes the issue on your side.

Thanks for reporting!

[haibren]

Thank you for handling it!