Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Improving the rainbow attack by reusing colours

Ågren, Martin LU ; Johansson, Thomas LU orcid and Hell, Martin LU (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:
author
; and
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
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
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
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         = {{0302-9743}},
  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}},
}