4
$\begingroup$

We are using the Ed25519 signature scheme (which uses Curve25519). A key pair is generated by generating the secret key from random data and then computing the 32-byte (256-bit) public key from said secret key.

The question is about the entropy (randomness) of the public key. We currently use the first 4 bytes of the public key as a "reasonably unique" ID of the public key. We have very limited space and cannot afford more than 4 bytes. Would we improve the uniqueness of the ID if we generate it differently? For example, the ID could be generated by XOR between Bytes 0-3 and Bytes 4-7 of the public key? Or using the first 4 bytes of sha-512 of the public key. Or what?

$\endgroup$
5
  • 6
    $\begingroup$ If you have 10k public keys, then with probability circa 1% two will share the first 4 bytes; with the probability growing sharply as you add more keys. No, there's no other way of generating 4 byte IDs that improve on this... $\endgroup$
    – poncho
    Commented Apr 4, 2017 at 17:39
  • $\begingroup$ @poncho Using the first 4 bytes of a hash over the public key cannot be worse right, or are the most significant bits perfectly distributed? Still, yeah, 4 bytes is not enough for a large number of public keys. A simple counter would be an option? > 4 billion keys... $\endgroup$
    – Maarten Bodewes
    Commented Apr 4, 2017 at 22:24
  • 2
    $\begingroup$ @MaartenBodewes: actually, Curve25519 is traditionally encoded in little-endian order, and so the first 4 bytes are the lower 32 bits, and so we'd expect them to look random. $\endgroup$
    – poncho
    Commented Apr 5, 2017 at 2:52
  • $\begingroup$ Ah yeah, with little endian it makes more sense :) $\endgroup$
    – Maarten Bodewes
    Commented Apr 5, 2017 at 8:37
  • 1
    $\begingroup$ @poncho can you be bothered to pack your first comment into an answer? :) $\endgroup$
    – SEJPM
    Commented Apr 5, 2017 at 9:13

1 Answer 1

4
$\begingroup$

If the 32-bit ids are assigned independently, the best you can hope for with a uniform random assignment of ids is a collision probability no more than about $n^2/2^{32}$ where $n$ is the number of ids you have, if $n$ is small; once $n$ grows past $2^{16}$ the probability of a collision rapidly approaches 1. This is the standard birthday paradox.

Using a nonuniform distribution on ids is even worse. The distribution of bits in the encoding of uniform random curve points is detectably nonuniform—enough that it was one of the first problems reported in Dual_EC_DRBG before everyone realized there was a back door. The low-order 32 bits are probably close enough to uniform in this case that it won't affect the collision probabilities; to alleviate that concern you could pass the encoded curve point through a hash like SHAKE128-32 first.

But you should be more concerned with what you hope to achieve using 32-bit ids in the first place! This has been a consistent source of trouble in OpenPGP, for example—fraudulent keys have been forged and uploaded to the key servers for every 32-bit key id possible. To avoid this trouble, you fundamentally need to:

  1. make the id assignments non-independent, e.g. use a secret permutation of 32-bit strings so that you can have up to four billion ids
  2. use a much larger id space, e.g. 256 bits
  3. accept that collisions will happen and find a way to deal with them gracefully, even under adversarial inputs that are all collisions
$\endgroup$

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.