Problems, solutions and experience of the first international student's Olympiad in cryptography.pdf Introduction The First Siberian Student's Olympiad in Cryptography with International participation - NSUCRYPTO'2014 was held on November 2014. There exist several school competitions in cryptography and information security, but this one is the first cryptographic Olympiad for students and professionals. The aim of the Olympiad was to involve students and young researchers in solving the curious and hard scientific problems of the modern cryptography. From the very beginning, the concept was not to stop on the training olympic tasks but to include unsolved research problems at the intersection of mathematics and cryptography. In this article, we give a detailed overview of the Olympiad. We start with the rules of participation and the description of rounds. Then in two big sections, we discuss 15 problems of the Olympiad and their solutions. Among them, there are both some amusing tasks based on historical ciphers and hard mathematical problems.We consider mathematical problems related to cipher constructing such as studying differential characteristics of S-boxes, S-box masking, determining relations between cyclic rotation and additions modulo 2 and 2n, constructing special linear subspaces in F^. Problems about the number of solutions of the equation F(x) + F(x + а) = 6 over the finite field F2n and APN functions are discussed. Some unsolved problems are proposed. The problem about the special watermarking ciphers is one of them. All problems were developed by the Program committee of the Olympiad. Solution check was also its duty. Organizers of the Olympiad are Novosibirsk State University, Sobolev Institute of Mathematics (Novosibirsk), Tomsk State University, Belarusian State University and University of Leuven (KU Leuven, Belgium). Programm committee was formed by G. Agibalov, S. Agievich, N. Kolomeec, S. Nikova, I. Pankratova, B. Preneel, V. Rijmen, and N. Tokareva. Local organizing committee from Novosibirsk consisted of A. Gorodilova, N. Kolomeec, G. Shushuev, V. Vitkup, D. Pokrasenko and S. Filiyzin. N. Tokareva was the general chair of the Olympiad. More than 450 participants from 12 countries were registered on the website of the Olympiad, www.nsucrypto.nsu.ru. Fifteen participants of the first round and eleven teams of the second round became winners and received prizes. The list of winners can be found in the last section of this paper. NSUCRYPTO will be a regular annual Olympiad held on November. In 2015, it starts on November, 15. We invite pupils, students and professionals to participate! 1. Organization and rules of the Olympiad Here we briefly formulate key points of the Olympiad. Its emblem is shown in Fig. 1. Rounds of the Olympiad. There were two independent Internet rounds. The First round (duration 4 hours 30 minutes) was individual and consisted of two sections: school and student's. It was held on November, 16. Theoretical problems in mathematics of cryptography were offered to participants. The second, team, round (duration 1 week; November, 17-24) was devoted to hard research and programming problems of cryptography. Everybody can participate! To become a participant of the Olympiad, it was necessary and sufficient to register on the website www.nsucrypto.nsu.ru. There were no restrictions on status and age of the participants. It means that senior pupils, students and all the others who are interested in cryptography were able to participate. Participants from any countries were welcome. During the registration, every participant had to choose his category: "senior pupil", "student" or "other / professional" and the section of the first round: "school" or "student's". The second round was common for all the participants. Language of the Olympiad. All problems were given in English. But solutions could be written in English or Russian. Format of the solutions. We accepted solutions in any electronic format (pdf, jpg, txt, rtf, docx, tex, etc). For example, a participant was able to write his solutions on a paper and send us a picture of it. Solutions should be written with all necessary details. Prizes. There were several groups of prizes: • for senior pupils - winners of the school section of the first round; • for students - winners of the student's section of the first round; • for participants in category "other / professional" - winners of the student's section of the first round; • for participants (for every category separately) - winners of the second round; • special prizes from the Programm committee for unsolved problems. Interesting moments. Sometimes we were asked: "The Olympiad is via Internet. Are not you afraid that participants will use everything: supercomputers, books, articles, websites on cryptography?" In fact, we only welcome such an active mobilization of all possible resources in purpose of solving the tasks! We hope that, in a future, such a brainstorm will help to solve really hard cryptographic problems. Fig. 1. 2. Problem structure of the Olympiad There were 15 problems on the Olympiad. Some of them were included in both rounds. Thus the school section of the first round consisted of 6 problems, whereas the student's section contained 8 problems. The first three problems were the same in each section (Tables 1,2). T a b l e 1 Problems of the first round (school section) N Problem title Maximal scores 1 A hidden message 4 2 A crypto room 4 3 The musical notation 4 4 Boolean cubes 4 5 A broken cipher machine 4 6 The Snowflake cipher 4 T a b l e 2 Problems of the first round (student's section) N Problem title Maximal scores 1 A hidden message 4 2 A crypto room 4 3 The musical notation 4 4 Linear subspaces 12 5 Number of solutions 8 6 A special parameter 10 7 S-box masking 8 8 Add-Rotate-Xor 10 The second round was composed of 11 problems (Table 3); it was common for all the participants. Three problems presented on the second round are unsolved (with declared special prizes from the Program Committee). T a b l e 3 Problems of the second round N Problem title Maximal scores 1 Watermarking cipher Special prize 2 APN permutation Special prize 3 The Snowflake cipher 4 4 Number of solutions 8 5 Super S-box Special prize 6 Boolean cubes 4 7 A special parameter 10 8 A pseudo-random generator 6 9 Add-Rotate-Xor 10 10 Linear subspaces 12 11 The musical notation 4 3. Problems 3.1. Problem "A hidden message" (4 scores) CrYPtogRapHY iS a ScIEnce Of "seCrET wriTinG". FOr aT Least Two THoUsANd yeaRS ThErE haVE bEeN peOPlE WHo WAnTeD to SEnd MESsaGes WHiCh coUlD oNly bEen rEAd bY tHe pEOPLe FoR whOm tHey were iNteNdeD. a loT oF different MEtHODs FoR coNcEalING mEssageS WerE invENtED stARTING WIth AnCIeNt cIPHerS lIKE "SkytaLE" and "ATBAsH" and ending wiTH MOdErn SymmeTRiC ANd PubliC-kEy enCRYptioN ALGOriTHmS SUch aS AeS and Rsa. the dEVELopMENT Of crYPtOgRaPHy cOntiNueS And NEVER sTopS! decrYPt THe mESsaGe tHat iS hIDdEn in thE teXT oF this TASk! tHE aLphabet FoR THE mEssAGE ConsisTs of ALl tWEnTy six enGliSh letTERS from "a" To "z" ANd Six puNCTuaTIoN MARkS " ", ".", ",", "!", "?", "'". 3.2. Problem "A crypto room" (4 scores) You are in a crypto room with a secret message in hands (Fig. 2). Decrypt it! Fig. 2. 3.3. Problem "The musical notation" (4 scores) Alice and Bob invented a new way for encrypting messages based on musical notations of melodies. They are not very good in musical notations, but they know the basic notes "do", "re", "mi", "fa", "sol", "la", "ti" and their places in the staff: To encrypt a message of length n in English alphabet, Alice chooses a melody consisting of n notes. She writes the message under the musical notation of the melody in such a way that each letter of the message corresponds to exactly one note's position in the musical notation. Then, for each note ("do", "re", ..., "ti"), Alice writes the row of the corresponding letters, takes a random integer number k for each i = 1,..., 7, and cyclically shifts letters in the i-th row by k positions to the right. Finally, Alice forms the ciphertext, writing letters of the shifted sets under the musical notation again. An example. Suppose that Alice wants to send the message HELLO. The row for "re" is (E L); for "mi" - (H L O). Alice takes random numbers 2 and 1 for "re" and "mi" respectively. After cyclical shifting to the right the first row by 2 positions and the second row by 1 position, she gets rows (E L) and (O H L). Hence, the ciphertext for the message is O E H L L. Decrypt the following ciphertext sent to Bob by Alice: ROLELISEOEEEHTOMVCPBDEFSON It is known that Alice used the musical notation below. 3.4. P r o b l e m " B o o l e a n c u b e s " ( 4 s c o r e s ) Alice has two cubes E1 and E2 of dimension 3 (Fig. 3). Their vertices have labels consisting of three integers; for example, (1,0,1) consists of integers 1, 0, 1. Consider an operation A that can be applied to a cube. The operation A contains three steps: Step 1. Take an arbitrary edge of the cube; Step 2. Take a number a which equals 1 or -1; Step 3. Add a to an arbitrary position of the first vertex of the chosen edge. Add a to an arbitrary position of the second vertex of the edge. Is it possible to get the cube E2 from the cube E1 by applying the operation A as many times as necessary? Give your arguments. The cube E1 The cube E2 Fig. 3. An example of applying the operation. Step 1. Take the edge ((1,0,0); (1,1,0)). Step 2. Let a = -1. Step 3. For the vertex (1, 0, 0), we choose the position 2 and, for the vertex (1,1, 0), we choose the position 1; after adding, the edge ((1, 0, 0); (1,1, 0)) becomes ((1,-1,0); (0,1,0)) (Fig. 4). Fig. 4. An illustration of the example 3.5. Problem "A broken cipher machine" (4 scores) Mary operates a cipher machine that encrypts messages like this: Step 1. It represents a message as a natural number n = abcdef...; Step 2. Then it adds all the digits in the number, Sn = a + b + c + d + e + f + Step 3. It inverts the order of digits in the number n and gets the number n' = ... fedcba; Step 4. As a result of the encryption, the machine prints the number m = n' + 2Sn. But now the cipher machine is broken: sometimes it works correctly, sometimes it prints a random number. After encryption of her secret number n, Mary found out that the result m is the power of two,that is, m = 2k for some integer k. Determine: was the encryption correct in this case? 3.6. Problem "The Snowflake cipher" (4 scores) Alice wants to encrypt some text using the Snowflake cipher. The encryption is described by the following algorithm: Step 1. Choose an arbitrary small triangle in the snowflake (see Fig. 5); Step 2. Put the first letter of your message into this triangle; Step 3. Write the next letter of the message (without spaces) into an arbitrary empty neighbouring triangle. Neighbouring means having a common edge. Repeat this step until the end of the message. Step 4. After inserting all the letters, write down the text from snowflake in horizontal order from top to bottom and from left to right. Determine what is the maximal possible length of a message that can be encrypted with the Snowflake cipher? Fig. 5. Fig.6. 3.7. Problem "A pseudo-random generator" (6 scores) Alice and Bob communicate in Russia through the Internet, using some protocol. In the process of communication, Bob sends random numbers to Alice. It is known that Bob's pseudo-random generator works in the following way: • it generates a binary sequence u0, u1, u2,... such that, for some secret c0,..., c15 G F2, Ui+16 = C15Ui+15 0 C14Ui+14 0 ... 0 Cou for all integer i ^ 0; • i-th random number r, i ^ 1, is calculated as = u16i + u16i+12 + u16i+2 22 + ... + u16i+15 215; • Bob initializes u0,u1 , ...,u15, using some integer number IV (initial value) from the interval (1, 216 - 1) in the same way, that is, IV = uo + U12 + U2 22 + ... + U15 215; • it is known that, as the value of IV, Bob uses the number t modulo 216, where t is the number of seconds from January 1, 1970, 00:00 (in Bob's time zone) to his current time (in his time zone too). Eve has intercepted the third and the fourth random numbers, namely r3 = 9 731 and r4 = 57 586. She lives in Novosibirsk and knows that Bob has initialized the generator on November 17, 2014, at about 12:05 UTC+6 up to several minutes. The number of seconds from January 1, 1970, 00:00 UTC+6 to November 17, 2014, 12:05 UTC+6 is equal to 1416 225 900. Help Eve to detect Bob's time zone. 3.8. Problem "Number of solutions" (8 scores) Let F256 be the finite field of characteristic 2 with 256 elements. Consider the function F : F256 ^ F256 such that F(x) = x254. Since x255 = 1 for all nonzero x G F256, we have F(x) = x-1 for all nonzero elements of F256. Further, we have F(0) = 0. Alice is going to use the function F as an S-box that maps 8 bits to 8 bits in a block cipher. But before doing this, she wants to find answers to the following questions. • How many solutions may the equation F (x + a) = F (x) + b (1) have for all different pairs of parameters a and b with nonzero values from F256? • How many solutions does the equation (1) have for the function F(x) = x2n-2 over the field F2n with an arbitrary n? Please, help Alice! An example. We want to encrypt the message: LOOK HOW IT WORKS. As a result, we can get the ciphertext: LHOWOOKITSKROW (Fig. 6). 3.9. Problem "S-box masking" (8 scores) To provide the security of a block cipher against the side channel attacks, some ideas of masking elements of the cipher are exploited. Here, we discuss masking S-boxes. Alice takes a bijective function S (S-box) that maps n bits to n bits. Bob claims that, for every such a function S, there exist two bijective S-boxes, say S' and S", mapping n bits to n bits in such a way that S(x) = S' (x) 0 S''(x) for all x e Fn Hence, Alice is able to mask an arbitrary bijective S-box by "dividing it into parts" for realization. But Alice wants to see the proof of this fact. Please help Bob to give the arguments. 3.10. Problem "A special parameter" (10 scores) In differential cryptanalysis of block ciphers, a special parameter P is used to measure the diffusion strength. In this problem, we study its properties. Let n, m be positive integers. Let a = (а\,..., am) be a vector with coordinates ai taken from the finite field F2n. Denote the number of nonzero coordinates ai, i = 1,..., m, by wt(a) and call this number the weight of a. The sum of a = (ab..., am) and b = (ab..., bm) in Fm is defined as a + b = (ai + bl,... ,am + bm). The special parameter P of a function ^ : Fm ^ Fm is defined to be e 1) 2) 3) P(

Скачать электронную версию публикации

1. Nyberg K. Differentially uniform mappings for cryptography. Eurocrypt'93, LNCS, 1994, vol. 765, no. 2, pp. 55-64.

2. Browning K. A., Dillon J.F., McQuistan M. T., and Wolfe A.J. An APN Permutation in Dimension Six. Post-proceedings of the 9-th Intern. Conf. on Finite Fields and Their Applications Fq'09, Contemporary Math., AMS, 2010, vol.518, pp. 33-42.

3. Daemen J. and Rijmen V. The Design of Rijndael: AES - The Advanced Encryption Standard. Springer, 2002. 238 p.

4. Qu L., Fu S., Dai Q., and Li C. When a Boolean Function can be Expressed as the Sum of two Bent Functions. Cryptology ePrint Archive, 2014/048.

5. Zieschang T. Combinatorial Properties of Basic Encryption Operations. Eurocrypt'97, LNCS, 1997, vol. 1233, pp. 14-26.

6. Agibalov G. P. Shifry s vodyanymi znakami [Watermarking Ciphers]. Prikladnaya diskretnaya matematika. Prilozhenie, 2015, no. 8, pp. 54-59. (in Russian)

7. http://writeupsd.blogspot.ru/2014/11/apn-permutation-finder.html.