Add SPAKE preauth support

This is an implementation of draft-ietf-kitten-krb-spake-preauth-05.
SPAKE preauth authenticates using the client principal long-term key,
but protects against offline dictionary attacks.

SPAKE preauth negotiates a group for use by the SPAKE2 algorithm.  The
edwards25519 group is implemented using code adapted from BoringSSL.
The P-256, P-384, and P-521 groups are implemented against OpenSSL.
edwards25519 is enabled by default on the client; no groups are
enabled by default on the KDC.

SPAKE preauth can also include a second factor.  Second factor support
isn't included in this implementation; comments have been left to
indicate what should change when it is added in.

Integration tests (tests/t_spake.py) are included with good coverage
of the negotiation scenarios.

Test vectors from the draft are checked against the group's "result"
operation.  The "keygen" operation is inherently random and is
therefore not tested against the vectors, but is effectively exercised
by the integration tests.

KDC optimistic challenge is implemented.  In the future we should
implement client optimistic SPAKE as well; this will require changes
to the generic client preauth framework.

In the future we should add per-realm configuration to deny encrypted
timestamp and encrypted challenge on a per-realm basis.  This
configuration should stick across client realm referrals.

In the future we should avoid attempting encrypting timestamp or
encrypted challenge if the KDC replies to a single-factor
SPAKEResponse message with PREAUTH_FAILED.  This will require a change
to the generic client preauth framework.

In the future we should make SPAKE support apply to the Windows build,
either by adding support for building plugin DLLs or by moving the
edwards25519 and client code to libkrb5.

[npmccallum@redhat.com: split up internal headers; split out group
registry contents; implemented P-384 and P-521]

ticket: 8647 (new)

6 files changed, 164 insertions, 4 deletions

diff --git a/doc/admin/conf_files/kdc_conf.rst b/doc/admin/conf_files/kdc_conf.rst
index fc6528e..997df08 100644
--- a/doc/admin/conf_files/kdc_conf.rst
+++ b/doc/admin/conf_files/kdc_conf.rst
@@ -43,10 +43,10 @@ The kdc.conf file may contain the following sections:
 [kdcdefaults]
 ~~~~~~~~~~~~~
 
-With two exceptions, relations in the [kdcdefaults] section specify
-default values for realm variables, to be used if the [realms]
-subsection does not contain a relation for the tag.  See the
-:ref:`kdc_realms` section for the definitions of these relations.
+Some relations in the [kdcdefaults] section specify default values for
+realm variables, to be used if the [realms] subsection does not
+contain a relation for the tag.  See the :ref:`kdc_realms` section for
+the definitions of these relations.
 
 * **host_based_services**
 * **kdc_listen**
@@ -56,6 +56,8 @@ subsection does not contain a relation for the tag.  See the
 * **no_host_referral**
 * **restrict_anonymous_to_tgt**
 
+The following [kdcdefaults] variables have no per-realm equivalent:
+
 **kdc_max_dgram_reply_size**
     Specifies the maximum packet size that can be sent over UDP.  The
     default value is 4096 bytes.
@@ -65,6 +67,12 @@ subsection does not contain a relation for the tag.  See the
     daemon.  The value may be limited by OS settings.  The default
     value is 5.
 
+**spake_preauth_kdc_challenge**
+    (String.)  Specifies the group for a SPAKE optimistic challenge.
+    See the **spake_preauth_groups** variable in :ref:`libdefaults`
+    for possible values.  The default is not to issue an optimistic
+    challenge.  (New in release 1.17.)
+
 
 .. _kdc_realms:
 
@@ -403,6 +411,12 @@ The following tags may be specified in a [realms] subsection:
     without allowing anonymous authentication to services.  The
     default value is false.  New in release 1.9.
 
+**spake_preauth_indicator**
+    (String.)  Specifies an authentication indicator value that the
+    KDC asserts into tickets obtained using SPAKE pre-authentication.
+    The default is not to add any indicators.  This option may be
+    specified multiple times.  New in release 1.17.
+
 **supported_enctypes**
     (List of *key*:*salt* strings.)  Specifies the default key/salt
     combinations of principals for this realm.  Any principals created
diff --git a/doc/admin/conf_files/krb5_conf.rst b/doc/admin/conf_files/krb5_conf.rst
index 4ed9832..8cfe5f4 100644
--- a/doc/admin/conf_files/krb5_conf.rst
+++ b/doc/admin/conf_files/krb5_conf.rst
@@ -365,6 +365,21 @@ The libdefaults section may contain any of the following relations:
     with the session key type.  See the **kdc_req_checksum_type**
     configuration option for the possible values and their meanings.
 
+**spake_preauth_groups**
+    A whitespace or comma-separated list of words which specifies the
+    groups allowed for SPAKE preauthentication.  The possible values
+    are:
+
+    ============ ================================
+    edwards25519 Edwards25519 curve (:rfc:`7748`)
+    P-256        NIST P-256 curve (:rfc:`5480`)
+    P-384        NIST P-384 curve (:rfc:`5480`)
+    P-521        NIST P-521 curve (:rfc:`5480`)
+    ============ ================================
+
+    The default value for the client is ``edwards25519``.  The default
+    value for the KDC is empty.  New in release 1.17.
+
 **ticket_lifetime**
     (:ref:`duration` string.)  Sets the default lifetime for initial
     ticket requests.  The default value is 1 day.
diff --git a/doc/admin/index.rst b/doc/admin/index.rst
index b702f40..292a641 100644
--- a/doc/admin/index.rst
+++ b/doc/admin/index.rst
@@ -15,6 +15,7 @@ For administrators
    backup_host.rst
    pkinit.rst
    otp.rst
+   spake.rst
    princ_dns.rst
    enctypes.rst
    https.rst
diff --git a/doc/admin/spake.rst b/doc/admin/spake.rst
new file mode 100644
index 0000000..b65c694
--- /dev/null
+++ b/doc/admin/spake.rst
@@ -0,0 +1,46 @@
+SPAKE Preauthentication
+=======================
+
+SPAKE preauthentication (added in release 1.17) uses public key
+cryptography techniques to protect against password dictionary
+attacks.  Unlike :ref:`PKINIT <pkinit>`, it does not require any
+additional infrastructure such as certificates; it simply needs to be
+turned on.  Using SPAKE preauthentication may modestly increase the
+CPU and network load on the KDC.
+
+SPAKE preauthentication can use one of four elliptic curve groups for
+its password-authenticated key exchange.  The recommended group is
+``edwards25519``; three NIST curves (``P-256``, ``P-384``, and
+``P-521``) are also supported.
+
+By default, SPAKE with the ``edwards25519`` group is enabled on
+clients, but the KDC does not offer SPAKE by default.  To turn it on,
+set the **spake_preauth_groups** variable in :ref:`libdefaults` to a
+list of allowed groups.  This variable affects both the client and the
+KDC.  Simply setting it to ``edwards25519`` is recommended::
+
+    [libdefaults]
+        spake_preauth_groups = edwards25519
+
+Set the **+requires_preauth** and **-allow_svr** flags on client
+principal entries, as you would for any preauthentication mechanism::
+
+    kadmin: modprinc +requires_preauth -allow_srv PRINCNAME
+
+Clients which do not implement SPAKE preauthentication will fall back
+to encrypted timestamp.
+
+By default, SPAKE preauthentication requires an extra network round
+trip to the KDC during initial authentication.  If most of the clients
+in a realm support SPAKE, this extra round trip can be eliminated
+using an optimistic challenge, by setting the
+**spake_preauth_kdc_challenge** variable in :ref:`kdcdefaults` to a
+single group name::
+
+    [kdcdefaults]
+        spake_preauth_kdc_challenge = edwards25519
+
+Using optimistic challenge will cause the KDC to do extra work for
+initial authentication requests that do not result in SPAKE
+preauthentication, but will save work when SPAKE preauthentication is
+used.
diff --git a/doc/formats/cookie.rst b/doc/formats/cookie.rst
index 640955c..e32365d 100644
--- a/doc/formats/cookie.rst
+++ b/doc/formats/cookie.rst
@@ -58,3 +58,40 @@ mechanisms which have separate request and reply types, the request
 type is used; this allows the KDC to determine whether a cookie is
 relevant to a request by comparing the request pa-data types to the
 cookie data types.
+
+SPAKE cookie format (version 1)
+-------------------------------
+
+Inside the SecureCookie wrapper, a data value of type 151 contains
+state for SPAKE pre-authentication.  This data is the concatenation of
+the following:
+
+* a two-byte big-endian version number with the value 1
+* a two-byte big-endian stage number
+* a four-byte big-endian group number
+* a four-byte big-endian length and data for the SPAKE value
+* a four-byte big-endian length and data for the transcript hash
+* zero or more second factor records, each consisting of:
+  - a four-byte big-endian second-factor type
+  - a four-byte big-endian length and data
+
+The stage value is 0 if the cookie was sent with a challenge message.
+Otherwise it is 1 for the first encdata message sent by the KDC during
+an exchange, 2 for the second, etc..
+
+The group value indicates the group number used in the SPAKE challenge.
+
+For a stage-0 cookie, the SPAKE value is the KDC private key,
+represented in the scalar marshalling form of the group.  For other
+cookies, the SPAKE value is the SPAKE result K, represented in the
+group element marshalling form.
+
+For a stage-0 cookie, the transcript hash is the intermediate hash
+after updating with the client support message (if one was sent) and
+challenge.  For other cookies it is the final hash.
+
+For a stage-0 cookie, there may be any number of second-factor
+records, including none; a second-factor type need not create a state
+field if it does not need one, and no record is created for SF-NONE.
+For other cookies, there must be exactly one second-factor record
+corresponding to the factor type chosen by the client.
diff --git a/doc/notice.rst b/doc/notice.rst
index a32e555..8f6b686 100644
--- a/doc/notice.rst
+++ b/doc/notice.rst
@@ -1237,3 +1237,50 @@ The following notice applies to
     STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
     ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
     OF THE POSSIBILITY OF SUCH DAMAGE.
+
+-------------------
+
+The following notice applies to portions of
+``src/plugins/preauth/spake/edwards25519.c`` and
+``src/plugins/preauth/spake/edwards25519_tables.h``:
+
+The MIT License (MIT)
+
+Copyright (c) 2015-2016 the fiat-crypto authors (see the AUTHORS file).
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to
+deal in the Software without restriction, including without limitation the
+rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
+sell copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
+IN THE SOFTWARE.
+
+-------------------
+
+The following notice applies to portions of
+``src/plugins/preauth/spake/edwards25519.c``:
+
+Copyright (c) 2015-2016, Google Inc.
+
+Permission to use, copy, modify, and/or distribute this software for any
+purpose with or without fee is hereby granted, provided that the above
+copyright notice and this permission notice appear in all copies.
+
+THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
+SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
+OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
+CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.