Publication Details
Title: Black Box Cryptanalysis of Hash Networks Based on Multipermutations
Author: C. P. Schnorr and S. Vaudenay
Group: ICSI Technical Reports
Date: April 1994
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1994/tr-94-017.pdf
Overview:
Black box cryptanalysis applies to hash algorithms consisting of many small boxes, connected by a known graph structure, so that the boxes can be evaluated forward and backwards by given oracles. We study attacks that work for any choice of the black boxes, i.e. we scrutinize the given graph structure. For example we analyze the graph of the fast Fourier transform (FFT). We present optimal black box inversions of FFT-compression functions and black box constructions of collisions. This determines the minimal depth of FFT-compression networks for collision-resistant hashing. We propose the concept of multipermutation, which is a pair of orthogonal latin squares, as a new cryptographic primitive that generalizes the boxes of the FFT. Our examples of multipermutations are based on the operations circular rotation, bitwise xor, addition and multiplication.
Bibliographic Information:
ICSI Technical Report TR-94-017
Bibliographic Reference:
C. P. Schnorr and S. Vaudenay. Black Box Cryptanalysis of Hash Networks Based on Multipermutations. ICSI Technical Report TR-94-017, April 1994
Author: C. P. Schnorr and S. Vaudenay
Group: ICSI Technical Reports
Date: April 1994
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1994/tr-94-017.pdf
Overview:
Black box cryptanalysis applies to hash algorithms consisting of many small boxes, connected by a known graph structure, so that the boxes can be evaluated forward and backwards by given oracles. We study attacks that work for any choice of the black boxes, i.e. we scrutinize the given graph structure. For example we analyze the graph of the fast Fourier transform (FFT). We present optimal black box inversions of FFT-compression functions and black box constructions of collisions. This determines the minimal depth of FFT-compression networks for collision-resistant hashing. We propose the concept of multipermutation, which is a pair of orthogonal latin squares, as a new cryptographic primitive that generalizes the boxes of the FFT. Our examples of multipermutations are based on the operations circular rotation, bitwise xor, addition and multiplication.
Bibliographic Information:
ICSI Technical Report TR-94-017
Bibliographic Reference:
C. P. Schnorr and S. Vaudenay. Black Box Cryptanalysis of Hash Networks Based on Multipermutations. ICSI Technical Report TR-94-017, April 1994