4
$\begingroup$

This question is in relation to Wikipedia article on Format Preserving Encryption

It says the following

It is also possible to make a FPE algorithm using a Feistel network. A Feistel network needs a source of pseudo-random values for the sub-keys for each round, and the output of the AES algorithm can be used as these pseudo-random values.

However I was taking a look at an implementation of FPE (Botan Crypto library). It is based on the scheme FE1 from the paper "Format-Preserving Encryption" by Bellare, Rogaway, et al

In the implementation I think it is using the SHA-256 hash to generate the pseudo-random values.

How does this compare (with respect to security) to the alternative of using the AES algorithm to generate the pseudo-random values?

Are both equally valid methods?

$\endgroup$
  • $\begingroup$ I guess it was the easiest and most straightforward choice as it looks like you can just feed all the stuff in and don't have to care about things like keys as you'd have to with AES and SHA-256 accepts any length inputs whereas AES requires 128-bit length inputs (+ 128/256 bit keys). $\endgroup$ – SEJPM Sep 1 '15 at 16:51
  • $\begingroup$ @SEJPM: no matter what primitive you use, you need to care about keys; a totally unkeyed FPE algorithm may have some security problems... $\endgroup$ – poncho Sep 1 '15 at 17:03
  • $\begingroup$ @poncho Well,... ok, looks like I didn't think hard enough before commenting... But one would still have the problem of somehow feeding in the other four inputs which means you can't use a single AES block but rather need to use some mode, which may fail at providing the neccessary security properties and needs more thought than using SHA-256 which is just a "fire-and-forget" solution. $\endgroup$ – SEJPM Sep 1 '15 at 17:11
  • $\begingroup$ Don't forget to accept any one of the answers if they sufficiently answer your question. $\endgroup$ – Maarten Bodewes Sep 5 '15 at 12:17
  • $\begingroup$ @SEJPM Can you elaborate on this - " you can't use a single AES block but rather need to use some mode, which may fail at providing the neccessary security properties and needs more thought" $\endgroup$ – erotavlas Sep 22 '15 at 17:51
8
$\begingroup$

A Feistel network is a way of constructing an invertible permutation from a (possibly non-invertible) function. If the function used is pseudorandom and has a large domain, then 3-4 rounds yields a pseudorandom permutation (3 rounds suffice if the adversary can only ask "compute" queries, and 4 rounds are needed if the adversary can ask "invert" queries). This is the famous Luby-Rackoff result. In the format-preserving constructions, more rounds are needed since the domain of the function can be small and this means that collisions are likely, etc.

In any case, these constructions can use ANY pseudorandom function. Thus, AES truncated to the appropriate output length is fine. HMAC is also very reasonably considered a pseudorandom function. Is plain SHA256 a pseudorandom function? Well, it depends exactly on what you do. If you compute $F_K(x) = SHA256(K || x)$ then this is certainly not pseudorandom due to extension attacks (given $F_K(x)$ it is possible to compute $F_K(x||y)$ for some $y$). However, if you know that you are only using a fixed length, or you encode that length, then it's a reasonable assumption. Personally, I prefer the HMAC assumption if you wish to base yourself on a hash function. However, I think that AES is the best choice (it's also much faster...).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.