Maximum Length NFSRs

Nowadays, I spend most of my time studying on Nonlinear Feedback Shift Registers (NFSRs). Especially the ones with Maximum period.

A feedback shift register is a device that shifts its contents into adjacent positions within the register and fills the position on the other end with a new value generated by the feedback function. If the feedback function is linear, everything is easy! :)But when you start to work on nonlinear feedback functions, things start to get a little bit harder.

There are some important unsolved problems and conjectures related to the selection of feedback function of a NFSR. There is no efficient method that finds feedback function with maximum period and also, given a feedback function it is hard to predict the period.

If you want to learn more about NFSRs, you can start with the following papers and books.

1. H. Fredricksen. A survey of full length nonlinear shift register cyclealgorithms. Siam Review, 24(2):195–221, 1982


2. S. W. Golomb. Shift Register Sequences. Aegean Park Press, LagunaHills, CA, USA, 1981


3. A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone. Handbook ofapplied cryptography. CRC Press, Boca Raton, Florida, 1996.
   

If you want to discuss anything about NFSRs, please feel free :)

A New Book - Cryptographic Engineering

This is a new book by Koc, Cetin Kaya (Ed.) written for graduate students and researchers in cryptography and engineers working in the industry.

Here are some details from the Springer web page: Cryptographic Engineering covers the theory and practice of engineering of cryptographic systems, including encryption and decryption engines, digital signature and authentication systems, true random number generators, and the design, implementation, testing, and validation of cryptographic systems. This book also addresses cryptanalysis of security systems for the purpose of checking their robustness and their strength against attacks, and building countermeasures in order to thwart such attacks by reducing their probability of success.

The material includes four important features: ASIC and FPGA hardware design for cryptography, Principles and practice of true random number generators, Detailed algorithmic treatment of public-key cryptographic systems and emphasis on the engineering of systems, and Side-channel attacks on cryptographic systems and countermeasure designs.

Cryptographic Engineering is a comprehensive text that is suitable as a handbook for hardware and software engineers who are interested in building secure systems using cryptographic techniques.

A Practical Cryptographic Attack

After CIMPA Summer School-Codes over Rings

This summer, METU hosted the CIMPA-UNESCO-TUBITAK summer school on "Codes over Rings". I was able to follow some of the lectures. There were about 40 participants from Germany, India, Irak, Iran, Jordan, Ivory Coast, Philippines and Tunisia.


In May 18-30 2009, there will be another summer school on cryptography in Morrocco. The deadline for registration is january 31, 2009. Here is the link.

CFP: 3rd Information Security and Cryptology Conference

This is the Call for papers of the 3rd Information Security and Cryptology Conference in Ankara, Turkey.

This year the main topic of the International Information Security and Cryptology Conference is “Homeland Security”. We are hoping that this conference will be a platform to discuss information security, to present new approaches and applications, and to inform wider audiences about security of the nation. We also believe that this conference will positively affect the researches and applications conducted in the field of information security and cryptology.

Conference Venue
The conference will take place in METU Culture and Convention Center, Ankara, TURKEY

Important Dates
Submission deadline November 10, 2008
Notification of decision November 30, 2008
Proceedings version deadline December 10, 2008
Conference December 25 - 27, 2008

For more info, use the link

What is the 47th Mersenne Prime ?

A Mersenne prime is a prime of the form 2^{P}-1. First Mersenne primes are 3, 7, 31, 127. Recently, researchers have discovered the two largest known Mersenne primes with 12,978,189 and 11,185,272 digits.

The larger number qualifies for a $100,000 research award. If you want to make some money, you can go for the 47th Mersenne prime. For more information, check out the webpage of GIMPS- Great Internet Mersenne Prime Search.

My recent paper "On Independence and Sensitivity of Statistical Randomness Tests"

The paper is a joint work with Ali Doganaksoy and Serdar Boztas. It is going to be presented in SETA08 (SEquences and Their Application) Conference in Lexington, Kentucky.

Abstract:

Statistical randomness testing has significant importance in analyzing the quality of random number generators. In this study, we focus on the independence of randomness tests and its effect on the coverage of test suites. We experimentally observe that frequency, overlapping template, longest run of ones, random walk height and maximum order complexity tests are correlated for short sequences. We also proposed the concept of sensitivity, where we analyze the effect of simple transformations on output $p$-values. We claim that whenever the effect is significant, the composition of the transformation and the test may be included to the suite as a new test.

Keywords: Randomness tests, Coverage, independence

Cryptanalysis of Stream Ciphers

Cryptanalysis is the study of deciphering the encrypted message without knowing the secret key. A trivial attack to any cryptosystem is to try every possible key until the correct one is recovered. If the key size is k, attacker has to try 2^k keys in the worst case, and on the average 2^{k-1} keys. To detect the correct key, a plaintext/ciphertext pair is needed. However, if the plaintext contain redundancies, it may still be possible to recover the key using only the ciphertexts. One advantage of the attack is that it can be implemented in parallel. As the ability to compute increases, larger key sizes are needed. The size of the secret key should be large enough to avoid these exhaustive or brute force search attacks. In todays technology, 80-bit keys seem to offer acceptable level of security.

All other attacks applied to stream ciphers are compared to exhaustive key search in terms of time, data and memory complexity. Time complexity is related to the required number of primitive operations and can be separated into two parts, offline and online. The offline part is done once independent of the secret key and the results obtained in this part is used to attack the system in the online part. Data complexity considers the amount of data required for the attack, lastly, memory complexity is determined by the required amount of memory. The attack is considered to be successful if the maximum of time, data and memory complexity is less than the complexity of exhaustive search. Attacks with higher complexity are not be considered to be successful.

Ciphertext Only Attacks: In this type, the attacker aims to obtain information about the secret key or the plaintext by only observing the ciphertext. This kind of attack is successful if some information about the plaintext such as the language is available.Also, if plaintext is written using ASCII characters, it is very likely that the most significant bit of each character is equal to 0. In that case, ciphertext only attacks can be considered as known plaintext attacks.

Known Plaintext Attacks: Most of the attacks available in the literature use this scenario. Since keystream is generated independent of plaintext, this type is equivalent to known keystream attacks. Well known chosen plaintext or chosen ciphertext attacks are not suitable to analyze synchronous stream ciphers since chosen plaintext attack is also equivalent to the known plaintext attack.

Known IV or Chosen IV Attacks: In most of the protocols the value of IV is assumed to be public. In chosen IV attacks, the attacker is allowed to choose the set of IVs and resynchronize the cipher using this set.

The attack models against symmetric cryptosystems are divided into two groups depending on the intention of the attacker. Key recovery attacks aim to recover the secret key whereas distinguishing attacks aim to find deviations of cipher outputfrom ideal distribution. It is clear that distinguishing attacks are weaker compared to key recovery attacks that enable to decrypt anygiven encrypted message. However, distinguishing attacks are suitable to detect the cipher used during communication, this has significant importanceespecially in military applications.Moreover, in many cases, the idea of distinguishers may be improved to recover the key. It should also be noted that most of the candidates of the NESSIE project were broken by distinguishing attacks and were not included in the final report of the project.

A New Book "New Stream Cipher Designs"

This state-of-the-art survey presents the outcome of the eSTREAM Project, which was launched in 2004 as part of ECRYPT, the European Network of Excellence in Cryptology (EU Framework VI).

The goal of eSTREAM was to promote the design of new stream ciphers with a particular emphasis on algorithms that would be either very fast in software or very resource-efficient in hardware. Algorithm designers were invited to submit new stream cipher proposals to eSTREAM, and 34 candidates were proposed from around the world. Over the following years the submissions were assessed with regard to both security and practicality by the cryptographic community, and the results were presented at major conferences and specialized workshops dedicated to the state of the art of stream ciphers.

This volume describes the most successful of the submitted designs and, over 16 chapters, provides full specifications of the ciphers that reached the final phase of the eSTREAM project. The book is rounded off by two implementation surveys covering both the software- and the hardware-oriented finalists

To order, follow the link .

Stream Cipher Designs Based on NP-hard Problems

In public key cryptography, the general idea is to design ciphers based difficult problems that take very long time to solve. These systems utilize a private and a public key, where the public key is used to encrypt messages and the private key is used for decryption. The security of these cryptosystems is based on the fact that the private key can be computed from the public key only by solving a NP-hard problem. As examples, RSA and Rabin cryptosystems based on integer factorization, and Diffie-Hellman, ElGamal systems based on discrete logarithm problem can be given.

The same idea may be used to design stream ciphers. However, generating fast stream ciphers using this approach is a challenge. The cipher QUAD, introduced by Berbain et al. is based on the iteration of multivariate quadratic system of m equations and n100) when the quadratic equations are random.

QUAD uses three fixed and publicly known multivariate system of quadratic equations, S, S_0 and S_1. S=(Q_1,\ldots,Q_{kn}) consists of kn randomly chosen equations with n variables over GF(q). S_0 and S_1 are smaller systems with n equations and $ variables. These two systems are only used during the initialization of the cipher where the internal state (x_1,\ldots,x_n), n-tuple of GF(q) values, is generated using key and IV.

Keystream generation phase of QUAD is iterative and in each iteration
the following steps are performed;

Compute S(x)=(Q_1(x),\ldots,Q_{kn}(x)) where x is the current internal state,
Output (Q_{n}(x),\ldots,Q_{kn}(x)),
Update the internal state as x=(Q_{1}(x),\ldots,Q_{n}(x)).

Analysis of different instances of QUAD(q,n,r) are given in the FSE 2007 paper by Yang et al., where q is the field size, n is the number of variables and r is the number of outputs per round. In particular, the instance of QUAD(256,20,20) is broken using XL-Wiedemann in approximately 2^{66} cycles.

Side Channel Attacks

Side channel attacks utilize implementation-specific characteristics such as time delays, power consumptions or electromagnetic radiation. Since these attacks are implementation specific, physical implementation of the cipher is very critical, even tiny changes may result in big differences in security.

Timing attacks and power analysis are important types of side channel attacks. In timing attacks, the time taken to execute various steps in algorithms is analyzed. In power analysis, the attacker uses the varying power consumption of a cryptographic hardware device during computation and tries to find information about the state of the device. Other types of side channel attacks; fault, electromagnetic, acoustic, visible light, error message, cache based, frequency based, scan based attacks are summarized in the paper "Side-Channel Attacks: Ten Years After Its Publication and the Impacts on Cryptographic Module Security Testing" by Zhou and Feng.

To avoid side channel attacks in stream ciphers, apart from implementation issues, it is advised not to use building blocks such as stuttering phase in Sober-t32 and repeated manipulations of same bytes as in key schedule of RC4.

Hash Function Designs Based on Stream Ciphers

Hash function are fundamental components of many cryptographic applications such as digital signatures, random number generation, integrity protection, e-cash etc. Employing hash functions for these applications both increase the security and improve the efficiency of these systems. However, availability of any weaknesses in hash function designs is a very serious threat against the security of these applications.

MD5, SHA-1 and RIPEMD are widely used hash functions especially in SSL, PGP, S/MINE, SSH and SFTP applications. The design of these hash functions are based on the hash function MD4 as they iteratively use a compression function that inputs state variable and a fixed length block, and outputs another fixed length block. The strength of these hash functions is based on the collision-resistance property of the compression function.

Recently, many attacks against hash functions having similar construction to MD4 are proposed. Nowadays, these constructions are not considered to provide sufficient level of security against collision resistance. These recent studies motivated National Institute of Standards and Technology (NIST) to announce a public competition to select a new cryptographic hash function to be used as the new standard. It is commonly believed that many alternative design approaches are going to be proposed for the competition. Designing hash functions based on stream ciphers is a good approach due to the efficiency and the speed of these ciphers.

Panama is the first hash function based on a stream cipher. However, an attack against Panama is proposed, thereafter RadioGatun, an improved version of Panama, is proposed and claimed to offer better security than MD4 primitives. In this approach, iterative use of a simple round function and inclusion of input blocks are proposed. After inclusion of all input blocks, the state is updated a number of times without producing any output. Another hash function RC4-Hash is based on the very popular stream cipher RC4.

We propose a new experimental hash function based on the stream cipher Dragon designed by Dawson et al. Details are available in our paper : "Hash Function Designs Based on Stream Ciphers" which is a joint work with Ozgur Ozugur and Onur Kurt, presented in the national conferance "Bilgi Güvenliği ve Kriptoloji Konferansi" Ankara, 2007. Please contact for the pdf.

My PhD Thesis

I defended my PhD thesis on 24th of April. The title is "On Statistical Analysis of Synchronous Stream Ciphers". My presentation.

Here is the abstract:

Synchronous stream ciphers constitute an important class of symmetric ciphers. After the call of the eSTREAM project in 2004, 34 stream ciphers with different design approaches were proposed. In this thesis, we aim to provide a general framework to analyze stream ciphers statistically. Firstly, we consider stream ciphers as pseudo random number generators and study the quality of their output. We propose three randomness tests based on one dimensional random walks. Moreover, we theoretically and experimentally analyze the relations of various randomness tests.
Secondly, we focus on the ideas of algebraic, time memory tradeoff (TMTO) and correlation attacks and propose a number of chosen IV distinguishers. We experimentally observe statistical weaknesses in some of the stream ciphers that are believed to be secure.

Statistical Analysis of Synchronous Stream Ciphers

This study is a joint work with A. Doganaksoy and Ç. Çalık. We presented this study in SASC06 Stream Ciphers Revisited, Leuven Belgium, 2006,pdf Here is the abstract:

Synchronous stream ciphers produce long keystreams to be
XORed with plaintext. The output keystreams should be indistinguishable
from truly random sequences and should not leak any information
about the secret key and the internal state of the cipher. In this study,
we propose six new statistical tests to evaluate the randomness properties
of synchronous stream ciphers. We applied four of these tests to the
ciphers presented to ECRYPT and tabulated the results.

A Framework for Chosen IV Statistical Analysis of Stream Ciphers

Together with Prof. Thomas Johansson and Hakan Englund, I wrote a paper on d-monomial distinguishers and presented it at Indocrypt 2007, Chennai pdf Here is the abstract:

Saarinen recently proposed a chosen IV statistical attack, called the $d$-monomial test, and used it to find weaknesses in several proposed stream ciphers. In this paper we generalize this idea and propose a framework for chosen IV statistical attacks using a polynomial description. We propose a few new statistical attacks, apply them on some existing stream cipher proposals, and give some conclusions regarding the strength of their IV initialization. In particular, we experimentally detected statistical weaknesses in some state bits of Grain-128 with full IV initialization as well as in the keystream of Trivium using an initialization reduced to 736 rounds from 1152 rounds. We also propose some stronger alternative initialization schemes with respect to these statistical attacks.

The d-monomial distinguisher is improved by Fischer et al to recover the key pdf.

Linear Approximations for Trivium with 288 clockings

In SASC 2007, we presented a linear approximation for reduced round Trivium. Here is the abstract of the paper:

Existence of linear approximations based on key, IV and outputbits with non-negligible biases is a serious threat for thesecurity of synchronous stream ciphers. In this study, we focus onthe cipher Trivium, which is one of the strong candidates of theECRYPT project. No weaknesses of full Trivium have been reportedso far. We defined a reduced version of the cipher in terms ofnumber of initial clockings and found a linear approximation withbias $2^{-43}$. Using this approximation alone is not enough tobreak the cipher, however, it can be combined with similarapproximations to attack the cipher. Also, we propose a change inthe key and IV loading method, by which it gets harder to findlinear approximations.

You can reach the full paper using the link . Better approximations were obtained by Vielhaber, pdf.

Bibtex:
@inproceedings{STuran_Kara07,
author = {M. S\"{o}nmez Turan and O. Kara},
title = {Linear Approximations for 2-round Trivium},
booktitle = {Proc. First International Conference on Security of Information and Networks (SIN 2007)},
year = {2007},
isbn = {978--1--4251--4109--7},
pages = {96--105},
location = {Gazimagusa, TRNC},
publisher = {Trafford Publishing},
}