Timeline for How hard is it to find plaintexts whose hashes satisfy $h(a)\oplus h(b)=h(c)$?
Current License: CC BY-SA 4.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 10, 2020 at 9:25 | history | edited | fgrieu♦ | CC BY-SA 4.0 |
Modernize links
|
| Feb 7, 2015 at 14:56 | history | edited | fgrieu♦ | CC BY-SA 3.0 |
Add missing word
|
| Feb 7, 2015 at 14:49 | comment | added | fgrieu♦ | @Hyperflame: Ah, I now see what you mean. I have changed the answer to clarify that I meant cost in units of work for a hash, and added discussion of number of (queries to an oracle implementing the) hash for an infinitely powerful adversary. | |
| Feb 7, 2015 at 14:46 | history | edited | fgrieu♦ | CC BY-SA 3.0 |
distinguish hash from work for a hash
|
| Feb 7, 2015 at 9:14 | comment | added | Fractalice | @fgrieu: I am confused that you say your bound is on the number of hashes. The first part of your answer provides both lower and upper bound on number of hashes, $O(2^{n/3})$. Of course number of all operations on hashes may be larger. A trivial meet-in-the middle will do it in $O(2^{2n/3})$ operations, so still finding collisions on $g(x)$ in $O(2^{n/2})$ is faster but requires more hashes. | |
| Feb 6, 2015 at 11:03 | history | edited | fgrieu♦ | CC BY-SA 3.0 |
H -> h
|
| Feb 6, 2015 at 8:30 | history | edited | fgrieu♦ | CC BY-SA 3.0 |
typo
|
| Feb 6, 2015 at 7:51 | comment | added | fgrieu♦ | @Hyperflame: see first paragraph in the second part of the updated answer. | |
| Feb 6, 2015 at 7:49 | history | edited | fgrieu♦ | CC BY-SA 3.0 |
Give both lower and upper bounds
|
| Feb 5, 2015 at 22:56 | comment | added | Fractalice | but doesn't this answer provide an upper bound also? I don't understand why it's stated as lower bound. | |
| Feb 1, 2015 at 20:13 | comment | added | D.W. | @JohnMeacham, I'm not familiar with SWIFFT, but if it satisfies $f(a+b)=f(a)+f(b)$, I would not call it a cryptographic hash function. The question specifically asks about cryptographic hash functions (and mentions SHA256 as an example); the term "cryptographic hash function" is often understood to require that the hash is effectively pseudorandom. So I think your criticism is debatable. If you have questions about what the OP meant by "cryptographic hash function", I suggest posting a comment underneath the question to ask the original poster to clarify. | |
| Feb 1, 2015 at 18:05 | history | edited | fgrieu♦ | CC BY-SA 3.0 |
Try to make the reasoning closer to correct; I'm not sure that it is quite.
|
| Feb 1, 2015 at 11:04 | history | edited | fgrieu♦ | CC BY-SA 3.0 |
the messages $M$ need not be random
|
| Feb 1, 2015 at 10:54 | history | edited | fgrieu♦ | CC BY-SA 3.0 |
Made hypothesis that $h$ behaves like a random function explicit
|
| Jan 31, 2015 at 2:01 | comment | added | John Meacham | Not true for all cryptographic hash functions, there are cryptographically strong hash functions for which generating triples of this form are downright trivial. notably SWIFFT where f(a + b) = f(a) + f(b) your answer is valid for cryptographic hashes that are also psuedorandom though, because if there were an easier than brute force way to generate the triples it would distinguish the function from a random function. | |
| Jan 30, 2015 at 22:43 | comment | added | poncho | @RobertNACIRI: yes; the obvious approach is to pick an arbitrary $a$, and then use a birthday attack to find a $b, c$. | |
| Jan 30, 2015 at 22:36 | comment | added | Robert NACIRI | @Poncho: Did you think to Birthday attack when you claim $O(2^{n/2})$ ? | |
| Jan 30, 2015 at 18:51 | comment | added | poncho | And it's easy to show that it's at most $O(2^{n/2})$ -- how can we establish where in that range the answer is? | |
| Jan 30, 2015 at 18:30 | history | answered | fgrieu♦ | CC BY-SA 3.0 |