Message-ID: <CAEBvHX=68_4AAt9DMW+X8NeMhLcqCR1Apeu0sswt=HMyU5Z90A@mail.gmail.com>
Date: Mon, 1 Sep 2014 03:00:21 +0530
From: Somitra Sanadhya <somitra@...td.ac.in>
To: discussions@...sword-hashing.net
Subject: Response to recent comments on Rig

Dear PHC discussion forum members,

We would like to comment on the recent comments of Mr Bill Cox on our
design "Rig" in PHC discussions forum on Date: 2014-08-29 22:01:07 GMT and
Date:2014-08-31 03:52:28 GMT.

While one issue he points out is correct (only due to a typo in our
design), all the remaining ones are wrong and a few do not show the level
of professionalism expected at this level. We, the designers of Rig, want
to bring certain issues to the attention of the forum and the panel
organizing the PHC. These are detailed in the following 8 bullet points:

1. Our report repeatedly mentions the usage of bit-reversal permutation,
but the corresponding step (Step 19) in Algorithm 1 had a typo. We typed
"k[br[j]] = k[br[j] \oplus ...." while it should have been "k[j] = k[br[j]]
\oplus ..." The present form of the update is NOT using the bit reversal
permutation (although we repeatedly claim the usage of the same in our
report) since memory at one location is being affected by the value at the
same location. Since Figure 1 and the reference code both used Algorithm 1
as the reference, the error continues in them. We wish to request the PHC
panel to allow us to revise our submission with this error rectified.

Note that our analysis of the design already assumed that the bit-reversal
permutation is present and hence the exponential memory hardening of the
design is achieved. Without the bit reversal, we only achieve quadratic
memory hardening (same as scrypt) and this could not have been our
intention. Note that the mail by Mr Cox (Date: 2014-08-31 03:52:28 GMT)
uses our design with this typo error to show an attack on it. This attack
is not present on the actual design when the typo is rectified as the
complexity of the attack becomes exponential as mentioned above.

Now we discuss other (wrong or inappropriate) comments by Mr Cox on our
design in the remainder of this mail.

2. Comment: "here's a statement in the RIG paper:
"Therefore, it is recommended in [6] to have password-independent
memory access patterns for a password hashing scheme. We have
attempted to follow this requirement using bit reversal permutation."
Why not credit Catena for the bit reversal pattern while they were at
it?"

Response: Before the password hashing competition started, the only known
designs (apart from bcrypt and scrypt) were Catena and Lyra. Catena was
uploaded on Cryptology ePrint Archive on 30th August 2013 as Report
2013/525. Similarly, Lyra was available on the same archive from 12th Jan
2014 as Report 2014/030. As responsible designers and academic researchers
in the field of Cryptology, we actively read the two design documents. The
influence of all the previously known designs is obvious in many
submissions to this competition (e.g. Keccak). This is as should be
expected in any field of research.

While mentioning the bit-reversal permutation, we did mention that the idea
of the same was from Catena, and mentioned it as reference [6] in our
submission report. Little did we realize that someone would resort to
accusing us with statements like "However, it's offensive to use other's
ideas and pretend they are your own." If someone thinks that ideas are not
acknowledged then we would like to offer the following minor change in our
report:

Current statement: "Therefore, it is recommended in [6] to have
password-independent memory access patterns for a password hashing scheme.
We have attempted to follow this requirement using bit reversal
permutation."

Revised version: "Therefore, it is recommended in [6] to have
password-independent memory access patterns for a password hashing scheme.
We have attempted to follow this requirement using bit reversal
permutation, as suggested in [6]."

We felt that this was obvious for anyone reading both [6] and Rig that this
was the case. However, to clarify any doubts, we offer to specifically add
the reference to Catena not only in the first sentence (where it is already
present), but in the second sentence as well. The charge of taking
someone's idea is clearly wrong.

3. The mail of Mr Cox accuses us of copying the hash function of Lyra2,
with the following comment: "Their hash matches Lyra2's stripped-down
Blake2b round character-for-character... hopefully just copied from the
same paper, but surely they got they idea from Lyra2, and those guys aren't
even in the bibliography."

This is patently false. First of all, the bibliography already mentions
Lyra, a design already available publicly before the start of PHC
submission (Lyra2 is parallel submission and we could not have known of it
while submitting our design). In fact, not only is Lyra in the
bibliography, it is the "first" reference in the bibliography ! Blake2b is
referenced in [7].

Further, the only difference in Blake2b and the stripped down version used
in our code is the removal of G function in our design. The designers of
Blake2b already suggested (in their design document) the removal of
function G for efficiency reasons. Our report has the following comment on
Page 12: "As per the authors of [7], the G-function of Blake2b can be
simplified by omitting the constants in G. This change improves the
performance and is the one we have implemented in our code."

It so happens that both we and the designers of Lyra followed this advice
from the designers of Blake2b and used Blake2b without the G function.
Consequently, it is only to be expected that the outputs of the two hash
functions match "stripped-down Blake2b round character-for-character".

Finally, our report already mentions (on Page 6) that "We use Blake2b [7]
in demonstrating the performance of our scheme later in this report,
although any other hash function could easily be used instead."

Specifically, Blake2b was used to facilitate comparison with publicly known
design "Lyra" available at the time when we were preparing our report.
Interestingly, a total of 6 PHC candidate designs choose Blake2 as the
underlying hash function ! These are (1) Catena, (2) Lanarea, (3) Lyra and
Lyra 2, (4) Rig, (5) TwoCats, (6) Yarn. The list of users of Blake2 is
available at https://blake2.net/ which includes these PHC candidates.

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.

In addition, this is a meaningless comment. Memory XORs and chaining are
standard ideas used everywhere in Symmetric cryptography.

5. Another comment is that "The XOR-ing over memory is an idea from Gambit
that we talked about quite a bit".

We would like to clarify that any person with a basic introduction to
Cryptographic designs should have known that XORing of data to randomize
outputs is a standard cryptographic technique. This can be seen in
countless encryption designs, hash function designs, modes of operations,
... etc. Obviously, there is no need to clarify this to a person with some
background in Cryptography. The fact that this idea appealed to us and we
used is because we (all the designers of Rig) come from Crypto background.

However, there is a bigger issue in the accusation above. Gambit is a
parallel submission to PHC and we could not have known of its existence and
possible usage of XOR for randomization. In fact, accusations such as this
make us feel that the commentator is biased and wishes to criticize our
design arbitrarily.

6. Another comment is: "The paper and code are all original (mostly), so
there's no plagiarism here."

This comment is once again insulting. It attempts to reinforce the false
notion that our design is a copy of other designs.

7. Mr Cox suggest us a "rewrite of their paper to be less dick-ish."

We would have liked the academic discourse to remain civil. Such language
was not expected in a public forum. We view this sentence very seriously.

8. Here is the first paragraph of the mail of Mr Cox copied verbatim from
his mail:
"As far as I can tell, RIG is a quick rewrite of Catena, using Lyra2's
hash function, and Gambit's XOR-ing over data.  The combination is
original, but that's all.  If the paper said, "We have combined these
three good ideas and thing the result is superior", then I would be OK
with it.  For example, someone needs to plug Lyra2's ultra-fast sponge
into Gambit.  Mixing ideas is fine.  I just think it's weird pasting
three ideas from the forum together without crediting the sources
properly.  It almost seems like they attempted to obfuscate their
sources.  The paper and code are all original (mostly), so there's no
plagiarism here.  You can't copyright an idea.  However, it's
offensive to use other's ideas and pretend they are your own.  All
that is needed to fix RIG, IMO, is some proper credit to where they
got their ideas, and a rewrite of their paper to be less dick-ish."

The above paragraph presents us in poor light and appears to bring our
design to disrepute. As any responsible designer, we went through all the
relevant material we could go through before the submission to PHC. In
fact, we studied bcrypt, scrypt, Lyra and Catena; all these designs were
available in public domain at the time of writing of our report. All four
are present in the bibliography of our report. We have no doubt that our
design has been influenced by the choices made by these four designs, but
isn't that how academic research happens (and in our humble opinion,
"should" happen) ?  Just because we use Blake2b in the manner suggested by
the designers of Blake2b, we are being accused of copying Lyra2 (which was
not even known publicly at the time of our submission, only its previous
version Lyra was known). The designers of Lyra/Lyra2 also used the same
suggestion of the designers of Blake2b as us. Further, as mentioned earlier
in this mail, Gambit design was not even known at the time of submission of
our design. We also remind the mailing list members that 6 designs in PHC
use Blake2b. The list is already provided in this mail.

The statements above are akin to criticizing an instance of OAEP-RSA for
using RSA by the famous RSA, the MD4/5 construction by Rivest and XOR as in
one time pad. To us, this appears quite a stretch of imagination to blame
us for "plagiarism". We have referenced the earlier designs where
appropriate in our report and if there was any doubt in anyone's mind, we
can certainly add a few sentences more in the documentation, but blatant
criticism such as the one above is biased, irrational and arbitrary.
Specifically, the original post is quite defamatory in its tone.

Further, this is important to note that use of rather colorful language
that Mr Cox has chosen in his mail is something we have never encountered
in our professional life as academicians working in the broad area of
Symmetric Cryptography. To us, it seems quite an embarrassing use of
language on a public forum involving designers of Crypto algorithms.

Maintaining a neutral position as a commentator is important for analyzing
schemes. We would rather appreciate someone talking about good and bad
points of designs in a objective way, rather than expressing personal
opinions. In our humble view, research does not progress by someone's likes
or dislikes. In case of any doubt on a serious issue such as plagiarism,
the right approach should have been to approach the designers first and ask
for their clarification.

PS: We would like to encourage and participate in research and analysis of
Cryptographic algorithms and their usage in applications such as password
hashing. However, such posts on the forum do not increase our enthusiasm
for the same.

Regards,
Somitra (on behalf of the Rig team: Chang, Jati, Mishra and Sanadhya)

---
Somitra Kr Sanadhya, PhD.
Asst. Prof., IIIT-Delhi
https://sites.google.com/a/iiitd.ac.in/somitra/
<http://www.iiitd.edu.in/~somitra>

Content of type "text/html" skipped

Powered by blists - more mailing lists