Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

[Tutorial] Hacking a weak hash

Revision en1, by TheScrasse, 2023-03-03 17:51:12

Hello everyone,

yesterday I hacked the following submission: 195599340. It wasn't trivial for me (I found it more difficult than solving the problem itself), but it doesn't require any weird mathematical knowledge. So, if you've never hacked before, you may want to try to hack that submission by yourself. Anyway, I wanted to share the hack as a tutorial (since I have not found similar blogs on Codeforces). Here is the "solution":

Solution

Let's read the submission. It calculates two hashes (stored in val[x]). We would like to generate a collision (= two non-isomorphic subtrees that have the same hashes). Let's notice some details:

  • The hash is deterministic (it doesn't rely on random variables), so it's potentially vulnerable.
  • The hash of small trees looks "manageable" (= it doesn't grow very fast), so it may be possible to find a collision just using small trees.

So, let's start printing the hashes of small trees. Actually it doesn't work (all those hashes are distinct). However, we can try merging those trees. In particular, if we attach a subtree with hash val[x] to node r, val[r] becomes {val[r].first * val[x].first * treeSize[x], val[r].second + (val[x].second * (treeSize[x] + 1))} (in modulo).

Now we want to attach subtrees to two nodes r, s, in such a way that their hashes become the same. So, we are interested in products of ai= val[x].first * treeSize[x] and sums of bi= val[x].second * (treeSize[x] + 1). Let's print their values for small trees Ti:

  • T1={(1,2)}, a1=6, b1=4
  • T2={(1,2),(1,3)}, a2=16, b2=9
  • T3={(1,2),(2,3)}, a3=24, b3=15
  • T4={(1,2),(1,3),(1,4)}, a4=40, b4=16
  • T5={(1,2),(1,3),(2,4)}, a5=60, b5=24
  • T6={(1,2),(2,3),(2,4)}, a6=80, b6=40
  • T7={(1,2),(2,3),(3,4)}, a7=120, b7=64

Let's find two distinct multisets of trees with equal ai and bi. That's equivalent to finding non-zero coefficients ei such that aeii=1 and biei=0 (if ei is positive, it contributes to a multiset; if it's negative, it contributes to the other multiset).

aeii=1 if the multiplicity of each prime factor is 0. For example, we can get rid of factors 2 by enforcing e3=e1, e6=e4, e7=e5 (so, we get ae11ae33=(a3/a1)e3=22e3, etc.).

Now we have only 2 equations (one for the multiplicity of 2, one for the sum), and more than 2 unknowns, so we can find a non-zero solution. One example is [16,0,16,69,37,69,37]. The total number of nodes is smaller than 2105, so we have found a hack.

Conclusions

In the next div3 / educational round, it's up to you to hack such submissions!

Bonus

Can you hack 195587728? It's still deterministic, but the hash function seems stronger. Maybe we can generate random trees with >109 nodes in total and hope that a collision happens (birthday paradox), but I have not tried.

Tags tutorial, hacking, hashing

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English TheScrasse 2023-03-03 17:51:12 3286 Initial revision (published)