Date: Thu, 2 Oct 2014 14:23:07 +0200
From: Dmitry Khovratovich <khovratovich@...il.com>
To: "discussions@...sword-hashing.net" <discussions@...sword-hashing.net>
Subject: Re: [PHC] Design Rationale and Security Analysis of PHC candidates

Thank you, Thomas,

This is a good example of a reductionist proof. I am ready to update the
table if you put this into a separate note. The issue with Rabin padding is
particularly relevant and deserves such a document.

Dmitry

On Thu, Oct 2, 2014 at 2:02 PM, Thomas Pornin <pornin@...et.org> wrote:

> On Thu, Oct 02, 2014 at 12:50:31PM +0200, Dmitry Khovratovich wrote:
> > The value "Explored" stands for the case when the designers actually try
> to
> > mount a collision/preimage attack on their design and show why it fails.
> It
> > is not the best possible option: ideally, one would provide some sort of
> > security proof that reduces the security of the mode of operation (which
> > the hashing scheme is) to the security of the underlying primitive, and
> > thus get the grade "Verified" or "Proven".
>
> In that case, I'll claim that "proven" status for Makwa.
>
> Without pre-hashing or post-hashing:
>
>   The Makwa core really is Rabin encryption, followed by many squarings.
>   Since the Rabin encryption output is a quadratic residue, and squaring
>   is a permutation of quadratic residues (when working modulo a Blum
>   integer), then it follows that any preimage attack against Makwa is
>   also a preimage attack against Rabin encryption (see note 2 below).
>   Rabin encryption is the "underlying primitive", still unbroken after
>   more than three decades of exposure in the field.
>
>   As for collisions: since the squarings are a permutation, only the
>   very first squaring may induce a collision. However, if there is a
>   collision, then you get two values x and y such that x^2 = y^2 modulo
>   N. Moreover, since the most significant bit of both values are zero,
>   it cannot be that x = -y. Then it follows that gcd(x+y,N) reveals a
>   non-trivial factor of N. Thus, finding a collision for Makwa (without
>   post-hashing) implies factoring N, which is known to be hard.
>
>   Note that the arguments above don't rely on any property of the salt.
>   It could be entirely under attacker's control; it would not change
>   anything here.
>
> With pre-hashing or post-hashing:
>
>   Makwa is a sequence of three elements: the pre-hash, the squarings,
>   and the post-hash. When considering a combination of successive
>   functions, it is rather obvious that:
>    - any preimage attack on the combination implies a preimage attack
>      on the last step;
>    - any collision attack on the combination implies a collision
>      atack on at least one of the steps.
>   We saw above that the middle step of Makwa (the squarings) is
>   resistant to both preimages and collisions (regardless of the
>   attacker's control on the salt). Thus, Makwa, in all generality, is
>   resistant to both preimages and collisions as long as the "hash
>   function" used for the pre-hashing and post-hashing step is also
>   resistant to collisions (note that the salt is not used for
>   pre-hashing and post-hashing).
>
>   However, that hash function is HMAC_DRBG, a well-known primitive which
>   has been proven to be "perfect" (indistinguishable from a random
>   oracle) as long as the underlying HMAC lives up to its promises (the
>   references are in the Makwa spec).
>
> One design principle of Makwa was to rely on existing, "proven"
> primitives (at least proven through years of exposure, though any kind
> of reduction proof is also nice to have).
>
>
>
> Note 1: you can still botch things by using post-hashing to get a
> deliberately short output; e.g. with 80 bits of output, resistance to
> preimages cannot exceed 2^80, and 2^40 for collisions. But mind the
> details:
>
>  - This "2^80" is counted in a number of evaluations of the underlying
>    function, which is designed to be slow. That does not translate to
>    the usual "2^80 simple operations" or "2^80 invocations of MD5".
>
>  - If an attacker is allowed to run 2^80 operations, then he can guess
>    the password, because we are hashing passwords, and it would not be
>    wise to claim that passwords offer 80 bits of entropy.
>
>  - Collisions are an issue for password hashing only in the context of
>    rather esoteric scenarios involving some underspecified extra bug. I
>    never found that convincing in any way; for me, resistance to
>    collisions is irrelevant to password hashing. However, if you worry
>    about collisions, then you can just ask for a twice longer output:
>    HMAC_DRBG can produce as many bytes as you wish.
>
>  - This point about output length is completely generic: it applies to
>    _all_ password hashing functions.
>
>
> Note 2: there is still one delicate point about Rabin encryption.
> Contrary to RSA, it was never specified with a RFC or a similar
> standard. In particular, the "padding" step was not specified. It is
> also known that while extracting square roots modulo N is _in general_
> equivalent to factoring N, square root extraction for some values can be
> easy: namely if x^2 < N (as integers), then the square root of x^2
> modulo N is also the square root of the natural integer x^2, i.e. x.
> This is a well-known property which also applies to RSA (with cubic
> roots for RSA with e=3). This is the reason why the PKCS#1 padding,
> defined for RSA, ensures that there are some non-zero bits in the most
> significant positions. The padding used in Makwa is very similar to the
> PKCS#1 padding, for pretty much the same reasons. In that sense, Makwa
> is as strong as Rabin encryption would be, if Rabin encryption was
> specified with PKCS#1 padding.
>
> To be more formal, I _define_ Rabin encryption to consist in the following:
>
>  - Pad input message m to a sequence x of the same length of N:
>
>     x = 0x00 || rrrrrr || m || len(m)
>
>    where len(m) is the length of m in bytes (expressed over a single byte),
>    and "rrrrrr" is a sequence of random bytes of suitable length (so that
>    the length of x equals that of N). There are at least 30 random bytes.
>
>  - The encrypted message is x^2 mod N (x is interpreted as an integer with
>    the big-endian convention).
>
> I claim that this instanciation of Rabin encryption is a faithful
> practical incarnation of "the" Rabin encryption scheme which has been
> studied at length by cryptographers. This is my underlying primitive.
>
> Makwa replaces the "random rrrrrr" with the deterministically generated
> bytes produced by HMAC_DRBG, but this is equivalent (from an attacker's
> point of view) because HMAC_DRBG is indistinguishable from a random
> oracle (see above).
>
>
> (I agree that this analysis is not well explained in the Makwa
> specification.)
>
>
>         --Thomas Pornin
>



-- 
Best regards,
Dmitry Khovratovich

Content of type "text/html" skipped

Powered by blists - more mailing lists