Hi folks,

Just wanted to say that the bug is not really a bug, in the following sense: For the Shamir based protocol to be secure, the field size MUST be bigger than than the number of players. If this is not the case, either a player would be assigned the point 0, or two players would be assigned the same point. In either case, the protocol is insecure. So that line of code is fine, provided the runtime
checks that the field or fields you use are  large enough and refuses to
run if not. If this check is not done, that's where the bug is instead :-)


regards, Ivan


On 21/04/2010, at 14.42, Janus Dam Nielsen wrote:

Hi VIFF'ers

I think I have found a bug in the Shamir code

In the following function:
def share(secret, threshold, num_players):
assert threshold >= 0 and threshold < num_players, "Threshold out of range"

    coef = [secret]
    for j in range(threshold):
        # TODO: introduce a random() method in FieldElements so that
        # this wont have to be a long when we are sharing a
        # GMPIntegerFieldElement.
        coef.append(rand.randint(0, long(secret.modulus)-1))

    shares = []
    for i in range(1, num_players+1):
        # Instead of calculating s_i as
        #
        #   s_i = s + a_1 x_i + a_2 x_i^2 + ... + a_t x_i^t
        #
        # we avoid the exponentiations by calculating s_i by
        #
        #   s_i = s + x_i (a_1 + x_i (a_2 + x_i ( ... (a_t) ... )))
        #
        # This is a little faster, even for small n and t.
        cur_point = secret.field(i)
        cur_share = coef[threshold]
        # Go backwards from threshold-1 down to 0
        for j in range(threshold-1, -1, -1):
            cur_share = coef[j] + cur_share * cur_point

        shares.append((cur_point, cur_share))

    return shares


The bug is this line:
        cur_point = secret.field(i)

If the number of player exceed the size of the field then the function returns the wrong id (cur_point)?

Anybody see anything wrong in this patch:
+++ b/viff/viff/passive.py
@@ -542,10 +542,10 @@
                 shares = shamir.share(field(number), threshold,
                                       self.num_players)
                 for other_id, share in shares:
-                    if other_id.value == self.id:
+                    if other_id == self.id:
results.append(Share(self, share.field, share))
                     else:
- self.protocols[other_id.value].sendShare (pc, share)
+                        self.protocols[other_id].sendShare(pc, share)
             else:
                 results.append(self._expect_share(peer_id, field))

diff --git a/viff/viff/shamir.py b/viff/viff/shamir.py
--- a/viff/viff/shamir.py
+++ b/viff/viff/shamir.py
@@ -72,7 +72,7 @@
         #   s_i = s + x_i (a_1 + x_i (a_2 + x_i ( ... (a_t) ... )))
         #
         # This is a little faster, even for small n and t.
-        cur_point = secret.field(i)
+        cur_point = i
         cur_share = coef[threshold]
         # Go backwards from threshold-1 down to 0
         for j in range(threshold-1, -1, -1):


____________________________________________________

Janus Dam Nielsen

Research and Innovationspecialist, PhD.
CENTRE FOR IT-SECURITY

THE ALEXANDRA INSTITUTE LTD.

T +45 40 83 09 10
E janus.niel...@alexandra.dk
W alexandra.dk

See our blog about security at blog.sikkerhed.alexandra.dk
____________________________________________________

_______________________________________________
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

_______________________________________________
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Reply via email to