idnits 2.17.1 draft-irtf-cfrg-kangarootwelve-02.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The abstract seems to contain references ([FIPS202]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 200 has weird spacing: '... input byte-...' == Line 202 has weird spacing: '...ByteLen posit...' -- The document date (March 12, 2020) is 1505 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: 'FIPS 202' is mentioned on line 27, but not defined -- Looks like a reference, but probably isn't: '1600' on line 189 -- Looks like a reference, but probably isn't: '0' on line 619 -- Looks like a reference, but probably isn't: '1' on line 593 -- Looks like a reference, but probably isn't: '2' on line 594 -- Looks like a reference, but probably isn't: '3' on line 595 -- Looks like a reference, but probably isn't: '4' on line 596 -- Looks like a reference, but probably isn't: '5' on line 577 -- Looks like a reference, but probably isn't: '6' on line 578 -- Looks like a reference, but probably isn't: '7' on line 579 -- Looks like a reference, but probably isn't: '8' on line 580 -- Looks like a reference, but probably isn't: '9' on line 581 -- Looks like a reference, but probably isn't: '10' on line 582 -- Looks like a reference, but probably isn't: '11' on line 583 Summary: 1 error (**), 0 flaws (~~), 4 warnings (==), 15 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Crypto Forum B. Viguier 3 Internet-Draft Radboud University 4 Intended status: Informational D. Wong, Ed. 5 Expires: September 13, 2020 Facebook 6 G. Van Assche, Ed. 7 STMicroelectronics 8 Q. Dang, Ed. 9 NIST 10 J. Daemen, Ed. 11 Radboud University 12 March 12, 2020 14 KangarooTwelve 15 draft-irtf-cfrg-kangarootwelve-02 17 Abstract 19 This document defines the KangarooTwelve eXtendable Output Function 20 (XOF), a hash function with output of arbitrary length. It provides 21 an efficient and secure hashing primitive, which is able to exploit 22 the parallelism of the implementation in a scalable way. It uses 23 tree hashing over a round-reduced version of SHAKE128 as underlying 24 primitive. 26 This document builds up on the definitions of the permutations and of 27 the sponge construction in [FIPS 202], and is meant to serve as a 28 stable reference and an implementation guide. 30 Status of This Memo 32 This Internet-Draft is submitted in full conformance with the 33 provisions of BCP 78 and BCP 79. 35 Internet-Drafts are working documents of the Internet Engineering 36 Task Force (IETF). Note that other groups may also distribute 37 working documents as Internet-Drafts. The list of current Internet- 38 Drafts is at https://datatracker.ietf.org/drafts/current/. 40 Internet-Drafts are draft documents valid for a maximum of six months 41 and may be updated, replaced, or obsoleted by other documents at any 42 time. It is inappropriate to use Internet-Drafts as reference 43 material or to cite them other than as "work in progress." 45 This Internet-Draft will expire on September 13, 2020. 47 Copyright Notice 49 Copyright (c) 2020 IETF Trust and the persons identified as the 50 document authors. All rights reserved. 52 This document is subject to BCP 78 and the IETF Trust's Legal 53 Provisions Relating to IETF Documents 54 (https://trustee.ietf.org/license-info) in effect on the date of 55 publication of this document. Please review these documents 56 carefully, as they describe your rights and restrictions with respect 57 to this document. Code Components extracted from this document must 58 include Simplified BSD License text as described in Section 4.e of 59 the Trust Legal Provisions and are provided without warranty as 60 described in the Simplified BSD License. 62 Table of Contents 64 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 65 1.1. Conventions . . . . . . . . . . . . . . . . . . . . . . . 3 66 2. Specifications . . . . . . . . . . . . . . . . . . . . . . . 4 67 2.1. Inner function F . . . . . . . . . . . . . . . . . . . . 5 68 2.2. Tree hashing over F . . . . . . . . . . . . . . . . . . . 6 69 2.3. length_encode( x ) . . . . . . . . . . . . . . . . . . . 9 70 3. Test vectors . . . . . . . . . . . . . . . . . . . . . . . . 9 71 4. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11 72 5. Security Considerations . . . . . . . . . . . . . . . . . . . 11 73 6. References . . . . . . . . . . . . . . . . . . . . . . . . . 12 74 6.1. Normative References . . . . . . . . . . . . . . . . . . 12 75 6.2. Informative References . . . . . . . . . . . . . . . . . 13 76 Appendix A. Pseudocode . . . . . . . . . . . . . . . . . . . . . 14 77 A.1. Keccak-p[1600,n_r=12] . . . . . . . . . . . . . . . . . . 14 78 A.2. KangarooTwelve . . . . . . . . . . . . . . . . . . . . . 15 79 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 16 81 1. Introduction 83 This document defines the KangarooTwelve eXtendable Output Function 84 (XOF) [K12], i.e. a generalization of a hash function that can return 85 an output of arbitrary length. KangarooTwelve is based on a Keccak-p 86 permutation specified in [FIPS202] and has a higher speed than SHAKE 87 and SHA-3. 89 The SHA-3 functions process data in a serial manner and are unable to 90 optimally exploit parallelism available in modern CPU architectures. 91 Similar to ParallelHash [SP800-185], KangarooTwelve splits the input 92 message in fragments to exploit available parallelism. It then 93 applies an inner hash function F on each of them separately before 94 applying F again on the concatenation of the digests. It makes use 95 of Sakura coding for ensuring soundness of the tree hashing mode 96 [SAKURA]. The inner hash function F is a sponge function and uses a 97 round-reduced version of the permutation Keccak-f used in SHA-3, 98 making it faster than ParallelHash. Its security builds up on the 99 scrutiny that Keccak has received since its publication 100 [KECCAK_CRYPTANALYSIS]. 102 With respect to [FIPS202] and [SP800-185] functions, KangarooTwelve 103 features the following advantages: 105 o Unlike SHA3-224, SHA3-256, SHA3-384, SHA3-512, KangarooTwelve has 106 an extendable output. 108 o Unlike any [FIPS202] defined function, similarly to functions 109 defined in [SP800-185], KangarooTwelve allows the use of a 110 customization string. 112 o Unlike any [FIPS202] and [SP800-185] functions but ParallelHash, 113 KangarooTwelve splits the input message in fragments to exploit 114 available parallelism. 116 o Unlike ParallelHash, KangarooTwelve does not have overhead when 117 processing short messages. 119 o The Keccak-f permutation in KangarooTwelve has half the number of 120 rounds of the one used in SHA3, making it faster than any function 121 defined in [FIPS202] and [SP800-185]. 123 1.1. Conventions 125 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 126 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 127 document are to be interpreted as described in RFC 2119 [RFC2119]. 129 The following notations are used throughout the document: 131 `...` denotes a string of bytes given in hexadecimal. For example, 132 `0B 80`. 134 |s| denotes the length of a byte string `s`. For example, |`FF FF`| 135 = 2. 137 `00`^b denotes a byte string consisting of the concatenation of b 138 bytes `00`. For example, `00`^7 = `00 00 00 00 00 00 00`. 140 `00`^0 denotes the empty byte-string. 142 a||b denotes the concatenation of two strings a and b. For example, 143 `10`||`F1` = `10 F1` 145 s[n:m] denotes the selection of bytes from n to m exclusive of a 146 string s. For example, for s = `A5 C6 D7`, s[0:1] = `A5` and 147 s[1:3] = `C6 D7`. 149 s[n:] denotes the selection of bytes from n to the end of a string 150 s. For example, for s = `A5 C6 D7`, s[0:] = `A5 C6 D7` and s[2:] 151 = `D7`. 153 In the following, x and y are byte strings of equal length: 155 x^=y denotes x takes the value x XOR y. 157 x & y denotes x AND y. 159 In the following, x and y are integers: 161 x+=y denotes x takes the value x + y. 163 x-=y denotes x takes the value x - y. 165 x**y denotes x multiplied by itself y times. 167 2. Specifications 169 KangarooTwelve is an eXtendable Output Function (XOF). It takes as 170 input two byte-strings (M, C) and a positive integer L where 172 M byte-string, is the Message and 174 C byte-string, is an OPTIONAL Customization string and 176 L positive integer, the number of output bytes requested. 178 The Customization string MAY serve as domain separation. It is 179 typically a short string such as a name or an identifier (e.g. URI, 180 ODI...) 182 By default, the Customization string is the empty string. For an API 183 that does not support a customization string input, C MUST be the 184 empty string. 186 2.1. Inner function F 188 The inner function F makes use of the permutation Keccak- 189 p[1600,n_r=12], i.e., a version of the permutation Keccak-f[1600] 190 used in SHAKE and SHA-3 instances reduced to its last n_r=12 rounds 191 and specified in FIPS 202, sections 3.3 and 3.4 [FIPS202]. KP 192 denotes this permutation. 194 F is a sponge function calling this permutation KP with a rate of 168 195 bytes or 1344 bits. It follows that F has a capacity of 1600 - 1344 196 = 256 bits or 32 bytes. 198 The sponge function F takes: 200 input byte-string, the input bytes and 202 outputByteLen positive integer, the length of the output in bytes 204 First the message is padded with zeroes to the closest multiple of 205 168 bytes. Then a byte `80` is XORed to the last byte of the padded 206 message. and the resulting string is split into a sequence of 207 168-byte blocks. 209 As defined by the sponge construction, the process operates on a 210 state and consists of two phases: the absorbing phase that processes 211 the input and the squeezing phase that produces the output. 213 In the absorbing phase the state is initialized to all-zero. The 214 message blocks are XORed into the first 168 bytes of the state. Each 215 block absorbed is followed with an application of KP to the state. 217 In the squeezing phase output is formed by taking the first 168 bytes 218 of the state, repeated as many times as necessary until outputByteLen 219 bytes are obtained, interleaved with the application of KP to the 220 state. 222 This definition of the sponge construction assumes a at least one- 223 byte-long input where the last byte is in the `01`-`7F` range. This 224 is the case in KangarooTwelve. 226 A pseudocode version is available as follows: 228 F(input, outputByteLen): 229 offset = 0 230 state = `00`^200 232 # === Absorb complete blocks === 233 while offset < |input| - 168 234 state ^= input[offset : offset + 168] || `00`^32 235 state = KP(state) 236 offset += 168 238 # === Absorb last block and treatment of padding === 239 LastBlockLength = |input| - offset 240 state ^= input[offset:] || `00`^(200-LastBlockLength) 241 state ^= `00`^167 || `80` || `00`^32 242 state = KP(state) 244 # === Squeeze === 245 output = `00`^0 246 while outputByteLen > 168 247 output = output || state[0:168] 248 outputByteLen -= 168 249 state = KP(state) 251 output = output || state[0:outputByteLen] 253 return output 254 end 256 2.2. Tree hashing over F 258 On top of the sponge function F, KangarooTwelve uses a Sakura- 259 compatible tree hash mode [SAKURA]. First, merge M and the OPTIONAL 260 C to a single input string S in a reversible way. length_encode( |C| 261 ) gives the length in bytes of C as a byte-string. length_encode( x ) 262 may be abbreviated as l_e( x ). See Section 2.3. 264 S = M || C || length_encode( |C| ) 266 Then, split S into n chunks of 8192 bytes. 268 S = S_0 || .. || S_(n-1) 269 |S_0| = .. = |S_(n-2)| = 8192 bytes 270 |S_(n-1)| <= 8192 bytes 272 From S_1 .. S_(n-1), compute the 32-byte Chaining Values CV_1 .. 273 CV_(n-1). In order to be optimally efficient, this computation 274 SHOULD exploit the parallelism available on the platform such as SIMD 275 instructions. 277 CV_i = F( S_i||`0B`, 32 ) 279 Compute the final node: FinalNode. 281 o If |S| <= 8192 bytes, FinalNode = S 283 o Otherwise compute FinalNode as follows: 285 FinalNode = S_0 || `03 00 00 00 00 00 00 00` 286 FinalNode = FinalNode || CV_1 287 .. 288 FinalNode = FinalNode || CV_(n-1) 289 FinalNode = FinalNode || length_encode(n-1) 290 FinalNode = FinalNode || `FF FF` 292 Finally, KangarooTwelve output is retrieved: 294 o If |S| <= 8192 bytes, from F( FinalNode||`07`, L ) 296 KangarooTwelve( M, C, L ) = F( FinalNode||`07`, L ) 298 o Otherwise from F( FinalNode||`06`, L ) 300 KangarooTwelve( M, C, L ) = F( FinalNode||`06`, L ) 302 The following figure illustrates the computation flow of 303 KangarooTwelve for |S| <= 8192 bytes: 305 +--------------+ F(..||`07`, L) 306 | S |-----------------> output 307 +--------------+ 309 The following figure illustrates the computation flow of 310 KangarooTwelve for |S| > 8192 bytes: 312 +--------------+ 313 | S_0 | 314 +--------------+ 315 || 316 +--------------+ 317 | `03`||`00`^7 | 318 +--------------+ 319 || 320 +---------+ F(..||`0B`,32) +--------------+ 321 | S_1 |----------------->| CV_1 | 322 +---------+ +--------------+ 323 || 324 +---------+ F(..||`0B`,32) +--------------+ 325 | S_2 |----------------->| CV_2 | 326 +---------+ +--------------+ 327 || 328 ... ... 329 || 330 +---------+ F(..||`0B`,32) +--------------+ 331 | S_(n-1) |----------------->| CV_(n-1) | 332 +---------+ +--------------+ 333 || 334 +--------------+ 335 | l_e( n-1 ) | 336 +--------------+ 337 || 338 +------------+ F(..||`06`, L) 339 | `FF FF` |-----------------> output 340 +------------+ 342 We provide a pseudocode version in Appendix A.2. 344 The table below gathers the values of the domain separation bytes 345 used by the tree hash mode: 347 +--------------------+------------------+ 348 | Type | Byte | 349 +--------------------+------------------+ 350 | SingleNode | `07` | 351 | | | 352 | IntermediateNode | `0B` | 353 | | | 354 | FinalNode | `06` | 355 +--------------------+------------------+ 357 2.3. length_encode( x ) 359 The function length_encode takes as inputs a non negative integer x < 360 256**255 and outputs a string of bytes x_(n-1) || .. || x_0 || n 361 where 363 x = sum from i=0..n-1 of 256**i * x_i 365 and where n is the smallest non-negative integer such that x < 366 256**n. n is also the length of x_(n-1) || .. || x_0. 368 As example, length_encode(0) = `00`, length_encode(12) = `0C 01` and 369 length_encode(65538) = `01 00 02 03` 371 A pseudocode version is as follows. 373 length_encode(x): 374 S = `00`^0 376 while x > 0 377 S = x mod 256 || S 378 x = x / 256 380 S = S || length(S) 382 return S 383 end 385 3. Test vectors 387 Test vectors are based on the repetition of the pattern `00 01 .. FA` 388 with a specific length. ptn(n) defines a string by repeating the 389 pattern `00 01 .. FA` as many times as necessary and truncated to n 390 bytes e.g. 392 Pattern for a length of 17 bytes: 393 ptn(17) = 394 `00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F 10` 396 Pattern for a length of 17**2 bytes: 397 ptn(17**2) = 398 `00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F 399 10 11 12 13 14 15 16 17 18 19 1A 1B 1C 1D 1E 1F 400 20 21 22 23 24 25 26 27 28 29 2A 2B 2C 2D 2E 2F 401 30 31 32 33 34 35 36 37 38 39 3A 3B 3C 3D 3E 3F 402 40 41 42 43 44 45 46 47 48 49 4A 4B 4C 4D 4E 4F 403 50 51 52 53 54 55 56 57 58 59 5A 5B 5C 5D 5E 5F 404 60 61 62 63 64 65 66 67 68 69 6A 6B 6C 6D 6E 6F 405 70 71 72 73 74 75 76 77 78 79 7A 7B 7C 7D 7E 7F 406 80 81 82 83 84 85 86 87 88 89 8A 8B 8C 8D 8E 8F 407 90 91 92 93 94 95 96 97 98 99 9A 9B 9C 9D 9E 9F 408 A0 A1 A2 A3 A4 A5 A6 A7 A8 A9 AA AB AC AD AE AF 409 B0 B1 B2 B3 B4 B5 B6 B7 B8 B9 BA BB BC BD BE BF 410 C0 C1 C2 C3 C4 C5 C6 C7 C8 C9 CA CB CC CD CE CF 411 D0 D1 D2 D3 D4 D5 D6 D7 D8 D9 DA DB DC DD DE DF 412 E0 E1 E2 E3 E4 E5 E6 E7 E8 E9 EA EB EC ED EE EF 413 F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 FA 414 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F 415 10 11 12 13 14 15 16 17 18 19 1A 1B 1C 1D 1E 1F 416 20 21 22 23 24 25` 418 KangarooTwelve(M=`00`^0, C=`00`^0, 32): 419 `1A C2 D4 50 FC 3B 42 05 D1 9D A7 BF CA 1B 37 51 420 3C 08 03 57 7A C7 16 7F 06 FE 2C E1 F0 EF 39 E5` 422 KangarooTwelve(M=`00`^0, C=`00`^0, 64): 423 `1A C2 D4 50 FC 3B 42 05 D1 9D A7 BF CA 1B 37 51 424 3C 08 03 57 7A C7 16 7F 06 FE 2C E1 F0 EF 39 E5 425 42 69 C0 56 B8 C8 2E 48 27 60 38 B6 D2 92 96 6C 426 C0 7A 3D 46 45 27 2E 31 FF 38 50 81 39 EB 0A 71` 428 KangarooTwelve(M=`00`^0, C=`00`^0, 10032), last 32 bytes: 429 `E8 DC 56 36 42 F7 22 8C 84 68 4C 89 84 05 D3 A8 430 34 79 91 58 C0 79 B1 28 80 27 7A 1D 28 E2 FF 6D` 432 KangarooTwelve(M=ptn(1 bytes), C=`00`^0, 32): 433 `2B DA 92 45 0E 8B 14 7F 8A 7C B6 29 E7 84 A0 58 434 EF CA 7C F7 D8 21 8E 02 D3 45 DF AA 65 24 4A 1F` 436 KangarooTwelve(M=ptn(17 bytes), C=`00`^0, 32): 437 `6B F7 5F A2 23 91 98 DB 47 72 E3 64 78 F8 E1 9B 438 0F 37 12 05 F6 A9 A9 3A 27 3F 51 DF 37 12 28 88` 440 KangarooTwelve(M=ptn(17**2 bytes), C=`00`^0, 32): 441 `0C 31 5E BC DE DB F6 14 26 DE 7D CF 8F B7 25 D1 442 E7 46 75 D7 F5 32 7A 50 67 F3 67 B1 08 EC B6 7C` 444 KangarooTwelve(M=ptn(17**3 bytes), C=`00`^0, 32): 445 `CB 55 2E 2E C7 7D 99 10 70 1D 57 8B 45 7D DF 77 446 2C 12 E3 22 E4 EE 7F E4 17 F9 2C 75 8F 0D 59 D0` 448 KangarooTwelve(M=ptn(17**4 bytes), C=`00`^0, 32): 449 `87 01 04 5E 22 20 53 45 FF 4D DA 05 55 5C BB 5C 450 3A F1 A7 71 C2 B8 9B AE F3 7D B4 3D 99 98 B9 FE` 452 KangarooTwelve(M=ptn(17**5 bytes), C=`00`^0, 32): 453 `84 4D 61 09 33 B1 B9 96 3C BD EB 5A E3 B6 B0 5C 454 C7 CB D6 7C EE DF 88 3E B6 78 A0 A8 E0 37 16 82` 456 KangarooTwelve(M=ptn(17**6 bytes), C=`00`^0, 32): 457 `3C 39 07 82 A8 A4 E8 9F A6 36 7F 72 FE AA F1 32 458 55 C8 D9 58 78 48 1D 3C D8 CE 85 F5 8E 88 0A F8` 460 KangarooTwelve(M=`00`^0, C=ptn(1 bytes), 32): 461 `FA B6 58 DB 63 E9 4A 24 61 88 BF 7A F6 9A 13 30 462 45 F4 6E E9 84 C5 6E 3C 33 28 CA AF 1A A1 A5 83` 464 KangarooTwelve(M=`FF`, C=ptn(41 bytes), 32): 465 `D8 48 C5 06 8C ED 73 6F 44 62 15 9B 98 67 FD 4C 466 20 B8 08 AC C3 D5 BC 48 E0 B0 6B A0 A3 76 2E C4` 468 KangarooTwelve(M=`FF FF FF`, C=ptn(41**2), 32): 469 `C3 89 E5 00 9A E5 71 20 85 4C 2E 8C 64 67 0A C0 470 13 58 CF 4C 1B AF 89 44 7A 72 42 34 DC 7C ED 74` 472 KangarooTwelve(M=`FF FF FF FF FF FF FF`, C=ptn(41**3 bytes), 32): 473 `75 D2 F8 6A 2E 64 45 66 72 6B 4F BC FC 56 57 B9 474 DB CF 07 0C 7B 0D CA 06 45 0A B2 91 D7 44 3B CF` 476 4. IANA Considerations 478 None. 480 5. Security Considerations 482 This document is meant to serve as a stable reference and an 483 implementation guide for the KangarooTwelve eXtendable Output 484 Function. It relies on the cryptanalysis of Keccak and provides with 485 the same security strength as SHAKE128, i.e., 128 bits of security 486 against all attacks 488 To be more precise, KangarooTwelve is made of two layers: 490 o The inner function F. This layer relies on cryptanalysis. 491 KangarooTwelve's F function is exactly Keccak[r=1344, c=256] (as 492 in SHAKE128) reduced to 12 rounds. Any reduced-round 493 cryptanalysis on Keccak is also a reduced-round cryptanalysis of 494 KangarooTwelve's F (provided the number of rounds attacked is not 495 higher than 12). 497 o The tree hashing over F. This layer is a mode on top of F that 498 does not introduce any vulnerability thanks to the use of Sakura 499 coding proven secure in [SAKURA]. 501 This reasoning is detailed and formalized in [K12]. 503 To achieve 128-bit security strength, the output L must be chosen 504 long enough so that there are no generic attacks that violate 128-bit 505 security. So for 128-bit (second) preimage security the output 506 should be at least 128 bits, for 128-bit of security against multi- 507 target preimage attacks with T targets the output should be at least 508 128+log_2(T) bits and for 128-bit collision security the output 509 should be at least 256 bits. 511 Furthermore, when the output length is at least 256 bits, 512 KangarooTwelve achieves NIST's post-quantum security level 2 513 [NISTPQ]. 515 6. References 517 6.1. Normative References 519 [FIPS202] National Institute of Standards and Technology, "FIPS PUB 520 202 - SHA-3 Standard: Permutation-Based Hash and 521 Extendable-Output Functions", 522 WWW http://dx.doi.org/10.6028/NIST.FIPS.202, August 2015. 524 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 525 Requirement Levels", BCP 14, RFC 2119, 526 DOI 10.17487/RFC2119, March 1997, 527 . 529 [SP800-185] 530 National Institute of Standards and Technology, "NIST 531 Special Publication 800-185 SHA-3 Derived Functions: 532 cSHAKE, KMAC, TupleHash and ParallelHash", 533 WWW https://doi.org/10.6028/NIST.SP.800-185, December 534 2016. 536 6.2. Informative References 538 [K12] Bertoni, G., Daemen, J., Peeters, M., Van Assche, G., and 539 R. Van Keer, "KangarooTwelve: fast hashing based on 540 Keccak-p", WWW http://eprint.iacr.org/2016/770.pdf, August 541 2016. 543 [KECCAK_CRYPTANALYSIS] 544 Keccak Team, "Summary of Third-party cryptanalysis of 545 Keccak", WWW https://www.keccak.team/third_party.html, 546 2017. 548 [NISTPQ] National Institute of Standards and Technology, 549 "Submission Requirements and Evaluation Criteria for the 550 Post-Quantum Cryptography Standardization Process", WWW 551 https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum- 552 Cryptography/documents/call-for-proposals-final-dec- 553 2016.pdf, December 2016. 555 [SAKURA] Bertoni, G., Daemen, J., Peeters, M., and G. Van Assche, 556 "Sakura: a flexible coding for tree hashing", 557 WWW http://eprint.iacr.org/2013/231.pdf, April 2013. 559 [XKCP] Bertoni, G., Daemen, J., Peeters, M., Van Assche, G., and 560 R. Van Keer, "eXtended Keccak Code Package", 561 WWW https://github.com/XKCP/XKCP, September 2018. 563 Appendix A. Pseudocode 565 The sub-sections of this appendix contain pseudocode definitions of 566 KangarooTwelve. A standalone Python version is also available in the 567 Keccak Code Package [XKCP] and in [K12] 569 A.1. Keccak-p[1600,n_r=12] 571 KP(state): 572 RC[0] = `8B 80 00 80 00 00 00 00` 573 RC[1] = `8B 00 00 00 00 00 00 80` 574 RC[2] = `89 80 00 00 00 00 00 80` 575 RC[3] = `03 80 00 00 00 00 00 80` 576 RC[4] = `02 80 00 00 00 00 00 80` 577 RC[5] = `80 00 00 00 00 00 00 80` 578 RC[6] = `0A 80 00 00 00 00 00 00` 579 RC[7] = `0A 00 00 80 00 00 00 80` 580 RC[8] = `81 80 00 80 00 00 00 80` 581 RC[9] = `80 80 00 00 00 00 00 80` 582 RC[10] = `01 00 00 80 00 00 00 00` 583 RC[11] = `08 80 00 80 00 00 00 80` 585 for x from 0 to 4 586 for y from 0 to 4 587 lanes[x][y] = state[8*(x+5*y):8*(x+5*y)+8] 589 for round from 0 to 11 590 # theta 591 for x from 0 to 4 592 C[x] = lanes[x][0] 593 C[x] ^= lanes[x][1] 594 C[x] ^= lanes[x][2] 595 C[x] ^= lanes[x][3] 596 C[x] ^= lanes[x][4] 597 for x from 0 to 4 598 D[x] = C[(x+4) mod 5] ^ ROL64(C[(x+1) mod 5], 1) 599 for y from 0 to 4 600 for x from 0 to 4 601 lanes[x][y] = lanes[x][y]^D[x] 603 # rho and pi 604 (x, y) = (1, 0) 605 current = lanes[x][y] 606 for t from 0 to 23 607 (x, y) = (y, (2*x+3*y) mod 5) 608 (current, lanes[x][y]) = 609 (lanes[x][y], ROL64(current, (t+1)*(t+2)/2)) 611 # chi 612 for y from 0 to 4 613 for x from 0 to 4 614 T[x] = lanes[x][y] 615 for x from 0 to 4 616 lanes[x][y] = T[x] ^((not T[(x+1) mod 5]) & T[(x+2) mod 5]) 618 # iota 619 lanes[0][0] ^= RC[round] 621 state = `00`^0 622 for x from 0 to 4 623 for y from 0 to 4 624 state = state || lanes[x][y] 626 return state 627 end 629 where ROL64(x, y) is a rotation of the 'x' 64-bit word toward the 630 bits with higher indexes by 'y' positions. The 8-bytes byte-string x 631 is interpreted as a 64-bit word in little-endian format. 633 A.2. KangarooTwelve 635 KangarooTwelve(inputMessage, customString, outputByteLen): 636 S = inputMessage || customString 637 S = S || length_encode( |customString| ) 639 if |S| <= 8192 640 return F(S || `07`, outputByteLen) 641 else 642 # === Kangaroo hopping === 643 FinalNode = S[0:8192] || `03` || `00`^7 644 offset = 8192 645 numBlock = 0 646 while offset < |S| 647 blockSize = min( |S| - offset, 8192) 648 CV = F(S[offset : offset + blockSize] || `0B`, 32) 649 FinalNode = FinalNode || CV 650 numBlock += 1 651 offset += blockSize 653 FinalNode = FinalNode || length_encode( numBlock ) || `FF FF` 655 return F(FinalNode || `06`, outputByteLen) 656 end 658 Authors' Addresses 660 Benoit Viguier 661 Radboud University 662 Toernooiveld 212 663 Nijmegen 664 The Netherlands 666 EMail: b.viguier@cs.ru.nl 668 David Wong (editor) 669 Facebook 671 EMail: davidwong.crypto@gmail.com 673 Gilles Van Assche (editor) 674 STMicroelectronics 676 EMail: gilles.vanassche@st.com 678 Quynh Dang (editor) 679 National Institute of Standards and Technology 681 EMail: quynh.dang@nist.gov 683 Joan Daemen (editor) 684 Radboud University 686 EMail: joan@cs.ru.nl