Is it possible to sign/verify a key-pair?

Question

We currently have the need to authenticate and verify generated keypairs. Our system allows users to register for our service which generates them a key-pair for use on our network. We are in need of a way to authenticate key-pairs so that we can verify they were generated by us, and not by someone else.

Is it possible to sign each of the generated key-pairs with a master key that can then be used to verify each generated key-pair? I thought this must be possible because it is somewhat similar to the way in which certificates work.

EDIT: To be more clear on what I am after. We are developing a decentralized content network (as a proof of concept). Authoritive Content Providers (those who are authoritive over the content they serve) will be allowed to register their "domain name" via a master registry. This master registry will maintain a master keypair that is used. The registry will issue the content provider a keypair that can be used to digitally sign their content and any information transmitted so that the client can verify that the person transmitting the data is authoritive over the domain name. The issue we are having is how to communicate to the client when we issue a new key pair to a new authoritive host? We thought that if we could sign each keypair with the master registries keypair, then we could hardcode the public key into the client and use it to verify each keypair.

Answer 1

What you are describing is the exact problem of public key distribution that PKI is meant to solve. When your "master key pair" is used to sign the public key of an authoritative content provider for a specific domain, then you are issuing a certificate linking the domain name with a public key. That is what you are intending to do, and that's PKI, whether you want it or not.

Where private keys are generated is orthogonal to the issue. A content provider obtains a certificate (key pair linked to its domain name) through some procedure designed to ensure that only the right provider obtains the private key. There are many ways to organize such a procedure, and the key pair may be generated on your side or on the provider side. Generally speaking, it is preferable that private keys are generated on the provider side, because otherwise the private key has to travel, and we don't like it when private keys travel. But that's only the general assertion; in practice, the context matters a lot. E.g. if you meet the provider's people physically, you can arrange for a physically protected transfer of the private key itself, or of a big fat password which was used to encrypt the private key.

As for the actual formats and protocols, it is highly recommended that you stick to existing standards, i.e. X.509 in the case of certificates. The main reason for that is that the software which is easiest to develop is the software which has already been developed. You will find a lot of X.509 support in the tools you are already using, integrated in your programming framework (e.g. both Java and .NET handle certificates natively) or as extra opensource libraries. It is tempting to reinvent your own format, but experience has repeatedly shown that it is a bad idea. The core point is that it is very hard to design a secure cryptographic protocol properly; it is easy to have something "which works", but the "secure" part is the difficult one, especially since it cannot be tested. Do yourself a favour: don't reinvent the wheel. NIH is called a "syndrome" for good reasons.

Answer 2

We decided to go with a fingerprinting approach. When we issue a provider with a keypair, we hash the public key plus the domain it's authoritive for together, and then sign it using the master registries key. This way, we can verify that a providers key is both valid and authoritive for their domain by verifying the hash of the key+domain Is valid.

If anyone has any better suggestions, I am still all ears.

NB: This is somewhat essentially what PKI does with certificates but without all the extra bloat of unneeded features that our PoC doesn't need.