Paper 2018/534

Cryptographic Constructions Supporting Implicit Data Integrity

Michael Kounavis, David Durham, and Sergej Deutsch

Abstract

We study a methodology for supporting data integrity called \lq implicit integrity\rq $\>$ and present cryptographic constructions supporting it. Implicit integrity allows for corruption detection without producing, storing or verifying mathematical summaries of the content such as MACs and ICVs, or any other type of message expansion. As with authenticated encryption, the main idea behind this methodology is that, whereas typical user data demonstrate patterns such as repeated bytes or words, decrypted data resulting from corrupted ciphertexts no longer demonstrate such patterns. Thus, by checking the entropy of some decrypted ciphertexts, corruption can be possibly detected. The main contribution of this paper is a notion of security which is associated with implicit integrity, and which is different from the typical requirement that the output of cryptographic systems should be indistinguishable from the output of a random permutation. The notion of security we discuss reflects the fact that it should be computationally difficult for an adversary to corrupt some ciphertext so that the resulting plaintext demonstrates specific patterns. We introduce two kinds of adversaries. First, an input perturbing adversary performs content corruption attacks. Second an oracle replacing adversary performs content replay attacks. We discuss requirements for supporting implicit integrity in these two adversary models, and provide security bounds for a construction called IVP, a three-level confusion diffusion network which can support implicit integrity and is inexpensive to implement.

Note: We modified the description of the adversaries and made the introduction to the main concepts smoother. We also updated the analysis of IVP to reflect the latest findings. Many thanks to all co-authors of the previous versions for their valuable contributions!