Friday, February 1, 2013

Riddle of 100 Passengers

Here is a riddle, that I came across recently. Enjoy!

There are a hundred passengers to board a plane with a hundred seats. Each passenger has a ticket with number from 1 to 100 and enters the plane in this order. The first passenger sits on seat 1, and the second sits on seat 2 and so on. However, the first passenger, instead of using his seat, chooses a random seat of the available 100. The second passenger comes in and sits in its seat, if it is available, otherwise chooses randomly from the 99 free seats. Third passenger sits in seat 3, if it is free, otherwise chooses a random seat from the remaining 98, etc. What is the probability that 100th passenger sits in the 100th seat?

Wednesday, October 10, 2012

Sunday, September 2, 2012

Another paper on NFSRs

"On the nonlinearity of maximum-length NFSR feedbacks" is published in Cryptography and Communications journal

Linear Feedback Shift Registers (LFSRs) are the main building block of many classical stream ciphers; however due to their inherent linearity, most of the LFSR-based designs do not offer the desired security levels. In the last decade, using Nonlinear Feedback Shift Registers (NFSRs) in stream ciphers became very popular. However, the theory of NFSRs is not well-understood, and there is no efficient method that constructs a cryptographically strong feedback function and also, given a feedback function it is hard to predict the period. In this paper, we study the maximum-length NFSRs, focusing on the nonlinearity of their feedback functions. First, we provide some upper bounds on the nonlinearity of the maximum-length feedback functions, and then we study the feedback functions having nonlinearity 2 in detail. We also show some techniques to improve the nonlinearity of a given feedback function using cross-joining.

Monday, July 23, 2012

AF is Short of Water!

Finally, I got the chance to visit the National Cryptologic Museum of NSA. Here you can use the German Enigma machines to encrypt your name (it is fun!), also see the huge US Navy Bombe used to decrypt Enigma. There is also a library including the David Kahn's collection. It is very interesting to listen to the stories on the impact of  cryptology. I think, one of the most interesting story is the battle of Midway. There is also a very nice gift shop! :) And, admission is free!

Monday, December 26, 2011

Evolutionary construction of de bruijn sequences

My recent paper presented at Artificial Intelligence and Security Workshop, Chicago, 2011.

A binary de Bruijn sequence of order n is a cyclic sequence of period 2n, in which each n-bit pattern appears exactly once. These sequences are commonly used in random number generation and symmetric key cryptography particularly in stream cipher design, mainly due to their good statistical properties. Constructing de Bruijn sequences is of interest and well studied in the literature. In this study, we propose a new randomized construction method based on genetic algorithms. The method models de Bruijn sequences as a special type of traveling salesman tours and tries to find optimal solutions to this special type of the traveling salesman problem (TSP). We present some experimental results for n < 14.

Sunday, December 19, 2010

SHA-3 Finalists

NIST announced the SHA-3 Finalists on December 9, 2010. Congratulations to the designers of Blake, Grostl, JH, Keccak and Skein. Any comments?

Friday, October 1, 2010

Near-Collisions for the Reduced Round Versions of Some Second Round SHA-3 Compression Functions using Hill Climbing

Our latest paper on near-collision resistance on some of the SHA-3 candidates; Blake, Fugue, JH and Hamsi is accepted for Indocrypt 2010.

Abstract :
A hash function is near-collision resistant, if it is hard to find two messages with hash values that differ in only a small number of bits. In this study, we use hill climbing methods to evaluate the near-collision resistance of some of the second round SHA-3 candidates. We practically obtained (i) 184/256-bit near-collision for the 2-round compression function of Blake-32; (ii) 192/256-bit near-collision for the 2-round compression function of Hamsi-256; (iii) 820/1024-bit near-collisions for 10-round compression function of JH. Among the 130 possible reduced variants of Fugue-256, we practically observed collisions for 7 variants (e.g. (k; r; t) = (1; 2; 5)) and near-collisions for 26 variants (e.g. 234/256 bit near-collision for (k; r; t) = (2; 1; 8)).

We would like to thank Charanjit S. Jutla for pointing out an error in Fugue's results, in the previous version of this paper which is presented at the SHA-3 Workshop.

Saturday, August 14, 2010

On the Compression Function of Hamsi

Hamsi is a family of cryptographic hash functions designed by Ozgul Kucuk. It is one of the second round candidates. The iteration mode of Hamsi is based on the `Concatenate-Permute-Truncate` design strategy. We recently published a paper titled "Message Recovery and Pseudo-preimage Attacks on the Compression Function of Hamsi-256" at PROGRESS IN CRYPTOLOGY – LATINCRYPT 2010.

Abstract: Hamsi is one of the second round candidates of the SHA-3 competition. In this study, we present non-random differential properties for the compression function of Hamsi-256. Based on these properties, we first demonstrate a distinguishing attack that requires a few evaluations of the compression function. Then, we present a message recovery attack with a complexity of 210.48 compression function evaluations. Also, we present a pseudo-preimage attack for the compression function with complexity 2254.25.

On Feedback Functions of Maximum Length Nonlinear Feedback Shift Registers

Our recent paper on the feedback functions of maximum length NFSRs is published in IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Science.

Abstract: Feedback shift registers are basic building blocks for many cryptographic primitives. Due to the insecurities of Linear Feedback Shift Register (LFSR) based systems, the use of Nonlinear Feedback Shift Registers (NFSRs) became more popular. In this work, we study the feedback functions of NFSRs with period 2n. First, we provide two new necessary conditions for feedback functions to be maximum length. Then, we consider NFSRs with k-monomial feedback functions and focus on two extreme cases where k=4 and k=2n-1. We study construction methods for these special cases.

Sunday, December 20, 2009

A new book - Computational Intelligence in Expensive Optimization Problems

Here is a book on optimization problems. It is going to be available in April 2010. The book includes a chapter with title "An evolutionary approach for the TSP and the TSP with Backhauls" written by H. Sural, N.E. Ozdemirel, I. Onder and myself.

If you want more details from Springer web page:

"In modern science and engineering, laboratory experiments are replaced by high fidelity and computationally expensive simulations. Using such simulations reduces costs and shortens development times but introduces new challenges to design optimization process. Examples of such challenges include limited computational resource for simulation runs, complicated response surface of the simulation inputs-outputs, and etc. Under such difficulties, classical optimization and analysis methods may perform poorly. This motivates the application of computational intelligence methods such as evolutionary algorithms, neural networks and fuzzy logic, which often perform well in such settings. This is the first book to introduce the emerging field of computational intelligence in expensive optimization problems."
Computational Intelligence , Engineering Design Optimization, Evolutionary Algorithms, Expensive Problems

Tuesday, May 19, 2009

Google SkyMap

My cell phone does not support Skymap for the moment, but I really liked the idea of moving your phone to find a specific star. Well of course I don't need SkyMap to spot Orion or the polar star. But might be useful to find some of the constellations and planets.

Here is its one minute demo.:

Monday, May 18, 2009

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 :)

Wolfram Alpha - Computational Knowledge Engine

It was officially launced today, and I had some chance to 'play' with it. I am impressed by a few of its features. One of them is when you input "ATTAGCGTTCAA", Wolfram Alpha recognizes it as a genome sequence and outputs some matches in human genome. :) Isn't that fun ? I believe it is going to be a serious competitor to Wikipedia.

There are also a few crypto related features. You can hash a given string using MD2, MD5 and SHA.

Here is a 13 minute demo, if you are interested.

Monday, April 13, 2009

How Mathematicians do it!

Real Analysts do it continuously.
Complex Analysts do it conformally and entirely.
Point Set Topologists do it openly, but compactly.
Combinatorists do it discretely.
Statisticians do it robustly.
Probabilists, we're not sure if they do it.
Logicians do it consistently.
Differential Topologists do it smoothly.
Algebraic Topologists do it manifold ways.
Algebraic Geometers scheme to do it without torsion.
Differential Geometers do it rigidly with torsion.
Numerical Analysts do it with arbitrary precision.
Applied Mathematicians do it everywhere.
Measure Theorists do it almost everywhere.
Ergodic Theorists do it dynamically.
Number Theorists do it in their prime.
Group Theorists simply do it.
Galois Theorists do it for love and honor.
Field Theorists do it with unity.
Set Theorists do it indeterminately.
Recursion Theorists do it undecidedly.
Proof Theorists do it correctly.
Model Theorists do it completely.
Constructivists do it directly.
Algebraists do it categorically.
Category Theorists do it polymorphously.
Linear Algebraists do it indiscriminately.
Search Theorists do it with infinitely divisible effort.
Operations Researchers maximize performance and minimize resources.
Software Analysts do it in RAM.
Software Engineers do it with user friendly I/O.
Pythagoras did it first.
Markov did it with chains.
Martingales do it without looking back.
Fermat did it, but can't prove it.
Norbert Wiener did it prodigiously.
Gauss did it better than anyone.

Cryptographers do it secretly! :) (by Vesko)

Originally from