How to Formalize Loop Iterations in Cryptographic Protocols Using ProVerif

Abstract

The formal verification of cryptographic protocols has been extensively studied in recent years. To verify the cryptographic protocol security, formal verification tools consider protocol properties as interactive processes involving a cryptographic functionality. In general, we formally define a cryptographic functionality as an abstract function. However, the actual cryptographic protocols used comprise complex combinations of cryptographic functionalities. Thus, we may not determine if the protocol is secure, even when the cryptographic protocol security with cryptographic functionalities is verified using verification tools. Increasing the reliability of the verification results necessitates the verification of the security properties of these algorithms using ProVerif. Many cryptographic algorithms have been designed as iterative algorithms. These include the Merkle and Damgård construction (MD construction) method for cryptographic hash functions and the cipher block chaining mode (CBC mode) for the block cipher mode of operation. However, formalizing an iterative execution is difficult in ProVerif. Thus, we propose a method for formalizing a model of iterative executions. In the proposed method, we describe to formalize iterative execution as a formal model of function calls. We demonstrate the validity of our proposed method by formally verifying the safety of the MD construction method, which behaves like an iterative execution by including a one-way compression function and internal variables changed by the output of these functions. We also present a method for formalizing a common block cipher mode of operation (i.e., CBC mode) used in the proposed method to handle iterative execution.

Keywords

• CBC mode
• formal method
• iterative execution
• MD construction
• ProVerif