Creating an Order Column for encrypted data

Question

I am saving encrypted data to a database.

Is there a way I can create a "hashcode" or fingerprint or checksum of the plain text data, that if I sort / order by on the "hashcode" the order would be the same as if I had saved the plain text data and perform the same sort / order by operation on it?

I basically need a SOUNDEX() type function that will give me a value that will maintain the order of the plain text data. I would then save both encrypted data and the "hashcode" and when querying the data order by the "hashcode" field.

I need to perform this in the application and preferably not in the SQL DB if at all possible.

I am using Entity Framework and SQL 2008 and C# 4.0.

Answer 1

Encrypting intentionally destroys any apparent structure in the plaintext, so any ordering structure will also be destroyed. Using a non-cryptographic hashcode will cause a potential security leak, given the known structure of the unencrypted records.

You could easily create an order column from the unencrypted data and store that, but it would require decrypting all or part of the database every time a new record was added.

You could start by numbering the records every ten: 10, 20, 30, ... which would allow the insertion of new records using binary search. Every so often decrypt and renumber the entire database, restoring the gaps between records. Not an ideal solution, but a possible one.