Re: [Cfrg] RGLC on draft-irtf-cfrg-kangarootwelve-01

[Benoît Viguier <[e-mail]>]

Dear Stephen,

Thank you for your comments on our draft!

Please find below some answers and comments.

On 2/16/20 3:53 PM, Stephen Farrell wrote:
> Hiya,
>
> On 16/02/2020 11:16, Alexey Melnikov wrote:
>> Dear CFRG participants,
>>
>> This message is starting 2 weeks RGLC on
>> draft-irtf-cfrg-kangarootwelve-01 ("KangarooTwelve"), that will end
>> on March 1st 2020. If you've read the document and think that it is
>> ready (or not ready) for publication as an RFC, please send a message
>> in reply to this email or directly to CFRG chairs
>> ([e-mail]). If you have detailed comments, these would
>> also be very helpful at this point.
> I had my 1st read of this and think it needs a bit of
> work, but am overall unclear if it ought be published
> now. (I also looked back at the list archive messages
> referring to k12.)
>
> I don't think CFRG ought be publishing very novel
> algorithm RFCs and am unclear how much study k12 has
> gotten outside the author team. The main reference
> given [1] has pointers to lots of work with titles that
> mention reduced-round keccak but it's unclear (to me,
> not having read 'em;-) how  relevant those are to k12.

Actually, all cryptanalysis of Keccak/SHA-3 is relevant to K12.
Cryptanalysis resources are scarce, we chose as an explicit design goal
to make K12 rely on cryptanalysis of Keccak/SHA-3.

To be more precise, K12 is made of two layers:

1) The inner function F. This layer relies on cryptanalysis. K12's F
function is exactly Keccak[r=1344, c=256] (as in SHAKE128) reduced to 12
rounds (no tweaks!). Hence, any reduced-round cryptanalysis on Keccak is
also a reduced round cryptanalysis of K12's F (provided the number of
rounds attacked is not higher than 12 of course).

2) The tree hashing over F. This layer is a mode on top of F that does
not introduce any vulnerability thanks to the use of Sakura coding
proven secure in the paper [Bertoni et al., ACNS 2014].

This reasoning is detailed and formalized in the paper [Bertoni et al.,
ACNS 2018], which is peer-reviewed.

> [1] is also used as [KECCAK_CRYPTANALYSIS] in the draft
> and is where the authors are pointing us to find
> security analysis of k12. I don't think an author-
> maintained web page like that is really good enough
> as the key reference for an RFC like this.

Good point indeed!

One option would be that we put all the references in the RFC. We are
not sure this is the right place for it, as we see an RFC more as
implementation guide rather than an analysis paper. For example:
https://tools.ietf.org/html/rfc7748 does not mention anything with
respect to the security of X25519 which is detailed in section 3 of
https://www.iacr.org/cryptodb/archive/2006/PKC/3351/3351.pdf.
Nevertheless, we are open to this option.

Another option would be to refer to [K12, Section 5]. In that section
attacks with the highest number of rounds are discussed and
corresponding paper are referred to. However with the possible
appearance of new cryptanalysis results, this section would become outdated.

> I totally get why the authors would find that
> easier/better, but that won't be true for a reader in
> 20 years time, so better to put in the precise
> references now. That should also clarify the extent to
> which those are about k12 (as defined here) and not
> about something else.
We agree with this, however Keccak cryptanalysis directly applies to K12.
> I think the references really need fixing before this
> ought be published. I'm not sure where the right line
> ought be drawn in terms of maturity of an algorithm
> before CFRG blesses it with an RFC. <4 years does seem
> short, even if this is strongly based on keccak. (Hence
> me being unsure overall.)
For us the maturity amounts to more than 4 years. Being SHA-3, Keccak is
a high-profile cryptanalysis target. As we did not tweak the round
function, K12 relies on sustained cryptanalysis since 2008.
> Separately, the draft could benefit from some guidance
> as to when this is thought to be useful - presumably
> that's when one wants a hash output that's >512 bits.
> IIRC, there are other RFCs (forget numbers, sorry),
> that describe how to get such outputs using standard
> hash functions. If there are such RFCs, it'd be good
> to reference those. Either way saying why and when this
> is preferable to use of standard hash functions would
> be good.
The standard hash functions (SHA-1 and SHA-2) are subject to length
extension attacks. And in all cases, K12 will be faster than SHA-3. If
that makes it clearer, we could add a short guidance as to when the user
can benefit the most from K12. We could simply reuse the arguments from
these slides: https://benoit.viguier.nl/files/K12atMontreal.pdf
> Other than the above, the draft seems clear (though
> I didn't try implement) and many thanks for not
> defining the usual pile of pointless variants/options:-)

Thanks, yes, that was another design goal for K12.

-- 
Kind regards,

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