5
$\begingroup$

I would like to use different EC keys for different purposes in an app, and I would like to easily see the purpose for which particular key (pair) was generated.

With ~65K attempts, I can generate a key-pair where the first byte of both the public and private key are equal to a particular "purpose code" byte value.

(e.g. 0x01 is for signing Xs, 0x02 is for signing Ys, 0x03 is for encrypting Zs, etc.)

Does this significantly weaken the keys, in ways other than lowering the brute-force workload from 2^256 to 2^248?

(The obvious approach is to keep the full 256 bits and use an extra byte for the "purpose" information. Generating a key, chosen to store a little data, has the advantage that this extra data can be encoded in all common key serialization formats, whereas a new "purpose" byte would need all new tools.)

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Usually this kind of information is kept in meta data. You could also store the key fingerprint of the public key (e.g. SHA-1 hash in hex over uncompressed public key value) together with the purpose. If you need to find out what private key is used, then perform signature verification. You do not want to rely on the private key value itself because that means that the private key value must be available. This is not the case in security tokens such as HSM's or smart cards. $\endgroup$
    – Maarten Bodewes ♦
    Oct 27, 2015 at 15:16
  • $\begingroup$ By fixing one byte, you loose aproximately 4 (i.e. 8/2) bits of security. $\endgroup$
    – user27950
    Oct 27, 2015 at 15:16
  • $\begingroup$ @MaartenBodewes I didn't make it clear enough that the a keypair would be selected where both the private and public keys began with the same byte value, so you never need to know the private key, where you wouldn't have needed to do so before. $\endgroup$
    – Thomas Von Panom
    Oct 27, 2015 at 16:28
  • 4
    $\begingroup$ You could use the hash of the private key for the purpose. That should avoid the weakening effect of fixing a byte of the private key. $\endgroup$
    – CodesInChaos
    Oct 27, 2015 at 17:06
  • 1
    $\begingroup$ Also note that the public key consists of the coordinates of a point on the curve. You would probably have to fix the byte value of the X coordinate. If you consider the uncompressed encoding or ASN.1 encoding then the public key starts with a fixed value (e.g. 04h or 30h) so you can wait a long time before those become 01h or 02h. $\endgroup$
    – Maarten Bodewes ♦
    Oct 27, 2015 at 20:17

1 Answer 1

Reset to default
3
$\begingroup$

By fixing the first byte of both the private and the public key you actually reduce the key space by about 16 bits, because only about one in $2^{16}$ key-pairs has that property – as you notice. (If there is no way to exploit the restriction on both keys at the same time, you may lose less security but I would assume the worst.)

Doing this is fine, unless the elliptic curve system is almost too small anyway. If it was insecure, then one in e.g. $2^{16}$ randomly generated keys would be similarly weak.

So worst case you should have ~112 bits of security since a 256-bit elliptic curve usually has about 128 bits of security, but that should be enough.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I agree on worst case. Just wondering...Any idea how to reach it ? Using the info on the private key allows to move from rho to kangaroo but that provides less than $2^8$ speedup due to change in constant factor. Any way to exploit the info on the public key ? $\endgroup$
    – Ruggero
    Oct 28, 2015 at 10:03
  • $\begingroup$ @Ruggero, yeah I don't know anything that could take advantage. $\endgroup$
    – otus
    Oct 28, 2015 at 10:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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