On Sat, May 05, 2012 at 01:47:45AM +0200, Ondrej Mikle wrote:
One trick I had in mind was create "secret hash function" (take the following with a grain of salt, algebra is not my "primary thing"):
- you keep generators g_i secret, which turns the problem from discrete-log into
a problem of finding n-th root in finite field (n is the value of the digraph, trigraph or few characters, e.g. encoded value of 'ec2bridge', possibly "blinded" by another multiplication with secret constant c_i)
- in general, computing n-th root is quite slow [1], but there are many special
cases like square root (quadratic residue)
- the above properties would make it slow for attacker to brute-force all
possible values - i.e. attacker can't just compute the result values of such homomorphic hash, because he doesn't know the function parameters (e.g. without computing the generators), but everyone can use the "homomorphic property" for testing parts
It sounds like you're talking about the homomorphic hashing paper you linked to in your last email. But there, the exponentiations are in Z_p, and taking n-th roots in Z_p is totally trivial.
I seem to have lost the thread of why we're doing this. Is it just to count how many bridges are running our ec2 / rackspace / etc. bridge images? Can't we just report that out of band? Is the EC2 IP space not known? I must be missing something.
- Ian