How to blow up too weak hashing without thinking

Revision en2, by physics0523, 2024-05-02 23:29:44

Sadly, until today, many people use single $$$\rm{mod} = 10^9+7$$$ or so on for hashing, so why not write how to blow up them easily, with minimized thinking process?

The key idea is simple. Just use Birthday attack.

  1. Write a function to calculate the hash value
  2. Write a random generator of string
  3. When there are $$$k$$$ possible distinct hash values, look up $$$O(\sqrt{k})$$$ random candidates
  4. Now we get a pair of strings that has exactly the same hash value!

In this method, the only things we should consider are that $$$k$$$ is small enough (around $$$k \le 10^{12}$$$ ), and the number of possible candidates is large enough. We don't need to care about what the hashing function is!

Example Code(C++)

Exercise:
Find two $$$18$$$-digit integers $$$x,y$$$ such that:

  • Each digit of $$$x,y$$$ are $$$1,3,5,7,9$$$
  • $$$x \equiv y \mod 998244353$$$
Short Explanation
Example Code(C++)
... then how to avoid attacking?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English physics0523 2024-05-02 23:29:44 281 Tiny change: 'hash value.\n- Add r' -> 'hash values.\n- Add r'
en1 English physics0523 2024-05-02 23:23:42 3408 Initial revision (published)