Cryptanalysis of Triple Modes of Operation

Multiple modes of operation and, in particular, triple modes of operation were proposed as a simple method to improve the strength of blockciphers, and in particular of DES. Developments in the cryptanalysis of DES in recent years have popularized the triple modes of DES, and such modes are now considered for ANSI standards. In a previous paper we analyzed multiple modes of operation and showed that the security of many multiple modes is significantly smaller than expected. In this paper we extend these results, with new cryptanalytic techniques, and show that all the (cascaded) triple modes of operation are not much more secure than a single encryption—in the case of DES they can be attacked with up to an order of 2 ⁵⁶ —2 ⁶⁶ chosen plaintexts or ciphertexts and complexity of analysis. We then propose several candidates for more secure modes. Received 19 August 1996 and revised 29 September 1997     

Cryptanalysis of the ANSI X9.52 CBCM mode

In this paper we cryptanalyze the CBCM mode of operation, which was almost included in the ANSI X9.52 Triple-DES Modes of Operation standard. The CBCM mode is a Triple-DES CBC variant which was designed against powerful attacks which control intermediate feedback for the benefit of the attacker. For this purpose, it uses intermediate feedbacks that the attacker cannot control, choosing them as a keyed OFB stream, independent of the plaintexts and the ciphertexts. In this paper we find a way to use even this kind of feedback for the benefit of the attacker, and we present an attack which requires a single chosen ciphertext of 2 ⁶⁵ blocks which needs to be stored and 2 ⁵⁹ complexity of analysis (CBCM encryptions) to find the key with a high probability. As a consequence of our attack, ANSI decided to remove the CBCM mode from the proposed standard. Received May 1998 and revised June 2001 Online publication 28 November 2001     

Two-Key Triple Encryption

In this paper we consider multiple encryption schemes built from conventional cryptosystems such as DES. The existing schemes are either vulnerable to variants of meet-in-the-middle attacks, i.e., they do not provide security corresponding to the full key length used or there is no proof that the schemes are as secure as the underlying cipher. We propose a variant of two-key triple encryption with a new method of generating three keys from two. Our scheme is not vulnerable to the meet-in-the-middle attack and, under an appropriate assumption, we can show that our scheme is at least about as hard to break as the underlying block cipher. Received 22 June 1995 and revised 11 October 1996     

Differential cryptanalysis of Lucifer

Differential cryptanalysis was introduced as an approach to analyze the security of DES-like cryptosystems. The first example of a DES-like cryptosystem was Lucifer, the direct predecessor of DES, which is still believed by many people to be much more secure than DES, since it has 128 key bits, and since no attacks against (the full variant of) Lucifer were ever reported in the cryptographic literature. In this paper we introduce a new extension of differential cryptanalysis, devised to extend the class of vulnerable cryptosystems. This new extension suggests key-dependent characteristics, calledconditional characteristics, selected to increase the characteristics' probabilities for keys in subsets of the key space. The application of conditional characteristics to Lucifer shows that more than half of the keys of Lucifer are insecure, and the attack requires about 2³⁶ complexity and chosen plaintexts to find these keys. The same extension can also be used to attack a new variant of DES, called RDES, which was designed to be immune against differential cryptanalysis. These new attacks flash new light on the design of DES, and show that the transition of Lucifer to DES strengthened the later cryptosystem.     

Partial Key Recovery Attack Against RMAC

In this paper new “partial” key recovery attacks against the RMAC block cipher based Message Authentication Code scheme are described. That is we describe attacks that, in some cases, recover one of the two RMAC keys much more efficiently than previously described attacks. Although all attacks, but one, are of no major threat in practice, in some cases there is reason for concern. In particular, the recovery of the second RMAC key (of k bits) may only require around 2^k/2 block cipher operations (encryptions or decryptions). The RMAC implementation using triple DES proposed by NIST is shown to be very weak.     

Known-IV, Known-in-Advance-IV, and Replayed-and-Known-IV Attacks on Multiple Modes of Operation of Block Ciphers

Normally, it has been believed that the initial values of cryptographic schemes do not need to be managed secretly unlike the secret keys. However, we show that multiple modes of operation of block ciphers can suffer a loss of security by the state of the initial values. We consider several attacks according to the environment of the initial values; known-IV attack, known-in-advance-IV attack, and replayed-and-known-IV attack. Our attacks on cascaded three-key triple modes of operation requires 3-7 blocks of plaintexts (or ciphertexts) and 3 · 2⁵⁶-9 · 2⁵⁶ encryptions. We also give the attacks on multiple modes proposed by Biham.     

Attacks on Fast Double Block Length Hash Functions

The security of hash functions based on a block cipher with a block length of m bits and a key length of k bits, where , is considered. New attacks are presented on a large class of iterated hash functions with a 2m -bit hash result which processes in each iteration two message blocks using two encryptions. In particular, the attacks break three proposed schemes: Parallel-DM, the PBGV hash function, and the LOKI DBH mode. Received 1 March 1996 and revised 16 December 1996     

一种轻量级数据加密标准循环掩码实现方案

随着智能卡技术的不断发展,智能卡芯片的安全性也面临越来越大的挑战。在众多加密算法中,数据加密标准(DES)算法是一种应用较广的对称加解密算法。为了抵御各种侧信道攻击,使用最为广泛的是在算法中通过掩码技术来消除真实密钥和功耗相关性,该文提出一种新的适用于DES的循环掩码方案,和之前文献中的预计算掩码方案相比,不仅预计算量大大减少,而且整个DES运算过程的中间数据都是带有掩码的,把掩码拆分后,还可以防护高阶攻击。     

Secure Hardware Implementation of Nonlinear Functions in the Presence of Glitches

Hardware implementations of cryptographic algorithms are vulnerable to side-channel attacks. Side-channel attacks that are based on multiple measurements of the same operation can be countered by employing masking techniques. Many protection measures depart from an idealized hardware model that is very expensive to meet with real hardware. In particular, the presence of glitches causes many masking techniques to leak information during the computation of nonlinear functions. We discuss a recently introduced masking method which is based on secret sharing and multi-party computation methods. The approach results in implementations that are provably resistant against a wide range of attacks, while making only minimal assumptions on the hardware. We show how to use this method to derive secure implementations of some nonlinear building blocks for cryptographic algorithms. Finally, we provide a provable secure implementation of the block cipher Noekeon and verify the results by means of low-level simulations.     

On the Security of a Practical Identification Scheme

We analyze the security of an interactive identification scheme. The scheme is the obvious extension of the original square root scheme of Goldwasser, Micali, and Rackoff to 2 ^m th roots. This scheme is quite practical, especially in terms of storage and communication complexity. Although this scheme is certainly not new, its security was apparently not fully understood. We prove that this scheme is secure if factoring integers is hard, even against active attacks where the adversary is first allowed to pose as a verifier before attempting impersonation. Received 29 July 1996 and revised 30 June 1998     

CBC MAC for Real-Time Data Sources

The Cipher Block Chaining (CBC) Message Authentication Code (MAC) is an authentication method which is widely used in practice. It is well known that the use of the CBC MAC for variable length messages is not secure, and a few rules of thumb for the correct use of the CBC MAC are known by folklore. The first rigorous proof of the security of CBC MAC, when used on fixed length messages, was given only recently by Bellare et al.[3]. They also suggested variants of CBC MAC that handle variable-length messages but in these variants the length of the message has to be known in advance (i.e., before the message is processed). We study CBC authentication of real-time applications in which the length of the message is not known until the message ends, and furthermore, since the application is real-time, it is not possible to start processing the authentication until after the message ends. We first consider a variant of CBC MAC, that we call the encrypted CBC MAC (EMAC), which handles messages of variable unknown lengths. Computing EMAC on a message is virtually as simple and as efficient as computing the standard CBC MAC on the message. We provide a rigorous proof that its security is implied by the security of the underlying block cipher. Next, we argue that the basic CBC MAC is secure when applied to a prefix-free message space. A message space can be made prefix-free by also authenticating the (usually hidden) last character which marks the end of the message. Received 16 September 1997 and revised 24 August 1999 Online publication 2 June 2000     

A robust and efficient dynamic identity‐based multi‐server authentication scheme using smart cards

In single‐server architecture, one service is maintained by one server. If a user wants to employ multiple services from different servers, he/she needs to register with these servers and to memorize numerous pairs of identities and passwords corresponding to each server. In order to improve user convenience, many authentication schemes have been provided for multi‐server environment with the property of single registration. In 2013, Li et al. provided an efficient multi‐server authentication scheme, which they contended that it could resist several attacks. Nevertheless, we find that their scheme is sensitive to the forgery attack and has a design flaw. This paper presents a more secure dynamic identity‐based multi‐server authentication scheme in order to solve the problem in the scheme by Li et al. Analyses show that the proposed scheme can preclude several attacks and support the revocation of anonymity to handle the malicious behavior of a legal user. Furthermore, our proposed scheme has a lower computation and communication costs, which make it is more suitable for practical applications. Copyright © 2014 John Wiley & Sons, Ltd.     

On-line Ciphers and the Hash-CBC Constructions

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 fixed IV. We then provide two constructions, HCBC1 and HCBC2, based on a given block cipher E and a family of computationally AXU functions. HCBC1 is proven secure against chosen-plaintext attacks assuming that E is a PRP secure against chosen-plaintext attacks, while HCBC2 is proven secure against chosen-ciphertext attacks assuming that E is a PRP secure against chosen-ciphertext attacks.     

On the Existence of Secure Keystream Generators

Designers of stream ciphers have generally used ad hoc methods to build systems that are secure against known attacks. There is often a sense that this is the best that can be done, that any system will eventually fall to a practical attack. In this paper we show that there are families of keystream generators that resist all possible attacks of a very general type in which a small number of known bits of a keystream are used to synthesize a generator of the keystream (called a synthesizing algorithm). Such attacks are exemplified by the Berlekamp—Massey attack. We first formalize the notions of a family of finite keystream generators and of a synthesizing algorithm. We then show that for any function h(n) that is in \cal O (2 ^n/d ) for every d>0 , there is a family \cal B of periodic sequences such that any efficient synthesizing algorithm outputs a generator of size h(log (\mathop \rm per \nolimits(B))) given the required number of bits of a sequence B∈ \cal B of large enough period. This result is tight in the sense that it fails for any faster growing function h(n) . We also consider several variations on this scenario. Received July 1996 and revised April 2000 Online publication 27 November, 2000     

基于CPLD／FPGA的AES算法混合流水实现

在加解密算法的硬件实现中,使用流水线结构可以显著地提高加密解密速度,但是由于这类结构并不适合于大多数的反馈模式,因而此类结构在当前密码学中的应用较少。为此,该文采用一种补偿手段,基于交叉CBC(Interleaved Cipher Block Chaining)模式,以混合流水结构成功地实现了AES(Advanced EncryptionStandard)的算法。该方案允许并行处理4个数据块(称为一次加密或解密),同时两次加密或解密之间还可实现部分并行。该方案在EP20k300EBC652-1(Ateral公司产品)上已得到成功验证。     

The Full Cost of Cryptanalytic Attacks

An open question about the asymptotic cost of connecting many processors to a large memory using three dimensions for wiring is answered, and this result is used to find the full cost of several cryptanalytic attacks. In many cases this full cost is higher than the accepted complexity of a given algorithm based on the number of processor steps. The full costs of several cryptanalytic attacks are determined, including Shanks method for computing discrete logarithms in cyclic groups of prime order n, which requires n^1/2+o(1) processor steps, but, when all factors are taken into account, has full cost n^2/3+o(1). Other attacks analyzed are factoring with the number field sieve, generic attacks on block ciphers, attacks on double and triple encryption, and finding hash collisions. In many cases parallel collision search gives a significant asymptotic advantage over well-known generic attacks.     

Attacks on Block Ciphers of Low Algebraic Degree

In this paper an attack on block ciphers is introduced, the interpolation attack. This method is useful for attacking ciphers that use simple algebraic functions (in particular quadratic functions) as S-boxes. Also, attacks based on higher-order differentials are introduced. They are special and important cases of the interpolation attacks. The attacks are applied to several block ciphers, the six-round prototype cipher by Nyberg and Knudsen, which is provably secure against ordinary differential cryptanalysis, a modified version of the block cipher SHARK, and a block cipher suggested by Kiefer. Received April 1999 and revised October 2000 Online publication 9 April 2001     

New types of cryptanalytic attacks using related keys

In this paper we study the influence of key-scheduling algorithms on the strength of blockciphers. We show that the key-scheduling algorithms of many blockciphers inherit obvious relationships between keys, and use these key relations to attack the blockciphers. Two new types of attacks are described: New chosen plaintext reductions of the complexity of exhaustive search attacks (and the faster variants based on complementation properties), and new low-complexity chosen key attacks. These attacks are independent of the number of rounds of the cryptosystems and of the details of the F-function and may have very small complexities. These attacks show that the key-scheduling algorithm should be carefully designed and that its structure should not be too simple. These attacks are applicable to both variants of LOKI and to Lucifer. DES is not vulnerable to the related keys attacks since the shift pattern in the key-scheduling algorithm is not the same in all the rounds.This research was supported by the fund for the promotion of research at the Technion.     

Encryption Modes with Almost Free Message Integrity

We define a new mode of operation for block ciphers which, in addition to providing confidentiality, also ensures message integrity. In contrast, previously for message integrity a separate pass was required to compute a cryptographic message authentication code (MAC). The new mode of operation, called Integrity Aware Parallelizable Mode (IAPM), requires a total of m+1 block cipher evaluations on a plain-text of length m blocks. For comparison, the well-known CBC (cipher block chaining) encryption mode requires m block cipher evaluations, and the second pass of computing the CBC-MAC essentially requires additional m+1 block cipher evaluations. As the name suggests, the new mode is also highly parallelizable.     

Cost-benefit analysis of a system with inspection, replacement and two types of repair

This paper investigates a mathematical model of a system composed of two units—one operative and the other in cold standby. There is a single repair facility which serves the triple role of inspection, repair and replacement of a failed unit. After inspection, the unit goes to minor (major) repair with probability p(q = 1 − p). Whenever the failed unit goes to major repair, an order is immediately placed for a new unit to replace the unit under major repair. Failure, inspection and delivery time distributions are negative exponential, whereas repair time distribution is arbitrary. The system is analysed in detail using the regenerative point technique and several reliability characteristics of interest to system designers and operation managers are obtained. Earlier results are verified in particular cases.