We study the computational hardness of finding collisions in neural networks, i.e. any two sets of weights that give the same labels to a random dataset. When the number of output neurons is sufficiently large, we establish the emergence of an overlap gap in the space of collisions. This is believed to indicate that efficient algorithms will not be able to find collisions. Such claim is supported by numerical experiments using approximate message passing algorithms, which stop working below the predicted value from the analysis. Our results also show that, by composing such a collision resistant neural network with an Error Correcting Code, one can obtain a Hash Function. Beyond relevance to cryptography for designing collision resistant one-way functions, our work uncovers new forms of computational hardness emerging in large neural networks.