Merge branch 'upstream-master'android-q-preview-1

Bug: b/124378762

42 files changed, 7219 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..9d4d4f8
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,3 @@
+build/**
+.gradle/**
+
diff --git a/CONTRIBUTING.md b/CONTRIBUTING.md
new file mode 100644
index 0000000..939e534
--- /dev/null
+++ b/CONTRIBUTING.md
@@ -0,0 +1,28 @@
+# How to Contribute
+
+We'd love to accept your patches and contributions to this project. There are
+just a few small guidelines you need to follow.
+
+## Contributor License Agreement
+
+Contributions to this project must be accompanied by a Contributor License
+Agreement. You (or your employer) retain the copyright to your contribution;
+this simply gives us permission to use and redistribute your contributions as
+part of the project. Head over to <https://cla.developers.google.com/> to see
+your current agreements on file or to sign a new one.
+
+You generally only need to submit a CLA once, so if you've already submitted one
+(even if it was for a different project), you probably don't need to do it
+again.
+
+## Code reviews
+
+All submissions, including submissions by project members, require review. We
+use GitHub pull requests for this purpose. Consult
+[GitHub Help](https://help.github.com/articles/about-pull-requests/) for more
+information on using pull requests.
+
+## Community Guidelines
+
+This project follows [Google's Open Source Community
+Guidelines](https://opensource.google.com/conduct/).
diff --git a/LICENSE b/LICENSE
new file mode 100644
index 0000000..d645695
--- /dev/null
+++ b/LICENSE
@@ -0,0 +1,202 @@
+
+                                 Apache License
+                           Version 2.0, January 2004
+                        http://www.apache.org/licenses/
+
+   TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
+
+   1. Definitions.
+
+      "License" shall mean the terms and conditions for use, reproduction,
+      and distribution as defined by Sections 1 through 9 of this document.
+
+      "Licensor" shall mean the copyright owner or entity authorized by
+      the copyright owner that is granting the License.
+
+      "Legal Entity" shall mean the union of the acting entity and all
+      other entities that control, are controlled by, or are under common
+      control with that entity. For the purposes of this definition,
+      "control" means (i) the power, direct or indirect, to cause the
+      direction or management of such entity, whether by contract or
+      otherwise, or (ii) ownership of fifty percent (50%) or more of the
+      outstanding shares, or (iii) beneficial ownership of such entity.
+
+      "You" (or "Your") shall mean an individual or Legal Entity
+      exercising permissions granted by this License.
+
+      "Source" form shall mean the preferred form for making modifications,
+      including but not limited to software source code, documentation
+      source, and configuration files.
+
+      "Object" form shall mean any form resulting from mechanical
+      transformation or translation of a Source form, including but
+      not limited to compiled object code, generated documentation,
+      and conversions to other media types.
+
+      "Work" shall mean the work of authorship, whether in Source or
+      Object form, made available under the License, as indicated by a
+      copyright notice that is included in or attached to the work
+      (an example is provided in the Appendix below).
+
+      "Derivative Works" shall mean any work, whether in Source or Object
+      form, that is based on (or derived from) the Work and for which the
+      editorial revisions, annotations, elaborations, or other modifications
+      represent, as a whole, an original work of authorship. For the purposes
+      of this License, Derivative Works shall not include works that remain
+      separable from, or merely link (or bind by name) to the interfaces of,
+      the Work and Derivative Works thereof.
+
+      "Contribution" shall mean any work of authorship, including
+      the original version of the Work and any modifications or additions
+      to that Work or Derivative Works thereof, that is intentionally
+      submitted to Licensor for inclusion in the Work by the copyright owner
+      or by an individual or Legal Entity authorized to submit on behalf of
+      the copyright owner. For the purposes of this definition, "submitted"
+      means any form of electronic, verbal, or written communication sent
+      to the Licensor or its representatives, including but not limited to
+      communication on electronic mailing lists, source code control systems,
+      and issue tracking systems that are managed by, or on behalf of, the
+      Licensor for the purpose of discussing and improving the Work, but
+      excluding communication that is conspicuously marked or otherwise
+      designated in writing by the copyright owner as "Not a Contribution."
+
+      "Contributor" shall mean Licensor and any individual or Legal Entity
+      on behalf of whom a Contribution has been received by Licensor and
+      subsequently incorporated within the Work.
+
+   2. Grant of Copyright License. Subject to the terms and conditions of
+      this License, each Contributor hereby grants to You a perpetual,
+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+      copyright license to reproduce, prepare Derivative Works of,
+      publicly display, publicly perform, sublicense, and distribute the
+      Work and such Derivative Works in Source or Object form.
+
+   3. Grant of Patent License. Subject to the terms and conditions of
+      this License, each Contributor hereby grants to You a perpetual,
+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+      (except as stated in this section) patent license to make, have made,
+      use, offer to sell, sell, import, and otherwise transfer the Work,
+      where such license applies only to those patent claims licensable
+      by such Contributor that are necessarily infringed by their
+      Contribution(s) alone or by combination of their Contribution(s)
+      with the Work to which such Contribution(s) was submitted. If You
+      institute patent litigation against any entity (including a
+      cross-claim or counterclaim in a lawsuit) alleging that the Work
+      or a Contribution incorporated within the Work constitutes direct
+      or contributory patent infringement, then any patent licenses
+      granted to You under this License for that Work shall terminate
+      as of the date such litigation is filed.
+
+   4. Redistribution. You may reproduce and distribute copies of the
+      Work or Derivative Works thereof in any medium, with or without
+      modifications, and in Source or Object form, provided that You
+      meet the following conditions:
+
+      (a) You must give any other recipients of the Work or
+          Derivative Works a copy of this License; and
+
+      (b) You must cause any modified files to carry prominent notices
+          stating that You changed the files; and
+
+      (c) You must retain, in the Source form of any Derivative Works
+          that You distribute, all copyright, patent, trademark, and
+          attribution notices from the Source form of the Work,
+          excluding those notices that do not pertain to any part of
+          the Derivative Works; and
+
+      (d) If the Work includes a "NOTICE" text file as part of its
+          distribution, then any Derivative Works that You distribute must
+          include a readable copy of the attribution notices contained
+          within such NOTICE file, excluding those notices that do not
+          pertain to any part of the Derivative Works, in at least one
+          of the following places: within a NOTICE text file distributed
+          as part of the Derivative Works; within the Source form or
+          documentation, if provided along with the Derivative Works; or,
+          within a display generated by the Derivative Works, if and
+          wherever such third-party notices normally appear. The contents
+          of the NOTICE file are for informational purposes only and
+          do not modify the License. You may add Your own attribution
+          notices within Derivative Works that You distribute, alongside
+          or as an addendum to the NOTICE text from the Work, provided
+          that such additional attribution notices cannot be construed
+          as modifying the License.
+
+      You may add Your own copyright statement to Your modifications and
+      may provide additional or different license terms and conditions
+      for use, reproduction, or distribution of Your modifications, or
+      for any such Derivative Works as a whole, provided Your use,
+      reproduction, and distribution of the Work otherwise complies with
+      the conditions stated in this License.
+
+   5. Submission of Contributions. Unless You explicitly state otherwise,
+      any Contribution intentionally submitted for inclusion in the Work
+      by You to the Licensor shall be under the terms and conditions of
+      this License, without any additional terms or conditions.
+      Notwithstanding the above, nothing herein shall supersede or modify
+      the terms of any separate license agreement you may have executed
+      with Licensor regarding such Contributions.
+
+   6. Trademarks. This License does not grant permission to use the trade
+      names, trademarks, service marks, or product names of the Licensor,
+      except as required for reasonable and customary use in describing the
+      origin of the Work and reproducing the content of the NOTICE file.
+
+   7. Disclaimer of Warranty. Unless required by applicable law or
+      agreed to in writing, Licensor provides the Work (and each
+      Contributor provides its Contributions) on an "AS IS" BASIS,
+      WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+      implied, including, without limitation, any warranties or conditions
+      of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
+      PARTICULAR PURPOSE. You are solely responsible for determining the
+      appropriateness of using or redistributing the Work and assume any
+      risks associated with Your exercise of permissions under this License.
+
+   8. Limitation of Liability. In no event and under no legal theory,
+      whether in tort (including negligence), contract, or otherwise,
+      unless required by applicable law (such as deliberate and grossly
+      negligent acts) or agreed to in writing, shall any Contributor be
+      liable to You for damages, including any direct, indirect, special,
+      incidental, or consequential damages of any character arising as a
+      result of this License or out of the use or inability to use the
+      Work (including but not limited to damages for loss of goodwill,
+      work stoppage, computer failure or malfunction, or any and all
+      other commercial damages or losses), even if such Contributor
+      has been advised of the possibility of such damages.
+
+   9. Accepting Warranty or Additional Liability. While redistributing
+      the Work or Derivative Works thereof, You may choose to offer,
+      and charge a fee for, acceptance of support, warranty, indemnity,
+      or other liability obligations and/or rights consistent with this
+      License. However, in accepting such obligations, You may act only
+      on Your own behalf and on Your sole responsibility, not on behalf
+      of any other Contributor, and only if You agree to indemnify,
+      defend, and hold each Contributor harmless for any liability
+      incurred by, or claims asserted against, such Contributor by reason
+      of your accepting any such warranty or additional liability.
+
+   END OF TERMS AND CONDITIONS
+
+   APPENDIX: How to apply the Apache License to your work.
+
+      To apply the Apache License to your work, attach the following
+      boilerplate notice, with the fields enclosed by brackets "[]"
+      replaced with your own identifying information. (Don't include
+      the brackets!)  The text should be enclosed in the appropriate
+      comment syntax for the file format. We also recommend that a
+      file or class name and description of purpose be included on the
+      same "printed page" as the copyright notice for easier
+      identification within third-party archives.
+
+   Copyright [yyyy] [name of copyright owner]
+
+   Licensed under the Apache License, Version 2.0 (the "License");
+   you may not use this file except in compliance with the License.
+   You may obtain a copy of the License at
+
+       http://www.apache.org/licenses/LICENSE-2.0
+
+   Unless required by applicable law or agreed to in writing, software
+   distributed under the License is distributed on an "AS IS" BASIS,
+   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+   See the License for the specific language governing permissions and
+   limitations under the License.
diff --git a/METADATA b/METADATA
new file mode 100644
index 0000000..1548a33
--- /dev/null
+++ b/METADATA
@@ -0,0 +1,12 @@
+name: "Ukey2"
+description:
+    "UKEY2 is a Diffie-Hellman based authenticated key exchange protocol."
+
+third_party {
+  url {
+    type: ARCHIVE
+    value: "https://user.git.corp.google.com/michalp/ukey2/"
+  }
+  version: "1.0"
+  last_upgrade_date { year: 2018 month: 12 day: 28 }
+}
diff --git a/MODULE_LICENSE_APACHE2 b/MODULE_LICENSE_APACHE2
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/MODULE_LICENSE_APACHE2
diff --git a/NOTICE b/NOTICE
new file mode 120000
index 0000000..7a694c9
--- /dev/null
+++ b/NOTICE
@@ -0,0 +1 @@
+LICENSE
\ No newline at end of file
diff --git a/README b/README
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/README
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..2f56370
--- /dev/null
+++ b/README.md
@@ -0,0 +1,329 @@
+# Ukey2
+This is not an officially supported Google product
+
+**Coathored by:** Alexei Czeskis, Thai Duong, Eduardo' Vela'' \<Nava\>, and Adam Stubblefield.
+
+**Status:** Implemented in Java (aczeskis@google.com)
+
+**Design reviewers:** Thai Duong, Bruno Blanchet, Martin Abadi, and Bo Wang
+
+**Implementation reviewer**: Thai Duong
+
+**Last Updated:** roughly in September 2016
+
+
+
+# Overview
+
+UKEY2 is a Diffie-Hellman based authenticated key exchange protocol.
+
+At the end of a UKEY2 run, a client and server have a shared master secret that can be used to
+derive keys which can be used in a subsequent protocol. UKEY2 only implicitly guarantees that
+servers know that clients believe the protocol finished correctly; that is, until a server
+receives a message on the next protocol from the client it does not know that the handshake
+completed.
+
+The intended usage of UKEY2 is to establish a secure channel between two user devices,
+e.g., laptop with Chromecast, phone with Google Glass, etc. The secure channel then can be used to
+transmit passwords or other credentials. It is especially useful when one wants to connect a brand
+ new device to a password-protected WIFI network.  UKEY2 is also usable over low-bandwidth
+transports like Bluetooth Low Energy (see [Performance](#performance)).
+
+# Message Framing
+
+Each UKEY2 message is framed inside an outer protobuf message:
+
+
+```
+message Ukey2Message {
+  enum Type {
+    UNKNOWN_DO_NOT_USE = 0;
+    ALERT = 1;
+    CLIENT_INIT = 2;
+    SERVER_INIT = 3;
+    CLIENT_FINISH = 4;
+  }
+
+  optional Type message_type = 1;   // Identifies message type
+  optional bytes message_data = 2;  // Actual message, to be parsed according to
+                                    // message_type
+}
+```
+
+
+
+# Alerts
+
+In case an error occurs, the client and server will reply with an Alert:
+
+
+```
+message Ukey2Alert {
+  enum AlertType {
+    // Framing errors
+    BAD_MESSAGE = 1;             // The message could not be deserialized
+    BAD_MESSAGE_TYPE = 2;        // message_type has an undefined value
+    INCORRECT_MESSAGE = 3;       // message_type received does not correspond to expected
+                                 // type at this stage of the protocol
+    BAD_MESSAGE_DATA = 4;        // Could not deserialize message_data as per value in
+                                 // message_type
+
+    // ClientInit and ServerInit errors
+    BAD_VERSION = 100;           // version is invalid; server cannot find suitable version
+                                 // to speak with client.
+    BAD_RANDOM = 101;            // Random data is missing or of incorrect length
+    BAD_HANDSHAKE_CIPHER = 102;  // No suitable handshake ciphers were found
+    BAD_NEXT_PROTOCOL = 103;     // The next protocol is missing, unknown, or unsupported
+    BAD_PUBLIC_KEY = 104;        // The public key could not be parsed
+
+    // Other errors
+    INTERNAL_ERROR = 200;       // An internal error has occurred.  error_message may
+                                // contain additional details for logging and debugging.
+  }
+
+  optional AlertType type = 1;
+  optional string error_message = 2;
+}
+```
+
+
+The type corresponds to the error that caused the `Alert` to be sent. Upon encountering an error,
+clients and servers send an Alert of the proper type and close the connection; all alerts are
+fatal. Upon receiving an `Alert`, clients and servers must close the connection, even if they
+cannot parse the `Alert`.  The `Alert` message may contain an optional `error_message` string
+that may be used to describe error details for logging.
+
+# Handshake Ciphersuites
+
+UKEY2 supports negotiation of the cryptographic primitives used in the handshake. Two primitives
+are required, a Diffie-Hellman function and a cryptographic hash function, which are represented
+by a single enum:
+
+
+```
+enum Ukey2HandshakeCipher {
+  RESERVED = 0;
+  P256_SHA512 = 100;        // NIST P-256 used for ECDH, SHA512 used for commitment
+  CURVE25519_SHA512 = 200;  // Curve 25519 used for ECDH, SHA512 used for commitment
+}
+```
+
+
+The implementations of all primitives must resist timing side-channel attacks. A summary of
+handshake ciphersuite negotiation is (see ClientInit and ServerInit messages for full details):
+
+*   The client enumerates the primitives it supports and the server choose the highest (by enum value) cipher that it also supports.
+*   The server replies with a public key using the chosen cipher and sends its own list of supported handshake cipher suites so that the client can verify that the right selection was made.
+
+
+# Handshake Details
+
+The UKEY2 handshake consists of three messages. First, the client sends a `ClientInit` message to
+the server -- conceptually, this consists of a list of cipher suites and a commitment to an
+ephemeral public key for each suite. The server responds with a `ServerInit` -- conceptually,
+this is the server's chosen cipher suite and an ephemeral public key for the cipher suites
+selected by the server.  Finally, the client responds with a `ClientFinished` -- conceptually,
+this consists of an ephemeral public key matching the cipher suite selected by the server.
+
+After the handshake, both client and server derive authentication strings, which may be shown to
+users for visual comparison or sent over some other channel in order to authenticate the handshake.
+The client and server also derive session keys for the next protocol.
+
+## The `ClientInit` Message
+
+The `ClientInit` message is defined as follows:
+
+
+```
+message Ukey2ClientInit {
+  optional int32 version = 1;  // highest supported version for rollback protection
+  optional bytes random = 2;   // random bytes for replay/reuse protection
+
+  // One commitment (hash of ClientFinished containing public key) per supported cipher
+  message CipherCommitment {
+    optional Ukey2HandshakeCipher handshake_cipher = 1;
+    optional bytes commitment = 2;
+  }
+  repeated CipherCommitment cipher_commitments = 3;
+
+  // Next protocol that the client wants to speak.
+  optional string next_protocol = 4;
+}
+```
+
+
+The `version` field is the maximum version that the client supports.  It should be 1 for now. The `random` field is exactly 32 cryptographically secure random bytes.  The `cipher_commitment` field is a protobuf consisting of a handshake cipher and a commitment which is a hash of the `ClientFinished` message that would be sent if the cipher were selected (the serialized, including framing, raw bytes of the last handshake message sent by the client), calculated with the hash function and the Diffie-Hellman function from the handshake cipher. The client includes each commitment in the order of their preference.  Note that only one commitment per `handshake_cipher` is allowed.  The client also includes the `next_protocol` field that specifies that the client wants to use to speak to the server.  Note that this protocol must implicitly imply a key length.  UKEY2, however, does not provide a namespace for the `next_protocol` values in order to provide layers separation between the handshake and the next protocols.
+
+
+## Interpreting `ClientInit`
+
+Upon receiving the `ClientInit` message, the server should:
+
+
+
+1.  Deserialize the protobuf; send an `Alert.BAD_MESSAGE` message if deserialization fails.
+1.  Verify that `message_type == Type.CLIENT_INIT`; send an `Alert.BAD_MESSAGE_TYPE` message if mismatch occurs.
+1.  Deserialize `message_data` as a `ClientInit` message; send an `Alert.BAD_MESSAGE_DATA` message if deserialization fails.
+1.  Check that `version == 1`; send `Alert.BAD_VERSION` message if mismatch.
+1.  Check that `random` is exactly 32 bytes; send `Alert.BAD_RANDOM` message if not.
+1.  Check to see if any of the `handshake_cipher` in `cipher_commitment` are acceptable. Servers should select the first `handshake_cipher` that it finds acceptable to support clients signaling deprecated but supported HandshakeCiphers. If no `handshake_cipher` is acceptable (or there are no HandshakeCiphers in the message), the server sends an `Alert.BAD_HANDSHAKE_CIPHER` message.
+1.  Checks that `next_protocol` contains a protocol that the server supports.  Send an `Alert.BAD_NEXT_PROTOCOL` message if not.
+
+If no alerts have been sent, the server replies with the `ServerInit` message.
+
+
+## The `ServerInit` Message 
+
+The `ServerInit` message is as follows
+
+
+```
+message Ukey2ServerInit {
+  optional int32 version = 1;  // highest supported version for rollback protection
+  optional bytes random = 2;   // random bytes for replay/reuse protection
+
+  // Selected Cipher and corresponding public key
+  optional Ukey2HandshakeCipher handshake_cipher = 3;
+  optional bytes public_key = 4;
+}
+```
+
+
+For now, `version` must be 1.  The random field is exactly 32 cryptographically secure random
+bytes.  The `handshake_cipher` field contains the server-chosen `HandshakeCipher`.  The
+`public_key` field contains the server-chosen corresponding public key.
+
+
+## Interpreting `ServerInit`
+
+When a client receives a `ServerInit` after having sent a `ClientInit`, it performs the following actions:
+
+
+1.  Deserialize the protobuf; send an `Alert.BAD_MESSAGE` message if deserialization fails.
+1.  Verify that `message_type == Type.SERVER_INIT`; send an `Alert.BAD_MESSAGE_TYPE` message if mismatch occurs.
+1.  Deserialize `message_data` as a `ServerInit` message; send an `Alert.BAD_MESSAGE_DATA` message if deserialization fails.
+1.  Check that `version == 1`; send `Alert.BAD_VERSION` message if mismatch.
+1.  Check that `random` is exactly 32 bytes; send `Alert.BAD_RANDOM` message if not.
+1.  Check that `handshake_cipher` matches a handshake cipher that was sent in
+`ClientInit.cipher_commitments`. If not, send an `Alert.BAD_HANDSHAKECIPHER` message.
+1.  Check that `public_key` parses into a correct public key structure.  If not, send an `Alert.BAD_PUBLIC_KEY` message.
+
+If no alerts have been sent, the client replies with the `ClientFinished` message.  After sending
+the `ClientFinished` message, the Client considers the handshake complete.
+
+
+**IMPORTANT:** The client should compute the authentication string `AUTH_STRING` and
+the next-protocol secret `NEXT_SECRET` (see below).  The client should use an out-of-band
+channel to verify the authentication string before proceeding to the next protocol.
+
+
+## The ClientFinished Message 
+
+The `ClientFinished` message is as follows:
+
+
+```
+message Ukey2ClientFinished {
+  optional bytes public_key = 1;  // public key matching selected handshake cipher
+}
+```
+
+
+The `public_key` contains the Client's public key (whose commitment was sent in the `ClientInit`
+message) for the server-selected handshake cipher.
+
+
+## Interpreting ClientFinished 
+
+When a server receives a `ClientFinished` after having sent a `ServerInit`, it performs the
+following actions:
+
+
+1.  Deserialize the protobuf; terminate the connection if deserialization fails.
+1.  Verify that `message_type == Type.CLIENT_FINISHED`; terminate the connection if mismatch occurs.
+1.  Verify that the hash of the `ClientFinished` matches the expected commitment for the chosen `handshake_cipher` from `ClientInit`.  Terminate the connection if the expected match fails.
+1.  Deserialize `message_data` as a `ClientFinished` message; terminate the connection if deserialization fails.
+1.  Check that `public_key` parses into a correct public key structure.  If not, terminate the connection.
+
+Note that because the client is not expecting a response, any error results in connection termination.
+
+After parsing the `ClientFinished` message, the Server considers the handshake complete.
+
+
+**IMPORTANT:** The server should compute the authentication string `AUTH_STRING` and the
+next-protocol secret `NEXT_SECRET` (see below).  The server should use an out-of-band channel to
+verify the authentication string before proceeding to the next protocol.
+
+
+# Deriving the Authentication String and the Next-Protocol Secret
+
+Let `DHS` = the negotiated Diffie-Hellman key derived from the Client and Server public keys.
+
+Let `M_1` = the serialized (including framing) raw bytes of the first message sent by
+the client
+
+Let `M_2` = the serialized (including framing) raw bytes of the first message sent by
+the server
+
+Let `Hash` = the hash from HandshakeCipher
+
+Let `L_auth` = length of authentication string in bytes.  Note that this length can
+be short (e.g., a 6 digit visual confirmation code).
+
+Let `L_next` = length of next protocol key
+
+Let `HKDF-Extract` and `HKDF-Expand` be as defined in [RFC5869](https://tools.ietf.org/html/rfc5869)
+instantiated with the hash from the `HandshakeCipher`.
+
+Let `PRK_AUTH = HKDF-Extract("UKEY2 v1 auth", DHS)`
+
+Let `PRK_NEXT = HKDF-Extract("UKEY2 v1 next", DHS)`
+
+Then `AUTH_STRING = HKDF-Expand(PRK_AUTH, M_1|M_2, L_auth)`
+
+Then `NEXT_SECRET = HKDF-Expand(PRK_NEXT, M_1|M_2, L_next)`
+
+
+# Security Discussion
+
+If client and server authenticate one-another using the `AUTH_STRING` through an out-of-band
+mechanism, we believe that this handshake is resistant to an active man-in-the-middle attacker.
+The attacker, whether he/she plays the role of the client or server, is forced to commit to a
+public key before seeing the other-party's public key.
+
+The authentication string and next secret are computed in such a way that knowledge of one does
+not allow an attacker to compute the other.  That is, if the attacker observed the `AUTH_STRING`
+(if it was shown on a monitor for example), the attacker could not compute `NEXT_SECRET`.
+Furthermore, both the authentication string and next secret depend on the full handshake
+transcript -- a manipulation of any handshake message by an adversary would change both the
+ authentication string and the next secret.  Note that although the last message is not directly
+ included in the HKDF computation, it is included as part of the commitment sent in `M_1.`
+
+@shabsi pointed out that by having the `HKDF` info field have bits that also go into making the
+`PRK`, this violates some security proof.  Those "shared" bits are the public keys that are sent
+in `M_2` and `M_3` and are also used to derive the DHS.  Though the "proof" may
+ not hold in theory, we do believe the security of the handshake is maintained in practice.
+
+A natural question may be why we didn't use
+[Short Authentication Strings](https://www.iacr.org/archive/crypto2005/36210303/36210303.pdf)
+(SAS).  The answer is two-fold.  First, traditional SAS does not incorporate a key exchange, only
+authentication; UKEY2 provides both.  Second, the paper does not give concrete primitives,
+instead describing abstract functions such as `commit() `and `open()`.  One concrete
+implementation of these functions would look similar to what UKEY2 does.
+
+Bruno Blanchet performed a formal proof of a simplified version of UKEY2.
+
+# Performance
+
+The messages are fairly compact.  Running a test where the client sent a single commitment for a
+`P256_SHA512` cipher and the `next_protocol` was set to "`AES_256_CBC-HMAC_SHA256"`, the total
+size of the messages were:
+
+
+| Message        | Length in Bytes |
+|:---------------|----------------:|
+|`ClientInit`    | 136             |
+|`ServerInit`    | 117             |
+|`ClientFinished`| 79              |
+
+
diff --git a/build.gradle b/build.gradle
new file mode 100644
index 0000000..bb46e75
--- /dev/null
+++ b/build.gradle
@@ -0,0 +1,23 @@
+apply plugin: 'java'
+apply plugin: 'com.google.protobuf'
+
+repositories {
+    jcenter()
+}
+
+buildscript {
+  repositories {
+    jcenter()
+  }
+  dependencies {
+    classpath 'com.google.protobuf:protobuf-gradle-plugin:0.8.7'
+  }
+}
+
+dependencies {
+    compile  "com.google.code.findbugs:jsr305:3.0.0"
+    compile "com.google.protobuf:protobuf-java:3.4.0"
+    compile "com.google.guava:guava:r05"
+}
+
+
diff --git a/src/.gradle/3.2.1/taskArtifacts/fileSnapshots.bin b/src/.gradle/3.2.1/taskArtifacts/fileSnapshots.bin
new file mode 100644
index 0000000..f0cc1a8
--- /dev/null
+++ b/src/.gradle/3.2.1/taskArtifacts/fileSnapshots.bin
diff --git a/src/.gradle/3.2.1/taskArtifacts/taskArtifacts.bin b/src/.gradle/3.2.1/taskArtifacts/taskArtifacts.bin
new file mode 100644
index 0000000..b1f5426
--- /dev/null
+++ b/src/.gradle/3.2.1/taskArtifacts/taskArtifacts.bin
diff --git a/src/.gradle/3.2.1/taskArtifacts/taskArtifacts.lock b/src/.gradle/3.2.1/taskArtifacts/taskArtifacts.lock
new file mode 100644
index 0000000..6fa2a90
--- /dev/null
+++ b/src/.gradle/3.2.1/taskArtifacts/taskArtifacts.lock
diff --git a/src/main/java/com/google/security/annotations/CryptoAnnotation.java b/src/main/java/com/google/security/annotations/CryptoAnnotation.java
new file mode 100644
index 0000000..7f4230d
--- /dev/null
+++ b/src/main/java/com/google/security/annotations/CryptoAnnotation.java
@@ -0,0 +1,68 @@
+/* Copyright 2018 Google LLC
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+// Copyright 2007 Google Inc. All Rights Reserved
+
+package com.google.security.annotations;
+
+import java.lang.annotation.ElementType;
+import java.lang.annotation.Retention;
+import java.lang.annotation.RetentionPolicy;
+import java.lang.annotation.Target;
+
+/**
+ * Crypto Key Annotation: Label any cryptographic keys in code with this 
+ * annotation. This will help identify cryptographic keys that are exposed in 
+ * source code. Keys in source code should be annotated with an owner, purpose,
+ * removal priority, and leak severity.
+ * 
+ * Example of usage:
+ *  @CryptoAnnotation(
+ *     purpose = CryptoAnnotation.Purpose.AUTHENTICATION,
+ *     owner = "sweis",
+ *     bugId = 7041243,
+ *     leakSeverity = CryptoAnnotation.LeakSeverity.S2,
+ *     removalPriority = CryptoAnnotation.RemovalPriority.P1,
+ *     description = "This key is used to sign blah blah blah."
+ *     removalDate = "9/2007
+ * )
+ * byte[] keyBytes = {0xDE, 0xAD, 0xBE, 0xEF};
+ * 
+ * @author sweis@google.com (Steve Weis)
+ */
+@Retention(RetentionPolicy.SOURCE)
+@Target({ElementType.FIELD, ElementType.LOCAL_VARIABLE})
+public @interface CryptoAnnotation {
+  /*
+   * Keys with "encryption" and "authentication" purposes should be removed
+   * from source code.
+   * 
+   * Keys with "obfuscation" and "integrity check" purposes do not necessarily
+   * need to be cryptographically strong. They may or may not be removed from
+   * code at the discretion of the code owner.
+   */
+  public enum Purpose {ENCRYPTION, AUTHENTICATION, OBFUSCATION,
+    INTEGRITY_CHECK, PASSWORD, OTHER}
+  public enum LeakSeverity {S0, S1, S2, S3, S4, NoRisk}
+  public enum RemovalPriority {P0, P1, P2, P3, P4, WillNotFix}
+  
+  LeakSeverity leakSeverity();
+  RemovalPriority removalPriority();
+  int bugId() default 0;
+  String owner(); // Will be contacted in the event a key is leaked
+  Purpose purpose();
+  String description() default "";
+  String removalDate() default "";
+}
+
diff --git a/src/main/java/com/google/security/annotations/SuppressInsecureCipherModeCheckerNoReview.java b/src/main/java/com/google/security/annotations/SuppressInsecureCipherModeCheckerNoReview.java
new file mode 100644
index 0000000..93dc716
--- /dev/null
+++ b/src/main/java/com/google/security/annotations/SuppressInsecureCipherModeCheckerNoReview.java
@@ -0,0 +1,57 @@
+/* Copyright 2018 Google LLC
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.google.security.annotations;
+
+import java.lang.annotation.Documented;
+import java.lang.annotation.ElementType;
+import java.lang.annotation.Retention;
+import java.lang.annotation.RetentionPolicy;
+import java.lang.annotation.Target;
+
+import javax.crypto.Cipher;
+
+/**
+ * This annotation is used to disable the InsecureCipherMode Error Prone checker for legacy code
+ * that didn't undergo a security review by ISE.
+ *
+ * <p>A {@link Cipher} object is created using one of the overloads of the
+ * {@link Cipher#getInstance()} method. This method takes a specification of the transformer either
+ * as a triple "Algorithm/Mode/Padding" or just "Algorithm", using the provider's default settings.
+ * The InsecureCipherMode checker implemented in Error Prone flags all call sites of
+ * {@link Cipher#getInstance()}, where either the insecure ECB mode or the provider's default mode
+ * is used. This method annotation is used to suppress the Error Prone checker for legacy code
+ * without review by ISE. The annotation is BUILD-visibility restricted and every use must be vetted
+ * by the ISE team.
+ *
+ * <p>Example of usage:
+ * <pre>
+ * {@code
+ * @SuppressInsecureCipherModeCheckerNoReview
+ * private String decrypt(String[] input) {
+ * Cipher aesCipher = Cipher.getInstance("AES");
+ * aesCipher.init(Cipher.DECRYPT_MODE, new SecretKeySpec(rawKeyMaterial, "AES"));
+ * // ...
+ * }
+ * }
+ * </pre>
+ *
+ * @author avenet@google.com (Arnaud J. Venet)
+ *
+ */
+@Documented
+@Target({ElementType.FIELD, ElementType.METHOD, ElementType.PARAMETER, ElementType.CONSTRUCTOR,
+    ElementType.LOCAL_VARIABLE})
+@Retention(RetentionPolicy.SOURCE)
+public @interface SuppressInsecureCipherModeCheckerNoReview {}
diff --git a/src/main/java/com/google/security/annotations/SuppressInsecureCipherModeCheckerPendingReview.java b/src/main/java/com/google/security/annotations/SuppressInsecureCipherModeCheckerPendingReview.java
new file mode 100644
index 0000000..a7957c1
--- /dev/null
+++ b/src/main/java/com/google/security/annotations/SuppressInsecureCipherModeCheckerPendingReview.java
@@ -0,0 +1,59 @@
+/* Copyright 2018 Google LLC
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.google.security.annotations;
+
+import java.lang.annotation.Documented;
+import java.lang.annotation.ElementType;
+import java.lang.annotation.Retention;
+import java.lang.annotation.RetentionPolicy;
+import java.lang.annotation.Target;
+
+import javax.crypto.Cipher;
+
+/**
+ * This annotation is used to temporarily disable the InsecureCipherMode Error Prone checker while
+ * the violation is being reviewed by ISE. A comment including a tracking bug for the ongoing
+ * security review should accompany the annotation. If the specific use is deemed a valid exception
+ * after review, the annotation should be changed to @SuppressInsecureCipherModeCheckerReviewed.
+ *
+ * <p>A {@link Cipher} object is created using one of the overloads of the
+ * {@link Cipher#getInstance()} method. This method takes a specification of the transformer either
+ * as a triple "Algorithm/Mode/Padding"  or just "Algorithm", using the provider's default settings.
+ * The InsecureCipherMode checker implemented in Error Prone flags all call sites of
+ * {@link Cipher#getInstance()}, where either the insecure ECB mode or the provider's default mode
+ * is used. This method annotation is used to suppress the Error Prone checker in use cases where an
+ * exception has been granted by ISE after proper review. The annotation is BUILD-visibility
+ * restricted and every use must be vetted by the ISE team.
+ *
+ * <p>Example of usage:
+ * <pre>
+ * {@code
+ * @SuppressInsecureCipherModeCheckerPendingReview // Tracking bug for the review: b/...
+ * private String decrypt(String[] input) {
+ * Cipher aesCipher = Cipher.getInstance("AES");
+ * aesCipher.init(Cipher.DECRYPT_MODE, new SecretKeySpec(rawKeyMaterial, "AES"));
+ * // ...
+ * }
+ * }
+ * </pre>
+ *
+ * @author avenet@google.com (Arnaud J. Venet)
+ *
+ */
+@Documented
+@Target({ElementType.FIELD, ElementType.METHOD, ElementType.PARAMETER, ElementType.CONSTRUCTOR,
+    ElementType.LOCAL_VARIABLE})
+@Retention(RetentionPolicy.SOURCE)
+public @interface SuppressInsecureCipherModeCheckerPendingReview {}
diff --git a/src/main/java/com/google/security/annotations/SuppressInsecureCipherModeCheckerReviewed.java b/src/main/java/com/google/security/annotations/SuppressInsecureCipherModeCheckerReviewed.java
new file mode 100644
index 0000000..d1780c5
--- /dev/null
+++ b/src/main/java/com/google/security/annotations/SuppressInsecureCipherModeCheckerReviewed.java
@@ -0,0 +1,58 @@
+/* Copyright 2018 Google LLC
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.google.security.annotations;
+
+import java.lang.annotation.Documented;
+import java.lang.annotation.ElementType;
+import java.lang.annotation.Retention;
+import java.lang.annotation.RetentionPolicy;
+import java.lang.annotation.Target;
+
+import javax.crypto.Cipher;
+
+/**
+ * This annotation is used to disable the InsecureCipherMode Error Prone checker after a proper
+ * review by ISE. A comment including a tracking bug for the security review should accompany the
+ * annotation.
+ *
+ * <p>A {@link Cipher} object is created using one of the overloads of the
+ * {@link Cipher#getInstance()} method. This method takes a specification of the transformer either
+ * as a triple "Algorithm/Mode/Padding"  or just "Algorithm", using the provider's default settings.
+ * The InsecureCipherMode checker implemented in Error Prone flags all call sites of
+ * {@link Cipher#getInstance()}, where either the insecure ECB mode or the provider's default mode
+ * is used. This method annotation is used to suppress the Error Prone checker in use cases where an
+ * exception has been granted by ISE after proper review. The annotation is BUILD-visibility
+ * restricted and every use must be vetted by the ISE team.
+ *
+ * <p>Example of usage:
+ * <pre>
+ * {@code
+ * @SuppressInsecureCipherModeCheckerReviewed // Tracking bug for the review: b/...
+ * private String decrypt(String[] input) {
+ * Cipher aesCipher = Cipher.getInstance("AES");
+ * aesCipher.init(Cipher.DECRYPT_MODE, new SecretKeySpec(rawKeyMaterial, "AES"));
+ * // ...
+ * }
+ * }
+ * </pre>
+ *
+ * @author avenet@google.com (Arnaud J. Venet)
+ *
+ */
+@Documented
+@Target({ElementType.FIELD, ElementType.METHOD, ElementType.PARAMETER, ElementType.CONSTRUCTOR,
+    ElementType.LOCAL_VARIABLE})
+@Retention(RetentionPolicy.SOURCE)
+public @interface SuppressInsecureCipherModeCheckerReviewed {}
diff --git a/src/main/java/com/google/security/cryptauth/lib/securegcm/D2DConnectionContext.java b/src/main/java/com/google/security/cryptauth/lib/securegcm/D2DConnectionContext.java
new file mode 100644
index 0000000..09023a5
--- /dev/null
+++ b/src/main/java/com/google/security/cryptauth/lib/securegcm/D2DConnectionContext.java
@@ -0,0 +1,274 @@
+/* Copyright 2018 Google LLC
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.google.security.cryptauth.lib.securegcm;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.protobuf.ByteString;
+import com.google.protobuf.InvalidProtocolBufferException;
+import com.google.security.cryptauth.lib.securegcm.DeviceToDeviceMessagesProto.DeviceToDeviceMessage;
+import com.google.security.cryptauth.lib.securegcm.TransportCryptoOps.Payload;
+import com.google.security.cryptauth.lib.securegcm.TransportCryptoOps.PayloadType;
+import java.io.UnsupportedEncodingException;
+import java.security.InvalidKeyException;
+import java.security.NoSuchAlgorithmException;
+import java.security.SignatureException;
+import java.util.Arrays;
+import javax.crypto.SecretKey;
+import javax.crypto.spec.SecretKeySpec;
+
+/**
+ * The full context of a secure connection. This object has methods to encode and decode messages
+ * that are to be sent to another device.
+ *
+ * Subclasses keep track of the keys shared with the other device, and of the sequence in which the
+ * messages are expected.
+ */
+public abstract class D2DConnectionContext {
+  private static final String UTF8 = "UTF-8";
+  private final int protocolVersion;
+
+  protected D2DConnectionContext(int protocolVersion) {
+    this.protocolVersion = protocolVersion;
+  }
+
+  /**
+   * @return the version of the D2D protocol.
+   */
+  public int getProtocolVersion() {
+    return protocolVersion;
+  }
+
+  /**
+   * Once initiator and responder have exchanged public keys, use this method to encrypt and
+   * sign a payload. Both initiator and responder devices can use this message.
+   *
+   * @param payload the payload that should be encrypted.
+   */
+  public byte[] encodeMessageToPeer(byte[] payload) {
+    incrementSequenceNumberForEncoding();
+    DeviceToDeviceMessage message = createDeviceToDeviceMessage(
+        payload, getSequenceNumberForEncoding());
+    try {
+      return D2DCryptoOps.signcryptPayload(
+          new Payload(PayloadType.DEVICE_TO_DEVICE_MESSAGE,
+              message.toByteArray()),
+          getEncodeKey());
+    } catch (InvalidKeyException e) {
+      // should never happen, since we agreed on the key earlier
+      throw new RuntimeException(e);
+    } catch (NoSuchAlgorithmException e) {
+      // should never happen
+      throw new RuntimeException(e);
+    }
+  }
+
+  /**
+   * Encrypting/signing a string for transmission to another device.
+   *
+   * @see #encodeMessageToPeer(byte[])
+   *
+   * @param payload the payload that should be encrypted.
+   */
+  public byte[] encodeMessageToPeer(String payload) {
+    try {
+      return encodeMessageToPeer(payload.getBytes(UTF8));
+    } catch (UnsupportedEncodingException e) {
+      // Should never happen - we should always be able to UTF-8-encode a string
+      throw new RuntimeException(e);
+    }
+  }
+
+  /**
+   * Once InitiatorHello and ResponderHello(AndPayload) are exchanged, use this method
+   * to decrypt and verify a message received from the other device. Both initiator and
+   * responder device can use this message.
+   *
+   * @param message the message that should be encrypted.
+   * @throws SignatureException if the message from the remote peer did not pass verification
+   */
+  public byte[] decodeMessageFromPeer(byte[] message) throws SignatureException {
+    try {
+      Payload payload = D2DCryptoOps.verifydecryptPayload(message, getDecodeKey());
+      if (!PayloadType.DEVICE_TO_DEVICE_MESSAGE.equals(payload.getPayloadType())) {
+        throw new SignatureException("wrong message type in device-to-device message");
+      }
+
+      DeviceToDeviceMessage messageProto = DeviceToDeviceMessage.parseFrom(payload.getMessage());
+      incrementSequenceNumberForDecoding();
+      if (messageProto.getSequenceNumber() != getSequenceNumberForDecoding()) {
+        throw new SignatureException("Incorrect sequence number");
+      }
+
+      return messageProto.getMessage().toByteArray();
+    } catch (InvalidKeyException e) {
+      throw new SignatureException(e);
+    } catch (NoSuchAlgorithmException e) {
+      // this shouldn't happen - the algorithms are hard-coded.
+      throw new RuntimeException(e);
+    } catch (InvalidProtocolBufferException e) {
+      throw new SignatureException(e);
+    }
+  }
+
+  /**
+   * Once InitiatorHello and ResponderHello(AndPayload) are exchanged, use this method
+   * to decrypt and verify a message received from the other device. Both initiator and
+   * responder device can use this message.
+   *
+   * @param message the message that should be encrypted.
+   */
+  public String decodeMessageFromPeerAsString(byte[] message) throws SignatureException {
+    try {
+      return new String(decodeMessageFromPeer(message), UTF8);
+    } catch (UnsupportedEncodingException e) {
+      // Should never happen - we should always be able to UTF-8-encode a string
+      throw new RuntimeException(e);
+    }
+  }
+
+  // package-private
+  static DeviceToDeviceMessage createDeviceToDeviceMessage(byte[] message, int sequenceNumber) {
+    DeviceToDeviceMessage.Builder deviceToDeviceMessage = DeviceToDeviceMessage.newBuilder();
+    deviceToDeviceMessage.setSequenceNumber(sequenceNumber);
+    deviceToDeviceMessage.setMessage(ByteString.copyFrom(message));
+    return deviceToDeviceMessage.build();
+  }
+
+  /**
+   * Returns a cryptographic digest (SHA256) of the session keys prepended by the SHA256 hash
+   * of the ASCII string "D2D"
+   * @throws NoSuchAlgorithmException if SHA 256 doesn't exist on this platform
+   */
+  public abstract byte[] getSessionUnique() throws NoSuchAlgorithmException;
+
+  /**
+   * Increments the sequence number used for encoding messages.
+   */
+  protected abstract void incrementSequenceNumberForEncoding();
+
+  /**
+   * Increments the sequence number used for decoding messages.
+   */
+  protected abstract void incrementSequenceNumberForDecoding();
+
+  /**
+   * @return the last sequence number used to encode a message.
+   */
+  @VisibleForTesting
+  abstract int getSequenceNumberForEncoding();
+
+  /**
+   * @return the last sequence number used to decode a message.
+   */
+  @VisibleForTesting
+  abstract int getSequenceNumberForDecoding();
+
+  /**
+   * @return the {@link SecretKey} used for encoding messages.
+   */
+  @VisibleForTesting
+  abstract SecretKey getEncodeKey();
+
+  /**
+   * @return the {@link SecretKey} used for decoding messages.
+   */
+  @VisibleForTesting
+  abstract SecretKey getDecodeKey();
+
+  /**
+   * Creates a saved session that can later be used for resumption.  Note, this must be stored in a
+   * secure location.
+   *
+   * @return the saved session, suitable for resumption.
+   */
+  public abstract byte[] saveSession();
+
+  /**
+   * Parse a saved session info and attempt to construct a resumed context.
+   * The first byte in a saved session info must always be the protocol version.
+   * Note that an {@link IllegalArgumentException} will be thrown if the savedSessionInfo is not
+   * properly formatted.
+   *
+   * @return a resumed context from a saved session.
+   */
+  public static D2DConnectionContext fromSavedSession(byte[] savedSessionInfo) {
+    if (savedSessionInfo == null || savedSessionInfo.length == 0) {
+      throw new IllegalArgumentException("savedSessionInfo null or too short");
+    }
+
+    int protocolVersion = savedSessionInfo[0] & 0xff;
+
+    switch (protocolVersion) {
+      case 0:
+        // Version 0 has a 1 byte protocol version, a 4 byte sequence number,
+        // and 32 bytes of AES key (1 + 4 + 32 = 37)
+        if (savedSessionInfo.length != 37) {
+          throw new IllegalArgumentException("Incorrect data length (" + savedSessionInfo.length
+              + ") for v0 protocol");
+        }
+        int sequenceNumber = bytesToSignedInt(Arrays.copyOfRange(savedSessionInfo, 1, 5));
+        SecretKey sharedKey = new SecretKeySpec(Arrays.copyOfRange(savedSessionInfo, 5, 37), "AES");
+        return new D2DConnectionContextV0(sharedKey, sequenceNumber);
+
+      case 1:
+        // Version 1 has a 1 byte protocol version, two 4 byte sequence numbers,
+        // and two 32 byte AES keys (1 + 4 + 4 + 32 + 32 = 73)
+        if (savedSessionInfo.length != 73) {
+          throw new IllegalArgumentException("Incorrect data length for v1 protocol");
+        }
+        int encodeSequenceNumber = bytesToSignedInt(Arrays.copyOfRange(savedSessionInfo, 1, 5));
+        int decodeSequenceNumber = bytesToSignedInt(Arrays.copyOfRange(savedSessionInfo, 5, 9));
+        SecretKey encodeKey =
+            new SecretKeySpec(Arrays.copyOfRange(savedSessionInfo, 9, 41), "AES");
+        SecretKey decodeKey =
+            new SecretKeySpec(Arrays.copyOfRange(savedSessionInfo, 41, 73), "AES");
+        return new D2DConnectionContextV1(encodeKey, decodeKey, encodeSequenceNumber,
+            decodeSequenceNumber);
+
+      default:
+        throw new IllegalArgumentException("Cannot rebuild context, unkown protocol version: "
+            + protocolVersion);
+    }
+  }
+
+  /**
+   * Convert 4 bytes in big-endian representation into a signed int.
+   */
+  static int bytesToSignedInt(byte[] bytes) {
+    if (bytes.length != 4) {
+      throw new IllegalArgumentException("Expected 4 bytes to encode int, but got: "
+          + bytes.length + " bytes");
+    }
+
+    return ((bytes[0] << 24) & 0xff000000)
+        |  ((bytes[1] << 16) & 0x00ff0000)
+        |  ((bytes[2] << 8)  & 0x0000ff00)
+        |   (bytes[3]        & 0x000000ff);
+  }
+
+  /**
+   * Convert a signed int into a 4 byte big-endian representation
+   */
+  static byte[] signedIntToBytes(int val) {
+    byte[] bytes = new byte[4];
+
+    bytes[0] = (byte) ((val >> 24) & 0xff);
+    bytes[1] = (byte) ((val >> 16) & 0xff);
+    bytes[2] = (byte) ((val >> 8)  & 0xff);
+    bytes[3] = (byte)  (val        & 0xff);
+
+    return bytes;
+  }
+}
diff --git a/src/main/java/com/google/security/cryptauth/lib/securegcm/D2DConnectionContextV0.java b/src/main/java/com/google/security/cryptauth/lib/securegcm/D2DConnectionContextV0.java
new file mode 100644
index 0000000..92aa02d
--- /dev/null
+++ b/src/main/java/com/google/security/cryptauth/lib/securegcm/D2DConnectionContextV0.java
@@ -0,0 +1,118 @@
+/* Copyright 2018 Google LLC
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.google.security.cryptauth.lib.securegcm;
+
+import java.io.ByteArrayOutputStream;
+import java.io.IOException;
+import java.security.MessageDigest;
+import java.security.NoSuchAlgorithmException;
+import javax.crypto.SecretKey;
+
+/**
+ * Implementation of {@link D2DConnectionContext} for version 0 of the D2D protocol. In this
+ * version, communication is half-duplex, as there is a shared key and a shared sequence number
+ * between the two sides.
+ */
+public class D2DConnectionContextV0 extends D2DConnectionContext {
+  public static final int PROTOCOL_VERSION = 0;
+
+  private final SecretKey sharedKey;
+  private int sequenceNumber;
+
+  /**
+   * Package private constructor. Should never be called directly except by the
+   * {@link D2DHandshakeContext}
+   *
+   * @param sharedKey
+   * @param initialSequenceNumber
+   */
+  D2DConnectionContextV0(SecretKey sharedKey, int initialSequenceNumber) {
+    super(PROTOCOL_VERSION);
+    this.sharedKey = sharedKey;
+    this.sequenceNumber = initialSequenceNumber;
+  }
+
+  @Override
+  public byte[] getSessionUnique() throws NoSuchAlgorithmException {
+    if (sharedKey == null) {
+      throw new IllegalStateException(
+          "Connection has not been correctly initialized; shared key is null");
+    }
+
+    MessageDigest md = MessageDigest.getInstance("SHA-256");
+    md.update(D2DCryptoOps.SALT);
+    return md.digest(sharedKey.getEncoded());
+  }
+
+  @Override
+  protected void incrementSequenceNumberForEncoding() {
+    sequenceNumber++;
+  }
+
+  @Override
+  protected void incrementSequenceNumberForDecoding() {
+    sequenceNumber++;
+  }
+
+  @Override
+  int getSequenceNumberForEncoding() {
+    return sequenceNumber;
+  }
+
+  @Override
+  int getSequenceNumberForDecoding() {
+    return sequenceNumber;
+  }
+
+  @Override
+  SecretKey getEncodeKey() {
+    return sharedKey;
+  }
+
+  @Override
+  SecretKey getDecodeKey() {
+    return sharedKey;
+  }
+
+  /**
+   * Structure of saved session is:
+   * +-----------------------------------------------------+
+   * |     1 Byte       | 4 Bytes (big endian) | 32 Bytes  |
+   * +-----------------------------------------------------+
+   * | Protocol Version |    sequence number   |    key    |
+   * +-----------------------------------------------------+
+   */
+  @Override
+  public byte[] saveSession() {
+    ByteArrayOutputStream bytes = new ByteArrayOutputStream();
+
+    try {
+      // Protocol version
+      bytes.write(0);
+
+      // Sequence number
+      bytes.write(signedIntToBytes(sequenceNumber));
+
+      // Key
+      bytes.write(sharedKey.getEncoded());
+    } catch (IOException e) {
+      // should not happen
+      e.printStackTrace();
+      return null;
+    }
+
+    return bytes.toByteArray();
+  }
+}
diff --git a/src/main/java/com/google/security/cryptauth/lib/securegcm/D2DConnectionContextV1.java b/src/main/java/com/google/security/cryptauth/lib/securegcm/D2DConnectionContextV1.java
new file mode 100644
index 0000000..4b5fb5e
--- /dev/null
+++ b/src/main/java/com/google/security/cryptauth/lib/securegcm/D2DConnectionContextV1.java
@@ -0,0 +1,146 @@
+/* Copyright 2018 Google LLC
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.google.security.cryptauth.lib.securegcm;
+
+import java.io.ByteArrayOutputStream;
+import java.io.IOException;
+import java.security.MessageDigest;
+import java.security.NoSuchAlgorithmException;
+import java.util.Arrays;
+import javax.crypto.SecretKey;
+
+/**
+ * Implementation of {@link D2DConnectionContext} for version 1 of the D2D protocol. In this
+ * version, communication is fully duplex, as separate keys and sequence nubmers are used for
+ * encoding and decoding.
+ */
+public class D2DConnectionContextV1 extends D2DConnectionContext {
+  public static final int PROTOCOL_VERSION = 1;
+
+  private final SecretKey encodeKey;
+  private final SecretKey decodeKey;
+  private int encodeSequenceNumber;
+  private int decodeSequenceNumber;
+
+  /**
+   * Package private constructor. Should never be called directly except by the
+   * {@link D2DHandshakeContext}
+   *
+   * @param encodeKey
+   * @param decodeKey
+   * @param initialEncodeSequenceNumber
+   * @param initialDecodeSequenceNumber
+   */
+  D2DConnectionContextV1(
+      SecretKey encodeKey,
+      SecretKey decodeKey,
+      int initialEncodeSequenceNumber,
+      int initialDecodeSequenceNumber) {
+    super(PROTOCOL_VERSION);
+    this.encodeKey = encodeKey;
+    this.decodeKey = decodeKey;
+    this.encodeSequenceNumber = initialEncodeSequenceNumber;
+    this.decodeSequenceNumber = initialDecodeSequenceNumber;
+  }
+
+  @Override
+  public byte[] getSessionUnique() throws NoSuchAlgorithmException {
+    if (encodeKey == null || decodeKey == null) {
+      throw new IllegalStateException(
+          "Connection has not been correctly initialized; encode key or decode key is null");
+    }
+
+    // Ensure that the initator and responder keys are hashed in a deterministic order, so they have
+    // the same session unique code.
+    byte[] encodeKeyBytes = encodeKey.getEncoded();
+    byte[] decodeKeyBytes = decodeKey.getEncoded();
+    int encodeKeyHash = Arrays.hashCode(encodeKeyBytes);
+    int decodeKeyHash = Arrays.hashCode(decodeKeyBytes);
+    byte[] firstKeyBytes = encodeKeyHash < decodeKeyHash ? encodeKeyBytes : decodeKeyBytes;
+    byte[] secondKeyBytes = firstKeyBytes == encodeKeyBytes ? decodeKeyBytes : encodeKeyBytes;
+
+    MessageDigest md = MessageDigest.getInstance("SHA-256");
+    md.update(D2DCryptoOps.SALT);
+    md.update(firstKeyBytes);
+    md.update(secondKeyBytes);
+    return md.digest();
+  }
+
+  @Override
+  protected void incrementSequenceNumberForEncoding() {
+    encodeSequenceNumber++;
+  }
+
+  @Override
+  protected void incrementSequenceNumberForDecoding() {
+    decodeSequenceNumber++;
+  }
+
+  @Override
+  int getSequenceNumberForEncoding() {
+    return encodeSequenceNumber;
+  }
+
+  @Override
+  int getSequenceNumberForDecoding() {
+    return decodeSequenceNumber;
+  }
+
+  @Override
+  SecretKey getEncodeKey() {
+    return encodeKey;
+  }
+
+  @Override
+  SecretKey getDecodeKey() {
+    return decodeKey;
+  }
+
+  /**
+   * Structure of saved session is:
+   * +------------------------------------------------------------------------------------------+
+   * |     1 Byte       | 4 Bytes (big endian) | 4 Bytes (big endian) |  32 Bytes  |  32 Bytes  |
+   * +------------------------------------------------------------------------------------------+
+   * | Protocol Version |   encode seq number  |   decode seq number  | encode key | decode key |
+   * +------------------------------------------------------------------------------------------+
+   */
+  @Override
+  public byte[] saveSession() {
+    ByteArrayOutputStream bytes = new ByteArrayOutputStream();
+
+    try {
+      // Protocol version
+      bytes.write(1);
+
+      // Encode sequence number
+      bytes.write(signedIntToBytes(encodeSequenceNumber));
+
+      // Decode sequence number
+      bytes.write(signedIntToBytes(decodeSequenceNumber));
+
+      // Encode Key
+      bytes.write(encodeKey.getEncoded());
+
+      // Decode Key
+      bytes.write(decodeKey.getEncoded());
+    } catch (IOException e) {
+      // should not happen
+      e.printStackTrace();
+      return null;
+    }
+
+    return bytes.toByteArray();
+  }
+}
diff --git a/src/main/java/com/google/security/cryptauth/lib/securegcm/D2DCryptoOps.java b/src/main/java/com/google/security/cryptauth/lib/securegcm/D2DCryptoOps.java
new file mode 100644
index 0000000..48dc52f
--- /dev/null
+++ b/src/main/java/com/google/security/cryptauth/lib/securegcm/D2DCryptoOps.java
@@ -0,0 +1,234 @@
+/* Copyright 2018 Google LLC
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.google.security.cryptauth.lib.securegcm;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.protobuf.InvalidProtocolBufferException;
+import com.google.security.cryptauth.lib.securegcm.DeviceToDeviceMessagesProto.DeviceToDeviceMessage;
+import com.google.security.cryptauth.lib.securegcm.DeviceToDeviceMessagesProto.ResponderHello;
+import com.google.security.cryptauth.lib.securegcm.SecureGcmProto.GcmMetadata;
+import com.google.security.cryptauth.lib.securegcm.TransportCryptoOps.Payload;
+import com.google.security.cryptauth.lib.securegcm.TransportCryptoOps.PayloadType;
+import com.google.security.cryptauth.lib.securemessage.CryptoOps;
+import com.google.security.cryptauth.lib.securemessage.CryptoOps.EncType;
+import com.google.security.cryptauth.lib.securemessage.CryptoOps.SigType;
+import com.google.security.cryptauth.lib.securemessage.PublicKeyProtoUtil;
+import com.google.security.cryptauth.lib.securemessage.SecureMessageBuilder;
+import com.google.security.cryptauth.lib.securemessage.SecureMessageParser;
+import com.google.security.cryptauth.lib.securemessage.SecureMessageProto.GenericPublicKey;
+import com.google.security.cryptauth.lib.securemessage.SecureMessageProto.Header;
+import com.google.security.cryptauth.lib.securemessage.SecureMessageProto.HeaderAndBody;
+import com.google.security.cryptauth.lib.securemessage.SecureMessageProto.SecureMessage;
+import java.security.InvalidKeyException;
+import java.security.NoSuchAlgorithmException;
+import java.security.PrivateKey;
+import java.security.PublicKey;
+import java.security.SignatureException;
+import java.security.spec.InvalidKeySpecException;
+import javax.annotation.Nullable;
+import javax.crypto.SecretKey;
+
+/**
+ * A collection of static utility methods used by {@link D2DHandshakeContext} for the Device to
+ * Device communication (D2D) library.
+ */
+class D2DCryptoOps {
+  // SHA256 of "D2D"
+  // package-private
+  static final byte[] SALT = new byte[] {
+    (byte) 0x82, (byte) 0xAA, (byte) 0x55, (byte) 0xA0, (byte) 0xD3, (byte) 0x97, (byte) 0xF8,
+    (byte) 0x83, (byte) 0x46, (byte) 0xCA, (byte) 0x1C, (byte) 0xEE, (byte) 0x8D, (byte) 0x39,
+    (byte) 0x09, (byte) 0xB9, (byte) 0x5F, (byte) 0x13, (byte) 0xFA, (byte) 0x7D, (byte) 0xEB,
+    (byte) 0x1D, (byte) 0x4A, (byte) 0xB3, (byte) 0x83, (byte) 0x76, (byte) 0xB8, (byte) 0x25,
+    (byte) 0x6D, (byte) 0xA8, (byte) 0x55, (byte) 0x10
+  };
+
+  // Don't instantiate
+  private D2DCryptoOps() { }
+
+  /**
+   * Used by the responder device to create a signcrypted message that contains
+   * a payload and a {@link ResponderHello}.
+   *
+   * @param sharedKey used to signcrypt the {@link Payload}
+   * @param publicDhKey the key the recipient will need to derive the shared DH secret.
+   *   This key will be added to the {@link ResponderHello} in the header.
+   * @param protocolVersion the protocol version to include in the proto
+   */
+  static byte[] signcryptMessageAndResponderHello(
+      Payload payload, SecretKey sharedKey, PublicKey publicDhKey, int protocolVersion)
+      throws InvalidKeyException, NoSuchAlgorithmException {
+    ResponderHello.Builder responderHello = ResponderHello.newBuilder();
+    responderHello.setPublicDhKey(PublicKeyProtoUtil.encodePublicKey(publicDhKey));
+    responderHello.setProtocolVersion(protocolVersion);
+    return signcryptPayload(payload, sharedKey, responderHello.build().toByteArray());
+  }
+
+  /**
+   * Used by a device to send a secure {@link Payload} to another device.
+   */
+  static byte[] signcryptPayload(
+      Payload payload, SecretKey masterKey)
+      throws InvalidKeyException, NoSuchAlgorithmException {
+    return signcryptPayload(payload, masterKey, null);
+  }
+
+  /**
+   * Used by a device to send a secure {@link Payload} to another device.
+   *
+   * @param responderHello is an optional public value to attach in the header of
+   *     the {@link SecureMessage} (in the DecryptionKeyId).
+   */
+  @VisibleForTesting
+  static byte[] signcryptPayload(
+      Payload payload, SecretKey masterKey, @Nullable byte[] responderHello)
+      throws InvalidKeyException, NoSuchAlgorithmException {
+    if ((payload == null) || (masterKey == null)) {
+      throw new NullPointerException();
+    }
+
+    SecureMessageBuilder secureMessageBuilder = new SecureMessageBuilder()
+        .setPublicMetadata(GcmMetadata.newBuilder()
+            .setType(payload.getPayloadType().getType())
+            .setVersion(SecureGcmConstants.SECURE_GCM_VERSION)
+            .build()
+            .toByteArray());
+
+    if (responderHello != null) {
+      secureMessageBuilder.setDecryptionKeyId(responderHello);
+    }
+
+    return secureMessageBuilder.buildSignCryptedMessage(
+            masterKey,
+            SigType.HMAC_SHA256,
+            masterKey,
+            EncType.AES_256_CBC,
+            payload.getMessage())
+        .toByteArray();
+  }
+
+  /**
+   * Extracts a ResponderHello proto from the header of a signcrypted message so that we
+   * can derive the shared secret that was used to sign/encrypt the message.
+   *
+   * @return the {@link ResponderHello} embedded in the signcrypted message.
+   */
+  static ResponderHello parseAndValidateResponderHello(
+      byte[] signcryptedMessageFromResponder) throws InvalidProtocolBufferException {
+    if (signcryptedMessageFromResponder == null) {
+      throw new NullPointerException();
+    }
+    SecureMessage secmsg = SecureMessage.parseFrom(signcryptedMessageFromResponder);
+    Header messageHeader = SecureMessageParser.getUnverifiedHeader(secmsg);
+    if (!messageHeader.hasDecryptionKeyId()) {
+      // Maybe this should be a different exception type, because in general, it's legal for the
+      // SecureMessage proto to not have the decryption key id, but it's illegal in this protocol.
+      throw new InvalidProtocolBufferException("Missing decryption key id");
+    }
+    byte[] encodedResponderHello = messageHeader.getDecryptionKeyId().toByteArray();
+    ResponderHello responderHello = ResponderHello.parseFrom(encodedResponderHello);
+    if (!responderHello.hasPublicDhKey()) {
+      throw new InvalidProtocolBufferException("Missing public key in responder hello");
+    }
+    return responderHello;
+  }
+
+  /**
+   * Used by a device to recover a secure {@link Payload} sent by another device.
+   */
+  static Payload verifydecryptPayload(
+      byte[] signcryptedMessage, SecretKey masterKey)
+      throws SignatureException, InvalidKeyException, NoSuchAlgorithmException {
+    if ((signcryptedMessage == null) || (masterKey == null)) {
+      throw new NullPointerException();
+    }
+    try {
+      SecureMessage secmsg = SecureMessage.parseFrom(signcryptedMessage);
+      HeaderAndBody parsed = SecureMessageParser.parseSignCryptedMessage(
+          secmsg,
+          masterKey,
+          SigType.HMAC_SHA256,
+          masterKey,
+          EncType.AES_256_CBC);
+      if (!parsed.getHeader().hasPublicMetadata()) {
+        throw new SignatureException("missing metadata");
+      }
+      GcmMetadata metadata = GcmMetadata.parseFrom(parsed.getHeader().getPublicMetadata());
+      if (metadata.getVersion() > SecureGcmConstants.SECURE_GCM_VERSION) {
+        throw new SignatureException("Unsupported protocol version");
+      }
+      return new Payload(PayloadType.valueOf(metadata.getType()), parsed.getBody().toByteArray());
+    } catch (InvalidProtocolBufferException e) {
+      throw new SignatureException(e);
+    } catch (IllegalArgumentException e) {
+      throw new SignatureException(e);
+    }
+  }
+
+  /**
+   * Used by the initiator device to derive the shared key from the {@link PrivateKey} in the
+   * {@link D2DHandshakeContext} and the responder's {@link GenericPublicKey} (contained in the
+   * {@link ResponderHello} proto).
+   */
+  static SecretKey deriveSharedKeyFromGenericPublicKey(
+      PrivateKey ourPrivateKey, GenericPublicKey theirGenericPublicKey) throws SignatureException {
+    try {
+      PublicKey theirPublicKey = PublicKeyProtoUtil.parsePublicKey(theirGenericPublicKey);
+      return EnrollmentCryptoOps.doKeyAgreement(ourPrivateKey, theirPublicKey);
+    } catch (InvalidKeySpecException e) {
+      throw new SignatureException(e);
+    } catch (InvalidKeyException e) {
+      throw new SignatureException(e);
+    }
+  }
+
+  /**
+   * Used to derive a distinct key for each initiator and responder.
+   * 
+   * @param masterKey the source key used to derive the new key.
+   * @param purpose a string to make the new key different for each purpose.
+   * @return the derived {@link SecretKey}.
+   */
+  static SecretKey deriveNewKeyForPurpose(SecretKey masterKey, String purpose)
+      throws NoSuchAlgorithmException, InvalidKeyException {
+    byte[] info = purpose.getBytes();
+    return KeyEncoding.parseMasterKey(CryptoOps.hkdf(masterKey, SALT, info));
+  }
+
+  /**
+   * Used by the initiator device to decrypt the first payload portion that was sent in the
+   * {@code responderHelloAndPayload}, and extract the {@link DeviceToDeviceMessage} contained
+   * within it. In order to decrypt, the {@code sharedKey} must first be derived.
+   *
+   * @see #deriveSharedKeyFromGenericPublicKey(PrivateKey, GenericPublicKey)
+   */
+  static DeviceToDeviceMessage decryptResponderHelloMessage(
+      SecretKey sharedKey, byte[] responderHelloAndPayload) throws SignatureException {
+    try {
+      Payload payload = verifydecryptPayload(responderHelloAndPayload, sharedKey);
+      if (!PayloadType.DEVICE_TO_DEVICE_RESPONDER_HELLO_PAYLOAD.equals(
+          payload.getPayloadType())) {
+        throw new SignatureException("wrong message type in responder hello");
+      }
+      return DeviceToDeviceMessage.parseFrom(payload.getMessage());
+    } catch (InvalidProtocolBufferException e) {
+      throw new SignatureException(e);
+    } catch (InvalidKeyException e) {
+      throw new SignatureException(e);
+    } catch (NoSuchAlgorithmException e) {
+      throw new SignatureException(e);
+    }
+  }
+}
diff --git a/src/main/java/com/google/security/cryptauth/lib/securegcm/D2DDiffieHellmanKeyExchangeHandshake.java b/src/main/java/com/google/security/cryptauth/lib/securegcm/D2DDiffieHellmanKeyExchangeHandshake.java
new file mode 100644
index 0000000..ae43d90
--- /dev/null
+++ b/src/main/java/com/google/security/cryptauth/lib/securegcm/D2DDiffieHellmanKeyExchangeHandshake.java
@@ -0,0 +1,308 @@
+/* Copyright 2018 Google LLC
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.google.security.cryptauth.lib.securegcm;
+
+import com.google.protobuf.InvalidProtocolBufferException;
+import com.google.security.cryptauth.lib.securegcm.DeviceToDeviceMessagesProto.DeviceToDeviceMessage;
+import com.google.security.cryptauth.lib.securegcm.DeviceToDeviceMessagesProto.InitiatorHello;
+import com.google.security.cryptauth.lib.securegcm.DeviceToDeviceMessagesProto.ResponderHello;
+import com.google.security.cryptauth.lib.securegcm.TransportCryptoOps.Payload;
+import com.google.security.cryptauth.lib.securegcm.TransportCryptoOps.PayloadType;
+import com.google.security.cryptauth.lib.securemessage.PublicKeyProtoUtil;
+import java.security.InvalidKeyException;
+import java.security.KeyPair;
+import java.security.NoSuchAlgorithmException;
+import java.security.PublicKey;
+import java.security.SignatureException;
+import java.security.spec.InvalidKeySpecException;
+import javax.crypto.SecretKey;
+
+/**
+ * Implements an unauthenticated EC Diffie Hellman Key Exchange Handshake
+ * <p>
+ * Initiator sends an InitiatorHello, which is a protobuf that contains a public key. Responder
+ * sends a responder hello, which a signed and encrypted message containing a payload, and a public
+ * key in the unencrypted header (payload is encrypted with the derived DH key).
+ * <p>
+ * Example Usage:
+ * <pre>
+ *    // initiator:
+ *    D2DHandshakeContext initiatorHandshakeContext =
+ *        D2DDiffieHellmanKeyExchangeHandshake.forInitiator();
+ *    byte[] initiatorHello = initiatorHandshakeContext.getNextHandshakeMessage();
+ *    // (send initiatorHello to responder)
+ *
+ *    // responder:
+ *    D2DHandshakeContext responderHandshakeContext =
+ *        D2DDiffieHellmanKeyExchangeHandshake.forResponder();
+ *    responderHandshakeContext.parseHandshakeMessage(initiatorHello);
+ *    byte[] responderHelloAndPayload = responderHandshakeContext.getNextHandshakeMessage(
+ *        toBytes(RESPONDER_HELLO_MESSAGE));
+ *    D2DConnectionContext responderCtx = responderHandshakeContext.toConnectionContext();
+ *    // (send responderHelloAndPayload to initiator)
+ *
+ *    // initiator
+ *    byte[] messageFromPayload =
+ *        initiatorHandshakeContext.parseHandshakeMessage(responderHelloAndPayload);
+ *    if (messageFromPayload.length > 0) {
+ *      handle(messageFromPayload);
+ *    }
+ *
+ *    D2DConnectionContext initiatorCtx = initiatorHandshakeContext.toConnectionContext();
+ * </pre>
+ */
+public class D2DDiffieHellmanKeyExchangeHandshake implements D2DHandshakeContext {
+  // Data passed to hkdf to create the key used by the initiator to encode messages.
+  private static final String INITIATOR_PURPOSE = "initiator";
+  // Data passed to hkdf to create the key used by the responder to encode messages.
+  private static final String RESPONDER_PURPOSE = "responder";
+
+  private KeyPair ourKeyPair;
+  private PublicKey theirPublicKey;
+  private SecretKey initiatorEncodeKey;
+  private SecretKey responderEncodeKey;
+  private State handshakeState;
+  private boolean isInitiator;
+  private int protocolVersionToUse;
+
+  private enum State {
+    // Initiator state
+    INITIATOR_START,
+    INITIATOR_WAITING_FOR_RESPONDER_HELLO,
+
+    // Responder state
+    RESPONDER_START,
+    RESPONDER_AFTER_INITIATOR_HELLO,
+
+    // Common completion state
+    HANDSHAKE_FINISHED,
+    HANDSHAKE_ALREADY_USED
+  }
+
+  private D2DDiffieHellmanKeyExchangeHandshake(State state) {
+    ourKeyPair = PublicKeyProtoUtil.generateEcP256KeyPair();
+    theirPublicKey = null;
+    initiatorEncodeKey = null;
+    responderEncodeKey = null;
+    handshakeState = state;
+    isInitiator = state == State.INITIATOR_START;
+    protocolVersionToUse = D2DConnectionContextV1.PROTOCOL_VERSION;
+  }
+
+  /**
+   * Creates a new Diffie Hellman handshake context for the handshake initiator
+   */
+  public static D2DDiffieHellmanKeyExchangeHandshake forInitiator() {
+    return new D2DDiffieHellmanKeyExchangeHandshake(State.INITIATOR_START);
+  }
+
+  /**
+   * Creates a new Diffie Hellman handshake context for the handshake responder
+   */
+  public static D2DDiffieHellmanKeyExchangeHandshake forResponder() {
+    return new D2DDiffieHellmanKeyExchangeHandshake(State.RESPONDER_START);
+  }
+
+  @Override
+  public boolean isHandshakeComplete() {
+    return handshakeState == State.HANDSHAKE_FINISHED
+        || handshakeState == State.HANDSHAKE_ALREADY_USED;
+  }
+
+  @Override
+  public byte[] getNextHandshakeMessage() throws HandshakeException {
+    switch(handshakeState) {
+      case INITIATOR_START:
+        handshakeState = State.INITIATOR_WAITING_FOR_RESPONDER_HELLO;
+        return InitiatorHello.newBuilder()
+            .setPublicDhKey(PublicKeyProtoUtil.encodePublicKey(ourKeyPair.getPublic()))
+            .setProtocolVersion(protocolVersionToUse)
+            .build()
+            .toByteArray();
+
+      case RESPONDER_AFTER_INITIATOR_HELLO:
+        byte[] responderHello = makeResponderHelloWithPayload(new byte[0]);
+        handshakeState = State.HANDSHAKE_FINISHED;
+        return responderHello;
+
+      default:
+        throw new HandshakeException("Cannot get next message in state: " + handshakeState);
+    }
+  }
+
+  @Override
+  public boolean canSendPayloadInHandshakeMessage() {
+    return handshakeState == State.RESPONDER_AFTER_INITIATOR_HELLO;
+  }
+
+  @Override
+  public byte[] getNextHandshakeMessage(byte[] payload) throws HandshakeException {
+    if (handshakeState != State.RESPONDER_AFTER_INITIATOR_HELLO) {
+      throw new HandshakeException(
+          "Cannot get next message with payload in state: " + handshakeState);
+    }
+
+    byte[] responderHello = makeResponderHelloWithPayload(payload);
+    handshakeState = State.HANDSHAKE_FINISHED;
+
+    return responderHello;
+  }
+
+  private byte[] makeResponderHelloWithPayload(byte[] payload) throws HandshakeException {
+    if (payload == null) {
+      throw new HandshakeException("Not expecting null payload");
+    }
+
+    try {
+      SecretKey masterKey =
+          EnrollmentCryptoOps.doKeyAgreement(ourKeyPair.getPrivate(), theirPublicKey);
+
+      // V0 uses the same key for encoding and decoding, but V1 uses separate keys.
+      switch (protocolVersionToUse) {
+        case D2DConnectionContextV0.PROTOCOL_VERSION:
+          initiatorEncodeKey = masterKey;
+          responderEncodeKey = masterKey;
+          break;
+        case D2DConnectionContextV1.PROTOCOL_VERSION:
+          initiatorEncodeKey = D2DCryptoOps.deriveNewKeyForPurpose(masterKey, INITIATOR_PURPOSE);
+          responderEncodeKey = D2DCryptoOps.deriveNewKeyForPurpose(masterKey, RESPONDER_PURPOSE);
+          break;
+        default:
+          throw new IllegalStateException("Unexpected protocol version: " + protocolVersionToUse);
+      }
+
+      DeviceToDeviceMessage deviceToDeviceMessage =
+          D2DConnectionContext.createDeviceToDeviceMessage(payload, 1 /* sequence number */);
+
+      return D2DCryptoOps.signcryptMessageAndResponderHello(
+          new Payload(PayloadType.DEVICE_TO_DEVICE_RESPONDER_HELLO_PAYLOAD,
+              deviceToDeviceMessage.toByteArray()),
+          responderEncodeKey,
+          ourKeyPair.getPublic(),
+          protocolVersionToUse);
+    } catch (InvalidKeyException|NoSuchAlgorithmException e) {
+      throw new HandshakeException(e);
+    }
+  }
+
+  @Override
+  public byte[] parseHandshakeMessage(byte[] handshakeMessage) throws HandshakeException {
+    if (handshakeMessage == null || handshakeMessage.length == 0) {
+      throw new HandshakeException("Handshake message too short");
+    }
+
+    switch(handshakeState) {
+      case INITIATOR_WAITING_FOR_RESPONDER_HELLO:
+          byte[] payload = parseResponderHello(handshakeMessage);
+          handshakeState = State.HANDSHAKE_FINISHED;
+          return payload;
+
+      case RESPONDER_START:
+          parseInitiatorHello(handshakeMessage);
+          handshakeState = State.RESPONDER_AFTER_INITIATOR_HELLO;
+          return new byte[0];
+
+      default:
+        throw new HandshakeException("Cannot parse message in state: " + handshakeState);
+    }
+  }
+
+  private byte[] parseResponderHello(byte[] responderHello) throws HandshakeException {
+     try {
+        ResponderHello responderHelloProto =
+            D2DCryptoOps.parseAndValidateResponderHello(responderHello);
+
+        // Downgrade to protocol version 0 if needed for backwards compatibility.
+        int protocolVersion = responderHelloProto.getProtocolVersion();
+        if (protocolVersion == D2DConnectionContextV0.PROTOCOL_VERSION) {
+          protocolVersionToUse = D2DConnectionContextV0.PROTOCOL_VERSION;
+        }
+
+        SecretKey masterKey = D2DCryptoOps.deriveSharedKeyFromGenericPublicKey(
+            ourKeyPair.getPrivate(), responderHelloProto.getPublicDhKey());
+
+        // V0 uses the same key for encoding and decoding, but V1 uses separate keys.
+        if (protocolVersionToUse == D2DConnectionContextV0.PROTOCOL_VERSION) {
+          initiatorEncodeKey = masterKey;
+          responderEncodeKey = masterKey;
+        } else {
+          initiatorEncodeKey = D2DCryptoOps.deriveNewKeyForPurpose(masterKey, INITIATOR_PURPOSE);
+          responderEncodeKey = D2DCryptoOps.deriveNewKeyForPurpose(masterKey, RESPONDER_PURPOSE);
+        }
+
+        DeviceToDeviceMessage message =
+            D2DCryptoOps.decryptResponderHelloMessage(responderEncodeKey, responderHello);
+
+        if (message.getSequenceNumber() != 1) {
+          throw new HandshakeException("Incorrect sequence number in responder hello");
+        }
+
+        return message.getMessage().toByteArray();
+      } catch (SignatureException | InvalidProtocolBufferException
+               | NoSuchAlgorithmException | InvalidKeyException e) {
+        throw new HandshakeException(e);
+      }
+  }
+
+  private void parseInitiatorHello(byte[] initiatorHello) throws HandshakeException {
+    try {
+        InitiatorHello initiatorHelloProto = InitiatorHello.parseFrom(initiatorHello);
+
+        if (!initiatorHelloProto.hasPublicDhKey()) {
+          throw new HandshakeException("Missing public key in initiator hello");
+        }
+
+        theirPublicKey = PublicKeyProtoUtil.parsePublicKey(initiatorHelloProto.getPublicDhKey());
+
+        // Downgrade to protocol version 0 if needed for backwards compatibility.
+        int protocolVersion = initiatorHelloProto.getProtocolVersion();
+        if (protocolVersion == D2DConnectionContextV0.PROTOCOL_VERSION) {
+          protocolVersionToUse = D2DConnectionContextV0.PROTOCOL_VERSION;
+        }
+      } catch (InvalidKeySpecException | InvalidProtocolBufferException e) {
+        throw new HandshakeException(e);
+      }
+  }
+
+  @Override
+  public D2DConnectionContext toConnectionContext() throws HandshakeException {
+    if (handshakeState == State.HANDSHAKE_ALREADY_USED) {
+      throw new HandshakeException("Cannot reuse handshake context; is has already been used");
+    }
+
+    if (!isHandshakeComplete()) {
+      throw new HandshakeException("Handshake is not complete; cannot create connection context");
+    }
+
+    handshakeState = State.HANDSHAKE_ALREADY_USED;
+
+    if (protocolVersionToUse == D2DConnectionContextV0.PROTOCOL_VERSION) {
+      // Both sides start with an initial sequence number of 1 because the last message of the
+      // handshake had an optional payload with sequence number 1.  D2DConnectionContext remembers
+      // the last sequence number used by each side.
+      // Note: initiatorEncodeKey == responderEncodeKey
+      return new D2DConnectionContextV0(initiatorEncodeKey, 1 /** initialSequenceNumber */);
+    } else {
+      SecretKey encodeKey = isInitiator ? initiatorEncodeKey : responderEncodeKey;
+      SecretKey decodeKey = isInitiator ? responderEncodeKey : initiatorEncodeKey;
+      // Only the responder sends a DeviceToDeviceMessage during the handshake, so it has an initial
+      // sequence number of 1.  The initiator will therefore have an initial sequence number of 0.
+      int initialEncodeSequenceNumber = isInitiator ? 0 : 1;
+      int initialDecodeSequenceNumber = isInitiator ? 1 : 0;
+      return new D2DConnectionContextV1(
+          encodeKey, decodeKey, initialEncodeSequenceNumber, initialDecodeSequenceNumber);
+    }
+  }
+}
diff --git a/src/main/java/com/google/security/cryptauth/lib/securegcm/D2DHandshakeContext.java b/src/main/java/com/google/security/cryptauth/lib/securegcm/D2DHandshakeContext.java
new file mode 100644
index 0000000..8c35d22
--- /dev/null
+++ b/src/main/java/com/google/security/cryptauth/lib/securegcm/D2DHandshakeContext.java
@@ -0,0 +1,158 @@
+/* Copyright 2018 Google LLC
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.google.security.cryptauth.lib.securegcm;
+
+/**
+ * Describes a cryptographic handshake with arbitrary number of round trips.  Some handshake
+ * messages may also send a payload.
+ *
+ * <p>Generic usage for handshake Initiator:
+ * {@code
+ *   // Handshake Initiator
+ *   D2DHandshakeContext handshake = <specific handshake>.forInitiator();
+ *   while (!handshake.isHandshakeComplete()) {
+ *     try {
+ *       // Get the next handshake message to send
+ *       byte[] initiatorMessage = handshake.getNextHandshakeMessage();
+ *
+ *       // Send the message out and get the response
+ *       socket.send(initiatorMessage);
+ *       byte[] responderMessage = socket.read();
+ *
+ *       // Handle the response and obtain the optional payload
+ *       byte[] payload = handshake.parseHandshakeMessage(responderMessage);
+ *
+ *       // Handle the payload if one was sent
+ *       if (payload.length > 0) {
+ *         handlePayload(payload);
+ *       }
+ *     } catch (HandshakeException e) {
+ *       // Handshake has failed, bail
+ *       Log("Handshake failed!", e);
+ *       return;
+ *     }
+ *   }
+ *
+ *   ConnectionContext connectionContext;
+ *   try {
+ *     // Upgrade handshake context to a full connection context
+ *     connectionContext = handshake.toConnectionContext();
+ *   } catch (HandshakeException e) {
+ *     Log("Cannot convert handshake to connection context", e);
+ *   }
+ * }
+ *
+ * <p>Generic usage for handshake Responder:
+ * {@code
+ *   // Handshake Responder
+ *   D2DHandshakeContext handshake = <specific handshake>.forResponder();
+ *
+ *   while (!handshake.isHandshakeComplete()) {
+ *     try {
+ *       // Get the message from the initiator
+ *       byte[] initiatorMessage = socket.read();
+ *
+ *       // Handle the message and get the payload if it exists
+ *       byte[] payload = handshake.parseHandshakeMessage(initiatorMessage);
+ *
+ *       // Handle the payload if one was sent
+ *       if (payload.length > 0) {
+ *         handlePayload(payload);
+ *       }
+ *
+ *       // Make sure that wasn't the last message
+ *       if (handshake.isHandshakeComplete()) {
+ *         break;
+ *       }
+ *
+ *       // Get next message to send and send it
+ *       byte[] responderMessage = handshake.getNextHandshakeMessage();
+ *       socket.send(responderMessage);
+ *     } catch (HandshakeException e) {
+ *       // Handshake has failed, bail
+ *       Log("Handshake failed!", e);
+ *       return;
+ *     }
+ *   }
+ *
+ *   ConnectionContext connectionContext;
+ *   try {
+ *     // Upgrade handshake context to a full connection context
+ *     connectionContext = handshake.toConnectionContext();
+ *   } catch (HandshakeException e) {
+ *     Log("Cannot convert handshake to connection context", e);
+ *   }
+ * }
+ */
+public interface D2DHandshakeContext {
+
+  /**
+   * Tells the caller whether the handshake has completed or not. If the handshake is complete, the
+   * caller may call {@link #toConnectionContext()} to obtain a connection context.
+   *
+   * @return true if the handshake is complete, false otherwise
+   */
+  boolean isHandshakeComplete();
+
+  /**
+   * Constructs the next message that should be sent in the handshake.
+   *
+   * @return the next message
+   * @throws HandshakeException if the handshake is over or if the next handshake message can't be
+   *     obtained (e.g., there is an internal error)
+   */
+  byte[] getNextHandshakeMessage() throws HandshakeException;
+
+  /**
+   * Tells the caller whether the next handshake message may carry a payload. If true, caller may
+   * call {@link #getNextHandshakeMessage(byte[])} instead of the regular
+   * {@link #getNextHandshakeMessage()}. If false, calling {@link #getNextHandshakeMessage(byte[])}
+   * will result in a {@link HandshakeException}.
+   *
+   * @return true if the next handshake message can carry a payload, false otherwise
+   */
+  boolean canSendPayloadInHandshakeMessage();
+
+  /**
+   * Constructs the next message that should be sent in the handshake along with a payload. Caller
+   * should verify that this method can be called by calling
+   * {@link #canSendPayloadInHandshakeMessage()}.
+   *
+   * @param payload the payload to include in the handshake message
+   * @return the next message
+   * @throws HandshakeException if the handshake is over or if the next handshake message can't be
+   *     obtained (e.g., there is an internal error) or if the payload may not be included in this
+   *     message
+   */
+  byte[] getNextHandshakeMessage(byte[] payload) throws HandshakeException;
+
+  /**
+   * Parses a handshake message and returns the included payload (if any).
+   *
+   * @param handshakeMessage message received in the handshake
+   * @return payload or empty byte[] if no payload was in the handshake message
+   * @throws HandshakeException if an error occurs in parsing the handshake message
+   */
+  byte[] parseHandshakeMessage(byte[] handshakeMessage) throws HandshakeException;
+
+  /**
+   * Creates a full {@link D2DConnectionContext}. May only be called if
+   * {@link #isHandshakeComplete()} returns true.
+   *
+   * @return a full {@link D2DConnectionContext}
+   * @throws HandshakeException if a connection context cannot be created
+   */
+  D2DConnectionContext toConnectionContext() throws HandshakeException;
+}
diff --git a/src/main/java/com/google/security/cryptauth/lib/securegcm/D2DSpakeEd25519Handshake.java b/src/main/java/com/google/security/cryptauth/lib/securegcm/D2DSpakeEd25519Handshake.java
new file mode 100644
index 0000000..da5abf1
--- /dev/null
+++ b/src/main/java/com/google/security/cryptauth/lib/securegcm/D2DSpakeEd25519Handshake.java
@@ -0,0 +1,648 @@
+/* Copyright 2018 Google LLC
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.google.security.cryptauth.lib.securegcm;
+
+import com.google.common.annotations.VisibleForTesting;
+import com.google.protobuf.ByteString;
+import com.google.protobuf.InvalidProtocolBufferException;
+import com.google.security.cryptauth.lib.securegcm.DeviceToDeviceMessagesProto.DeviceToDeviceMessage;
+import com.google.security.cryptauth.lib.securegcm.DeviceToDeviceMessagesProto.EcPoint;
+import com.google.security.cryptauth.lib.securegcm.DeviceToDeviceMessagesProto.SpakeHandshakeMessage;
+import com.google.security.cryptauth.lib.securegcm.Ed25519.Ed25519Exception;
+import com.google.security.cryptauth.lib.securegcm.TransportCryptoOps.Payload;
+import com.google.security.cryptauth.lib.securegcm.TransportCryptoOps.PayloadType;
+import java.math.BigInteger;
+import java.security.InvalidKeyException;
+import java.security.MessageDigest;
+import java.security.NoSuchAlgorithmException;
+import java.security.SecureRandom;
+import java.security.SignatureException;
+import javax.crypto.spec.SecretKeySpec;
+
+/**
+ * Implements a {@link D2DHandshakeContext} by using SPAKE2 (Simple Password-Based Encrypted Key
+ * Exchange Protocol) on top of the Ed25519 curve.
+ * SPAKE2: http://www.di.ens.fr/~mabdalla/papers/AbPo05a-letter.pdf
+ * Ed25519: http://ed25519.cr.yp.to/
+ *
+ * <p>Usage:
+ * {@code
+ *   // initiator:
+ *   D2DHandshakeContext initiatorHandshakeContext =
+ *       D2DSpakeEd25519Handshake.forInitiator(PASSWORD);
+ *   byte[] initiatorMsg = initiatorHandshakeContext.getNextHandshakeMessage();
+ *   // (send initiatorMsg to responder)
+ *
+ *   // responder:
+ *   D2DHandshakeContext responderHandshakeContext =
+ *       D2DSpakeEd25519Handshake.forResponder(PASSWORD);
+ *   responderHandshakeContext.parseHandshakeMessage(initiatorMsg);
+ *   byte[] responderMsg = responderHandshakeContext.getNextHandshakeMessage();
+ *   // (send responderMsg to initiator)
+ *
+ *   // initiator:
+ *   initiatorHandshakeContext.parseHandshakeMessage(responderMsg);
+ *   initiatorMsg = initiatorHandshakeContext.getNextHandshakeMessage();
+ *   // (send initiatorMsg to responder)
+ *
+ *   // responder:
+ *   responderHandshakeContext.parseHandshakeMessage(initiatorMsg);
+ *   responderMsg = responderHandshakeContext.getNextHandshakeMessage();
+ *   D2DConnectionContext responderCtx = responderHandshakeContext.toConnectionContext();
+ *   // (send responderMsg to initiator)
+ *
+ *   // initiator:
+ *   initiatorHandshakeContext.parseHandshakeMessage(responderMsg);
+ *   D2DConnectionContext initiatorCtx = initiatorHandshakeContext.toConnectionContext();
+ * }
+ *
+ * <p>The initial computation is:
+ *   Initiator                                              Responder
+ *    has KM (pre-agreed point)                              has KM (pre-agreed point)
+ *    has KN (pre-agreed point)                              has KN (pre-agreed point)
+ *    has Password (pre-agreed)                              has Password (pre-agreed)
+ *    picks random scalar Xi (private key)                   picks random scalar Xr (private key)
+ *    computes the public key Pxi = G*Xi                     computes the public key Pxr = G*Xr
+ *    computes commitment:                                   computes commitment:
+ *      Ci = KM * password + Pxi                               Cr = KN * password + Pxr
+ *
+ * <p>The flow is:
+ *   Initiator                                              Responder
+ *              ----- Ci --------------------------------->
+ *              <--------------------------------- Cr -----
+ *   computes shared key K:                                 computes shared key K:
+ *    (Cr - KN*password) * Xi                                (Ci - KM*password) * Xr
+ *   computes hash:                                         computes hash:
+ *    Hi = sha256(0|Cr|Ci|K)                                 Hr = sha256(1|Ci|Cr|K)
+ *              ----- Hi --------------------------------->
+ *                                                          Verify Hi
+ *              <-------------- Hr (optional payload) -----
+ *   Verify Hr
+ */
+public class D2DSpakeEd25519Handshake implements D2DHandshakeContext {
+  // Minimum length password that is acceptable for the handshake
+  public static final int MIN_PASSWORD_LENGTH = 4;
+  /**
+   * Creates a new SPAKE handshake object for the initiator.
+   *
+   * @param password the password that should be used in the handshake.  Note that this should be
+   *     at least {@value #MIN_PASSWORD_LENGTH} bytes long
+   */
+  public static D2DSpakeEd25519Handshake forInitiator(byte[] password) throws HandshakeException {
+    return new D2DSpakeEd25519Handshake(State.INITIATOR_START, password);
+  }
+
+  /**
+   * Creates a new SPAKE handshake object for the responder.
+   *
+   * @param password the password that should be used in the handshake.  Note that this should be
+   *     at least {@value #MIN_PASSWORD_LENGTH} bytes long
+   */
+  public static D2DSpakeEd25519Handshake forResponder(byte[] password) throws HandshakeException {
+    return new D2DSpakeEd25519Handshake(State.RESPONDER_START, password);
+  }
+
+  //
+  // The protocol requires two verifiable, randomly generated group point. They were generated
+  // using the python code below. The algorithm is to first pick a random y in the group and solve
+  // the elliptic curve equation for a value of x, if possible. We then use (x, y) as the random
+  // point.
+  // Source of ed25519 is here: http://ed25519.cr.yp.to/python/ed25519.py
+  // import ed25519
+  // import hashlib
+  //
+  // # Seeds
+  // seed1 = 'D2D Ed25519 point generation seed (M)'
+  // seed2 = 'D2D Ed25519 point generation seed (N)'
+  //
+  // def find_seed(seed):
+  //   # generate a random scalar for the y coordinate
+  //   y = hashlib.sha256(seed).hexdigest()
+  //
+  //   P = ed25519.scalarmult(ed25519.B, int(y, 16) % ed25519.q)
+  //   if (not ed25519.isoncurve(P)):
+  //       print 'Wat? P should be on curve!'
+  //
+  //   print '  x: ' + hex(P[0])
+  //   print '  y: ' + hex(P[1])
+  //   print
+  //
+  // find_seed(seed1)
+  // find_seed(seed2)
+  //
+  // Output is:
+  //   x: 0x1981fb43f103290ecf9772022db8b19bfaf389057ed91e8486eb368763435925L
+  //   y: 0xa714c34f3b588aac92fd2587884a20964fd351a1f147d5c4bbf5c2f37a77c36L
+  //
+  //   x: 0x201a184f47d9a7973891d148e3d1c864d8084547131c2c1cefb7eebd26c63567L
+  //   y: 0x6da2d3b18ec4f9aa3b08e39c997cd8bf6e9948ffd4feffecaf8dd0b3d648b7e8L
+  //
+  // To get extended representation X, Y, Z, T, do: Z = 1, T = X*Y mod P
+  @VisibleForTesting
+  static final BigInteger[] KM = new BigInteger[] {
+    new BigInteger(new byte[] {(byte) 0x19, (byte) 0x81, (byte) 0xFB, (byte) 0x43,
+        (byte) 0xF1, (byte) 0x03, (byte) 0x29, (byte) 0x0E, (byte) 0xCF, (byte) 0x97,
+        (byte) 0x72, (byte) 0x02, (byte) 0x2D, (byte) 0xB8, (byte) 0xB1, (byte) 0x9B,
+        (byte) 0xFA, (byte) 0xF3, (byte) 0x89, (byte) 0x05, (byte) 0x7E, (byte) 0xD9,
+        (byte) 0x1E, (byte) 0x84, (byte) 0x86, (byte) 0xEB, (byte) 0x36, (byte) 0x87,
+        (byte) 0x63, (byte) 0x43, (byte) 0x59, (byte) 0x25}),
+    new BigInteger(new byte[] {(byte) 0x0A, (byte) 0x71, (byte) 0x4C, (byte) 0x34,
+        (byte) 0xF3, (byte) 0xB5, (byte) 0x88, (byte) 0xAA, (byte) 0xC9, (byte) 0x2F,
+        (byte) 0xD2, (byte) 0x58, (byte) 0x78, (byte) 0x84, (byte) 0xA2, (byte) 0x09,
+        (byte) 0x64, (byte) 0xFD, (byte) 0x35, (byte) 0x1A, (byte) 0x1F, (byte) 0x14,
+        (byte) 0x7D, (byte) 0x5C, (byte) 0x4B, (byte) 0xBF, (byte) 0x5C, (byte) 0x2F,
+        (byte) 0x37, (byte) 0xA7, (byte) 0x7C, (byte) 0x36}),
+    BigInteger.ONE,
+    new BigInteger(new byte[] {(byte) 0x04, (byte) 0x8F, (byte) 0xC1, (byte) 0xCE,
+        (byte) 0xE5, (byte) 0x83, (byte) 0x99, (byte) 0x25, (byte) 0xE5, (byte) 0x9B,
+        (byte) 0x80, (byte) 0xEA, (byte) 0xAD, (byte) 0x82, (byte) 0xAC, (byte) 0x0A,
+        (byte) 0x3C, (byte) 0xFE, (byte) 0xC5, (byte) 0x60, (byte) 0x93, (byte) 0x59,
+        (byte) 0x8B, (byte) 0x48, (byte) 0x44, (byte) 0xDD, (byte) 0x2A, (byte) 0x3E,
+        (byte) 0x24, (byte) 0x5D, (byte) 0x88, (byte) 0x33})};
+
+  @VisibleForTesting
+  static final BigInteger[] KN = new BigInteger[] {
+    new BigInteger(new byte[] {(byte) 0x20, (byte) 0x1A, (byte) 0x18, (byte) 0x4F,
+        (byte) 0x47, (byte) 0xD9, (byte) 0xA7, (byte) 0x97, (byte) 0x38, (byte) 0x91,
+        (byte) 0xD1, (byte) 0x48, (byte) 0xE3, (byte) 0xD1, (byte) 0xC8, (byte) 0x64,
+        (byte) 0xD8, (byte) 0x08, (byte) 0x45, (byte) 0x47, (byte) 0x13, (byte) 0x1C,
+        (byte) 0x2C, (byte) 0x1C, (byte) 0xEF, (byte) 0xB7, (byte) 0xEE, (byte) 0xBD,
+        (byte) 0x26, (byte) 0xC6, (byte) 0x35, (byte) 0x67}),
+    new BigInteger(new byte[] {(byte) 0x6D, (byte) 0xA2, (byte) 0xD3, (byte) 0xB1,
+        (byte) 0x8E, (byte) 0xC4, (byte) 0xF9, (byte) 0xAA, (byte) 0x3B, (byte) 0x08,
+        (byte) 0xE3, (byte) 0x9C, (byte) 0x99, (byte) 0x7C, (byte) 0xD8, (byte) 0xBF,
+        (byte) 0x6E, (byte) 0x99, (byte) 0x48, (byte) 0xFF, (byte) 0xD4, (byte) 0xFE,
+        (byte) 0xFF, (byte) 0xEC, (byte) 0xAF, (byte) 0x8D, (byte) 0xD0, (byte) 0xB3,
+        (byte) 0xD6, (byte) 0x48, (byte) 0xB7, (byte) 0xE8}),
+    BigInteger.ONE,
+    new BigInteger(new byte[] {(byte) 0x16, (byte) 0x40, (byte) 0xED, (byte) 0x5A,
+        (byte) 0x54, (byte) 0xFA, (byte) 0x0B, (byte) 0x07, (byte) 0x22, (byte) 0x86,
+        (byte) 0xE9, (byte) 0xD2, (byte) 0x2F, (byte) 0x46, (byte) 0x47, (byte) 0x63,
+        (byte) 0xFB, (byte) 0xF6, (byte) 0x0D, (byte) 0x79, (byte) 0x1D, (byte) 0x37,
+        (byte) 0xB9, (byte) 0x09, (byte) 0x3B, (byte) 0x58, (byte) 0x4D, (byte) 0xF4,
+        (byte) 0xC9, (byte) 0x95, (byte) 0xF7, (byte) 0x81})};
+
+  // Base point B as per ed25519.cr.yp.to
+  @VisibleForTesting
+  /* package */ static final BigInteger[] B = new BigInteger[] {
+    new BigInteger(new byte[] {(byte) 0x21, (byte) 0x69, (byte) 0x36, (byte) 0xD3,
+        (byte) 0xCD, (byte) 0x6E, (byte) 0x53, (byte) 0xFE, (byte) 0xC0, (byte) 0xA4,
+        (byte) 0xE2, (byte) 0x31, (byte) 0xFD, (byte) 0xD6, (byte) 0xDC, (byte) 0x5C,
+        (byte) 0x69, (byte) 0x2C, (byte) 0xC7, (byte) 0x60, (byte) 0x95, (byte) 0x25,
+        (byte) 0xA7, (byte) 0xB2, (byte) 0xC9, (byte) 0x56, (byte) 0x2D, (byte) 0x60,
+        (byte) 0x8F, (byte) 0x25, (byte) 0xD5, (byte) 0x1A}),
+    new BigInteger(new byte[] {(byte) 0x66, (byte) 0x66, (byte) 0x66, (byte) 0x66,
+        (byte) 0x66, (byte) 0x66, (byte) 0x66, (byte) 0x66, (byte) 0x66, (byte) 0x66,
+        (byte) 0x66, (byte) 0x66, (byte) 0x66, (byte) 0x66, (byte) 0x66, (byte) 0x66,
+        (byte) 0x66, (byte) 0x66, (byte) 0x66, (byte) 0x66, (byte) 0x66, (byte) 0x66,
+        (byte) 0x66, (byte) 0x66, (byte) 0x66, (byte) 0x66, (byte) 0x66, (byte) 0x66,
+        (byte) 0x66, (byte) 0x66, (byte) 0x66, (byte) 0x58}),
+    BigInteger.ONE,
+    new BigInteger(new byte[] {(byte) 0x67, (byte) 0x87, (byte) 0x5F, (byte) 0x0F,
+        (byte) 0xD7, (byte) 0x8B, (byte) 0x76, (byte) 0x65, (byte) 0x66, (byte) 0xEA,
+        (byte) 0x4E, (byte) 0x8E, (byte) 0x64, (byte) 0xAB, (byte) 0xE3, (byte) 0x7D,
+        (byte) 0x20, (byte) 0xF0, (byte) 0x9F, (byte) 0x80, (byte) 0x77, (byte) 0x51,
+        (byte) 0x52, (byte) 0xF5, (byte) 0x6D, (byte) 0xDE, (byte) 0x8A, (byte) 0xB3,
+        (byte) 0xA5, (byte) 0xB7, (byte) 0xDD, (byte) 0xA3})};
+
+  // Number of bits needed to represent a point
+  private static final int POINT_SIZE_BITS = 256;
+
+  // Java Message Digest name for SHA 256
+  private static final String SHA256 = "SHA-256";
+
+  // Pre-shared password hash represented as an integer
+  private BigInteger passwordHash;
+
+  // Current state of the handshake
+  private State handshakeState;
+
+  // Derived shared key
+  private byte[] sharedKey;
+
+  // Private key (random scalar)
+  private BigInteger valueX;
+
+  // Public key (random point, in extended notation, based on valueX)
+  private BigInteger[] pointX;
+
+  // Commitment we've received from the other party (their password-authenticated public key)
+  private BigInteger[] theirCommitmentPointAffine;
+  private BigInteger[] theirCommitmentPointExtended;
+
+  // Commitment we've sent to the other party (our password-authenticated public key)
+  private BigInteger[] ourCommitmentPointAffine;
+  private BigInteger[] ourCommitmentPointExtended;
+
+  private enum State {
+    // Initiator state
+    INITIATOR_START,
+    INITIATOR_WAITING_FOR_RESPONDER_COMMITMENT,
+    INITIATOR_AFTER_RESPONDER_COMMITMENT,
+    INITIATOR_WAITING_FOR_RESPONDER_HASH,
+
+    // Responder state
+    RESPONDER_START,
+    RESPONDER_AFTER_INITIATOR_COMMITMENT,
+    RESPONDER_WAITING_FOR_INITIATOR_HASH,
+    RESPONDER_AFTER_INITIATOR_HASH,
+
+    // Common completion state
+    HANDSHAKE_FINISHED,
+    HANDSHAKE_ALREADY_USED
+  }
+
+  @VisibleForTesting
+  D2DSpakeEd25519Handshake(State state, byte[] password) throws HandshakeException {
+    if (password == null || password.length < MIN_PASSWORD_LENGTH) {
+      throw new HandshakeException("Passwords must be at least " + MIN_PASSWORD_LENGTH + " bytes");
+    }
+
+    handshakeState = state;
+    passwordHash = new BigInteger(1 /* positive */, hash(password));
+
+    do {
+      valueX = new BigInteger(POINT_SIZE_BITS, new SecureRandom());
+    } while (valueX.equals(BigInteger.ZERO));
+
+    try {
+      pointX = Ed25519.scalarMultiplyExtendedPoint(B, valueX);
+    } catch (Ed25519Exception e) {
+      throw new HandshakeException("Could not make public key point", e);
+    }
+  }
+
+  @Override
+  public boolean isHandshakeComplete() {
+    switch (handshakeState) {
+      case HANDSHAKE_FINISHED:
+        // fall-through intentional
+      case HANDSHAKE_ALREADY_USED:
+        return true;
+
+      default:
+        return false;
+    }
+  }
+
+  @Override
+  public byte[] getNextHandshakeMessage() throws HandshakeException {
+    byte[] nextMessage;
+
+    switch(handshakeState) {
+      case INITIATOR_START:
+        nextMessage = makeCommitmentPointMessage(true /* is initiator */);
+        handshakeState = State.INITIATOR_WAITING_FOR_RESPONDER_COMMITMENT;
+        break;
+
+      case RESPONDER_AFTER_INITIATOR_COMMITMENT:
+        nextMessage = makeCommitmentPointMessage(false /* is initiator */);
+        handshakeState = State.RESPONDER_WAITING_FOR_INITIATOR_HASH;
+        break;
+
+      case INITIATOR_AFTER_RESPONDER_COMMITMENT:
+        nextMessage = makeSharedKeyHashMessage(true /* is initiator */, null /* no payload */);
+        handshakeState = State.INITIATOR_WAITING_FOR_RESPONDER_HASH;
+        break;
+
+      case RESPONDER_AFTER_INITIATOR_HASH:
+        nextMessage = makeSharedKeyHashMessage(false /* is initiator */, null /* no payload */);
+        handshakeState = State.HANDSHAKE_FINISHED;
+        break;
+
+      default:
+        throw new HandshakeException("Cannot get next message in state: " + handshakeState);
+    }
+
+    return nextMessage;
+  }
+
+  @Override
+  public byte[] getNextHandshakeMessage(byte[] payload) throws HandshakeException {
+    byte[] nextMessage;
+
+    switch (handshakeState) {
+      case RESPONDER_AFTER_INITIATOR_HASH:
+        nextMessage = makeSharedKeyHashMessage(false /* is initiator */, payload);
+        handshakeState = State.HANDSHAKE_FINISHED;
+        break;
+
+      default:
+        throw new HandshakeException(
+            "Cannot send handshake message with payload in state: " + handshakeState);
+    }
+
+    return nextMessage;
+  }
+
+  private byte[] makeCommitmentPointMessage(boolean isInitiator) throws HandshakeException {
+    try {
+      ourCommitmentPointExtended =
+          Ed25519.scalarMultiplyExtendedPoint(isInitiator ? KM : KN, passwordHash);
+      ourCommitmentPointExtended = Ed25519.addExtendedPoints(ourCommitmentPointExtended, pointX);
+      ourCommitmentPointAffine = Ed25519.toAffine(ourCommitmentPointExtended);
+
+      return SpakeHandshakeMessage.newBuilder()
+          .setEcPoint(
+              EcPoint.newBuilder()
+                .setCurve(DeviceToDeviceMessagesProto.Curve.ED_25519)
+                .setX(ByteString.copyFrom(ourCommitmentPointAffine[0].toByteArray()))
+                .setY(ByteString.copyFrom(ourCommitmentPointAffine[1].toByteArray()))
+                .build())
+          .setFlowNumber(isInitiator ? 1 : 2 /* first or second message */)
+          .build()
+          .toByteArray();
+    } catch (Ed25519Exception e) {
+      throw new HandshakeException("Could not make commitment point message", e);
+    }
+  }
+
+  private void makeSharedKey(boolean isInitiator) throws HandshakeException {
+
+    if (handshakeState != State.RESPONDER_START
+        && handshakeState != State.INITIATOR_WAITING_FOR_RESPONDER_COMMITMENT) {
+      throw new HandshakeException("Cannot make shared key in state: " + handshakeState);
+    }
+
+    try {
+      BigInteger[] kNMP = Ed25519.scalarMultiplyExtendedPoint(isInitiator ? KN : KM, passwordHash);
+
+      // TheirPublicKey = TheirCommitment - kNMP = (TheirPublicKey + kNMP) - kNMP
+      BigInteger[] theirPublicKey =
+          Ed25519.subtractExtendedPoints(theirCommitmentPointExtended, kNMP);
+
+      BigInteger[] sharedKeyPoint = Ed25519.scalarMultiplyExtendedPoint(theirPublicKey, valueX);
+      sharedKey = hash(pointToByteArray(Ed25519.toAffine(sharedKeyPoint)));
+    } catch (Ed25519Exception e) {
+      throw new HandshakeException("Error computing shared key", e);
+    }
+  }
+
+  private byte[] makeSharedKeyHashMessage(boolean isInitiator, byte[] payload)
+      throws HandshakeException {
+    SpakeHandshakeMessage.Builder handshakeMessage = SpakeHandshakeMessage.newBuilder()
+        .setHashValue(ByteString.copyFrom(computeOurKeyHash(isInitiator)))
+        .setFlowNumber(isInitiator ? 3 : 4 /* third or fourth message */);
+
+    if (canSendPayloadInHandshakeMessage() && payload != null) {
+      DeviceToDeviceMessage deviceToDeviceMessage =
+          D2DConnectionContext.createDeviceToDeviceMessage(payload, 1 /* sequence number */);
+      try {
+        handshakeMessage.setPayload(ByteString.copyFrom(
+            D2DCryptoOps.signcryptPayload(
+              new Payload(PayloadType.DEVICE_TO_DEVICE_RESPONDER_HELLO_PAYLOAD,
+                  deviceToDeviceMessage.toByteArray()),
+              new SecretKeySpec(sharedKey, "AES"))));
+      } catch (InvalidKeyException | NoSuchAlgorithmException e) {
+        throw new HandshakeException("Cannot set payload", e);
+      }
+    }
+
+    return handshakeMessage.build().toByteArray();
+  }
+
+  private byte[] computeOurKeyHash(boolean isInitiator) throws HandshakeException {
+    return hash(concat(
+        new byte[] { (byte) (isInitiator ? 0 : 1) },
+        pointToByteArray(theirCommitmentPointAffine),
+        pointToByteArray(ourCommitmentPointAffine),
+        sharedKey));
+  }
+
+  private byte[] computeTheirKeyHash(boolean isInitiator) throws HandshakeException {
+    return hash(concat(
+        new byte[] { (byte) (isInitiator ? 1 : 0) },
+        pointToByteArray(ourCommitmentPointAffine),
+        pointToByteArray(theirCommitmentPointAffine),
+        sharedKey));
+  }
+
+  private byte[] pointToByteArray(BigInteger[] p) {
+    return concat(p[0].toByteArray(), p[1].toByteArray());
+  }
+
+  @Override
+  public boolean canSendPayloadInHandshakeMessage() {
+    return handshakeState == State.RESPONDER_AFTER_INITIATOR_HASH;
+  }
+
+  @Override
+  public byte[] parseHandshakeMessage(byte[] handshakeMessage) throws HandshakeException {
+    if (handshakeMessage == null || handshakeMessage.length == 0) {
+      throw new HandshakeException("Handshake message too short");
+    }
+
+    byte[] payload = new byte[0];
+
+    switch(handshakeState) {
+      case RESPONDER_START:
+        // no payload can be sent in this message
+        parseCommitmentMessage(handshakeMessage, false /* is initiator */);
+        makeSharedKey(false /* is initiator */);
+        handshakeState = State.RESPONDER_AFTER_INITIATOR_COMMITMENT;
+        break;
+
+      case INITIATOR_WAITING_FOR_RESPONDER_COMMITMENT:
+        // no payload can be sent in this message
+        parseCommitmentMessage(handshakeMessage, true /* is initiator */);
+        makeSharedKey(true /* is initiator */);
+        handshakeState = State.INITIATOR_AFTER_RESPONDER_COMMITMENT;
+        break;
+
+      case RESPONDER_WAITING_FOR_INITIATOR_HASH:
+        // no payload can be sent in this message
+        parseHashMessage(handshakeMessage, false /* is initiator */);
+        handshakeState = State.RESPONDER_AFTER_INITIATOR_HASH;
+        break;
+
+      case INITIATOR_WAITING_FOR_RESPONDER_HASH:
+        payload = parseHashMessage(handshakeMessage, true /* is initiator */);
+        handshakeState = State.HANDSHAKE_FINISHED;
+        break;
+
+      default:
+        throw new HandshakeException("Cannot parse message in state: " + handshakeState);
+    }
+
+    return payload;
+  }
+
+  private byte[] parseHashMessage(byte[] handshakeMessage, boolean isInitiator)
+      throws HandshakeException {
+    SpakeHandshakeMessage hashMessage;
+
+    // Parse the message
+    try {
+      hashMessage = SpakeHandshakeMessage.parseFrom(handshakeMessage);
+    } catch (InvalidProtocolBufferException e) {
+      throw new HandshakeException("Could not parse hash message", e);
+    }
+
+    // Check flow number
+    if (!hashMessage.hasFlowNumber()) {
+      throw new HandshakeException("Hash message missing flow number");
+    }
+    int expectedFlowNumber = isInitiator ? 4 : 3;
+    int actualFlowNumber = hashMessage.getFlowNumber();
+    if (actualFlowNumber != expectedFlowNumber) {
+      throw new HandshakeException("Hash message has flow number " + actualFlowNumber
+          + ", but expected flow number " + expectedFlowNumber);
+    }
+
+    // Check and extract hash
+    if (!hashMessage.hasHashValue()) {
+      throw new HandshakeException("Hash message missing hash value");
+    }
+
+    byte[] theirHash = hashMessage.getHashValue().toByteArray();
+    byte[] theirCorrectHash = computeTheirKeyHash(isInitiator);
+
+    if (!constantTimeArrayEquals(theirCorrectHash, theirHash)) {
+      throw new HandshakeException("Hash message had incorrect hash value");
+    }
+
+    if (isInitiator && hashMessage.hasPayload()) {
+      try {
+        DeviceToDeviceMessage message = D2DCryptoOps.decryptResponderHelloMessage(
+            new SecretKeySpec(sharedKey, "AES"),
+            hashMessage.getPayload().toByteArray());
+
+        if (message.getSequenceNumber() != 1) {
+          throw new HandshakeException("Incorrect sequence number in responder hello");
+        }
+
+        return message.getMessage().toByteArray();
+
+      } catch (SignatureException e) {
+        throw new HandshakeException("Error recovering payload from hash message", e);
+      }
+    }
+
+    // empty/no payload
+    return new byte[0];
+  }
+
+  private void parseCommitmentMessage(byte[] handshakeMessage, boolean isInitiator)
+      throws HandshakeException {
+    SpakeHandshakeMessage commitmentMessage;
+
+    // Parse the message
+    try {
+      commitmentMessage = SpakeHandshakeMessage.parseFrom(handshakeMessage);
+    } catch (InvalidProtocolBufferException e) {
+      throw new HandshakeException("Could not parse commitment message", e);
+    }
+
+    // Check flow number
+    if (!commitmentMessage.hasFlowNumber()) {
+      throw new HandshakeException("Commitment message missing flow number");
+    }
+    if (commitmentMessage.getFlowNumber() != (isInitiator ? 2 : 1)) {
+      throw new HandshakeException("Commitment message has wrong flow number");
+    }
+
+    // Check point and curve; and extract point
+    if (!commitmentMessage.hasEcPoint()) {
+      throw new HandshakeException("Commitment message missing point");
+    }
+    EcPoint commitmentPoint = commitmentMessage.getEcPoint();
+    if (!commitmentPoint.hasCurve()
+        || commitmentPoint.getCurve() != DeviceToDeviceMessagesProto.Curve.ED_25519) {
+      throw new HandshakeException("Commitment message has wrong curve");
+    }
+
+    if (!commitmentPoint.hasX()) {
+      throw new HandshakeException("Commitment point missing x coordinate");
+    }
+
+    if (!commitmentPoint.hasY()) {
+      throw new HandshakeException("Commitment point missing y coordinate");
+    }
+
+    // Build the point
+    theirCommitmentPointAffine = new BigInteger[] {
+        new BigInteger(commitmentPoint.getX().toByteArray()),
+        new BigInteger(commitmentPoint.getY().toByteArray())
+    };
+
+    // Validate the point to be sure
+    try {
+      Ed25519.validateAffinePoint(theirCommitmentPointAffine);
+      theirCommitmentPointExtended = Ed25519.toExtended(theirCommitmentPointAffine);
+    } catch (Ed25519Exception e) {
+      throw new HandshakeException("Error validating their commitment point", e);
+    }
+  }
+
+  @Override
+  public D2DConnectionContext toConnectionContext() throws HandshakeException {
+    if (handshakeState == State.HANDSHAKE_ALREADY_USED) {
+      throw new HandshakeException("Cannot reuse handshake context; is has already been used");
+    }
+
+    if (!isHandshakeComplete()) {
+      throw new HandshakeException("Handshake is not complete; cannot create connection context");
+    }
+
+    handshakeState = State.HANDSHAKE_ALREADY_USED;
+
+    // Both sides start with an initial sequence number of 1 because the last message of the
+    // handshake had an optional payload with sequence number 1.  D2DConnectionContext remembers
+    // the last sequence number used.
+    return new D2DConnectionContextV0(
+        new SecretKeySpec(sharedKey, "AES"), 1 /* initialSequenceNumber */);
+  }
+
+  /**
+   * Implementation of byte array concatenation copied from Guava.
+   */
+  private static byte[] concat(byte[]... arrays) {
+    int length = 0;
+    for (byte[] array : arrays) {
+      length += array.length;
+    }
+
+    byte[] result = new byte[length];
+    int pos = 0;
+    for (byte[] array : arrays) {
+      System.arraycopy(array, 0, result, pos, array.length);
+      pos += array.length;
+    }
+
+    return result;
+  }
+
+  private static byte[] hash(byte[] message) throws HandshakeException {
+    try {
+      return MessageDigest.getInstance(SHA256).digest(message);
+    } catch (NoSuchAlgorithmException e) {
+      throw new HandshakeException("Error performing hash", e);
+    }
+  }
+
+  private static boolean constantTimeArrayEquals(byte[] a, byte[] b) {
+    if (a == null || b == null) {
+      return (a == b);
+    }
+    if (a.length != b.length) {
+      return false;
+    }
+    byte result = 0;
+    for (int i = 0; i < b.length; i++) {
+      result = (byte) (result | (a[i] ^ b[i]));
+    }
+    return (result == 0);
+  }
+}
diff --git a/src/main/java/com/google/security/cryptauth/lib/securegcm/Ed25519.java b/src/main/java/com/google/security/cryptauth/lib/securegcm/Ed25519.java
new file mode 100644
index 0000000..2ea2563
--- /dev/null
+++ b/src/main/java/com/google/security/cryptauth/lib/securegcm/Ed25519.java
@@ -0,0 +1,271 @@
+/* Copyright 2018 Google LLC
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.google.security.cryptauth.lib.securegcm;
+
+import static java.math.BigInteger.ONE;
+import static java.math.BigInteger.ZERO;
+
+import com.google.common.annotations.VisibleForTesting;
+
+import java.math.BigInteger;
+
+/**
+ * Implements the Ed25519 twisted Edwards curve.  See http://ed25519.cr.yp.to/ for more details.
+ */
+public class Ed25519 {
+
+  // Don't instantiate
+  private Ed25519() { }
+
+  // Curve parameters (http://ed25519.cr.yp.to/)
+  private static final int HEX_RADIX = 16;
+  private static final BigInteger Ed25519_P =
+      new BigInteger("7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED", HEX_RADIX);
+  private static final BigInteger Ed25519_D =
+      new BigInteger("52036CEE2B6FFE738CC740797779E89800700A4D4141D8AB75EB4DCA135978A3", HEX_RADIX);
+
+  // Helps to do fast addition k = 2*d
+  private static final BigInteger Ed25519_K =
+      new BigInteger("2406D9DC56DFFCE7198E80F2EEF3D13000E0149A8283B156EBD69B9426B2F159", HEX_RADIX);
+
+  // Identity point in extended representation (0, 1, 1, 0)
+  static final BigInteger[] IDENTITY_POINT = new BigInteger[] {ZERO, ONE, ONE, ZERO};
+
+  // Helps for reading coordinate type in point representation
+  private static final int X = 0;
+  private static final int Y = 1;
+  private static final int Z = 2;
+  private static final int T = 3;
+
+  // Number of bits that we need to represent a point.  Realistically, we only need 255, but using
+  // 256 doesn't hurt.
+  private static final int POINT_SIZE_BITS = 256;
+
+  /**
+   * Returns the result of multiplying point p by scalar k. A point is represented as a BigInteger
+   * array of length 2 where the first element (at index 0) is the X coordinate and the second
+   * element (at index 1) is the Y coordinate.
+   */
+  public static BigInteger[] scalarMultiplyAffinePoint(BigInteger[] p, BigInteger k)
+      throws Ed25519Exception {
+    return toAffine(scalarMultiplyExtendedPoint(toExtended(p), k));
+  }
+
+  /**
+   * Returns the sum of two points in affine representation. A point is represented as a BigInteger
+   * array of length 2 where the first element (at index 0) is the X coordinate and the second
+   * element (at index 1) is the Y coordinate.
+   */
+  public static BigInteger[] addAffinePoints(BigInteger[] p1, BigInteger[] p2)
+      throws Ed25519Exception {
+    return toAffine(addExtendedPoints(toExtended(p1), toExtended(p2)));
+  }
+
+  /**
+   * Returns the result of subtracting p2 from p1 (i.e., p1 - p2) in affine representation. A point
+   * is represented as a BigInteger array of length 2 where the first element (at index 0) is the X
+   * coordinate and the second element (at index 1) is the Y coordinate.
+   */
+  public static BigInteger[] subtractAffinePoints(BigInteger[] p1, BigInteger[] p2)
+      throws Ed25519Exception {
+    return toAffine(subtractExtendedPoints(toExtended(p1), toExtended(p2)));
+  }
+
+  /**
+   * Validates that a given point in affine representation is on the curve and is positive.
+   * @throws Ed25519Exception if the point does not validate
+   */
+  public static void validateAffinePoint(BigInteger[] p) throws Ed25519Exception {
+    checkPointIsInAffineRepresentation(p);
+
+    BigInteger x = p[X];
+    BigInteger y = p[Y];
+
+    if (x.signum() != 1 || y.signum() != 1) {
+      throw new Ed25519Exception("Point encoding must use only positive integers");
+    }
+
+    if ((x.compareTo(Ed25519_P) >= 0) || (y.compareTo(Ed25519_P) >= 0)) {
+      throw new Ed25519Exception("Point lies outside of the expected field");
+    }
+
+    BigInteger xx = x.multiply(x);
+    BigInteger yy = y.multiply(y);
+    BigInteger lhs = xx.negate().add(yy).mod(Ed25519_P);                           // -x*x + y*y
+    BigInteger rhs = ONE.add(Ed25519_D.multiply(xx).multiply(yy)).mod(Ed25519_P);  // 1 + d*x*x*y*y
+
+    if (!lhs.equals(rhs)) {
+      throw new Ed25519Exception("Point does not lie on the expected curve");
+    }
+  }
+
+  /**
+   * Returns the result of multiplying point p by scalar k
+   */
+  static BigInteger[] scalarMultiplyExtendedPoint(BigInteger[] p, BigInteger k)
+      throws Ed25519Exception {
+    checkPointIsInExtendedRepresentation(p);
+    if (k == null) {
+      throw new Ed25519Exception("Can't multiply point by null");
+    }
+
+    if (k.bitLength() > POINT_SIZE_BITS) {
+      throw new Ed25519Exception(
+          "Refuse to multiply point by scalar with more than " + POINT_SIZE_BITS + " bits");
+    }
+
+    // Perform best effort time-constant accumulation
+    BigInteger[] q = IDENTITY_POINT;
+    BigInteger[] r = IDENTITY_POINT;
+    BigInteger[] doubleAccumulator = p;
+    for (int i = 0; i < POINT_SIZE_BITS; i++) {
+      if (k.testBit(i)) {
+        q = addExtendedPoints(q, doubleAccumulator);
+      } else {
+        r = addExtendedPoints(q, doubleAccumulator);
+      }
+      if (i < POINT_SIZE_BITS - 1) {
+        doubleAccumulator = doubleExtendedPoint(doubleAccumulator);
+      }
+    }
+
+    // Not needed, but we're just trying to fool the compiler into not optimizing away r
+    r = subtractExtendedPoints(r, r);
+    q = addExtendedPoints(q, r);
+    return q;
+  }
+
+  /**
+   * Returns the doubling of a point in extended representation
+   */
+  private static BigInteger[] doubleExtendedPoint(BigInteger[] p) throws Ed25519Exception {
+    // The Edwards curve is complete, so we can just add a point to itself.
+    // Note that the currently best known algorithms for doubling have the same order as addition.
+    // https://hyperelliptic.org/EFD/g1p/auto-twisted-extended-1.html
+    checkPointIsInExtendedRepresentation(p);
+
+    BigInteger c = p[T].pow(2).multiply(Ed25519_K);
+    BigInteger d = p[Z].pow(2).shiftLeft(1);
+    BigInteger e = p[Y].multiply(p[X]).shiftLeft(2);
+    BigInteger f = d.subtract(c);
+    BigInteger g = d.add(c);
+    BigInteger h = p[Y].pow(2).add(p[X].pow(2)).shiftLeft(1);
+
+    return new BigInteger[] {
+        e.multiply(f).mod(Ed25519_P),
+        g.multiply(h).mod(Ed25519_P),
+        f.multiply(g).mod(Ed25519_P),
+        e.multiply(h).mod(Ed25519_P)
+    };
+  }
+
+  /**
+   * Returns the result of subtracting p2 from p1 (p1 - p2)
+   */
+  static BigInteger[] subtractExtendedPoints(BigInteger[] p1, BigInteger[] p2)
+      throws Ed25519Exception {
+    checkPointIsInExtendedRepresentation(p1);
+    checkPointIsInExtendedRepresentation(p2);
+
+    return addExtendedPoints(p1, new BigInteger[] {p2[X].negate(), p2[Y], p2[Z], p2[T].negate()});
+  }
+
+  /**
+   * Returns the sum of two points in extended representation
+   * Uses: https://hyperelliptic.org/EFD/g1p/auto-twisted-extended-1.html#addition-add-2008-hwcd-3
+   */
+  static BigInteger[] addExtendedPoints(BigInteger[] p1, BigInteger[] p2)
+      throws Ed25519Exception {
+    checkPointIsInExtendedRepresentation(p1);
+    checkPointIsInExtendedRepresentation(p2);
+
+    BigInteger a = p1[Y].subtract(p1[X]).multiply(p2[Y].subtract(p2[X]));
+    BigInteger b = p1[Y].add(p1[X]).multiply(p2[Y].add(p2[X]));
+    BigInteger c = p1[T].multiply(Ed25519_K).multiply(p2[T]);
+    BigInteger d = p1[Z].add(p1[Z]).multiply(p2[Z]);
+    BigInteger e = b.subtract(a);
+    BigInteger f = d.subtract(c);
+    BigInteger g = d.add(c);
+    BigInteger h = b.add(a);
+
+    return new BigInteger[] {
+        e.multiply(f).mod(Ed25519_P),
+        g.multiply(h).mod(Ed25519_P),
+        f.multiply(g).mod(Ed25519_P),
+        e.multiply(h).mod(Ed25519_P)
+    };
+  }
+
+  /**
+   * Converts a point in affine representation to extended representation
+   */
+  @VisibleForTesting
+  static BigInteger[] toExtended(BigInteger[] p) throws Ed25519Exception {
+    checkPointIsInAffineRepresentation(p);
+
+    return new BigInteger[] {p[X], p[Y], ONE, p[X].multiply(p[Y]).mod(Ed25519_P)}; // x, y, 1, x*y
+  }
+
+  /**
+   * Converts a point in extended representation to affine representation
+   */
+  @VisibleForTesting
+  static BigInteger[] toAffine(BigInteger[] p) throws Ed25519Exception {
+    checkPointIsInExtendedRepresentation(p);
+
+    return new BigInteger[] {p[X].multiply(p[Z].modInverse(Ed25519_P)).mod(Ed25519_P), // x = X / Z
+        p[Y].multiply(p[Z].modInverse(Ed25519_P)).mod(Ed25519_P)};                     // y = Y / Z
+  }
+
+  /**
+   * Checks that a given point is in the extended representation
+   * @throws Ed25519Exception if the point is not in the extended representation
+   */
+  @VisibleForTesting
+  static void checkPointIsInExtendedRepresentation(BigInteger[] p) throws Ed25519Exception {
+    if (p == null || p.length != 4 || p[X] == null || p[Y] == null || p[Z] == null
+        || p[T] == null) {
+      throw new Ed25519Exception("Point is not in extended representation");
+    }
+  }
+
+  /**
+   * Checks that a given point is in the affine representation
+   * @throws Ed25519Exception if the point is not in the affine representation
+   */
+  @VisibleForTesting
+  static void checkPointIsInAffineRepresentation(BigInteger[] p) throws Ed25519Exception {
+    if (p == null || p.length != 2 || p[X] == null || p[Y] == null) {
+      throw new Ed25519Exception("Point is not in affine representation");
+    }
+  }
+
+  /**
+   * Represents an unrecoverable error that has occurred while performing a curve operation.
+   */
+  public static class Ed25519Exception extends Exception {
+    public Ed25519Exception(String message) {
+      super(message);
+    }
+
+    public Ed25519Exception(Exception e) {
+      super(e);
+    }
+
+    public Ed25519Exception(String message, Exception e) {
+      super(message, e);
+    }
+  }
+}
diff --git a/src/main/java/com/google/security/cryptauth/lib/securegcm/EnrollmentCryptoOps.java b/src/main/java/com/google/security/cryptauth/lib/securegcm/EnrollmentCryptoOps.java
new file mode 100644
index 0000000..328cb53
--- /dev/null
+++ b/src/main/java/com/google/security/cryptauth/lib/securegcm/EnrollmentCryptoOps.java
@@ -0,0 +1,233 @@
+/* Copyright 2018 Google LLC
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.google.security.cryptauth.lib.securegcm;
+
+import com.google.protobuf.InvalidProtocolBufferException;
+import com.google.security.annotations.SuppressInsecureCipherModeCheckerPendingReview;
+import com.google.security.cryptauth.lib.securegcm.SecureGcmProto.GcmDeviceInfo;
+import com.google.security.cryptauth.lib.securegcm.SecureGcmProto.GcmMetadata;
+import com.google.security.cryptauth.lib.securegcm.TransportCryptoOps.PayloadType;
+import com.google.security.cryptauth.lib.securemessage.CryptoOps.EncType;
+import com.google.security.cryptauth.lib.securemessage.CryptoOps.SigType;
+import com.google.security.cryptauth.lib.securemessage.PublicKeyProtoUtil;
+import com.google.security.cryptauth.lib.securemessage.SecureMessageBuilder;
+import com.google.security.cryptauth.lib.securemessage.SecureMessageParser;
+import com.google.security.cryptauth.lib.securemessage.SecureMessageProto.HeaderAndBody;
+import com.google.security.cryptauth.lib.securemessage.SecureMessageProto.SecureMessage;
+import java.security.InvalidKeyException;
+import java.security.KeyPair;
+import java.security.MessageDigest;
+import java.security.NoSuchAlgorithmException;
+import java.security.PrivateKey;
+import java.security.PublicKey;
+import java.security.SignatureException;
+import java.security.spec.InvalidKeySpecException;
+import java.util.Arrays;
+import javax.crypto.KeyAgreement;
+import javax.crypto.SecretKey;
+
+/**
+ * Utility class for implementing Secure GCM enrollment flows.
+ */
+public class EnrollmentCryptoOps {
+
+  private EnrollmentCryptoOps() { }  // Do not instantiate
+
+  /**
+   * Type of symmetric key signature to use for the signcrypted "outer layer" message.
+   */
+  private static final SigType OUTER_SIG_TYPE = SigType.HMAC_SHA256;
+
+  /**
+   * Type of symmetric key encryption to use for the signcrypted "outer layer" message.
+   */
+  private static final EncType OUTER_ENC_TYPE = EncType.AES_256_CBC;
+
+  /**
+   * Type of public key signature to use for the (cleartext) "inner layer" message.
+   */
+  private static final SigType INNER_SIG_TYPE = SigType.ECDSA_P256_SHA256;
+
+  /**
+   * Type of public key signature to use for the (cleartext) "inner layer" message on platforms that
+   * don't support Elliptic Curve operations (such as old Android versions).
+   */
+  private static final SigType LEGACY_INNER_SIG_TYPE = SigType.RSA2048_SHA256;
+
+  /**
+   * Which {@link KeyAgreement} algorithm to use.
+   */
+  private static final String KA_ALG = "ECDH";
+
+  /**
+   * Which {@link KeyAgreement} algorithm to use on platforms that don't support Elliptic Curve.
+   */
+  private static final String LEGACY_KA_ALG = "DH";
+
+  /**
+   * Used by both the client and server to perform a key exchange.
+   *
+   * @return a {@link SecretKey} derived from the key exchange
+   * @throws InvalidKeyException if either of the input keys is of the wrong type
+   */
+  @SuppressInsecureCipherModeCheckerPendingReview // b/32143855
+  public static SecretKey doKeyAgreement(PrivateKey myKey, PublicKey peerKey)
+      throws InvalidKeyException {
+    String alg = KA_ALG;
+    if (KeyEncoding.isLegacyPrivateKey(myKey)) {
+      alg = LEGACY_KA_ALG;
+    }
+    KeyAgreement agreement;
+    try {
+      agreement = KeyAgreement.getInstance(alg);
+    } catch (NoSuchAlgorithmException e) {
+      throw new RuntimeException(e);
+    }
+
+    agreement.init(myKey);
+    agreement.doPhase(peerKey, true);
+    byte[] agreedKey = agreement.generateSecret();
+
+    // Derive a 256-bit AES key by using sha256 on the Diffie-Hellman output
+    return KeyEncoding.parseMasterKey(sha256(agreedKey));
+  }
+
+  public static KeyPair generateEnrollmentKeyAgreementKeyPair(boolean isLegacy) {
+    if (isLegacy) {
+      return PublicKeyProtoUtil.generateDh2048KeyPair();
+    }
+    return PublicKeyProtoUtil.generateEcP256KeyPair();
+  }
+
+  /**
+   * @return SHA-256 hash of {@code masterKey}
+   */
+  public static byte[] getMasterKeyHash(SecretKey masterKey) {
+    return sha256(masterKey.getEncoded());
+  }
+
+  /**
+   * Used by the client to signcrypt an enrollment request before sending it to the server.
+   *
+   *  <p>Note: You <em>MUST</em> correctly set the value of the {@code device_master_key_hash} on
+   *  {@code enrollmentInfo} from {@link #getMasterKeyHash(SecretKey)} before calling this method.
+   *
+   * @param enrollmentInfo the enrollment request to send to the server. You must correctly set
+   *   the {@code device_master_key_hash} field.
+   * @param masterKey the shared key derived from the key agreement
+   * @param signingKey the signing key corresponding to the user's {@link PublicKey} being enrolled
+   * @return the encrypted enrollment message
+   * @throws IllegalArgumentException if {@code enrollmentInfo} doesn't have a valid
+   *   {@code device_master_key_hash}
+   * @throws InvalidKeyException if {@code masterKey} or {@code signingKey} is the wrong type
+   */
+  public static byte[] encryptEnrollmentMessage(
+      GcmDeviceInfo enrollmentInfo, SecretKey masterKey, PrivateKey signingKey)
+          throws InvalidKeyException, NoSuchAlgorithmException {
+    if ((enrollmentInfo == null) || (masterKey == null) || (signingKey == null)) {
+      throw new NullPointerException();
+    }
+
+    if (!Arrays.equals(enrollmentInfo.getDeviceMasterKeyHash().toByteArray(),
+        getMasterKeyHash(masterKey))) {
+      throw new IllegalArgumentException("DeviceMasterKeyHash not set correctly");
+    }
+
+    // First create the inner message, which is basically a self-signed certificate
+    SigType sigType =
+        KeyEncoding.isLegacyPrivateKey(signingKey) ? LEGACY_INNER_SIG_TYPE : INNER_SIG_TYPE;
+    SecureMessage innerMsg = new SecureMessageBuilder()
+        .setVerificationKeyId(enrollmentInfo.getUserPublicKey().toByteArray())
+        .buildSignedCleartextMessage(signingKey, sigType, enrollmentInfo.toByteArray());
+
+    // Next create the outer message, which uses the newly exchanged master key to signcrypt
+    SecureMessage outerMsg = new SecureMessageBuilder()
+        .setVerificationKeyId(new byte[] {})  // Empty
+        .setPublicMetadata(GcmMetadata.newBuilder()
+            .setType(PayloadType.ENROLLMENT.getType())
+            .setVersion(SecureGcmConstants.SECURE_GCM_VERSION)
+            .build()
+            .toByteArray())
+        .buildSignCryptedMessage(
+            masterKey, OUTER_SIG_TYPE, masterKey, OUTER_ENC_TYPE, innerMsg.toByteArray());
+    return outerMsg.toByteArray();
+  }
+
+  /**
+   * Used by the server to decrypt the client's enrollment request.
+   * @param enrollmentMessage generated by the client's call to
+   *        {@link #encryptEnrollmentMessage(GcmDeviceInfo, SecretKey, PrivateKey)}
+   * @param masterKey the shared key derived from the key agreement
+   * @return the client's enrollment request data
+   * @throws SignatureException if {@code enrollmentMessage} is malformed or has been tampered with
+   * @throws InvalidKeyException if {@code masterKey} is the wrong type
+   */
+  public static GcmDeviceInfo decryptEnrollmentMessage(
+      byte[] enrollmentMessage, SecretKey masterKey, boolean isLegacy)
+      throws SignatureException, InvalidKeyException, NoSuchAlgorithmException {
+    if ((enrollmentMessage == null) || (masterKey == null)) {
+      throw new NullPointerException();
+    }
+
+    HeaderAndBody outerHeaderAndBody;
+    GcmMetadata outerMetadata;
+    HeaderAndBody innerHeaderAndBody;
+    byte[] encodedUserPublicKey;
+    GcmDeviceInfo enrollmentInfo;
+    try {
+      SecureMessage outerMsg = SecureMessage.parseFrom(enrollmentMessage);
+      outerHeaderAndBody = SecureMessageParser.parseSignCryptedMessage(
+          outerMsg, masterKey, OUTER_SIG_TYPE, masterKey, OUTER_ENC_TYPE);
+      outerMetadata = GcmMetadata.parseFrom(outerHeaderAndBody.getHeader().getPublicMetadata());
+
+      SecureMessage innerMsg = SecureMessage.parseFrom(outerHeaderAndBody.getBody());
+      encodedUserPublicKey = SecureMessageParser.getUnverifiedHeader(innerMsg)
+          .getVerificationKeyId().toByteArray();
+      PublicKey userPublicKey = KeyEncoding.parseUserPublicKey(encodedUserPublicKey);
+      SigType sigType = isLegacy ? LEGACY_INNER_SIG_TYPE : INNER_SIG_TYPE;
+      innerHeaderAndBody = SecureMessageParser.parseSignedCleartextMessage(
+          innerMsg, userPublicKey, sigType);
+      enrollmentInfo = GcmDeviceInfo.parseFrom(innerHeaderAndBody.getBody());
+    } catch (InvalidProtocolBufferException e) {
+      throw new SignatureException(e);
+    } catch (InvalidKeySpecException e) {
+      throw new SignatureException(e);
+    }
+
+    boolean verified =
+           (outerMetadata.getType() == PayloadType.ENROLLMENT.getType())
+        && (outerMetadata.getVersion() <= SecureGcmConstants.SECURE_GCM_VERSION)
+        && outerHeaderAndBody.getHeader().getVerificationKeyId().isEmpty()
+        && innerHeaderAndBody.getHeader().getPublicMetadata().isEmpty()
+        // Verify the encoded public key we used matches the encoded public key key being enrolled
+        && Arrays.equals(encodedUserPublicKey, enrollmentInfo.getUserPublicKey().toByteArray())
+        && Arrays.equals(getMasterKeyHash(masterKey),
+            enrollmentInfo.getDeviceMasterKeyHash().toByteArray());
+
+    if (verified) {
+      return enrollmentInfo;
+    }
+    throw new SignatureException();
+  }
+
+  static byte[] sha256(byte[] input) {
+    try {
+      MessageDigest sha256 = MessageDigest.getInstance("SHA-256");
+      return sha256.digest(input);
+    } catch (NoSuchAlgorithmException e) {
+      throw new RuntimeException(e);  // Shouldn't happen
+    }
+  }
+}
diff --git a/src/main/java/com/google/security/cryptauth/lib/securegcm/HandshakeException.java b/src/main/java/com/google/security/cryptauth/lib/securegcm/HandshakeException.java
new file mode 100644
index 0000000..bb5fffc
--- /dev/null
+++ b/src/main/java/com/google/security/cryptauth/lib/securegcm/HandshakeException.java
@@ -0,0 +1,32 @@
+/* Copyright 2018 Google LLC
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.google.security.cryptauth.lib.securegcm;
+
+/**
+ * Represents an unrecoverable error that has occurred during the handshake procedure.
+ */
+public class HandshakeException extends Exception {
+  public HandshakeException(String message) {
+    super(message);
+  }
+
+  public HandshakeException(Exception e) {
+    super(e);
+  }
+
+  public HandshakeException(String message, Exception e) {
+    super(message, e);
+  }
+}
diff --git a/src/main/java/com/google/security/cryptauth/lib/securegcm/KeyEncoding.java b/src/main/java/com/google/security/cryptauth/lib/securegcm/KeyEncoding.java
new file mode 100644
index 0000000..9690a89
--- /dev/null
+++ b/src/main/java/com/google/security/cryptauth/lib/securegcm/KeyEncoding.java
@@ -0,0 +1,171 @@
+/* Copyright 2018 Google LLC
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.google.security.cryptauth.lib.securegcm;
+
+import com.google.protobuf.InvalidProtocolBufferException;
+import com.google.security.cryptauth.lib.securemessage.PublicKeyProtoUtil;
+import com.google.security.cryptauth.lib.securemessage.SecureMessageProto.GenericPublicKey;
+import java.security.KeyFactory;
+import java.security.NoSuchAlgorithmException;
+import java.security.PrivateKey;
+import java.security.PublicKey;
+import java.security.interfaces.ECPrivateKey;
+import java.security.interfaces.ECPublicKey;
+import java.security.spec.InvalidKeySpecException;
+import java.security.spec.PKCS8EncodedKeySpec;
+import javax.crypto.SecretKey;
+import javax.crypto.interfaces.DHPrivateKey;
+import javax.crypto.spec.SecretKeySpec;
+
+/**
+ * Utility class for encoding and parsing keys used by SecureGcm.
+ */
+public class KeyEncoding {
+  private KeyEncoding() {} // Do not instantiate
+
+  private static boolean simulateLegacyCryptoRequired = false;
+
+  /**
+   * The JCA algorithm name to use when encoding/decoding symmetric keys.
+   */
+  static final String SYMMETRIC_KEY_ENCODING_ALG = "AES";
+
+  public static byte[] encodeMasterKey(SecretKey masterKey) {
+    return masterKey.getEncoded();
+  }
+
+  public static SecretKey parseMasterKey(byte[] encodedMasterKey) {
+    return new SecretKeySpec(encodedMasterKey, SYMMETRIC_KEY_ENCODING_ALG);
+  }
+
+  public static byte[] encodeUserPublicKey(PublicKey pk) {
+    return encodePublicKey(pk);
+  }
+
+  public static byte[] encodeUserPrivateKey(PrivateKey sk) {
+    return sk.getEncoded();
+  }
+
+  public static PrivateKey parseUserPrivateKey(byte[] encodedPrivateKey, boolean isLegacy)
+      throws InvalidKeySpecException {
+    PKCS8EncodedKeySpec keySpec = new PKCS8EncodedKeySpec(encodedPrivateKey);
+    if (isLegacy) {
+      return getRsaKeyFactory().generatePrivate(keySpec);
+    }
+    return getEcKeyFactory().generatePrivate(keySpec);
+  }
+
+  public static PublicKey parseUserPublicKey(byte[] keyBytes) throws InvalidKeySpecException {
+    return parsePublicKey(keyBytes);
+  }
+
+  public static byte[] encodeKeyAgreementPublicKey(PublicKey pk) {
+    return encodePublicKey(pk);
+  }
+
+  public static PublicKey parseKeyAgreementPublicKey(byte[] keyBytes)
+      throws InvalidKeySpecException {
+    return parsePublicKey(keyBytes);
+  }
+
+  public static byte[] encodeKeyAgreementPrivateKey(PrivateKey sk) {
+    if (isLegacyPrivateKey(sk)) {
+      return PublicKeyProtoUtil.encodeDh2048PrivateKey((DHPrivateKey) sk);
+    }
+    return sk.getEncoded();
+  }
+
+  public static PrivateKey parseKeyAgreementPrivateKey(byte[] keyBytes, boolean isLegacy)
+      throws InvalidKeySpecException {
+    if (isLegacy) {
+      return PublicKeyProtoUtil.parseDh2048PrivateKey(keyBytes);
+    }
+    PKCS8EncodedKeySpec keySpec = new PKCS8EncodedKeySpec(keyBytes);
+    return getEcKeyFactory().generatePrivate(keySpec);
+  }
+
+  public static byte[] encodeSigningPublicKey(PublicKey pk) {
+    return encodePublicKey(pk);
+  }
+
+  public static PublicKey parseSigningPublicKey(byte[] keyBytes) throws InvalidKeySpecException {
+    return parsePublicKey(keyBytes);
+  }
+
+  public static byte[] encodeSigningPrivateKey(PrivateKey sk) {
+    return sk.getEncoded();
+  }
+
+  public static PrivateKey parseSigningPrivateKey(byte[] keyBytes) throws InvalidKeySpecException {
+    PKCS8EncodedKeySpec keySpec = new PKCS8EncodedKeySpec(keyBytes);
+    return getEcKeyFactory().generatePrivate(keySpec);
+  }
+
+  public static boolean isLegacyPublicKey(PublicKey pk) {
+    if (pk instanceof ECPublicKey) {
+      return false;
+    }
+    return true;
+  }
+
+  public static boolean isLegacyPrivateKey(PrivateKey sk) {
+    if (sk instanceof ECPrivateKey) {
+      return false;
+    }
+    return true;
+  }
+
+  public static boolean isLegacyCryptoRequired() {
+    return PublicKeyProtoUtil.isLegacyCryptoRequired() || simulateLegacyCryptoRequired;
+  }
+
+  /**
+   * When testing, use this to force {@link #isLegacyCryptoRequired()} to return {@code true}
+   */
+  // @VisibleForTesting
+  public static void setSimulateLegacyCrypto(boolean forceLegacy) {
+    simulateLegacyCryptoRequired = forceLegacy;
+  }
+
+  private static byte[] encodePublicKey(PublicKey pk) {
+    return PublicKeyProtoUtil.encodePublicKey(pk).toByteArray();
+  }
+
+  private static PublicKey parsePublicKey(byte[] keyBytes) throws InvalidKeySpecException {
+    try {
+      return PublicKeyProtoUtil.parsePublicKey(GenericPublicKey.parseFrom(keyBytes));
+    } catch (InvalidProtocolBufferException e) {
+      throw new InvalidKeySpecException("Unable to parse GenericPublicKey", e);
+    } catch (IllegalArgumentException e) {
+      throw new InvalidKeySpecException("Unable to parse GenericPublicKey", e);
+    }
+  }
+
+  static KeyFactory getEcKeyFactory() {
+    try {
+      return KeyFactory.getInstance("EC");
+    } catch (NoSuchAlgorithmException e) {
+      throw new RuntimeException(e);  // No ECDH provider available
+    }
+  }
+
+  static KeyFactory getRsaKeyFactory() {
+    try {
+      return KeyFactory.getInstance("RSA");
+    } catch (NoSuchAlgorithmException e) {
+      throw new RuntimeException(e);  // No RSA provider available
+    }
+  }
+}
diff --git a/src/main/java/com/google/security/cryptauth/lib/securegcm/SecureGcmConstants.java b/src/main/java/com/google/security/cryptauth/lib/securegcm/SecureGcmConstants.java
new file mode 100644
index 0000000..8482628
--- /dev/null
+++ b/src/main/java/com/google/security/cryptauth/lib/securegcm/SecureGcmConstants.java
@@ -0,0 +1,49 @@
+/* Copyright 2018 Google LLC
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.google.security.cryptauth.lib.securegcm;
+
+/**
+ * A container for GCM related constants used by SecureGcm channels.
+ */
+public final class SecureGcmConstants {
+  private SecureGcmConstants() {} // Do not instantiate
+
+  public static final int SECURE_GCM_VERSION = 1;
+
+  /**
+   * The GCM sender identity used by this library (GMSCore).
+   */
+  public static final String SENDER_ID = "745476177629";
+
+  /**
+   * The key used for indexing the GCM {@link TransportCryptoOps.Payload} within {@code AppData}.
+   */
+  public static final String MESSAGE_KEY = "P";
+
+  /**
+   * The origin that should be use for GCM device enrollments.
+   */
+  public static final String GOOGLE_ORIGIN = "google.com";
+
+  /**
+   * The origin that should be use for GCM Legacy android device enrollments.
+   */
+  public static final String LEGACY_ANDROID_ORIGIN = "c.g.a.gms";
+
+  /**
+   * The name of the protocol this library speaks.
+   */
+  public static final String PROTOCOL_TYPE_NAME = "gcmV1";
+}
diff --git a/src/main/java/com/google/security/cryptauth/lib/securegcm/TransportCryptoOps.java b/src/main/java/com/google/security/cryptauth/lib/securegcm/TransportCryptoOps.java
new file mode 100644
index 0000000..a22edc4
--- /dev/null
+++ b/src/main/java/com/google/security/cryptauth/lib/securegcm/TransportCryptoOps.java
@@ -0,0 +1,268 @@
+/* Copyright 2018 Google LLC
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.google.security.cryptauth.lib.securegcm;
+
+import com.google.protobuf.InvalidProtocolBufferException;
+import com.google.security.cryptauth.lib.securegcm.SecureGcmProto.GcmMetadata;
+import com.google.security.cryptauth.lib.securemessage.CryptoOps.EncType;
+import com.google.security.cryptauth.lib.securemessage.CryptoOps.SigType;
+import com.google.security.cryptauth.lib.securemessage.SecureMessageBuilder;
+import com.google.security.cryptauth.lib.securemessage.SecureMessageParser;
+import com.google.security.cryptauth.lib.securemessage.SecureMessageProto.HeaderAndBody;
+import com.google.security.cryptauth.lib.securemessage.SecureMessageProto.SecureMessage;
+import java.security.InvalidKeyException;
+import java.security.KeyPair;
+import java.security.NoSuchAlgorithmException;
+import java.security.PrivateKey;
+import java.security.PublicKey;
+import java.security.SignatureException;
+import java.security.interfaces.ECPublicKey;
+import java.security.interfaces.RSAPublicKey;
+import javax.crypto.SecretKey;
+
+/**
+ * Utility class for implementing a secure transport for GCM messages.
+ */
+public class TransportCryptoOps {
+  private TransportCryptoOps() {} // Do not instantiate
+
+  /**
+   * A type safe version of the {@link SecureGcmProto} {@code Type} codes.
+   */
+  public enum PayloadType {
+    ENROLLMENT(SecureGcmProto.Type.ENROLLMENT),
+    TICKLE(SecureGcmProto.Type.TICKLE),
+    TX_REQUEST(SecureGcmProto.Type.TX_REQUEST),
+    TX_REPLY(SecureGcmProto.Type.TX_REPLY),
+    TX_SYNC_REQUEST(SecureGcmProto.Type.TX_SYNC_REQUEST),
+    TX_SYNC_RESPONSE(SecureGcmProto.Type.TX_SYNC_RESPONSE),
+    TX_PING(SecureGcmProto.Type.TX_PING),
+    DEVICE_INFO_UPDATE(SecureGcmProto.Type.DEVICE_INFO_UPDATE),
+    TX_CANCEL_REQUEST(SecureGcmProto.Type.TX_CANCEL_REQUEST),
+    LOGIN_NOTIFICATION(SecureGcmProto.Type.LOGIN_NOTIFICATION),
+    PROXIMITYAUTH_PAIRING(SecureGcmProto.Type.PROXIMITYAUTH_PAIRING),
+    GCMV1_IDENTITY_ASSERTION(SecureGcmProto.Type.GCMV1_IDENTITY_ASSERTION),
+    DEVICE_TO_DEVICE_RESPONDER_HELLO_PAYLOAD(
+        SecureGcmProto.Type.DEVICE_TO_DEVICE_RESPONDER_HELLO_PAYLOAD),
+    DEVICE_TO_DEVICE_MESSAGE(SecureGcmProto.Type.DEVICE_TO_DEVICE_MESSAGE),
+    DEVICE_PROXIMITY_CALLBACK(SecureGcmProto.Type.DEVICE_PROXIMITY_CALLBACK),
+    UNLOCK_KEY_SIGNED_CHALLENGE(SecureGcmProto.Type.UNLOCK_KEY_SIGNED_CHALLENGE);
+
+    private final SecureGcmProto.Type type;
+    PayloadType(SecureGcmProto.Type type) {
+      this.type = type;
+    }
+
+    public SecureGcmProto.Type getType() {
+      return this.type;
+    }
+
+    public static PayloadType valueOf(SecureGcmProto.Type type) {
+      return PayloadType.valueOf(type.getNumber());
+    }
+
+    public static PayloadType valueOf(int type) {
+      for (PayloadType payloadType : PayloadType.values()) {
+        if (payloadType.getType().getNumber() == type) {
+          return payloadType;
+        }
+      }
+      throw new IllegalArgumentException("Unsupported payload type: " + type);
+    }
+  }
+
+  /**
+   * Encapsulates a {@link PayloadType} specifier, and a corresponding raw {@code message} payload.
+   */
+  public static class Payload {
+    private final PayloadType payloadType;
+    private final byte[] message;
+
+    public Payload(PayloadType payloadType, byte[] message) {
+      if ((payloadType == null) || (message == null)) {
+        throw new NullPointerException();
+      }
+      this.payloadType = payloadType;
+      this.message = message;
+    }
+
+    public PayloadType getPayloadType() {
+      return payloadType;
+    }
+
+    public byte[] getMessage() {
+      return message;
+    }
+  }
+
+  /**
+   * Used by the the server-side to send a secure {@link Payload} to the client.
+   *
+   * @param masterKey used to signcrypt the {@link Payload}
+   * @param keyHandle the name by which the client refers to the specified {@code masterKey}
+   */
+  public static byte[] signcryptServerMessage(
+      Payload payload, SecretKey masterKey, byte[] keyHandle)
+      throws InvalidKeyException, NoSuchAlgorithmException {
+    if ((payload == null) || (masterKey == null) || (keyHandle == null)) {
+      throw new NullPointerException();
+    }
+    return new SecureMessageBuilder()
+        .setVerificationKeyId(keyHandle)
+        .setPublicMetadata(GcmMetadata.newBuilder()
+            .setType(payload.getPayloadType().getType())
+            .setVersion(SecureGcmConstants.SECURE_GCM_VERSION)
+            .build()
+            .toByteArray())
+        .buildSignCryptedMessage(
+            masterKey,
+            SigType.HMAC_SHA256,
+            masterKey,
+            EncType.AES_256_CBC,
+            payload.getMessage())
+        .toByteArray();
+  }
+
+  /**
+   * Extracts the {@code keyHandle} from a {@code signcryptedMessage}.
+   *
+   * @see #signcryptServerMessage(Payload, SecretKey, byte[])
+   */
+  public static byte[] getKeyHandleFor(byte[] signcryptedServerMessage)
+      throws InvalidProtocolBufferException  {
+    if (signcryptedServerMessage == null) {
+      throw new NullPointerException();
+    }
+    SecureMessage secmsg = SecureMessage.parseFrom(signcryptedServerMessage);
+    return SecureMessageParser.getUnverifiedHeader(secmsg).getVerificationKeyId().toByteArray();
+  }
+
+  /**
+   * Used by a client to recover a secure {@link Payload} sent by the server-side.
+   *
+   * @see #getKeyHandleFor(byte[])
+   * @see #signcryptServerMessage(Payload, SecretKey, byte[])
+   */
+  public static Payload verifydecryptServerMessage(
+      byte[] signcryptedServerMessage, SecretKey masterKey)
+      throws SignatureException, InvalidKeyException, NoSuchAlgorithmException {
+    if ((signcryptedServerMessage == null) || (masterKey == null)) {
+      throw new NullPointerException();
+    }
+    try {
+      SecureMessage secmsg = SecureMessage.parseFrom(signcryptedServerMessage);
+      HeaderAndBody parsed = SecureMessageParser.parseSignCryptedMessage(
+          secmsg,
+          masterKey,
+          SigType.HMAC_SHA256,
+          masterKey,
+          EncType.AES_256_CBC);
+      GcmMetadata metadata = GcmMetadata.parseFrom(parsed.getHeader().getPublicMetadata());
+      if (metadata.getVersion() > SecureGcmConstants.SECURE_GCM_VERSION) {
+        throw new SignatureException("Unsupported protocol version");
+      }
+      return new Payload(PayloadType.valueOf(metadata.getType()), parsed.getBody().toByteArray());
+    } catch (InvalidProtocolBufferException | IllegalArgumentException e) {
+      throw new SignatureException(e);
+    }
+  }
+
+  /**
+   * Used by the the client-side to send a secure {@link Payload} to the client.
+   *
+   * @param userKeyPair used to sign the {@link Payload}. In particular, the {@link PrivateKey}
+   *   portion is used for signing, and (the {@link PublicKey} portion is sent to the server.
+   * @param masterKey used to encrypt the {@link Payload}
+   */
+  public static byte[] signcryptClientMessage(
+      Payload payload, KeyPair userKeyPair, SecretKey masterKey)
+      throws InvalidKeyException, NoSuchAlgorithmException {
+    if ((payload == null) || (masterKey == null)) {
+      throw new NullPointerException();
+    }
+
+    PublicKey userPublicKey = userKeyPair.getPublic();
+    PrivateKey userPrivateKey = userKeyPair.getPrivate();
+
+    return new SecureMessageBuilder()
+        .setVerificationKeyId(KeyEncoding.encodeUserPublicKey(userPublicKey))
+        .setPublicMetadata(GcmMetadata.newBuilder()
+            .setType(payload.getPayloadType().getType())
+            .setVersion(SecureGcmConstants.SECURE_GCM_VERSION)
+            .build()
+            .toByteArray())
+        .buildSignCryptedMessage(
+            userPrivateKey,
+            getSigTypeFor(userPublicKey),
+            masterKey,
+            EncType.AES_256_CBC,
+            payload.getMessage())
+        .toByteArray();
+  }
+
+  /**
+   * Used by the server-side to recover a secure {@link Payload} sent by a client.
+   *
+   * @see #getEncodedUserPublicKeyFor(byte[])
+   * @see #signcryptClientMessage(Payload, KeyPair, SecretKey)
+   */
+  public static Payload verifydecryptClientMessage(
+      byte[] signcryptedClientMessage, PublicKey userPublicKey, SecretKey masterKey)
+      throws SignatureException, InvalidKeyException, NoSuchAlgorithmException {
+    if ((signcryptedClientMessage == null) || (masterKey == null)) {
+      throw new NullPointerException();
+    }
+    try {
+      SecureMessage secmsg = SecureMessage.parseFrom(signcryptedClientMessage);
+      HeaderAndBody parsed = SecureMessageParser.parseSignCryptedMessage(
+          secmsg,
+          userPublicKey,
+          getSigTypeFor(userPublicKey),
+          masterKey,
+          EncType.AES_256_CBC);
+      GcmMetadata metadata = GcmMetadata.parseFrom(parsed.getHeader().getPublicMetadata());
+      if (metadata.getVersion() > SecureGcmConstants.SECURE_GCM_VERSION) {
+        throw new SignatureException("Unsupported protocol version");
+      }
+      return new Payload(PayloadType.valueOf(metadata.getType()), parsed.getBody().toByteArray());
+    } catch (InvalidProtocolBufferException | IllegalArgumentException e) {
+      throw new SignatureException(e);
+    }
+  }
+
+  /**
+   * Extracts an encoded {@code userPublicKey} from a {@code signcryptedClientMessage}.
+   *
+   * @see #signcryptClientMessage(Payload, KeyPair, SecretKey)
+   */
+  public static byte[] getEncodedUserPublicKeyFor(byte[] signcryptedClientMessage)
+      throws InvalidProtocolBufferException  {
+    if (signcryptedClientMessage == null) {
+      throw new NullPointerException();
+    }
+    SecureMessage secmsg = SecureMessage.parseFrom(signcryptedClientMessage);
+    return SecureMessageParser.getUnverifiedHeader(secmsg).getVerificationKeyId().toByteArray();
+  }
+
+  private static SigType getSigTypeFor(PublicKey userPublicKey) throws InvalidKeyException {
+    if (userPublicKey instanceof ECPublicKey) {
+      return SigType.ECDSA_P256_SHA256;
+    } else if (userPublicKey instanceof RSAPublicKey) {
+      return SigType.RSA2048_SHA256;
+    } else {
+      throw new InvalidKeyException("Unsupported key type");
+    }
+  }
+}
diff --git a/src/main/java/com/google/security/cryptauth/lib/securegcm/Ukey2Handshake.java b/src/main/java/com/google/security/cryptauth/lib/securegcm/Ukey2Handshake.java
new file mode 100644
index 0000000..0d01c9a
--- /dev/null
+++ b/src/main/java/com/google/security/cryptauth/lib/securegcm/Ukey2Handshake.java
@@ -0,0 +1,1041 @@
+/* Copyright 2018 Google LLC
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.google.security.cryptauth.lib.securegcm;
+
+import com.google.protobuf.ByteString;
+import com.google.protobuf.InvalidProtocolBufferException;
+import com.google.security.cryptauth.lib.securegcm.UkeyProto.Ukey2Alert;
+import com.google.security.cryptauth.lib.securegcm.UkeyProto.Ukey2ClientFinished;
+import com.google.security.cryptauth.lib.securegcm.UkeyProto.Ukey2ClientInit;
+import com.google.security.cryptauth.lib.securegcm.UkeyProto.Ukey2ClientInit.CipherCommitment;
+import com.google.security.cryptauth.lib.securegcm.UkeyProto.Ukey2Message;
+import com.google.security.cryptauth.lib.securegcm.UkeyProto.Ukey2ServerInit;
+import com.google.security.cryptauth.lib.securemessage.CryptoOps;
+import com.google.security.cryptauth.lib.securemessage.PublicKeyProtoUtil;
+import com.google.security.cryptauth.lib.securemessage.SecureMessageProto.GenericPublicKey;
+import java.io.ByteArrayOutputStream;
+import java.io.IOException;
+import java.io.UnsupportedEncodingException;
+import java.security.InvalidKeyException;
+import java.security.KeyPair;
+import java.security.MessageDigest;
+import java.security.NoSuchAlgorithmException;
+import java.security.PublicKey;
+import java.security.SecureRandom;
+import java.security.spec.InvalidKeySpecException;
+import java.util.Arrays;
+import java.util.HashMap;
+import java.util.List;
+import javax.annotation.Nullable;
+import javax.crypto.SecretKey;
+import javax.crypto.spec.SecretKeySpec;
+
+/**
+ * Implements UKEY2 and produces a {@link D2DConnectionContext}.
+ *
+ * <p>Client Usage:
+ * <code>
+ * try {
+ *   Ukey2Handshake client = Ukey2Handshake.forInitiator(HandshakeCipher.P256_SHA512);
+ *   byte[] handshakeMessage;
+ *
+ *   // Message 1 (Client Init)
+ *   handshakeMessage = client.getNextHandshakeMessage();
+ *   sendMessageToServer(handshakeMessage);
+ *
+ *   // Message 2 (Server Init)
+ *   handshakeMessage = receiveMessageFromServer();
+ *   client.parseHandshakeMessage(handshakeMessage);
+ *
+ *   // Message 3 (Client Finish)
+ *   handshakeMessage = client.getNextHandshakeMessage();
+ *   sendMessageToServer(handshakeMessage);
+ *
+ *   // Get the auth string
+ *   byte[] clientAuthString = client.getVerificationString(STRING_LENGTH);
+ *   showStringToUser(clientAuthString);
+ *
+ *   // Using out-of-band channel, verify auth string, then call:
+ *   client.verifyHandshake();
+ *
+ *   // Make a connection context
+ *   D2DConnectionContext clientContext = client.toConnectionContext();
+ * } catch (AlertException e) {
+ *   log(e.getMessage);
+ *   sendMessageToServer(e.getAlertMessageToSend());
+ * } catch (HandshakeException e) {
+ *   log(e);
+ *   // terminate handshake
+ * }
+ * </code>
+ *
+ * <p>Server Usage:
+ * <code>
+ * try {
+ *   Ukey2Handshake server = Ukey2Handshake.forResponder(HandshakeCipher.P256_SHA512);
+ *   byte[] handshakeMessage;
+ *
+ *   // Message 1 (Client Init)
+ *   handshakeMessage = receiveMessageFromClient();
+ *   server.parseHandshakeMessage(handshakeMessage);
+ *
+ *   // Message 2 (Server Init)
+ *   handshakeMessage = server.getNextHandshakeMessage();
+ *   sendMessageToServer(handshakeMessage);
+ *
+ *   // Message 3 (Client Finish)
+ *   handshakeMessage = receiveMessageFromClient();
+ *   server.parseHandshakeMessage(handshakeMessage);
+ *
+ *   // Get the auth string
+ *   byte[] serverAuthString = server.getVerificationString(STRING_LENGTH);
+ *   showStringToUser(serverAuthString);
+ *
+ *   // Using out-of-band channel, verify auth string, then call:
+ *   server.verifyHandshake();
+ *
+ *   // Make a connection context
+ *   D2DConnectionContext serverContext = server.toConnectionContext();
+ * } catch (AlertException e) {
+ *   log(e.getMessage);
+ *   sendMessageToClient(e.getAlertMessageToSend());
+ * } catch (HandshakeException e) {
+ *   log(e);
+ *   // terminate handshake
+ * }
+ * </code>
+ */
+public class Ukey2Handshake {
+
+  /**
+   * Creates a {@link Ukey2Handshake} with a particular cipher that can be used by an initiator /
+   * client.
+   *
+   * @throws HandshakeException
+   */
+  public static Ukey2Handshake forInitiator(HandshakeCipher cipher) throws HandshakeException {
+    return new Ukey2Handshake(InternalState.CLIENT_START, cipher);
+  }
+
+  /**
+   * Creates a {@link Ukey2Handshake} with a particular cipher that can be used by an responder /
+   * server.
+   *
+   * @throws HandshakeException
+   */
+  public static Ukey2Handshake forResponder(HandshakeCipher cipher) throws HandshakeException {
+    return new Ukey2Handshake(InternalState.SERVER_START, cipher);
+  }
+
+  /**
+   * Handshake States. Meaning of states:
+   * <ul>
+   * <li>IN_PROGRESS: The handshake is in progress, caller should use
+   * {@link Ukey2Handshake#getNextHandshakeMessage()} and
+   * {@link Ukey2Handshake#parseHandshakeMessage(byte[])} to continue the handshake.
+   * <li>VERIFICATION_NEEDED: The handshake is complete, but pending verification of the
+   * authentication string. Clients should use {@link Ukey2Handshake#getVerificationString(int)} to
+   * get the verification string and use out-of-band methods to authenticate the handshake.
+   * <li>VERIFICATION_IN_PROGRESS: The handshake is complete, verification string has been
+   * generated, but has not been confirmed. After authenticating the handshake out-of-band, use
+   * {@link Ukey2Handshake#verifyHandshake()} to mark the handshake as verified.
+   * <li>FINISHED: The handshake is finished, and caller can use
+   * {@link Ukey2Handshake#toConnectionContext()} to produce a {@link D2DConnectionContext}.
+   * <li>ALREADY_USED: The handshake has already been used and should be discarded / garbage
+   * collected.
+   * <li>ERROR: The handshake produced an error and should be destroyed.
+   * </ul>
+   */
+  public enum State {
+    IN_PROGRESS,
+    VERIFICATION_NEEDED,
+    VERIFICATION_IN_PROGRESS,
+    FINISHED,
+    ALREADY_USED,
+    ERROR,
+  }
+
+  /**
+   * Currently implemented UKEY2 handshake ciphers. Each cipher is a tuple consisting of a key
+   * negotiation cipher and a hash function used for a commitment. Currently the ciphers are:
+   * <code>
+   *   +-----------------------------------------------------+
+   *   | Enum        | Key negotiation       | Hash function |
+   *   +-------------+-----------------------+---------------+
+   *   | P256_SHA512 | ECDH using NIST P-256 | SHA512        |
+   *   +-----------------------------------------------------+
+   * </code>
+   *
+   * <p>Note that these should correspond to values in device_to_device_messages.proto.
+   */
+  public enum HandshakeCipher {
+    P256_SHA512(UkeyProto.Ukey2HandshakeCipher.P256_SHA512);
+    // TODO(aczeskis): add CURVE25519_SHA512
+
+    private final UkeyProto.Ukey2HandshakeCipher value;
+
+    HandshakeCipher(UkeyProto.Ukey2HandshakeCipher value) {
+      // Make sure we only accept values that are valid as per the ukey protobuf.
+      // NOTE: Don't use switch statement on value, as that will trigger a bug. b/30682989.
+      if (value == UkeyProto.Ukey2HandshakeCipher.P256_SHA512) {
+          this.value = value;
+      } else {
+          throw new IllegalArgumentException("Unknown cipher value: " + value);
+      }
+    }
+
+    public UkeyProto.Ukey2HandshakeCipher getValue() {
+      return value;
+    }
+  }
+
+  /**
+   * If thrown, this exception contains information that should be sent on the wire. Specifically,
+   * the {@link #getAlertMessageToSend()} method returns a <code>byte[]</code> that communicates the
+   * error to the other party in the handshake. Meanwhile, the {@link #getMessage()} method can be
+   * used to get a log-able error message.
+   */
+  public static class AlertException extends Exception {
+    private final Ukey2Alert alertMessageToSend;
+
+    public AlertException(String alertMessageToLog, Ukey2Alert alertMessageToSend) {
+      super(alertMessageToLog);
+      this.alertMessageToSend = alertMessageToSend;
+    }
+
+    /**
+     * @return a message suitable for sending to other member of handshake.
+     */
+    public byte[] getAlertMessageToSend() {
+      return alertMessageToSend.toByteArray();
+    }
+  }
+
+  // Maximum version of the handshake supported by this class.
+  public static final int VERSION = 1;
+
+  // Random nonce is fixed at 32 bytes (as per go/ukey2).
+  private static final int NONCE_LENGTH_IN_BYTES = 32;
+
+  private static final String UTF_8 = "UTF-8";
+
+  // Currently, we only support one next protocol.
+  private static final String NEXT_PROTOCOL = "AES_256_CBC-HMAC_SHA256";
+
+  // Clients need to store a map of message 3's (client finishes) for each commitment.
+  private final HashMap<HandshakeCipher, byte[]> rawMessage3Map = new HashMap<>();
+
+  private final HandshakeCipher handshakeCipher;
+  private final HandshakeRole handshakeRole;
+  private InternalState handshakeState;
+  private final KeyPair ourKeyPair;
+  private PublicKey theirPublicKey;
+  private SecretKey derivedSecretKey;
+
+  // Servers need to store client commitments.
+  private byte[] theirCommitment;
+
+  // We store the raw messages sent for computing the authentication strings and next key.
+  private byte[] rawMessage1;
+  private byte[] rawMessage2;
+
+  // Enums for internal state machinery
+  private enum InternalState {
+    // Initiator/client state
+    CLIENT_START,
+    CLIENT_WAITING_FOR_SERVER_INIT,
+    CLIENT_AFTER_SERVER_INIT,
+
+    // Responder/server state
+    SERVER_START,
+    SERVER_AFTER_CLIENT_INIT,
+    SERVER_WAITING_FOR_CLIENT_FINISHED,
+
+    // Common completion state
+    HANDSHAKE_VERIFICATION_NEEDED,
+    HANDSHAKE_VERIFICATION_IN_PROGRESS,
+    HANDSHAKE_FINISHED,
+    HANDSHAKE_ALREADY_USED,
+    HANDSHAKE_ERROR,
+  }
+
+  // Helps us remember our role in the handshake
+  private enum HandshakeRole {
+    CLIENT,
+    SERVER
+  }
+
+  /**
+   * Never invoked directly. Caller should use {@link #forInitiator(HandshakeCipher)} or
+   * {@link #forResponder(HandshakeCipher)} instead.
+   *
+   * @throws HandshakeException if an unrecoverable error occurs and the connection should be shut
+   * down.
+   */
+  private Ukey2Handshake(InternalState state, HandshakeCipher cipher) throws HandshakeException {
+    if (cipher == null) {
+      throwIllegalArgumentException("Invalid handshake cipher");
+    }
+    this.handshakeCipher = cipher;
+
+    switch (state) {
+      case CLIENT_START:
+        handshakeRole = HandshakeRole.CLIENT;
+        break;
+      case SERVER_START:
+        handshakeRole = HandshakeRole.SERVER;
+        break;
+      default:
+        throwIllegalStateException("Invalid handshake state");
+        handshakeRole = null; // unreachable, but makes compiler happy
+    }
+    this.handshakeState = state;
+
+    this.ourKeyPair = genKeyPair(cipher);
+  }
+
+  /**
+   * Get the next handshake message suitable for sending on the wire.
+   *
+   * @throws HandshakeException if an unrecoverable error occurs and the connection should be shut
+   * down.
+   */
+  public byte[] getNextHandshakeMessage() throws HandshakeException {
+    switch (handshakeState) {
+      case CLIENT_START:
+        rawMessage1 = makeUkey2Message(Ukey2Message.Type.CLIENT_INIT, makeClientInitMessage());
+        handshakeState = InternalState.CLIENT_WAITING_FOR_SERVER_INIT;
+        return rawMessage1;
+
+      case SERVER_AFTER_CLIENT_INIT:
+        rawMessage2 = makeUkey2Message(Ukey2Message.Type.SERVER_INIT, makeServerInitMessage());
+        handshakeState = InternalState.SERVER_WAITING_FOR_CLIENT_FINISHED;
+        return rawMessage2;
+
+      case CLIENT_AFTER_SERVER_INIT:
+        // Make sure we have a message 3 for the chosen cipher.
+        if (!rawMessage3Map.containsKey(handshakeCipher)) {
+          throwIllegalStateException(
+              "Client state is CLIENT_AFTER_SERVER_INIT, and cipher is "
+                  + handshakeCipher
+                  + ", but no corresponding raw client finished message has been generated");
+        }
+        handshakeState = InternalState.HANDSHAKE_VERIFICATION_NEEDED;
+        return rawMessage3Map.get(handshakeCipher);
+
+      default:
+        throwIllegalStateException("Cannot get next message in state: " + handshakeState);
+        return null; // unreachable, but makes compiler happy
+    }
+  }
+
+  /**
+   * Returns an authentication string suitable for authenticating the handshake out-of-band. Note
+   * that the authentication string can be short (e.g., a 6 digit visual confirmation code). Note:
+   * this should only be called when the state returned byte {@link #getHandshakeState()} is
+   * {@link State#VERIFICATION_NEEDED}, which means this can only be called once.
+   *
+   * @param byteLength length of output in bytes. Min length is 1; max length is 32.
+   */
+  public byte[] getVerificationString(int byteLength) throws HandshakeException {
+    if (byteLength < 1 || byteLength > 32) {
+      throwIllegalArgumentException("Minimum length is 1 byte, max is 32 bytes");
+    }
+
+    if (handshakeState != InternalState.HANDSHAKE_VERIFICATION_NEEDED) {
+      throwIllegalStateException("Unexpected state: " + handshakeState);
+    }
+
+    try {
+      derivedSecretKey =
+          EnrollmentCryptoOps.doKeyAgreement(ourKeyPair.getPrivate(), theirPublicKey);
+    } catch (InvalidKeyException e) {
+      // unreachable in practice
+      throwHandshakeException(e);
+    }
+
+    ByteArrayOutputStream byteStream = new ByteArrayOutputStream();
+    try {
+      byteStream.write(rawMessage1);
+      byteStream.write(rawMessage2);
+    } catch (IOException e) {
+      // unreachable in practice
+      throwHandshakeException(e);
+    }
+    byte[] info = byteStream.toByteArray();
+
+    byte[] salt = null;
+
+    try {
+      salt = "UKEY2 v1 auth".getBytes(UTF_8);
+    } catch (UnsupportedEncodingException e) {
+      // unreachable in practice
+      throwHandshakeException(e);
+    }
+
+    byte[] authString = null;
+    try {
+      authString = CryptoOps.hkdf(derivedSecretKey, salt, info);
+    } catch (InvalidKeyException | NoSuchAlgorithmException e) {
+      // unreachable in practice
+      throwHandshakeException(e);
+    }
+
+    handshakeState = InternalState.HANDSHAKE_VERIFICATION_IN_PROGRESS;
+    return Arrays.copyOf(authString, byteLength);
+  }
+
+  /**
+   * Invoked to let handshake state machine know that caller has validated the authentication
+   * string obtained via {@link #getVerificationString(int)}; Note: this should only be called when
+   * the state returned byte {@link #getHandshakeState()} is {@link State#VERIFICATION_IN_PROGRESS}.
+   */
+  public void verifyHandshake() {
+    if (handshakeState != InternalState.HANDSHAKE_VERIFICATION_IN_PROGRESS) {
+      throwIllegalStateException("Unexpected state: " + handshakeState);
+    }
+    handshakeState = InternalState.HANDSHAKE_FINISHED;
+  }
+
+  /**
+   * Parses the given handshake message.
+   * @throws AlertException if an error occurs that should be sent to other party.
+   * @throws HandshakeException in an error occurs and the connection should be torn down.
+   */
+  public void parseHandshakeMessage(byte[] handshakeMessage)
+      throws AlertException, HandshakeException {
+    switch (handshakeState) {
+      case SERVER_START:
+        parseMessage1(handshakeMessage);
+        handshakeState = InternalState.SERVER_AFTER_CLIENT_INIT;
+        break;
+
+      case CLIENT_WAITING_FOR_SERVER_INIT:
+        parseMessage2(handshakeMessage);
+        handshakeState = InternalState.CLIENT_AFTER_SERVER_INIT;
+        break;
+
+      case SERVER_WAITING_FOR_CLIENT_FINISHED:
+        parseMessage3(handshakeMessage);
+        handshakeState = InternalState.HANDSHAKE_VERIFICATION_NEEDED;
+        break;
+
+      default:
+        throwIllegalStateException("Cannot parse message in state " + handshakeState);
+    }
+  }
+
+  /**
+   * Returns the current state of the handshake. See {@link State}.
+   */
+  public State getHandshakeState() {
+    switch (handshakeState) {
+      case CLIENT_START:
+      case CLIENT_WAITING_FOR_SERVER_INIT:
+      case CLIENT_AFTER_SERVER_INIT:
+      case SERVER_START:
+      case SERVER_WAITING_FOR_CLIENT_FINISHED:
+      case SERVER_AFTER_CLIENT_INIT:
+        // fallback intended -- these are all in-progress states
+        return State.IN_PROGRESS;
+
+      case HANDSHAKE_ERROR:
+        return State.ERROR;
+
+      case HANDSHAKE_VERIFICATION_NEEDED:
+        return State.VERIFICATION_NEEDED;
+
+      case HANDSHAKE_VERIFICATION_IN_PROGRESS:
+        return State.VERIFICATION_IN_PROGRESS;
+
+      case HANDSHAKE_FINISHED:
+        return State.FINISHED;
+
+      case HANDSHAKE_ALREADY_USED:
+        return State.ALREADY_USED;
+
+      default:
+        // unreachable in practice
+        throwIllegalStateException("Unknown state");
+        return null; // really unreachable, but makes compiler happy
+    }
+  }
+
+  /**
+   * Can be called to generate a {@link D2DConnectionContext}. Note: this should only be called
+   * when the state returned byte {@link #getHandshakeState()} is {@link State#FINISHED}.
+   *
+   * @throws HandshakeException
+   */
+  public D2DConnectionContext toConnectionContext() throws HandshakeException {
+    switch (handshakeState) {
+      case HANDSHAKE_ERROR:
+        throwIllegalStateException("Cannot make context; handshake had error");
+        return null; // makes linter happy
+      case HANDSHAKE_ALREADY_USED:
+        throwIllegalStateException("Cannot reuse handshake context; is has already been used");
+        return null; // makes linter happy
+      case HANDSHAKE_VERIFICATION_NEEDED:
+        throwIllegalStateException("Handshake not verified, cannot create context");
+        return null; // makes linter happy
+      case HANDSHAKE_FINISHED:
+        // We're done, okay to return a context
+        break;
+      default:
+        // unreachable in practice
+        throwIllegalStateException("Handshake is not complete; cannot create connection context");
+    }
+
+    if (derivedSecretKey == null) {
+      throwIllegalStateException("Unexpected state error: derived key is null");
+    }
+
+    ByteArrayOutputStream byteStream = new ByteArrayOutputStream();
+    try {
+      byteStream.write(rawMessage1);
+      byteStream.write(rawMessage2);
+    } catch (IOException e) {
+      // unreachable in practice
+      throwHandshakeException(e);
+    }
+    byte[] info = byteStream.toByteArray();
+
+    byte[] salt = null;
+    try {
+      salt = "UKEY2 v1 next".getBytes(UTF_8);
+    } catch (UnsupportedEncodingException e) {
+      // unreachable
+      throwHandshakeException(e);
+    }
+
+    SecretKey nextProtocolKey = null;
+    try {
+      nextProtocolKey = new SecretKeySpec(CryptoOps.hkdf(derivedSecretKey, salt, info), "AES");
+    } catch (InvalidKeyException | NoSuchAlgorithmException e) {
+      // unreachable in practice
+      throwHandshakeException(e);
+    }
+
+    SecretKey clientKey = null;
+    SecretKey serverKey = null;
+    try {
+      clientKey = D2DCryptoOps.deriveNewKeyForPurpose(nextProtocolKey, "client");
+      serverKey = D2DCryptoOps.deriveNewKeyForPurpose(nextProtocolKey, "server");
+    } catch (InvalidKeyException | NoSuchAlgorithmException e) {
+      // unreachable in practice
+      throwHandshakeException(e);
+    }
+
+    handshakeState = InternalState.HANDSHAKE_ALREADY_USED;
+
+    return new D2DConnectionContextV1(
+        handshakeRole == HandshakeRole.CLIENT ? clientKey : serverKey,
+        handshakeRole == HandshakeRole.CLIENT ? serverKey : clientKey,
+        0 /* initial encode sequence number */,
+        0 /* initial decode sequence number */);
+  }
+
+  /**
+   * Generates the byte[] encoding of a {@link Ukey2ClientInit} message.
+   *
+   * @throws HandshakeException
+   */
+  private byte[] makeClientInitMessage() throws HandshakeException {
+    Ukey2ClientInit.Builder clientInit = Ukey2ClientInit.newBuilder();
+    clientInit.setVersion(VERSION);
+    clientInit.setRandom(ByteString.copyFrom(generateRandomNonce()));
+    clientInit.setNextProtocol(NEXT_PROTOCOL);
+
+    // At the moment, we only support one cipher
+    clientInit.addCipherCommitments(generateP256SHA512Commitment());
+
+    return clientInit.build().toByteArray();
+  }
+
+  /**
+   * Generates the byte[] encoding of a {@link Ukey2ServerInit} message.
+   */
+  private byte[] makeServerInitMessage() {
+    Ukey2ServerInit.Builder serverInit = Ukey2ServerInit.newBuilder();
+    serverInit.setVersion(VERSION);
+    serverInit.setRandom(ByteString.copyFrom(generateRandomNonce()));
+    serverInit.setHandshakeCipher(handshakeCipher.getValue());
+    serverInit.setPublicKey(
+        PublicKeyProtoUtil.encodePublicKey(ourKeyPair.getPublic()).toByteString());
+
+    return serverInit.build().toByteArray();
+  }
+
+  /**
+   * Generates a keypair for the provided handshake cipher. Currently only P256_SHA512 is
+   * supported.
+   *
+   * @throws HandshakeException
+   */
+  private KeyPair genKeyPair(HandshakeCipher cipher) throws HandshakeException {
+    switch (cipher) {
+      case P256_SHA512:
+        return PublicKeyProtoUtil.generateEcP256KeyPair();
+      default:
+        // Should never happen
+        throwHandshakeException("unknown cipher: " + cipher);
+    }
+    return null; // unreachable, but makes compiler happy
+  }
+
+  /**
+   * Attempts to parse message 1 (which is a wrapped {@link Ukey2ClientInit}). See go/ukey2 for
+   * details.
+   *
+   * @throws AlertException if an error occurs
+   */
+  private void parseMessage1(byte[] handshakeMessage) throws AlertException, HandshakeException {
+    // Deserialize the protobuf; send a BAD_MESSAGE message if deserialization fails
+    Ukey2Message message = null;
+    try {
+      message = Ukey2Message.parseFrom(handshakeMessage);
+    } catch (InvalidProtocolBufferException e) {
+      throwAlertException(Ukey2Alert.AlertType.BAD_MESSAGE,
+          "Can't parse message 1 " + e.getMessage());
+    }
+
+    // Verify that message_type == Type.CLIENT_INIT; send a BAD_MESSAGE_TYPE message if mismatch
+    if (!message.hasMessageType() || message.getMessageType() != Ukey2Message.Type.CLIENT_INIT) {
+      throwAlertException(
+          Ukey2Alert.AlertType.BAD_MESSAGE_TYPE,
+          "Expected, but did not find ClientInit message type");
+    }
+
+    // Deserialize message_data as a ClientInit message; send a BAD_MESSAGE_DATA message if
+    // deserialization fails
+    if (!message.hasMessageData()) {
+      throwAlertException(Ukey2Alert.AlertType.BAD_MESSAGE_DATA,
+          "Expected message data, but didn't find it");
+    }
+    Ukey2ClientInit clientInit = null;
+    try {
+      clientInit = Ukey2ClientInit.parseFrom(message.getMessageData());
+    } catch (InvalidProtocolBufferException e) {
+      throwAlertException(Ukey2Alert.AlertType.BAD_MESSAGE_DATA,
+          "Can't parse message data into ClientInit");
+    }
+
+    // Check that version == VERSION; send BAD_VERSION message if mismatch
+    if (!clientInit.hasVersion()) {
+      throwAlertException(Ukey2Alert.AlertType.BAD_VERSION, "ClientInit missing version");
+    }
+    if (clientInit.getVersion() != VERSION) {
+      throwAlertException(Ukey2Alert.AlertType.BAD_VERSION, "ClientInit version mismatch");
+    }
+
+    // Check that random is exactly NONCE_LENGTH_IN_BYTES bytes; send Alert.BAD_RANDOM message if
+    // not.
+    if (!clientInit.hasRandom()) {
+      throwAlertException(Ukey2Alert.AlertType.BAD_RANDOM, "ClientInit missing random");
+    }
+    if (clientInit.getRandom().toByteArray().length != NONCE_LENGTH_IN_BYTES) {
+      throwAlertException(Ukey2Alert.AlertType.BAD_RANDOM, "ClientInit has incorrect nonce length");
+    }
+
+    // Check to see if any of the handshake_cipher in cipher_commitment are acceptable. Servers
+    // should select the first handshake_cipher that it finds acceptable to support clients
+    // signaling deprecated but supported HandshakeCiphers. If no handshake_cipher is acceptable
+    // (or there are no HandshakeCiphers in the message), the server sends a BAD_HANDSHAKE_CIPHER
+    //  message
+    List<Ukey2ClientInit.CipherCommitment> commitments = clientInit.getCipherCommitmentsList();
+    if (commitments.isEmpty()) {
+      throwAlertException(
+          Ukey2Alert.AlertType.BAD_HANDSHAKE_CIPHER, "ClientInit is missing cipher commitments");
+    }
+    for (Ukey2ClientInit.CipherCommitment commitment : commitments) {
+      if (!commitment.hasHandshakeCipher()
+          || !commitment.hasCommitment()) {
+        throwAlertException(
+            Ukey2Alert.AlertType.BAD_HANDSHAKE_CIPHER,
+            "ClientInit has improperly formatted cipher commitment");
+      }
+
+      // TODO(aczeskis): for now we only support one cipher, eventually support more
+      if (commitment.getHandshakeCipher() == handshakeCipher.getValue()) {
+        theirCommitment = commitment.getCommitment().toByteArray();
+      }
+    }
+    if (theirCommitment == null) {
+      throwAlertException(Ukey2Alert.AlertType.BAD_HANDSHAKE_CIPHER,
+          "No acceptable commitments found");
+    }
+
+    // Checks that next_protocol contains a protocol that the server supports. Send a
+    // BAD_NEXT_PROTOCOL message if not. We currently only support one protocol
+    if (!clientInit.hasNextProtocol() || !NEXT_PROTOCOL.equals(clientInit.getNextProtocol())) {
+      throwAlertException(Ukey2Alert.AlertType.BAD_NEXT_PROTOCOL, "Incorrect next protocol");
+    }
+
+    // Store raw message for AUTH_STRING computation
+    rawMessage1 = handshakeMessage;
+  }
+
+  /**
+   * Attempts to parse message 2 (which is a wrapped {@link Ukey2ServerInit}). See go/ukey2 for
+   * details.
+   */
+  private void parseMessage2(final byte[] handshakeMessage)
+      throws AlertException, HandshakeException {
+    // Deserialize the protobuf; send a BAD_MESSAGE message if deserialization fails
+    Ukey2Message message = null;
+    try {
+      message = Ukey2Message.parseFrom(handshakeMessage);
+    } catch (InvalidProtocolBufferException e) {
+      throwAlertException(Ukey2Alert.AlertType.BAD_MESSAGE,
+          "Can't parse message 2 " + e.getMessage());
+    }
+
+    // Verify that message_type == Type.SERVER_INIT; send a BAD_MESSAGE_TYPE message if mismatch
+    if (!message.hasMessageType()) {
+      throwAlertException(Ukey2Alert.AlertType.BAD_MESSAGE_TYPE,
+          "Expected, but did not find message type");
+    }
+    if (message.getMessageType() == Ukey2Message.Type.ALERT) {
+      handshakeState = InternalState.HANDSHAKE_ERROR;
+      throwHandshakeMessageFromAlertMessage(message);
+    }
+    if (message.getMessageType() != Ukey2Message.Type.SERVER_INIT) {
+      throwAlertException(
+          Ukey2Alert.AlertType.BAD_MESSAGE_TYPE,
+          "Expected, but did not find SERVER_INIT message type");
+    }
+
+    // Deserialize message_data as a ServerInit message; send a BAD_MESSAGE_DATA message if
+    // deserialization fails
+    if (!message.hasMessageData()) {
+
+      throwAlertException(Ukey2Alert.AlertType.BAD_MESSAGE_DATA,
+          "Expected message data, but didn't find it");
+    }
+    Ukey2ServerInit serverInit = null;
+    try {
+      serverInit = Ukey2ServerInit.parseFrom(message.getMessageData());
+    } catch (InvalidProtocolBufferException e) {
+      throwAlertException(Ukey2Alert.AlertType.BAD_MESSAGE_DATA,
+          "Can't parse message data into ServerInit");
+    }
+
+    // Check that version == VERSION; send BAD_VERSION message if mismatch
+    if (!serverInit.hasVersion()) {
+      throwAlertException(Ukey2Alert.AlertType.BAD_VERSION, "ServerInit missing version");
+    }
+    if (serverInit.getVersion() != VERSION) {
+      throwAlertException(Ukey2Alert.AlertType.BAD_VERSION, "ServerInit version mismatch");
+    }
+
+    // Check that random is exactly NONCE_LENGTH_IN_BYTES bytes; send Alert.BAD_RANDOM message if
+    // not.
+    if (!serverInit.hasRandom()) {
+      throwAlertException(Ukey2Alert.AlertType.BAD_RANDOM, "ServerInit missing random");
+    }
+    if (serverInit.getRandom().toByteArray().length != NONCE_LENGTH_IN_BYTES) {
+      throwAlertException(Ukey2Alert.AlertType.BAD_RANDOM, "ServerInit has incorrect nonce length");
+    }
+
+    // Check that handshake_cipher matches a handshake cipher that was sent in
+    // ClientInit.cipher_commitments. If not, send a BAD_HANDSHAKECIPHER message
+    if (!serverInit.hasHandshakeCipher()) {
+      throwAlertException(Ukey2Alert.AlertType.BAD_HANDSHAKE_CIPHER, "No handshake cipher found");
+    }
+    HandshakeCipher serverCipher = null;
+    for (HandshakeCipher cipher : HandshakeCipher.values()) {
+      if (cipher.getValue() == serverInit.getHandshakeCipher()) {
+        serverCipher = cipher;
+        break;
+      }
+    }
+    if (serverCipher == null || serverCipher != handshakeCipher) {
+      throwAlertException(Ukey2Alert.AlertType.BAD_HANDSHAKE_CIPHER,
+          "No acceptable handshake cipher found");
+    }
+
+    // Check that public_key parses into a correct public key structure. If not, send a
+    // BAD_PUBLIC_KEY message.
+    if (!serverInit.hasPublicKey()) {
+      throwAlertException(Ukey2Alert.AlertType.BAD_PUBLIC_KEY, "No public key found in ServerInit");
+    }
+    theirPublicKey = parseP256PublicKey(serverInit.getPublicKey().toByteArray());
+
+    // Store raw message for AUTH_STRING computation
+    rawMessage2 = handshakeMessage;
+  }
+
+  /**
+   * Attempts to parse message 3 (which is a wrapped {@link Ukey2ClientFinished}). See go/ukey2 for
+   * details.
+   */
+  private void parseMessage3(final byte[] handshakeMessage) throws HandshakeException {
+    // Deserialize the protobuf; terminate the connection if deserialization fails.
+    Ukey2Message message = null;
+    try {
+      message = Ukey2Message.parseFrom(handshakeMessage);
+    } catch (InvalidProtocolBufferException e) {
+      throwHandshakeException("Can't parse message 3", e);
+    }
+
+    // Verify that message_type == Type.CLIENT_FINISH; terminate connection if mismatch occurs
+    if (!message.hasMessageType()) {
+      throw new HandshakeException("Expected, but did not find message type");
+    }
+    if (message.getMessageType() == Ukey2Message.Type.ALERT) {
+      throwHandshakeMessageFromAlertMessage(message);
+    }
+    if (message.getMessageType() != Ukey2Message.Type.CLIENT_FINISH) {
+      throwHandshakeException("Expected, but did not find CLIENT_FINISH message type");
+    }
+
+    // Verify that the hash of the ClientFinished matches the expected commitment from ClientInit.
+    // Terminate the connection if the expected match fails.
+    verifyCommitment(handshakeMessage);
+
+    // Deserialize message_data as a ClientFinished message; terminate the connection if
+    // deserialization fails.
+    if (!message.hasMessageData()) {
+      throwHandshakeException("Expected message data, but didn't find it");
+    }
+    Ukey2ClientFinished clientFinished = null;
+    try {
+      clientFinished = Ukey2ClientFinished.parseFrom(message.getMessageData());
+    } catch (InvalidProtocolBufferException e) {
+      throwHandshakeException(e);
+    }
+
+    // Check that public_key parses into a correct public key structure. If not, terminate the
+    // connection.
+    if (!clientFinished.hasPublicKey()) {
+      throwHandshakeException("No public key found in ClientFinished");
+    }
+    try {
+      theirPublicKey = parseP256PublicKey(clientFinished.getPublicKey().toByteArray());
+    } catch (AlertException e) {
+      // Wrap in a HandshakeException because error should not be sent on the wire.
+      throwHandshakeException(e);
+    }
+  }
+
+  private void verifyCommitment(byte[] handshakeMessage) throws HandshakeException {
+    byte[] actualClientFinishHash = null;
+    switch (handshakeCipher) {
+      case P256_SHA512:
+        actualClientFinishHash = sha512(handshakeMessage);
+        break;
+      default:
+        // should be unreachable
+        throwIllegalStateException("Unexpected handshakeCipher");
+    }
+
+    // Time constant after Java SE 6 Update 17
+    // See http://www.oracle.com/technetwork/java/javase/6u17-141447.html
+    if (!MessageDigest.isEqual(actualClientFinishHash, theirCommitment)) {
+      throwHandshakeException("Commitment does not match");
+    }
+  }
+
+  private void throwHandshakeMessageFromAlertMessage(Ukey2Message message)
+      throws HandshakeException {
+    if (message.hasMessageData()) {
+      Ukey2Alert alert = null;
+      try {
+        alert = Ukey2Alert.parseFrom(message.getMessageData());
+      } catch (InvalidProtocolBufferException e) {
+        throwHandshakeException("Cannot parse alert message", e);
+      }
+
+      if (alert.hasType() && alert.hasErrorMessage()) {
+        throwHandshakeException(
+            "Received Alert message. Type: "
+                + alert.getType()
+                + " Error Message: "
+                + alert.getErrorMessage());
+      } else if (alert.hasType()) {
+        throwHandshakeException("Received Alert message. Type: " + alert.getType());
+      }
+    }
+
+    throwHandshakeException("Received empty Alert Message");
+  }
+
+  /**
+   * Parses an encoded public P256 key.
+   */
+  private PublicKey parseP256PublicKey(byte[] encodedPublicKey)
+      throws AlertException, HandshakeException {
+    try {
+      return PublicKeyProtoUtil.parsePublicKey(GenericPublicKey.parseFrom(encodedPublicKey));
+    } catch (InvalidProtocolBufferException | InvalidKeySpecException e) {
+      throwAlertException(Ukey2Alert.AlertType.BAD_PUBLIC_KEY,
+          "Cannot parse public key: " + e.getMessage());
+      return null; // unreachable, but makes compiler happy
+    }
+  }
+
+  /**
+   * Generates a {@link CipherCommitment} for the P256_SHA512 cipher.
+   */
+  private CipherCommitment generateP256SHA512Commitment() throws HandshakeException {
+    // Generate the corresponding finished message if it's not done yet
+    if (!rawMessage3Map.containsKey(HandshakeCipher.P256_SHA512)) {
+      generateP256SHA512ClientFinished(ourKeyPair);
+    }
+
+    CipherCommitment.Builder cipherCommitment = CipherCommitment.newBuilder();
+    cipherCommitment.setHandshakeCipher(UkeyProto.Ukey2HandshakeCipher.P256_SHA512);
+    cipherCommitment.setCommitment(
+        ByteString.copyFrom(sha512(rawMessage3Map.get(HandshakeCipher.P256_SHA512))));
+
+    return cipherCommitment.build();
+  }
+
+  /**
+   * Generates and records a {@link Ukey2ClientFinished} message for the P256_SHA512 cipher.
+   */
+  private Ukey2ClientFinished generateP256SHA512ClientFinished(KeyPair p256KeyPair) {
+    byte[] encodedKey = PublicKeyProtoUtil.encodePublicKey(p256KeyPair.getPublic()).toByteArray();
+
+    Ukey2ClientFinished.Builder clientFinished = Ukey2ClientFinished.newBuilder();
+    clientFinished.setPublicKey(ByteString.copyFrom(encodedKey));
+
+    rawMessage3Map.put(
+        HandshakeCipher.P256_SHA512,
+        makeUkey2Message(Ukey2Message.Type.CLIENT_FINISH, clientFinished.build().toByteArray()));
+
+    return clientFinished.build();
+  }
+
+  /**
+   * Generates the serialized representation of a {@link Ukey2Message} based on the provided type
+   * and data.
+   */
+  private byte[] makeUkey2Message(Ukey2Message.Type messageType, byte[] messageData) {
+    Ukey2Message.Builder message = Ukey2Message.newBuilder();
+
+    switch (messageType) {
+      case ALERT:
+      case CLIENT_INIT:
+      case SERVER_INIT:
+      case CLIENT_FINISH:
+        // fall through intentional; valid message types
+        break;
+      default:
+        throwIllegalArgumentException("Invalid message type: " + messageType);
+    }
+    message.setMessageType(messageType);
+
+    // Alerts a blank message data field
+    if (messageType != Ukey2Message.Type.ALERT) {
+      if (messageData == null || messageData.length == 0) {
+        throwIllegalArgumentException("Cannot send empty message data for non-alert messages");
+      }
+      message.setMessageData(ByteString.copyFrom(messageData));
+    }
+
+    return message.build().toByteArray();
+  }
+
+  /**
+   * Returns a {@link Ukey2Alert} message of given type and having the loggable additional data if
+   * present.
+   */
+  private Ukey2Alert makeAlertMessage(Ukey2Alert.AlertType alertType,
+      @Nullable String loggableAdditionalData) throws HandshakeException {
+    switch (alertType) {
+      case BAD_MESSAGE:
+      case BAD_MESSAGE_TYPE:
+      case INCORRECT_MESSAGE:
+      case BAD_MESSAGE_DATA:
+      case BAD_VERSION:
+      case BAD_RANDOM:
+      case BAD_HANDSHAKE_CIPHER:
+      case BAD_NEXT_PROTOCOL:
+      case BAD_PUBLIC_KEY:
+      case INTERNAL_ERROR:
+        // fall through intentional; valid alert types
+        break;
+      default:
+        throwHandshakeException("Unknown alert type: " + alertType);
+    }
+
+    Ukey2Alert.Builder alert = Ukey2Alert.newBuilder();
+    alert.setType(alertType);
+
+    if (loggableAdditionalData != null) {
+      alert.setErrorMessage(loggableAdditionalData);
+    }
+
+    return alert.build();
+  }
+
+  /**
+   * Generates a cryptoraphically random nonce of NONCE_LENGTH_IN_BYTES bytes.
+   */
+  private static byte[] generateRandomNonce() {
+    SecureRandom rng = new SecureRandom();
+    byte[] randomNonce = new byte[NONCE_LENGTH_IN_BYTES];
+    rng.nextBytes(randomNonce);
+    return randomNonce;
+  }
+
+  /**
+   * Handy wrapper to do SHA512.
+   */
+  private byte[] sha512(byte[] input) throws HandshakeException {
+    MessageDigest sha512;
+    try {
+      sha512 = MessageDigest.getInstance("SHA-512");
+      return sha512.digest(input);
+    } catch (NoSuchAlgorithmException e) {
+      throwHandshakeException("No security provider initialized yet?", e);
+      return null; // unreachable in practice, but makes compiler happy
+    }
+  }
+
+  // Exception wrappers that remember to set the handshake state to ERROR
+
+  private void throwAlertException(Ukey2Alert.AlertType alertType, String alertLogStatement)
+      throws AlertException, HandshakeException {
+    handshakeState = InternalState.HANDSHAKE_ERROR;
+    throw new AlertException(alertLogStatement, makeAlertMessage(alertType, alertLogStatement));
+  }
+
+  private void throwHandshakeException(String logMessage) throws HandshakeException {
+    handshakeState = InternalState.HANDSHAKE_ERROR;
+    throw new HandshakeException(logMessage);
+  }
+
+  private void throwHandshakeException(Exception e) throws HandshakeException {
+    handshakeState = InternalState.HANDSHAKE_ERROR;
+    throw new HandshakeException(e);
+  }
+
+  private void throwHandshakeException(String logMessage, Exception e) throws HandshakeException {
+    handshakeState = InternalState.HANDSHAKE_ERROR;
+    throw new HandshakeException(logMessage, e);
+  }
+
+  private void throwIllegalStateException(String logMessage) {
+    handshakeState = InternalState.HANDSHAKE_ERROR;
+    throw new IllegalStateException(logMessage);
+  }
+
+  private void throwIllegalArgumentException(String logMessage) {
+    handshakeState = InternalState.HANDSHAKE_ERROR;
+    throw new IllegalArgumentException(logMessage);
+  }
+}
diff --git a/src/main/java/com/google/security/cryptauth/lib/securegcm/device_to_device_messages_config.asciipb b/src/main/java/com/google/security/cryptauth/lib/securegcm/device_to_device_messages_config.asciipb
new file mode 100644
index 0000000..0e2952c
--- /dev/null
+++ b/src/main/java/com/google/security/cryptauth/lib/securegcm/device_to_device_messages_config.asciipb
@@ -0,0 +1,3 @@
+optimize_mode: LITE_RUNTIME
+
+allowed_message: "securegcm.DeviceToDeviceMessage"
diff --git a/src/main/java/com/google/security/cryptauth/lib/securegcm/securegcm_config.asciipb b/src/main/java/com/google/security/cryptauth/lib/securegcm/securegcm_config.asciipb
new file mode 100644
index 0000000..d838bd3
--- /dev/null
+++ b/src/main/java/com/google/security/cryptauth/lib/securegcm/securegcm_config.asciipb
@@ -0,0 +1,4 @@
+optimize_mode: LITE_RUNTIME
+
+allowed_enum: "securegcm.Type"
+allowed_message: "securegcm.GcmMetadata"
diff --git a/src/main/java/com/google/security/cryptauth/lib/securemessage/CryptoOps.java b/src/main/java/com/google/security/cryptauth/lib/securemessage/CryptoOps.java
new file mode 100644
index 0000000..1e3b196
--- /dev/null
+++ b/src/main/java/com/google/security/cryptauth/lib/securemessage/CryptoOps.java
@@ -0,0 +1,517 @@
+/* Copyright 2018 Google LLC
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.google.security.cryptauth.lib.securemessage;
+
+import com.google.security.annotations.SuppressInsecureCipherModeCheckerReviewed;
+import java.io.UnsupportedEncodingException;
+import java.security.InvalidAlgorithmParameterException;
+import java.security.InvalidKeyException;
+import java.security.Key;
+import java.security.MessageDigest;
+import java.security.NoSuchAlgorithmException;
+import java.security.PrivateKey;
+import java.security.PublicKey;
+import java.security.SecureRandom;
+import java.security.Signature;
+import java.security.SignatureException;
+import javax.annotation.Nullable;
+import javax.crypto.BadPaddingException;
+import javax.crypto.Cipher;
+import javax.crypto.IllegalBlockSizeException;
+import javax.crypto.Mac;
+import javax.crypto.NoSuchPaddingException;
+import javax.crypto.SecretKey;
+import javax.crypto.spec.IvParameterSpec;
+import javax.crypto.spec.SecretKeySpec;
+
+/**
+ * Encapsulates the cryptographic operations used by the {@code SecureMessage*} classes.
+ */
+public class CryptoOps {
+  
+  private CryptoOps() {}  // Do not instantiate
+
+  /**
+   * Enum of supported signature types, with additional mappings to indicate the name of the
+   * underlying JCA algorithm used to create the signature.
+   * @see <a href=
+   * "http://docs.oracle.com/javase/7/docs/technotes/guides/security/StandardNames.html">
+   * Java Cryptography Architecture, Standard Algorithm Name Documentation</a>
+   */
+  public enum SigType {
+    HMAC_SHA256(SecureMessageProto.SigScheme.HMAC_SHA256, "HmacSHA256", false),
+    ECDSA_P256_SHA256(SecureMessageProto.SigScheme.ECDSA_P256_SHA256, "SHA256withECDSA", true),
+    RSA2048_SHA256(SecureMessageProto.SigScheme.RSA2048_SHA256, "SHA256withRSA", true);
+
+    public SecureMessageProto.SigScheme getSigScheme() {
+      return sigScheme;
+    }
+
+    public String getJcaName() {
+      return jcaName;
+    }
+
+    public boolean isPublicKeyScheme() {
+      return publicKeyScheme;
+    }
+
+    public static SigType valueOf(SecureMessageProto.SigScheme sigScheme) {
+      for (SigType value : values()) {
+        if (value.sigScheme.equals(sigScheme)) {
+          return value;
+        }
+      }
+      throw new IllegalArgumentException("Unsupported SigType: " + sigScheme);
+    }
+
+    private final SecureMessageProto.SigScheme sigScheme;
+    private final String jcaName;
+    private final boolean publicKeyScheme;
+
+    SigType(SecureMessageProto.SigScheme sigType, String jcaName, boolean publicKeyScheme) {
+      this.sigScheme = sigType;
+      this.jcaName = jcaName;
+      this.publicKeyScheme = publicKeyScheme;
+    }
+  }
+
+  /**
+   * Enum of supported encryption types, with additional mappings to indicate the name of the
+   * underlying JCA algorithm used to perform the encryption.
+   * @see <a href=
+   * "http://docs.oracle.com/javase/7/docs/technotes/guides/security/StandardNames.html">
+   * Java Cryptography Architecture, Standard Algorithm Name Documentation</a>
+   */
+  public enum EncType {
+    NONE(SecureMessageProto.EncScheme.NONE, "InvalidDoNotUseForJCA"),
+    AES_256_CBC(SecureMessageProto.EncScheme.AES_256_CBC, "AES/CBC/PKCS5Padding");
+
+    public SecureMessageProto.EncScheme getEncScheme() {
+      return encScheme;
+    }
+
+    public String getJcaName() {
+      return jcaName;
+    }
+
+    public static EncType valueOf(SecureMessageProto.EncScheme encScheme) {
+      for (EncType value : values()) {
+        if (value.encScheme.equals(encScheme)) {
+          return value;
+        }
+      }
+      throw new IllegalArgumentException("Unsupported EncType: " + encScheme);
+    }
+
+    private final SecureMessageProto.EncScheme encScheme;
+    private final String jcaName;
+
+    EncType(SecureMessageProto.EncScheme encScheme, String jcaName) {
+      this.encScheme = encScheme;
+      this.jcaName = jcaName;
+    }
+  }
+
+  /**
+   * Truncated hash output length, in bytes.
+   */
+  static final int DIGEST_LENGTH = 20;
+  /**
+   * A salt value specific to this library, generated as SHA-256("SecureMessage")
+   */
+  private static final byte[] SALT = sha256("SecureMessage");
+  private static final byte[] CONSTANT_01 = { 0x01 };  // For convenience
+
+  /**
+   * Signs {@code data} using the algorithm specified by {@code sigType} with {@code signingKey}.
+   *
+   * @param rng is required for public key signature schemes
+   * @return raw signature
+   * @throws InvalidKeyException if {@code signingKey} is incompatible with {@code sigType}
+   * @throws NoSuchAlgorithmException if the security provider is inadequate for {@code sigType}
+   */
+  static byte[] sign(
+      SigType sigType, Key signingKey, @Nullable SecureRandom rng, byte[] data)
+      throws InvalidKeyException, NoSuchAlgorithmException {
+    if ((signingKey == null) || (data == null)) {
+      throw new NullPointerException();
+    }
+    if (sigType.isPublicKeyScheme()) {
+      if (rng == null) {
+        throw new NullPointerException();
+      }
+      if (!(signingKey instanceof PrivateKey)) {
+        throw new InvalidKeyException("Expected a PrivateKey");
+      }
+      Signature sigScheme = Signature.getInstance(sigType.getJcaName());
+      sigScheme.initSign((PrivateKey) signingKey, rng);
+      try {
+        // We include a fixed magic value (salt) in the signature so that if the signing key is
+        // reused in another context we can't be confused -- provided that the other user of the
+        // signing key only signs statements that do not begin with this salt.
+        sigScheme.update(SALT);
+        sigScheme.update(data);
+        return sigScheme.sign();
+      } catch (SignatureException e) {
+        throw new IllegalStateException(e);  // Consistent with failures in Mac.doFinal
+      }
+    } else {
+      Mac macScheme = Mac.getInstance(sigType.getJcaName());
+      // Note that an AES-256 SecretKey should work with most Mac schemes
+      SecretKey derivedKey = deriveAes256KeyFor(getSecretKey(signingKey), getPurpose(sigType));
+      macScheme.init(derivedKey);
+      return macScheme.doFinal(data);
+    }
+  }
+
+  /**
+   * Verifies the {@code signature} on {@code data} using the algorithm specified by
+   * {@code sigType} with {@code verificationKey}.
+   *
+   * @return true iff the signature is verified
+   * @throws NoSuchAlgorithmException if the security provider is inadequate for {@code sigType}
+   * @throws InvalidKeyException if {@code verificationKey} is incompatible with {@code sigType}
+   * @throws SignatureException
+   */
+  static boolean verify(Key verificationKey, SigType sigType, byte[] signature, byte[] data)
+      throws NoSuchAlgorithmException, InvalidKeyException, SignatureException {
+    if ((verificationKey == null) || (signature == null) || (data == null)) {
+      throw new NullPointerException();
+    }
+    if (sigType.isPublicKeyScheme()) {
+      if (!(verificationKey instanceof PublicKey)) {
+        throw new InvalidKeyException("Expected a PublicKey");
+      }
+      Signature sigScheme = Signature.getInstance(sigType.getJcaName());
+      sigScheme.initVerify((PublicKey) verificationKey);
+      sigScheme.update(SALT);  // See the comments in sign() for more on this
+      sigScheme.update(data);
+      return sigScheme.verify(signature);
+    } else {
+      Mac macScheme = Mac.getInstance(sigType.getJcaName());
+      SecretKey derivedKey =
+          deriveAes256KeyFor(getSecretKey(verificationKey), getPurpose(sigType));
+      macScheme.init(derivedKey);
+      return constantTimeArrayEquals(signature, macScheme.doFinal(data));
+    }
+  }
+
+  /**
+   * Generate a random IV appropriate for use with the algorithm specified in {@code encType}.
+   *
+   * @return a freshly generated IV (a random byte sequence of appropriate length)
+   * @throws NoSuchAlgorithmException if the security provider is inadequate for {@code encType}
+   */
+  @SuppressInsecureCipherModeCheckerReviewed
+  // See b/26525455 for security review.
+  static byte[] generateIv(EncType encType, SecureRandom rng) throws NoSuchAlgorithmException {
+    if (rng == null) {
+      throw new NullPointerException();
+    }
+    try {
+      Cipher encrypter = Cipher.getInstance(encType.getJcaName());
+      byte[] iv = new byte[encrypter.getBlockSize()];
+      rng.nextBytes(iv);
+      return iv;
+    } catch (NoSuchPaddingException e) {
+      throw new NoSuchAlgorithmException(e);  // Consolidate into NoSuchAlgorithmException
+    }
+  }
+
+  /**
+   * Encrypts {@code plaintext} using the algorithm specified in {@code encType}, with the specified
+   * {@code iv} and {@code encryptionKey}.
+   *
+   * @param rng source of randomness to be used with the specified cipher, if necessary
+   * @return encrypted data
+   * @throws NoSuchAlgorithmException if the security provider is inadequate for {@code encType}
+   * @throws InvalidKeyException if {@code encryptionKey} is incompatible with {@code encType}
+   */
+  @SuppressInsecureCipherModeCheckerReviewed
+  // See b/26525455 for security review.
+  static byte[] encrypt(
+      Key encryptionKey, EncType encType, @Nullable SecureRandom rng, byte[] iv, byte[] plaintext)
+      throws NoSuchAlgorithmException, InvalidKeyException {
+    if ((encryptionKey == null) || (iv == null) || (plaintext == null)) {
+      throw new NullPointerException();
+    }
+    if (encType == EncType.NONE) {
+      throw new NoSuchAlgorithmException("Cannot use NONE type here");
+    }
+    try {
+      Cipher encrypter = Cipher.getInstance(encType.getJcaName());
+      SecretKey derivedKey =
+          deriveAes256KeyFor(getSecretKey(encryptionKey), getPurpose(encType));
+      encrypter.init(Cipher.ENCRYPT_MODE, derivedKey, new IvParameterSpec(iv), rng);
+      return encrypter.doFinal(plaintext);
+    } catch (InvalidAlgorithmParameterException e) {
+      throw new AssertionError(e);  // Should never happen
+    } catch (IllegalBlockSizeException e) {
+      throw new AssertionError(e);  // Should never happen
+    } catch (BadPaddingException e) {
+      throw new AssertionError(e);  // Should never happen
+    } catch (NoSuchPaddingException e) {
+      throw new NoSuchAlgorithmException(e);  // Consolidate into NoSuchAlgorithmException
+    }
+  }
+
+  /**
+   * Decrypts {@code ciphertext} using the algorithm specified in {@code encType}, with the
+   * specified {@code iv} and {@code decryptionKey}.
+   *
+   * @return the plaintext (decrypted) data
+   * @throws NoSuchAlgorithmException if the security provider is inadequate for {@code encType}
+   * @throws InvalidKeyException if {@code decryptionKey} is incompatible with {@code encType}
+   * @throws InvalidAlgorithmParameterException if {@code encType} exceeds legal cryptographic
+   * strength limits in this jurisdiction
+   * @throws IllegalBlockSizeException if {@code ciphertext} contains an illegal block
+   * @throws BadPaddingException if {@code ciphertext} contains an illegal padding
+   */
+  @SuppressInsecureCipherModeCheckerReviewed
+  // See b/26525455 for security review
+  static byte[] decrypt(Key decryptionKey, EncType encType, byte[] iv, byte[] ciphertext)
+      throws NoSuchAlgorithmException, InvalidKeyException, InvalidAlgorithmParameterException,
+          IllegalBlockSizeException, BadPaddingException {
+    if ((decryptionKey == null) || (iv == null) || (ciphertext == null)) {
+      throw new NullPointerException();
+    }
+    if (encType == EncType.NONE) {
+      throw new NoSuchAlgorithmException("Cannot use NONE type here");
+    }
+    try {
+      Cipher decrypter = Cipher.getInstance(encType.getJcaName());
+      SecretKey derivedKey =
+          deriveAes256KeyFor(getSecretKey(decryptionKey), getPurpose(encType));
+      decrypter.init(Cipher.DECRYPT_MODE, derivedKey, new IvParameterSpec(iv));
+      return decrypter.doFinal(ciphertext);
+    } catch (NoSuchPaddingException e) {
+      throw new AssertionError(e);  // Should never happen
+    }
+  }
+
+  /**
+   * Computes a collision-resistant hash of {@link #DIGEST_LENGTH} bytes
+   * (using a truncated SHA-256 output).
+   */
+  static byte[] digest(byte[] data) throws NoSuchAlgorithmException {
+    MessageDigest sha256 = MessageDigest.getInstance("SHA-256");
+    byte[] truncatedHash = new byte[DIGEST_LENGTH];
+    System.arraycopy(sha256.digest(data), 0, truncatedHash, 0, DIGEST_LENGTH);
+    return truncatedHash;
+  }
+
+  /**
+   * Returns {@code true} if the two arrays are equal to one another.
+   * When the two arrays differ in length, trivially returns {@code false}.
+   * When the two arrays are equal in length, does a constant-time comparison
+   * of the two, i.e. does not abort the comparison when the first differing
+   * element is found.
+   *
+   * <p>NOTE: This is a copy of {@code java/com/google/math/crypto/ConstantTime#arrayEquals}.
+   *
+   * @param a An array to compare
+   * @param b Another array to compare
+   * @return {@code true} if these arrays are both null or if they have equal
+   *         length and equal bytes in all elements
+   */
+  static boolean constantTimeArrayEquals(@Nullable byte[] a, @Nullable byte[] b) {
+    if (a == null || b == null) {
+      return (a == b);
+    }
+    if (a.length != b.length) {
+      return false;
+    }
+    byte result = 0;
+    for (int i = 0; i < b.length; i++) {
+      result = (byte) (result | a[i] ^ b[i]);
+    }
+    return (result == 0);
+  }
+
+  // @VisibleForTesting
+  static String getPurpose(SigType sigType) {
+    return "SIG:" + sigType.getSigScheme().getNumber();
+  }
+
+  // @VisibleForTesting
+  static String getPurpose(EncType encType) {
+    return "ENC:" + encType.getEncScheme().getNumber();
+  }
+
+  private static SecretKey getSecretKey(Key key) throws InvalidKeyException {
+    if (!(key instanceof SecretKey)) {
+      throw new InvalidKeyException("Expected a SecretKey");
+    }
+    return (SecretKey) key;
+  }
+
+  /**
+   * @return the UTF-8 encoding of the given string
+   * @throws RuntimeException if the UTF-8 charset is not present.
+   */
+  public static byte[] utf8StringToBytes(String input) {
+    try {
+      return input.getBytes("UTF-8");
+    } catch (UnsupportedEncodingException e) {
+      throw new RuntimeException(e);  // Shouldn't happen, UTF-8 is universal
+    }
+  }
+
+  /**
+   * @return SHA-256(UTF-8 encoded input)
+   */
+  public static byte[] sha256(String input) {
+    MessageDigest sha256;
+    try {
+      sha256 = MessageDigest.getInstance("SHA-256");
+      return sha256.digest(utf8StringToBytes(input));
+    } catch (NoSuchAlgorithmException e) {
+      throw new RuntimeException("No security provider initialized yet?", e);
+    }
+  }
+
+  /**
+   * A key derivation function specific to this library, which accepts a {@code masterKey} and an
+   * arbitrary {@code purpose} describing the intended application of the derived sub-key,
+   * and produces a derived AES-256 key safe to use as if it were independent of any other
+   * derived key which used a different {@code purpose}.
+   *
+   * @param masterKey any key suitable for use with HmacSHA256
+   * @param purpose a UTF-8 encoded string describing the intended purpose of derived key
+   * @return a derived SecretKey suitable for use with AES-256
+   * @throws InvalidKeyException if the encoded form of {@code masterKey} cannot be accessed
+   */
+  static SecretKey deriveAes256KeyFor(SecretKey masterKey, String purpose)
+      throws NoSuchAlgorithmException, InvalidKeyException {
+    return new SecretKeySpec(hkdf(masterKey, SALT, utf8StringToBytes(purpose)), "AES");
+  }
+
+  /**
+   * Implements HKDF (RFC 5869) with the SHA-256 hash and a 256-bit output key length.
+   *
+   * Please make sure to select a salt that is fixed and unique for your codebase, and use the
+   * {@code info} parameter to specify any additional bits that should influence the derived key.
+   *
+   * @param inputKeyMaterial master key from which to derive sub-keys
+   * @param salt a (public) randomly generated 256-bit input that can be re-used
+   * @param info arbitrary information that is bound to the derived key (i.e., used in its creation)
+   * @return raw derived key bytes = HKDF-SHA256(inputKeyMaterial, salt, info)
+   * @throws InvalidKeyException if the encoded form of {@code inputKeyMaterial} cannot be accessed
+   */
+  public static byte[] hkdf(SecretKey inputKeyMaterial, byte[] salt, byte[] info)
+      throws NoSuchAlgorithmException, InvalidKeyException {
+    if ((inputKeyMaterial == null) || (salt == null) || (info == null)) {
+      throw new NullPointerException();
+    }
+    return hkdfSha256Expand(hkdfSha256Extract(inputKeyMaterial, salt), info);
+  }
+
+  /**
+   * @return the concatenation of {@code a} and {@code b}, treating {@code null} as the empty array.
+   */
+  static byte[] concat(@Nullable byte[] a, @Nullable byte[] b) {
+    if ((a == null) && (b == null)) {
+      return new byte[] { };
+    }
+    if (a == null) {
+      return b;
+    }
+    if (b == null) {
+      return a;
+    }
+    byte[] result = new byte[a.length + b.length];
+    System.arraycopy(a, 0, result, 0, a.length);
+    System.arraycopy(b, 0, result, a.length, b.length);
+    return result;
+  }
+
+  /**
+   * Since {@code Arrays.copyOfRange(...)} is not available on older Android platforms,
+   * a custom method for computing a subarray is provided here.
+   *
+   * @return the substring of {@code in} from {@code beginIndex} (inclusive)
+   *   up to {@code endIndex} (exclusive)
+   */
+  static byte[] subarray(byte[] in, int beginIndex, int endIndex) {
+    if (in == null) {
+      throw new NullPointerException();
+    }
+    int length = endIndex - beginIndex;
+    if ((length < 0)
+        || (beginIndex < 0)
+        || (endIndex < 0)
+        || (beginIndex >= in.length)
+        || (endIndex > in.length)) {
+      throw new IndexOutOfBoundsException();
+    }
+    byte[] result = new byte[length];
+    if (length > 0) {
+      System.arraycopy(in, beginIndex, result, 0, length);
+    }
+    return result;
+  }
+
+  /**
+   * The HKDF (RFC 5869) extraction function, using the SHA-256 hash function. This function is
+   * used to pre-process the inputKeyMaterial and mix it with the salt, producing output suitable
+   * for use with HKDF expansion function (which produces the actual derived key).
+   *
+   * @see #hkdfSha256Expand(byte[], byte[])
+   * @return HMAC-SHA256(salt, inputKeyMaterial)  (salt is the "key" for the HMAC)
+   * @throws InvalidKeyException if the encoded form of {@code inputKeyMaterial} cannot be accessed
+   * @throws NoSuchAlgorithmException if the HmacSHA256 or AES algorithms are unavailable
+   */
+  private static byte[] hkdfSha256Extract(SecretKey inputKeyMaterial, byte[] salt)
+      throws NoSuchAlgorithmException, InvalidKeyException {
+    Mac macScheme = Mac.getInstance("HmacSHA256");
+    try {
+      macScheme.init(new SecretKeySpec(salt, "AES"));
+    } catch (InvalidKeyException e) {
+      throw new AssertionError(e);  // This should never happen
+    }
+    // Note that the SecretKey encoding format is defined to be RAW, so the encoded form should be
+    // consistent across implementations.
+    byte[] encodedKeyMaterial = inputKeyMaterial.getEncoded();
+    if (encodedKeyMaterial == null) {
+      throw new InvalidKeyException("Cannot get encoded form of SecretKey");
+    }
+    return macScheme.doFinal(encodedKeyMaterial);
+  }
+
+  /**
+   * Special case of HKDF (RFC 5869) expansion function, using the SHA-256 hash function and
+   * allowing for a maximum output length of 256 bits.
+   *
+   * @param pseudoRandomKey should be generated by {@link #hkdfSha256Expand(byte[], byte[])}
+   * @param info arbitrary information the derived key should be bound to
+   * @return raw derived key bytes = HMAC-SHA256(pseudoRandomKey, info | 0x01)
+   * @throws NoSuchAlgorithmException if the HmacSHA256 or AES algorithms are unavailable
+   */
+  private static byte[] hkdfSha256Expand(byte[] pseudoRandomKey, byte[] info)
+      throws NoSuchAlgorithmException {
+    Mac macScheme = Mac.getInstance("HmacSHA256");
+    try {
+      macScheme.init(new SecretKeySpec(pseudoRandomKey, "AES"));
+    } catch (InvalidKeyException e) {
+      throw new AssertionError(e);  // This should never happen
+    }
+    // Arbitrary "info" to be included in the MAC.
+    macScheme.update(info);
+    // Note that RFC 5869 computes number of blocks N = ceil(hash length / output length), but
+    // here we only deal with a 256 bit hash up to a 256 bit output, yielding N=1.
+    return macScheme.doFinal(CONSTANT_01);
+  }
+
+}
diff --git a/src/main/java/com/google/security/cryptauth/lib/securemessage/PublicKeyProtoUtil.java b/src/main/java/com/google/security/cryptauth/lib/securemessage/PublicKeyProtoUtil.java
new file mode 100644
index 0000000..ab97cca
--- /dev/null
+++ b/src/main/java/com/google/security/cryptauth/lib/securemessage/PublicKeyProtoUtil.java
@@ -0,0 +1,643 @@
+/* Copyright 2018 Google LLC
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.google.security.cryptauth.lib.securemessage;
+
+import com.google.protobuf.ByteString;
+import com.google.security.annotations.SuppressInsecureCipherModeCheckerPendingReview;
+import com.google.security.cryptauth.lib.securemessage.SecureMessageProto.DhPublicKey;
+import com.google.security.cryptauth.lib.securemessage.SecureMessageProto.EcP256PublicKey;
+import com.google.security.cryptauth.lib.securemessage.SecureMessageProto.GenericPublicKey;
+import com.google.security.cryptauth.lib.securemessage.SecureMessageProto.SimpleRsaPublicKey;
+import java.math.BigInteger;
+import java.security.InvalidAlgorithmParameterException;
+import java.security.KeyFactory;
+import java.security.KeyPair;
+import java.security.KeyPairGenerator;
+import java.security.NoSuchAlgorithmException;
+import java.security.PublicKey;
+import java.security.SecureRandom;
+import java.security.interfaces.ECPublicKey;
+import java.security.interfaces.RSAPublicKey;
+import java.security.spec.ECFieldFp;
+import java.security.spec.ECGenParameterSpec;
+import java.security.spec.ECParameterSpec;
+import java.security.spec.ECPoint;
+import java.security.spec.ECPublicKeySpec;
+import java.security.spec.InvalidKeySpecException;
+import java.security.spec.RSAPublicKeySpec;
+import javax.crypto.interfaces.DHPrivateKey;
+import javax.crypto.interfaces.DHPublicKey;
+import javax.crypto.spec.DHParameterSpec;
+import javax.crypto.spec.DHPublicKeySpec;
+
+/**
+ * Utility class containing static factory methods for a simple protobuf based representation of
+ * EC public keys that is intended for use with the SecureMessage library.
+ *
+ * N.B.: Requires the availability of an EC security provider supporting the NIST P-256 curve.
+ *
+ */
+public class PublicKeyProtoUtil {
+
+  private PublicKeyProtoUtil() {}  // Do not instantiate
+
+  /**
+   * Caches state about whether the current platform supports Elliptic Curve algorithms.
+   */
+  private static final Boolean IS_LEGACY_CRYPTO_REQUIRED = determineIfLegacyCryptoRequired();
+
+  private static final BigInteger ONE = new BigInteger("1");
+  private static final BigInteger TWO = new BigInteger("2");
+
+  /**
+   * Name for Elliptic Curve cryptography algorithm suite, used by the security provider. If the
+   * security provider does not implement the specified algorithm, runtime errors will ensue.
+   */
+  private static final String EC_ALG = "EC";
+
+  /**
+   * A common name for the NIST P-256 curve, used by most Java security providers.
+   */
+  private static final String EC_P256_COMMON_NAME = "secp256r1";
+
+  /**
+   * A name the NIST P-256 curve, used by the OpenSSL Java security provider (e.g,. on Android).
+   */
+  private static final String EC_P256_OPENSSL_NAME = "prime256v1";
+
+  /**
+   * The {@link ECParameterSpec} for the NIST P-256 Elliptic Curve.
+   */
+  private static final ECParameterSpec EC_P256_PARAMS = isLegacyCryptoRequired() ? null :
+      ((ECPublicKey) generateEcP256KeyPair().getPublic()).getParams();
+
+  /**
+   * The prime {@code p} describing the field for the NIST P-256 curve.
+   */
+  private static final BigInteger EC_P256_P = isLegacyCryptoRequired() ? null :
+      ((ECFieldFp) EC_P256_PARAMS.getCurve().getField()).getP();
+
+  /**
+   * The coefficient {@code a} for the NIST P-256 curve.
+   */
+  private static final BigInteger EC_P256_A = isLegacyCryptoRequired() ? null :
+      EC_P256_PARAMS.getCurve().getA();
+
+  /**
+   * The coefficient {@code b} for the NIST P-256 curve.
+   */
+  private static final BigInteger EC_P256_B = isLegacyCryptoRequired() ? null :
+      EC_P256_PARAMS.getCurve().getB();
+
+  /**
+   * Maximum number of bytes in a 2's complement encoding of a NIST P-256 elliptic curve point.
+   */
+  private static final int MAX_P256_ENCODING_BYTES = 33;
+
+  /**
+   * The JCA name for the RSA cryptography suite.
+   */
+  private static final String RSA_ALG = "RSA";
+
+  private static final int RSA2048_MODULUS_BITS = 2048;
+
+  /**
+   * Maximum number of bytes in a 2's complement encoding of a 2048-bit RSA key.
+   */
+  private static final int MAX_RSA2048_ENCODING_BYTES = 257;
+
+  /**
+   * The JCA name for the Diffie-Hellman cryptography suite.
+   */
+  private static final String DH_ALG = "DH";
+
+  /**
+   * The prime from the 2048-bit MODP Group (group 14) described in RFC 3526, to be used for
+   * Diffie-Hellman computations. Use only if Elliptic Curve ciphers are unavailable.
+   */
+  public static final BigInteger DH_P = new BigInteger(
+      "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1" +
+      "29024E088A67CC74020BBEA63B139B22514A08798E3404DD" +
+      "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245" +
+      "E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED" +
+      "EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3D" +
+      "C2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F" +
+      "83655D23DCA3AD961C62F356208552BB9ED529077096966D" +
+      "670C354E4ABC9804F1746C08CA18217C32905E462E36CE3B" +
+      "E39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9" +
+      "DE2BCBF6955817183995497CEA956AE515D2261898FA0510" +
+      "15728E5A8AACAA68FFFFFFFFFFFFFFFF", 16);
+
+  /**
+   * The generator for the 2048-bit MODP Group (group 14) described in RFC 3526, to be used for
+   * Diffie-Hellman computations. Use only if Elliptic Curve ciphers are unavailable.
+   */
+  public static final BigInteger DH_G = TWO;
+
+  /**
+   * The size of the Diffie-Hellman exponent to use, in bits.
+   */
+  public static final int DH_LEN = 512;
+
+  /**
+   * Maximum number of bytes in a 2's complement encoding of a
+   * Diffie-Hellman key using {@link #DH_G}.
+   */
+  private static final int MAX_DH2048_ENCODING_BYTES = 257;
+
+  /**
+   * Version code for the Honeycomb release of Android, which is the first release supporting
+   * Elliptic Curve.
+   */
+  public static final int ANDROID_HONEYCOMB_SDK_INT = 11;
+
+  /**
+   * Encodes any supported {@link PublicKey} type as a {@link GenericPublicKey} proto message.
+   *
+   * @see SecureMessageProto constants (defined in the .proto file) for supported types
+   */
+  public static GenericPublicKey encodePublicKey(PublicKey pk) {
+    if (pk == null) {
+      throw new NullPointerException();
+    }
+    if (pk instanceof ECPublicKey) {
+      return GenericPublicKey.newBuilder()
+          .setType(SecureMessageProto.PublicKeyType.EC_P256)
+          .setEcP256PublicKey(encodeEcPublicKey(pk))
+          .build();
+    }
+    if (pk instanceof RSAPublicKey) {
+      return GenericPublicKey.newBuilder()
+          .setType(SecureMessageProto.PublicKeyType.RSA2048)
+          .setRsa2048PublicKey(encodeRsa2048PublicKey(pk))
+          .build();
+    }
+    if (pk instanceof DHPublicKey) {
+      return GenericPublicKey.newBuilder()
+          .setType(SecureMessageProto.PublicKeyType.DH2048_MODP)
+          .setDh2048PublicKey(encodeDh2048PublicKey(pk))
+          .build();
+    }
+    throw new IllegalArgumentException("Unsupported PublicKey type");
+  }
+
+  /**
+   * Encodes an {@link ECPublicKey} to an {@link EcP256PublicKey} proto message.
+   */
+  public static EcP256PublicKey encodeEcPublicKey(PublicKey pk) {
+    ECPublicKey epk = pkToECPublicKey(pk);
+    return EcP256PublicKey.newBuilder()
+        .setX(extractX(epk))
+        .setY(extractY(epk))
+        .build();
+  }
+
+  /**
+   * Encodes a 2048-bit {@link RSAPublicKey} to an {@link SimpleRsaPublicKey} proto message.
+   */
+  public static SimpleRsaPublicKey encodeRsa2048PublicKey(PublicKey pk) {
+    RSAPublicKey rpk = pkToRSAPublicKey(pk);
+    return SimpleRsaPublicKey.newBuilder()
+        .setN(ByteString.copyFrom(rpk.getModulus().toByteArray()))
+        .setE(rpk.getPublicExponent().intValue())
+        .build();
+  }
+
+  /**
+   * Encodes a 2048-bit {@link DhPublicKey} using the {@link #DH_G} group to a
+   * {@link DhPublicKey} proto message.
+   */
+  public static DhPublicKey encodeDh2048PublicKey(PublicKey pk) {
+    DHPublicKey dhpk = pkToDHPublicKey(pk);
+    return DhPublicKey.newBuilder()
+        .setY(ByteString.copyFrom(dhpk.getY().toByteArray()))
+        .build();
+  }
+
+  /**
+   * Extracts a {@link PublicKey} from an {@link GenericPublicKey} proto message.
+   *
+   * @throws InvalidKeySpecException if the input is not a valid and/or supported public key type
+   */
+  public static PublicKey parsePublicKey(GenericPublicKey gpk) throws InvalidKeySpecException {
+    if (!gpk.hasType()) {
+      // "required" means nothing in micro proto land. We have to check this ourselves.
+      throw new InvalidKeySpecException("GenericPublicKey.type is a required field");
+    }
+    switch (gpk.getType()) {
+      case EC_P256:
+        if (!gpk.hasEcP256PublicKey()) {
+          break;
+        }
+        return parseEcPublicKey(gpk.getEcP256PublicKey());
+      case RSA2048:
+        if (!gpk.hasRsa2048PublicKey()) {
+          break;
+        }
+        return parseRsa2048PublicKey(gpk.getRsa2048PublicKey());
+      case DH2048_MODP:
+        if (!gpk.hasDh2048PublicKey()) {
+          break;
+        }
+        return parseDh2048PublicKey(gpk.getDh2048PublicKey());
+      default:
+        throw new InvalidKeySpecException("Unsupported GenericPublicKey type: " + gpk.getType());
+    }
+    throw new InvalidKeySpecException("key object is missing for key type: " + gpk.getType());
+  }
+
+  /**
+   * Extracts a {@link ECPublicKey} from an {@link EcP256PublicKey} proto message.
+   *
+   * @throws InvalidKeySpecException if the input is not a valid NIST P-256 public key or if
+   *   this platform does not support Elliptic Curve keys
+   */
+  public static ECPublicKey parseEcPublicKey(EcP256PublicKey p256pk)
+      throws InvalidKeySpecException {
+    if (!p256pk.hasX() || !p256pk.hasY()) {
+      throw new InvalidKeySpecException("Key is missing a required coordinate");
+    }
+    if (isLegacyCryptoRequired()) {
+      throw new InvalidKeySpecException("Elliptic Curve keys not supported on this platform");
+    }
+    byte[] encodedX = p256pk.getX().toByteArray();
+    byte[] encodedY = p256pk.getY().toByteArray();
+    try {
+      validateEcP256CoordinateEncoding(encodedX);
+      validateEcP256CoordinateEncoding(encodedY);
+      BigInteger wX = new BigInteger(encodedX);
+      BigInteger wY = new BigInteger(encodedY);
+      validateEcP256CurvePoint(wX, wY);
+      return (ECPublicKey) KeyFactory.getInstance(EC_ALG).generatePublic(
+          new ECPublicKeySpec(new ECPoint(wX, wY), EC_P256_PARAMS));
+    } catch (NoSuchAlgorithmException e) {
+      throw new RuntimeException(e);
+    }
+  }
+
+  /**
+   * Extracts a {@link RSAPublicKey} from an {@link SimpleRsaPublicKey} proto message.
+   *
+   * @throws InvalidKeySpecException when the input RSA public key is invalid
+   */
+  public static RSAPublicKey parseRsa2048PublicKey(SimpleRsaPublicKey pk)
+      throws InvalidKeySpecException {
+    if (!pk.hasN()) {
+      throw new InvalidKeySpecException("required field is missing");
+    }
+    byte[] encodedN = pk.getN().toByteArray();
+    validateSimpleRsaEncoding(encodedN);
+    BigInteger n = new BigInteger(encodedN);
+    if (n.bitLength() != RSA2048_MODULUS_BITS) {
+      throw new InvalidKeySpecException();
+    }
+    BigInteger e = BigInteger.valueOf(pk.getE());
+    try {
+      return (RSAPublicKey) KeyFactory.getInstance(RSA_ALG).generatePublic(
+          new RSAPublicKeySpec(n, e));
+    } catch (NoSuchAlgorithmException e1) {
+      throw new AssertionError(e1);  // Should never happen
+    }
+  }
+
+  /**
+   * Extracts a {@link DHPublicKey} from an {@link DhPublicKey} proto message.
+   *
+   * @throws InvalidKeySpecException when the input DH public key is invalid
+   */
+  @SuppressInsecureCipherModeCheckerPendingReview // b/32143855
+  public static DHPublicKey parseDh2048PublicKey(DhPublicKey pk) throws InvalidKeySpecException {
+    if (!pk.hasY()) {
+      throw new InvalidKeySpecException("required field is missing");
+    }
+    byte[] encodedY = pk.getY().toByteArray();
+    validateDhEncoding(encodedY);
+    BigInteger y;
+    try {
+      y = new BigInteger(encodedY);
+    } catch (NumberFormatException e) {
+      throw new InvalidKeySpecException();
+    }
+    validateDhGroupElement(y);
+    try {
+      return (DHPublicKey) KeyFactory.getInstance(DH_ALG).generatePublic(
+          new DHPublicKeySpec(y, DH_P, DH_G));
+    } catch (NoSuchAlgorithmException e) {
+      throw new AssertionError(e);  // Should never happen
+    }
+  }
+
+  /**
+   * @return a freshly generated NIST P-256 Elliptic Curve key pair.
+   */
+  public static KeyPair generateEcP256KeyPair() {
+    return getEcKeyGen().generateKeyPair();
+  }
+
+  /**
+   * @return a freshly generated 2048-bit RSA key pair.
+   */
+  public static KeyPair generateRSA2048KeyPair() {
+    return getRsaKeyGen().generateKeyPair();
+  }
+
+  /**
+   * @return a freshly generated Diffie-Hellman key pair for the 2048-bit group
+   *   described by {@link #DH_G}
+   */
+  public static KeyPair generateDh2048KeyPair() {
+    try {
+      return getDhKeyGen().generateKeyPair();
+    } catch (InvalidAlgorithmParameterException e) {
+      // Construct an appropriate KeyPair manually, since this platform refuses to do it for us
+      DHParameterSpec spec = new DHParameterSpec(DH_P, DH_G);
+      BigInteger x = new BigInteger(DH_LEN, new SecureRandom());
+      DHPrivateKey privateKey = new DHPrivateKeyShim(x, spec);
+      DHPublicKey publicKey = new DHPublicKeyShim(DH_G.modPow(x, DH_P), spec);
+      return new KeyPair(publicKey, privateKey);
+    }
+  }
+
+  /**
+   * A lightweight encoding for a {@link DHPrivateKey}. Strongly recommended over attempting to use
+   * {@link DHPrivateKey#getEncoded()}, but not compatible with the standard encoding.
+   *
+   * @see #parseDh2048PrivateKey(byte[])
+   */
+  public static byte[] encodeDh2048PrivateKey(DHPrivateKey sk) {
+    return sk.getX().toByteArray();
+  }
+
+  /**
+   * Parses a {@link DHPrivateKey} encoded with {@link #encodeDh2048PrivateKey(DHPrivateKey)}.
+   */
+  public static DHPrivateKey parseDh2048PrivateKey(byte[] encodedX)
+      throws InvalidKeySpecException {
+    validateDhEncoding(encodedX);  // Could be stricter for x, but should be fine to use this
+    BigInteger x;
+    try {
+      x = new BigInteger(encodedX);
+    } catch (NumberFormatException e) {
+      throw new InvalidKeySpecException();
+    }
+    validateDhGroupElement(x);  // Again, this validation should be good enough
+    return new DHPrivateKeyShim(x, new DHParameterSpec(DH_P, DH_G));
+  }
+
+  /**
+   * @throws InvalidKeySpecException if point ({@code x},{@code y}) isn't on the NIST P-256 curve
+   */
+  private static void validateEcP256CurvePoint(BigInteger x, BigInteger y)
+      throws InvalidKeySpecException {
+    if ((x.signum() == -1) || (y.signum() == -1)) {
+      throw new InvalidKeySpecException("Point encoding must use only non-negative integers");
+    }
+
+    BigInteger p = EC_P256_P;
+    if ((x.compareTo(p) >= 0) || (y.compareTo(p) >= 0)) {
+      throw new InvalidKeySpecException("Point lies outside of the expected field");
+    }
+
+    // Points on the curve satisfy y^2 = x^3 + ax + b  (mod p)
+    BigInteger lhs = squareMod(y, p);
+    BigInteger rhs = squareMod(x, p).add(EC_P256_A) // = (x^2 + a)
+        .multiply(x).mod(p) // = x(x^2 + a) = x^3 + ax
+        .add(EC_P256_B) // = x^3 + ax + b
+        .mod(p);
+    if (!lhs.equals(rhs)) {
+      throw new InvalidKeySpecException("Point does not lie on the expected curve");
+    }
+  }
+
+  /**
+   * @return value of {@code x}^2 (mod {@code p})
+   */
+  private static BigInteger squareMod(BigInteger x, BigInteger p) {
+    return x.multiply(x).mod(p);
+  }
+
+  /**
+   * @throws InvalidKeySpecException if the coordinate is too large for a 256-bit curve
+   */
+  private static void validateEcP256CoordinateEncoding(byte[] p) throws InvalidKeySpecException {
+    if ((p.length == 0)
+        || (p.length > MAX_P256_ENCODING_BYTES)
+        || (p.length == MAX_P256_ENCODING_BYTES && p[0] != 0)) {
+      throw new InvalidKeySpecException();  // Intentionally vague for security reasons
+    }
+  }
+
+  /**
+   * @throws InvalidKeySpecException if the input is too large for a 2048-bit RSA modulus
+   */
+  private static void validateSimpleRsaEncoding(byte[] n) throws InvalidKeySpecException {
+    if (n.length == 0 || n.length > MAX_RSA2048_ENCODING_BYTES) {
+      throw new InvalidKeySpecException();
+    }
+  }
+
+  /**
+   * @throws InvalidKeySpecException if the public key is too large for a 2048-bit DH group
+   */
+  private static void validateDhEncoding(byte[] y) throws InvalidKeySpecException {
+    if (y.length == 0 || y.length > MAX_DH2048_ENCODING_BYTES) {
+      throw new InvalidKeySpecException();
+    }
+  }
+
+  /**
+   * @throws InvalidKeySpecException if {@code y} is not a valid Diffie-Hellman public key
+   */
+  private static void validateDhGroupElement(BigInteger y) throws InvalidKeySpecException {
+    // Check that 1 < y < p -1
+    if ((y.compareTo(ONE) < 1) || (y.compareTo(DH_P.subtract(ONE)) > -1)) {
+      throw new InvalidKeySpecException();
+    }
+  }
+
+  private static ByteString extractY(ECPublicKey epk) {
+    return ByteString.copyFrom(epk.getW().getAffineY().toByteArray());
+  }
+
+  private static ByteString extractX(ECPublicKey epk) {
+    return ByteString.copyFrom(epk.getW().getAffineX().toByteArray());
+  }
+
+  private static ECPublicKey pkToECPublicKey(PublicKey pk) {
+    if (pk == null) {
+      throw new NullPointerException();
+    }
+    if (!(pk instanceof ECPublicKey)) {
+      throw new IllegalArgumentException("Not an EC Public Key");
+    }
+    return (ECPublicKey) pk;
+  }
+
+  private static RSAPublicKey pkToRSAPublicKey(PublicKey pk) {
+    if (pk == null) {
+      throw new NullPointerException();
+    }
+    if (!(pk instanceof RSAPublicKey)) {
+      throw new IllegalArgumentException("Not an RSA Public Key");
+    }
+    return (RSAPublicKey) pk;
+  }
+
+  private static DHPublicKey pkToDHPublicKey(PublicKey pk) {
+    if (pk == null) {
+      throw new NullPointerException();
+    }
+    if (!(pk instanceof DHPublicKey)) {
+      throw new IllegalArgumentException("Not a DH Public Key");
+    }
+    return (DHPublicKey) pk;
+  }
+
+  /**
+   * @return an EC {@link KeyPairGenerator} object initialized for NIST P-256.
+   */
+  private static KeyPairGenerator getEcKeyGen() {
+    KeyPairGenerator keygen;
+    try {
+      keygen = KeyPairGenerator.getInstance(EC_ALG);
+    } catch (NoSuchAlgorithmException e) {
+      throw new RuntimeException(e);
+    }
+    try {
+      // Try using the OpenSSL provider first, since we prefer it over BouncyCastle
+      keygen.initialize(new ECGenParameterSpec(EC_P256_OPENSSL_NAME));
+      return keygen;
+    } catch (InvalidAlgorithmParameterException e) {
+      // Try another name for NIST P-256
+    }
+    try {
+      keygen.initialize(new ECGenParameterSpec(EC_P256_COMMON_NAME));
+      return keygen;
+    } catch (InvalidAlgorithmParameterException e) {
+      throw new RuntimeException("Unable to find the NIST P-256 curve");
+    }
+  }
+
+  /**
+   * @return an RSA {@link KeyPairGenerator} object initialized for 2048-bit keys.
+   */
+  private static KeyPairGenerator getRsaKeyGen() {
+    try {
+      KeyPairGenerator keygen = KeyPairGenerator.getInstance(RSA_ALG);
+      keygen.initialize(RSA2048_MODULUS_BITS);
+      return keygen;
+    } catch (NoSuchAlgorithmException e) {
+      throw new AssertionError(e);  // This should never happen
+    }
+  }
+
+  /**
+   * @return a DH {@link KeyPairGenerator} object initialized for the group described by {@link
+   *     #DH_G}.
+   * @throws InvalidAlgorithmParameterException on some platforms that don't support large DH groups
+   */
+  @SuppressInsecureCipherModeCheckerPendingReview // b/32143855
+  private static KeyPairGenerator getDhKeyGen() throws InvalidAlgorithmParameterException {
+    try {
+      KeyPairGenerator keygen = KeyPairGenerator.getInstance(DH_ALG);
+      keygen.initialize(new DHParameterSpec(DH_P, DH_G, DH_LEN));
+      return keygen;
+    } catch (NoSuchAlgorithmException e) {
+      throw new AssertionError(e);  // This should never happen
+    }
+  }
+
+  /**
+   * A lightweight shim class to enable the creation of {@link DHPublicKey} and {@link DHPrivateKey}
+   * objects that accept arbitrary {@link DHParameterSpec}s -- unfortunately, many platforms do
+   * not support using reasonably sized Diffie-Hellman groups any other way. For instance, see
+   * <a href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6521495">Java bug 6521495</a>.
+   */
+  public abstract static class DHKeyShim {
+
+    private BigInteger eitherXorY;
+    private DHParameterSpec params;
+
+    public DHKeyShim(BigInteger eitherXorY, DHParameterSpec params) {
+      this.eitherXorY = eitherXorY;
+      this.params = params;
+    }
+
+    public DHParameterSpec getParams() {
+      return params;
+    }
+
+    public String getAlgorithm() {
+      return "DH";
+    }
+
+    public String getFormat() {
+      return null;
+    }
+
+    public byte[] getEncoded() {
+      return null;
+    }
+
+    public BigInteger getX() {
+      return eitherXorY;
+    }
+
+    public BigInteger getY() {
+      return eitherXorY;
+    }
+  }
+
+  /**
+   * A simple {@link DHPublicKey} implementation.
+   *
+   * @see DHKeyShim
+   */
+  public static class DHPublicKeyShim extends DHKeyShim implements DHPublicKey {
+    public DHPublicKeyShim(BigInteger y, DHParameterSpec params) {
+      super(y, params);
+    }
+  }
+
+  /**
+   * A simple {@link DHPrivateKey} implementation.
+   *
+   * @see DHKeyShim
+   */
+  public static class DHPrivateKeyShim extends DHKeyShim implements DHPrivateKey {
+    public DHPrivateKeyShim(BigInteger x, DHParameterSpec params) {
+      super(x, params);
+    }
+  }
+
+  /**
+   * @return true if this platform does not support Elliptic Curve algorithms
+   */
+  public static boolean isLegacyCryptoRequired() {
+    return IS_LEGACY_CRYPTO_REQUIRED;
+  }
+
+  /**
+   * @return true if using the Elliptic Curve key generator fails on this platform
+   */
+  private static boolean determineIfLegacyCryptoRequired() {
+    try {
+      getEcKeyGen();
+    } catch (Exception e) {
+      return true;
+    }
+    return false;
+  }
+}
diff --git a/src/main/java/com/google/security/cryptauth/lib/securemessage/SecureMessageBuilder.java b/src/main/java/com/google/security/cryptauth/lib/securemessage/SecureMessageBuilder.java
new file mode 100644
index 0000000..f59ce4e
--- /dev/null
+++ b/src/main/java/com/google/security/cryptauth/lib/securemessage/SecureMessageBuilder.java
@@ -0,0 +1,277 @@
+/* Copyright 2018 Google LLC
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.google.security.cryptauth.lib.securemessage;
+
+import com.google.protobuf.ByteString;
+import com.google.security.cryptauth.lib.securemessage.CryptoOps.EncType;
+import com.google.security.cryptauth.lib.securemessage.CryptoOps.SigType;
+import com.google.security.cryptauth.lib.securemessage.SecureMessageProto.Header;
+import com.google.security.cryptauth.lib.securemessage.SecureMessageProto.HeaderAndBodyInternal;
+import com.google.security.cryptauth.lib.securemessage.SecureMessageProto.SecureMessage;
+import java.security.InvalidKeyException;
+import java.security.Key;
+import java.security.NoSuchAlgorithmException;
+import java.security.SecureRandom;
+import java.util.Arrays;
+import javax.annotation.Nullable;
+
+/**
+ * Builder for {@link SecureMessage} protos. Can be used to create either signed messages,
+ * or "signcrypted" (encrypted then signed) messages that include a tight binding between the
+ * ciphertext portion and a verification key identity.
+ *
+ * @see SecureMessageParser
+ */
+public class SecureMessageBuilder {
+  private ByteString publicMetadata;
+  private ByteString verificationKeyId;
+  private ByteString decryptionKeyId;
+  /**
+   * This data is never sent inside the protobufs, so the builder just saves it as a byte[].
+   */
+  private byte[] associatedData;
+
+  private SecureRandom rng;
+
+  public SecureMessageBuilder() {
+    reset();
+    this.rng = new SecureRandom();
+  }
+
+  /**
+   * Resets this {@link SecureMessageBuilder} instance to a blank configuration (and returns it).
+   */
+  public SecureMessageBuilder reset() {
+    this.publicMetadata = null;
+    this.verificationKeyId = null;
+    this.decryptionKeyId = null;
+    this.associatedData = null;
+    return this;
+  }
+
+  /**
+   * Optional metadata to be sent along with the header information in this {@link SecureMessage}.
+   * <p>
+   * Note that this value will be sent <em>UNENCRYPTED</em> in all cases.
+   * <p>
+   * Can be used with either cleartext or signcrypted messages, but is intended primarily for use
+   * with signcrypted messages.
+   */
+  public SecureMessageBuilder setPublicMetadata(byte[] publicMetadata) {
+    this.publicMetadata = ByteString.copyFrom(publicMetadata);
+    return this;
+  }
+
+  /**
+   * The recipient of the {@link SecureMessage} should be able to uniquely determine the correct
+   * verification key, given only this value.
+   * <p>
+   * Can be used with either cleartext or signcrypted messages. Setting this is mandatory for
+   * signcrypted messages using a public key {@link SigType}, in order to bind the encrypted
+   * body to a specific verification key.
+   * <p>
+   * Note that this value is sent <em>UNENCRYPTED</em> in all cases.
+   */
+  public SecureMessageBuilder setVerificationKeyId(byte[] verificationKeyId) {
+    this.verificationKeyId = ByteString.copyFrom(verificationKeyId);
+    return this;
+  }
+
+  /**
+   * To be used only with {@link #buildSignCryptedMessage(Key, SigType, Key, EncType, byte[])},
+   * this value is sent <em>UNENCRYPTED</em> as part of the header. It should be used by the
+   * recipient of the {@link SecureMessage} to identify an appropriate key to use for decrypting
+   * the message body.
+   */
+  public SecureMessageBuilder setDecryptionKeyId(byte[] decryptionKeyId) {
+    this.decryptionKeyId = ByteString.copyFrom(decryptionKeyId);
+    return this;
+  }
+
+  /**
+   * Additional data is "associated" with this {@link SecureMessage}, but will not be sent as
+   * part of it. The recipient of the {@link SecureMessage} will need to provide the same data in
+   * order to verify the message body. Setting this to {@code null} is equivalent to using an
+   * empty array (unlike the behavior of {@code VerificationKeyId} and {@code DecryptionKeyId}).
+   * <p>
+   * Note that the <em>size</em> (length in bytes) of the associated data will be sent in the
+   * <em>UNENCRYPTED</em> header information, even if you are using encryption.
+   * <p>
+   * If you will be using {@link #buildSignedCleartextMessage(Key, SigType, byte[])}, then anyone
+   * observing the {@link SecureMessage} may be able to infer this associated data via an
+   * "offline dictionary attack". That is, when no encryption is used, you will not be hiding this
+   * data simply because it is not being sent over the wire.
+   */
+  public SecureMessageBuilder setAssociatedData(@Nullable byte[] associatedData) {
+   this.associatedData = associatedData;
+   return this;
+  }
+
+  // @VisibleForTesting
+  SecureMessageBuilder setRng(SecureRandom rng) {
+    this.rng = rng;
+    return this;
+  }
+
+  /**
+   * Generates a signed {@link SecureMessage} with the payload {@code body} left
+   * <em>UNENCRYPTED</em>.
+   *
+   * <p>Note that if you have used {@link #setAssociatedData(byte[])}, the associated data will
+   * be subject to offline dictionary attacks if you use a public key {@link SigType}.
+   *
+   * <p>Doesn't currently support symmetric keys stored in a TPM (since we access the raw key).
+   *
+   * @see SecureMessageParser#parseSignedCleartextMessage(SecureMessage, Key, SigType)
+   */
+  public SecureMessage buildSignedCleartextMessage(Key signingKey, SigType sigType, byte[] body)
+          throws NoSuchAlgorithmException, InvalidKeyException {
+    if ((signingKey == null) || (sigType == null) || (body == null)) {
+      throw new NullPointerException();
+    }
+    if (decryptionKeyId != null) {
+      throw new IllegalStateException("Cannot set decryptionKeyId for a cleartext message");
+    }
+
+    byte[] headerAndBody = serializeHeaderAndBody(
+        buildHeader(sigType, EncType.NONE, null).toByteArray(), body);
+    return createSignedResult(signingKey, sigType, headerAndBody, associatedData);
+  }
+
+  /**
+   * Generates a signed and encrypted {@link SecureMessage}. If the signature type requires a public
+   * key, such as with ECDSA_P256_SHA256, then the caller <em>must</em> set a verification id using
+   * the {@link #setVerificationKeyId(byte[])} method. The verification key id will be bound to the
+   * encrypted {@code body}, preventing attacks that involve stripping the signature and then
+   * re-signing the encrypted {@code body} as if it was originally sent by the attacker.
+   *
+   * <p>
+   * It is safe to re-use one {@link javax.crypto.SecretKey} as both {@code signingKey} and
+   * {@code encryptionKey}, even if that key is also used for
+   * {@link #buildSignedCleartextMessage(Key, SigType, byte[])}. In fact, the resulting output
+   * encoding will be more compact when the same symmetric key is used for both.
+   *
+   * <p>
+   * Note that PublicMetadata and other header fields are left <em>UNENCRYPTED</em>.
+   *
+   * <p>
+   * Doesn't currently support symmetric keys stored in a TPM (since we access the raw key).
+   *
+   * @param encType <em>must not</em> be set to {@link EncType#NONE}
+   * @see SecureMessageParser#parseSignCryptedMessage(SecureMessage, Key, SigType, Key, EncType)
+   */
+  public SecureMessage buildSignCryptedMessage(
+      Key signingKey, SigType sigType, Key encryptionKey, EncType encType, byte[] body)
+          throws NoSuchAlgorithmException, InvalidKeyException {
+    if ((signingKey == null)
+        || (sigType == null)
+        || (encryptionKey == null)
+        || (encType == null)
+        || (body == null)) {
+      throw new NullPointerException();
+    }
+    if (encType == EncType.NONE) {
+      throw new IllegalArgumentException(encType + " not supported for encrypted messages");
+    }
+    if (sigType.isPublicKeyScheme() && (verificationKeyId == null)) {
+      throw new IllegalStateException(
+          "Must set a verificationKeyId when using public key signature with encryption");
+    }
+
+    byte[] iv = CryptoOps.generateIv(encType, rng);
+    byte[] header = buildHeader(sigType, encType, iv).toByteArray();
+
+    // We may or may not need an extra tag in front of the plaintext body
+    byte[] taggedBody;
+    // We will only sign the associated data when we don't tag the plaintext body
+    byte[] associatedDataToBeSigned;
+    if (taggedPlaintextRequired(signingKey, sigType, encryptionKey)) {
+      // Place a "tag" in front of the the plaintext message containing a digest of the header
+      taggedBody = CryptoOps.concat(
+          // Digest the header + any associated data, yielding a tag to be encrypted with the body.
+          CryptoOps.digest(CryptoOps.concat(header, associatedData)),
+          body);
+      associatedDataToBeSigned = null; // We already handled any associatedData via the tag
+    } else {
+      taggedBody = body;
+      associatedDataToBeSigned = associatedData;
+    }
+
+    // Compute the encrypted body, which binds the tag to the message inside the ciphertext
+    byte[] encryptedBody = CryptoOps.encrypt(encryptionKey, encType, rng, iv, taggedBody);
+
+    byte[] headerAndBody = serializeHeaderAndBody(header, encryptedBody);
+    return createSignedResult(signingKey, sigType, headerAndBody, associatedDataToBeSigned);
+  }
+
+  /**
+   * Indicates whether a "tag" is needed next to the plaintext body inside the ciphertext, to
+   * prevent the same ciphertext from being reused with someone else's signature on it.
+   */
+  static boolean taggedPlaintextRequired(Key signingKey, SigType sigType, Key encryptionKey) {
+    // We need a tag if different keys are being used to "sign" vs. encrypt
+    return sigType.isPublicKeyScheme()
+        || !Arrays.equals(signingKey.getEncoded(), encryptionKey.getEncoded());
+  }
+
+  /**
+   * @param iv IV or {@code null} if IV to be left unset in the Header
+   */
+  private Header buildHeader(SigType sigType, EncType encType, byte[] iv) {
+    Header.Builder result = Header.newBuilder()
+        .setSignatureScheme(sigType.getSigScheme())
+        .setEncryptionScheme(encType.getEncScheme());
+    if (verificationKeyId != null) {
+      result.setVerificationKeyId(verificationKeyId);
+    }
+    if (decryptionKeyId != null) {
+      result.setDecryptionKeyId(decryptionKeyId);
+    }
+    if (publicMetadata != null) {
+      result.setPublicMetadata(publicMetadata);
+    }
+    if (associatedData != null) {
+      result.setAssociatedDataLength(associatedData.length);
+    }
+    if (iv != null) {
+      result.setIv(ByteString.copyFrom(iv));
+    }
+    return result.build();
+  }
+
+  /**
+   * @param header a serialized representation of a {@link Header}
+   * @param body arbitrary payload data
+   * @return a serialized representation of a {@link SecureMessageProto.HeaderAndBody}
+   */
+  private byte[] serializeHeaderAndBody(byte[] header, byte[] body) {
+    return HeaderAndBodyInternal.newBuilder()
+        .setHeader(ByteString.copyFrom(header))
+        .setBody(ByteString.copyFrom(body))
+        .build()
+        .toByteArray();
+  }
+
+  private SecureMessage createSignedResult(
+      Key signingKey, SigType sigType, byte[] headerAndBody, @Nullable byte[] associatedData)
+      throws NoSuchAlgorithmException, InvalidKeyException {
+    byte[] sig =
+        CryptoOps.sign(sigType, signingKey, rng, CryptoOps.concat(headerAndBody, associatedData));
+    return SecureMessage.newBuilder()
+        .setHeaderAndBody(ByteString.copyFrom(headerAndBody))
+        .setSignature(ByteString.copyFrom(sig))
+        .build();
+  }
+}
diff --git a/src/main/java/com/google/security/cryptauth/lib/securemessage/SecureMessageParser.java b/src/main/java/com/google/security/cryptauth/lib/securemessage/SecureMessageParser.java
new file mode 100644
index 0000000..e1c60e3
--- /dev/null
+++ b/src/main/java/com/google/security/cryptauth/lib/securemessage/SecureMessageParser.java
@@ -0,0 +1,270 @@
+/* Copyright 2018 Google LLC
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package com.google.security.cryptauth.lib.securemessage;
+
+import com.google.protobuf.ByteString;
+import com.google.protobuf.InvalidProtocolBufferException;
+import com.google.security.cryptauth.lib.securemessage.CryptoOps.EncType;
+import com.google.security.cryptauth.lib.securemessage.CryptoOps.SigType;
+import com.google.security.cryptauth.lib.securemessage.SecureMessageProto.Header;
+import com.google.security.cryptauth.lib.securemessage.SecureMessageProto.HeaderAndBody;
+import com.google.security.cryptauth.lib.securemessage.SecureMessageProto.HeaderAndBodyInternal;
+import com.google.security.cryptauth.lib.securemessage.SecureMessageProto.SecureMessage;
+import java.security.InvalidAlgorithmParameterException;
+import java.security.InvalidKeyException;
+import java.security.Key;
+import java.security.NoSuchAlgorithmException;
+import java.security.SignatureException;
+import javax.annotation.Nullable;
+import javax.crypto.BadPaddingException;
+import javax.crypto.IllegalBlockSizeException;
+
+/**
+ * Utility class to parse and verify {@link SecureMessage} protos. Verifies the signature on the
+ * message, and decrypts "signcrypted" messages (while simultaneously verifying the signature).
+ *
+ * @see SecureMessageBuilder
+ */
+public class SecureMessageParser {
+
+  private SecureMessageParser() {}  // Do not instantiate
+
+  /**
+   * Extracts the {@link Header} component from a {@link SecureMessage} but <em>DOES NOT VERIFY</em>
+   * the signature when doing so. Callers should not trust the resulting output until after a
+   * subsequent {@code parse*()} call has succeeded.
+   *
+   * <p>The intention is to allow the caller to determine the type of the protocol message and which
+   * keys are in use, prior to attempting to verify (and possibly decrypt) the payload body.
+   */
+  public static Header getUnverifiedHeader(SecureMessage secmsg)
+      throws InvalidProtocolBufferException {
+    if (!secmsg.hasHeaderAndBody()) {
+      throw new InvalidProtocolBufferException("Missing header and body");
+    }
+    if (!HeaderAndBody.parseFrom(secmsg.getHeaderAndBody()).hasHeader()) {
+      throw new InvalidProtocolBufferException("Missing header");
+    }
+    Header result = HeaderAndBody.parseFrom(secmsg.getHeaderAndBody()).getHeader();
+    // Check that at least a signature scheme was set
+    if (!result.hasSignatureScheme()) {
+      throw new InvalidProtocolBufferException("Missing header field(s)");
+    }
+    // Check signature scheme is legal
+    try {
+      SigType.valueOf(result.getSignatureScheme());
+    } catch (IllegalArgumentException e) {
+      throw new InvalidProtocolBufferException("Corrupt/unsupported SignatureScheme");
+    }
+    // Check encryption scheme is legal
+    if (result.hasEncryptionScheme()) {
+      try {
+        EncType.valueOf(result.getEncryptionScheme());
+      } catch (IllegalArgumentException e) {
+        throw new InvalidProtocolBufferException("Corrupt/unsupported EncryptionScheme");
+      }
+    }
+    return result;
+  }
+
+  /**
+   * Parses a {@link SecureMessage} containing a cleartext payload body, and verifies the signature.
+   *
+   * @return the parsed {@link HeaderAndBody} pair (which is fully verified)
+   * @throws SignatureException if signature verification fails
+   * @see SecureMessageBuilder#buildSignedCleartextMessage(Key, SigType, byte[])
+   */
+  public static HeaderAndBody parseSignedCleartextMessage(
+      SecureMessage secmsg, Key verificationKey, SigType sigType)
+          throws NoSuchAlgorithmException, InvalidKeyException, SignatureException {
+    return parseSignedCleartextMessage(secmsg, verificationKey, sigType, null);
+  }
+
+  /**
+   * Parses a {@link SecureMessage} containing a cleartext payload body, and verifies the signature.
+   *
+   * @param associatedData optional associated data bound to the signature (but not in the message)
+   * @return the parsed {@link HeaderAndBody} pair (which is fully verified)
+   * @throws SignatureException if signature verification fails
+   * @see SecureMessageBuilder#buildSignedCleartextMessage(Key, SigType, byte[])
+   */
+  public static HeaderAndBody parseSignedCleartextMessage(
+      SecureMessage secmsg, Key verificationKey, SigType sigType, @Nullable byte[] associatedData)
+          throws NoSuchAlgorithmException, InvalidKeyException, SignatureException {
+    if ((secmsg == null) || (verificationKey == null) || (sigType == null)) {
+      throw new NullPointerException();
+    }
+    return verifyHeaderAndBody(
+        secmsg,
+        verificationKey,
+        sigType,
+        EncType.NONE,
+        associatedData,
+        false /* suppressAssociatedData is always false for signed cleartext */);
+  }
+
+  /**
+   * Parses a {@link SecureMessage} containing an encrypted payload body, extracting a decryption of
+   * the payload body and verifying the signature.
+   *
+   * @return the parsed {@link HeaderAndBody} pair (which is fully verified and decrypted)
+   * @throws SignatureException if signature verification fails
+   * @see SecureMessageBuilder#buildSignCryptedMessage(Key, SigType, Key, EncType, byte[])
+   */
+  public static HeaderAndBody parseSignCryptedMessage(
+      SecureMessage secmsg,
+      Key verificationKey,
+      SigType sigType,
+      Key decryptionKey,
+      EncType encType)
+    throws InvalidKeyException, NoSuchAlgorithmException, SignatureException {
+    return parseSignCryptedMessage(secmsg, verificationKey, sigType, decryptionKey, encType, null);
+  }
+
+  /**
+   * Parses a {@link SecureMessage} containing an encrypted payload body, extracting a decryption of
+   * the payload body and verifying the signature.
+   *
+   * @param associatedData optional associated data bound to the signature (but not in the message)
+   * @return the parsed {@link HeaderAndBody} pair (which is fully verified and decrypted)
+   * @throws SignatureException if signature verification fails
+   * @see SecureMessageBuilder#buildSignCryptedMessage(Key, SigType, Key, EncType, byte[])
+   */
+  public static HeaderAndBody parseSignCryptedMessage(
+      SecureMessage secmsg,
+      Key verificationKey,
+      SigType sigType,
+      Key decryptionKey,
+      EncType encType,
+      @Nullable byte[] associatedData)
+          throws InvalidKeyException, NoSuchAlgorithmException, SignatureException {
+    if ((secmsg == null)
+        || (verificationKey == null)
+        || (sigType == null)
+        || (decryptionKey == null)
+        || (encType == null)) {
+      throw new NullPointerException();
+    }
+    if (encType == EncType.NONE) {
+      throw new SignatureException("Not a signcrypted message");
+    }
+
+    boolean tagRequired =
+        SecureMessageBuilder.taggedPlaintextRequired(verificationKey, sigType, decryptionKey);
+    HeaderAndBody headerAndEncryptedBody;
+    headerAndEncryptedBody = verifyHeaderAndBody(
+        secmsg,
+        verificationKey,
+        sigType,
+        encType,
+        associatedData,
+        tagRequired /* suppressAssociatedData if it is handled by the tag instead */);
+
+    byte[] rawDecryptedBody;
+    Header header = headerAndEncryptedBody.getHeader();
+    if (!header.hasIv()) {
+      throw new SignatureException();
+    }
+    try {
+      rawDecryptedBody = CryptoOps.decrypt(
+          decryptionKey, encType, header.getIv().toByteArray(),
+          headerAndEncryptedBody.getBody().toByteArray());
+    } catch (InvalidAlgorithmParameterException e) {
+      throw new SignatureException();
+    } catch (IllegalBlockSizeException e) {
+      throw new SignatureException();
+    } catch (BadPaddingException e) {
+      throw new SignatureException();
+    }
+
+    if (!tagRequired) {
+      // No tag expected, so we're all done
+      return HeaderAndBody.newBuilder(headerAndEncryptedBody)
+          .setBody(ByteString.copyFrom(rawDecryptedBody))
+          .build();
+    }
+
+    // Verify the tag that binds the ciphertext to the header, and remove it
+    byte[] headerBytes;
+    try {
+      headerBytes =
+          HeaderAndBodyInternal.parseFrom(secmsg.getHeaderAndBody()).getHeader().toByteArray();
+    } catch (InvalidProtocolBufferException e) {
+      // This shouldn't happen, but throw it up just in case
+      throw new SignatureException(e);
+    }
+    boolean verifiedBinding = false;
+    byte[] expectedTag = CryptoOps.digest(CryptoOps.concat(headerBytes, associatedData));
+    if (rawDecryptedBody.length >= CryptoOps.DIGEST_LENGTH) {
+      byte[] actualTag = CryptoOps.subarray(rawDecryptedBody, 0, CryptoOps.DIGEST_LENGTH);
+      if (CryptoOps.constantTimeArrayEquals(actualTag, expectedTag)) {
+        verifiedBinding = true;
+      }
+    }
+    if (!verifiedBinding) {
+      throw new SignatureException();
+    }
+
+    int bodyLen = rawDecryptedBody.length - CryptoOps.DIGEST_LENGTH;
+    return HeaderAndBody.newBuilder(headerAndEncryptedBody)
+        // Remove the tag and set the plaintext body
+        .setBody(ByteString.copyFrom(rawDecryptedBody, CryptoOps.DIGEST_LENGTH, bodyLen))
+        .build();
+  }
+
+  private static HeaderAndBody verifyHeaderAndBody(
+      SecureMessage secmsg,
+      Key verificationKey,
+      SigType sigType,
+      EncType encType,
+      @Nullable byte[] associatedData,
+      boolean suppressAssociatedData /* in case it is in the tag instead */)
+      throws NoSuchAlgorithmException, InvalidKeyException, SignatureException {
+    if (!secmsg.hasHeaderAndBody() || !secmsg.hasSignature()) {
+      throw new SignatureException("Signature failed verification");
+    }
+    byte[] signature = secmsg.getSignature().toByteArray();
+    byte[] data = secmsg.getHeaderAndBody().toByteArray();
+    byte[] signedData = suppressAssociatedData ? data : CryptoOps.concat(data, associatedData);
+
+    // Try not to leak the specific reason for verification failures, due to security concerns.
+    boolean verified = CryptoOps.verify(verificationKey, sigType, signature, signedData);
+    HeaderAndBody result = null;
+    try {
+      result = HeaderAndBody.parseFrom(secmsg.getHeaderAndBody());
+      // Even if declared required, micro proto doesn't throw an exception if fields are not present
+      if (!result.hasHeader() || !result.hasBody()) {
+        throw new SignatureException("Signature failed verification");
+      }
+      verified &= (result.getHeader().getSignatureScheme() == sigType.getSigScheme());
+      verified &= (result.getHeader().getEncryptionScheme() == encType.getEncScheme());
+      // Check that either a decryption operation is expected, or no DecryptionKeyId is set.
+      verified &= (encType != EncType.NONE) || !result.getHeader().hasDecryptionKeyId();
+      // If encryption was used, check that either we are not using a public key signature or a
+      // VerificationKeyId was set (as is required for public key based signature + encryption).
+      verified &= (encType == EncType.NONE) || !sigType.isPublicKeyScheme() ||
+          result.getHeader().hasVerificationKeyId();
+      int associatedDataLength = associatedData == null ? 0 : associatedData.length;
+      verified &= (result.getHeader().getAssociatedDataLength() == associatedDataLength);
+    } catch (InvalidProtocolBufferException e) {
+      verified = false;
+    }
+
+    if (verified) {
+      return result;
+    }
+    throw new SignatureException("Signature failed verification");
+  }
+}
diff --git a/src/main/proto/device_to_device_messages.proto b/src/main/proto/device_to_device_messages.proto
new file mode 100644
index 0000000..c3bd2cf
--- /dev/null
+++ b/src/main/proto/device_to_device_messages.proto
@@ -0,0 +1,83 @@
+/* Copyright 2018 Google LLC
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+syntax = "proto2";
+
+package securegcm;
+
+option java_package = "com.google.security.cryptauth.lib.securegcm";
+option java_outer_classname = "DeviceToDeviceMessagesProto";
+option objc_class_prefix = "SGCM";
+
+import "securemessage.proto";
+
+// Used by protocols between devices
+message DeviceToDeviceMessage {
+  // the payload of the message
+  optional bytes message = 1;
+
+  // the sequence number of the message - must be increasing.
+  optional int32 sequence_number = 2;
+}
+
+// sent as the first message from initiator to responder
+// in an unauthenticated Diffie-Hellman Key Exchange
+message InitiatorHello {
+  // The session public key to send to the responder
+  optional securemessage.GenericPublicKey public_dh_key = 1;
+
+  // The protocol version
+  optional int32 protocol_version = 2 [default = 0];
+}
+
+// sent inside the header of the first message from the responder to the
+// initiator in an unauthenticated Diffie-Hellman Key Exchange
+message ResponderHello {
+  // The session public key to send to the initiator
+  optional securemessage.GenericPublicKey public_dh_key = 1;
+
+  // The protocol version
+  optional int32 protocol_version = 2 [default = 0];
+}
+
+// Type of curve
+enum Curve {
+  ED_25519 = 1;
+}
+
+// A convenience proto for encoding curve points in affine representation
+message EcPoint {
+  required Curve curve = 1;
+
+  // x and y are encoded in big-endian two's complement
+  // client MUST verify (x,y) is a valid point on the specified curve
+  required bytes x = 2;
+  required bytes y = 3;
+}
+
+message SpakeHandshakeMessage {
+  // Each flow in the protocol bumps this counter
+  optional int32 flow_number = 1;
+
+  // Some (but not all) SPAKE flows send a point on an elliptic curve
+  optional EcPoint ec_point = 2;
+
+  // Some (but not all) SPAKE flows send a hash value
+  optional bytes hash_value = 3;
+
+  // The last flow of a SPAKE protocol can send an optional payload,
+  // since the key exchange is already complete on the sender's side.
+  optional bytes payload = 4;
+}
+
diff --git a/src/main/proto/passwordless_auth_payloads.proto b/src/main/proto/passwordless_auth_payloads.proto
new file mode 100644
index 0000000..054d91c
--- /dev/null
+++ b/src/main/proto/passwordless_auth_payloads.proto
@@ -0,0 +1,38 @@
+/* Copyright 2018 Google LLC
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+syntax = "proto2";
+
+package securegcm;
+
+option java_package = "com.google.security.cryptauth.lib.securegcm";
+option java_outer_classname = "SecureGcmPasswordlessAuthProto";
+option objc_class_prefix = "SGCM";
+
+
+message IdentityAssertion {
+
+  // Browser data contains the challenge, origin, etc.
+  optional bytes browser_data_hash = 1;
+
+  // A counter that we expect to increase.
+  optional int64 counter = 2;
+
+  // An integer encoding whether the user actively approved this assertion,
+  // or whether the phone auto-issued the assertion.
+  // Possible values are:
+  // 1: User explicitly approved the login.
+  // 0: Phone approved login without consulting the user.
+  optional int32 user_approval = 3;
+}
diff --git a/src/main/proto/proximity_payloads.proto b/src/main/proto/proximity_payloads.proto
new file mode 100644
index 0000000..9c2f1ec
--- /dev/null
+++ b/src/main/proto/proximity_payloads.proto
@@ -0,0 +1,58 @@
+/* Copyright 2018 Google LLC
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+syntax = "proto2";
+
+import "securegcm.proto";
+
+package securegcm;
+
+option java_package = "com.google.security.cryptauth.lib.securegcm";
+option java_outer_classname = "SecureGcmProximityAuthProto";
+option objc_class_prefix = "SGCM";
+
+// Message used when one device wants to initiate a Proximity Auth pairing with another device
+// DEPRECATED. DO NOT USE
+message CloudToDeviceProximityAuthPairing {
+// The name or description of the device that wants to pair with another
+// personal device of the user.  This is a string that may be shown to the
+// user or may be kept in logs.
+  optional string initiating_device_name = 1;
+
+  // The original device's Bluetooth address in human readable form
+  // (e.g., <code>AA:BB:CC:DD:EE:FF</code>)
+  optional string initiating_device_bt_address = 2;
+
+  // A symmetric key that was generated by the original device.
+  optional bytes ephemeral_symmetric_key = 3;
+
+  // Optional additional metadata that the initiating device can choose to send.
+  // Used for quick protocol iteration.
+  optional bytes additional_metadata = 4;
+}
+
+// Message to push to eligible unlock devices so that they can contact the
+// device to be unlocked. Used by FindEligibleUnlockDevicesRequest, with
+// PayloadType = DEVICE_PROXIMITY_CALLBACK.
+message DeviceProximityCallback {
+  // Required. The bluetooth MAC address that should be contacted by the unlock
+  // device.
+  optional string callback_bluetooth_address = 1;
+
+  // Required. The type of the device that triggered this callback to be sent.
+  optional DeviceType source_device_type = 2;
+
+  // The version of the setup protocol that the source device expects to use.
+  optional int32 protocol_version = 3;
+}
diff --git a/src/main/proto/securegcm.proto b/src/main/proto/securegcm.proto
new file mode 100644
index 0000000..b7dae25
--- /dev/null
+++ b/src/main/proto/securegcm.proto
@@ -0,0 +1,307 @@
+/* Copyright 2018 Google LLC
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+syntax = "proto2";
+
+package securegcm;
+
+option java_package = "com.google.security.cryptauth.lib.securegcm";
+option java_outer_classname = "SecureGcmProto";
+option objc_class_prefix = "SGCM";
+
+// Message used only during enrollment
+// Field numbers should be kept in sync with DeviceInfo in:
+//   java/com/google/security/cryptauth/backend/services/common/common.proto
+message GcmDeviceInfo {
+  // This field's name does not match the one in DeviceInfo for legacy reasons.
+  // Consider using long_device_id and device_type instead when enrolling
+  // non-android devices.
+  optional fixed64 android_device_id = 1;
+
+  // Used for device_address of DeviceInfo field 2, but for GCM capable devices.
+  optional bytes gcm_registration_id = 102;
+
+  // Used for device_address of DeviceInfo field 2, but for iOS devices.
+  optional bytes apn_registration_id = 202;
+
+  // Does the user have notifications enabled for the given device address.
+  optional bool notification_enabled = 203 [ default = true ];
+
+  // Used for device_address of DeviceInfo field 2, a Bluetooth Mac address for
+  // the device (e.g., to be used with EasyUnlock)
+  optional string bluetooth_mac_address = 302;
+
+  // SHA-256 hash of the device master key (from the key exchange).
+  // Differs from DeviceInfo field 3, which contains the actual master key.
+  optional bytes device_master_key_hash = 103;
+
+  // A SecureMessage.EcP256PublicKey
+  required bytes user_public_key = 4;
+
+  // device's model name
+  // (e.g., an android.os.Build.MODEL or UIDevice.model)
+  optional string device_model = 7;
+
+  // device's locale
+  optional string locale = 8;
+
+  // The handle for user_public_key (and implicitly, a master key)
+  optional bytes key_handle = 9;
+
+  // The initial counter value for the device, sent by the device
+  optional int64 counter = 12 [default = 0];
+
+  // The Operating System version on the device
+  // (e.g., an android.os.Build.DISPLAY or UIDevice.systemVersion)
+  optional string device_os_version = 13;
+
+  // The Operating System version number on the device
+  // (e.g., an android.os.Build.VERSION.SDK_INT)
+  optional int64 device_os_version_code = 14;
+
+  // The Operating System release on the device
+  // (e.g., an android.os.Build.VERSION.RELEASE)
+  optional string device_os_release = 15;
+
+  // The Operating System codename on the device
+  // (e.g., an android.os.Build.VERSION.CODENAME or UIDevice.systemName)
+  optional string device_os_codename = 16;
+
+  // The software version running on the device
+  // (e.g., Authenticator app version string)
+  optional string device_software_version = 17;
+
+  // The software version number running on the device
+  // (e.g., Authenticator app version code)
+  optional int64 device_software_version_code = 18;
+
+  // Software package information if applicable
+  // (e.g., com.google.android.apps.authenticator2)
+  optional string device_software_package = 19;
+
+  // Size of the display in thousandths of an inch (e.g., 7000 mils = 7 in)
+  optional int32 device_display_diagonal_mils = 22;
+
+  // For Authzen capable devices, their Authzen protocol version
+  optional int32 device_authzen_version = 24;
+
+  // Not all devices have device identifiers that fit in 64 bits.
+  optional bytes long_device_id = 29;
+
+  // The device manufacturer name
+  // (e.g., android.os.Build.MANUFACTURER)
+  optional string device_manufacturer = 31;
+
+  // Used to indicate which type of device this is.
+  optional DeviceType device_type = 32 [ default = ANDROID ];
+
+  // Fields corresponding to screenlock type/features and hardware features
+  // should be numbered in the 400 range.
+
+  // Is this device using  a secure screenlock (e.g., pattern or pin unlock)
+  optional bool using_secure_screenlock = 400 [ default = false ];
+
+  // Is auto-unlocking the screenlock (e.g., when at "home") supported?
+  optional bool auto_unlock_screenlock_supported = 401 [ default = false ];
+
+  // Is auto-unlocking the screenlock (e.g., when at "home") enabled?
+  optional bool auto_unlock_screenlock_enabled = 402 [ default = false ];
+
+  // Does the device have a Bluetooth (classic) radio?
+  optional bool bluetooth_radio_supported = 403 [ default = false ];
+
+  // Is the Bluetooth (classic) radio on?
+  optional bool bluetooth_radio_enabled = 404 [ default = false ];
+
+  // Does the device hardware support a mobile data connection?
+  optional bool mobile_data_supported = 405 [ default = false ];
+
+  // Does the device support tethering?
+  optional bool tethering_supported = 406 [ default = false ];
+
+  // Does the device have a BLE radio?
+  optional bool ble_radio_supported = 407 [ default = false ];
+
+  // Is the device a "Pixel Experience" Android device?
+  optional bool pixel_experience = 408 [ default = false ];
+
+  // Is the device running in the ARC++ container on a chromebook?
+  optional bool arc_plus_plus = 409 [ default = false ];
+
+  // Is the value set in |using_secure_screenlock| reliable? On some Android
+  // devices, the platform API to get the screenlock state is not trustworthy.
+  // See b/32212161.
+  optional bool is_screenlock_state_flaky = 410 [ default = false ];
+
+  // A list of multi-device software features supported by the device.
+  repeated SoftwareFeature supported_software_features = 411;
+
+  // A list of multi-device software features currently enabled (active) on the
+  // device.
+  repeated SoftwareFeature enabled_software_features = 412;
+
+  // The enrollment session id this is sent with
+  optional bytes enrollment_session_id = 1000;
+
+  // A copy of the user's OAuth token
+  optional string oauth_token = 1001;
+}
+
+// This enum is used by iOS devices as values for device_display_diagonal_mils
+// in GcmDeviceInfo. There is no good way to calculate it on those devices.
+enum AppleDeviceDiagonalMils {
+  // This is the mils diagonal on an iPhone 5.
+  APPLE_PHONE = 4000;
+  // This is the mils diagonal on an iPad mini.
+  APPLE_PAD = 7900;
+}
+
+// This should be kept in sync with DeviceType in:
+// java/com/google/security/cryptauth/backend/services/common/common_enums.proto
+enum DeviceType {
+  UNKNOWN = 0;
+  ANDROID = 1;
+  CHROME = 2;
+  IOS = 3;
+  BROWSER = 4;
+  OSX = 5;
+}
+
+// MultiDevice features which may be supported and enabled on a device.
+enum SoftwareFeature {
+  UNKNOWN_FEATURE = 0;
+  BETTER_TOGETHER_HOST = 1;
+  BETTER_TOGETHER_CLIENT = 2;
+  EASY_UNLOCK_HOST = 3;
+  EASY_UNLOCK_CLIENT = 4;
+  MAGIC_TETHER_HOST = 5;
+  MAGIC_TETHER_CLIENT = 6;
+  SMS_CONNECT_HOST = 7;
+  SMS_CONNECT_CLIENT = 8;
+}
+
+// A list of "reasons" that can be provided for calling server-side APIs.
+// This is particularly important for calls that can be triggered by different
+// kinds of events. Please try to keep reasons as generic as possible, so that
+// codes can be re-used by various callers in a sensible fashion.
+enum InvocationReason {
+  REASON_UNKNOWN = 0;
+  // First run of the software package invoking this call
+  REASON_INITIALIZATION = 1;
+  // Ordinary periodic actions (e.g. monthly master key rotation)
+  REASON_PERIODIC = 2;
+  // Slow-cycle periodic action (e.g. yearly keypair rotation???)
+  REASON_SLOW_PERIODIC = 3;
+  // Fast-cycle periodic action (e.g. daily sync for Smart Lock users)
+  REASON_FAST_PERIODIC = 4;
+  // Expired state (e.g. expired credentials, or cached entries) was detected
+  REASON_EXPIRATION = 5;
+  // An unexpected protocol failure occurred (so attempting to repair state)
+  REASON_FAILURE_RECOVERY = 6;
+  // A new account has been added to the device
+  REASON_NEW_ACCOUNT = 7;
+  // An existing account on the device has been changed
+  REASON_CHANGED_ACCOUNT = 8;
+  // The user toggled the state of a feature (e.g. Smart Lock enabled via BT)
+  REASON_FEATURE_TOGGLED = 9;
+  // A "push" from the server caused this action (e.g. a sync tickle)
+  REASON_SERVER_INITIATED = 10;
+  // A local address change triggered this (e.g. GCM registration id changed)
+  REASON_ADDRESS_CHANGE = 11;
+  // A software update has triggered this
+  REASON_SOFTWARE_UPDATE = 12;
+  // A manual action by the user triggered this (e.g. commands sent via adb)
+  REASON_MANUAL = 13;
+  // A custom key has been invalidated on the device (e.g. screen lock is
+  // disabled).
+  REASON_CUSTOM_KEY_INVALIDATION = 14;
+  // Periodic action triggered by auth_proximity
+  REASON_PROXIMITY_PERIODIC = 15;
+}
+
+enum Type {
+  ENROLLMENT = 0;
+  TICKLE = 1;
+  TX_REQUEST = 2;
+  TX_REPLY = 3;
+  TX_SYNC_REQUEST = 4;
+  TX_SYNC_RESPONSE = 5;
+  TX_PING = 6;
+  DEVICE_INFO_UPDATE = 7;
+  TX_CANCEL_REQUEST = 8;
+
+  // DEPRECATED (can be re-used after Aug 2015)
+  PROXIMITYAUTH_PAIRING = 10;
+
+  // The kind of identity assertion generated by a "GCM V1" device (i.e.,
+  // an Android phone that has registered with us a public and a symmetric
+  // key)
+  GCMV1_IDENTITY_ASSERTION = 11;
+
+  // Device-to-device communications are protected by an unauthenticated
+  // Diffie-Hellman exchange. The InitiatorHello message is simply the
+  // initiator's public DH key, and is not encoded as a SecureMessage, so
+  // it doesn't have a tag.
+  // The ResponderHello message (which is sent by the responder
+  // to the initiator), on the other hand, carries a payload that is protected
+  // by the derived shared key. It also contains the responder's
+  // public DH key. ResponderHelloAndPayload messages have the
+  // DEVICE_TO_DEVICE_RESPONDER_HELLO tag.
+  DEVICE_TO_DEVICE_RESPONDER_HELLO_PAYLOAD = 12;
+
+  // Device-to-device communications are protected by an unauthenticated
+  // Diffie-Hellman exchange. Once the initiator and responder
+  // agree on a shared key (through Diffie-Hellman), they will use messages
+  // tagged with DEVICE_TO_DEVICE_MESSAGE to exchange data.
+  DEVICE_TO_DEVICE_MESSAGE = 13;
+
+  // Notification to let a device know it should contact a nearby device.
+  DEVICE_PROXIMITY_CALLBACK = 14;
+
+  // Device-to-device communications are protected by an unauthenticated
+  // Diffie-Hellman exchange. During device-to-device authentication, the first
+  // message from initiator (the challenge) is signed and put into the payload
+  // of the message sent back to the initiator.
+  UNLOCK_KEY_SIGNED_CHALLENGE = 15;
+
+  // Specialty (corp only) features
+  LOGIN_NOTIFICATION = 101;
+}
+
+message GcmMetadata {
+  required Type type = 1;
+  optional int32 version = 2 [default = 0];
+}
+
+message Tickle {
+  // Time after which this tickle should expire
+  optional fixed64 expiry_time = 1;
+}
+
+message LoginNotificationInfo {
+  // Time at which the server received the login notification request.
+  optional fixed64 creation_time = 2;
+
+  // Must correspond to user_id in LoginNotificationRequest, if set.
+  optional string email = 3;
+
+  // Host where the user's credentials were used to login, if meaningful.
+  optional string host = 4;
+
+  // Location from where the user's credentials were used, if meaningful.
+  optional string source = 5;
+
+  // Type of login, e.g. ssh, gnome-screensaver, or web.
+  optional string event_type = 6;
+}
diff --git a/src/main/proto/securemessage.proto b/src/main/proto/securemessage.proto
new file mode 100644
index 0000000..062e425
--- /dev/null
+++ b/src/main/proto/securemessage.proto
@@ -0,0 +1,124 @@
+/* Copyright 2018 Google LLC
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+// Proto definitions for SecureMessage format
+
+syntax = "proto2";
+
+package securemessage;
+option java_package = "com.google.security.cryptauth.lib.securemessage";
+option java_outer_classname = "SecureMessageProto";
+option objc_class_prefix = "SMSG";
+
+message SecureMessage {
+  // Must contain a HeaderAndBody message
+  required bytes header_and_body = 1;
+  // Signature of header_and_body
+  required bytes signature = 2;
+}
+
+// Supported "signature" schemes (both symmetric key and public key based)
+enum SigScheme {
+  HMAC_SHA256 = 1;
+  ECDSA_P256_SHA256 = 2;
+  // Not recommended -- use ECDSA_P256_SHA256 instead
+  RSA2048_SHA256 = 3;
+}
+
+// Supported encryption schemes
+enum EncScheme {
+  // No encryption
+  NONE = 1;
+  AES_256_CBC = 2;
+}
+
+message Header {
+  required SigScheme signature_scheme = 1;
+  required EncScheme encryption_scheme = 2;
+  // Identifies the verification key
+  optional bytes verification_key_id = 3;
+  // Identifies the decryption key
+  optional bytes decryption_key_id = 4;
+  // Encryption may use an IV
+  optional bytes iv = 5;
+  // Arbitrary per-protocol public data, to be sent with the plain-text header
+  optional bytes public_metadata = 6;
+  // The length of some associated data this is not sent in this SecureMessage,
+  // but which will be bound to the signature.
+  optional uint32 associated_data_length = 7 [ default = 0 ];
+}
+
+message HeaderAndBody {
+  // Public data about this message (to be bound in the signature)
+  required Header header = 1;
+  // Payload data
+  required bytes body = 2;
+}
+
+// Must be kept wire-format compatible with HeaderAndBody. Provides the
+// SecureMessage code with a consistent wire-format representation that
+// remains stable irrespective of protobuf implementation choices. This
+// low-level representation of a HeaderAndBody should not be used by
+// any code outside of the SecureMessage library implementation/tests.
+message HeaderAndBodyInternal {
+  // A raw (wire-format) byte encoding of a Header, suitable for hashing
+  required bytes header = 1;
+  // Payload data
+  required bytes body = 2;
+}
+
+// -------
+// The remainder of the messages defined here are provided only for
+// convenience. They are not needed for SecureMessage proper, but are
+// commonly useful wherever SecureMessage might be applied.
+// -------
+
+// A list of supported public key types
+enum PublicKeyType {
+  EC_P256 = 1;
+  RSA2048 = 2;
+  // 2048-bit MODP group 14, from RFC 3526
+  DH2048_MODP = 3;
+}
+
+// A convenience proto for encoding NIST P-256 elliptic curve public keys
+message EcP256PublicKey {
+  // x and y are encoded in big-endian two's complement (slightly wasteful)
+  // Client MUST verify (x,y) is a valid point on NIST P256
+  required bytes x = 1;
+  required bytes y = 2;
+}
+
+// A convenience proto for encoding RSA public keys with small exponents
+message SimpleRsaPublicKey {
+  // Encoded in big-endian two's complement
+  required bytes n = 1;
+  optional int32 e = 2 [default = 65537];
+}
+
+// A convenience proto for encoding Diffie-Hellman public keys,
+// for use only when Elliptic Curve based key exchanges are not possible.
+// (Note that the group parameters must be specified separately)
+message DhPublicKey {
+  // Big-endian two's complement encoded group element
+  required bytes y = 1;
+}
+
+message GenericPublicKey {
+  required PublicKeyType type = 1;
+  optional EcP256PublicKey ec_p256_public_key = 2;
+  optional SimpleRsaPublicKey rsa2048_public_key = 3;
+  // Use only as a last resort
+  optional DhPublicKey dh2048_public_key = 4;
+}
diff --git a/src/main/proto/ukey.proto b/src/main/proto/ukey.proto
new file mode 100644
index 0000000..155b279
--- /dev/null
+++ b/src/main/proto/ukey.proto
@@ -0,0 +1,104 @@
+/* Copyright 2018 Google LLC
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     https://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+syntax = "proto2";
+
+package securegcm;
+
+option java_package = "com.google.security.cryptauth.lib.securegcm";
+option java_outer_classname = "UkeyProto";
+
+message Ukey2Message {
+  enum Type {
+    UNKNOWN_DO_NOT_USE = 0;
+    ALERT = 1;
+    CLIENT_INIT = 2;
+    SERVER_INIT = 3;
+    CLIENT_FINISH = 4;
+  }
+
+  optional Type message_type = 1;   // Identifies message type
+  optional bytes message_data = 2;  // Actual message, to be parsed according to
+                                    // message_type
+}
+
+message Ukey2Alert {
+  enum AlertType {
+    // Framing errors
+    BAD_MESSAGE = 1;             // The message could not be deserialized
+    BAD_MESSAGE_TYPE = 2;        // message_type has an undefined value
+    INCORRECT_MESSAGE = 3;       // message_type received does not correspond to
+                                 // expected type at this stage of the protocol
+    BAD_MESSAGE_DATA = 4;        // Could not deserialize message_data as per
+                                 //  value inmessage_type
+
+    // ClientInit and ServerInit errors
+    BAD_VERSION = 100;           // version is invalid; server cannot find
+                                 // suitable version to speak with client.
+    BAD_RANDOM = 101;            // Random data is missing or of incorrect
+                                 // length
+    BAD_HANDSHAKE_CIPHER = 102;  // No suitable handshake ciphers were found
+    BAD_NEXT_PROTOCOL = 103;     // The next protocol is missing, unknown, or
+                                 // unsupported
+    BAD_PUBLIC_KEY = 104;        // The public key could not be parsed
+
+    // Other errors
+    INTERNAL_ERROR = 200;       // An internal error has occurred. error_message
+                                // may contain additional details for logging
+                                // and debugging.
+  }
+
+  optional AlertType type = 1;
+  optional string error_message = 2;
+}
+
+enum Ukey2HandshakeCipher {
+  RESERVED = 0;
+  P256_SHA512 = 100;        // NIST P-256 used for ECDH, SHA512 used for
+                            // commitment
+  CURVE25519_SHA512 = 200;  // Curve 25519 used for ECDH, SHA512 used for
+                            // commitment
+}
+
+message Ukey2ClientInit {
+  optional int32 version = 1;  // highest supported version for rollback
+                               // protection
+  optional bytes random = 2;   // random bytes for replay/reuse protection
+
+  // One commitment (hash of ClientFinished containing public key) per supported
+  // cipher
+  message CipherCommitment {
+    optional Ukey2HandshakeCipher handshake_cipher = 1;
+    optional bytes commitment = 2;
+  }
+  repeated CipherCommitment cipher_commitments = 3;
+
+  // Next protocol that the client wants to speak.
+  optional string next_protocol = 4;
+}
+
+message Ukey2ServerInit {
+  optional int32 version = 1;  // highest supported version for rollback
+                               // protection
+  optional bytes random = 2;   // random bytes for replay/reuse protection
+
+  // Selected Cipher and corresponding public key
+  optional Ukey2HandshakeCipher handshake_cipher = 3;
+  optional bytes public_key = 4;
+}
+
+message Ukey2ClientFinished {
+  optional bytes public_key = 1;  // public key matching selected handshake
+                                  // cipher
+}