While the identity scheme described in RFC-2875 is based on a ubiquitous Diffie-Hellman infrastructure, it is expensive to generate and use when compared to others described here. There are five schemes now implemented in Autokey to prove identity: (1) trusted certificates (TC), (2) private certificates (PC), (3) a modified Schnorr algorithm (IFF aka Identify Friendly or Foe), (4) a modified Guillou-Quisquater algorithm (GQ), and (5) a modified Mu-Varadharajan algorithm (MV). The TC scheme, which involves a certificate trail to a trusted host, is discussed on the Autokey Protocol page. Each of the others involves generating parameters specific to the scheme, together with public and private values used by the scheme.
In order to simplify implementation, each scheme uses existing structures in the OpenSSL library, including those for RSA and DSA cryptography. As these structures are sometimes used in ways far different than their original purpose, they are called cuckoo structures in the descriptions that follow.
In the challenge-response schemes client Alice asks server Bob to prove identity relative to a secret group key b provided by a trusted authority (TA). As shown in the figure above, client Alice rolls random nonce1 and sends to server Bob. Bob rolls random nonce2, performs some mathematical function and returns the response along with the hash of some private value to Alice. Alice performs another mathematical function and verifies the result matches the hash in Bob’s message.
Each of the five schemes is intended for specific use. There are three kinds of keys, trusted agent, server and client. Servers can be clients of other servers, but clients cannot be servers for dependent clients. In general, the goals of the schemes are that clients cannot masquerade as a servers and a servers cannot masquerade as a trusted agents (TAs), but they differ somewhat on how to achieve these goals. To the extent that identity can be verified without revealing the group key, the schemes are properly described as zero-knowledge proofs.
The four identity schemes described here have different design goals and are intended for specific application. The PC scheme is intended for one-way broadcast configurations where clients cannot run a duplex protocol. It is essentially a symmetric key cryptosystem where the certificate itself is the key.
The IFF scheme is intended for servers operated by national laboratories. The servers share a private group key and provide the public client parameters on request. The clients cannot masquerade as servers.
The GQ scheme is intended for exceptionally hostile scenarios where it is necessary to change the client key at relatively frequent intervals. As in the IFF scheme the servers share a private group key and provide the public client parameters on request. In this scheme clients requre a public key to complete the exchange. This is conveyed in the server certificate in an extension field. The certificate can be changed while retaining the same group key.
The MV scheme is intended for the most challenging scenarios where it is necessary to protect against both server and client masquerade. The private values used by the TA to generate the cryptosystem are not available to the servers and the private values used by the servers to encrypt data are not available to the clients. Thus, a client cannot masquerade as a server and a server cannot masquerade as a TA. However, a client can verify a server has the correct group key even though neither the client nor server know the group key, nor can either manufacture a client key acceptable to any other client. A further feature of this scheme is that the TA can collaborate with the servers to revoke client keys.
The PC scheme shown above uses a private certificate as the group key. A certificate is designated private by a X509 Version 3 extension field when generated by the ntp-keygen program in the NTP software distribution. In the Autokey context it functions as a symmetric key. The private certificate is generated by a TA and distributed to all group members by secure means and is never revealed outside the group. A client is marked trusted in the (optional) Parameter Exchange and authentic when the first signature is verified. This scheme is cryptographically strong as long as the private certificate is protected; however, it can be very awkward to refresh the keys or certificate, since new values must be securely distributed to a possibly large population and activated simultaneously.
The Schnorr (IFF) identity scheme can be used when certificates are generated by utilities other than the ntp-keygen program in the NTP software distribution. Certificates can be generated by the OpenSSL library or an external public certificate authority, but conveying an arbitrary public value in a certificate extension field might not be possible. The TA generates the IFF parameters, private key and public key, then sends these values to the servers and the parameters and public key to the clients. Without the private key a client cannot masquerade as a legitimate server.
The DSA parameters are generated by routines in the OpenSSL library. The IFF values hide in a DSA cuckoo structure which uses the same parameters. The values are used by an identity scheme based on DSA cryptography and described in 4 and 5 p. 285. The p is a 512-bit prime, g a generator of the multiplicative group Zp* and _q_ a 160-bit prime that divides _p_ - 1 and is a _q_th root of 1 mod _p_; that is, _gq_ = 1 mod _p_. The TA rolls a private random group key _b_ (0 < _b_ < _q_) and computes the public key _v_ = _gb_, then distributes private (_p_, _q_, _g_, _b_) to the servers using secure means and public (_p_, _q_, _g, v_) to the clients not necessarily using secure means.
The TA generates a DSA parameter structure for use as IFF parameters. The IFF parameters are identical to the DSA parameters, so the OpenSSL library DSA parameter generation routine can be used directly. The DSA parameter structure is written to a file as an encrypted DSA key encoded in PEM. Unused structure members are set to one.
Alice challenges Bob to confirm identity using the following protocol exchange.
The Guillou-Quisquater (GQ) identity scheme is useful when certificates are generated by the ntp-keygen program in the NTP software distribution. The TA generates the GQ parameters, private key and public key, then sends these values to the servers and the parameters to the clients. The public key is inserted in an X.509 extension field when the certificate is generated. Without the private key a client cannot masquerade as a legitimate server.
The RSA parameters are generated by routines in the OpenSSL libbrary. The GQ values hide in a RSA cuckoo structure which uses the same parameters. The values are used in an identity scheme based on RSA cryptography and described in 1 and 5 p. 300 (with errors). The 512-bit public modulus n = p q, where p and q are secret large primes. The TA rolls random group key b (0 < b < n) and sends (n, b) to the servers using secure means. The private key and public key are constructed later.
The TA generates a RSA parameter structure for use as GQ parameters. The RSA parameter structure is written to a file as an encrypted RSA key encoded in PEM. Unused structure members are set to one.
When generating new certificates, the server rolls new random private key u (0 < u < n) and public key its inverse u-1 obscured by the group key v = u-1 b. These values replace the private and public keys normally generated by the RSA scheme. In addition, the public key v is conveyed in a X.509 certificate extension.
Alice challenges Bob to confirm identity using the following exchange.
The Mu-Varadharajan (MV) scheme was originally intended to encrypt broadcast transmissiions to receivers which do not transmit. There is one encryption key for the broadcaster and a separate decryption key for each receiver. It operates something like a pay-per-view satellite broadcasting system where the session key is encrypted by the broadcaster and the decryption keys are held in a tamperproof set-top box. We don’t use it this way, but read on.
In the MV scheme the TA constructs an intricate cryptosystem involving a number of activation keys known only to the TA. The TA decides which keys to activate and provides to the servers an encryption key E and server decryption keys gbar and ghat which depend on the activated keys. The servers have no additional information and, in particular, cannot masquerade as a TA. In addition, the TA provides for each activation key j individual client decryption keys _xbar_and xhat, which do not need to be changed if the TA enables or disables an activation key. The clients have no further information and, in particular, cannot masquerade as a server or TA.
Clients are assigned one of the activation keys and are provided with the corresponding client key. There can be any number of clients sharing the same activation key according to policy. While the machinery to enable and disable ativation keys is included in the current implementation, specific means and interfaces to do this are not yet available, so only one client key is provided.
The scheme is designed so that clients can construct the inverse of E from the server gbar and ghat and client xbar and xhat. In the scheme both E and its inverse are exponentiated by a server nonce, so the product is always one and the secrecy depends on the descrete log problem.
The MV values hide in a DSA cuckoo structure which uses the same parameters, but generated in a different way. The values are used in an encryption scheme similar to El Gamal cryptography and use a polynomial formed from the expansion of product terms (x - xj), as described in 3. The paper has significant errors and serious omissions.
The TA generates the modulus, encryption key and server decryption keys as an encrypted DSA key encoded in PEM. Unused structure members are set to one.
|E||g||private encrypt key||server|
|gbar||priv_key||server decrypt key||server|
|ghat||pub_key||server decrypt key||server|
The TA generates the modulus and client decryption keys as a nonencrypted DSA key encoded in PEM. It is used only by designated recipient(s) who pay a suitably outrageous fee for its use. Unused structure members are set to one.
|xbar||priv_key||client decrypt key||client|
|xhat||pub_key||client decrypt key||client|
The devil is in the details. Let q be the product of n distinct primes s_1j_ (_j_ = 1…_n_), where each _s_1_j_, also called an activation key, has _m_ significant bits. Let prime _p_ = 2_q_ + 1, so that _q_ and each _s_1_j_ divide _p_ - 1 and _p_ has _M_ = _n__m_ + 1 significant bits. Let _g_ be a generator of the multiplicative group _Zp_*; that is, gcd(_g_, _p_ - 1) = 1 and _gq_ = 1 mod _p_. We do modular arithmetic over _Zq_ and then project into _Zp_* as powers of _g._ Sometimes we have to compute an inverse _b_-1 of random _b_ in _Zq_, but for that purpose we require gcd(_b_, _q_) = 1. We expect _M_ to be in the 500-bit range and _n_ relatively small, like 30. The TA uses a nasty probabilistic algorithm to generate the cryptosystem. In the following let the number of bits in the modulus _m_ = 512.
The cryptosystem parameters n, p, q, g, s_1j, s_j (j = 1…n) have been determined. The TA sets up a specific instance of the scheme as follows.
Alice challenges Bob to confirm identity using the following exchange.
1 Guillou, L.C., and J.-J. Quisquatar. A “paradoxical” identity-based signature scheme resulting from zero-knowledge. Proc. CRYPTO 88 Advanced in Cryptology, Springer-Verlag, 1990, 216-231.
3 Mu, Y., and V. Varadharajan. Robust and secure broadcasting. Proc. INDOCRYPT 2001, LNCS 2247, Springer Verlag, 2001, 223-231.
4 Schnorr, C.P. Efficient signature generation for smart cards. J. Cryptology 4, 3 (1991), 161-174.
5 Stinson, D.R. Cryptography - Theory and Practice. CRC Press, Boca Raton, FA, 1995, ISBN 0-8493-8521-0.
Was this page helpful?
Glad to hear it!
Sorry to hear that.