- Briefing Slides
- Related Pages
- Introduction
- Private Certificate (PC) Cryptosystem
- Schnorr (IFF) Cryptosystem
- Guillou-Quisquater (GQ) Cryptosystem
- Mu-Varadharajan (MV) Cryptosystem
- Selected Publications

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 *Z _{p}** and _q_ a 160-bit prime that divides _p_ - 1 and is a _q_th root of 1 mod _p_; that is, _g

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.

IFF | DSA | Item | Include |
---|---|---|---|

p |
p |
modulus | all |

q |
q |
modulus | all |

g |
g |
generator | all |

b |
priv_key |
group key | server |

v |
pub_key |
client key | client |

Alice challenges Bob to confirm identity using the following protocol exchange.

- Alice rolls random
*r*(0 <*r*<*q*) and sends to Bob. - Bob rolls random
*k*(0 <*k*<*q*), computes*y*=*k*+*b r*mod*q*and*x*=*g*_^{k}_ mod _p_, then sends (_y_, hash(_x_)) to Alice. - Alice computes
*z*=*g*^{y}*v*mod^{r}*p*and verifies hash(*z*) equals hash(*x*).

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

GQ | RSA | Item | Include |
---|---|---|---|

n |
n |
modulus | all |

b |
e |
group key | all |

u |
p |
server key | server |

v |
q |
client key | client |

Alice challenges Bob to confirm identity using the following exchange.

- Alice rolls random
*r*(0 <*r*<*n*) and sends to Bob. - Bob rolls random
*k*(1 <*k*<*n*) and computes*y*=*k**u*mod^{r}*n*and*x*=*k*mod^{b}*n*, then sends (*y*, hash(*x*)) to Alice. - Alice computes
*z*=*v*mod^{r}y^{b}*n*and verifies hash(*z*) equals hash(*x*).

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* - *x _{j}*), as described in

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.

MV | DSA | Item | Include |
---|---|---|---|

p |
p |
modulus | all |

q |
q |
modulus | server |

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.

MV | DSA | Item | Include |
---|---|---|---|

p |
p |
modulus | all |

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_1*_{j}_ (_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 _Z_{p}_*; that is, gcd(_g_, _p_ - 1) = 1 and _g^{q}_ = 1 mod _p_. We do modular arithmetic over _Z_{q}_ and then project into _Z_{p}_* as powers of _g._ Sometimes we have to compute an inverse _b_^{-1} of random _b_ in _Z_{q}_, 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 object is to generate a multiplicative group
*Z** modulo a prime _p_ and a subset _Z_{p}_{q}_ mod _q_, where _q_ is the product of _n_ distinct _m_-bit primes _s_1__{j}_ (_j_ = 1…_n_) and _q_ divides _p_ - 1. As a practical matter, it is tough to find more than 31 distinct primes for _mn_ = 512 or 61 primes for _mn_ = 1024. The latter can take several hundred iterations and several minutes on a Sun Blade 1000. - Compute the modulus
*q*as the product of the primes. Compute the modulus*p*as 2_q_ + 1 and test _p_ for primality. If _p_ is composite, replace one of the primes with a new distinct prime and try again. Note that _q_ will hardly be a secret since we have to reveal _p_ to servers and clients. However, factoring _q_ to find the primes should be adequately hard, as this is the same problem considered hard in RSA. Question: is it as hard to find _n_ small prime factors totalling _n_ bits as it is to find two large prime factors totalling _n_ bits? Remember, the bad guy doesn’t know _n_. - Associate with each
*s_1*_{j}_ an element _s_{j}_ such that _s_{j}_ _s_1__{j}_ = _s_1__{j}_ mod _q_. One way to find an _s_{j}_ is to compute the quotient (_q_ + _s_1__{j}_) / _s_1__{j}_mod _p_. The student should prove the remainder is always zero. - Compute the generator
*g*of*Z*using a random roll such that gcd(_{p}*g*,*p*- 1) = 1 and*g*= 1. If not, roll again.^{q}

The cryptosystem parameters *n*, *p*, *q*, *g*, *s_1*_{j}*, s__{j}* (

- Roll random roots
*x*mod_{j}*q*(*j*= 1…*n*) for a polynomial of order*n*. While it may not be strictly necessary, Make sure each root has no factors in common with*q*. - Generate polynomial coefficients
*a*(_{i}*i*= 0…*n*) from the expansion of root products (*x*-*x*) mod_{i}*q*in powers of*x*using a fast method contributed by Charlie Boncelet. - Generate
*g*=_{i}*g*mod^{ai}*p*for all*i*and the generator*g*. Verify prod(*g*) = 1 for all_{i}^{ai}^{xji}*i*,*j*. Note the*a*exponent is computed mod_{i}x_{j}^{i}*q*, but the*g*is computed mod_{i}*p*. Also note the expression given in the paper cited is incorrect. - Make master encryption key
*A*= Prod(*g*) (_{i}^{xj}*i*= 0…*n*,*j*= 1…*n*- 1). Keep it around for awhile, since it is expensive to compute. - Roll private random group key
*b*mod*q*(0 <*b*<*q*), where gcd(*b*,*q*) = 1 to guarantee the inverse exists, then compute*b*^{-1}mod*q*. If*b*is changed, all keys must be recomputed. - Make private client keys
*xbar*=_{j}*b*^{-1}Sum(*x*mod_{i}^{n}*q)*(*i*= 1…n,*i*!=*j*) and*xhat*=_{j}*s*for all_{j}x_{j}^{n}*j*. Note that the keys for the*j_th client involve only*remain secret. The TA sends (*s*and that_{j}*s_1*_{j}*p*,*xbar*,_{j}*xhat*) to the _j_th client(s) using nonsecure means._{j} - The activation key is initially
*q*by construction. The TA revokes client*j*by dividing*q*by*s_1*_{j}_. The quotient becomes the activation key*s*. Note we always have to revoke one key; otherwise, the plaintext and cryptotext would be identical. The TA computes private server encryption key*E*=*A*and server decryption keys^{s}*gbar*=*gbar*and^{s}*ghat*=*ghat*mod^{sb}*p*and sends (*p*,*E*,*gbar*,*ghat*) to the servers using secure means. These values must be recomputed if an activation key is changed.

Alice challenges Bob to confirm identity using the following exchange.

- Alice rolls random
*r*(0 <*r*<*q*) and sends to Bob. - Bob rolls random
*k*(0 <*k*<*q*), computes*y*=*rE*,^{k}*ybar*= _gbar^{k}_and*yhat*=*ghat*, then returns (^{k}*y*,*ybar*,*yhat*) to Alice. - Alice computes the session decryption key (
*E*)^{k}^{-1}=*ybar*^{xhatj}*yhat*then verifies that^{xbarj}__,*y*=*r.*

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.

2 Mills, D.L. The Autokey security architecture, protocol and algorithms. Electrical and Computer Engineering Technical Report 06-1-1, University of Delaware, January 2006, 59 pp, PDF.

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.