Tony Harminc wrote: >I've heard about this format-preserving encryption for a while, but >haven't had the justification for spending time to really understand >what goes on. But it seems to me on the face of it that any such >encryption must be substantially weaker than what we usually think of >as strong encryption. Surely for (e.g.) a 16-digit credit card number >there are only 10**16 and probably effectively *many* fewer (given a >check digit and the likelihood that the first and last four digits are >far less secure than the middle eight) encrypted possibilities, >compared to almost 2**64 or about 10**19 possibilities for an >arbitrary 8-byte block of data.
Ah, but the key (pun intended) to encryption strength isn’t the size of the target text, but the size of the keyspace. In fact, I’d argue that in some ways, FPE is *stronger*. The way to look at this is to consider a brute-force attack (never mind the practicality or lack thereof of such an approach—we’ll assume you have an entire planet full of GPU-based machines). You have a ciphertext (or set of ciphertexts), which you know to be encrypted PAN(s). With some other mode of 256-bit AES, you could instantly eliminate a given key as soon as one of the decrypted values didn’t look like a PAN. With FPE, *every* decrypted value looks like a PAN. You can eliminate some of them by looking at the Luhn, maybe (there are, amazingly, live cards out there with invalid Luhns), but you still have the same problem: you have to run through (on average) half the possible key values to find the plaintext. Let’s cheat further and assume you have matching plaintexts. That doesn’t help any—the key is the number of possible keys. In fact, as you note, with 2**256 keys, there are a bunch of possible keys that will encrypt PAN A to ciphertext A. But they won’t all encrypt PAN B to ciphertext B. So the key strength is unchanged. Independent (i.e., non-Voltage-generated) security proofs exist, and NIST has done the analysis as well. In fact, the original proposal for SP 800-38G (the NIST FPE standard) had three different FPE algorithms. One of those, which NIST calls “FF2” (Voltage FPE is “FF1”) has been dropped from the draft because a weakness was found. http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/ffsem/ffsem-spec.pdf is a reasonably readable document about Voltage FPE, by one of our big-brain crypto guys. By “reasonably readable”, I mean that I was able to mostly understand it after only a few readings ☺ https://www.voltage.com/wp-content/uploads/UCSD_Rogaway_Synopsis_Format_Preserving_Encyption-1.pdf is another document that might be interesting. Does this help? I can go on at greater length…(zzzzzzzzzz) -- …phsiii Phil Smith III Senior Architect & Product Manager, Mainframe & Enterprise HP Security Voltage [email protected]<mailto:[email protected]> T 703-476-4511 M 703-568-6662 Hewlett-Packard Company Herndon, VA ---------------------------------------------------------------------- For IBM-MAIN subscribe / signoff / archive access instructions, send email to [email protected] with the message: INFO IBM-MAIN
