123 reputation
4
bio website
location
age
visits member for 1 year, 4 months
seen Sep 14 '13 at 19:06

Jul
23
awarded  Editor
Jul
23
awarded  Supporter
Jul
23
revised Compare two hashes with different salt
added 1107 characters in body
Jul
14
awarded  Scholar
Jul
14
accepted Compare two hashes with different salt
Jul
12
comment Compare two hashes with different salt
Beautiful!! Thanks!
Jul
12
comment Compare two hashes with different salt
Thanks! This sounds really interesting. I don't know much about eliptic curve crypto, so I'm not sure if this does what I want, but this gives me a great place to start.
Jul
12
comment Compare two hashes with different salt
I'm sorry I'm still not getting this. I really do appreciate the time you're putting in here. As I understand it, without a salt you can use a rainbow table to do an O(1) lookup of a hash. Thus the time required to crack a single hash is O(1). In your response, you say that with $f$ you can crack a hash by computing $f(C_a, C_i)$ for all $C_i$ which is $O(n)$, where $n$ is the number of credit cards in the world. Without $f$ you'd compute the salted hash of every credit card numbrer for a complexity of $O(n)$. Thus, the time to crack appears the same with or without $f$. What am I missing?
Jul
12
comment Compare two hashes with different salt
Isn't computing $f(C_a, C_i)$ for all $C_i$ the same amount of work as computing $Hash(C_i, Salt)$ for all credit card numbers? In other words, I don't see how the existence of the rainbow table makes cracking things any faster if $f$ exists. What am I missing. I definitely understand the concerns about using a fast hash and the small space of credit card #'s.
Jul
12
comment Compare two hashes with different salt
Ack! I'm sorry, hit enter before I was ready and the comment didn't format right: "Compare C_a against all C_i using the method we assume exists". I think this equates to the following: for each H_i in the DB we want to crack: for each H_j in the rainbow table: if f(H_i, S_i, 0) == f(H_j, 0, S_i): H_i corresponds to C_j, break So we have to compute something for every user, CC# combination, which is the same amount of work we'd have to do if f() didn't exist. If that's incorrect, could you perhaps show me some pseudo-code to demonstrate the attack? Thanks!!
Jul
12
comment Compare two hashes with different salt
I don't understand why you'd have to be able to "undo" the hash. For example, if hash(C1 || S1 || S2) == hash(C1 || S2 || S1) you can do this but you can't necessarily reverse the hash. The above doesn't work because order is important in hashing, but it's not obvious to me that this is impossible.
Jul
12
awarded  Student
Jul
12
comment Compare two hashes with different salt
I don't follow. I thought the purpose was to prevent rainbow table attacks. It seems that the existence of f doesn't necessarily mean a rainbow table attack is now possible. Note that f doesn't reveal the credit card number, it just tells me if C1 = C2. If I had a rainbow table, I'd still have to compute f(table entry, salt) for each entry in the database, which isn't any faster than just computing the salted hash of every possible credit card, right?
Jul
12
asked Compare two hashes with different salt