REMOTE ALGORITHMIC COMPLEXITY ATTACKS AGAINST RANDOMIZED HASH TABLES

Noa Bar-Yosef, Avishai Wool

2007

Abstract

Many network devices, such as routers, firewalls, and intrusion detection systems, usually maintain perconnection state in a hash table. However, hash tables are susceptible to algorithmic complexity attacks, in which the attacker degenerates the hash into a simple linked list. A common counter-measure is to randomize the hash table by adding a secret value, known only to the device, as a parameter to the hash function. Our goal is to demonstrate how the attacker can defeat this protection: we demonstrate how to discover this secret value, and to do so remotely, using network traffic. We show that if the secret value is small enough, such an attack is possible. Our attack does not rely on any weakness of a particular hash function and can work against any hash — although a poorly chosen hash function, that produces many collisions, can make the attack more efficient. We present a mathematical modeling of the attack, simulate the attack on different network topologies and finally describe a real-life attack against a weakened version of the Linux Netfilter.

Paper Citation

in Harvard Style

Bar-Yosef N. and Wool A. (2007). REMOTE ALGORITHMIC COMPLEXITY ATTACKS AGAINST RANDOMIZED HASH TABLES . In Proceedings of the Second International Conference on Security and Cryptography - Volume 1: SECRYPT, (ICETE 2007) ISBN 978-989-8111-12-8, pages 117-124. DOI: 10.5220/0002118101170124

in Bibtex Style

@conference{secrypt07,
author={Noa Bar-Yosef and Avishai Wool},
title={REMOTE ALGORITHMIC COMPLEXITY ATTACKS AGAINST RANDOMIZED HASH TABLES},
booktitle={Proceedings of the Second International Conference on Security and Cryptography - Volume 1: SECRYPT, (ICETE 2007)},
year={2007},
pages={117-124},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0002118101170124},
isbn={978-989-8111-12-8},
}

in EndNote Style

TY - CONF
JO - Proceedings of the Second International Conference on Security and Cryptography - Volume 1: SECRYPT, (ICETE 2007)
TI - REMOTE ALGORITHMIC COMPLEXITY ATTACKS AGAINST RANDOMIZED HASH TABLES
SN - 978-989-8111-12-8
AU - Bar-Yosef N.
AU - Wool A.
PY - 2007
SP - 117
EP - 124
DO - 10.5220/0002118101170124