A More Robust and Secure Version of Paired Distance Protocol

Abstract

In 2013, Ronald L. Rivest and Ari Juels proposed the concept of honeywords for the early detection of password breaches. Thereafter, many other honeyword generation approaches have been proposed in the literature. However, all of these existing honeyword approaches require a very large amount of space to store k-1 no. of honeywords along with one real password for each user. Hence, these existing approaches are not memory efficient.

In 2015, Paired Distance Protocol (PDP) was proposed by Nilesh et al. which was the first and only algorithm to overcome this limitation of large memory footprint and was shown to be as secure as its peers. In this work, we show that the design of the PDP protocol has many limitations which makes it insecure against several new attacks.

Thus, despite being memory efficient, it cannot be rendered fit for practical use owing to reduced security. We then propose an improved design framework of Paired Distance Protocol (PDP) which overcomes all the existing limitations and is resistant to all the attacks.

We provide a detailed security analysis of our proposed version and also perform a comparative analysis with the original PDP protocol and other peer algorithms existing in the literature. We show that our proposed version retains memory efficiency as its predecessor and at the same is more secure than the original PDP, thus making it better than the other approaches which is verified through provided analysis.