Attacking the SL2 hashing scheme

Chris Charnes; Josef Pieprzyk

doi:10.1007/BFb0000444

Attacking the SL₂ hashing scheme

Chris Charnes, Josef Pieprzyk

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

15 Citations (Scopus)

Abstract

Tillich and Zemor proposed a definition of a new hash function which uses SL₂(2,2ⁿ), the group of unimodular two-dimensional matrices with entries in GF(2ⁿ), to compute the hash values of binary strings. This hashing scheme has several attractive features; hash values can be computed quickly and small modifications to the input text can be detected. However, this scheme is weak. Using a group theoretic argument we are able to produce two distinct binary strings of small length which hash to the same value in SL₂(2,2ⁿ) for the range specified by Tillich and Zémor.

Original language	English
Title of host publication	Advances in Cryptology - ASIACRYPT 1994 - 4th International Conference on the Theory and Applications of Cryptology, Proceedings
Place of Publication	Berlin; Heidelberg
Publisher	Springer, Springer Nature
Pages	322-330
Number of pages	9
Volume	917
ISBN (Electronic)	9783540492368
ISBN (Print)	9783540593393
DOIs	https://doi.org/10.1007/BFb0000444
Publication status	Published - 1995
Externally published	Yes
Event	4th International Conference on the Theory and Applications of Cryptology, ASIACRYPT 1994 - Wollongong, Australia Duration: 28 Nov 1994 → 1 Dec 1994

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	917
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Other

Other	4th International Conference on the Theory and Applications of Cryptology, ASIACRYPT 1994
Country/Territory	Australia
City	Wollongong
Period	28/11/94 → 1/12/94

Access to Document

10.1007/BFb0000444

Cite this

Charnes, C., & Pieprzyk, J. (1995). Attacking the SL₂ hashing scheme. In Advances in Cryptology - ASIACRYPT 1994 - 4th International Conference on the Theory and Applications of Cryptology, Proceedings (Vol. 917, pp. 322-330). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 917). Springer, Springer Nature. https://doi.org/10.1007/BFb0000444

Charnes, Chris ; Pieprzyk, Josef. / Attacking the SL₂ hashing scheme. Advances in Cryptology - ASIACRYPT 1994 - 4th International Conference on the Theory and Applications of Cryptology, Proceedings. Vol. 917 Berlin; Heidelberg : Springer, Springer Nature, 1995. pp. 322-330 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{860d310d5d4d4b9390444cdadb192eaf,

title = "Attacking the SL2 hashing scheme",

abstract = "Tillich and Zemor proposed a definition of a new hash function which uses SL2(2,2n), the group of unimodular two-dimensional matrices with entries in GF(2n), to compute the hash values of binary strings. This hashing scheme has several attractive features; hash values can be computed quickly and small modifications to the input text can be detected. However, this scheme is weak. Using a group theoretic argument we are able to produce two distinct binary strings of small length which hash to the same value in SL2(2,2n) for the range specified by Tillich and Z{\'e}mor.",

author = "Chris Charnes and Josef Pieprzyk",

year = "1995",

doi = "10.1007/BFb0000444",

language = "English",

isbn = "9783540593393",

volume = "917",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer, Springer Nature",

pages = "322--330",

booktitle = "Advances in Cryptology - ASIACRYPT 1994 - 4th International Conference on the Theory and Applications of Cryptology, Proceedings",

address = "United States",

note = "4th International Conference on the Theory and Applications of Cryptology, ASIACRYPT 1994 ; Conference date: 28-11-1994 Through 01-12-1994",

}

Charnes, C & Pieprzyk, J 1995, Attacking the SL₂ hashing scheme. in Advances in Cryptology - ASIACRYPT 1994 - 4th International Conference on the Theory and Applications of Cryptology, Proceedings. vol. 917, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 917, Springer, Springer Nature, Berlin; Heidelberg, pp. 322-330, 4th International Conference on the Theory and Applications of Cryptology, ASIACRYPT 1994, Wollongong, Australia, 28/11/94. https://doi.org/10.1007/BFb0000444

Attacking the SL₂ hashing scheme. / Charnes, Chris; Pieprzyk, Josef.
Advances in Cryptology - ASIACRYPT 1994 - 4th International Conference on the Theory and Applications of Cryptology, Proceedings. Vol. 917 Berlin; Heidelberg: Springer, Springer Nature, 1995. p. 322-330 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 917).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - Attacking the SL2 hashing scheme

AU - Charnes, Chris

AU - Pieprzyk, Josef

PY - 1995

Y1 - 1995

N2 - Tillich and Zemor proposed a definition of a new hash function which uses SL2(2,2n), the group of unimodular two-dimensional matrices with entries in GF(2n), to compute the hash values of binary strings. This hashing scheme has several attractive features; hash values can be computed quickly and small modifications to the input text can be detected. However, this scheme is weak. Using a group theoretic argument we are able to produce two distinct binary strings of small length which hash to the same value in SL2(2,2n) for the range specified by Tillich and Zémor.

AB - Tillich and Zemor proposed a definition of a new hash function which uses SL2(2,2n), the group of unimodular two-dimensional matrices with entries in GF(2n), to compute the hash values of binary strings. This hashing scheme has several attractive features; hash values can be computed quickly and small modifications to the input text can be detected. However, this scheme is weak. Using a group theoretic argument we are able to produce two distinct binary strings of small length which hash to the same value in SL2(2,2n) for the range specified by Tillich and Zémor.

UR - http://www.scopus.com/inward/record.url?scp=84955579812&partnerID=8YFLogxK

U2 - 10.1007/BFb0000444

DO - 10.1007/BFb0000444

M3 - Conference proceeding contribution

AN - SCOPUS:84955579812

SN - 9783540593393

VL - 917

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 322

EP - 330

BT - Advances in Cryptology - ASIACRYPT 1994 - 4th International Conference on the Theory and Applications of Cryptology, Proceedings

PB - Springer, Springer Nature

CY - Berlin; Heidelberg

T2 - 4th International Conference on the Theory and Applications of Cryptology, ASIACRYPT 1994

Y2 - 28 November 1994 through 1 December 1994

ER -

Charnes C, Pieprzyk J. Attacking the SL₂ hashing scheme. In Advances in Cryptology - ASIACRYPT 1994 - 4th International Conference on the Theory and Applications of Cryptology, Proceedings. Vol. 917. Berlin; Heidelberg: Springer, Springer Nature. 1995. p. 322-330. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/BFb0000444