An Integrative Framework to Protocol Analysis and Repair: Bellare–Rogaway Model + Planning + Model Checker

Article type: Research Article

Authors: Choo, Kim-Kwang Raymond^;

Affiliations: Australian Institute of Criminology, GPO Box 2944, Canberra ACT 2601 Australia, e-mail: raymond.choo@aic.gov.au

Note: [] The views and opinions expressed in this paper are those of the author and do not reflect those of the Australian Government and Australian Institute of Criminology. Research was performed while the author was with the Intelligent Systems Laboratory / University of Western Sydney.

Abstract: A modified version of the Bellare and Rogaway (1993) adversarial model is encoded using Asynchronous Product Automata (APA). A model checker tool, Simple Homomorphism Verification Tool (SHVT), is then used to perform state-space analysis on the Automata in the setting of planning problem. The three-party identity-based secret public key protocol (3P-ID-SPK) protocol of Lim and Paterson (2006), which claims to provide explicit key authentication, is used as a case study. We then refute its heuristic security argument by revealing a previously unpublished flaw in the protocol using SHVT. We then show how our approach can automatically repair the protocol. This is, to the best of our knowledge, the first work that integrates an adversarial model from the computational complexity paradigm with an automated tool from the computer security paradigm to analyse protocols in an artificial intelligence problem setting – planning problem – and, more importantly, to repair protocols.

Keywords: key establishment protocols, model checker, key authentication, provable security, planning problem

Journal: Informatica, vol. 18, no. 4, pp. 547-568, 2007