What a lovely hat

This work describes vulnerabilities in the specification of the AEAD packets as introduced in the novel LibrePGP specification that is implemented by the widely used GnuPG application and the AES-based AEAD schemes as well as the Key Wrap Algorithm specified in the Cryptographic Message Syntax (CMS). These new attacks exploit the possibility to downgrade AEAD or AES Key Wrap ciphertexts to valid legacy CFB- or CBC-encrypted related ciphertexts and require that the attacker learns the...

In this research, we introduce MIND-Crypt, a novel attack framework that uses deep learning (DL) and transfer learning (TL) to challenge the indistinguishability of block ciphers, specifically SPECK32/64 encryption algorithm in CBC mode (Cipher Block Chaining) against Known Plaintext Attacks (KPA). Our methodology includes training a DL model with ciphertexts of two messages encrypted using the same key. The selected messages have the same byte-length and differ by only one bit at the binary...

To improve the throughput of Byzantine Fault Tolerance (BFT) consensus protocols, the Directed Acyclic Graph (DAG) topology has been introduced to parallel data processing, leading to the development of DAG-based BFT consensus. However, existing DAG-based works heavily rely on Reliable Broadcast (RBC) protocols for block broadcasting, which introduces significant latency due to the three communication steps involved in each RBC. For instance, DAGRider, a representative DAG-based protocol,...

To enable parallel processing, the Directed Acyclic Graph (DAG) structure is introduced to the design of asynchronous Byzantine Fault Tolerant (BFT) consensus protocols, known as DAG-based BFT. Existing DAG-based BFT protocols operate in successive waves, with each wave containing three or four Reliable Broadcast (RBC) rounds to broadcast data, resulting in high latency due to the three communication steps required in each RBC. For instance, Tusk, a state-of-the-art DAG-based BFT protocol,...

Let's consider a scenario where the server encrypts data using AES-CBC without authentication and then sends only the encrypted ciphertext through TLS (without IV). Then, having a padding oracle, we managed to recover the initialization vector and the sensitive data, doing a cybersecurity audit for a Chilean company.

Syndrome-based early epidemic warning plays a vital role in preventing and controlling unknown epidemic outbreaks. It monitors the frequency of each syndrome, issues a warning if some frequency is aberrant, identifies potential epidemic outbreaks, and alerts governments as early as possible. Existing systems adopt a cloud-assisted paradigm to achieve cross-facility statistics on the syndrome frequencies. However, in these systems, all symptom data would be directly leaked to the cloud, which...

Fault injection attacks represent an effective threat to embedded systems. Recently, Laurent et al. have reported that fault injection attacks can leverage faults inside the microarchitecture. However, state-of-the-art counter-measures, hardware-only or with hardware support, do not consider the integrity of microarchitecture control signals that are the target of these faults. We present MAFIA, a microarchitecture protection against fault injection attacks. MAFIA ensures integrity of...

Incompressibility is a popular security notion for white-box cryptography and captures that a large encryption program cannot be compressed without losing functionality. Fouque, Karpman, Kirchner and Minaud (FKKM) defined strong incompressibility, where a compressed program should not even help to distinguish encryptions of two messages of equal length. Equivalently, the notion can be phrased as indistinguishability under chosen-plaintext attacks and key-leakage (LK-IND-CPA), where the...

Code-Based Cryptosystem, CBC, is one of the candidates for Post-Quantum Cryptosystems, PQCs. Its security primarily bases on the Syndrome Decoding Problem, SDP. In this paper, we focus on the rank CBC whose security relies on the rank SDP. The GRS (Gaborit-Ruatta-Schrek) algorithm is well known as the current best decoding algorithm for the rank SDP. We propose the quantum version of the GRS algorithm. Then, we introduce the attack strategy using that quantum algorithm for previous rank...

In this paper we formally introduce a novel mode of operation based on the cipher block chaining mode. The main idea of this mode is to use a stateful block cipher instead of a stateless one. Afterwards, we show how to implement our proposal and present a performance analysis of our mode. Next, we provide a concrete security analysis by computing a tight bound on the success of adversaries based on their resources. The results of our performance and security analyses are that this novel mode...

We study the post-quantum security of authenticated encryption (AE) schemes, designed with classical security in mind. Under superposition attacks, many CBC-MAC variants have been broken, and AE modes employing those variants, such as EAX and GCM, thus fail at authenticity. As we show, the same modes are IND-qCPA insecure, i.e., they fail to provide privacy under superposition attacks. However, a constrained version of GCM is IND-qCPA secure, and a nonce-based variant of the CBC-MAC is...

Since 2016, NIST has been standardrizing Post-Quantum Cryptosystems, PQCs. Code-Based Cryptosystem, CBC, which is considered to be one of PQCs, uses the Syndrome Decoding Problem as the basis for its security. NIST's PQC standardization project is currently in its 4th round and some CBC encryption schemes remain there. In this paper, we consider the quantum security for these cryptosystems.

OMAC --- a single-keyed variant of CBC-MAC by Iwata and Kurosawa --- is a widely used and standardized (NIST FIPS 800-38B, ISO/IEC 29167-10:2017) message authentication code (MAC) algorithm. The best security bound for OMAC is due to Nandi who proved that OMAC's pseudorandom function (PRF) advantage is upper bounded by $ O(q^2\ell/2^n) $, where $ n $, $ q $, and $ \ell $, denote the block size of the underlying block cipher, the number of queries, and the maximum permissible query length (in...

3kf9 is a three-key CBC-type MAC that enhances the standardized integrity algorithm f9 (3GPP-MAC). It has beyond-birthday-bound security and is expected to be a possible candidate in constrained environments when instantiated with lightweight blockciphers. Two variants 2kf9 and 1kf9 were proposed to reduce key size for efficiency, but recently, Leurent et al. (CRYPTO'18) and Shen et al. (CRYPTO'21) pointed out critical flaws on these two variants and invalidated their security proofs with...

TrCBC is a variant of CBC-MAC which appeared in Information Processing Letters, 112(7):302-307, 2012. The authors claimed TrCBC to be a secure message authentication code (MAC) with some interesting properties. If TrCBC is instantiated with a block cipher with block length n, then it requires ⌈λ/n⌉ block cipher calls for authenticating a λ-bit message and requires a single key, which is the block cipher key. The authors state that TrCBC can have tag lengths of size less than n/2. We show...

We fully characterize the post-quantum security of the \(\mathsf{CBC}\), \(\mathsf{CFB}\), \(\mathsf{OFB}\) and \(\mathsf{CTR}\) modes of operation by considering all possible notions of \(\textsf{qIND-qCPA}\) security defined by Carstens, Ebrahimi, Tabia and Unruh (TCC 2021), thus extending the work performed by Anand, Targhi, Tabia and Unruh (PQCrypto 2016). We show that the results obtained by Anand et al. for the \(\textsf{qIND-qCPA-P6}\) security of these modes carry on to the other...

Industry 4.0 is all about doing things in a concurrent, secure, and fine-grained manner. IoT edge-sensors and their associated data play a predominant role in today's industry ecosystem. Breaching data or forging source devices after injecting advanced persistent threats (APT) damages the industry owners' money and loss of operators' lives. The existing challenges include APT injection attacks targeting vulnerable edge devices, insecure data transportation, trust inconsistencies among...

A large number of the symmetric-key mode of operations, such as classical CBC-MAC, have serial structures. While a serial mode gives an implementation advantage in terms of required memory or footprint compared to the parallel counterparts, it wastes the capability of parallel process even when it is available. The problem is becoming more relevant as lightweight cryptography is going to be deployed in the real world. In this article, we propose an alternative implementation strategy for...

The problem of Byzantine Fault Tolerance (BFT) has received a lot of attention in the last 30 years. The seminal work by Fisher, Lynch, and Paterson (FLP) shows that there does not exist a deterministic BFT protocol in complete asynchronous networks against a single failure. In order to address this challenge, researchers have designed randomized BFT protocols in asynchronous networks and deterministic BFT protocols in partial synchronous networks. For both kinds of protocols, a basic...

We propose HERMES, a scalable, secure, and privacy-enhancing system for users to share and access vehicles. HERMES securely outsources operations of vehicle access token generation to a set of untrusted servers. It builds on an earlier proposal, namely SePCAR [1], and extends the system design for improved efficiency and scalability. To cater to system and user needs for secure and private computations, HERMES utilizes and combines several cryptographic primitives with secure multiparty...

We present malleability attacks against encrypted binary executable files when they are encrypted by CBC mode of operation. While the CBC malleability is classic and has been used to attack on various real-world applications, the risk of encrypting binary executable via CBC mode on common OSs has not been widely recognized. We showed that, with a certain non-negligible probability, it is possible to manipulate the CBC-encrypted binary files so that the decryption result allows an arbitrary...

In an article from HOST 2018, which appears in extended form in the Cryptology ePrint Archive, Baksi, Bhasin, Breier, Khairallah, and Peyrin proposed the tweak-in-plaintext method to protect block ciphers against a differential fault analysis (DFA). We argue that this method lacks existential motivation as neither of its two envisioned use cases, i.e., the electronic codebook (ECB) and the cipher block chaining (CBC) modes of operation, is competitive. Furthermore, in a variant of the method...

Ethereum Research team has proposed a family of Casper blockchain consensus protocols. It has been shown in the literature that the Casper Friendly Finality Gadget (Casper FFG) cannot achieve liveness property in partially synchronous networks such as the Internet environment. The ``Correct-by-Construction'' family of Casper blockchain consensus protocols (CBC Casper) has been proposed as a finality gadget for the future Proof-of-Stake (PoS) based Ethereum blockchain. Unfortunately, no...

We propose a new nonce-misuse-resistant authenticated encryption scheme, which instantiates the SIV paradigm of Rogaway and Shrimpton. In contrast to the GCM-SIV approach proposed by Gueron and Lindell, we do only use a single type of cryptographic primitive, which can be advantageous in restricted embedded devices. Furthermore, we use three independent and fixed subkeys derived from a single master key. Similar to the CCM mode, our scheme uses a combination of the CTR mode for the symmetric...

Authenticated encryption (AE) has been a vital operation in cryptography due to its ability to provide confidentiality, integrity, and authenticity at the same time. Its use has soared in parallel with widespread use of the Internet and has led to several new schemes. There have been studies investigating software performance of various schemes. However, the same is yet to be done for hardware. We present a comprehensive survey of hardware (specifically ASIC) performance of the most commonly...

Decentralised ledgers are a prime application case for consensus protocols. Changing sets of validators have to agree on a set of transactions in an asynchronous network and in the presence of Byzantine behaviour. Major research efforts focus on creating consensus protocols under such conditions, with proof-of-stake (PoS) representing a promising candidate. PoS aims to reduce the waste of energy inherent to proof-of-work (PoW) consensus protocols. However, a significant challenge is to get...

The need for high-quality randomness in cryptography makes random-number generation one of its most fundamental tasks. A recent important line of work (initiated by Dodis et al., CCS ’13) focuses on the notion of *robustness* for *pseudorandom number generators (PRNGs) with inputs*—these are primitives that use various sources to accumulate sufficient entropy into a state, from which pseudorandom bits are extracted. Robustness ensures that PRNGs remain secure even under state compromise and...

In this work we show that the sponge construction can be used to construct quantum-secure pseudorandom functions. As our main result we prove that random sponges are quantum indistinguishable from random functions. In this setting the adversary is given superposition access to the input-output behavior of the construction but not to the internal function. Our proofs hold under the assumption that the internal function is a random function or permutation. We then use this result to obtain a...

We present hash functions that are almost optimally one-way in the quantum setting. Our hash functions are based on the Merkle-Damgård construction iterating a Davies-Meyer compression function, which is built from a block cipher. The quantum setting that we use is a natural extention of the classical ideal cipher model. Recent work has revealed that symmetric-key schemes using a block cipher or a public permutation, such as CBC-MAC or the Even-Mansour cipher, can get completely broken with...

This article presents universal forgery and multiple forgeries against MergeMAC that has been recently proposed to fit scenarios where bandwidth is limited and where strict time constraints apply. MergeMAC divides an input message into two parts, $m\|\tilde{m}$, and its tag is computed by $\mathcal{F}( \mathcal{P}_1(m) \oplus \mathcal{P}_2(\tilde{m}) )$, where $\mathcal{P}_1$ and $\mathcal{P}_2$ are PRFs and $\mathcal{F}$ is a public function. The tag size is 64 bits. The designers claim...

Today, about 10% of TLS connections are still using CBC-mode cipher suites, despite a long history of attacks and the availability of better options (e.g. AES-GCM). In this work, we present three new types of attack against four popular fully patched implementations of TLS (Amazon's s2n, GnuTLS, mbed TLS and wolfSSL) which elected to use ``pseudo constant time'' countermeasures against the Lucky 13 attack on CBC-mode. Our attacks combine several variants of the PRIME+PROBE cache timing...

ISO/IEC 9797-1 is an international standard for block-cipher-based Message Authentication Code (MAC). The current version ISO/IEC 9797-1:2011 specifies six single-pass CBC-like MAC structures that are capped at the birthday bound security. For a higher security that is beyond-birthday bound, it recommends to use the concatenation combiner of two single-pass MACs. In this paper, we reveal the invalidity of the suggestion, by presenting a birthday bound forgery attack on the concatenation...

The counter mode (CTR) is a simple, efficient and widely used encryption mode using a block cipher. It comes with a security proof that guarantees no attacks up to the birthday bound (i.e. as long as the number of encrypted blocks $\sigma$ satisfies $\sigma \ll 2^{n/2}$), and a matching attack that can distinguish plaintext/ciphertext pairs from random using about $2^{n/2}$ blocks of data. The main goal of this paper is to study attacks against the counter mode beyond this simple...

Given the value of imported counterfeit and pirated goods, the need for secure supply chain management is pertinent. Maleki et al. (HOST 2017) propose a new management scheme based on RFID tags (with 2-3K bits NVM) which, if compared to other schemes, is competitive on several performance and security metrics. Its main idea is to have each RFID tag stores its reader events in its own NVM while moving through the supply chain. In order to bind a tag's identity to each event such that an...

Bit permutations are a common choice for diffusion function in lightweight block ciphers, owing to their low implementation footprint. In this paper, we present a novel Side-Channel Assisted Differential-Plaintext Attack (SCADPA), exploiting specific vulnerabilities of bit permutations. SCADPA is a chosen-plaintext attack, knowledge of the ciphertext is not required. Unlike statistical methods, commonly used for distinguisher in standard power analysis, the proposed method is more...

At CRYPTO 2015, Minaud and Seurin introduced and studied the iterated random permutation problem, which is to distinguish the $r$-th iterate of a random permutation from a random permutation. In this paper, we study the closely related iterated random function problem, and prove the first almost-tight bound in the adaptive setting. More specifically, we prove that the advantage to distinguish the $r$-th iterate of a random function from a random function using $q$ queries is bounded by...

Security features of modern (SoC) FPAGs permit to protect the confidentiality of hard- and software IP when the devices are powered off as well as to validate the authenticity of IP when being loaded at startup. However, these approaches are insufficient since attackers with physical access can also perform attacks during runtime, demanding for additional security measures. In particular, RAM used by modern (SoC) FPGAs is under threat since RAM stores software IP as well as all kinds of...

An universal forgery attack means that for any given message $M$, an adversary without the key can forge the corresponding Message Authentication Code (MAC) tag $\tau$, and the pair $(M,\tau)$ can be verified with probability 1. For a idea MAC, the universal forgery attack should be infeasible to be implemented, whose complexity is believed to be min{$(2^n, 2^k)$} queries in the classic setting, where $n$ is the tag length and $k$ is the key length of the MAC, respectively. In this paper,...

We prove the security of NMAC, HMAC, AMAC, and the cascade construction with fixed input-length as quantum-secure pseudo-random functions (PRFs). Namely, they are indistinguishable from a random oracle against any polynomial-time quantum adversary that can make quantum superposition queries. In contrast, many blockcipher-based PRFs including CBC-MAC were recently broken by quantum superposition attacks. Classical proof strategies for these constructions do not generalize to the quantum...

Traditionally, modes of Message Authentication Codes(MAC) such as Cipher Block Chaining (CBC) are instantiated using block ciphers or keyed Pseudo Random Permutations(PRP). However, one can also use domain preserving keyed Pseudo Random Functions(PRF) to instantiate MAC modes. The very first security proof of CBC-MAC, essentially modeled the PRP as a PRF. Until now very little work has been done to investigate the difference between PRP vs PRF instantiations. Only known result is the rather...

Recent results of Kaplan et al., building on previous work by Kuwakado and Morii, have shown that a wide variety of classically-secure symmetric-key cryptosystems are completely broken when exposed to quantum CPA attacks. In such an attack, the quantum adversary has the ability to query the cryptographic functionality in superposition. The vulnerable cryptosystems include the Even-Mansour block cipher, the three-round Feistel network, the Encrypted-CBC-MAC, and many others. In this work, we...

The implementation of the AES encryption core by Moradi et al. at Eurocrypt 2011 is one of the smallest in terms of gate area. The circuit takes around 2400 gates and operates on an 8 bit datapath. However this is an encryption only core and unable to cater to block cipher modes like CBC and ELmD that require access to both the AES encryption and decryption modules. In this paper we look to investigate whether the basic circuit of Moradi et al. can be tweaked to provide dual functionality of...

The confidentiality notion of security against selective opening attacks considers adver- saries that obtain challenge ciphertexts and are allowed to adaptively open them, thereby revealing the encrypted message and the randomness used to encrypt. The SO notion is stronger than that of CCA security and is often required when formally arguing towards the security of multi-user applications. While different ways of achieving correspondingly secure schemes are known, as they generally employ...

While modern block ciphers, such as AES, have a block size of at least 128 bits, there are many 64-bit block ciphers, such as 3DES and Blowfish, that are still widely supported in Internet security protocols such as TLS, SSH, and IPsec. When used in CBC mode, these ciphers are known to be susceptible to collision attacks when they are used to encrypt around $2^{32}$ blocks of data (the so-called birthday bound). This threat has traditionally been dismissed as impractical since it requires...

In this paper we introduce a new type of attack, called nonlinear invariant attack. As application examples, we present new attacks that are able to distinguish the full versions of the (tweakable) block ciphers Scream, iScream and Midori64 in a weak-key setting. Those attacks require only a handful of plaintext-ciphertext pairs and have minimal computational costs. Moreover, the nonlinear invariant attack on the underlying (tweakable) block cipher can be extended to a ciphertext-only attack...

This paper proposes a highly efficient AES hardware architecture that supports both encryption and decryption for the CBC mode. Some conventional AES architectures employ pipelining techniques to enhance the throughput and efficiency. However, such pipelined architectures are frequently unfit because many practical cryptographic applications work in the CBC mode, where block-wise parallelism is not available for encryption. In this paper, we present an efficient AES encryption/decryption...

We examine the IND-qCPA security of the wide-spread block cipher modes of operation CBC, CFB, OFB, CTR, and XTS (i.e., security against quantum adversaries doing queries in superposition). We show that OFB and CTR are secure assuming that the underlying block cipher is a standard secure PRF (a pseudorandom function secure under classical queries). We give counterexamples that show that CBC, CFB, and XTS are not secure under the same assumption. And we give proofs that CBC and CFB mode are...

In Crypto'05, Bellare et al. proved an $O(\ell q^2 /2^n)$ bound for the PRF (pseudorandom function) security of the CBC-MAC based on an $n$-bit random permutation $\Pi$, provided $\ell < 2^{n/3}$. Here an adversary can make at most $q$ prefix-free queries each having at most $\ell$ many ``blocks'' (elements of $\{0,1\}^n$). In the same paper an $O(\ell^{o(1)} q^2 /2^n)$ bound for EMAC (or encrypted CBC-MAC) was proved, provided $\ell < 2^{n/4}$. Both proofs are based on {\bf structure...

AES-NI, or Advanced Encryption Standard New Instructions, is an extension of the x86 architecture proposed by Intel in 2008. With a pipelined implementation utilizing AES-NI, parallelizable modes such as AES-CTR become extremely efficient. However, out of the four non-trivial NIST-recommended encryption modes, three are inherently sequential: CBC, CFB, and OFB. This inhibits the advantage of using AES-NI significantly. Similar observations apply to CMAC, CCM and a great deal of other modes....

We provide further evidence that implementing software countermeasures against timing attacks is a non-trivial task and requires domain-specific software development processes: we report an implementation bug in the S2N library, recently released by AWS Labs. This bug (now fixed) allowed bypassing the balancing countermeasures against timing attacks deployed in the implementation of the MAC-then-Encode-then-CBC-Encrypt (MEE-CBC) component, creating a timing side-channel similar to that...

s2n is an implementation of the TLS protocol that was released in late June 2015 by Amazon. It is implemented in around 6,000 lines of C99 code. By comparison, OpenSSL needs around 70,000 lines of code to implement the protocol. At the time of its release, Amazon announced that s2n had undergone three external security evaluations and penetration tests. We show that, despite this, s2n - as initially released - was vulnerable to a timing attack in the case of CBC-mode ciphersuites, which...

MACs (Message Authentication Codes) are widely adopted in communication systems to ensure data integrity and data origin authentication, e.g. CBC-MACs in the ISO standard 9797-1. However, all the current designs based on block cipher either suffer from birthday attacks or require long key sizes. In this paper, we focus on designing {\em single keyed block cipher based MAC achieving beyond-birthday-bound (BBB) security (in terms of number of queries) in the standard model}. Here, we develop...

Conventional Cipher Feedback Mode (CFB) can allow the transmission unit to be shorter than the block-cipher length. Eventually, it causes no delay and even any message expansion unlike the ECB and CBC mode of operation where encryption cannot begin unless and until a complete block of full-length (say 64 bits) plain-text data is available. However, because of stalling during the block encryption, CFB cannot provide low latency, low jitter; these are two imperative properties in the sense of...

In CT-RSA 2010, Kan Yasuda has shown that the sum of two independent Encrypted CBC (ECBC) MACs is a secure PRF with security beyond birthday bound. It was mentioned in the abstract of the paper that ``no proof of security above the birthday bound $(2^{n/2})$ has been known for the sum of CBC MACs" (where $n$ is the tag size in bits). Kan Yasuda's paper did not consider the sum of actual CBC outputs and hence the PRF-security of the same has been left open. In this paper, we solve this...

We prove (nearly) tight bounds on the concrete PRF-security of two constructions of message-authentication codes (MACs): (1) The truncated CBC-MAC construction, which operates as plain CBC-MAC (without prefix-free encoding of messages), but only returns a subset of the output bits. (2) The MAC derived from the sponge hash-function family by pre-pending a key to the message, which is the de-facto standard method for SHA-3-based message authentication. The tight analysis of keyed sponges is...

In many applications, encryption alone does not provide enough security. To enhance security, dedicated authenticated encryption (AE) mode are invented. Galios Counter Mode (GCM) and Counter with CBC-MAC mode (CCM) are the AE modes recommended by the National Institute of Standards and Technology. To support high data rates, AE modes are usually implemented in hardware. However, natural faults reduce its reliability and may undermine both its encryption and authentication capability. We...

Side Channel Attacks (SCA) using power measurements are a known method of breaking cryptographic algorithms such as AES. Published research into attacks on AES frequently target only AES-128, and often target only the core Electronic Code-Book (ECB) algorithm, without discussing surrounding issues such as triggering, along with breaking the initialization vector. This paper demonstrates a complete attack on a secure bootloader, where the firmware files have been encrypted with AES-256-CBC....

NMAC is a mode of operation which turns a fixed input-length keyed hash function f into a variable input-length function. A~practical single-key variant of NMAC called HMAC is a very popular and widely deployed message authentication code (MAC). Security proofs and attacks for NMAC can typically be lifted to HMAC. NMAC was introduced by Bellare, Canetti and Krawczyk [Crypto'96], who proved it to be a secure pseudorandom function (PRF), and thus also a MAC, assuming that (1) f is a PRF...

The notion of indifferentiability, which is a stronger version of the classic notion of indistinguishability, was introduced by Maurer, Renner, and Holenstein in 2003. Indifferentiability, among other things, gives us a way of ``securely replacing" a random oracle of one type by a random oracle of a different type. Most indifferentiability proofs in the literature are very complicated, which makes them difficult to verify and in some cases, has even resulted in them being erroneous. In this...

Authenticated encryption (AE) has recently gained renewed interest due to the ongoing CAESAR competition. This paper deals with the performance of block cipher modes of operation for AE in parallel software. We consider the example of the AES on Intel's new Haswell microarchitecture that has improved instructions for AES and finite field multiplication. As opposed to most previous high-performance software implementations of operation modes -- that have considered the encryption of single...

ANSI X9.24-1:2009 specifies the key check value, which is used to verify the integrity of the blockcipher key. This value is defined as the most significant bits of the ciphertext of the zero block, and is assumed to be publicly known data for verification. ISO/IEC 9797-1:2011 illustrates a total of ten CBC MACs, where one of these MACs, the basic CBC MAC, is widely known to be insecure. In this paper, we consider the remaining nine CBC MACs and derive the quantitative security impact of...

We define and analyze the security of a blockcipher mode of operation, CLOC, for provably secure authenticated encryption with associated data. The design of CLOC aims at optimizing previous schemes, CCM, EAX, and EAX-prime, in terms of the implementation overhead beyond the blockcipher, the precomputation complexity, and the memory requirement. With these features, CLOC is suitable for handling short input data, say 16 bytes, without needing precomputation nor large memory. This property is...

While standard message authentication codes (MACs) guarantee authenticity of messages, they do not, in general, guarantee the anonymity of the sender and recipient. For example it may be easy for an observer to determine whether or not two authenticated messages were sent by the same party even without any information about the secret key used. However preserving any uncertainty an attacker may have about the identities of honest parties engaged in authenticated communication is an important...

Message authentication codes (MACs) are an essential primitive in cryptography. They are used to ensure the integrity and authenticity of a message, and can also be used as a building block for larger schemes, such as chosen-ciphertext secure encryption, or identity-based encryption. MACs are often built in two steps: first, the `front end' of the MAC produces a short digest of the long message, then the `back end' provides a mixing step to make the output of the MAC unpredictable for an...

In some wireless environments, minimizing the size of messages is paramount due to the resulting significant energy savings. We present CMCC, an authenticated encryption scheme with associated data (AEAD) that is also nonce misuse resistant. The main focus for this work is minimizing ciphertext expansion, especially for short messages including plaintext lengths less than the underlying block cipher length (e.g., 16 bytes). For many existing AEAD schemes, a successful forgery leads directly...

To against some known attacks to Secure Shell (SSH), I propose some fixes to SSH. The fixes include add a key producer function and revise the MAC.

The block cipher modes of operation that are widely used (CBC, CTR, CFB) are secure up to the birthday bound; that is, if $w2^{w}$ or fewer bits of data are encrypted with a $w$-bit block cipher. However, the detailed security properties close to this bound are not widely appreciated, despite the fact that $64$-bit block ciphers are sometimes used in that domain. This work addresses the issue by analyzing plaintext-recovery attacks that are effective close to that bound. We describe...

We present a new mode of operation for obtaining authenticated encryption suited for use in banking and government environments where cryptographic services are only available via a Hardware Security Module (HSM) which protects the keys but offers a limited API. The practical problem is that despite the existence of better modes of operation, modern HSMs still provide nothing but a basic (unauthenticated) CBC mode of encryption, and since they mediate all access to the key, solutions must...

Liskov, Rivest and Wagner formalized the tweakable blockcipher (TBC) primitive at CRYPTO'02. The typical recipe for instantiating a TBC is to start with a blockcipher, and then build up a construction that admits a tweak. Almost all such constructions enjoy provable security only to the birthday bound, and the one that does achieve security beyond the birthday bound (due to Minematsu) severely restricts the tweak size and requires per-invocation blockcipher rekeying. This paper gives the...

We present the notion of PROG-KDM security for public-key encryption schemes. This security notion captures both KDM security and revealing of secret keys (key corruptions) in a single definition. This is achieved by requiring the existence of a simulator that can program ciphertexts when a secret key is revealed, i.e., the simulator can delay the decision what plaintext is contained in what ciphertext to the moment where the ciphertext is opened. The definition is formulated in the random...

We show how to exploit the encrypted key import functions of a variety of different cryptographic devices to reveal the imported key. The attacks are padding oracle attacks, where error messages resulting from incorrectly padded plaintexts are used as a side channel. In the asymmetric encryption case, we modify and improve Bleichenbacher's attack on RSA PKCS#1v1.5 padding, giving new cryptanalysis that allows us to carry out the `million message attack' in a mean of 49 000 and median of 14...

Both certificateless cryptography (CLC) and certificate-based cryptography (CBC) are two novel public key paradigms which combine the merits of traditional public key cryptography (PKC) and identity-based cryptography (IBC). They succeed in avoiding the key escrow problem in IBC and reducing the public key management overhead in traditional PKC. This paper deals with the generic construction of certificate based signature (CBS) from certificateless signature (CLS). Wu et...

Symbolic encryption, in the style of Dolev-Yao models, is ubiquitous in formal security analysis aiming at the automated verification of network protocols. The naive use of symbolic encryption, however, may unnecessarily require an expensive construction: an arbitrary-length encryption scheme that is private and non-malleable in an adaptive CCA-CPA setting. Most of the time, such assumptions remain hidden and rather symbolic encryption is instantiated with a seemingly ``good'' cryptographic...

TLS is the most important cryptographic protocol in use today. However, up to now there is no complete cryptographic security proof in the standard model, nor in any other model. We give the first such proof for the core cryptographic protocol of TLS ciphersuites based on ephemeral Diffie-Hellman key exchange (TLS-DHE), which include the cipher suite TLS DHE DSS WITH 3DES EDE CBC SHA mandatory in TLS 1.0 and TLS 1.1. It is impossible to prove security of the TLS Handshake in any classical...

The ALRED family of Message Authentication Codes (MAC's) is based on three principles: Using a keyless block cipher in CBC mode to process the message, choosing AES-128 as this cipher, and reducing the effective number of rounds to 4 in order to speed up the processing. In this paper we show that each one of these principles creates significant weaknesses. More specifically, we show that any ALRED-type MAC which uses a keyless block cipher is vulnerable to new time/memory tradeoff...

We suggest a new framework for block ciphers named Advanced Block Cipher, or shortly ABC. ABC has additional non-secret parameters that ensure that each call to the underlying block cipher uses a different pseudo-random permutation. It therefore ensures that attacks that require more than one block encrypted under the same secret permutation cannot apply. In particular, this framework protects against dictionary attacks, and differential and linear attacks, and eliminates weaknesses of ECB...

This paper investigates compression of data encrypted with block ciphers, such as the Advanced Encryption Standard (AES). It is shown that such data can be feasibly compressed without knowledge of the secret key. Block ciphers operating in various chaining modes are considered and it is shown how compression can be achieved without compromising security of the encryption scheme. Further, it is shown that there exists a fundamental limitation to the practical compressibility of block ciphers...

This paper provides a unified framework for {\em improving} \PRF(pseudorandom function) advantages of several popular MACs (message authentication codes) based on a blockcipher modeled as \tx{RP} (random permutation). In many known MACs, the inputs of the underlying blockcipher are defined to be some deterministic affine functions of previously computed outputs of the blockcipher. Keeping the similarity in mind, we introduce a class of \tx{ADE}s (affine domain extensions) and a wide...

We consider the construction and analysis of pseudorandom functions (PRF) for message authentication. Earlier work due to Bernstein and Vaudenay show how to reduce the analysis of PRFs to some probability calculations. We revisit this result and use it to prove some general results on constructions which use a PRF with ``small'' domain to build a PRF with ``large'' domain. These results are then used to analyse several existing and new constructions. Important among them is a...

In this paper, we first present a new distinguisher on the CBC-MAC based on a block cipher in Cipher Block Chaining (CBC) mode. It can also be used to distinguish other CBC-like MACs from random functions. The main results of this paper are on the second-preimage attack on CBC-MAC and CBC-like MACs include TMAC, OMAC, CMAC, PC-MAC and MACs based on three-key encipher CBC mode. Instead of exhaustive search, this attack can be performed with the birthday attack complexity.

In this paper, we present new distinguishers of the MAC construction \textsc{Alred} and its specific instance \textsc{Alpha}-MAC based on AES, which is proposed by Daemen and Rijmen in 2005. For the \textsc{Alred} construction, we describe a general distinguishing attack which leads to a forgery attack directly. The complexity is $2^{64.5}$ chosen messages and $2^{64.5}$ queries with success probability 0.63. We also use a two-round collision differential path for \textsc{Alpha}-MAC, to...

Online ciphers are those ciphers whose ciphertexts can be computed in real time by using a length-preserving encryption algorithm. HCBC1 and HCBC2 are two known examples of Hash Cipher Block Chaining online ciphers. The first construction is secure against chosen plaintext adversary (or called CPA-secure) whereas the latter is secure against chosen ciphertext adversary (or called CCA-secure). In this paper, we have provided simple security analysis of these online ciphers. We have also...

In this paper, we present some new applications of the bounds for the differential probability of a SDS (Substitution-Diffusion-Substitution) structure by Park et al. at FSE 2003. Park et al. have applied their result on the AES cipher which uses the SDS structure based on MDS matrices. We shall apply their result to practical ciphers that use SDS structures based on {0,1}-matrices of size n times n. These structures are useful because they can be efficiently implemented in hardware. We...

We study the standard block cipher modes of operation: CBC, CFB, and OFB and analyse their security. We don't look at ECB other than briefly to note its insecurity, and we have no new results on counter mode. Our results improve over those previously published in that (a) our bounds are better, (b) our proofs are shorter and easier, (c) the proofs correct errors we discovered in previous work, or some combination of these. We provide a new security notion for symmetric encryption which...

The security of interchanged use of modes of operation of block ciphers have not been discussed in the public literature. So far, the modes of operation of block ciphers have been treated as completely independent and uncorrelated. In this paper we represent both CBC and OFB as quasigroup string transformations, and then show that OFB mode is a special case of the CBC mode of operation. That raise possibilities for construction of several devastating attack scenarios against that...

We present an improved security analysis of OMAC, the construction is widely used as a candidate of MAC or Pseudo Random Function (or PRF). In this direction, the first result was given in Crypto-05 where an improved security analysis of CBC (for fixed length or for arbitrary length prefix-free messages) had provided. Followed by this work, improved bounds for XCBC, TMAC and PMAC were found. The improved bounds are of the form $\mathrm{O}(\frac{Lq^2}{2^n})$ where the original bounds are...

We initiate a study of on-line ciphers. These are ciphers that can take input plaintexts of large and varying lengths and will output the i-th block of the ciphertext after having processed only the first i blocks of the plaintext. Such ciphers permit length-preserving encryption of a data stream with only a single pass through the data. We provide security definitions for this primitive and study its basic properties. We then provide attacks on some possible candidates, including CBC with...

In Crypto 2001, Bellare {\em et al.} introduced {\em online cipher} (or online permutation) and proposed two Hash-CBC mode constructions, namely {\bf HCBC} and {\bf HPCBC} along with security proofs. We observe that, the security proofs in their paper are {\em wrong} and it may not be fixed easily. In this paper, we provide a {\em simple} security analysis of these online ciphers. Moreover, we propose two variants of HPCBC, namely {\bf MHCBC-1} and {\bf MHCBC-2}. The first variant,...

In this paper we compute the collision probability of CBC-MAC for suitably chosen messages. We show that the probability is $\Omega(\ell q^2/N)$ where $\ell$ is the number of message block, $N$ is the size of the domain and $q$ is the total number of queries. For random oracle the probability is $O(q^2/N)$. This improved collision probability will help us to have an efficient distinguishing attack and MAC-forgery attack. We also show collision probability for PMAC with collision...

Blockwise-adaptive chosen-plaintext and chosen-ciphertext attack are new models for cryptanalytic adversaries, first discovered by Joux, et al [JMV02], and describe a vulnerability in SSH discovered by Bellare, et al [BKN02]. Unlike traditional chosen-plaintext (CPA) or chosen-ciphertext (CCA) adversaries, the blockwise adversary can submit individual blocks for encryption or decryption rather than entire messages. This paper focuses on the search for on-line encryption schemes which are...

Recently Bernstein has provided a simpler proof of unpredictability of CBC construction which is giving insight of the construction. Unpredictability of any function intuitively means that the function behaves very closely to a uniform random function. In this paper we make a unifying and simple approach to prove unpredictability of many existing constructions. We first revisit Bernstein's proof. Using this idea we can show a simpler proof of unpredictability of a class of DAG based...

This paper introduces a chosen-plaintext vulnerability in the Secure Sockets Layer (SSL) and Trasport Layer Security (TLS) protocols which enables recovery of low entropy strings such as can be guessed from a likely set of 2--1000 options. SSL and TLS are widely used for securing communication over the Internet. When utilizing block ciphers for encryption, the SSL and TLS standards mandate the use of the cipher block chaining (CBC) mode of encryption which requires an initialization vector...

We construct a reasonably efficient threshold and proactive pseudo-random permutation (PRP). Our protocol needs only O(1) communication rounds. It tolerates up to (n-1)/2 of n dishonest servers in the semi-honest environment. Many protocols that use PRPs (e.g., a CBC block cipher mode) can now be translated into the distributed setting. Our main technique for constructing invertible threshold PRPs is a distributed Luby-Rackoff construction where both the secret keys *and* the input are...

Some message authentication codes (MACs) are vulnerable to multiple forgery attacks, in which an attacker can gain information that allows her to succeed in forging multiple message/tag pairs. This property was first noted in MACs based on universal hashing, such as the Galois/Counter Mode (GCM) of operation for block ciphers. However, we show that CBC-MAC and HMAC also have this property, and for some parameters are more vulnerable than GCM. We present multiple-forgery attacks against...

We prove a general domain extension theorem for pseudo-random functions (PRFs). Given a PRF $F$ from $n$ bits to $n$ bits, it is well known that employing $F$ in a chaining mode (CBC-MAC) yields a PRF on the bigger domain. Viewing each application of $F$ in this chaining mode to be a node in a graph, and the chaining as the edges between the nodes, the resulting graph is just a line graph. In this paper, we show that the underlying graph can be an arbitrary directed acyclic graph (DAG),...

We present an update of the Pelican MAC function, called Pelican 2.0. Both versions have the Alred construction and are based on Rijndael. they are a factor 2.5 more efficient than CBC-MAC with Rijndael, while providing a comparable claimed security level. The difference between Pelican 2.0 and the original version is that the initial value changes from the all-zero string to another constant. The reason for this is the negative impact on security if key check values are available computed...

The game-playing technique is a powerful tool for analyzing cryptographic constructions. We illustrate this by using games as the central tool for proving security of three-key triple-encryption, a long-standing open problem. Our result, which is in the ideal-cipher model, demonstrates that for DES parameters (56-bit keys and 64-bit plaintexts) an adversary's maximal advantage is small until it asks about $2^{78}$ queries. Beyond this application, we develop the foundations for game playing,...

We revisit the randomized approach followed in the design of the RMAC message authentication code in order to construct a MAC with similar properties, but based on Wegman-Carter's $\varepsilon$-universal hash families instead of a classical CBC chain. This yields a new message authentication code called FRMAC whose security bounds are, as in RMAC, beyond the birthday paradox limit. With efficient hash functions in software, the performance of FRMAC for large messages is similar to those of...

The Secure Sockets Layer (SSL) protocol is widely used for securing communication over the Internet. When utilizing block ciphers for encryption, the SSL standard mandates the use of the cipher block chaining (CBC) mode of encryption which requires an initialization vector (IV) in order to encrypt. Although the initial IV used by SSL is a (pseudo)random string which is generated and shared during the initial handshake phase, subsequent IVs used by SSL are chosen in a deterministic,...

We describe a new method for authenticated encryption, which uses information from the internal state of the cipher to provide the authentication. This methodology has a number of benefits. The encryption has properties similar to CBC mode, yet the encipherment and authentication mechanisms can be parallelized and/or pipelined. The authentication overhead is minimal, so the computational cost of the authenticated encryption is very nearly that of the encryption process. Also, the...