Design and Analysis of Some Symmetric Key Schemes for Encryption and Authentication

Abstract

This thesis mainly focuses on the design and analysis of tweakable enciphering schemes (TESs) and message authentication codes (MACs). Tweakable enciphering schemes are length preserving encryption schemes that provide security of a strong tweakable pseudorandom permutation. There are several constructions of TES using block ciphers as the main cryptographic primitive. Recently, public random permutations have been widely considered as a replacement for block ciphers in several cryptographic schemes, including Authenticated Encryption (AE) schemes, MACs, etc. However, to the best of our knowledge, a systematic study of constructing TESs using public random permutations is missing. We fill this gap by constructing TES using public permutations. We propose two main constructions with several variants. The basic construction, which we call ppTES is generically constructed using a public random permutation, a length expanding pseudorandom function (PRF) based on public random permutations and an almost xor-universal and almost-regular (AXUAR) hash function. We show a concrete instantiation of ppTES and prove its security using the H-Coefficient technique. ppTES requires both forward and inverse calls to the public random permutation. Most public random permutations are designed with the goal of making the forward calls extremely fast. Thus, a TES construction that does not need computing the inverse of a permutation will have better efficiency. This fact leads us to design a TES that uses a public permutation but does not require the inverse calls to the permutation. We call this construction as IpTES. In addition to a public permutation, IpTES uses an AXUAR hash function. To ensure the inverse free property, we suitably use a two-round Feistel structure. We prove that IpTES is a birthday bound secure public permutation based TES. The rest of the work is on MACs. TrCBC is a variant of the famous CBC MAC which was proposed by Zhang et al. in 2012. It was claimed that TrCBC is a secure MAC with significant efficiency advantages over other secure variants of CBC. The authors also mentioned the only disadvantage of TrCBC to be the fact that it produces shorter tags; in particular, it was claimed that TrCBC can only produce secure tags of length less than n=2, where n is the block length of the underlying block cipher. We mount a concrete practical attack on TrCBC. We show that with high probability, an adversary can forge TrCBC with tag length n=2 􀀀 1 with just three queries. We discuss some general scenarios of our concrete attack and also do a detailed analysis of the authors’ security claims of TrCBC. Next, we study variable output length pseudorandom functions and their use in constructing secure MACs, which can produce tags of varying lengths using the same key. In this regard, we propose a generic construction of converting a fixed output length PRF to a variable output length PRF and discuss its utility in constructing MACs. We also propose some modifications to the famous block cipher based MAC called PMAC to equip it to produce tags of varying lengths. Finally, we do an extensive study of a newly proposed MAC, 2k-LightMAC_Plus. 2k-LightMAC_Plus was proposed by Datta et al. in FSE 2018, where the author proved that the scheme provides 2n=3 bits of security. We improve this bound and show that 2k-LightMAC_Plus provably achieves 3n=4 bit security. We also exhibit a matching attack on the construction and hence establish that our bound is tight. Our proof uses several components of Mirror Theory.