Method and apparatus for fault tolerant TCP handshaking that includes a first node and a second node both connected in a network where the second node is one of at least two nodes in a cluster of nodes. The second node receives a first message from the first node where the first message includes a sequence number. The second node generates a fingerprint and replaces a portion of the sequence number with the fingerprint to form a cryptographic sequence number. The cryptographic sequence number is sent from the second node to the first node. A second message that includes the cryptographic sequence number is received from the first node at the second node. Any node in the cluster can verify that the cryptographic sequence number sent by the first node was created by one of the nodes in the cluster thereby providing fault tolerant TCP handshaking.