Yeah, I had a similar intuition about that approach possibly being weak or problematic. However, if my cursory reading of the algorithm is at all correct, the goal may simply be to consistently choose another hash value (a different min hash) and it may work fine. In other words, the same hash values would be considered the minimum after XORing with a random number and they will be different from the initial hash that was selected as the minimum without XORing. Those are the behaviors that matter and not so much that the hashes that result from the XORing are cryptographically secure.