Improving the rainbow attack by reusing colours

Summary, in English

Hashing or encrypting a key or a password is a vital part in most network security protocols. The most practical generic attack on such schemes is a time memory trade-off attack. Such an attack inverts any one-way function using a trade-off between memory and execution time. Existing techniques include the Hellman attack and the rainbow attack, where the latter uses different reduction functions ("colours") within a table.



This work investigates the possibility of reusing colours, i.e., repeating the reduction functions, in the rainbow attack. We show how this outperforms the Hellman and the rainbow attack in a model of fixed resources. We try to characterize exactly when this improvement appears and in such a case the choice of an optimal number of colours.

• Author: Martin Ågren; Thomas Johansson; Martin Hell
• Editor: Juan A. Garay; Atsuko Miyaji; Akira Otsuka
• Department/s: Department of Electrical and Information Technology
• Publishing year: 2009
• Language: English
• Pages: 362-378
• Publication/Series: Cryptology and Network Security/Lecture Notes in Computer Science
• Volume: 5888
• Links: http://www.springerlink.com/openurl.asp?genre=article&id=doi:10.1007/978-3-642-10433-6_24; http://dx.doi.org/10.1007/978-3-642-10433-6_24
• Document type: Conference paper
• Publisher: Springer
• Topic: Electrical Engineering, Electronic Engineering, Information Engineering
• Keywords: Thin rainbow attack; Rainbow attack; Hellman attack; Time memory trade-off; TMTO
• Conference name: 8th International Conference, CANS 2009
• Conference date: 2009-12-12 - 2009-12-14
• Conference place: Kanazawa, Japan
• Status: Published
• Research group: Crypto and Security
• ISBN/ISSN/Other: ISSN: 1611-3349; ISSN: 0302-9743; ISBN: 978-3-642-10432-9