Accurate False-Positive Probability of Multiset-Based Demirci-Selçuk Meet-in-the-Middle Attacks

Dongjae Lee, Deukjo Hong, Jaechul Sung, Seokhie Hong

    Research output: Contribution to journalArticlepeer-review

    Abstract

    In this study, we focus on evaluating the false-positive probability of the Demirci-Selçuk meet-in-the-middle attack, particularly within the context of configuring precomputed tables with multisets. During the attack, the adversary effectively reduces the size of the key space by filtering out the wrong keys, subsequently recovering the master key from the reduced key space. The false-positive probability is defined as the probability that a wrong key will pass through the filtering process. Due to its direct impact on the post-filtering key space size, the false-positive probability is an important factor that influences the complexity and feasibility of the attack. However, despite its significance, the false-positive probability of the multiset-based Demirci-Selçuk meet-in-the-middle attack has not been thoroughly discussed, to the best of our knowledge. We generalize the Demirci-Selçuk meet-in-the-middle attack and present a sophisticated method for accurately calculating the false-positive probability. We validate our methodology through toy experiments, demonstrating its high precision. Additionally, we propose a method to optimize an attack by determining the optimal format of precomputed data, which requires the precise falsepositive probability. Applying our approach to previous attacks on AES and ARIA,we have achieved modest improvements. Specifically, we enhance the memory complexity and time complexity of the offline phase of previous attacks on 7-round AES-128/192/256, 7-round ARIA-192/256, and 8- round ARIA-256 by factors ranging from 20:56 to 23. Additionally, we have improved the overall time complexity of attacks on 7-round ARIA-192/256 by factors of 20:13 and 20:42, respectively.

    Original languageEnglish
    Pages (from-to)1212-1228
    Number of pages17
    JournalIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
    VolumeE107.A
    Issue number8
    DOIs
    Publication statusPublished - 2024 Aug

    Bibliographical note

    Publisher Copyright:
    © 2024 The Institute of Electronics.

    Keywords

    • AES
    • ARIA
    • Demirci-Selçuk meet-in-the-middle attack
    • false-positive probability
    • optimization

    ASJC Scopus subject areas

    • Signal Processing
    • Computer Graphics and Computer-Aided Design
    • Electrical and Electronic Engineering
    • Applied Mathematics

    Fingerprint

    Dive into the research topics of 'Accurate False-Positive Probability of Multiset-Based Demirci-Selçuk Meet-in-the-Middle Attacks'. Together they form a unique fingerprint.

    Cite this