Cryptography, PRNGs, Hash functions, Quasigroups

My papers, preprints and unpublished papers in: Cryptography, PRNGs, Hash functions, Quasigroups, Cryptanalysis, Error Correcting Codes Welcome to my crypto research page. As you can notice from the published and unpublished papers, I am working with quasigroup string transformations to develop different cryptographic and communication algorithms. Well, I am aware that quasigroups are not in the mainstream of cryptographic research, but as you can see from the developed algorithms, you can hardly find any other single mathematical paradigm by which you can develop: Cryptographic secure PRNGs, Block ciphers with variable block length, Stream Ciphers (both synchronous and self synchronizing), Cryptographically secure hash functions with variable output length, Cryptanalysis of block ciphers by quasigroups simulators, and lately: I have defined a new class of stream ciphers: Totally Asynchronous Stream Ciphers - TASCs. Q: What can be TASCs used for? A: For developing amazing Quasigroup Error Correcting Codes.
“Unbiased Random Sequences from Quasigroup String Transformations”, (S. Markovski, D. Gligoroski, L. Kocarev, to appear in the proceedings of Fast Software Encryption (FSE'05), Paris, France and Lecture Notes in Computer Science, Springer-Verlag, February, 2005.) This is an early version. Here are the SLIDES of my talk at FSE2005.	Abstract The need of true random number generators for many purposes (ranging from applications in cryptography and stochastic simulation, to search heuristics and game playing) is increasing every day. Many sources of randomness possess the property of stationarity. However, while a biased die may be a good source of entropy, many applications require input in the form of unbiased bits, rather than biased ones. In this paper, we present a new technique for simulating fair coin flips using a biased, stationary source of randomness. Moreover, the same technique can also be used to improve some of the properties of pseudo random number generators. In particular, an improved pseudo random number generator has almost unmeasurable period, uniform distribution of the letters, pairs of letters, triples of letters, and so on, and passes many statistical tests of randomness. Our algorithm for simulating fair coin flips using a biased, stationary source of randomness (or for improving the properties of pseudo random number generators) is designed by using quasigroup string transformations and its properties are mathematically provable. It is very flexible, the input/output strings can be of 2-bits letters, 4-bits letters, bytes, 2-bytes letters, and so on. It is of linear complexity and it needs less than 1Kb memory space in its 2-bits and 4-bits implementations, hence it is suitable for embedded systems as well.
“New Directions in Coding: From Statistical Physics to Quasigroup String Transformations”, (D. Gligoroski, S. Markovski, L. Kocarev, Accepted for 2004 International Symposium on Nonlinear Theory and its Applications, NOLTA2004, Fukuoka, Japan, November 29 - December 3, 2004.)	Abstract The last several years have witnessed major theoretical advances in communications and coding theory resulting in a new coding concept called codes on graphs. Codes on graphs, and specially their prime examples, low-density parity check (LDPC) codes and turbo codes is a research area of great current interest. In this paper we first overview the basic relation between codes on graph and spin systems, iterative decoding algorithms and nonlinear dynamical systems, and power-law networks and codes on graphs. Then, we show that there exists a class of codes, generated by quasigroup string transformations, which are almost random and outperform significantly Turbo and LDPC codes. For example, for $SNR=-0.5$~dB, rate $1/4$ and block length of only $864$ bits produce $BER=4.1\times 10^{-5}$.
“EdonZ – Totally Asynchronous Stream Cipher”, (D. Gligoroski, S. Markovski, L. Kocarev, 2004) – .	Abstract Stream ciphers are usually synchronous or self-synchronizing. In this paper we define a new type of Totally Asynchronous Stream Ciphers. Those ciphers have the property that if some error (intentional or non intentional) occur during the communication, the resulting decryption will be totally destroyed, and the rest of the communication stream will not self-synchronize.
“EdonX – synchronous stream cipher”, (D. Gligoroski, S. Markovski, L. Kocarev, 2004) – .	Abstract In this paper we describe a synchronous stream cipher called EdonX. The specialty of the design of EdonX is that it operates on 4-bit registers and use one fixed lookup table that is a Latin square of order 16 which can be stored in only 128 bytes. Together with the internal memory and the execution code of the algorithm, EdonX can be implemented in less then 1024 bytes.
“Generating Quasigroups of Huge Order”, (S. Markovski and D. Gligoroski) – The International Conference on Discrete Mathematics and Applications 7 (ICDMA7) June 17-22, 2004, Bansko, Bulgaria. We prepare the paper for conference proceedings. Here are the slides from the talk.	Abstract There are some applications of quasigroups in cryptography that need quasigroups of huge order (for example of order 2¹⁰²⁴). Clearly, the applications are possible only if the quasigroups are effectively defined. We propose several ways of effective definitions of quasigroups of huge order, and possibilities of their applications.
“Classification of Quasigroups by Random Walk on Torus”, (S. Markovski, D. Gligoroski, J. Markovski, 2004) – accepted for The IJCAR 2004 Workshop on Computer-Supported Mathematical Theory Development, Cork, Ireland, July 05, 2004 .	Abstract Quasigroups are algebraic structures closely related to Latin squares which have many different applications. There are several classifications of quasigroups based on their algebraic properties. In this paper we propose another classification based on the properties of strings obtained by specific quasigroup transformations. More precisely, in our research we identified some quasigroup transformations which can be applied to arbitrary strings to produce pseudo random sequences. We performed tests for randomness of the obtained pseudo-random sequences by random walks on torus. The randomness tests provided an empirical classification of quasigroups.
“Quasigroup cryptanalysis” (D. Gligoroski, 2004) – hmmm :-).	Abstract We design a quasigroup block cipher BabyQ, that is very easily breakable if one pair of known plaintext and ciphertext are given. Then, for any block cipher that we want to analyze, we produce a pair of (plaintext, ciphertext) and then try to find a quasigroup that simulate the work of the block cipher being investigated. The rate of simulation can vary from 1% to 30%. We show examples how to simulate weaker versions of DES, AES, and RSA with small number of bits.
“Stream cipher based on quasigroup string transformations in $Z_p^*$”, (D. Gligoroski, 2004), accepted to be published in Macedonian Academy of Science and Arts, annual Proceedings in Mathematical and Technical Sciences	Abstract In this paper we design a stream cipher that uses the algebraic structure of the multiplicative group Zp (where p is a big prime number used in ElGamal algorithm), by defining a quasigroup of order p−1 and by doing quasigroup string transformations. The cryptographical strength of the proposed stream cipher is based on the fact that breaking it would be at least as hard as solving systems of multivariate polynomial equations modulo big prime number p which is NP-hard problem and there are no known fast randomized or deterministic algorithms for solving it. Unlikely the speed of known ciphers that work in Zp for big prime numbers p, the speed of this stream cipher both in encryption and decryption phase is comparable with the fastest symmetric key stream ciphers.
"Generating highly nonlinear Boolean functions using a Genetic algorithm", (A.Dimovski, D.Gligoroski), in Proceedings of 1^st Balcan Conference in Informatics, November 2003, Thessaloniki, Greece.	Abstract In this paper a few algorithms are presented which assist with finding Boolean functions with good cryptographic properties, especially with high nonlinearity. First, a basic hill-climbing algorithm is described which improve the nonlinearity of a Boolean function. Then this algorithm is modified to incorporate a genetic algorithm. It is shown that these new search techniques are extremely powerful when compared to traditional random search techniques. Experimental results successfully prove this statement.
"Quasigroup transformations and their cryptographic potentials", slides from my talk at EIDMA Cryptography Working Group, Utrecht, October 10, 2003.
"Attacks On the Transposition Ciphers using Optimization Heuristics", (A.Dimovski, D.Gligoroski), in Proceedings of ICEST 2003, October 2003, Sofia, Bulgaria.	Abstract In this paper three optimization heuristics are presented which can be utilized in attacks on the transposition cipher. These heuristics are simulated annealing, genetic algorithm and tabu search. We will show that each of these heuristics provides effective automated techniques for the cryptanalysis of the ciphertext. The property which make this cipher vulnerable, is that it is not sophisticated enough to hide the inherent properties or statistics of the language of the plaintext.
"Attack On the Polyalphabetic Substitution Cipher Using a Parallel Genetic Algorithm", (A.Dimovski, D.Gligoroski), Technical report, Swiss-Macedonian cooperation trought SCOPES project, March 2003, Ohrid, Macedonia.	Abstract In this paper is presented an automated attack on the polyalphabetic substitution cipher. The property which make this cipher vulnerable, is that it is not sophisticated enough to hide the inherent properties or statistics of the language of the plaintext. The attack described here effectively reduces the complexity of a polyalphabetic substitution cipher attack to that of a monoalphabetic one, if there is a computer with B processing nodes, where B is the period of the polyalphabetic substitution cipher.
"Edon16 - library of reconfigurable quasigroup cryptographic primitives", (D. Gligoroski, 2003), unpublished, Source codes	Abstract In this paper we describe several programming modules which perform string transformations with quasigroups. The modules use one or two quasigroups of order 16, thus, taking only 128 bytes for storage per quasigroup or 256 working bytes per quasigroup. By using those modules as cryptographic primitives we have developed a block cipher, a stream cipher, a hash function with variable length of output that is strongly collision free and a pseudo random number generator. The cryptographic strength of the block cipher is examined by calculation of the XOR distribution tables for the first four rounds and we show that the distribution in the XOR tables converges to uniform, thus making attack with differential cryptanalysis inefficient to Edon16 block cipher. The strength of other algorithms is shown in some other research papers of us.
"Two infinite classes of cryptographic hash functions", (D. Gligoroski, S. Markovski, V. Bakeva, 2003), unpublished, Source codes	Abstract We offer two new definitions of two infinite classes of strongly collision free hash functions that we gave a name “Edon”–C and “Edon”– R. Beside the fact that “Edon” are infinite classes of hash functions, “Edon” hash functions have other “good” properties such as possibility to have variable length of output, and also their strongly collision free property can be mathematically and experimentally proved. The whole concept is based on the theory of quasigroups, and the cryptographic properties of string processing with quasigroups.
"On Infinite Class of Strongly Collision Resistant Hash Functions "EDON-F" with Variable Length of Output", (D. Gligoroski, S. Markovski, V. Bakeva) in Proceedings of 1st International Conference On Mathematics and Informatics for Industry, April, 2003, Thessaloniki, Greece	Abstract Two infinite classes of strongly collision free hash functions “Edon-C” and “Edon-R” are defined in [GMB 2003]. Here we propose one more hash function of similar ‘Edon’ type called “Edon-F”. This hash function is based on the theory of quasigroups and the cryptographic properties of quasigroup string processing, i.e. by similar idea as the others ‘Edon’ type of hush functions are designed. The “Edon-F” hash function is designed in such a way to be much faster than “Edon-C” and “Edon-R”, i.e. it is with linear complexity. The price for that is paid on the security level, in the sense that the length of the output message (the message digest) should be enough large.
Application SHREDDER.EXE (Free Win32 - DOS Cryptographic encoder/decoder - Stream cipher, for Pentium processors)
"Capacity of quasigroups for generating information" - invited talk at 2nd CiiT Conference of Informatics and Information Technology, Molika - Macedonia, December 2001 (SlideShow) See Mathematica 4.1 Notebook.
"QUASIGROUPS AND HASH FUNCTIONS", (S. Markovski, D. Gligoroski, and V. Bakeva), in Proceedings of the SIXTH INTERNATIONAL CONFERENCE on Discrete Mathematics and Applications 31.08.2001 - 02.09.2001, Bansko, Bulgaria, South-West University, Blagoevgrad, Bulgaria	Abstract In this paper we consider two quasigroup transformations QM1 : A^2m→A^2m and QM2 : A^m→A^2m, where A is the carrier of a quasigroup. Based on these transformations we show that different kinds of hash functions can be designed with suitable security.
"Random walk tests for pseudo-random number generators", (S. Markovski, D. Gligoroski, and V. Bakeva), in Mathematical Communications of Croatian Mathematical Society 6(2001) No.2, 135-143	Abstract It is well known that there are no perfectly well generators of random sequences of numbers, implying the need of testing the randomness of the sequences produced by such generators. There are many tests for measuring the uniformity of the random sequences, and here we propose a few new ones, designed by random walks. The experiments we have made show that our tests discover some discrepancies of the random sequences passing many other tests.
"Secure two-way on-line communication by using quasigroup enciphering with almost public key", (S. Markovski, D. Gligoroski and B. Stojcevska), in Novi Sad Journal of Mathematics, 30(2000) No. 2	Abstract Security is one of the issues in trend in networking domain. Obtaining a reliable method for providing secure communication is one of the basic tasks in this area. We implemented a solution by using a Quasigroup Enciphering method with almost public key as a new concept explained in detail in this paper. This Quasigroup Enciphering method is based on using quasigroups for deffning suitable encryption and decryption functions. The security properties of these functions make them suitable for this application. We developed a program for on-line chat using these functions implemented in C language.
"Quasigroup String Processing: Part 1", (S. Markovski, D. Gligoroski, and V. Bakeva) Maced. Acad. of Sci. and Arts, Sc. Math. Tech. Scien. XX 1-2(1999) 13-28	The paper where we mathematically defined quasigroup string transformations, and proved some important theorems.
"Using quasigroups for one-one secure encoding", S. Markovski, D.Gligoroski and S. Andova, Proceedings of LIRA '97 - Novi Sad Yugoslavia	Abstract In this article we apply a method for encrypting messages based on the properties of the quasigroups. According to the analysis given in the article the method is extremely secure. Beside that, the plain text and its cipher text are of the same length, and the encoding is of stream nature guarantying a very fast implementation. This was the first paper with quasigroup string transformations from 1997. However, the method that is described there is not at all secure. But we think that it has a value as a first in the series of papers where we use quasigroup string transformations.