tech-invite   World Map     

IETF     RFCs     Groups     SIP     ABNFs    |    3GPP     Specs     Glossaries     Architecture     IMS     UICC    |    search     info

RFC 5906

 
 
 

Network Time Protocol Version 4: Autokey Specification

Part 3 of 3, p. 39 to 58
Prev RFC Part

 


prevText      Top      Up      ToC       Page 39 
12.  Security Considerations

   This section discusses the most obvious security vulnerabilities in
   the various Autokey dances.  In the following discussion, the
   cryptographic algorithms and private values themselves are assumed
   secure; that is, a brute force cryptanalytic attack will not reveal
   the host private key, sign private key, cookie value, identity
   parameters, server seed or autokey seed.  In addition, an intruder
   will not be able to predict random generator values.

12.1.  Protocol Vulnerability

   While the protocol has not been subjected to a formal analysis, a few
   preliminary assertions can be made.  In the client/server and
   symmetric dances, the underlying NTP on-wire protocol is resistant to
   lost, duplicate, and bogus packets, even if the clock is not
   synchronized, so the protocol is not vulnerable to a wiretapper
   attack.  The on-wire protocol is resistant to replays of both the
   client request packet and the server reply packet.  A man-in-the-
   middle attack, even if it could simulate a valid cookie, could not
   prove identity.

   In the broadcast dance, the client begins with a volley in client/
   server mode to obtain the autokey values and signature, so has the
   same protection as in that mode.  When continuing in receive-only
   mode, a wiretapper cannot produce a key list with valid signed
   autokey values.  If it replays an old packet, the client will reject
   it by the timestamp check.  The most it can do is manufacture a
   future packet causing clients to repeat the autokey hash operations
   until exceeding the maximum key number.  If this happens the
   broadcast client temporarily reverts to client mode to refresh the
   autokey values.

Top      Up      ToC       Page 40 
   By assumption, a man-in-the-middle attacker that intercepts a packet
   cannot break the wire or delay an intercepted packet.  If this
   assumption is removed, the middleman could intercept a broadcast
   packet and replace the data and message digest without detection by
   the clients.

   As mentioned previously in this memo, the TC identity scheme is
   vulnerable to a man-in-the-middle attack where an intruder could
   create a bogus certificate trail.  To foil this kind of attack,
   either the PC, IFF, GQ, or MV identity schemes must be used.

   A client instantiates cryptographic variables only if the server is
   synchronized to a proventic source.  A server does not sign values or
   generate cryptographic data files unless synchronized to a proventic
   source.  This raises an interesting issue: how does a client generate
   proventic cryptographic files before it has ever been synchronized to
   a proventic source?  (Who shaves the barber if the barber shaves
   everybody in town who does not shave himself?)  In principle, this
   paradox is resolved by assuming the primary (stratum 1) servers are
   proventicated by external phenomenological means.

12.2.  Clogging Vulnerability

   A self-induced clogging incident cannot happen, since signatures are
   computed only when the data have changed and the data do not change
   very often.  For instance, the autokey values are signed only when
   the key list is regenerated, which happens about once an hour, while
   the public values are signed only when one of them is updated during
   a dance or the server seed is refreshed, which happens about once per
   day.

   There are two clogging vulnerabilities exposed in the protocol
   design: an encryption attack where the intruder hopes to clog the
   victim server with needless cryptographic calculations, and a
   decryption attack where the intruder attempts to clog the victim
   client with needless cryptographic calculations.  Autokey uses public
   key cryptography and the algorithms that perform these functions
   consume significant resources.

   In client/server and peer dances, an encryption hazard exists when a
   wiretapper replays prior cookie request messages at speed.  There is
   no obvious way to deflect such attacks, as the server retains no
   state between requests.  Replays of cookie request or response
   messages are detected and discarded by the client on-wire protocol.

   In broadcast mode, a decryption hazard exists when a wiretapper
   replays autokey response messages at speed.  Once synchronized to a
   proventic source, a legitimate extension field with timestamp the

Top      Up      ToC       Page 41 
   same as or earlier than the most recently received of that type is
   immediately discarded.  This foils a man-in-the-middle cut-and-paste
   attack using an earlier response, for example.  A legitimate
   extension field with timestamp in the future is unlikely, as that
   would require predicting the autokey sequence.  However, this causes
   the client to refresh and verify the autokey values and signature.

   A determined attacker can destabilize the on-wire protocol or an
   Autokey dance in various ways by replaying old messages before the
   client or peer has synchronized for the first time.  For instance,
   replaying an old symmetric mode message before the peers have
   synchronize will prevent the peers from ever synchronizing.
   Replaying out of order Autokey messages in any mode during a dance
   could prevent the dance from ever completing.  There is nothing new
   in these kinds of attack; a similar vulnerability even exists in TCP.

Top      Up      ToC       Page 42 
13.  IANA Consideration

   The IANA has added the following entries to the NTP Extensions Field
   Types registry:

      +------------+------------------------------------------+
      | Field Type | Meaning                                  |
      +------------+------------------------------------------+
      |   0x0002   | No-Operation Request                     |
      |   0x8002   | No-Operation Response                    |
      |   0xC002   | No-Operation Error Response              |
      |   0x0102   | Association Message Request              |
      |   0x8102   | Association Message Response             |
      |   0xC102   | Association Message Error Response       |
      |   0x0202   | Certificate Message Request              |
      |   0x8202   | Certificate Message Response             |
      |   0xC202   | Certificate Message Error Response       |
      |   0x0302   | Cookie Message Request                   |
      |   0x8302   | Cookie Message Response                  |
      |   0xC302   | Cookie Message Error Response            |
      |   0x0402   | Autokey Message Request                  |
      |   0x8402   | Autokey Message Response                 |
      |   0xC402   | Autokey Message Error Response           |
      |   0x0502   | Leapseconds Value Message Request        |
      |   0x8502   | Leapseconds Value Message Response       |
      |   0xC502   | Leapseconds Value Message Error Response |
      |   0x0602   | Sign Message Request                     |
      |   0x8602   | Sign Message Response                    |
      |   0xC602   | Sign Message Error Response              |
      |   0x0702   | IFF Identity Message Request             |
      |   0x8702   | IFF Identity Message Response            |
      |   0xC702   | IFF Identity Message Error Response      |
      |   0x0802   | GQ Identity Message Request              |
      |   0x8802   | GQ Identity Message Response             |
      |   0xC802   | GQ Identity Message Error Response       |
      |   0x0902   | MV Identity Message Request              |
      |   0x8902   | MV Identity Message Response             |
      |   0xC902   | MV Identity Message Error Response       |
      +------------+------------------------------------------+

14.  References

14.1.  Normative References

   [RFC5905]  Mills, D., Martin, J., Ed., Burbank, J., and W. Kasch,
              "Network Time Protocol Version 4: Protocol and Algorithms
              Specification", RFC 5905, June 2010.

Top      Up      ToC       Page 43 
14.2.  Informative References

   [DASBUCH]  Mills, D., "Computer Network Time Synchronization - the
              Network Time Protocol", 2006.

   [GUILLOU]  Guillou, L. and J. Quisquatar, "A "paradoxical" identity-
              based signature scheme resulting from zero-knowledge",
              1990.

   [MV]       Mu, Y. and V. Varadharajan, "Robust and secure
              broadcasting", 2001.

   [RFC1305]  Mills, D., "Network Time Protocol (Version 3)
              Specification, Implementation", RFC 1305, March 1992.

   [RFC2412]  Orman, H., "The OAKLEY Key Determination Protocol",
              RFC 2412, November 1998.

   [RFC2522]  Karn, P. and W. Simpson, "Photuris: Session-Key Management
              Protocol", RFC 2522, March 1999.

   [RFC2875]  Prafullchandra, H. and J. Schaad, "Diffie-Hellman Proof-
              of-Possession Algorithms", RFC 2875, July 2000.

   [RFC3279]  Bassham, L., Polk, W., and R. Housley, "Algorithms and
              Identifiers for the Internet X.509 Public Key
              Infrastructure Certificate and Certificate Revocation List
              (CRL) Profile", RFC 3279, April 2002.

   [RFC4210]  Adams, C., Farrell, S., Kause, T., and T. Mononen,
              "Internet X.509 Public Key Infrastructure Certificate
              Management Protocol (CMP)", RFC 4210, September 2005.

   [RFC4302]  Kent, S., "IP Authentication Header", RFC 4302,
              December 2005.

   [RFC4303]  Kent, S., "IP Encapsulating Security Payload (ESP)",
              RFC 4303, December 2005.

   [RFC4306]  Kaufman, C., "Internet Key Exchange (IKEv2) Protocol",
              RFC 4306, December 2005.

   [RFC5280]  Cooper, D., Santesson, S., Farrell, S., Boeyen, S.,
              Housley, R., and W. Polk, "Internet X.509 Public Key
              Infrastructure Certificate and Certificate Revocation List
              (CRL) Profile", RFC 5280, May 2008.

Top      Up      ToC       Page 44 
   [SCHNORR]  Schnorr, C., "Efficient signature generation for smart
              cards", 1991.

   [STINSON]  Stinson, D., "Cryptography - Theory and Practice", 1995.

Top      Up      ToC       Page 45 
Appendix A.  Timestamps, Filestamps, and Partial Ordering

   When the host starts, it reads the host key and host certificate
   files, which are required for continued operation.  It also reads the
   sign key and leapseconds values, when available.  When reading these
   files, the host checks the file formats and filestamps for validity;
   for instance, all filestamps must be later than the time the UTC
   timescale was established in 1972 and the certificate filestamp must
   not be earlier than its associated sign key filestamp.  At the time
   the files are read, the host is not synchronized, so it cannot
   determine whether the filestamps are bogus other than by using these
   simple checks.  It must not produce filestamps or timestamps until
   synchronized to a proventic source.

   In the following, the relation A --> B is Lamport's "happens before"
   relation, which is true if event A happens before event B. When
   timestamps are compared to timestamps, the relation is false if A
   <--> B; that is, false if the events are simultaneous.  For
   timestamps compared to filestamps and filestamps compared to
   filestamps, the relation is true if A <--> B. Note that the current
   time plays no part in these assertions except in (6) below; however,
   the NTP protocol itself ensures a correct partial ordering for all
   current time values.

   The following assertions apply to all relevant responses:

   1.  The client saves the most recent timestamp T0 and filestamp F0
       for the respective signature type.  For every received message
       carrying timestamp T1 and filestamp F1, the message is discarded
       unless T0 --> T1 and F0 --> F1.  The requirement that T0 --> T1
       is the primary defense against replays of old messages.

   2.  For timestamp T and filestamp F, F --> T; that is, the filestamp
       must happen before the timestamp.  If not, this could be due to a
       file generation error or a significant error in the system clock
       time.

   3.  For sign key filestamp S, certificate filestamp C, cookie
       timestamp D and autokey timestamp A, S --> C --> D --> A; that
       is, the autokey must be generated after the cookie, the cookie
       after the certificate, and the certificate after the sign key.

   4.  For sign key filestamp S and certificate filestamp C specifying
       begin time B and end time E, S --> C--> B --> E; that is, the
       valid period must not be retroactive.

Top      Up      ToC       Page 46 
   5.  A certificate for subject S signed by issuer I and with filestamp
       C1 obsoletes, but does not necessarily invalidate, another
       certificate with the same subject and issuer but with filestamp
       C0, where C0 --> C1.

   6.  A certificate with begin time B and end time E is invalid and
       cannot be used to verify signatures if t --> B or E --> t, where
       t is the current proventic time.  Note that the public key
       previously extracted from the certificate continues to be valid
       for an indefinite time.  This raises the interesting possibility
       where a truechimer server with expired certificate or a
       falseticker with valid certificate are not detected until the
       client has synchronized to a proventic source.

Appendix B.  Identity Schemes

   There are five identity schemes in the NTPv4 reference
   implementation: (1) private certificate (PC), (2) trusted certificate
   (TC), (3) a modified Schnorr algorithm (IFF - Identify Friend or
   Foe), (4) a modified Guillou-Quisquater (GQ) algorithm, and (5) a
   modified Mu-Varadharajan (MV) algorithm.

   The PC scheme is intended for testing and development and not
   recommended for general use.  The TC scheme uses a certificate trail,
   but not an identity scheme.  The IFF, GQ, and MV identity schemes use
   a cryptographically strong challenge-response exchange where an
   intruder cannot learn the group key, even after repeated observations
   of multiple exchanges.  These schemes begin when the client sends a
   nonce to the server, which then rolls its own nonce, performs a
   mathematical operation and sends the results to the client.  The
   client performs a second mathematical operation to prove the server
   has the same group key as the client.

Top      Up      ToC       Page 47 
Appendix C.  Private Certificate (PC) Scheme

   The PC scheme shown in Figure 12 uses a private certificate as the
   group key.

                             Trusted
                            Authority
              Secure     +-------------+    Secure
          +--------------| Certificate |-------------+
          |              +-------------+             |
          |                                          |
         \|/                                        \|/
   +-------------+                            +-------------+
   | Certificate |                            | Certificate |
   +-------------+                            +-------------+
       Server                                     Client

            Figure 12: Private Certificate (PC) Identity Scheme

   A certificate is designated private when the X.509v3 Extended Key
   Usage extension field is present and contains "Private".  The private
   certificate is distributed to all other group members by secret
   means, so in fact becomes a symmetric key.  Private certificates are
   also trusted, so there is no need for a certificate trail or identity
   scheme.

Appendix D.  Trusted Certificate (TC) Scheme

   All other schemes involve a conventional certificate trail as shown
   in Figure 13.
                                                           Trusted
                   Host                 Host                 Host
              +-----------+        +-----------+        +-----------+
         +--->|  Subject  |   +--->|  Subject  |   +--->|  Subject  |
         |    +-----------+   |    +-----------+   |    +-----------+
   ...---+    |  Issuer   |---+    |  Issuer   |---+    |  Issuer   |
              +-----------+        +-----------+        +-----------+
              | Signature |        | Signature |        | Signature |
              +-----------+        +-----------+        +-----------+

            Figure 13: Trusted Certificate (TC) Identity Scheme

   As described in RFC 4210 [RFC4210], each certificate is signed by an
   issuer one step closer to the trusted host, which has a self-signed
   trusted certificate.  A certificate is designated trusted when an
   X.509v3 Extended Key Usage extension field is present and contains
   "trustRoot".  If no identity scheme is specified in the parameter
   exchange, this is the default scheme.

Top      Up      ToC       Page 48 
Appendix E.  Schnorr (IFF) Identity Scheme

   The IFF scheme is useful when the group key is concealed, so that
   client keys need not be protected.  The primary disadvantage is that
   when the server key is refreshed all hosts must update the client
   key.  The scheme shown in Figure 14 involves a set of public
   parameters and a group key including both private and public
   components.  The public component is the client key.

                                     Trusted
                                    Authority
                                  +------------+
                                  | Parameters |
                       Secure     +------------+   Insecure
                    +-------------| Group Key  |-----------+
                    |             +------------+           |
                   \|/                                    \|/
              +------------+         Challenge       +------------+
              | Parameters |<------------------------| Parameters |
              +------------+                         +------------+
              |  Group Key |------------------------>| Client Key |
              +------------+         Response        +------------+
                  Server                                 Client

                 Figure 14: Schnorr (IFF) Identity Scheme

   By happy coincidence, the mathematical principles on which IFF is
   based are similar to DSA.  The scheme is a modification an algorithm
   described in [SCHNORR] and [STINSON] (p. 285).  The parameters are
   generated by routines in the OpenSSL library, but only the moduli p,
   q and generator g are used.  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 qth root of 1 mod p; that is, g^q = 1 mod p.  The TA
   rolls a private random group key b (0 < b < q), then computes public
   client key v = g^(q-b) mod p.  The TA distributes (p, q, g, b) to all
   servers using secure means and (p, q, g, v) to all clients not
   necessarily using secure means.

   The TA hides IFF parameters and keys in an OpenSSL DSA cuckoo
   structure.  The IFF parameters are identical to the DSA parameters,
   so the OpenSSL library can be used directly.  The structure shown in
   Figure 15 is written to a file as a DSA private key encoded in PEM.
   Unused structure members are set to one.

Top      Up      ToC       Page 49 
              +----------------------------------+-------------+
              |   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    |
              +---------+----------+-------------+-------------+

                 Figure 15: IFF Identity Scheme Structure

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

   1.  Alice rolls random r (0 < r < q) and sends to Bob.

   2.  Bob rolls random k (0 < k < q), computes y = k + br mod q and x =
       g^k mod p, then sends (y, hash(x)) to Alice.

   3.  Alice computes z = g^y * v^r mod p and verifies hash(z) equals
       hash(x).

   If the hashes match, Alice knows that Bob has the group key b.
   Besides making the response shorter, the hash makes it effectively
   impossible for an intruder to solve for b by observing a number of
   these messages.  The signed response binds this knowledge to Bob's
   private key and the public key previously received in his
   certificate.

Appendix F.  Guillard-Quisquater (GQ) Identity Scheme

   The GQ scheme is useful when the server key must be refreshed from
   time to time without changing the group key.  The NTP utility
   programs include the GQ client key in the X.509v3 Subject Key
   Identifier extension field.  The primary disadvantage of the scheme
   is that the group key must be protected in both the server and
   client.  A secondary disadvantage is that when a server key is
   refreshed, old extension fields no longer work.  The scheme shown in
   Figure 16 involves a set of public parameters and a group key used to
   generate private server keys and client keys.

Top      Up      ToC       Page 50 
                                     Trusted
                                    Authority
                                  +------------+
                                  | Parameters |
                       Secure     +------------+   Secure
                    +-------------| Group Key  |-----------+
                    |             +------------+           |
                   \|/                                    \|/
              +------------+         Challenge       +------------+
              | Parameters |<------------------------| Parameters |
              +------------+                         +------------+
              |  Group Key |                         |  Group Key |
              +------------+         Response        +------------+
              | Server Key |------------------------>| Client Key |
              +------------+                         +------------+
                  Server                                 Client

                 Figure 16: Schnorr (IFF) Identity Scheme

   By happy coincidence, the mathematical principles on which GQ is
   based are similar to RSA.  The scheme is a modification of an
   algorithm described in [GUILLOU] and [STINSON] (p. 300) (with
   errors).  The parameters are generated by routines in the OpenSSL
   library, but only the moduli p and q are used.  The 512-bit public
   modulus is n=pq, where p and q are secret large primes.  The TA rolls
   random large prime b (0 < b < n) and distributes (n, b) to all group
   servers and clients using secure means, since an intruder in
   possession of these values could impersonate a legitimate server.
   The private server key and public client key are constructed later.

   The TA hides GQ parameters and keys in an OpenSSL RSA cuckoo
   structure.  The GQ parameters are identical to the RSA parameters, so
   the OpenSSL library can be used directly.  When generating a
   certificate, the server rolls random server key u (0 < u < n) and
   client key its inverse obscured by the group key v = (u^-1)^b mod n.
   These values replace the private and public keys normally generated
   by the RSA scheme.  The client key is conveyed in a X.509 certificate
   extension.  The updated GQ structure shown in Figure 17 is written as
   an RSA private key encoded in PEM.  Unused structure members are set
   to one.

Top      Up      ToC       Page 51 
              +---------------------------------+-------------+
              |   GQ    |   RSA    |   Item     |   Include   |
              +=========+==========+============+=============+
              |    n    |    n     | modulus    |    all      |
              +---------+----------+------------+-------------+
              |    b    |    e     | group key  |    all      |
              +---------+----------+------------+-------------+
              |    u    |    p     | server key |   server    |
              +---------+----------+------------+-------------+
              |    v    |    q     | client key |   client    |
              +---------+----------+------------+-------------+

                  Figure 17: GQ Identity Scheme Structure

   Alice challenges Bob to confirm identity using the following
   exchange.

   1.  Alice rolls random r (0 < r < n) and sends to Bob.

   2.  Bob rolls random k (0 < k < n) and computes y = ku^r mod n and x
       = k^b mod n, then sends (y, hash(x)) to Alice.

   3.  Alice computes z = (v^r)*(y^b) mod n and verifies hash(z) equals
       hash(x).

   If the hashes match, Alice knows that Bob has the corresponding
   server key u.  Besides making the response shorter, the hash makes it
   effectively impossible for an intruder to solve for u by observing a
   number of these messages.  The signed response binds this knowledge
   to Bob's private key and the client key previously received in his
   certificate.

Appendix G.  Mu-Varadharajan (MV) Identity Scheme

   The MV scheme is perhaps the most interesting and flexible of the
   three challenge/response schemes, but is devilishly complicated.  It
   is most useful when a small number of servers provide synchronization
   to a large client population where there might be considerable risk
   of compromise between and among the servers and clients.  The client
   population can be partitioned into a modest number of subgroups, each
   associated with an individual client key.

   The TA generates an intricate cryptosystem involving encryption and
   decryption keys, together with a number of activation keys and
   associated client keys.  The TA can activate and revoke individual
   client keys without changing the client keys themselves.  The TA
   provides to the servers an encryption key E, and partial decryption
   keys g-bar and g-hat which depend on the activated keys.  The servers

Top      Up      ToC       Page 52 
   have no additional information and, in particular, cannot masquerade
   as a TA.  In addition, the TA provides to each client j individual
   partial decryption keys x-bar_j and x-hat_j, which do not need to be
   changed if the TA activates or deactivates any client key.  The
   clients have no further information and, in particular, cannot
   masquerade as a server or TA.

   The scheme uses an encryption algorithm similar to El Gamal
   cryptography and a polynomial formed from the expansion of product
   terms (x-x_1)(x-x_2)(x-x_3)...(x-x_n), as described in [MV].  The
   paper has significant errors and serious omissions.  The cryptosystem
   is constructed so that, for every encryption key E its inverse is
   (g-bar^x-hat_j)(g-hat^x-bar_j) mod p for every j.  This remains true
   if both quantities are raised to the power k mod p.  The difficulty
   in finding E is equivalent to the discrete log problem.

   The scheme is shown in Figure 18.  The TA generates the parameters,
   group key, server keys, and client keys, one for each client, all of
   which must be protected to prevent theft of service.  Note that only
   the TA has the group key, which is not known to either the servers or
   clients.  In this sense, the MV scheme is a zero-knowledge proof.

                                     Trusted
                                    Authority
                                  +------------+
                                  | Parameters |
                                  +------------+
                                  | Group Key  |
                                  +------------+
                                  | Server Key |
                       Secure     +------------+   Secure
                    +-------------| Client Key |-----------+
                    |             +------------+           |
                   \|/                                    \|/
              +------------+         Challenge       +------------+
              | Parameters |<------------------------| Parameters |
              +------------+                         +------------+
              | Server Key |------------------------>| Client Key |
              +------------+         Response        +------------+
                  Server                                 Client

              Figure 18: Mu-Varadharajan (MV) Identity Scheme

   The TA hides MV parameters and keys in OpenSSL DSA cuckoo structures.
   The MV parameters are identical to the DSA parameters, so the OpenSSL
   library can be used directly.  The structure shown in the figures
   below are written to files as a the fkey encoded in PEM.  Unused
   structure members are set to one.  The Figure 19 shows the data

Top      Up      ToC       Page 53 
   structure used by the servers, while Figure 20 shows the client data
   structure associated with each activation key.

              +---------------------------------+-------------+
              |   MV    |   DSA    |   Item     |   Include   |
              +=========+==========+============+=============+
              |    p    |    p     | modulus    |    all      |
              +---------+----------+------------+-------------+
              |    q    |    q     | modulus    |   server    |
              +---------+----------+------------+-------------+
              |    E    |    g     | private    |   server    |
              |         |          | encrypt    |             |
              +---------+----------+------------+-------------+
              |  g-bar  | priv_key | public     |   server    |
              |         |          | decrypt    |             |
              +---------+----------+------------+-------------+
              |  g-hat  | pub_key  | public     |   server    |
              |         |          | decrypt    |             |
              +---------+----------+------------+-------------+

                   Figure 19: MV Scheme Server Structure


              +---------------------------------+-------------+
              |   MV    |   DSA    |   Item     |   Include   |
              +=========+==========+============+=============+
              |    p    |    p     | modulus    |    all      |
              +---------+----------+------------+-------------+
              | x-bar_j | priv_key | public     |   client    |
              |         |          | decrypt    |             |
              +---------+----------+------------+-------------+
              | x-hat_j | pub_key  | public     |   client    |
              |         |          | decrypt    |             |
              +---------+----------+------------+-------------+

                   Figure 20: MV Scheme Client Structure

   The devil is in the details, which are beyond the scope of this memo.
   The steps in generating the cryptosystem activating the keys and
   generating the partial decryption keys are in [DASBUCH] (page 170
   ff).

   Alice challenges Bob to confirm identity using the following
   exchange.

   1.  Alice rolls random r (0 < r < q) and sends to Bob.

Top      Up      ToC       Page 54 
   2.  Bob rolls random k (0 < k < q) and computes the session
       encryption key E-prime = E^k mod p and partial decryption keys
       g-bar-prime = g-bar^k mod p and g-hat-prime = g-hat^k mod p.  He
       encrypts x = E-prime * r mod p and sends (x, g-bar-prime, g-hat-
       prime) to Alice.

   3.  Alice computes the session decryption key E^-1 = (g-bar-prime)^x-
       hat_j (g-hat-prime)^x-bar_j mod p and verifies that r = E^-1 x.

Appendix H.  ASN.1 Encoding Rules

   Certain value fields in request and response messages contain data
   encoded in ASN.1 distinguished encoding rules (DER).  The BNF grammar
   for each encoding rule is given below along with the OpenSSL routine
   used for the encoding in the reference implementation.  The object
   identifiers for the encryption algorithms and message digest/
   signature encryption schemes are specified in [RFC3279].  The
   particular algorithms required for conformance are not specified in
   this memo.

Appendix I.  COOKIE Request, IFF Response, GQ Response, MV Response

   The value field of the COOKIE request message contains a sequence of
   two integers (n, e) encoded by the i2d_RSAPublicKey() routine in the
   OpenSSL distribution.  In the request, n is the RSA modulus in bits
   and e is the public exponent.

   RSAPublicKey ::= SEQUENCE {
           n ::= INTEGER,
           e ::= INTEGER
   }

   The IFF and GQ responses contain a sequence of two integers (r, s)
   encoded by the i2d_DSA_SIG() routine in the OpenSSL distribution.  In
   the responses, r is the challenge response and s is the hash of the
   private value.

   DSAPublicKey ::= SEQUENCE {
           r ::= INTEGER,
           s ::= INTEGER
   }

   The MV response contains a sequence of three integers (p, q, g)
   encoded by the i2d_DSAparams() routine in the OpenSSL library.  In
   the response, p is the hash of the encrypted challenge value and (q,
   g) is the client portion of the decryption key.

Top      Up      ToC       Page 55 
   DSAparameters ::= SEQUENCE {
           p ::= INTEGER,
           q ::= INTEGER,
           g ::= INTEGER
   }

Appendix J.  Certificates

   Certificate extension fields are used to convey information used by
   the identity schemes.  While the semantics of these fields generally
   conform with conventional usage, there are subtle variations.  The
   fields used by Autokey version 2 include:

   o  Basic Constraints.  This field defines the basic functions of the
      certificate.  It contains the string "critical,CA:TRUE", which
      means the field must be interpreted and the associated private key
      can be used to sign other certificates.  While included for
      compatibility, Autokey makes no use of this field.

   o  Key Usage.  This field defines the intended use of the public key
      contained in the certificate.  It contains the string
      "digitalSignature,keyCertSign", which means the contained public
      key can be used to verify signatures on data and other
      certificates.  While included for compatibility, Autokey makes no
      use of this field.

   o  Extended Key Usage.  This field further refines the intended use
      of the public key contained in the certificate and is present only
      in self-signed certificates.  It contains the string "Private" if
      the certificate is designated private or the string "trustRoot" if
      it is designated trusted.  A private certificate is always
      trusted.

   o  Subject Key Identifier.  This field contains the client identity
      key used in the GQ identity scheme.  It is present only if the GQ
      scheme is in use.

   The value field contains an X.509v3 certificate encoded by the
   i2d_X509() routine in the OpenSSL distribution.  The encoding follows
   the rules stated in [RFC5280], including the use of X.509v3 extension
   fields.

   Certificate ::= SEQUENCE {
           tbsCertificate                  TBSCertificate,
           signatureAlgorithm              AlgorithmIdentifier,
           signatureValue                  BIT STRING
   }

Top      Up      ToC       Page 56 
   The signatureAlgorithm is the object identifier of the message
   digest/signature encryption scheme used to sign the certificate.  The
   signatureValue is computed by the certificate issuer using this
   algorithm and the issuer private key.

   TBSCertificate ::= SEQUENCE {
           version                         EXPLICIT v3(2),
           serialNumber                    CertificateSerialNumber,
           signature                       AlgorithmIdentifier,
           issuer                          Name,
           validity                        Validity,
           subject                         Name,
           subjectPublicKeyInfo            SubjectPublicKeyInfo,
           extensions                      EXPLICIT Extensions OPTIONAL
   }

   The serialNumber is an integer guaranteed to be unique for the
   generating host.  The reference implementation uses the NTP seconds
   when the certificate was generated.  The signature is the object
   identifier of the message digest/signature encryption scheme used to
   sign the certificate.  It must be identical to the
   signatureAlgorithm.

   CertificateSerialNumber
   SET { ::= INTEGER
           Validity ::= SEQUENCE {
                   notBefore              UTCTime,
                   notAfter               UTCTime
           }
   }

   The notBefore and notAfter define the period of validity as defined
   in Appendix B.

   SubjectPublicKeyInfo ::= SEQUENCE {
           algorithm                       AlgorithmIdentifier,
           subjectPublicKey                BIT STRING
   }

   The AlgorithmIdentifier specifies the encryption algorithm for the
   subject public key.  The subjectPublicKey is the public key of the
   subject.

Top      Up      ToC       Page 57 
   Extensions ::= SEQUENCE SIZE (1..MAX) OF Extension
   Extension ::= SEQUENCE {
           extnID                          OBJECT IDENTIFIER,
           critical                        BOOLEAN DEFAULT FALSE,
           extnValue                       OCTET STRING
   }

   SET {
           Name ::= SEQUENCE {
                   OBJECT IDENTIFIER       commonName
                   PrintableString         HostName
           }
   }

   For trusted host certificates, the subject and issuer HostName is the
   NTP name of the group, while for all other host certificates the
   subject and issuer HostName is the NTP name of the host.  In the
   reference implementation, if these names are not explicitly
   specified, they default to the string returned by the Unix
   gethostname() routine (trailing NUL removed).  For other than self-
   signed certificates, the issuer HostName is the unique DNS name of
   the host signing the certificate.

   It should be noted that the Autokey protocol itself has no provisions
   to revoke certificates.  The reference implementation is purposely
   restarted about once a week, leading to the regeneration of the
   certificate and a restart of the Autokey protocol.  This restart is
   not enforced for the Autokey protocol but rather for NTP
   functionality reasons.

   Each group host operates with only one certificate at a time and
   constructs a trail by induction.  Since the group configuration must
   form an acyclic graph, with roots at the trusted hosts, it does not
   matter which, of possibly several, signed certificates is used.  The
   reference implementation chooses a single certificate and operates
   with only that certificate until the protocol is restarted.

Top      Up      ToC       Page 58 
Authors' Addresses

   Brian Haberman (editor)
   The Johns Hopkins University Applied Physics Laboratory
   11100 Johns Hopkins Road
   Laurel, MD  20723-6099
   US

   Phone: +1 443 778 1319
   EMail: brian@innovationslab.net


   Dr. David L. Mills
   University of Delaware
   Newark, DE  19716
   US

   Phone: +1 302 831 8247
   EMail: mills@udel.edu