A remote data protection network provides a blind hashing service. A blind hashing server receives a message such as a digest from a client, and uses the message to derive a set of indices or offsets into a huge block of random data that is maintained by the remote data protection network. The corresponding extents of data in the block are combined, e.g. using a hash or HMAC function, and then returned to the invoking client, e.g. as a salt. The message and response may be salted with a unique client salt.