diff --git a/src/handshake.rs b/src/handshake.rs
line changes: +22/-16
index a4cf738..5393efe
--- a/src/handshake.rs
+++ b/src/handshake.rs

@@ -241,15 +241,13 @@ impl OssuaryConnection {
                 // default to 0s.
                 let sig: [u8; SIGNATURE_LEN] = match server_secret {
                     Some(s) => {
+                        let mut sign_data = [0u8; KEY_LEN + NONCE_LEN + CHALLENGE_LEN];
+                        sign_data[0..KEY_LEN].copy_from_slice(&self.local_key.public);
+                        sign_data[KEY_LEN..KEY_LEN+NONCE_LEN].copy_from_slice(&self.local_key.nonce);
+                        sign_data[KEY_LEN+NONCE_LEN..].copy_from_slice(&self.remote_auth.challenge.unwrap_or([0u8; CHALLENGE_LEN]));
                         let server_public = PublicKey::from(&s);
                         let keypair = Keypair { secret: s, public: server_public };
-                        match self.remote_auth.challenge {
-                            Some(ref c) => keypair.sign(c).to_bytes(),
-                            None => {
-                                self.reset_state(None);
-                                return Err(OssuaryError::InvalidSignature);
-                            }
-                        }
+                        keypair.sign(&sign_data).to_bytes()
                     },
                     None => [0; SIGNATURE_LEN],
                 };

@@ -298,13 +296,11 @@ impl OssuaryConnection {
                     Some(s) => {
                         let client_public = PublicKey::from(&s);
                         let keypair = Keypair { secret: s, public: client_public };
-                        match self.remote_auth.challenge {
-                            Some(ref c) => keypair.sign(c).to_bytes(),
-                            None => {
-                                self.reset_state(None);
-                                return Err(OssuaryError::InvalidSignature);
-                            }
-                        }
+                        let mut sign_data = [0u8; KEY_LEN + NONCE_LEN + CHALLENGE_LEN];
+                        sign_data[0..KEY_LEN].copy_from_slice(&self.local_key.public);
+                        sign_data[KEY_LEN..KEY_LEN+NONCE_LEN].copy_from_slice(&self.local_key.nonce);
+                        sign_data[KEY_LEN+NONCE_LEN..].copy_from_slice(&self.remote_auth.challenge.unwrap_or([0u8; CHALLENGE_LEN]));
+                        keypair.sign(&sign_data).to_bytes()
                     },
                     None => [0; SIGNATURE_LEN],
                 };

@@ -483,7 +479,12 @@ impl OssuaryConnection {
                                             self.reset_state(None);
                                             return Err(OssuaryError::InvalidSignature);
                                         }
-                                    match pubkey.verify(&chal, &signature) {
+                                    // This is the first encrypted message, so the nonce has not changed yet
+                                    let mut sign_data = [0u8; KEY_LEN + NONCE_LEN + CHALLENGE_LEN];
+                                    sign_data[0..KEY_LEN].copy_from_slice(self.remote_key.as_ref().map(|k| &k.public).unwrap_or(&[0u8; KEY_LEN]));
+                                    sign_data[KEY_LEN..KEY_LEN+NONCE_LEN].copy_from_slice(self.remote_key.as_ref().map(|k| &k.nonce).unwrap_or(&[0u8; NONCE_LEN]));
+                                    sign_data[KEY_LEN+NONCE_LEN..].copy_from_slice(&self.local_auth.challenge.unwrap_or([0u8; CHALLENGE_LEN]));
+                                    match pubkey.verify(&sign_data, &signature) {
                                         Ok(_) => {},
                                         Err(_) => {
                                             self.reset_state(None);

@@ -561,7 +562,12 @@ impl OssuaryConnection {
                                                 self.reset_state(None);
                                                 return Err(OssuaryError::InvalidSignature);
                                         }
-                                        match pubkey.verify(&challenge, &signature) {
+                                        // This is the first encrypted message, so the nonce has not changed yet
+                                        let mut sign_data = [0u8; KEY_LEN + NONCE_LEN + CHALLENGE_LEN];
+                                        sign_data[0..KEY_LEN].copy_from_slice(self.remote_key.as_ref().map(|k| &k.public).unwrap_or(&[0u8; KEY_LEN]));
+                                        sign_data[KEY_LEN..KEY_LEN+NONCE_LEN].copy_from_slice(self.remote_key.as_ref().map(|k| &k.nonce).unwrap_or(&[0u8; NONCE_LEN]));
+                                        sign_data[KEY_LEN+NONCE_LEN..].copy_from_slice(&self.local_auth.challenge.unwrap_or([0u8; CHALLENGE_LEN]));
+                                        match pubkey.verify(&sign_data, &signature) {
                                             Ok(_) => {},
                                             Err(_) => {
                                                 self.reset_state(None);

diff --git a/src/lib.rs b/src/lib.rs
line changes: +14/-12
index 1212046..04415d2
--- a/src/lib.rs
+++ b/src/lib.rs

@@ -30,14 +30,14 @@
 //! ```text
 //! <client> --> [  session x25519 public key,
 //!                 session nonce,
-//!                 client random challenge    ]  --> <server>
+//!                 client random challenge                ] --> <server>
 //! <client> <-- [  session x25519 public key,
 //!                 session nonce],
-//!              [[ auth x25519 public key,
+//!              [[ auth ed25519 public key,
 //!                 server random challenge,
-//!                 client challenge signature ]] <-- <server>
-//! <client> --> [[ auth x25519 public key,
-//!                 server challenge signature ]] --> <server>
+//!                 signature(pubkey, nonce, challenge),  ]] <-- <server>
+//! <client> --> [[ auth ed25519 public key,
+//!                 signature(pubkey, nonce, challenge),  ]] --> <server>
 //! ```
 //!
 //! Host authentication (verifying the identity of the remote server or client)

@@ -52,8 +52,10 @@
 //!   its identity in authenticated connections.
 //! * **auth public key**: Public part of long-lived public/private key pair
 //!   used for host authentication.
-//! * **signature**: Signature of remote party's random challenge with auth
-//!   private key, to prove identity.
+//! * **signature**: Signature, with long-lived private authentication key, of
+//!   local party's session public key and nonce (the ECDH parameters) and
+//!   remote party's random challenge, to prove host identity and prevent
+//!   man-in-the-middle attacks.
 //!
 //! ## Security Protections
 //!

@@ -80,10 +82,10 @@
 //!
 //! ### Man-in-the-Middle
 //!
-//! Host authentication with Ed25519 signature verification prevents man-in-the-
-//! middle attacks.  Host authentication is optional, and requires out-of-band
-//! exchange of host public keys or a Trust On First Use policy, so MITM attacks
-//! may be possible if care is not taken.
+//! Host authentication with Ed25519 signature verification of ECDH parameters
+//! prevents man-in-the-middle attacks.  Host authentication is optional, and
+//! requires out-of-band exchange of host public keys or a Trust On First Use
+//! policy, so MITM attacks may be possible if care is not taken.
 //!
 //! ## Security Limitations
 //!

@@ -95,7 +97,7 @@
 //! ### Keys In RAM
 //!
 //! No efforts are taken to secure key data in RAM.  Attacks from privileged
-//! local prcesses are possible.
+//! local processes are possible.
 //!
 //! ### Keys On Disk
 //!