Publication:
Breaking Cuckoo Hash: Black Box Attacks

Simple item page
dc.affiliation.dptoUC3M. Departamento de Ingeniería Telemáticaes
dc.affiliation.grupoinvUC3M. Grupo de Investigación: Network Technologieses
dc.contributor.authorReviriego Vasallo, Pedro
dc.contributor.authorTing, Daniel
dc.contributor.funderComunidad de Madrides
dc.contributor.funderMinisterio de Ciencia e Innovación (España)es
dc.date.accessioned2022-08-25T08:42:00Z
dc.date.available2022-08-25T08:42:00Z
dc.date.issued2022-07-09
dc.description.abstractIntroduced less than twenty years ago, cuckoo hashing has a number of attractive features like a constant worst case number of memory accesses for queries and close to full memory utilization. Cuckoo hashing has been widely adopted to perform exact matching of an incoming key with a set of stored (key, value) pairs in both software and hardware implementations. This widespread adoption makes it important to consider the security of cuckoo hashing. Most hash based data structures can be attacked by generating collisions that reduce their performance. In fact, for cuckoo hashing collisions could lead to insertion failures which in some systems would lead to a system failure. For example, if cuckoo hashing is used to perform Ethernet lookup and a given MAC address cannot be added to the cuckoo hash, the switch would not be able to correctly forward frames to that address. Previous works have shown that this can be done when the attacker knows the hash functions used in the implementation. However, in many cases the attacker would not have that information and would only have access to the cuckoo hash operations to perform insertions, removals or queries. This article considers the security of a cuckoo hash to an attacker that has only a black box access to it. The analysis shows that by carefully performing user operations on the cuckoo hash, the attacker can force insertion failures with a small set of elements. The proposed attack has been implemented and tested for different configurations to demonstrate its feasibility. The fact that cuckoo hash can be broken with only access to its user functions should be taken into account when implementing it in critical systems. The article also discusses potential approaches to mitigate this vulnerability.en
dc.description.sponsorshipThis work was supported by the ACHILLES project (PID2019-104207RB-I00) and the Go2Edge network (RED2018-102585-T) funded by the Spanish Ministry of Science and Innovation and by the Madrid Community project TAPIR-CM (P2018/TCS-4496).en
dc.description.statusPublicadoes
dc.format.extent6
dc.identifier.bibliographicCitationIEEE Transactions on Dependable and Secure Computing, (2022), 19(4), pp.: 2421-2427.en
dc.identifier.doihttps://doi.org/10.1109/TDSC.2021.3058336
dc.identifier.issn1545-5971
dc.identifier.publicationfirstpage2421
dc.identifier.publicationissue4
dc.identifier.publicationlastpage2427
dc.identifier.publicationtitleIEEE Transactions on Dependable and Secure Computingen
dc.identifier.publicationvolume19
dc.identifier.urihttps://hdl.handle.net/10016/35600
dc.identifier.uxxiAR/0000027530
dc.language.isoengen
dc.publisherIEEEen
dc.relation.projectIDGobierno de España. PID2019-104207RB-I00/ACHILLESes
dc.relation.projectIDGobierno de España. RED2018-102585-T)/Go2Edgees
dc.relation.projectIDComunidad de Madrid. P2018/TCS-4496/TAPIR-CMes
dc.rights© 2021 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.en
dc.rights.accessRightsopen accessen
dc.subject.ecienciaTelecomunicacioneses
dc.subject.otherKey value storeen
dc.subject.otherSecurityen
dc.subject.otherVulnerabilityen
dc.subject.otherComputer network securityen
dc.subject.otherCryptographyen
dc.subject.otherData structuresen
dc.subject.otherLocal area networksen
dc.subject.otherHash functionsen
dc.subject.otherCuckoo hashen
dc.titleBreaking Cuckoo Hash: Black Box Attacksen
dc.typeresearch article*
dc.type.hasVersionAM*
dspace.entity.typePublication
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
breaking_IEEE-TDSC_2022_ps.pdf
Size:
362.71 KB
Format:
Adobe Portable Document Format
Download
Collections
DIT - RYSC - Artículos en Revistas Internacionales / International Journals