Message-ID: <CAOqphBeCXVt70FS+Kq9oLhDorSxJX+G=XU2dX6=wXxuFcUogPw@mail.gmail.com>
Date: Tue, 2 Sep 2014 11:48:38 +0530
From: Sweta Mishra <swetam@...td.ac.in>
To: discussions <discussions@...sword-hashing.net>
Subject: Re: [PHC] Response to recent comments on Rig

The internal collisions being reported were known to us at the time of the
design of Rig, and were already handled as explained below. They are NOT a
threat to the security of Rig. We allow inputs to be of arbitrary lengths
in Rig. The first hash input contains the concatenation of password (pwd),
salt (s), 64-bit representation of number of iterations (n) and 64-bit
representation of output length. However, the number of iterations and
output length will be fixed for a specific implementation. We will still
allow variable length password and salt by design. The concern expressed
was for the situation when Rig(pwd_1, salt_1) = Rig(pwd_2, salt_2). To
ensure that such internal collisions do not become a concern, we take the
last hash input as the concatenation of the chaining value and counter along
with the salt and the value m=2^m_cost. On page 14 of our report, it is
mentioned that, "Even if one can find collisions in the first hash
calculations, the attacker can not use it unless the salt is also same."
This design choice will not allow the final outputs of Rig to collide with
effort better than birthday bound. There are few other points that are
raised in another mail and we will address them in couple of few days. We
wish to send a detailed report (along with a revised version of the doc and
code, containing more references as discussed in the mailing list, removal
of the typo etc.). This week, the Rig team members are preoccupied in some
other work and hence please expect the detailed answer by early next week.


Thanks & Regards
Sweta Mishra


On Mon, Sep 1, 2014 at 4:40 PM, Bill Cox <waywardgeek@...hershed.org> wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On 08/31/2014 05:30 PM, Somitra Sanadhya wrote:
> > 4. Another comment by Mr Cox is: "the memory swapping algorithm
> > that the Catena guys invented fairly recently is there..."
> >
> > We would like to know which memory swapping algorithm is being
> > referred to in the above statement ? Catena takes two inputs,
> > hashes the concatenation of these two, and writes the result in
> > some location in the array. On the other hand, Rig does two
> > different memory overwrite operations. In the first one, we use
> > sequential XOR of the chaining variable with the value of the same
> > variable from the previous round at the same location. In the
> > second one, we XOR the chaining variable with the input variable
> > indexed by the bit-reversal permutation from the previous round.
>
> I was wrong here, because I had not noticed your bug yet.  Your
> suggested fix will not work.  To get it to work, you will need to do
> what I though you were doing, and use Catena's trick to use one array
> for KeySet instead of two.
>
> Your suggested fix is to replace:
>
>     k[br(j)] = k[br(j)] XOR truncate(ChainingValue)
>
> with
>
>     k[j] = k[br(j)] XOR truncate(ChainingValue)
>
> This will overwrite the value in position j.  Later, for all values of
> j where br(j) > j, when you read from k[j] to compute k[br(j)], you
> will read the value from the current row, when you meant to read the
> value from the previous row.
>
> Catena's trick is to realize that once you read from k[br(j)], you no
> longer need to remember the value stored in k[br(j)].  Instead of
> writing to k[j], write to k[br(j)], just like your submission does,
> which is why I thought you were using this trick.
>
> On the next row, instead of reading from k[br(j)], you need to read
> from k[j], because the data is already stored in bit-reversal order.
> You will also need to write to k[j], since that is the location no
> longer needed.  You will need different code for the even vs odd row
> updates, but it saves you from having to have two k arrays.
>
> I recommend you use this trick and simply acknowledge it the code
> and/or paper.
>
> I think you have an error in your security proof.
>
> Look at the proof starting on page 16.  In the first line "E1", you
> convert the probability that a value is stored from Pr(value at Pj is
> stored) to i/m.  You simply assume that the probability of the value
> being stored is proportional to the ration of values stored divided by
> the total values, independent of any property of Pr.
>
> If Pr were the identity permutation, an attacker simply needs one
> memory location, and he can compute the entire row sequentially, with
> no recomputations at all.  Clearly there needs to be some mathematical
> property of Pr that we can depend on to avoid this.  A pebbling proof
> like Catena's is needed here.
>
> Bill
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1
>
> iQIcBAEBAgAGBQJUBFQTAAoJEAcQZQdOpZUZRmIQAKZYIOMvATsHn42V+XGv3fNa
> 9KJ9YvMnVtMZY8JMVhaRoFKoHWlWHL3fhOvh1AOOZampWTCKy6DsIqXmjdX6oWqT
> jQLTLbxN6knczRKp8TN5sUO/HCuja71utjOd/wS7qyFLgl9z7gOdWgemmosH5Uyz
> U8O+7SSfsGWKGZQxQwvkfe4fpqy0Kjyct3IjhhY4Os2tOrSqPmPPYNNEL+46gr8E
> bzGcB4KVNVz9jXv2qBdqg0nsoBZWsDonYIa+L6H4nsFSm+EaZNWKy5ocFKbH3y5I
> KLTona7FKsOFFXDlmvoAq2OetoTa6ciXKXls1o9HF0DrwBQ2EYhz9tVKdlqjL2iW
> U6qDgnQP1oWIXECb1CO9DhIyL4Hlpd2hCP3UJH/a7lK+3w/MXP+xuBViPtI/qyrW
> GqnRo/KazwqRvf0dm72+ztD1E9wsSqQYPfnGIWgTXoPrCqOHJuRftUxd55pVKvrt
> RDVA2vcUHpBNcZflQf0WvzRWjRJSzfovx3wHQg/YHFWmJuCMyoP/7amc5HCgvw2G
> 2QBUHMf2ei/aNVzTQFTwvE1Tv8LQCbWNvR5XRkIPQihJL+40RJDkl1/uo6ZLOwof
> 7oLQA7LQeept1YbQj66oXE5t+lljoMFouI4LskM2Y1lWkmGpyvGK6yuBwlXQswhH
> UmMTKHsdgvJZBj8hN1Mg
> =SXWf
> -----END PGP SIGNATURE-----
>

Content of type "text/html" skipped

Powered by blists - more mailing lists