FPL: White-Box Secure Block Cipher Using Parallel Table Look-Ups

Jihoon Kwon, ByeongHak Lee, Jooyoung Lee, Dukjae Moon

TL;DR

This paper introduces FPL, a novel white-box secure block cipher construction that uses parallel table look-ups. FPL offers provable security against sophisticated attacks, providing a flexible and efficient alternative for protecting cryptographic keys in environments where the implementation is fully exposed.

What Problem Does This Paper Address?

The "white-box" threat model in cryptography assumes an adversary has complete access to the encryption implementation, including the secret key. This is a significant challenge for protecting sensitive data, as an attacker could potentially extract the key through code analysis. While many white-box cryptography schemes have been proposed, they often rely on complex constructions or have been broken by subsequent attacks. This paper addresses the need for a robust, provably secure, and practical white-box block cipher that can withstand advanced cryptanalytic techniques.

Methods

The core of the proposed solution is FPL (Feistel cipher using Parallel table Look-ups), a balanced Feistel cipher. Each round of FPL uses a "probe function" to determine multiple indices into an underlying table. The sum of values retrieved from these table look-ups forms the output of the round function. This parallel table look-up mechanism is key to its efficiency and security.

The authors define specific properties for the probe function – "superposedness" and "linear independence" – which are crucial for achieving white-box security. They then provide a provable security analysis in terms of "space hardness," a notion that an adversary cannot produce a functionally equivalent program of significantly smaller size. The paper also proposes a concrete instantiation, FPLAES, which uses a round-reduced AES for its underlying tables and probe functions.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Parallel Table Look-ups for White-Box Security: The paper demonstrates that parallel table look-ups, guided by a probe function, can be a powerful primitive for constructing white-box secure ciphers. This approach offers a different paradigm compared to traditional substitution-permutation networks.
  • Provable Security via Space Hardness: By defining and analyzing security in terms of "space hardness," the authors provide a strong theoretical foundation for FPL's resistance to code lifting and other white-box attacks.
  • Flexibility and Efficiency: FPL's design allows for flexible choices in block size and table size, and its parallel nature enables efficient implementation on modern hardware.
  • Concrete Instantiation with AES: The FPLAES instantiation shows that FPL can be practically realized using well-understood components like AES, offering a balance of security and performance.

Key Results

The paper presents theoretical security bounds for FPL against known-space and non-adaptive chosen-space attacks, demonstrating its resistance to various adversarial capabilities. The FPLAES instantiation is shown to provide strong security without significant performance degradation compared to existing schemes like SPACE, WhiteBlock, and WEM. Table 1 and Table 3 provide quantitative comparisons of FPLAES's security and performance across different parameter choices and against other schemes. For instance, FPLAES-(128, 12, 40, 11) offers strong security with a table leakage of 44% for ksa-wsh and 41% for ksa-ssh.

Limitations and Future Work

The authors acknowledge that achieving strong space hardness against adaptive chosen-space attacks is challenging for any table-based white-box design. While they offer a heuristic argument for FPL's weak space hardness against such attacks, a formal proof is not provided. Future work could focus on formalizing this security for adaptive attacks and exploring further optimizations for FPL's performance and its instantiation with other primitives. The paper also suggests that FPL's design might be suitable for applications like format-preserving encryption.

Summary updated

BibTeX
@article{kwon2020fpl,
  author = {Jihoon Kwon and ByeongHak Lee and Jooyoung Lee and Dukjae Moon},
  title = {{FPL: White-Box Secure Block Cipher Using Parallel Table Look-Ups}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2020},
}
Figure