Watch your constants: malicious Streebog
2015; Institution of Engineering and Technology; Volume: 9; Issue: 6 Linguagem: Inglês
10.1049/iet-ifs.2014.0540
ISSN1751-8717
Autores Tópico(s)Coding theory and cryptography
ResumoIET Information SecurityVolume 9, Issue 6 p. 328-333 Research ArticleFree Access Watch your constants: malicious Streebog Riham AlTawy, Riham AlTawy Concordia Institute for Information Systems Engineering, Concordia University, Montréal, QC, CanadaSearch for more papers by this authorAmr M. Youssef, Corresponding Author Amr M. Youssef youssef@ciise.concordia.ca Concordia Institute for Information Systems Engineering, Concordia University, Montréal, QC, CanadaSearch for more papers by this author Riham AlTawy, Riham AlTawy Concordia Institute for Information Systems Engineering, Concordia University, Montréal, QC, CanadaSearch for more papers by this authorAmr M. Youssef, Corresponding Author Amr M. Youssef youssef@ciise.concordia.ca Concordia Institute for Information Systems Engineering, Concordia University, Montréal, QC, CanadaSearch for more papers by this author First published: 01 November 2015 https://doi.org/10.1049/iet-ifs.2014.0540Citations: 4AboutSectionsPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Share a linkShare onFacebookTwitterLinkedInRedditWechat Abstract In August 2012, the Streebog hash function was selected as the new Russian cryptographic hash standard (GOST R 34.11-2012). In this study, the authors investigate the new standard in the context of malicious hashing and present a practical collision for a malicious version of the full hash function. In particular, they apply the rebound attack to find three solutions for three different differential paths for four rounds. Then, using the freedom of the round constants they connect them to obtain a collision for the 12 rounds of the compression function. Additionally, and because of the simple processing of the counter, they bypass the barrier of the checksum finalisation step and transfer the compression function collision to the hash function output with no additional cost. The presented attack has a practical complexity and is verified by an example. Although the results of this study may not have a direct impact on the security of the current Streebog hash function, it presents an urge for the designers to publish the origin of the used parameters and the rational behind their choices in order for this function to gain enough confidence and widespread adoption by the security community. 1 Introduction Research on malicious cryptographic primitives has always been thought of as the work of intelligence agencies. The belief that governmental spy agencies work hard to incorporate backdoors in their primitives, which enable the efficient manipulation of certain security properties, has always been lurking in the cryptographic community. This belief was further strengthened last year after Edward Snowden exposed the existence of the NSA's Bullrun decryption project [1]. Leaked documents have shown that the National Security Agency (NSA) has deliberately inserted a backdoor in the standardised pseudorandom number generator Dual_EC_DRBG [2]. This backdoor provides the knowledge of the internal state of the generator and accordingly its subsequent outputs. Additionally, it is also speculated that NSA paid RSA Security $10 million in a secret deal to use Dual_EC_DRBG as the default pseudorandom number generator in the RSA BSAFE cryptography library [2]. With Dual_EC_DRBG being recommended by National Institute for Standards and Technology (NIST) at that time, these revelations have raised suspicions with respect to the NIST standards being manipulated by the NSA, particularly, after voices from the cryptographic community began suggesting the possibility of the NSA compromising the NIST's recommended elliptic curve constants [3]. Only few papers have been peer reviewed in public venues in the area of malicious cryptography. Young and Yung [4] were among the first to address the topic of malicious cryptography through their cryptovirology project. Later Rijmen and Preneel [5] proposed malicious versions of CAST and LOKI by hiding linear relations in the used Sboxes. Work related to malicious ciphers, implementations and pseudorandom generators includes [6-10]. Although most of the previous work focused on ciphers, just recently the concept of malicious hashing have been introduced in [11, 12]. Specifically, Albertini et al. proposed a malicious version of SHA-1 by which collisions can be produced in an efficient way. They have used the freedom of the round constants to satisfy a given differential path and generate one block message collisions. Streebog was proposed in 2010 [13]. It has an output length of 512/256 bit. The compression function employs a 12-round Advanced Encryption Standard (AES)-like cipher with 8 × 8 byte internal state. The compression function operates in Miyaguchi–Preneel mode and is plugged in a modified Merkle–Damgård domain extender with a modular checksum finalisation step [14]. Streebog officially replaces the previous standard GOST R 34.11-94 [refer to a set of technical standards maintained by the Euro-Asian Council for Standardization, Metrology and Certification (EASC), a regional standards organization operating under the auspices of the Commonwealth of Independent States (CIS).] which has been theoretically broken in [15, 16]. The new GOST is standardised by internet engineering task force (IETF) as request for comments (RFC) 6896 [17] as well. Unlike the specifications of other hash functions, the reference of the new GOST standard [14] gives no information about how or why the parameters of the function (e.g. round constants, matrix constants and the number of rounds) have been chosen. This fact opens the door to our analysis, which makes use of exactly two parameters: the heavily random looking independent constants and the number of rounds, to present practical collisions for a malicious version of Streebog. Early works related to the cryptanalysis of Streebog have been introduced in [18-21] and in [22-24], where practical semi-free-start collision and near collision examples for reduced round versions have been presented in only [18, 24]. In this paper, we investigate a malicious version of Streebog. We exploit the randomness of the independent round constants and take advantage of the number of rounds of the compression function to efficiently generate collisions for the compression function. More precisely, we first employ the rebound attack technique proposed in [24] to find three pairs of messages and keys that satisfy a specific three 4-round differential paths independently. In the sequel, we use the freedom of five out of the twelve round constants to connect the three obtained solutions and obtain collisions for the 12 round compression function. Finally, we tune the last constant of the compression function to adjust its output after the feedforward to cancel the effect of the counter, Ni−1, addition of the following compression function call, and append another identical colliding message pair. Hence, we generate a two block messages 22 multi-collision structure where two of them have the same modular sum, and thus a collision at the output of the hash function. Although the previous work [11] stated that compression function collisions are not sufficient to generate hash function collision in constructions that incorporate checksum, our results prove that this is not the case for Streebog. Table 1 provides the six new constants used in our malicious version of Streebog. Table 2 shows the other six unchanged (original) constants. An example of the two block message collision along with its corresponding digest is provided in Table 3. Table 1. Six new constants C1 C4 C5 3b 7b 5d ca f1 e4 23 2f 7b 51 2e eb f5 f6 ab f4 9b b1 e8 b9 00 2f 6d 75 de dd 27 78 d6 9b fe 93 42 52 38 55 1b 14 c2 9d 96 d7 e3 12 a2 5c 66 9c f7 9f 94 dd 27 02 f3 a2 6e 5b 20 23 c9 b9 8f 3d 7e aa 0e bf dd 0e 04 88 4b 8e ad 06 8d 6f 3a fd a5 cc 0b e3 78 9b 9d 52 f7 30 67 e2 8c b5 37 1e fa da e2 5c b1 2a 0f 3a bc 30 cc de 99 39 07 69 6b 1c 1b 28 09 6d 0d 78 0f 7d 0d 18 ba f6 0c e9 cb 69 60 cf 89 c9 20 cd 4c fa 57 06 9e da f6 4f 27 b7 42 a3 7d 68 cd 64 e7 e6 7c 81 ef d7 97 6e 1d 20 22 e9 ce 7e 54 3f 5b 41 e8 61 e2 cb 9d a6 71 ac 16 c5 bf cc b9 c1 35 0c 56 b4 d8 a5 01 b7 C8 C9 C12 02 e5 04 18 6c 11 2d 01 f9 53 2e c1 78 84 d2 6e a3 23 32 b5 81 5e 1b 85 02 f1 f2 49 5d d0 aa 7b 17 ae c9 5a a4 44 4c 8d f4 67 4d bc c3 77 fd 7f 98 4c e1 b8 08 fd 0f 60 21 8b 63 a4 c1 2a 32 b8 f8 a1 db b5 e3 69 99 41 46 79 75 f7 37 5d a1 8c 41 2c 9a d0 71 20 55 30 eb 15 09 84 de 8d 22 ea 3c b5 83 ac 90 27 38 30 fb 71 99 26 59 a8 6f 4f 9d e6 44 d5 fd 40 7b 5d 25 af e8 05 d1 bd e3 34 8e 37 7a c5 06 ad 7f 93 d1 32 45 08 e9 3d 3f 51 ea eb 50 bf be 39 32 9a 50 0b be 70 04 4b 9d 5c 2a 36 ae cc 53 97 0f fc 61 1a 1a 22 e1 0d ff 58 d7 aa 2c 27 6e cd 41 01 41 a7 84 f3 44 91 24 3e Table 2. Six unchanged (original) constants C2 C3 C6 6f a3 b5 8a a9 9d 2f 1a f5 74 dc ac 2b ce 2f c7 ae 4f ae ae 1d 3a d3 d9 4f e3 9d 46 0f 70 b5 d7 0a 39 fc 28 6a 3d 84 35 6f a4 c3 3b 7a 30 39 c0 f3 fe ea 72 0a 23 2b 98 06 f1 5e 5f 52 9c 1f 8b 2d 66 c4 f9 51 42 a4 6c 61 d5 5e 0f 16 b5 01 31 f2 ea 75 14 b1 29 7b 7b 18 7f 9a b4 9a f0 8e c6 9a b5 17 6b 12 d6 99 58 d3 e2 0f e4 90 35 9e b1 cf fa a6 b7 1c 9a b7 b4 5c b5 61 c2 db 0a a7 ca c1 c9 3a 37 60 62 db 09 0a f2 1f 66 c2 be c6 b6 55 dd a2 1b d7 cb cd 56 c2 b6 f4 43 86 7a db 31 bf 71 c5 72 36 90 4f 35 e6 79 04 70 21 b1 9b b7 99 1e 96 f5 0a ba 0a b2 fa 68 40 7a 46 64 7d 6e C7 C10 C11 f4 c7 0e 16 ee aa c5 ec ab be de a6 80 05 6f 52 7b cd 9e d0 ef c8 89 fb 51 ac 86 fe bf 24 09 54 38 2a e5 48 b2 e4 f3 f3 30 02 c6 cd 63 5a fe 94 39 9e c6 c7 e6 bf 87 c9 89 41 e7 1c ff 8a 78 db d8 fa 6b bb eb ab 07 61 d3 47 3e 33 19 7a 93 c9 1f ff e1 8a 1b 33 61 03 20 01 80 21 14 84 66 79 09 92 ab c5 2d 82 2c 37 9f e7 67 02 af 69 33 4b 8a 1d 71 ef ea 48 b9 ca 06 47 69 83 28 4a 05 04 7a 1e 6c 30 3b 76 52 f4 ef ba cd 1d 7d 47 6e 98 35 17 45 4c a2 3c 4a f3 36 98 fa d1 15 3b b6 c3 de a2 59 4a c0 6f d8 5d 88 86 56 4d 3a 14 d4 93 74 b4 c7 fb 98 45 9c ed 6b ca a4 cd 81 f3 2d 1b Table 3. Example of a 2-block message collision for the malicious Streebog hash function m m ′ Δm d2 d7 5d 81 b1 63 d8 cc d2 d7 5d 81 b1 63 d8 cc 00 00 00 00 00 00 00 00 63 16 bb de 0e 61 85 d6 63 16 bb de 0e 61 85 d6 00 00 00 00 00 00 00 00 97 89 a3 e6 55 cf 46 e7 97 89 a3 e6 55 cf 46 e7 00 00 00 00 00 00 00 00 37 de 22 19 54 d6 01 95 37 de 22 bb 54 d6 01 95 00 00 00 a2 00 00 00 00 13 44 b8 4d a3 4d 36 4c 13 44 b8 4d a3 4d 36 4c 00 00 00 00 00 00 00 00 a3 50 36 27 f3 51 7f ee a3 50 36 27 f3 51 7f ee 00 00 00 00 00 00 00 00 58 23 1d 88 80 1b 09 62 58 23 1d 88 80 1b 09 62 00 00 00 00 00 00 00 00 08 9d bc 4d aa a1 73 2a 08 9d bc 4d aa a1 73 2a 00 00 00 00 00 00 00 00 94e19a2ad9252ca78d14600c20488ad66de12c72ab3aac19f7bb9e277abe973aea22f1c3fa3be180c6dd212f4b19eefed80fb114c44dfb39ffdb2cfad24c6275 The rest of this paper is organised as follows. In the next section, a description of the Streebog hash function along with the notation used throughout this paper is provided. A brief overview of the rebound attack is given in Section 3. Afterwards, in Section 4, we provide a detailed description of the used approach, the malicious compression function attack and its corresponding complexity. In Section 5, we show how collisions of the malicious hash function are generated using the attack presented in Section 4. Finally, this paper is concluded and a short discussion is provided in Section 6. 2 Description of Streebog Streebog outputs a 512 or 256 bit hash value, where half the last state is truncated when adopting the 256 bit output. The standard specifies two different initialisation vector (IVs) to be used with the two output lengths. The function can process messages of length up to 2512 − 1. The compression function iterates over 12 rounds of an AES-like cipher with an 8 × 8 byte internal state and a final round of key mixing. The compression function operates in MP mode and is plugged in Merkle–Damgård domain extender with a finalisation step. The input message M is padded into a multiple of 512 bits by appending one followed by zeros. The message length for MD-strengthening is further included as an extra separate block, followed by a block of a checksum evaluated by the modulo 2512 addition of all message blocks as a finalisation step. More precisely, let n = ⌊(|M |/512)⌋ and the input message , where |M | is the length of M and x is an incomplete or an empty block. The message is padded as follows: let , then the padded message . Let . The compression function gN is fed with three inputs: the chaining value hi−1, a message block mi−1 and the counter of bits hashed so far Ni−1 = 512 × (i − 1). (see Fig. 1). Let hi be a 512 bit chaining variable. The first state is loaded with the initial value IV and assigned to h0. The hash value of M is computed as follows where H (M) is the hash value of M and g0 is gN with Ni−1 = 0. As depicted in Fig. 1, the compression function gN consists of: KN: A non-linear whitening round of the chaining value. It takes a 512 bit chaining variable hi−1 and a counter of the bits hashed so far Ni−1 and outputs a 512 bit key K. E: An AES-based cipher that iterates over the message for 12 rounds in addition to a finalisation key mixing round. The cipher E takes a 512 bit key K and a 512 bit message block m as a plaintext. As shown in Fig. 2, it consists of two similar parallel flows for the state update and the key scheduling. Fig. 1Open in figure viewerPowerPoint Streebog's compression function gN Fig. 2Open in figure viewerPowerPoint Internal block cipher (E) Both KN and E operate on an 8 × 8 byte key state K. E updates an additional 8 × 8 byte message state M. In one round, a given state is updated by the following sequence of transformations: AddKey (X): XOR with either a round key, a constant or the counter of bits hashed so far (Ni−1). SubBytes (S): A non-linear byte bijective mapping. Transposition (P): Byte permutation. Linear transformation (L): Row multiplication by an maximum distance separable (MDS) matrix in GF(28). Initially, state K is loaded with the chaining value hi−1 and updated by KN as follows Now K contains the key K1 to be used by the cipher E. The message state M is initially loaded with the message block m and E (K1, m) runs the key scheduling function on state K to generate 12 round keys, K2, K3, …, K13, as follows where Cj−1 is the constant used at round j − 1. The state M is updated as follows The final round output is given by E (K1, m) = M13 ⊕ K13. The output of gN in the MP mode is E (KN (hi−1, Ni−1), mi−1) ⊕ mi−1 ⊕ hi−1 as shown in Fig. 1. For further details, the reader is referred to [14]. 2.1 Notation Let M and K be (8 × 8) byte states denoting the message and key state, respectively. The following notation is used throughout this paper: Mj: The message state at the beginning of round j. : The message state after the U transformation at round j, where U ∈ X, S, P, L. Mj [r, c]: A byte at row r and column c of state Mj. Mj [row r]: Eight bytes located at row r of Mj state. Mj [col c]: Eight bytes located at column c of Mj state. Same notation applies to K. 3 Rebound attack The rebound attack was proposed by Mendel et al. [25] for the cryptanalysis of AES-based hash functions. It is a differential attack that follows the inside-out or start-from-the-middle approach which is used in the boomerang attack [26]. The attack is composed of three phases, one inbound and two outbounds. The compression function, internal block cipher or permutation of the hash function is divided into three parts. If C is a block cipher, then C is expressed as C = Cfw ○ Cin ○ Cbw. The middle part is the inbound phase and the forward and backward parts are the two outbound phases. In the inbound phase, a low probability XOR differential path is used and all possible degrees of freedom are used to satisfy the inbound path. In the two outbound phases, high probability truncated paths [27] are used. In other words, one starts from the middle satisfying Cin, then hash forward and backward to satisfy Cfw and Cbw probabilistically. For an 8 × 8 byte state, the basic rebound attack finds two states satisfying an inbound phase over two rounds . The main idea of the attack is to pick random differences at each of the two outer states. Then propagate both backward and forward until the output and input of the Sbox, respectively. Using the Sbox differential distribution table (DDT), we find values that satisfy input and output differentials. This process is further illustrated in Fig. 3. The last step of the attack is called the Sbox matching phase and its complexity depends on the Sbox DDT. If the probability of differentials that have solutions is p, then the matching probability is given by p8. Fig. 3Open in figure viewerPowerPoint Rebound attack The literature related to the rebound attack includes Mendel et al. 's first proposal on the International Organization for Standardization (ISO) standard Whirlpool and the SHA-3 finalist Grøstl [25, 28]. In particular, Mendel et al. presented a 4.5-round collision, 5.5-round semi-free-start collision and 7.5-round near collision attacks on the Whirlpool compression function. As for Grøstl-256, a 6-round semi-free-start collision is given. Subsequently, rebound attacks have been applied to other AES-based hash functions such as LANE [29], JH [30], Echo [31], Streebog [18] and Grøstl [32]. Various tweaks have been applied to the basic rebound attack in order to construct differential paths that cover more rounds such as merging multiple inbounds [33], super Sbox cryptanalysis [34], extended 5-round inbound [33] and linearised match-in-the-middle and start-from-the-middle techniques [35]. Finally, Kölbl and Rechberger [24] presented a practical method to find semi-free-start collision for a 4-round AES-based compression function. More precisely, they have proposed a way to first find a specific differential path for transition, and then use the freedom in the key to find two messages that follow the given path. They have implemented their approach on Streebog and presented a semi-free-start collision for the 4-round reduced compression function. In what follows, we show how we use this approach to generate collisions for a malicious version of Streebog compression function. 4 Malicious compression function collision In this section, we give the details of our malicious adaptation of the streebog compression function that allows us to efficiently construct collisions for the 12 round compression function. Our approach makes use of the heavily random looking independent round constants and the 12 rounds of the compression function. In fact, the specific number of rounds (12) used in Streebog enables us to find three independent solutions for the commonly known 1→8→64→8→1 four round differential path and then, by changing five constants, we can successfully connect them and generate a collision. Our attack starts by finding the first solution which is a pair of messages and a key that follow the given differential path shown in Fig. 4. In doing so, we employ the approach proposed in [24] which is composed of two procedures and is briefly described as follows: (a) Building the differential characteristic: In this procedure, one determines the exact differential transitions of the above truncated differential trail as follows: (1) Choose a random difference at and propagate it backward until the full active state . (2) For each byte difference in , save a set of all possible input differences. (3) Create a table TL of all possible 255 byte difference values d3 (candidates for ) and their corresponding 8 byte difference values L (d3) (candidates for ). These values are the result of applying the linear transformation L to a difference at column 3. (4) For each row of , check if there is a possible match with the rows in TL. (5) To achieve the transition from one active byte in to eight active bytes in , steps 2 and 4 must be repeated for only one row between states . Fig. 4Open in figure viewerPowerPoint First truncated differential path According to the Streebog Sbox differential distribution properties, finding the differential characteristic has a complexity of [24]. (b) Finding a solution for the differential path: Once we have found a characteristic, we now need to find a message pair that follows it. This can be done by performing the following steps: (1) Set the message state at with a solution that satisfies the full active state differentials from the above procedure. (2) Use K3 [col 3] to satisfy the solutions of the Sbox differentials at . Moreover, use K3 [row 3] to satisfy the solutions of the Sbox differentials at . Since there is 1 byte, K3 [3, 3], shared between the two solutions, one needs to repeat the above procedure 28 times. For more details on the specifics of the used technique, the reader is referred to [24]. 4.1 Our proposed technique for finding collisions of the malicious compression function To this end, we have found a solution to the first differential path with a key input different from that is produced by the standard IV. This solution gives us a specific input and output differences at M1 [3, 3] and , respectively. In the sequel, we restart the above two procedures to search for the second differential characteristic and its solution such that this second search covers rounds five to eight and has an input difference at M5 [3, 3] equals to the output difference of the first path. Since we restrict the input difference of the second path to a specific value, the complexity of the second procedure of our search is increased by a factor of 28. However, the overall search complexity is still dominated by the first procedure which is about 220. Finally, we search for the third and last differential path and its solution which covers rounds 9–12. For this path, we have to restrict its input difference at M9 [3, 3] to be equal at and its output difference at to be equal at M1 [3, 3], so that the latter cancels out after the feedforward. Fig. 5 depicts an overview of our technique. Similarly, coloured input and output differences in the states which result from the three solutions are chosen to be equal. The constants that are evaluated to connect the three solutions and to obtain the desired IV and compression function output values are also shown in the figure. Fig. 5Open in figure viewerPowerPoint Our approach for finding collision for the full round compression function 4.2 Connecting the three solutions Now that we have the three solutions, we can start tuning specific round constants to connect them. We first work on the first solution's key output K1, which is different than that generated by the standard IV. To solve this problem, we fix the new . By doing this, we guarantee that the resulting new key satisfies the first differential path. Thus, the new colliding messages are and . To connect the first and second solutions, we have to change K5. However, altering K5 affects both K4 and K6, which are restricted by the solutions of the first and second paths, respectively. To cancel the propagation of alteration to the latter two round keys, we compute the new two constants C5 and C4 as follows where and K4 are solutions of the first path, whereas and are solutions of the second path. To connect the second and third paths, we perform the same procedure to compute the new C8 and C9. Having all the new five constants in place, Table 3, gives an example of a colliding message pair which has the same compression function output using IV = 0 and Ni−1 = 0. 5 Collision attack on the full malicious Streebog Although the previous work [11] speculated that collisions of the compression function cannot be reflected at the output of the hash function when employing a checksum finalisation step, in this section, we show how to turn the previous compression function collision to a hash function collision. On top of the modular checksum finalisation step, Streebog incorporates a counter Ni−1 with each compression function call. However, Ni−1 is mixed with the chaining value with a simple XOR operation. It should be noted that once the constants of the compression function are fixed to some values, they remain the same for all successive executions of the compression function. Accordingly, it is infeasible to search for a different collision with the same constants. Our approach is to replicate the first collision two times, thus creating a 2-block multi-collision structure with the same h2 input to the padding call gN (h2, mp, N2) as depicted in Fig. 6. By doing this, it is guaranteed that four messages collide at h2, and only two of them collide at the output of the hash function. Namely, those two that have the same modular checksum which are and . However, using the same collision twice implies that the second collision should have a chaining input h1 equal to that of the first collision which is IV = 0. For this, we compute a new C12 to enforce the output of the first collision h1 to be 512, which is equal to the value of N1 used in the following compression function call. The desired value of C12 is evaluated as follows To this end, at the input of the second compression function call h1 cancels the effect of N1 and the second colliding message pair has a chaining input internal state equal to that of the IV which is used at the first call. Fig. 6Open in figure viewerPowerPoint Malicious Streebog collision 6 Conclusion and discussion In this paper, we have investigated a malicious version of Streebog. We took advantage of the heavily random looking constants and the number of rounds of the compression function to present a 2-block message pair with the same digest. Our approach first searches for three solutions for three different 4-round differential paths and use the freedom of five constants to connect them to produce a compression function collision. Finally, we employed the freedom in the last constant used in the round key generation to cancel the effect of the counter used in the second compression function call. Hence, we are able to append a second similar message pair, thus creating a 22 multi-collision structure where only two of them have the same modular checksum and accordingly the same digest. It should be noted that these results has no impact on the security of the original standard. Additionally, this new set of constants does not provide collision for GOST-256 as it uses a different IV. However, they are interesting in the light of the absence of the source of the used parameters of the standard. Our results also show one of the first examples of compression function collisions being sufficient to generate hash function collisions. It is interesting to mention that because of the versatility of the used differential path where the 1 byte difference can virtually be anywhere in the state, we obtain the freedom to satisfy the magic number as well as other constraints that are needed to produce meaningful collisions for some specific file formats (compare Section 4 in [12]). In other words, as the difference is sparse and the complexity of the attack is upper bounded by 220, if one requires to find two messages that start with a specific byte value, then we need to repeat the first path search 256 times which raises the time complexity of the attack by a factor of 28. As a future direction, one may investigate the applicability of the attack if the number of rounds is not a multiple of four. Moreover, one might try searching for a malicious adaptation that holds for the two versions of the hash function simultaneously. Finally, we see that this paper provides an incentive for the designers of Streebog to publish the origin of the used parameters and the rational behind their choices. 7 Acknowledgments This work is supported by the Natural Sciences and Engineering Research Council of Canada under grant N00930. The authors thank the anonymous reviewers for their comments that helped improve the presentation of this paper. 8 References 1 Wikipedia: ' Bullrun (decryption program) — Wikipedia, the free encyclopedia', 2014. Online; accessed 22 October 2014 2 Wikipedia: ' Dual_EC_DRBG — Wikipedia, the free encyclopedia', 2014. Online; accessed 22 October 2014 3Schneier, B.: ' The NSA is breaking most encryption on the internet'. Available at https://www.schneier.com/blog/archives/2013/09/the_nsa_is_brea.html. Online; published September 2013 4Young, A., Yung, M.: ' Malicious cryptography: exposing cryptovirology' ( John Wiley & Sons, Indianapolis, Indiana, 2004) 5Rijmen, V., Preneel, B.: 'A family of trapdoor ciphers'. FSE 1997 (LNCS, 1267), pp. 139– 148 6Biham, E., Carmeli, Y., Shamir, A.: 'Bug attacks'. CRYPTO, 2008 (LNCS, 5157), pp. 221– 240 7Patarin, J., Goubin, L.: 'Trapdoor one-way permutations and multivariate polynomials'. ICICS, 1997 (LNCS, 1334), pp. 356– 368 8Filiol, E.: 'Malicious cryptography techniques for unreversable (malicious or not) binaries'. CoRR, 2010, vol. abs/1009.4000 9Paterson, K.G.: 'Imprimitive permutation groups and trapdoors in iterated block ciphers'. FSE, 1999 (LNCS, 1636), pp. 201– 214 10Aumasson, J.-P.: 'Cryptographic backdooring', 2014. Available at https://www.131002.net/data/talks/backdooring_nsc14.pdf, Online; accessed 25 January 2015 11Aumasson, J.-P.: ' Eve's SHA3 candidate: malicious hashing'. Online article, 2011. Available at https://www.131002.net/data/papers/Aum11a.pdf 12Albertini, A., Aumasson, J.-P., Eichlseder, M., Mendel, F., Schläffer, M.: 'Malicious hashing: Eve's variant of SHA-1'. SAC, 2014 (LNCS, 8781), pp. 1– 19 13Matyukhin, D., Rudskoy, V., Shishkin, V.: 'A perspective hashing algorithm'. RusCrypto, 2010. (In Russian) 14 'The National Hash Standard of the Russian Federation GOST R 34.11-2012',. Russian Federal Agency on Technical Regulation and Metrology report, 2012. Available at http://www.tc26.ru/en/standard/gost/GOST_R_34_11-2012_eng.pdf 15Mendel, F., Pramstaller, N., Rechberger, C., Kontak, M., Szmidt, J.: 'Cryptanalysis of the GOST hash function'. CRYPTO, 2008 (LNCS, 5157), pp. 162– 178 16Mendel, F., Pramstaller, N., Rechberger, C.: 'A (second) preimage attack on the GOST hash function'. FSE, 2008 (LNCS, 5086), pp. 224– 234 17 IETF: ' GOST R 34.11-2012: Hash Function', 2013. (RFC6896) 18AlTawy, R., Kircanski, A., Youssef, A.M.: 'Rebound attacks on Stribog'. ICISC, 2013 (LNCS, 8565), pp. 175– 188 19AlTawy, R., Youssef, A.M.: 'Integral distinguishers for reduced-round Stribog', Inform. Process. Lett., 2014, 114, (8), pp. 426– 431 (https://doi.org/10.1016/j.ipl.2014.03.005) 20AlTawy, R., Youssef, A.M.: 'Preimage attacks on reduced-round Stribog'. AFRICACRYPT, 2014 (LNCS, 8469), pp. 109– 125 21Ma, B., Li, B., Hao, R., Li, X.: 'Improved cryptanalysis on reduced-round GOST and Whirlpool hash function'. Applied Cryptography and Network Security, 2014 (LNCS, 8479), pp. 289– 307 22Kazymyrov, O., Kazymyrova, V.: 'Algebraic aspects of the Russian hash standard GOST R 34.11-2012'. CTCrypt, 2013, pp. 160– 176. Available at http://www.eprint.iacr.org/2013/556 23Guo, J., Jean, J., Leurent, G., Peyrin, T., Wang, L.: 'The usage of counter revisited: Second-preimage attack on new Russian standardized hash function'. SAC, 2014 (LNCS, 8781), pp. 195– 211 24Kölbl, S., Rechberger, C.: 'Practical attacks on AES-like cryptographic hash functions'. Latincrypt, 2014 (LNCS) 25Mendel, F., Rechberger, C., Schläffer, M., Thomsen, S.S.: 'The rebound attack: cryptanalysis of reduced Whirlpool and Grøstl'. FSE, 2009 (LNCS, 5665), pp. 260– 276 26Wagner, D.: 'The boomerang attack'. FSE, 1999 (LNCS, 1636), pp. 156– 170 27Knudsen, L.R.: 'Truncated and higher order differentials'. FSE, 1995 (LNCS, 1008), pp. 196– 211 28Mendel, F., Rechberger, C., Schläffer, M., Thomsen, S.S.: 'Rebound attacks on the reduced Grøstl hash function'. CT-RSA, 2010 (LNCS, 5985), pp. 350– 365 29Matusiewicz, K., Naya-Plasencia, M., Nikolić, I., Sasaki, Y., Schläffer, M.: 'Rebound attack on the full lane compression function'. ASIACRYPT, 2009 (LNCS, 5912), pp. 106– 125 30Rijmen, V., Toz, D., Varici, K.: 'Rebound attack on reduced-round versions of JH'. FSE, 2010 (LNCS, 6147), pp. 286– 303 31Jean, J., Fouque, P.-A.: 'Practical near-collisions and collisions on round-reduced ECHO-256 compression function'. FSE, 2011 (LNCS, 6733), pp. 107– 127 32Mendel, F., Rijmen, V., Schläffer, M.: 'Collision attack on 5 rounds of Grøstl'. FSE, 2014 (LNCS) 33Lamberger, M., Mendel, F., Rechberger, C., Rijmen, V., Schläffer, M.: 'Rebound distinguishers: Results on the full Whirlpool compression function'. ASIACRYPT, 2009 (LNCS, 5912), pp. 126– 143 34Gilbert, H., Peyrin, T.: 'Super-Sbox cryptanalysis: improved attacks for AES-like permutations'. FSE, 2010 (LNCS, 6147), pp. 365– 383 35Mendel, F., Peyrin, T., Rechberger, C., Schläffer, M.: 'Improved cryptanalysis of the reduced Grøstl compression function, ECHO permutation and AES block cipher'. SAC, 2009 (LNCS, 5867), pp. 16– 35 Citing Literature Volume9, Issue6November 2015Pages 328-333 FiguresReferencesRelatedInformation
Referência(s)