We improve the attack of Durak and Vaudenay (CRYPTO’17) on NIST Format-Preserving Encryption standard FF3, reducing the running time from O(N5) to O(N17/6) for domain ZN×ZN. Concretely, DV’s attack needs about 2^50 operations to recover encrypted 6-digit PINs, whereas ours only spends about 2^30 operations. In realizing this goal, we provide a pedagogical example of how to use distinguishing attacks to speed up slide attacks. In addition, we improve the running time of DV’s known-plaintext attack on 4-round Feistel of domain ZN×ZN from O(N3) time to just O(N5/3) time. We also generalize our attacks to a general domain ZM×ZN, allowing one to recover encrypted SSNs using about 2^50 operations. Finally, we provide some proof-of-concept implementations to empirically validate our results.
In this paper, we motivate the need for image encryption techniques that preserve certain visual features in images and hide all other information, to balance privacy and usability in the context of cloud-based image storage services. In particular, we introduce the concept of ideal or exact Thumbnail-Preserving Encryption (TPE), a special case of format-preserving encryption, and present a concrete construction. In TPE, a ciphertext is itself an image that has the same thumbnail as the plaintext (unecrypted) image, but that provably leaks nothing about the plaintext beyond its thumbnail. We provide a formal security analysis for the construction, and a prototype implementation to demonstrate compatibility with existing services. We also study the ability of users to distinguish between thumbnail images preserved by TPE. Our findings indicate that TPE is an efficient and promising approach to balance usability and privacy concerns for images. Our code and a demo are available at: http://photoencryption.org.