Date: Tue, 31 Mar 2015 11:11:59 +0800
From: Hongjun Wu <wuhongjun@...il.com>
To: discussions@...sword-hashing.net
Subject: Re: [PHC] Another PHC candidates "mechanical" tests (ROUND2)

Dear Alexander,

First, I'd like to point out that the security of preimage/collision of
Pomelo (and some PHC Second round candidates) is somehow similar to the
security of the initialization of stream ciphers, rather than similar to
the security of hash function in which there is no secret key.

When I was designing POMELO, the first priority is to ensure that the
password cannot be recovered due to collision (it follows from my
experience on the cryptanalysis and design of stream ciphers).  It is the
reason that the first half operations of POMELO are strictly revertible so
as to prevent collision, but to achieve diffusion.

Some confusion/diffusion idea of POMELO partly comes from my stream cipher
HC (i.e., using expansion and table lookups).  Since its publication in
2004, HC remains as a very strong cipher.

Anyway, I will provide more analysis of POMELO in the updated report.

BTW, I think that it is not necessary to use strong crypto primitive (such
as strong hash function) in the design of password  hashing scheme,
especially if we want to process large amount of memory in a fast way.
Eventually it turns out that a number of second round candidates need to
cut the round number significantly.   I feel that it is no longer true that
those PHC candidates are based on strong crypto primitives, although they
are still very strong.

Maybe we can now say that most of the second round candidates are no longer
built on strong crypto primitives (such as strong hash functions or strong
block ciphers) to achieve their security,  not just POMELO itself.


Best Regards,
hongjun


On Tue, Mar 31, 2015 at 4:15 AM, Solar Designer <solar@...nwall.com> wrote:

> On Tue, Mar 31, 2015 at 02:08:34AM +0800, Hongjun Wu wrote:
> > 3)  A strong hash function is not needed for POMELO.
> >      I believe that POMELO  is much stronger than any existing hash
> > function for the KDF/PH applications.
>
> Most likely it is, but the confidence in it is currently lower than e.g.
> in SHA-2 family functions.
>
> > (For performance reason, a strong
> > hash function has to be sufficiently fast and small.  So even in a very
> > strong hash function, not many operations can be used for processing a
> > message block.)
> >      In the POMELO report, I did not talk much about POMELO against
> > preimage and collision attack. I can explain more in the updated report.
> >      When I was designing POMELO v2,  only the memory hardening security
> > worth my analysis.   The preimage and collision security are trivial.
>
> Of course, it's much easier (in fact, trivial as you say) to achieve
> preimage and collision resistance in PHC candidates than in fast
> cryptographic hashes.  The problem, though, is that "much easier" and
> even "trivial" do not necessarily imply "has been achieved".
>
> If you tried to, I think you would be able to deliberately construct a
> PHC candidate that would appear OK at first glance, but would not be
> preimage or/and collision resistant.  Right?  And this might happen
> unintentionally, too.
>
> > Simply speaking, the state size of POMELO is too large comparing to a
> hash
> > function, and the operations used in a cryptographic hash function
> > (compression function) is much less than that used in POMELO.
> >      Some example: considering SHA-512, there are only 64+64 = 128 simple
> > steps to compress a 128-byte message (if we consider message expansion as
> > 64 steps); while in POMELO v2, there are about 3*256 = 768 steps when
> > m_cost = 0, t_cost = 0.     In POMELO v2, in order to prevent password
> > hashing being too fast, it is required that m_cost + t_cost >= 5.  It
> means
> > that POMELO v2 consists of at least 32*256+512 = 8704 steps, far more
> than
> > that in a compression function of SHA-512.
>
> Simply comparing the number of operations is not convincing enough.
> For example, what if most of those cancel out, or are reversible, or if
> there are tiny biases that add up to something significant after so many
> steps?  This is almost certainly not the case, but until shown otherwise
> the possibilities are there.
>
> A more realistic risk is issues with how the password and salt inputs
> are processed early on.  Things like the original bcrypt $2$'s trivial
> collisions for "ab" vs. "abab", etc.
>
> I think it's reasonable that people want an analysis of POMELO's basic
> security.
>
> Alexander
>

Content of type "text/html" skipped

Powered by blists - more mailing lists