A New Cryptanalsis Method Of Cellular Automata Based Encryption Systems

Abstract

Şifreleme haberleşme ağlarıyla gönderilen veya elektronik ortamlarda depolanan bilgileri korumayla ilgilenen bilimsel bir disiplindir. Aynı zamanda mesajın orijinalliğini kontrol etmek, dijital imza üretmek, para transferi için elektronik kimlik oluşturmak, kredi kartı bilgileri göndermek ve programlan virüslerden korumak için kullanılır. Şifrelemedeki temel problem açık mesajları şifreli mesajlara dönüştürecek ve şifre analize (şifrelenmiş mesaja ulaşarak açık mesajı elde etme tekniği) dayanabilecek bir yöntem geliştirmektir. Şifreleme dünyası şifreleme algoritmaları için bir güvenlik ölçütü araya gelmiştir. Claude Shannon ilk kez şifreleme sistemleri için bu amaçla bir matematiksel model vermiştir. Şifre analiz, anahtara sahip olmadan açık mesaja ulaşmak için yapılan çalışmaların tümüdür. Genel kabul şifre analizcinin kullanılan şifreleme sisteminin tüm detaylarını anahtar hariç bildiği şeklindedir. Bu Kerckhoff kuralı olarak bilinmektedir. Eğer şifre analizci kullanılan şifre sistemini bilmiyor ise işi güçleşecektir. Ancak şifreleme sisteminin güvenliği buna dayandırılamaz. Böylece şifreleme sistemleri Kerckhoff kuralı esas alınarak tasarlanır. Yapılabilecek saldırılar şu şekilde sınıflanabilir: 1. Şifreli metin saldırısı (Ciphertext Only- Attack): Şifre analizci sadece şifreli metine sahiptir. 2. Bilinen açık metin saldırısı (Known-Plaintext Attack): Şifre analizci aynı anahtar için bazı açık ve şifreli metin çiftlerini bilir. 3. Seçilmiş açık metin saldırısı (Chosen-Plaintext Attack): Şifre analizci geçici olarak şifreleme cihazına erişebilir ve kendi seçmiş olduğu bazı açık metinler için şifrelenmiş metinler elde edebilir. 4. Seçilmiş şifreli metin saldırısı (Chosen-Ciphertext Attack): Şifre analizci geçici olarak şifre çözme cihazına erişebilir ve seçtiği bazı şifrelenmiş metinler için açık metinler elde edebilir. İş yükü (work factor), bir algoritmayı kırmak için gereken bütün analizlerin bir ölçütüdür. İş yükünü tanımlamak için belirlenmiş bir kurallar kümesi yoktur. Genel olarak ölçüt şifre analiz için geçen süre ve gerekli matematiksel işlem adedi veya gerekli donanım ve yazılımların miktarı ile verilebilir. Gerekli olan para miktarı da genel bir karşılaştırma ölçütü olarak alınabilir XV Eksiksiz şifre analiz (exhaustive search) metodunda, anahtar veya açık mesaj mümkün bütün çözümler tek tek denenerek bulunur. Elde şifrelenmiş ve buna karşı düşen açık mesaj çifti varsa, mümkün bütün anahtarlar şifrelenmiş mesaj eldeki doğru mesajı verinceye kadar denenerek doğru anahtar bulunur. Elde sadece şifrelenmiş mesaj varsa, anlamlı bir mesaja ulaşıncaya kadar bütün anahtarlar sırasıyla denenerek aday anahtar bulunur. Eksiksiz şifre analizi için iş yükü deneme sayısıyla doğrudan orantılıdır. Bu tür saldın yapılacak deneme sayısı çok fazla yapılarak engellenir. Bir diğer tür şifre analizi ise şifre algoritmasından faydalanarak bazı parametrelere göre açık mesajı veya anahtarı (veya anahtarın bir kısmını) veren matematiksel denklemlerin çıkarılmasıdır. Bunu önlemek için bu tür denklemler oluşturulduğunda bunların çok karmaşık olmasını sağlayacak şekilde şifre algoritması tasarlanmakta, böylece algoritmanın analiz edilmesi pratikte mümkün olmamaktadır. Walsh dönüşümü ve fonksiyonları, işaret işleme, görüntü işleme, haberleşme, lojik tasarım ve analiz konularında geniş bir biçimde kullanılmıştır. Daha sonraları bu uygulama alanlarına şifreleme de katılmış, ilk kez Rueppel tarafından DES isimli şifreleme algoritmasının S-kutulanndan ikincisine yaklaşık bir fonksiyon bulmak amacıyla kullanılmıştır. Bu tezde bir şifre analiz aracı olarak kullanılan en iyi doğrusal yaklaşığın (best affine approximation - BAA) tanımı Walsh fonksiyonları esas alınarak aşağıda verilen şekilde hesaplanmaktadır. Walsh fonksiyonu, iki vektör w, z e GF(2") (GF Galois field) için ö(w,z) = (-l)wz, w z = w1zl@---®wnzn, şeklinde tanımlanır (© işlemi modulo 2 toplamayı göstermektedir). Her hangi bir boole fonksiyonunun Walsh dönüşümü S(/)(w) = 2~" ^(-l)fiz) Q(w,z) şeklinde zeGF(2)" ifade edilebilir ve bu gösterilim kullanılarak bu boole fonksiyonuna en yakın affine (doğrusal ve doğrusal fonksiyonların komplementlerinin oluşturduğu küme) fonksiyon, Pf(wx) =- +- S(f)(w), w,zeGF(2)" şeklinde bulunabilir. Bu tezde de affine yaklaşıklık, CA yerel fonksiyonuna (local function) doğrusal yaklaşıklık elde etmek için kullanılmıştır. Hücresel otomata (Cellular automata-CA), ilk kez Stanislav Ulam'in önerileri ardından, karmaşık sistemlerin davranışlarım modellemek için, John Von Neuman tarafından ortaya atılmıştır. Bir boyutlu CA, doğrusal bir dizi şeklinde birbirine bağlanmış n hücreden oluşmuş olup her hücre 0 veya 1 değerini alır. q=2r+l değişkenli bir boole fonksiyonu olan _/(*), hücre değerlerini günceller (şekil 1). Her hücre değeri paralel ve senkron olarak, xt+1 = f(xt ) fonksiyonu ile de ifade edildiği gibi, t=l,2,...,n değerleri için ayrık zamanda güncellenir. Sınır değerleri, indeksin mod n'e göre hesaplanması ile elde edilir, yani, doğrusal olarak birbirine bağlanmış bu dizi, aslmda, dairesel bir kaydedicidir (register), r, fix) fonksiyonun çapı olarak adlandırılmaktadır. Her hangi bir hücrenin yeni değeri hesaplanırken o hücrenin kendi değeri ve r komşuluğunda olan q hücrenin değeri kullanılır. q=3 için CA aşağıdaki şekilde gösterilmiştir. Mümkün n hücre olması ve her birinin 0 veya 1 değeri alabilmesi nedeni ile mümkün 2" tane durum vektörü vardır. S*, k. andaki durum vektörünü göstersin. Bu durumda CA, fc=0'da Sq başlangıç vektöründen başlayarak k = 1, 2, 3, için Sı, S2, S3, xvı sk Sk+ı Şekil 1: 1 boyutlu, 1 yançaplı fonksiyonlu hücresel otomata. vektörlerini izleyecektir. Bu sistemin zaman içindeki iterasyonu doğal olarak bir çevrime girecektir, Sk=Sk+p- Burada, P periyodu göstermekte olup, f[x) fonksiyonunun, başlangıç koşulunun ve hücre sayısının bir fonksiyonudur, fix) fonksiyonuna yerel fonksiyon (local map), S* durumunu (state) Sk+ı durumuna götüren fonksiyona genel fonksiyon (global map) adı verilir. Açıktır ki, CA'nın genel fonksiyonu 1-1 ve üzerine (onto) ise, CA'nın tersi vardır, dolayısıyla, ICA'dır. CA kullanılarak oluşturulmuş üreteçlerin şifreleme amacı ile kullanılabilmesi için başlangıç değerinin (başlangıç durum vektörü So) verilen durum vektörlerinden bulunması güç olmalıdır. Wolfram, bu problemin NP-tam (nondeterministic polynomial) sınıfından olduğunu ve şu ana kadar n'ye üstel (exponansiyel) olarak bağlı olan algoritmalardan daha iyi bir algoritma bulunamadığını göstermiştir.30 numaralı kurala sahip CA rasgele sayı üreteci olarak ilk kez Wolfram tarafından önerilmiştir. Bu sistem yardımı ile üretilen durum vektörlerinin, rasgelelik özelliklerini sağladığı görülmüştür. Önerilen Zikzak Algoritmasının Tanımlanması: Önerilen algoritma yaptığı iterasyonlar nedeniyle zikzak algoritması olarak isimlendirilmiştir. Zikzak algoritması, ^-değişkenli fix) fonksiyonunun en iyi doğrusal yaklaşıklığını (Best Affine Approximation-BAA) kullanmaktadır. j{x) fonksiyonunun BAA'sı olan g-değişkenli affine g(x) fonksiyonu, boole fonksiyonlarının spektral analiz araçları kullanılarak elde edilebilir. Bir başka deyişle, g(x), f[x) ile doğrusal fonksiyonlar arasındaki en düşük Hamming uzaklığına sahip olan affine fonksiyondur. İki fonksiyon arasındaki Hamming uzaklığı bu tezde şöyle verilmiştir: Fonksiyonların mümkün bütün girişlerinin, xeZg, bu fonksiyonlara uygulanmasıyla elde edilen 29 uzunluklu vektörlerin Hamming uzaklığına, fonksiyonların Hamming uzaklığı denir. xvıı Önerilen zikzak algoritması şekil 2 yardımıyla şöyle açıklanabilir. Durum vektörü Sit+ı, fix) fonksiyonunun 5* vektörüne uygulanması sonucunda oluşturulmuştur. Amaç S* vektörünü bulmaktır, ancak, fix) genel halde doğrusal olmayan bir fonksiyon olup, tüm çözümleri tek tek denemek dışmda analitik bir çözüm bilinmemektedir. Algoritmada ilk olarak fix) yerine, fix)'in en iyi doğrusal yaklaşığı olan g(x) doğrusal fonksiyonu kullanılarak, Sk vektörüyle yaklaşık olarak aynı olan S^ vektörü hesaplanır. Bu işlem g(x) vektörü kullanılarak oluşturulan bant matrisin tanımladığı doğrusal denklem sisteminin, Sk+ı kullanılarak çözülmesiyle kolayca gerçeklenir. Ancak elde edilen Si vektörünün geçerli bir çözüm olduğunun kontrol edilmesi, yani fix) uygulandığında Sjt+ı'i üretmesi, yani, Sl+1=Sk+ı olması gerekmektedir. Aksi durumda, geçerli bir çözüm üretilememiş olup, elde edilen 5^'da hata düzeltmesi yapılmalıdır. Bu düzeltme, 5^+1 ve Sji+ı'in aynı olmayan noktalan dikkate alınarak, S*k üzerinde yapılır. Bu işlemin sonucunda geçerli bir S*k elde edilir. Şekil 2: Algoritmanın bir kısmının şematik gösterilimi. Önerilen Zikzak Algoritmasının Analizi: Zaman karmaşıklığı bu şifre analiz metodu için temel ölçüttür. Önerilen zikzak algoritmasının anlamlı olması için zaman karmaşıklığının, eksiksiz denemenin zaman karmaşıklığından daha az olmalıdır. Eksiksiz deneme n genişlikli bir CA için 0(2") şeklinde verilir. Her güncelleme fonksiyonu yeni bir sistem tanımladığı için analitik bir karmaşıklık fonksiyonu vermek çok güçtür. Bu nedenle ancak 11. adıma kadar olan kısım için bir üst şuur verilebilmiştir. Analitik üst sınır 0((l+a)n) 0.5

Cryptography is a scientific discipline that is concerned for the protection of information transmitted through communications networks or stored in electronic media. It can also be used for message authentication, digital signature and personal identification for authorizing electronic funds transfer, credit card transactions, protecting programs against viruses. A basic problem in cryptography is devising procedures to transform messages (plaintext) into cryptograms (ciphertext) that can withstand intense cryptanalysis (the techniques used by opponents to penetrate encrypted communications and recover the original information). The world of cryptology has searched a measure for the security of the encryption algorithm. Shannon is the first person that gave the mathematical model for the security of cryptographic system. Obtaining plaintext from the ciphertext without having encryption key and/or algorithm is called cryptanalysis. The general assumption that is usually made is that the opponent, the cryptanalyst, knows the cryptosystem with all details being used but not the key. This is usually referred to as Kerckhoff s principle. Of course, if cryptanalyst does not know the cryptosystem being used, that will make his task more difficult. However, the security of a cryptosystem is not based on the assumption that cryptanalyst does not know what system is being employed. Hence, cryptosystem is designed under Kerckhoff s principle. Different types of attacks can be enumerated as follows: 1. Ciphertext Only: The opponent possesses a string of ciphertext, c. 2. Known Plaintext: The opponent possesses a string of plaintext p, and corresponding ciphertext c. 3. Chosen Plaintext: The opponent has obtained temporary access to the encryption machinery. Hence, he can choose a plaintext string, p, and construct the corresponding ciphertext string, c. 4. Chosen Ciphertext: The opponent has obtained temporary access to the decryption machinery. Hence, he can choose a ciphertext string, c, and construct the corresponding plaintext string, p. Work factor measures what is needed to carry out a specific analysis or attack against a cryptographic algorithm. In practice, there is no universally accepted, fixed set of parameters used to express the work factor. However, it is frequently measured in one or more of the following: cryptanalyst hours, number of mathematical or logical operations, computing resources, necessary special hardware and calendar time. To be useful, the work factor should be expressed using parameters, which can be translated for the purpose of comparison into a common base, such as cost in dollars. In an exhaustive attack, an attempt is made to recover the plaintext or key by using direct search methods. For example, in key exhaustion, a known plaintext is enciphered with a trial key and result is compared for equality with the known corresponding ciphertext. If only ciphertext is available, it can be decrypted with the trial key and the resulting plaintext can be inspected to see if it makes any sense. In this way, it can be determined if the trial key is a candidate for the unknown key or not. The work factor of an exhaustive attack, which is directly proportional to the number of trials, is easily determined even when the number of trials is so large that the attack is not feasible. This is not the case with some other attacks from a definition of the cryptographic algorithm solved for the variable or variables representing the known message or key. One way to thwart this purely mathematical attack is to construct the algorithm so that each plaintext bit is a sufficiently complex mathematical function of the ciphertext and plaintext. If the mathematical equations describing the algorithms operation are so complex that, an analytical attack cannot be successful, then a work factor for this method cannot be calculated. In that case, one usually says that the algorithm cannot be broken in the practical sense. Walsh functions and Walsh transforms have a wide range of applications to signal processing, image processing and communication as well as logic design and analysis. Rueppel have investigated the applications of spectral techniques to cryptology by analyzing 2.nd S-box of DES (Data Encryption Standard) algorithm. Presentation of Walsh transform can be given as follows: Let w and z are two vectors in GF(2)n.For all w and z in GF(2)n, the Walsh functions are defined as: Q(w, z) = (-l)wz where w z = wlz1®---® wnz", and © denotes modulo-2 addition (exclusive-or operation). The Walsh transform is defined as S(f)(w) = 2" ^(-l)fU)Q(w,z). The following formula about how to determine zeGF(2)° the best affine approximation (BAA) of Boolean functions was developed by Rueppel with an information approach Pf(wx) = - I - Sf(w). BAA is used to find affine approximation to a nonlinear updating function of the cellular automata at the proposed zigzag algorithm. Cellular Automata were introduced by John von Neuman, following a suggestion of Ulam, to provide a more realistic model for the behavior of complex systems. A one-dimensional cellular automaton consists of a linearly connected array of n cells, each of which takes the value of 0 or 1, and a Boolean function ^jc) with q variables. The value of the cell jc,- is updated in parallel (synchronously) using this function in discrete time steps as xi =f[x) for i= 1,2,... n. The boundary conditions are usually handled by taking the index values modulo n, i.e., the linearly connected array is actually a circular register. The parameter q is usually an odd integer, i.e., q = 2r+ 1, where r is often named the radius of the function /(x); the new value of the ith cell is calculated using the value of the ith cell itself and the values of r neighboring cells to the right and left of the ith cell. The cellular automaton for q=3 is illustrated in Figure 1. xi sk st. :+l Figure 1: One-dimensional cellular automata with the radius one updating function. Since there are n cells, each of which takes the values of 0 or 1, there are 2" possible state vectors. Let Sk denote the state vector at the time step L Starting from an initial state vector So, the cellular automaton moves to the states Si, Sz, S3, etc., at time steps k = 1, 2, 3, etc. The state vector Sk takes values from the set of n-bit binary vectors as k advances, and the state machine will eventually cycle, i.e., it will reach a state Sk+p which was visited earlier Sk - Sk+p. The period P is a function of the initial state, the updating function, and the number of cells. The cells alter their states synchronously on discrete time steps according to the local rule / of the CA. The global rule is a function from Sk to Sk+i that gives the new state of each cell as a function of the old states of its neighbors. A cellular automaton is invertible if its global map is invertible, i.e., if updating function is one-to-one and onto. The construction of seed value of CA (the initial state vector So) from the given sequence of state vector must be difficult for cryptographic applications. It was stated by the Wolfram that this problem is in the class NP. No systematic algorithm for its solution is currently known that takes a time less than exponential in n. The cellular automaton chosen, known as rule 30, seems according to the numerical evidence to generate temporal sequences that have a high degree of randomness is shown by Wolfram. Brief Description of the Proposed Zigzag Algorithm: The proposed algorithm is named as zigzag algorithm because of iterations. The zigzag algorithm is based on the best affine approximation of the ^-variable updating function f(x). Using tools from the spectral analysis of Boolean functions a ^-variable linear function g(x) that is the best affine approximation to fix) is constructed. In other words, g(x) has the minimum Hamming distance tof[x) among all linear functions. The Hamming distance between two functions is defined as the xn Hamming distance between the binary vectors of length 2q produced by the application of all possible input values xe Z\ to these functions. Figure 2. Schematic representation of the first four steps of zigzag algorithm. The main idea of the zigzag algorithm is illustrated in Figure 2. The state vector Sk+i is computed by applying the function f(x) to the state vector S*. An approximation to St is calculated by finding a vector S*k that maps to Sk+i under the linear function g(x). The vector S*k is computed by solving a set of linear equations whose matrix is determined by the parameters of the linear function g(x). Then f(x) is applied to S*k and calculated S*k+l which is an approximation to the state vector Sk+i. Since 5jt+i is known, S*+i and S*M are compared, and corrections to the state vector S*k is made until the state vector S*k which results in the equality 5^+1= S*+i is obtained. The zigzag algorithm calculates one of the predecessors of the state vector Sk+i- Analysis of the Zigzag Algorithm: The time complexity is the basic criteria for success of the zigzag algorithm. The time complexity of zigzag algorithm must be smaller than exhaustive search for usefulness. The order of exhaustive search can be given as 0(2") for size n CA. Since each updating function defines a new system, analytic derivation cannot be given, hence only a loose upper bound can be given up to step 11 of zigzag algorithm. Analytical upper bound is derived as 0((l+a)n) for up to step 11 of the zigzag algorithm. Consequently, whole algorithm (up to step 12) execution time can be derived empirically by the help of computer simulation and curve fitting techniques. The time complexity of the zigzag algorithm is exponential. Hence, oc2p" is chosen nonlinear model. Since chosen model has a property that is known as intrinsically linear, a linear regression method can be used by the help of some xm transformation, hence empirical average complexity is found as O(20656n 89658). This complexity is approximately square root of exhaustive search. Zigzag algorithm has three different halting steps, which are step 4, step 11, and step 12. The zigzag algorithm finds solution and stops at one of these steps. The halting step depends on r, n, updating rule and S*. The step 4 is essential, since the zigzag algorithm finds solution in polynomial time complexity, 0(ng2), instead of exponential time complexity in this step. It is also fact that if the updating function is affine, the solution can be found in polynomial time complexity by just solving linear equations, but it is not true for nonlinear updating functions. Computer experiments show that 36.19 % of all configurations can be found in 0(nq2) time for size 13 although expected success rate is 3.181 %, which shows that experimental success rate is approximately 10 times larger than the expected success rate. Applications of Proposed Zigzag Algorithm: The applicability of proposed zigzag algorithm is depending how the CA is used on the construction of encryption algorithm. The concept of the zigzag algorithm can be applied to a variety of cryptographic systems, for instance, the proposed zigzag algorithm was applied to two different cryptographic algorithms: The first one was Wolfram's pseudorandom number generator. It was shown that, the security of Wolfram generator was reduced further. The second one was about Damgard cryptographic hash function. It was shown that collision values could be calculated by the help of the zigzag algorithm. The given zigzag algorithm is useful for some cryptanalytic attacks; moreover the concept of the zigzag algorithm can be generalized for cryptographic systems, which are based on different algebraic systems.