diff --git a/src/handshake.rs b/src/handshake.rs
line changes: +68/-26
index 79753b1..e2eb470
--- a/src/handshake.rs
+++ b/src/handshake.rs

@@ -188,7 +188,9 @@ impl OssuaryConnection {
         }
         let written = match self.state {
             // No-op states
-            ConnectionState::Encrypted => {0},
+            ConnectionState::Encrypted |
+            ConnectionState::ClientRaiseUntrustedServer |
+            ConnectionState::ClientWaitServerApproval => {0},
 
             // Timeout wait states
             ConnectionState::ServerWaitHandshake(t) |

@@ -387,8 +389,11 @@ impl OssuaryConnection {
         }
         self.remote_msg_id = pkt.header.msg_id + 1;
 
-        println!("Recv packet: ({}) {:?} <- {:?}", self.is_server(), self.state, pkt.kind());
         match self.state {
+            // no-op states
+            ConnectionState::ClientRaiseUntrustedServer |
+            ConnectionState::ClientWaitServerApproval => {},
+
             // Non-receive states.  Receiving handshake data is an error.
             ConnectionState::ClientSendHandshake |
             ConnectionState::ClientSendAuthentication |

@@ -472,28 +477,31 @@ impl OssuaryConnection {
                                         return Err(OssuaryError::InvalidSignature);
                                     }
                                 };
-                                // TODO: support trust on first use
-                                if self.authorized_keys.len() > 0 {
-                                    if chal.iter().all(|x| *x == 0) ||
-                                        sig.iter().all(|x| *x == 0) ||
-                                        enc_pkt.public_key.iter().all(|x| *x == 0) {
-                                            // Parameters must be non-zero
-                                            self.reset_state(None);
-                                            return Err(OssuaryError::InvalidSignature);
-                                        }
-                                    // 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);
-                                            return Err(OssuaryError::InvalidSignature);
-                                        },
+
+                                // All servers should have an auth key set, so
+                                // these parameters should be non-zero and the
+                                // signature should verify.
+                                if chal.iter().all(|x| *x == 0) ||
+                                    sig.iter().all(|x| *x == 0) ||
+                                    enc_pkt.public_key.iter().all(|x| *x == 0) {
+                                        // Parameters must be non-zero
+                                        self.reset_state(None);
+                                        return Err(OssuaryError::InvalidSignature);
                                     }
+
+                                // 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);
+                                        return Err(OssuaryError::InvalidSignature);
+                                    },
                                 }
+
                                 self.remote_auth = AuthKeyMaterial {
                                     challenge: Some(chal),
                                     public_key: Some(pubkey),

@@ -501,7 +509,11 @@ impl OssuaryConnection {
                                     secret_key: None,
                                 };
                                 let _ = self.remote_key.as_mut().map(|k| increment_nonce(&mut k.nonce));
-                                self.state = ConnectionState::ClientSendAuthentication;
+
+                                match self.authorized_keys.contains(&enc_pkt.public_key) {
+                                    true => self.state = ConnectionState::ClientSendAuthentication,
+                                    false => self.state = ConnectionState::ClientRaiseUntrustedServer,
+                                }
                             }
                         }
                     },

@@ -556,7 +568,6 @@ impl OssuaryConnection {
                                     }
                                 };
                                 match self.conn_type {
-                                    // TODO: only permit known pubkeys
                                     ConnectionType::AuthenticatedServer => {
                                         if challenge.iter().all(|x| *x == 0) ||
                                             sig.iter().all(|x| *x == 0) ||

@@ -565,6 +576,7 @@ impl OssuaryConnection {
                                                 self.reset_state(None);
                                                 return Err(OssuaryError::InvalidSignature);
                                         }
+
                                         // 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]));

@@ -577,6 +589,15 @@ impl OssuaryConnection {
                                                 return Err(OssuaryError::InvalidSignature);
                                             },
                                         }
+
+                                        // Ensure this key is permitted to connect
+                                        match self.authorized_keys.contains(&enc_pkt.public_key) {
+                                            true => {},
+                                            false => {
+                                                self.reset_state(None);
+                                                return Err(OssuaryError::InvalidKey);
+                                            },
+                                        }
                                     }
                                     _ => {},
                                 }

@@ -607,10 +628,31 @@ impl OssuaryConnection {
     /// Returns whether the handshake process is complete.
     ///
     ///
-    pub fn handshake_done(&self) -> Result<bool, &OssuaryError> {
+    pub fn handshake_done(&mut self) -> Result<bool, OssuaryError> {
+        let failed = match self.state {
+            ConnectionState::Failed(_) => true,
+            _ => false,
+        };
+        if failed {
+            let mut new_state = ConnectionState::Failed(OssuaryError::ConnectionFailed);
+            std::mem::swap(&mut self.state, &mut new_state);
+            match new_state {
+                ConnectionState::Failed(e) => return Err(e),
+                _ => return Err(OssuaryError::ConnectionFailed),
+            }
+        }
         match self.state {
             ConnectionState::Encrypted => Ok(true),
-            ConnectionState::Failed(ref e) => Err(e),
+            ConnectionState::Failed(ref _e) => Err(OssuaryError::ConnectionFailed),
+            ConnectionState::ClientRaiseUntrustedServer => {
+                self.state = ConnectionState::ClientWaitServerApproval;
+                let mut key: Vec<u8> = Vec::new();
+                match self.remote_auth.public_key {
+                    Some(ref p) => key.extend_from_slice(p.as_bytes()),
+                    None => key.extend_from_slice(&[0; KEY_LEN]),
+                };
+                Err(OssuaryError::UntrustedServer(key))
+            },
             _ => Ok(false),
         }
     }

diff --git a/src/lib.rs b/src/lib.rs
line changes: +35/-10
index 8a171f6..c7d5bf4
--- a/src/lib.rs
+++ b/src/lib.rs

@@ -25,7 +25,7 @@
 //! are encrypted with the established session key.
 //!
 //! In the following diagram, fields in [single brackets] are sent in the clear,
-//! and those in [[double brackets]] are encrypted:
+//! and those in [[double brackets]] are encrypted with the shared session key:
 //!
 //! ```text
 //! <client> --> [  session x25519 public key,

@@ -124,14 +124,13 @@
 
 //
 // TODO
-//  - server certificate (TOFU)
 //  - consider all unexpected packet types to be errors
 //  - ensure that a reset on one end always sends a reset to the other
 //  - limit connection retries
 //  - tests should check their received strings
 //  - rustdoc everything
+//  - expose generate_auth_keypair in FFI
 //
-// TODO: raise OssuaryError::UntrustedServer() when trust-on-first-use
 
 pub mod clib;
 mod connection;

@@ -150,6 +149,8 @@ use chacha20_poly1305_aead::{encrypt,decrypt};
 use x25519_dalek::{EphemeralSecret, EphemeralPublic, SharedSecret};
 use ed25519_dalek::{Signature, Keypair, SecretKey, PublicKey};
 
+use rand::rngs::OsRng;
+
 const PROTOCOL_VERSION: u8 = 1u8;
 
 // Maximum time to wait (in seconds) for a handshake response

@@ -298,6 +299,23 @@ enum ConnectionState {
     /// Next client state: Encrypted
     ClientSendAuthentication,
 
+    /// Client is about to raise an UntrustedServer error to the caller
+    ///
+    /// The client has established and verified a connection with a remote
+    /// server, but the server's authentication key is unknown.  The
+    /// [`OssuaryError::UntrustedServer`] will be raised on the next call to
+    /// [`OssuaryConnection::handhake_done`].
+    ClientRaiseUntrustedServer,
+
+    /// Client is waiting for the caller to approve an unknown remote server
+    ///
+    /// After raising [`OssuaryError::UntrustedServer`], the client waits in
+    /// this state until the server's public key is added to the list of
+    /// authorized keys with [`OssuaryConnection::add_authorized_key`], or
+    /// the connection is killed.  This permits callers to implement a
+    /// Trust-On-First-Use policy.
+    ClientWaitServerApproval,
+
     /// Connection is established, encrypted, and optionally authenticated.
     Encrypted,
 

@@ -332,7 +350,7 @@ pub enum ConnectionType {
     /// Authenticated servers only allow connections from clients with secret
     /// keys set using [`OssuaryConnection::set_secret_key`], and with the
     /// matching public key registered with the server using
-    /// [`OssuaryConnection::set_authorized_keys`].
+    /// [`OssuaryConnection::add_authorized_keys`].
     AuthenticatedServer,
 
     /// This context is a server that does not support authentication.

@@ -354,7 +372,7 @@ pub enum ConnectionType {
 /// [`ConnectionType`] identifying whether it is to act as a client or server.
 /// Server contexts can optionally require authentication, verified by providing
 /// a list of public keys of permitted clients with
-/// [`OssuaryConnection::set_authorized_keys`].  Clients, on the other hand,
+/// [`OssuaryConnection::add_authorized_keys`].  Clients, on the other hand,
 /// authenticate by setting their secret key with
 /// [`OssuaryConnection::set_secret_key`].
 ///

@@ -403,6 +421,13 @@ impl Default for OssuaryConnection {
     }
 }
 
+/// Generate secret/public Ed25519 keypair for host authentication
+pub fn generate_auth_keypair() -> Result<([u8; KEY_LEN],[u8; KEY_LEN]), OssuaryError> {
+    let mut rng = OsRng::new()?;
+    let keypair: Keypair = Keypair::generate(&mut rng);
+    Ok((keypair.secret.to_bytes(), keypair.public.to_bytes()))
+}
+
 /// Cast the data bytes in a NetworkPacket into a struct
 fn interpret_packet<'a, T>(pkt: &'a NetworkPacket) -> Result<&'a T, OssuaryError> {
     let s: &T = slice_as_struct(&pkt.data)?;

@@ -448,8 +473,8 @@ mod tests {
     use crate::*;
 
     #[test]
-    fn test_set_authorized_keys() {
-        let mut conn = OssuaryConnection::new(ConnectionType::AuthenticatedServer);
+    fn test_add_authorized_keys() {
+        let mut conn = OssuaryConnection::new(ConnectionType::AuthenticatedServer, None).unwrap();
 
         // Vec of slices
         let keys: Vec<&[u8]> = vec![

@@ -458,7 +483,7 @@ mod tests {
               0xbb, 0x9e, 0x86, 0x62, 0x28, 0x7c, 0x33, 0x89,
               0xa2, 0xe1, 0x63, 0xdc, 0x55, 0xde, 0x28, 0x1f]
         ];
-        let _ = conn.set_authorized_keys(keys).unwrap();
+        let _ = conn.add_authorized_keys(keys).unwrap();
 
         // Vec of owned arrays
         let keys: Vec<[u8; 32]> = vec![

@@ -467,7 +492,7 @@ mod tests {
              0xbb, 0x9e, 0x86, 0x62, 0x28, 0x7c, 0x33, 0x89,
              0xa2, 0xe1, 0x63, 0xdc, 0x55, 0xde, 0x28, 0x1f]
         ];
-        let _ = conn.set_authorized_keys(keys.iter().map(|x| x.as_ref()).collect::<Vec<&[u8]>>()).unwrap();
+        let _ = conn.add_authorized_keys(keys.iter().map(|x| x.as_ref()).collect::<Vec<&[u8]>>()).unwrap();
 
         // Vec of vecs
         let keys: Vec<Vec<u8>> = vec![

@@ -476,6 +501,6 @@ mod tests {
                  0xbb, 0x9e, 0x86, 0x62, 0x28, 0x7c, 0x33, 0x89,
                  0xa2, 0xe1, 0x63, 0xdc, 0x55, 0xde, 0x28, 0x1f]
         ];
-        let _ = conn.set_authorized_keys(keys.iter().map(|x| x.as_slice())).unwrap();
+        let _ = conn.add_authorized_keys(keys.iter().map(|x| x.as_slice())).unwrap();
     }
 }

diff --git a/tests/basic.rs b/tests/basic.rs
line changes: +15/-3
index 8a0815f..ac26f63
--- a/tests/basic.rs
+++ b/tests/basic.rs

@@ -9,7 +9,18 @@ fn event_loop<T>(mut conn: OssuaryConnection,
                  is_server: bool) -> Result<(), std::io::Error>
 where T: std::io::Read + std::io::Write {
     // Run the opaque handshake until the connection is established
-    while conn.handshake_done().unwrap() == false {
+    loop {
+        match conn.handshake_done() {
+            Ok(true) => break,
+            Ok(false) => {},
+            Err(OssuaryError::UntrustedServer(pubkey)) => {
+                // Trust-On-First-Use would be implemented here.  This
+                // client trusts all servers.
+                let keys: Vec<&[u8]> = vec![&pubkey];
+                let _ = conn.add_authorized_keys(keys).unwrap();
+            }
+            Err(e) => panic!("Handshake failed with error: {:?}", e),
+        }
         if conn.send_handshake(&mut stream).is_ok() {
             loop {
                 match conn.recv_handshake(&mut stream) {

@@ -50,7 +61,8 @@ fn server() -> Result<(), std::io::Error> {
     let listener = TcpListener::bind("127.0.0.1:9988").unwrap();
     let stream: TcpStream = listener.incoming().next().unwrap().unwrap();
     let _ = stream.set_read_timeout(Some(std::time::Duration::from_millis(100u64)));
-    let conn = OssuaryConnection::new(ConnectionType::UnauthenticatedServer);
+    // This server lets any client connect
+    let conn = OssuaryConnection::new(ConnectionType::UnauthenticatedServer, None).unwrap();
     let _ = event_loop(conn, stream, true);
     Ok(())
 }

@@ -58,7 +70,7 @@ fn server() -> Result<(), std::io::Error> {
 fn client() -> Result<(), std::io::Error> {
     let stream = TcpStream::connect("127.0.0.1:9988").unwrap();
     let _ = stream.set_read_timeout(Some(std::time::Duration::from_millis(100u64)));
-    let conn = OssuaryConnection::new(ConnectionType::Client);
+    let conn = OssuaryConnection::new(ConnectionType::Client, None).unwrap();
     let _ = event_loop(conn, stream, false);
     Ok(())
 }

diff --git a/tests/basic_auth.rs b/tests/basic_auth.rs
line changes: +33/-10
index 25c946a..ffcb9db
--- a/tests/basic_auth.rs
+++ b/tests/basic_auth.rs

@@ -9,7 +9,15 @@ fn event_loop<T>(mut conn: OssuaryConnection,
                  is_server: bool) -> Result<(), std::io::Error>
 where T: std::io::Read + std::io::Write {
     // Run the opaque handshake until the connection is established
-    while conn.handshake_done().unwrap() == false {
+    loop {
+        match conn.handshake_done() {
+            Ok(true) => break,
+            Ok(false) => {},
+            Err(OssuaryError::UntrustedServer(_)) => {
+                panic!("Untrusted server, authentication failed!")
+            }
+            Err(e) => panic!("Handshake failed with error: {:?}", e),
+        }
         if conn.send_handshake(&mut stream).is_ok() {
             loop {
                 match conn.recv_handshake(&mut stream) {

@@ -48,26 +56,41 @@ where T: std::io::Read + std::io::Write {
 fn server() -> Result<(), std::io::Error> {
     let listener = TcpListener::bind("127.0.0.1:9988").unwrap();
     let stream: TcpStream = listener.incoming().next().unwrap().unwrap();
-    let mut conn = OssuaryConnection::new(ConnectionType::AuthenticatedServer);
-    let keys: Vec<&[u8]> = vec![
+    let auth_secret_key = &[
+        0x50, 0x29, 0x04, 0x97, 0x62, 0xbd, 0xa6, 0x07,
+        0x71, 0xca, 0x29, 0x14, 0xe3, 0x83, 0x19, 0x0e,
+        0xa0, 0x9e, 0xd4, 0xb7, 0x1a, 0xf9, 0xc9, 0x59,
+        0x3e, 0xa3, 0x1c, 0x85, 0x0f, 0xc4, 0xfa, 0xa2,
+    ];
+    let client_keys: Vec<&[u8]> = vec![
         &[0xbe, 0x1c, 0xa0, 0x74, 0xf4, 0xa5, 0x8b, 0xbb,
           0xd2, 0x62, 0xa7, 0xf9, 0x52, 0x3b, 0x6f, 0xb0,
           0xbb, 0x9e, 0x86, 0x62, 0x28, 0x7c, 0x33, 0x89,
           0xa2, 0xe1, 0x63, 0xdc, 0x55, 0xde, 0x28, 0x1f]
     ];
-    let _ = conn.set_authorized_keys(keys).unwrap();
+    // This server only accepts connections from a single known client
+    let mut conn = OssuaryConnection::new(ConnectionType::AuthenticatedServer, Some(auth_secret_key)).unwrap();
+    let _ = conn.add_authorized_keys(client_keys).unwrap();
     let _ = event_loop(conn, stream, true);
     Ok(())
 }
 
 fn client() -> Result<(), std::io::Error> {
     let stream = TcpStream::connect("127.0.0.1:9988").unwrap();
-    let mut conn = OssuaryConnection::new(ConnectionType::Client);
-    let _ = conn.set_secret_key(
-        &[0x10, 0x86, 0x6e, 0xc4, 0x8a, 0x11, 0xf3, 0xc5,
-          0x6d, 0x77, 0xa6, 0x4b, 0x2f, 0x54, 0xaa, 0x06,
-          0x6c, 0x0c, 0xb4, 0x75, 0xd8, 0xc8, 0x7d, 0x35,
-          0xb4, 0x91, 0xee, 0xd6, 0xac, 0x0b, 0xde, 0xbc]).unwrap();
+    let sec_key = &[0x10, 0x86, 0x6e, 0xc4, 0x8a, 0x11, 0xf3, 0xc5,
+                    0x6d, 0x77, 0xa6, 0x4b, 0x2f, 0x54, 0xaa, 0x06,
+                    0x6c, 0x0c, 0xb4, 0x75, 0xd8, 0xc8, 0x7d, 0x35,
+                    0xb4, 0x91, 0xee, 0xd6, 0xac, 0x0b, 0xde, 0xbc];
+    let server_public_key = &[
+        0x20, 0x88, 0x55, 0x8e, 0xbd, 0x9b, 0x46, 0x1d,
+        0xd0, 0x9d, 0xf0, 0x00, 0xda, 0xf4, 0x0f, 0x87,
+        0xf7, 0x38, 0x40, 0xc5, 0x54, 0x18, 0x57, 0x60,
+        0x74, 0x39, 0x3b, 0xb9, 0x70, 0xe1, 0x46, 0x98,
+    ];
+    let keys: Vec<&[u8]> = vec![server_public_key];
+    // This client only accepts connections to a single known server
+    let mut conn = OssuaryConnection::new(ConnectionType::Client, Some(sec_key)).unwrap();
+    let _ = conn.add_authorized_keys(keys).unwrap();
     let _ = event_loop(conn, stream, false);
     Ok(())
 }

diff --git a/tests/clib_ffi.rs b/tests/clib_ffi.rs
line changes: +19/-5
index 8f48ef4..dc1fb3a
--- a/tests/clib_ffi.rs
+++ b/tests/clib_ffi.rs

@@ -2,12 +2,15 @@ use ossuary::clib::{
     ossuary_create_connection,
     ossuary_destroy_connection,
     ossuary_set_secret_key,
-    ossuary_set_authorized_keys,
+    ossuary_add_authorized_keys,
     ossuary_send_handshake,
     ossuary_recv_handshake,
     ossuary_handshake_done,
     ossuary_send_data,
     ossuary_recv_data,
+    ossuary_remote_public_key,
+    ossuary_add_authorized_key,
+    OSSUARY_ERR_UNTRUSTED_SERVER,
 };
 
 use std::thread;

@@ -21,13 +24,13 @@ fn server() -> Result<(), std::io::Error> {
     for stream in listener.incoming() {
         let mut stream: TcpStream = stream.unwrap();
         let mut reader = std::io::BufReader::new(stream.try_clone().unwrap());
-        let mut conn = ossuary_create_connection(1);
+        let mut conn = ossuary_create_connection(1, ::std::ptr::null_mut());
         let key: &[u8; 32] = &[0xbe, 0x1c, 0xa0, 0x74, 0xf4, 0xa5, 0x8b, 0xbb,
                                0xd2, 0x62, 0xa7, 0xf9, 0x52, 0x3b, 0x6f, 0xb0,
                                0xbb, 0x9e, 0x86, 0x62, 0x28, 0x7c, 0x33, 0x89,
                                0xa2, 0xe1, 0x63, 0xdc, 0x55, 0xde, 0x28, 0x1f];
         let keys: &[*const u8; 1] = &[key as *const u8];
-        ossuary_set_authorized_keys(conn, keys as *const *const u8, keys.len() as u8);
+        ossuary_add_authorized_keys(conn, keys as *const *const u8, keys.len() as u8);
 
         let out_buf: [u8; 512] = [0; 512];
 

@@ -89,7 +92,7 @@ fn server() -> Result<(), std::io::Error> {
 
 fn client() -> Result<(), std::io::Error> {
     let mut stream = TcpStream::connect("127.0.0.1:9989").unwrap();
-    let mut conn = ossuary_create_connection(0);
+    let mut conn = ossuary_create_connection(0, ::std::ptr::null_mut());
     let key: &[u8; 32] = &[0x10, 0x86, 0x6e, 0xc4, 0x8a, 0x11, 0xf3, 0xc5,
                            0x6d, 0x77, 0xa6, 0x4b, 0x2f, 0x54, 0xaa, 0x06,
                            0x6c, 0x0c, 0xb4, 0x75, 0xd8, 0xc8, 0x7d, 0x35,

@@ -99,7 +102,18 @@ fn client() -> Result<(), std::io::Error> {
     let out_buf: [u8; 512] = [0; 512];
 
     let mut reader = std::io::BufReader::new(stream.try_clone().unwrap());
-    while ossuary_handshake_done(conn) == 0 {
+    loop {
+        match ossuary_handshake_done(conn) {
+            0 => {},
+            x if x > 0 => break,
+            OSSUARY_ERR_UNTRUSTED_SERVER => {
+                let key = [0u8; 32];
+                ossuary_remote_public_key(conn, &key as *const u8 as *mut u8, key.len() as u16);
+                ossuary_add_authorized_key(conn, &key as *const u8);
+                continue;
+            },
+            x => panic!("handshake failed: {}", x),
+        }
         let mut out_len = out_buf.len() as u16;
         let wrote = ossuary_send_handshake(conn,
                                            (&out_buf) as *const u8 as *mut u8,