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.)

$\endgroup$
  • 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 '15 at 15:16
  • $\begingroup$ By fixing one byte, you loose aproximately 4 (i.e. 8/2) bits of security. $\endgroup$ – user27950 Oct 27 '15 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 '15 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 '15 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 '15 at 20:17
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$
  • $\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 '15 at 10:03
  • $\begingroup$ @Ruggero, yeah I don't know anything that could take advantage. $\endgroup$ – otus Oct 28 '15 at 10:36

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.