# Difference between revisions of "LASH-n"

From The ECRYPT Hash Function Website

Mschlaeffer (talk | contribs) |
(→Best Known Results) |
||

(12 intermediate revisions by 3 users not shown) | |||

Line 1: | Line 1: | ||

− | == | + | == Specification == |

− | + | * digest size: 160,256,384,512 bits | |

− | * digest size: 160 bits | + | * max. message length: arbitrary length |

− | * max. message length: | + | * compression function: 640,1024,1536,2048-bit message blocks and 640,1024,1536,2048-bit state size |

− | * compression function: | + | <!-- |

− | * Specification: | + | * Specification: http://csrc.nist.gov/groups/ST/hash/documents/SAARINEN_lash4-1_ORIG.pdf |

--> | --> | ||

+ | <bibtex> | ||

@MISC{nistBentaharPSSS06, | @MISC{nistBentaharPSSS06, | ||

author = {Kamel Bentahar and Dan Page and Markku-Juhani O. Saarinen and Joseph H. Silverman and Nigel Smart}, | author = {Kamel Bentahar and Dan Page and Markku-Juhani O. Saarinen and Joseph H. Silverman and Nigel Smart}, | ||

Line 14: | Line 15: | ||

year = {2006}, | year = {2006}, | ||

abstract = {We present a practical cryptographic hash function based on the Miyaguchi-Preneel construction, which instead of using a block cipher as the main component uses a modular matrix multiplication. Thus as the core component it uses a compression function which is closely related to the theoretical lattice based hash function considered by Goldreich, Goldwasser and Halevi. We show that by suitable parameter choices we can produce a hash function which is comparable in performance to existing deployed hash functions such as SHA-1 and SHA-2.}, | abstract = {We present a practical cryptographic hash function based on the Miyaguchi-Preneel construction, which instead of using a block cipher as the main component uses a modular matrix multiplication. Thus as the core component it uses a compression function which is closely related to the theoretical lattice based hash function considered by Goldreich, Goldwasser and Halevi. We show that by suitable parameter choices we can produce a hash function which is comparable in performance to existing deployed hash functions such as SHA-1 and SHA-2.}, | ||

− | url = {http://csrc.nist.gov/groups/ST/hash/ | + | url = {http://csrc.nist.gov/groups/ST/hash/documents/SAARINEN_lash4-1_ORIG.pdf}, |

} | } | ||

+ | </bibtex> | ||

== Cryptanalysis == | == Cryptanalysis == | ||

Line 21: | Line 23: | ||

=== Best Known Results === | === Best Known Results === | ||

+ | LASH-n is vulnerable to attacks that trade time for memory, including collision attacks as fast as 2<sup>(4n/11)</sup> and preimage attacks as fast as 2<sup>(4n/7)</sup>. | ||

---- | ---- | ||

Line 30: | Line 33: | ||

=== Collision Attacks === | === Collision Attacks === | ||

+ | |||

+ | <bibtex> | ||

+ | @inproceedings{fseSteinfeldCMPGLW08, | ||

+ | author = {Ron Steinfeld and Scott Contini and Krystian Matusiewicz and Josef Pieprzyk and Jian Guo and San Ling and Huaxiong Wang}, | ||

+ | title = {Cryptanalysis of LASH}, | ||

+ | booktitle = {FSE}, | ||

+ | year = {2008}, | ||

+ | pages = {207-223}, | ||

+ | abstract = {We show that the LASH-x hash function is vulnerable to attacks that trade time for memory, including collision attacks as fast as 2(4x/11) and preimage attacks as fast as 2^(4x/7). Moreover, we briefly mention heuristic lattice based collision attacks that use small memory but require very long messages that are expected to find collisions much faster than 2^x/2. All of these attacks exploit the designers’ choice of an all zero IV. We then consider whether LASH can be patched simply by changing the IV. In this case, we show that LASH is vulnerable to a 2^(7x/8) preimage attack. We also show that LASH is trivially not a PRF when any subset of input bytes is used as a secret key. None of our attacks depend upon the particular contents of the LASH matrix - we only assume that the distribution of elements is more or less uniform. Additionally, we show a generalized birthday attack on the final compression of LASH which requires $O\left(x2^{\frac{x}{2(1+\frac{107}{105})}}\right) \approx O(x2^{x/4})$ time and memory. Our method extends the Wagner algorithm to truncated sums, as is done in the final transform in LASH.}, | ||

+ | url = {http://dx.doi.org/10.1007/978-3-540-71039-4_13}, | ||

+ | editor = {Kaisa Nyberg}, | ||

+ | publisher = {Springer}, | ||

+ | series = {LNCS}, | ||

+ | volume = {5086}, | ||

+ | isbn = {978-3-540-71038-7}, | ||

+ | } | ||

+ | </bibtex> | ||

---- | ---- |

## Latest revision as of 11:34, 10 November 2008

## Contents

## 1 Specification

- digest size: 160,256,384,512 bits
- max. message length: arbitrary length
- compression function: 640,1024,1536,2048-bit message blocks and 640,1024,1536,2048-bit state size

*Kamel Bentahar, Dan Page, Markku-Juhani O. Saarinen, Joseph H. Silverman, Nigel Smart* - **LASH**

- ,2006
- http://csrc.nist.gov/groups/ST/hash/documents/SAARINEN_lash4-1_ORIG.pdf

Bibtex**Author :**Kamel Bentahar, Dan Page, Markku-Juhani O. Saarinen, Joseph H. Silverman, Nigel Smart**Title :**LASH**In :**-**Address :****Date :**2006

## 2 Cryptanalysis

### 2.1 Best Known Results

LASH-n is vulnerable to attacks that trade time for memory, including collision attacks as fast as 2^{(4n/11)} and preimage attacks as fast as 2^{(4n/7)}.

### 2.2 Generic Attacks

### 2.3 Collision Attacks

*Ron Steinfeld, Scott Contini, Krystian Matusiewicz, Josef Pieprzyk, Jian Guo, San Ling, Huaxiong Wang* - **Cryptanalysis of LASH**

- FSE 5086:207-223,2008
- http://dx.doi.org/10.1007/978-3-540-71039-4_13

Bibtex**Author :**Ron Steinfeld, Scott Contini, Krystian Matusiewicz, Josef Pieprzyk, Jian Guo, San Ling, Huaxiong Wang**Title :**Cryptanalysis of LASH**In :**FSE -**Address :****Date :**2008