Text

theses

emph{Property-preserving encryption} (PPE) provides accessible methods to encrypt the databases in an efficient way by preserving specific fuctionalities of databases. PPE as an impactful research area accommodates deterministic encryption, order-revealing encryption (ORE) and format-preserving encryption (FPE). Although the simplicity and compatibility of PPE makes it demanding in real world systems, the security of these primitives has been unclear since their invention. In this work, we study and explore the range of threats in ORE and FPE established with a Feistel network as the elementary unit. We take system- and theory-centric approach to address the issues in ORE, FPE, and Feistel networks which form building blocks of some particular FPE schemes (and potentially many other constructions) of our interest. %Dataset characteristics for which ORE is especially insecure have been identified, such as small message spaces and low-entropy distributions. On the other hand, properties like one-wayness on uniformly-distributed datasets have been proved for ORE constructions. We start with ORE where the ordering relation of messages is preserved (and revealed) on corresponding after encryption. In our work, we demonstrate two issues in ORE: firstly, we show that when multiple columns of correlated data are encrypted with ORE, attacks can use the encrypted columns together to reveal more information than prior attacks could extract from the columns individually. Secondly, we apply known attacks, and develop new attacks, to show that the emph{leakage} of concrete ORE schemes on non-uniform data leads to more accurate plaintext recovery than is suggested by the security theorems which only deal with uniform inputs. We then consider the recently published FPE standards: FF1 and FF3, by The National Institute of Standards and Technology (NIST) . Particularly, FF1 and FF3 are both tweakable block cipher based on Feistel network (FN). Feistel network in FPE is an iterative cipher that are composed of multiple rounds to encrypt the plaintext by breaking it into left and right branches. Each iteration, called round, consists of a secret round function (i.e. a keyed pseudo-random function) and modular addition. In each round, one half of the input is evaluated with a round function and then applied by modular addition with the other half (which is preserved for the next round). The outputs are permuted and then input to the next round. The security of FN hinges on the security of its round functions and the number of iterations (more iteratitions assure stronger security at the cost of efficiency). In the NIST standards, FF1 and FF3 are AES-based modes of operation composed with 10-round and 8-round Feistel network respectively. FPE is specifically designed for small domain sizes when $N^2 geq 10$ where $N$ is the branch size of Feistel network. In this work, we investigate the security of Feistel network thoroughly since its security has not yet been understood well with already existing theoretical analyses to integrate with small domains. %FN is a potential cipher to develop new efficient tools to encrypt databases just as in FPE. ofix{Can you help me to make last two sentence better? What I am trying to say is that the security of FN ``could'' be important for encrypted databases}. We develop a set of new generic attacks for Feistel network that have direct effect on FF1 and FF3. First, we give a generic known-plaintext attack to a 4-round Feistel network that reconstructs the entire tables for all round functions. It requires a data complexity of $N^{frac{3}{2}} left( frac{N}{2}
ight)^{frac{1}{6}}$ known plaintexts and time complexity of $O(N^{3})$. Our 4-round attack can be easily extended to five or more rounds with complexity $N^{(r-5)N+o(N)}$. We continue further to explore more generic attacks on arbitrary number of rounds that covers 8-round and 10-round Feistel network. In that direction, our ideas are developed around exhaustive search on the round functions by using an early abort that eliminates as many candidates as possible during the reconstruction phase of round function. We conclude that neither FF1 when $N leq 11$ nor FF3 when $ Nleq14$ offers 128-bit security. Finally, we give a new total break attack to the FF3 scheme by exploiting the bad domain separation in its design. It is practical when the domain size is small. Our attack is not generic and enables slide attack due to its weak design. Luckily, we can provide an easy and intuitive fix to prevent the FF3 scheme from our attack. A follow-up work after the slide attack to the FF3, we develop a new generic attacks on Feistel networks (without restricting ourselves to any of its system design). Unfortunately, our research indicates that the security assurance of FF3 is still not viable even with our suggested patch when the domain size is tiny.

ETD_8314

Ph.D.

Includes bibliographical references

by Fatma Durak

doi:10.7282/T39P34SW

ETD doctoral

The author owns the copyright to this work.