3
$\begingroup$

While sending an EC point we mainly have two options, send it compressed or uncompressed. The uncompressed has prefix 04 and compressed has 02 or 03 which indicates which $y$ to choose. Actually, it is costly, first find the $y$ and $-y$ from the curve equation;

$$E(K): y^2=x^3+ax+b$$ a cube and a square root is required. If the base field is prime then select according to the last bit of $y$ or $-y$. Select the one with 0 if 02 is encoded and select the one with 1 if 03 is encoded.

For 32-byte coordinates, this can save 31-byte of message size ( one byte increased, we send 65 for uncompressed due to prefix). If we consider the cost, it increases the computation, and sending 64-bye instead of 33-byte is not really a huge issue.

Now, Bernstein in their slides mentions that

Never send uncompressed $(x; y)$. Design protocols to compress one coordinate down to $1$ bit, or $0$ bits! Drastically limits possibilities for attacker to choose points.

How does sending compressed points in ECC can limit the attacker's capabilities?

$\endgroup$
8
  • $\begingroup$ Note: the zero is using only $x$ coordinate as ECDH. $\endgroup$ – kelalaka Mar 4 at 20:30
  • $\begingroup$ See crypto.stackexchange.com/questions/25086/… $\endgroup$ – Eugene Styer Mar 4 at 21:28
  • $\begingroup$ @EugeneStyer actually, it says never send, the attack talked in the second answer talks about getting compressed vs uncompressed. $\endgroup$ – kelalaka Mar 4 at 21:34
  • 1
    $\begingroup$ @AmanGrewal Yes, I know and aware of that. I stuck with the word sending. Instead of sending if it were the word communicating I would have no problem. I feel like if I send uncompressed then the attacker has some advantage. $\endgroup$ – kelalaka Mar 4 at 23:02
  • 1
    $\begingroup$ I see. I think you're reading too much into the word send, but maybe there's something here $\endgroup$ – Aman Grewal Mar 4 at 23:17
3
$\begingroup$

If the implementation is using uncompressed point exchange, The attacker gets an opportunity to supply points to Bob that are not in the Curve which was selected by Alice and Bob. The attacker will supply points to Bob that are in curves of a lower order which makes it possible to estimate Bobs secret.

Therefore if the implementation ensures that Bob has to calculate the point then he will come to know that the point being provided is not on the curve selected by Alice and Bob in the first place and will result in coming to know about the attack or the corruption.

Two basic constructs in ECC are the standard curves and Implementation by programmers. The argument is should use of compression be specified in the standard or should be left to the implementation. Since compression is so important for ensuring security it should be made part of the standard( As per the presenters ) to prevent implementation errors.

$\endgroup$
2
  • $\begingroup$ More clarity may merit this answer more upvotes. $\endgroup$ – DannyNiu Mar 5 at 6:37
  • $\begingroup$ Upvoted, however, actually, your approach is the same. Forcing some validation due to the compression and is costlier than usual validation. Yes, if you define your protocol only compressed then you can force some of the validation naturally. I think people unconditionally assume that uncompressed sending implies not validation. So, what if the implementation accepts compressed and uncompressed and does validation of the key. Is there an attack vector if I send uncompressed? $\endgroup$ – kelalaka Mar 5 at 8:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.