Subject: [Cfrg] RFC Draft for KangarooTwelve XOF draft-viguier-kangarootwelve-00

From: Benoît Viguier <[email-masked]>
Date: Wed, 14 Jun 2017 18:21:19 +0200

Hello everyone,

I wrote this RFC draft for KangarooTwelve
(https://eprint.iacr.org/2016/770).
It provides an efficient and secure hashing primitive, which is able to
exploit
the parallelism of the implementation in a scalable way. It uses tree
hashing
over a round-reduced version of SHAKE128 as underlying primitive.

The reference code is also at available at:
https://github.com/KeccakTeam/KeccakCodePackage
(Standalone/KangarooTwelve-reference/K12.py)

Draft is available here:
https://tools.ietf.org/html/draft-viguier-kangarootwelve-00

I would like to submit this RFC under the Internet Research Task Force
stream,
and as far as I understood I need a Research Group (RFC 5743).
Anyone would be interested to be the Editor?

Of course, any other feedback is welcome.

-- 
Kind regards,

Benoît Viguier
Software Engineer - PhD Student | Cryptography & Formal Methods
Radboud University | Mercator 1, room 03.17, Toernooiveld 212
6525 EC Nijmegen, the Netherlands | www.viguier.nl

--------------------------------------------------------------------------
This message (and any attachments) is intended solely for the addressee(s)
and may contain confidential information. If you are not the addressee, do
not copy this message (and any attachments), forward or share this message
with third parties. You are requested to notify the sender immediately and
delete this message.

---

From: David Wong <[email-masked]>
Date: Thu, 15 Jun 2017 18:27:17 +0100

Hey Benoit,

I'm happy to see that the first draft is done!

The whole thing looks pretty good to me. I have some minor feedback as
well as a major one right below:

I think the specification mixes implementation tricks and the real
specification keccak. If you're planning on giving (reversed) values
in hexadecimal for the dsByte and the padding, I think it is worth
specifying the sponge function differently with inversed operations in
the permutation and a transformation from input to lanes, relevant to
the tricks that implementations use. This would also mean getting rid
of any LSB 0 bit-numbering mention in the convention section. I think
this RFC would be a really good opportunity to clear things up and
simplify the implementers' job.

I would start by defining F as F(input, domain_separation,
output_length). Then the following algorithm for the function F:

// Padding
1. append the domain_separation byte to the input
2. append zeros to the input until it becomes a multiple of the rate (168 bytes)
3. XOR the last byte of the padded input with 0x80

// XOR'ing
4. split the input in n blocks of 168 bytes (rate size): block_1, ..., block_n
5. For each block, apply the Absorb algorithm
      Absorb(block_1, state); ...; Absorb(block_n, state)
      (note that each Absorb call is taking an updated state from the
previous Absorb call)

// Output'ing
6. concatenate the outputs of Squeeze algorithm until the amount of
bytes collected is greater or equal
   to output_length
      output = Squeeze(state) || ... || Squeeze(state)
      (note that each Squeeze call is taking an updated state from the
previous Squeeze call)
7. truncate the output to the size of output_length and return the result

// Absorb algorithm
Absorb(input, state) takes an input of 168 bytes, the state of the
sponge and updates the state.

1. Split the input in 21 8-byte blocks: input_1, ..., input_21; such that
   input_i = {b_i_0, b_i_1, b_i_2, b_i_3, b_i_4, b_i_5, b_i_6, b_i_7}
2. For each input_i, reverse the order of the bytes, such that
   reversed_input_i = {b_i_7, b_i_6, b_i_5, b_i_4, b_i_3, b_i_2, b_i_1, b_i_0}
3. For the first 21 "public" lanes of the sponge seen as
   Lane_i = {L_i_0, L_i_1, L_i_2, L_i_3, L_i_4, L_i_5, L_i_6, L_i_7},
   XOR each reversed_input_i against each Lane_i, such that
   Lane_i = {L_i_0 + b_i_7, L_i_1 + b_i_6, L_i_2 + b_i_5, L_i_3 +
b_i_4, L_i_4 + b_i_3, L_i_5 + b_i_2, L_i_6 + b_i_1, L_i_7 + b_i_0}
4. Update the sponge state by calling the permutation with only the
last 12 rounds (see Appendix A)

// Squeeze algorithm
output = Squeeze(state) takes the state of the sponge and updates the
state, while returning a 168 bytes output

1. Copy out the 21 "public" lanes of the sponge state Lane_1, ...,
Lane_21 seen as
   Lane_i = {L_i_0, L_i_1, L_i_2, L_i_3, L_i_4, L_i_5, L_i_6, L_i_7}
2. Reverse the bytes of each copied lane:
   Reversed_Lane_i = {L_i_7, L_i_6, L_i_5, L_i_4, L_i_3, L_i_2, L_i_1, L_i_0}
3. Update the sponge state by calling the permutation with only the
last 12 rounds (see Appendix A)
4. Return Reversed_Lane_1 || ... || Reversed_Lane_21

Now, in the appendix A.1. of the permutation, I would be careful to
define every operation in the reverse direction. For example ROL64()
is done by a left shift << instead of a right shift >>. It should also
be mentionned that operations have been reversed since the lanes have
been reversed.

I think this is important because the point of such an RFC is to dumb
down the technical details and facilitate the implementation. A lot of
shortcuts can be taken here because we do not care about other
rate+capacity variants, or non-multiple of bytes.

I have some more feedback about details here and there. Feel free to
ignore or acknowledge as you deem relevant.

→ The abstract

  It could contain more information on the use-case rather than on
what type of primitive it is.
  I'm saying that because I often run into obscure RFC and have a hard
time understanding from the abstract what they are for. Here is how I
would think is important:

  * K12          → KangarooTwelve is an eXtendable Output Function (XOF)
  * trust        → The design is based on SHA-3 and done by the same inventors
  * XOF          → It provides an arbitrary output length that can be
truncated to any desired size
  * fast         → Its performs better than SHA-3, SHA-2 and SHA-1
  * big inputs   → It takes advantage of tree hashing to efficiently
parallelize hashing of big files
  * small inputs → Due to Sakura Coding and the padding, no penalty
exists for small inputs

  This could be written as:

  This document defines the KangarooTwelve eXtendable Output Function (XOF),
  a hash function based on SHA-3 and designed by the same inventors that
  provides outputs of arbitrary lengths. It performs better than SHA-3, SHA-2
  and SHA-1; taking advantage of parallelism to speed up hashing of big files
  while still being efficient by avoiding penalties for small inputs.

→ The introduction

  - It could use the same spiel about the no-penalty for small inputs.
  - You mention Keccak without defining what it is (you mention
Keccak-p before though).

→ Section 1.1. Conventions

  - Do you really need the MUST, SHOULD, etc... keywords?
    I'm not sure any of these makes too much sense in K12's context.
  - "LSB 0 bit convention" is also called "LSB 0 bit-numbering", which
might more formal and fit to the context?

> |s|  denotes the length of a byte string "s".  For example, |"FF FF"| = 2.

  I think this should emphasize the unit: "denotes the length of a
value in 'bytes'"

→ Section 2.1. Inner function: F

> Keccak-p[1600,n_r=12]

  I think it should be noted that these are the "last" 12 rounds of
the permutation with 24 rounds.

  Also I'd prefer a function F defined as F(input, domain_separation,
output_length) to simplify the
  other parts of the RFC.

> The input string S SHOULD be represented as a pair (Sbytes, dS),

  Not sure why the "SHOULD" or why the mention of a "pair". What's a
pair in C :) ?

>  multi-rate padding rule pad10*1

  - You mention the multi-rate padding without defining it.
  - Do we really need these explanations on the computation of `dS`?
Just giving the values should be enough imo

→ Section 2.2. Tree hashing over F

  - Could this section simply be renamed "Hashing"?
  - I would also enumerate the steps and simplify a few things. For example:

  KangarooTwelve( input, custom_string, output_length ) takes any
input to be hashed, a
  (optionally empty) customization string and a desired output length.
It then execute
  the following steps:

  1. Concatenate input, custom_string and right_encode(|custom_string|).
       S = input || custom_string || right_encode(|custom_string|)
  2. If the byte length of S is less than 8192 bytes, then run the
sponge function
     on S with dsByte = 0x07 and ignore the rest of these steps.
Otherwise skip this
     step and go directly to step 3.
       F(S, dsByte=0x07, output_length)
  3. Split the concatenated value into n chunks of 8192 bytes, where
the last one can
     be shorter or equal to 8192 bytes). For example with 5 chunks:
       S = S_0 || .. || S_4
       with |S_0| = |S_1| = |S_2| = |S_3| = 8192 bytes
       and |S_4| <= 8192 bytes
  4. Compute CV_1 to CV_4, optionally using the parallelism supported
by your architecture.
     (For example this is achievable on Intel architecture by using
SIMD instructions.)
       Node_i  = S_i || `110`
       CV_i    = F(Node_i, dsByte=0x0B, output_length=32)
  5. To compute the final input, start by contatenating the first
chunk with the hexadecimal string "03 00 00 00 00 00 00 00"
       final_input = S_0 || "03 00 00 00 00 00 00 00"
  6. Append the concatenation of all the the CV_i to the final input.
       final_input = final_input || CV_1 || CV_2 || CV_3 || CV_4
  7. Append the encoding of the number of chunks minus one (4 in our
example) to the final input.
       final_input = final_input || right_encoding(n-1)
  8. Append the hexadecimal string "FF FF" to the final input.
       final_input = final_input || "FF FF"
  9. Run the sponge function on the final input with dsByte = 0x06
       F(final_input, dsByte=0x06, output_length)

> For |S| > 8192 bytes

  I think diagrams should be in the appendix (or at least in a
different section). Also a diagram for `|S| <= 8192 bytes` would be
nice as well :)

                                 +--------------+
                                 |    message   |
                                 +--------------+
                                        ||
                                 +--------------+
                                 | custom_string|
                                 +--------------+
                                        ||
                     +-----------------------------------+  F(dsByte=0x07)
                     | right_encode(|custom_string|)
|-----------------> output
                     +-----------------------------------+

→ 2.3.  right_encode( x )

> x = x / 256

  I don't think you define the division here. I would define it in
this section as well as in the convention section (1.1):

     a / b outputs the quotient of the operation: a divided by b. For
example 10 = 3 * 9 + 1, so 3 would be outputed
     by the operation 10 / 9. Furthermore, since 240 = 0 * 256 + 240,
0 would be the output of 240 / 256.

→ Section 3. Test Vectors

  These should probably be in an Appendix.

→ Appendix A.3.

  You could also think of including (or replacing yours with) the
python function there:
  https://github.com/gvanas/KeccakCodePackage/blob/master/Standalone/KangarooTwelve-reference/K12.py#L98:L113
  But I think it should be noted that this is not taking advantage of
parallelism.

I probably have more, but this is starting to get huge so... I'll wait
until you tell me if I'm being unreasonable.

Thanks again for your work Benoit!

Regards,
David