Attacks on Stream Cipher System
Attacks on Stream Cipher
Abstract
This paper focuses on the classification of cipher system, i.e., stream and block cipher . The benefits of stream cipher over block cipher system. The classification of attacks on stream cipher systems and techniques of cryptanalysis and immunity towards those types of attacks.
Keywords: Stream Cipher, Attacks, Cryptology, Cryptanalysis, Classification of Ciphers and Attacks.
Introduction
A specific method to hide the meaning of a message is called a cipher, and the process of transforming the message or plaintext to a coded message, or ciphertext, is known as encryption. The reverse process of transforming the ciphertext back to the original plaintext is known as decryption. A cipher can be seen as a combination of a general cryptographic algorithm and a key that decides the encryption details in the specific case[1]. The key in modern ciphers is often a sequence of bits (zeros and ones). As the general algorithm is often publicly known, the confidentiality of the message depends on the secrecy of the key (Kerckoff’s law).
Cryptanalysis is the science of recovering information without knowledge of the key. The term cryptology is sometimes used for the area of cryptography and cryptanalysis together. Cryptology uses ideas from several other fields such as information theory, computer science, number theory, and abstract algebra.
Classification of Ciphers
Cryptosystems can either be secret key and symmetric (AES, DES, RC4), or public key and asymmetric (ElGamal, McEliece, RSA). In a symmetric system the sender and receiver have agreed on a secret key, that is used for both encryption and decryption. In an asymmetric cryptosystem the sender uses the receiver’s publicly available public key to encrypt, and the receiver can then decrypt with his private key. The idea of public key cryptography was proposed as recently as 1976 by Diffie and Hellman [2]. The first public key cryptosystem was RSA, which was proposed in 1977 by Rivest, Shamir and Adleman [3]. In secret key cryptography a public key cryptosystem is often used to distribute the secret key.
Symmetric cryptosystems is usually divided into stream ciphers and block ciphers. Stream ciphers encrypt individual characters (usually binary digits) of a plaintext one at a time, using an encryption transformation which varies with time. By contrast, block ciphers tend to simultaneously encrypt groups of characters of a plaintext message using a fixed encryption transformation.
Block ciphers operate with a fixed transformation on large blocks of plaintext data; stream ciphers operate with a time-varying transformation on individual plaintext digits. While block ciphers operate on large blocks of data, stream ciphers typically operate on smaller units of plaintext, usually bits. The encryption of any particular plaintext with a block cipher will result in the same ciphertext when the same key is used. With a stream cipher, the transformation of these smaller plaintext units will vary, depending on when they are encountered during the encryption process.
The benefits of Stream Ciphers over Block ciphers are[4]:
- Stream ciphers are generally much faster than block ciphers.
- The keystream can be sometimes be generated prior to encryption/decryption.
- No or limited error propagation
- Low hardware complexity
- Long period with no repetitions
- Statistically random
- Depends on large enough key
- Large linear complexity
- Correlation immunity
- Confusion
- Diffusion
- Use of highly non-linear Boolean functions
Attacks on Stream Ciphers
An Attack is a successful or unsuccessful attempt at breaking part or all of a cryptosystem. The cryptanalysis (Kryptos = “hidden” and analytein = “ to loosen” ) is the study of methods for obtaining the meaning of encrypted information, without access to the secret information which is normally required to do so. Typically, this involves finding the secret key. There are several common types of attacks that an attacker can use to enter a system, such as those that exploit buffer overflows, weak passwords, or even configuration issues. Aside from the common types of attacks and their associated vulnerabilities, there exist plenty of other types of attacks that can be used to make life difficult for a system or security administrator.
The cryptanalysis uses the following tools [15]:
- Probability theory and statistics.
- The Linear algebra
- Abstract algebra (group theory)
- Computer languages
- Complexity theory
The methods for attacking a stream cipher can be classified according to the information available to the cryptanalyst, the aim of the attack, or the way the attack is done. It is often assumed that the attacker has knowledge of the cryptographic algorithm, but not the key.
Fig: A binary additive stream cipher [16].
The different categories of attacks based on the information available to the attacker include:
Ciphertext-only attack: known ciphertext attack is an attack model for cryptanalysis where the attacker is assumed to have access only to a set of ciphertexts. The attack is completely successful if the corresponding plaintexts can be deduced, or even better, the key. The plaintext must have
redundancies for such an attack to be successful. The various statistical techniques developed by cryptographers for attacking ciphertext are:
-
-
- Frequency analysis.
- Traffic analysis
- Brute force attack
-
Known-plaintext attack: The attacker has samples of both the plaintext and its encrypted version (ciphertext) and is at liberty to make use of them to reveal further secret information; typically this is the secret key.
· Chosen-plaintext attack: A chosen-plaintext attack (CPA) is an attack model for cryptanalysis which presumes that the attacker has the capability to choose arbitrary plaintexts to be encrypted and obtain the corresponding ciphertexts. The goal of the attack is to gain some further information which reduces the security of the encryption scheme. In the worst case, a chosen-plaintext attack could reveal the scheme's secret key. Any cipher that can prevent chosen-plaintext attacks is then also guaranteed to be secure against known-plaintext and ciphertext-only attacks; this is a conservative approach to security. The two distinguished forms of chosen plaintext attacks are :
§ Batch chosen-plaintext attack
§ Adaptive chosen-plaintext attack
Chosen-ciphertext attack: An attack model where the cryptanalyst gathers information, at least in part, by choosing a ciphertext and obtaining its decryption under an unknown key. The aim is to deduce the key. A better approach is to use a cryptosystem which is provably secure under chosen-ciphertext attack, including (among others) RSA-OAEP, Cramer-Shoup and many forms of authenticated symmetric encryption.
The attacks are also classified based on the aim of the attack as follows:
Key recovery: A method to recover the key.
Prediction A method for predicting a bit or sequence of bits of the keystream with a probability better than guessing.
Distinguishing A statistical method to distinguish the keystream from a random sequence
Key Recovery methods:
Exhaustive Key Search: is a trivial way to recover a key. Given a keystream the attacker tries all different keys until the right one is found. If the key is n bits, the attacker has to try 2n keys in the worst case and 2n?1 keys on average. Brute force attack requires a large amount of computing power and a large amount of time to run. For the majority of encryption algorithms a brute force attack is impractical due to the large number of possibilities.
Key Size n(bits)
Number of
Alternative Keys
Time required at
1 encryption/µs
Time required at
106 encryptions/µs
32
232 = 4.3 x 109
231 µs = 35.8 minutes
2.15 milliseconds
56
256 = 4.3 x 1016
255 µs = 1142 years
10.01 hours
128
2128 = 4.3 x 1038
2127 µs = 5.4 x 109 years
5.4 x 1018 years
168
2168 = 4.3 x 1050
2167 µs = 5.9 x 1036 years
5.9 x 1030 years
26 characters (permutation)
26! = 4 x 1036
2 x 1026 µs = 6.4 x 1012 years
6.4 x 106 years
Average Time Required for Exhaustive Key Search
Dictionary attack: This essentially involves running through a dictionary of words in the hope that the key (or the plaintext) is one of them. This type of attack is often used to determine passwords since people usually use easy to remember words. So this type o attack can be prevented by avoiding the words present in the dictionaries as key or password. Alphanumeric characters can be a better option against dictionary attack.
Time Memory Trade-offs: A time memory trade-off (TMTO) attack is an attack were large amounts of precomputed data is used to lower the computational complexity. The name comes from the fact that there is often a trade-off between the amount of memory used for data storage and the amount of time used for computations. Birthday attack is the first TMTO attack used to break A5 cipher used in GSM standard [5]. To avoid the known TMTO attacks for stream ciphers, the state size should be at least twice the key size, and the IV size should be at least as large as the key size.
Distinguishing Attacks: A distinguishing attack is a method for distinguishing the keystream from a truly random sequence. Distinguishing attacks can be generic in the sense that they are likely to work on a category of ciphers, or very specific and targeted at a specific cipher. A typical specific distinguishing attack uses the fact that some part of the keystream, with a high probability, is a function of some other parts of the keystream.
Zi = f(Zi?1,Zi?1, . . . ,Zi?n)
If a cipher fails any of the ordinary statistical tests like frequency test, serial test, poker test, runs test, and autocorrelation test, this can be used to distinguish the keystream. Distinguishing attacks often require large amounts of keystream. An easy way to get away from such attacks is to state that the cipher must be rekeyed after a certain amount of keystream.
Guess and Determinate attack: The strategy used here is to guess a few of the unknown variables in the cipher, and from the guessed values deduce the values of other unknown variables. This is often slower compared to exhaustive key search due to nonlinearities and irregularities in the cipher. Because of this, an assumption is made that makes the cipher more linear. If the probability that the assumption holds is p, the expected number of tries until the assumption holds are 1/p.
The attack is successful if 2g · (1/p) · w < 2k, where g is the number of guessed bits, p is the probability that the assumption holds, w is the work needed to determine if the guess is right and the assumption holds, and k is the key size.
Differential Cryptanalysis:
The attacker can introduce errors during the computation, leading to an error in the output. By examining the difference between an unfaulty computation and a faulty one, the attacker can deduce information on the computation [6]. These ideas are used in various cryptanalytic attacks on stream ciphers. For example, in [7] it is shown that two IVs with some given difference may produce the same key stream. A key difference or even an initial value difference can be used to predict the stream differences with some probability. This phenomena is easily observed and detected where the key loading procedure and the key updating procedure are linear (as in an LFSR), as well as in nonlinear procedures that initialize the internal state of the stream cipher like in RC4 [8].
Correlation attack: The correlation attack is a class of attack on stream cipher and can be applied if the keystream z1, z2, . . .zn must be correlated with the output sequence a1, a2 . . . of a much simpler internal device, such as a LFSR. The two sequences are correlated if the probability P(zi = ai) ? 0.5[9][10][11]. Synchronous stream ciphers are resynchronized frequently. During the resynchronization period, the secret key is manipulated while the power consumption is data dependent, we can utilize this mortal weakness to perform CPA (Correlation Power Analysis) to recover the secret key [18]. The basic correlation attacks are mainly cipher text only or known plain text attack.
Algebraic attack: A method of cryptanalytic attack used against block ciphers and stream ciphers that exhibit a significant amount of mathematical structure. Any stream cipher is defined by a system of algebraic equations. A solution of this system gives the secret key. Algebraic attacks on LFSR-based stream ciphers recover the secret key by solving an over defined system of multivariate algebraic equations. They exploit multivariate relations involving key bits and output bits and become very efficient if such relations of low degrees may be found. In view of algebraic attacks, low degree multiples of Boolean functions are a basic concern in the design of stream ciphers as well as of block ciphers.
The immunity for Algebraic attack is, if there are several filtering functions fi in a stream cipher, there should be no algebraic combination of the fi and of “reasonable” size, that would have an unusually low degree. By extension, this criterion also applies to stream ciphers that have only one filtering function.
Indeed a cipher having only one filtering function f, can be seen as using several functions defined as: f, f ? L, f ? L2, . . .. It can be seen that, in all cases, our security criterion can be re-formulated as: there should be no non-trivial multivariate relations of low degree that relate the key bits and one or many output bits of the cipher [12].
Side Channel Attack: “Side channel” attacks are based on “Side channel information”. Side channel information is information retrieved from the physical implementation instead of theoretic weaknesses. Any information that can be measured, and is dependent on the key, state, or plaintext. Side channel analyses are of concern because the attacks can be mounted quickly and also be implemented using readily available hardware costing only a few dollars to thousands of dollars. The amount of time required to attack and analysis depends on the types of attack (power analysis, timing attack,etc). In a timing attack the attacker tries to break a cipher by analyzing the execution time for encryption or decryption. It can be done if the encryption or decryption time depends on the input. The cryptosystems often take slightly different time to process different inputs. This is usually the case for asymmetric algorithms [13].
The timing attacks are based on measuring the time required for a unit to perform operations. This information can lead to the information about the secret keys. Power analysis is similar to a timing attack, but the attacker studies the power consumption of a cryptographic device (smart card, CPU). Other information that has been suggested includes leaked electromagnetic radiation and sound [14]. To circumvent side channel attacks, in general the time that operations take must be totally independent of the input data or key data. Whenever different sub operations are performed according to key bits or input data ,all sub operations should take same number of clock cycles. This will prevent timing attacks. Blinding is another technique for preventing side channel attacks.. Blinding means that the execution time and power consumption are made independent of the inputs.
The other technique to prevent side channel attacks is by avoiding the use of procedures that use intermediates or keys for conditional branching operations. Calculations should be performed using functions that use elementary operations (AND,OR and EXOR). This feature can make it extremely difficult to guess the input and key values using measurement of timing or power consumption .Introduction of random delays to perform the operations can also make the attack difficult. Power Consumption Balancing can also be used where dummy registers and gates are used to perform useless operations. Reducing the signal size and addition of noise increases the number of samples required to attack, possibly to an unfeasibly large number [17].
Conclusion
This paper summarizes the basic Cryptographic cipher system, specially the Stream cipher system, its advantages over the Block cipher system. The attacks and classification of attacks and some common types of attacks applied on Stream cipher systems for cryptanalysis and the Immunity towards those types of attacks.
References:
[1]. Simon Singh. The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography. Anchor Books, New York, 2000. ISBN 0-385-49532-3.
[2]. Whitfield Diffie and Martin E. Hellman. New Directions in Cryptography. IEEE Transactions on Information Theory, 22(6):644–654, November 1976.
http://www.cs.jhu.edu/~rubin/courses/sp03/papers/diffie.hellman.pdf.
[3]. Ron Rivest, Adi Shamir, and Len Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 21(2):120–126, 1978. http://theory.lcs.mit.edu/~rivest/rsapaper.pdf.
[4]. Marcus Schafheutle and Stefan Pyka. Stream Ciphers. Technical report, NESSIE consortium, February 2003. 103–122 pp. https://www.cosic.esat.kuleuven.be/nessie/deliverables/D20-v2.pdf.
[5]. Jovan Dj. Goli´c. Cryptanalysis of alleged A5 stream cipher. In Eurocrypt’97 LNCS 1233, pages 239–255.Springer-Verlag,1997.
http://www.gsm-security.net/papers/Cryptanalysis_of_Alleged_A5_Stream_Cipher.pdf.
[6]. Differential Cryptanalysis in Stream Ciphers : Eli Biham1 Orr Dunkelman?2 1Computer Science Department, Technion. Haifa 32000, Israelbiham@cs.technion.ac.il 2Katholieke Universiteit Leuven, Dept. of Electrical Engineering ESAT/SCD-COSIC. Kasteelpark Arenberg 10, B-3001 Leuven-Heverlee, Belgium orr.dunkelman@esat.kuleuven.be.
[7]. Hongjun Wu, Bart Preneel, Attacking the IV Setup of Py and Pypy, eSTREAM website, 2006. Available online at http://www.ecrypt.eu.org/stream/papersdir/2006/050.pdf.
[8]. Ronald L. Rivest, RSA security Response to weaknesses in key scheduling algorithm of RC4, Technical note, RSA Data Security, Inc., 2001. [The structure of RC4 was never published officially, it was leaked in 1994 to the Internet. This note confirms that the leaked code is indeed RC4].
[9]. Thomas Siegenthaler. Decrypting a Class of Stream Ciphers Using Ciphertext Only. IEEE Transactions on Computers, 34(1):81–85, January 1985
[10]. Fredrik J¨onsson. Some results on fast correlation attacks. PhD thesis, Lund University, May 2002.
http://homes.esat.kuleuven.be/~jlano/stream/papers/jon02.ps
[11]. Willi Meier and Othmar Staffelbach. Fast correlation attacks on certain stream
ciphers. Journal of Cryptology, 1(3):159–176, 1989.
[12]. Algebraic Attacks on Stream Ciphers with Linear Feedback Nicolas T. Courtois1 and Willi Meier2 Cryptography Research, Schlumberger Smart Cards, 36-38 rue de la Princesse, BP 45, F-78430 Louveciennes Cedex, France, courtois@minrank.org 2 FH Aargau, CH-5210 Windisch, Switzerland, meierw@fh-argau.ch.
[13]. David Brumley and Dan Boneh. Remote Timing Attacks are Practical. In Proceedings of the 12th USENIX Security Symposium, August 2003.
http://www.cs.cmu.edu/~dbrumley/pubs/openssltiming.pdf.
[14]. Adi Shamir and Eran Tromer. Acoustic cryptanalysis: on nosy people and noisy machines. http://www.wisdom.weizmann.ac.il/~tromer/acoustic/
[15] M. Robshaw. Stream ciphers. Technical Report TR – 701. RSALabs, July 1995.
[16] Analysis of Stream Cipher Security Algorithm,Journal of Information and Computing Science,Vol. 2, No. 4, 2007, pp. 288-298, Musbah J. Aqel 1 +, Ziad A. Alqadi 2 ++, Ibraheim M. El Emary, Received October 12, 2006, accepted January 30 2007.
[17] An Introduction to Side Channel Attacks , Hagai Bar-El, White paper,Discretix Technologies limited.
[18] Correlation Power Analysis Attack against Synchronous Stream Ciphers, Keke Wu1, Huiyun Li1, Bo Peng2, Fengqi Yu1 1. Department of Integrated Electronics, Shenzhen Institute of Advanced Technology (CAS), Shenzhen, China 2. Side Channel Security Technology LaboratoryZTEIC Design Co., Ltd, Shenzhen, China {kk.wu, hy.li, fq.yu}@siat.ac.cn, peng.bo@zte.com.cn.
About the Author
Anaish for Dummies - a dictionary of the language of Anastacia fans
[simpleaffiliate source="amazon" results="10"]dictionary for dummies[/simpleaffiliate]
[simpleaffiliate source="cj" results="10"]dictionary for dummies[/simpleaffiliate]
[simpleaffiliate source="clickbank" results="10"]dictionary for dummies[/simpleaffiliate]
No comments:
Post a Comment