Improving the rainbow attack by reusing colours
(2009) 8th International Conference, CANS 2009 5888. p.362-378- Abstract
- 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... (More) - 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. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/1540038
- author
- Ågren, Martin LU ; Johansson, Thomas LU and Hell, Martin LU
- organization
- publishing date
- 2009
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- keywords
- Thin rainbow attack, Rainbow attack, Hellman attack, Time memory trade-off, TMTO
- host publication
- Cryptology and Network Security/Lecture Notes in Computer Science
- editor
- Garay, Juan A. ; Miyaji, Atsuko and Otsuka, Akira
- volume
- 5888
- pages
- 362 - 378
- publisher
- Springer
- conference name
- 8th International Conference, CANS 2009
- conference location
- Kanazawa, Japan
- conference dates
- 2009-12-12 - 2009-12-14
- external identifiers
-
- wos:000280395000024
- scopus:71549158206
- ISSN
- 1611-3349
- 0302-9743
- ISBN
- 978-3-642-10432-9
- DOI
- 10.1007/978-3-642-10433-6_24
- language
- English
- LU publication?
- yes
- id
- f6c2f8eb-0bff-4430-ae27-110b534d20bc (old id 1540038)
- alternative location
- http://www.springerlink.com/openurl.asp?genre=article&id=doi:10.1007/978-3-642-10433-6_24
- date added to LUP
- 2016-04-01 11:56:20
- date last changed
- 2024-03-11 11:25:29
@inproceedings{f6c2f8eb-0bff-4430-ae27-110b534d20bc, abstract = {{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.<br/><br> <br/><br> 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 = {{Ågren, Martin and Johansson, Thomas and Hell, Martin}}, booktitle = {{Cryptology and Network Security/Lecture Notes in Computer Science}}, editor = {{Garay, Juan A. and Miyaji, Atsuko and Otsuka, Akira}}, isbn = {{978-3-642-10432-9}}, issn = {{1611-3349}}, keywords = {{Thin rainbow attack; Rainbow attack; Hellman attack; Time memory trade-off; TMTO}}, language = {{eng}}, pages = {{362--378}}, publisher = {{Springer}}, title = {{Improving the rainbow attack by reusing colours}}, url = {{http://dx.doi.org/10.1007/978-3-642-10433-6_24}}, doi = {{10.1007/978-3-642-10433-6_24}}, volume = {{5888}}, year = {{2009}}, }