diff --git a/src/handshake.rs b/src/handshake.rs
line changes: +4/-0
index 5393efe..79753b1
--- a/src/handshake.rs
+++ b/src/handshake.rs

@@ -274,6 +274,7 @@ impl OssuaryConnection {
                                                      &sig)?;
                 let w = write_packet(self, &mut buf, struct_as_slice(&pkt),
                                      PacketType::ServerHandshake)?;
+                increment_nonce(&mut self.local_key.nonce);
                 self.state = ConnectionState::ServerWaitAuthentication(std::time::SystemTime::now());
                 w
             },

@@ -324,6 +325,7 @@ impl OssuaryConnection {
                                                           &sig)?;
                 let w = write_packet(self, &mut buf, struct_as_slice(&pkt),
                                      PacketType::ClientAuthentication)?;
+                increment_nonce(&mut self.local_key.nonce);
                 self.state = ConnectionState::Encrypted;
                 w
             },

@@ -498,6 +500,7 @@ impl OssuaryConnection {
                                     signature: Some(sig),
                                     secret_key: None,
                                 };
+                                let _ = self.remote_key.as_mut().map(|k| increment_nonce(&mut k.nonce));
                                 self.state = ConnectionState::ClientSendAuthentication;
                             }
                         }

@@ -579,6 +582,7 @@ impl OssuaryConnection {
                                 }
                                 self.remote_auth.signature = Some(sig);
                                 self.remote_auth.public_key = Some(pubkey);
+                                let _ = self.remote_key.as_mut().map(|k| increment_nonce(&mut k.nonce));
                                 self.state = ConnectionState::Encrypted;
                             }
                         }

diff --git a/src/lib.rs b/src/lib.rs
line changes: +9/-2
index 04415d2..8a171f6
--- a/src/lib.rs
+++ b/src/lib.rs

@@ -124,7 +124,6 @@
 
 //
 // TODO
-//  - Increment nonce on each encryption/decryption:
 //  - 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

@@ -410,6 +409,15 @@ fn interpret_packet<'a, T>(pkt: &'a NetworkPacket) -> Result<&'a T, OssuaryError
     Ok(s)
 }
 
+fn increment_nonce(nonce: &mut [u8]) -> bool {
+    let wrapped = nonce.iter_mut().rev().fold(1, |acc, x| {
+        let (val,carry) = x.overflowing_add(acc);
+        *x = val;
+        carry as u8
+    });
+    wrapped != 0
+}
+
 /// Cast the data bytes in a NetworkPacket into a struct, and also return the
 /// remaining unused bytes if the data is larger than the struct.
 fn interpret_packet_extra<'a, T>(pkt: &'a NetworkPacket)

@@ -470,5 +478,4 @@ mod tests {
         ];
         let _ = conn.set_authorized_keys(keys.iter().map(|x| x.as_slice())).unwrap();
     }
-
 }