Efficient Protocol-Proving Algorithm Based on Improved Authentication Tests

A new efficient protocol-proving algorithm was proposed for verifying security protocols. This algorithm is based on the improved authentication tests model, which enhances the original model by formalizing the message reply attack. With exact causal dependency relations between messages in this model, the protocol-proving algorithm can avoid the state explosion caused by asynchronous. In order to get the straight proof of security protocols, three authentication theorems are exploited for evaluating the agreement and distinction properties. When the algorithm terminates, it outputs either the proof results or the potential flaws of the security protocol. The experiment shows that the protocol-proving algorithm can detect the type flaw attack on Neuman-Stubblebine protocol, and prove the correctness of NSL protocol by exploring only 10 states.