Authors: Tomović, Siniša 
Knežević, Milica 
Mihaljević, Miodrag J. 
Affiliations: Computer Science 
Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: Analysis and Correction of the Attack against the LPN-Problem Based Authentication Protocols
Journal: Mathematics
Volume: 9
Issue: 5
First page: 573
Issue Date: 8-Mar-2021
Rank: ~M21a
ISSN: 2227-7390
DOI: 10.3390/math9050573
This paper reconsiders a powerful man-in-the-middle attack against Random-HB# and HB# authentication protocols, two prominent representatives of the HB family of protocols, which are built based on the Learning Parity in Noise (LPN) problem. A recent empirical report pointed out that the attack does not meet the claimed precision and complexity. Performing a thorough theoretical and numerical re-evaluation of the attack, in this paper we identify the root cause of the detected problem, which lies in reasoning based on approximate probability distributions of the central attack events, that can not provide the required precision due to the inherent limitations in the use of the Central Limit Theorem for this particular application. We rectify the attack by employing adequate Bayesian reasoning, after establishing the exact distributions of these events, and overcome the mentioned limitations. We further experimentally confirm the correctness of the rectified attack and show that it satisfies the required, targeted accuracy and efficiency, unlike the original attack.
Keywords: lightweight cryptography | authentication | HB-family | man-in-the-middle attack | cryptanalysis | Poisson-Binomial distribution | LPN problem
Publisher: MDPI
Project: AI4TrustBC 

Show full item record

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.