# Is there a format preserving cryptographically secure hash?

I want a way to 'scramble' strings (like words, names) in a predictable way but I don't ever want to (myself or anyone else) be able to 'unscramble' the strings.

I found that perhaps what I am looking for is a cryptographically secure hash.

But can it do these things

1 - preserve the length of the original string?

2 - preserve the format (keep numbers as numbers, or characters within certain ranges)

3 - Collision resistant

4 - Reusable for a finite length of time - like over a few minutes to a few months (i need to reuse the algorithm over and over so that a string 'scrambled' today will come out the exact same way in the future using the same algorithm)

EDIT: The reason why I use the term cryptographically secure hash is that it is supposed to be 'practically impossible' to invert. It is the impossible to invert feature that I am looking for. I do not care to recover the meaning or content of the original message. i.e. For example using encryption, I do not want someone to be able to determine a 'key' by analyzing the output message, or find patterns in the output message that would enable them to determine the input message.

I think the closest to what I seek is probably Format Preserving Encryption, however, the concern is the fact that the encryption is reversible. I'm curious if it can be made irreversible. Then a hash came to mind.

• 1&2 is easy. $\:$ Rank-then-hash-then-unrank can plausibly do 1&2&3 against uniform adversaries.
– user991
Mar 6, 2015 at 5:55
• If hash preserves the length of the original string then it is just a permutation (like block cipher). Use a FPE algorithm to encrypt the input and throw the key, consider the ciphertext as your hash ! Mar 6, 2015 at 9:26
• @sashank: If $P\to C=E_K(P)$ is a block cipher of 128-bit block size and key size assimilated to a random oracle implementing a random permutation for each $K$ (e.g. AES-128), then $P\to H(P)=E_P(P)$ is a plausible 128-bit hash that preserves the length of the original string. I'm reading Ricky Demer's comment as using something on that tune.
– fgrieu
Mar 6, 2015 at 11:14
• I think it is required to fully state your requirements for this "encryption". Encryption is about confidentiality, a hash is about creating a 1:1 relation with a statically sized value. Maybe you could state them separately below the question? Mar 6, 2015 at 11:38
• @sashank The only issue is that that isn't reproducible -- a hash always produced the same output on the same input, but if you're using a cipher, you'd have to keep the key to do that. Mar 6, 2015 at 14:15

Cryptographically secure hashes usually work on bitstrings of arbitrary length and output a fixed length bitstring. The secure part is being collision resistant and preimage resistant, so that you have a practical oneway function, and those are the properties you want for "scrambling".

As fgrieu psted in the comments, one easy way to do this is to utilize an encryption scheme, and use the plaintext for the key as well. That means, in order to decrypt the ciphertext you would need the plaintext. Formally:

$$F(p):= E_p(p)$$ with $E_k(p)$ denoting an encryption method with key $p$. If you want to utilize format preserving encryption, you might have to make adaptions how the plaintext actually is used for the "key input".

One more remark: Usually the key should be generated uniform randomly, and depending on your format, this might not be true. Therefore, if you use a normal hash function on the input $p$, then you should get a uniformly distributed hash value, and if you use this as key, you should be fine. Theoretic remark: In the random oracle model this should work just fine. So, we can adapt this to:

$$F(p):= \hat{E}_{H(p)}(p)$$

with a format preserving encryption function $\hat{E}_k(p)$ and a cryptographically secure hash function $H(p)$, where the key length $|k|$ is equal or less than the length of the output of the hash function $|H(p)|$.

• I like the idea of using the input plaintext as the key. If I'm passing my plaintext through a format preserving encryption, does the hash function I use on the plaintext (when constructing the key) need to be a cryptographically secure hash? (or did you mean it doesnn't when you said 'normal hash function') May 1, 2015 at 15:13
• As noted in the last sentence, it should be a cryptographically secure one. I am not entirely sure if it is strictly needed, but it wouldn't hurt.
– tylo
May 4, 2015 at 10:55
• Doesn't this still make the FPE vulnerable to brute force attack? I mean if the attacker knows the algorithm, and the method for generating the key from input plaintext. Oct 23, 2015 at 2:00
• This is not about the construction of FPE. It is about creating a cryptographic hash function (and utilizing FPE to do so). Cryptographically secure hash functions don't protect against brute force (of small message spaces) at all. It is about collision resistance and preimage resistance. If short message spaces are a problem, you should use a construction with a key anyway (e.g. MAC).
– tylo
Oct 23, 2015 at 14:21