Date: Thu, 12 Feb 2015 20:07:19 +0530
From: Donghoon Chang <pointchang@...il.com>
To: "discussions@...sword-hashing.net" <discussions@...sword-hashing.net>
Subject: Re: [PHC] PHC status report

Dear Stefan,

I wrote my comments in below.

There where also security issues with some of the 14 candidates
which where promoted into the 2nd round. NIST decided which security issues
they considered serious, and which they didn't. Which is perfectly OK, NIST
had to do that.

CubeHash makes an nice example. The 1st-round submission of CubeHash was
both absurdly slow and broken by a preimage attack. It was human judgement
to keep CubeHash in, not neutral facts. Regarding the performance, it was
based on an extremely conservative choice of the security parameters, which
could be fixed. The preimage attack was based on a narrow pipe, and there
appeared no plausible way to push that attack further.

To keep CubeHash in the game, in spite of a clear violation of the original
security requirements, NIST even tweaked these requirements by
re-interpreting them. Approximately 2^512 turned into more than 2^480.

This is no complaint, CubeHash was a more interesting design than most of
the candidates that where kicked out. NIST really did the right thing,
IMHO. But claiming the SHA-3 process has been so much based on scientific
facts is plain wrong.


=> I am also happy that CubeHash was not selected as one of finalists based
on scientific evidences regarding security and performance issues!


Doesn't it bother you that the compression function of Keccak/SHA-3 is not
collision resistant?

NIST decided for some class of candidates (including Keccak, the final
winner) to ignore "pseudo-collisions" (collisions of the compression
function), while the same attack on other candidates was an immediate
killer. This choice is based on judgement, not on scientifically measurable
facts.


=> From the view of the structural soundness of Keccak, the invertibility
of the Keccak permutation is not at issue, because the sponge construction,
which is the domain extension of Keccak, is proved to be collision
resistant, preimage resistant, second preimage resistant, and
indifferentiable in the single stage game in the ideal permutation model.
So, here, a main issue is that it is reasonable to assume that there is no
any non-trivial non-randomness property of the Keccak permutation. So, many
papers tried to analyze the permutation in order to find any non-trivial
non-randomness property. But, fortunately, till now, there is no evidence
that Keccak permutation has non-trivial non-randomness property, though the
ideal permutation model is too strong. Therefore, based on the criteria
such as CR, PR, SPR, etc. , based on security and performance evaluation,
Keccak design has been survived.

=> In case of SHA-2, it was proved that if its compression function is PR
(CR), then SHA-2 is PR (CR). In case of Keccak/SHA-3, it was proved that if
its underlying permutation is ideal, then Keccak/SHA-3 is PR (CR). In this
perspective, the invertibility of internal state of SHA-3 is not issue.

=> As I and Moti showed in the Crypto 2012 rump session (
http://crypto.2012.rump.cr.yp.to/008b781ca9928f2c0d20b91f768047fc.pdf), we
raised an issue of the invertibility of the internal state of Keccak/SHA-3.
If it is used for HMAC-SHA-3, once any internal state of inner hash call is
known to attacker along with a message, then the attacker can find the
secret key. We called it the midgame attack which is a kind of side channel
attack. However, at that time, even now, it might take time to be
considered as  one of new scientific security concept of the
midgame attack.

Except for CubeHash, on both accounts (security and performance).
Interestingly, CubeHash is actually a very elegant and simple design ...


=> I agree with you. Since I was not in the 1st round selection committee,
I do not know how CubeHash was chosen. But, finally, CubeHash was not
selected according to scientific criteria. (See the second round report
regarding who CubeHash failed to satisfy the criteria regarding security
and performance.)

=> As you agree, we should not make any mistake once again. That's why now
I request the PHC panel to take only good aspects of NIST SHA-3 selection
process, by writing a public report and by evaluating each PHC candidate
according to security and performance.

I disagree. Moreover, more half of the 1st-round candidates for SHA-3 have
been broken. This was a much easier choice than in the case of PHC.


=> Yes, you are right that it was easier to narrow from 51 to 14 for the
second-round candidates of SHA-3. But, at least I want to point out that
PHC seems to simply ignore steps like the 1, 2, 3 round procedures (based
only on security and performance) of the SHA-3 competition and directly
jump into the final stage in a similar way that Keccak was chosen from the
five finalists.

- Donghoon

2015-02-12 19:19 GMT+05:30 <Stefan.Lucks@...-weimar.de>:

> On Thu, 12 Feb 2015, Donghoon Chang wrote:
>
>  Let me try to explain how NIST chose 14 candidates from 51 in scientific
>> ways. (At that time, I was
>> not involved in NIST.)  But, it is clear why 14 was chosen based on
>> scientific facts, not based on
>> any kind of elegance concept.
>>
>
> There where also security issues with some of the 14 candidates which
> where promoted into the 2nd round. NIST decided which security issues they
> considered serious, and which they didn't. Which is perfectly OK, NIST had
> to do that.
>
> CubeHash makes an nice example. The 1st-round submission of CubeHash was
> both absurdly slow and broken by a preimage attack. It was human judgement
> to keep CubeHash in, not neutral facts. Regarding the performance, it was
> based on an extremely conservative choice of the security parameters, which
> could be fixed. The preimage attack was based on a narrow pipe, and there
> appeared no plausible way to push that attack further.
>
> To keep CubeHash in the game, in spite of a clear violation of the
> original security requirements, NIST even tweaked these requirements by
> re-interpreting them. Approximately 2^512 turned into more than 2^480.
>
> This is no complaint, CubeHash was a more interesting design than most of
> the candidates that where kicked out. NIST really did the right thing,
> IMHO. But claiming the SHA-3 process has been so much based on scientific
> facts is plain wrong.
>
>  Can you imagine that we would have used SHA-2 without any worry if the
>> compression function of SHA-2 were not collision resistant?
>>
>
> Doesn't it bother you that the compression function of Keccak/SHA-3 is not
> collision resistant?
>
> NIST decided for some class of candidates (including Keccak, the final
> winner) to ignore "pseudo-collisions" (collisions of the compression
> function), while the same attack on other candidates was an immediate
> killer. This choice is based on judgement, not on scientifically measurable
> facts.
>
>  In case of the remaining 14 candidates, there was no any security issue
>> on their underlying primitives and performance-wise there was no extremely
>> slowness.
>>
>
> Except for CubeHash, on both accounts (security and performance).
> Interestingly, CubeHash is actually a very elegant and simple design ...
>
>  Therefore, I don't think that the PHC panel's 9-candidate selecting
>> process is similar to the 14 2-round candidates selection procedure of the
>> SHA-3 project.
>>
>
> I disagree. Moreover, more half of the 1st-round candidates for SHA-3 have
> been broken. This was a much easier choice than in the case of PHC.
>
>
>
> ------  I  love  the  taste  of  Cryptanalysis  in  the morning!  ------
> uni-weimar.de/de/medien/professuren/mediensicherheit/people/stefan-lucks
> --Stefan.Lucks (at) uni-weimar.de, Bauhaus-Universität Weimar, Germany--
>

Content of type "text/html" skipped

Powered by blists - more mailing lists