[math-fun] How good are "Galois Hash" functions as hash functions?
[I apologize for this possible duplicate: I was inadvertently disconnected from math-fun for the past few weeks, so I missed any answers.] So-called "Galois Hash" ("GHASH") functions are used in some MAC codes today, and run reasonably fast due to new instructions on Intel & other processors. To a zero-th order approximation, GHASH(k,M)=M(k), where M is a vector of polynomial coefficients, M(k) denotes polynomial evaluation of M(x) at x=k, for secret key k, and algebra is performed over various interesting rings. (I'm purposely staying away from the actual NIST GHASH, because it has been optimized in a number of ways for both security and performance that I'm not worried about for the purpose of this email.) Since the "message" is encoded in the poly coefficients, we have a huge amount of machinery to bring to bear in any analysis, all the way up to and including FFT's. Depending upon the chosen ring, these poly coefficients might be fixed-size blocks of bits from the message. So how good are these types of hash functions in performing hashes such as the kinds of things that SHA1 & SHA-256 are used for -- e.g., detecting changes in movie-length (4 GByte) files ? For my purposes right now, I'm not at all worried about CPU performance, but performance in the sense of detecting changes, given a particular number of hash output bits.
I think there are some bounds in the CRYPTO '96 paper: "Universal Hash Functions from Exponential Sums over Finite Fields and Galois Rings" These are derived from previous results. Hilarie
So-called "Galois Hash" ("GHASH") functions are used in some MAC codes today, and run reasonably fast due to new instructions on Intel & other processors.
To a zero-th order approximation, GHASH(k,M)=M(k), where M is a vector of polynomial coefficients, M(k) denotes polynomial evaluation of M(x) at x=k, for secret key k, and algebra is performed over various interesting rings. (I'm purposely staying away from the actual NIST GHASH, because it has been optimized in a number of ways for both security and performance that I'm not worried about for the purpose of this email.)
Since the "message" is encoded in the poly coefficients, we have a huge amount of machinery to bring to bear in any analysis, all the way up to and including FFT's. Depending upon the chosen ring, these poly coefficients might be fixed-size blocks of bits from the message.
So how good are these types of hash functions in performing hashes such as the kinds of things that SHA1 & SHA-256 are used for -- e.g., detecting changes in movie-length (4 GByte) files ?
For my purposes right now, I'm not at all worried about CPU performance, but performance in the sense of detecting changes, given a particular number of hash output bits.
participants (2)
-
Henry Baker -
Hilarie Orman