Hardened Bloom filters, with an application to unobservability

• Autorzy: Bernard M. , Leprévost F.

Identyfikatory

DOI

10.2478/v10065-012-0018-y

• Języki publikacji: EN

Abstrakty

EN

Classical Bloom filters may be used to elegantly check if an element e belongs to a set S, and, if not, to add e to S. They do not store any data and only provide boolean answers regarding the membership of a given element in the set, with some probability of false positive answers. Bloom filters are often used in caching system to check that some requested data actually exist before doing a costly lookup to retrieve them. However, security issues may arise for some other applications where an active attacker is able to inject data crafted to degrade the filters’ algorithmic properties, resulting for instance in a Denial of Service (DoS) situation. This leads us to the concept of hardened Bloom filters, combining classical Bloom filters with cryptographic hash functions and secret nonces. We show how this approach is successfully used in the TrueNyms unobservability system and protects it against replay attacks.

Słowa kluczowe

EN

Bloom Filter; cryptographic hash functions; secret nonce; TrueNyms unobservability system

• Wydawca: Wydawnictwo UMCS
• Czasopismo: Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica
• Rocznik: 2012
• Tom: Vol. 12, no. 4
• Strony: 11--22
• Opis fizyczny: Bibliogr. 11 poz., rys.

Twórcy

autor

Bernard M.

• LACS, University of Luxembourg, 162 a, Avenue de la Faïencerie, L-1511 Luxembourg

autor

Leprévost F.

• LACS, University of Luxembourg, 162 a, Avenue de la Faïencerie, L-1511 Luxembourg

Bibliografia

• [1] Bloom B. H., Space/time trade-offs in hash coding with allowable errors, Communications of the ACM 13 (7) (1970): 422.
• [2] Bernard N., Leprévost F., Unobservability of low-latency communications: the TrueNyms protocol, work in progress.
• [3] Knuth D. E., Sorting and Searching,The Art of Computer Programming 3 (1998).
• [4] Menezes A. J., van Oorschot P. C., Vanstone S. A., Handbook of Applied Cryptography, Discrete Mathematics and its Applications, CRC Press (1997).
• [5] Anderson R., Security Engineering: A Guide to Building Dependable Distributed Systems, Wiley (2001).
• [6] Preneel B., Dobbertin H., Bosselaers A., The Cryptographic Hash Function RIPEMD-160, CryptoBytes 3 (2) (1997): 9.
• [7] Bernard N., Non-observabilité des communications à faible latence, Université du Luxembourg, Université de Grenoble 1 – Joseph Fourier (2008).
• [8] Bernard N., Leprévost F., Beyond TOR: The TrueNyms Protocol, Security and Intelligent Information Systems 7053 (2012): 68.
• [9] Goldschlag D. M., Reed M. G., Syverson P. F., Hiding Routing Information, Proceedings of Information Hiding: First International Workshop, Springer-Verlag, LNCS 1174 (1996): 137.
• [10] Reed M. G., Syverson P. F., Goldschlag D. M., Anonymous connections and Onion Routing, IEEE Journal on Selected Areas in Communications 16(4) (1998): 482.
• [11] Knudsen L., Block ChainingModes of Operation, Department of Informatics, University of Bergen (2000); http://www.ii.uib.no/publikasjoner/texrap/ps/2000-207.ps