5
$\begingroup$

At my Day Job(tm) we've encountered a bug wherein if the leading digit of the X or Y value of a public key are zero, "shit happens" (this bug is in our code - I'm not suggesting there's some problem with EC itself. It's just an encoding thing and it's not particularly interesting for this question).

Naively, this suggests that we should expect 1 out of 128 keys to trigger the bug, but that assumes that the X and Y values are evenly distributed. Are they?

If it matters, the curve is secp256r1.

$\endgroup$
  • 1
    $\begingroup$ The leading digit in which base? $\endgroup$ – SEJPM Jan 2 at 20:26
  • $\begingroup$ The first byte (for each of X and Y) of the usual binary encoding. For secp256r1, each value is nominally 32 bytes long, but when it’s “small” it will have a leading zero byte. $\endgroup$ – nsayer Jan 2 at 20:35
  • $\begingroup$ You can experiment it. This can be a good test, right? $\endgroup$ – kelalaka Jan 2 at 20:37
  • $\begingroup$ Well, I was hoping for something non-empirical. $\endgroup$ – nsayer Jan 2 at 20:51
  • 5
    $\begingroup$ I'd expect 1 in 256 keys to trigger the bug if you control the input, and 256 in 256 keys to trigger the bug if an attacker controls the input. $\endgroup$ – Gilles Jan 2 at 23:21
4
$\begingroup$

Yes, the coordinates are more or less evenly distributed, between 0 and the order of the curve (exclusive). The Certicom curves such as secp256r1 generally have an order very near the maximum of the bit size, e.g. the secp256r1 curve has the following order $n$:

FFFFFFFF 00000000 FFFFFFFF FFFFFFFF BCE6FAAD A7179E84 F3B9CAC2 FC632551

So that means that there is about one in 256 chances that the first byte is completely zero for each coordinate.

This is slightly different for e.g. Brainpool curves as the order is randomly chosen (for the correct bit size, of course) and thus lower, brainpoolP256r1 has for instance the following prime order $q$ (same thing, different name):

A9FB57DB A1EEA9BC 3E660A90 9D838D71 8C397AA3 B561A6F7 901E0E82 974856A7

so the chances are slightly higher for brainpool curves that the first byte is fully zero (slightly lower than one in A9 of course, so about 1 in 169).


It gets even more "funny", as I've seen implementations fix this by making sure that the leftmost byte is set to 00 if it is missing, in case constant size X and Y coordinates are required. Of course, that fails if the first two bytes are set to zero, with a much smaller but non-negligible chance. The chance of it starting with 16 bytes of zero are of course negligible, but otherwise you'd better make sure.

A donkey doesn't stumble over the same stone twice, as we say in the Netherlands (A fox is not caught twice in the same snare.)


You can have the same fun with EC private keys or RSA private keys, by the way. The RSA specification lists how to create constant size, unsigned, big endian values that you require in the definition of the I2OSP (Integer to Octet String Primitive) definition.

Note that that definition is a rather mathematical way of saying that you need to prefix enough zero bytes. I've seen a crypto professor implement it using big integer arithmetic. This is definitely not required. It is just a formal description how it commonly looks in computer memory if you encode the value correctly. For more info, see my answers here on crypto and the implemention on SO for Java (shameless plugs, sorry 'bout that).


P.S. The chance of either coordinate starting with a zero byte is about $1 - {({255 \over 256})^2}$. That's ever so slightly lower than $1 \over 128$, but $1 \over 128$ is a good ballpark figure I guess.

$\endgroup$
  • 1
    $\begingroup$ I presume with modulus calculations that the distribution of the coords within 0..N is about evenly distributed and tests do suggest this, but I would happily stand corrected if those empirical results are challenged (even if it doesn't matter much with regards to how this should be solved in practice). $\endgroup$ – Maarten Bodewes Jan 4 at 13:56
  • 1
    $\begingroup$ I believe that's n for secp256k1 not r1, and I'd expect pubkey coords go up to p, while privatekey goes to n? Also, RSA private and public keys mostly use the ASN.1 structures in PKCS1 and thus BER/DER's variable-length signed INTEGER, but RSA plaintext, cryptogram, message representative and signature use fixed-length unsigned I2OSP/OS2IP. One of the small differences between SECG SEC1 and RFC 5915 for EC privatekey, noted in appendix B, is that SEC1 defines I2OSP itself while 5915 references PKCS1v2.1=RFC3447. PS: what happens if the donkey falls on the fox? $\endgroup$ – dave_thompson_085 Jan 5 at 4:42
  • $\begingroup$ @dave_thompson_085 Thanks again, that's a bit more than just one remark. Please allow me some time to edit; I've fixed the copy/paste error first (that was made because I expected the prime curve to be listed first as in the brainpool curve spec). $p$ and $n$ are of course very close, but I'll make sure that I don't spread any confusion. A larger edit will probably have to be made for ASN.1 structures, although I strongly expect some kind of system that requires fixed length structures from the question. $\endgroup$ – Maarten Bodewes Jan 5 at 9:02

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.