Advanced

Improving the rainbow attack by reusing colours

Ågren, Martin LU ; Johansson, Thomas LU and Hell, Martin LU (2009) 8th International Conference, CANS 2009 In Cryptology and Network Security/Lecture Notes in Computer Science 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:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
Thin rainbow attack, Rainbow attack, Hellman attack, Time memory trade-off, TMTO
in
Cryptology and Network Security/Lecture Notes in Computer Science
editor
Garay, Juan A.; Miyaji, Atsuko; Otsuka, Akira; ; and
volume
5888
pages
362 - 378
publisher
Springer
conference name
8th International Conference, CANS 2009
external identifiers
  • wos:000280395000024
  • scopus:71549158206
ISSN
0302-9743
1611-3349
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
2010-02-01 14:08:11
date last changed
2017-03-05 03:29:34
@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         = {0302-9743},
  keyword      = {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},
  volume       = {5888},
  year         = {2009},
}