diff options
author | Florian Dold <florian.dold@gmail.com> | 2015-12-11 19:19:47 +0000 |
---|---|---|
committer | Florian Dold <florian.dold@gmail.com> | 2015-12-11 19:19:47 +0000 |
commit | 94c458d11dc2322a3e90eebbbe9a123220440a69 (patch) | |
tree | 2dcdf548bcd47ee3c447975f4b463b3e74ea882e /src/set | |
parent | 2718db6f29c81df70171b1f5488a068cc7650c72 (diff) | |
download | gnunet-94c458d11dc2322a3e90eebbbe9a123220440a69.tar.gz gnunet-94c458d11dc2322a3e90eebbbe9a123220440a69.zip |
Proper salting for set union.
Diffstat (limited to 'src/set')
-rw-r--r-- | src/set/gnunet-service-set_protocol.h | 21 | ||||
-rw-r--r-- | src/set/gnunet-service-set_union.c | 90 |
2 files changed, 88 insertions, 23 deletions
diff --git a/src/set/gnunet-service-set_protocol.h b/src/set/gnunet-service-set_protocol.h index eee0dc5ae..b96ea0889 100644 --- a/src/set/gnunet-service-set_protocol.h +++ b/src/set/gnunet-service-set_protocol.h | |||
@@ -96,6 +96,27 @@ struct IBFMessage | |||
96 | }; | 96 | }; |
97 | 97 | ||
98 | 98 | ||
99 | struct InquiryMessage | ||
100 | { | ||
101 | /** | ||
102 | * Type: #GNUNET_MESSAGE_TYPE_SET_UNION_P2P_IBF | ||
103 | */ | ||
104 | struct GNUNET_MessageHeader header; | ||
105 | |||
106 | /** | ||
107 | * Salt used when hashing elements for this inquiry. | ||
108 | */ | ||
109 | uint32_t salt GNUNET_PACKED; | ||
110 | |||
111 | /** | ||
112 | * Reserved, set to 0. | ||
113 | */ | ||
114 | uint32_t reserved GNUNET_PACKED; | ||
115 | |||
116 | /* rest: inquiry IBF keys */ | ||
117 | }; | ||
118 | |||
119 | |||
99 | /** | 120 | /** |
100 | * During intersection, the first (and possibly second) message | 121 | * During intersection, the first (and possibly second) message |
101 | * send it the number of elements in the set, to allow the peers | 122 | * send it the number of elements in the set, to allow the peers |
diff --git a/src/set/gnunet-service-set_union.c b/src/set/gnunet-service-set_union.c index 4cba00eb0..c8f3ba24b 100644 --- a/src/set/gnunet-service-set_union.c +++ b/src/set/gnunet-service-set_union.c | |||
@@ -172,6 +172,16 @@ struct OperationState | |||
172 | * Hashes for elements that we have demanded from the other peer. | 172 | * Hashes for elements that we have demanded from the other peer. |
173 | */ | 173 | */ |
174 | struct GNUNET_CONTAINER_MultiHashMap *demanded_hashes; | 174 | struct GNUNET_CONTAINER_MultiHashMap *demanded_hashes; |
175 | |||
176 | /** | ||
177 | * Salt that we're using for sending IBFs | ||
178 | */ | ||
179 | uint32_t salt_send; | ||
180 | |||
181 | /** | ||
182 | * Salt for the IBF we've received and that we're currently decoding. | ||
183 | */ | ||
184 | uint32_t salt_receive; | ||
175 | }; | 185 | }; |
176 | 186 | ||
177 | 187 | ||
@@ -334,18 +344,13 @@ fail_union_operation (struct Operation *op) | |||
334 | * a salt. | 344 | * a salt. |
335 | * | 345 | * |
336 | * @param src the hash code | 346 | * @param src the hash code |
337 | * @param salt salt to use | ||
338 | * @return the derived IBF key | 347 | * @return the derived IBF key |
339 | */ | 348 | */ |
340 | static struct IBF_Key | 349 | static struct IBF_Key |
341 | get_ibf_key (const struct GNUNET_HashCode *src, | 350 | get_ibf_key (const struct GNUNET_HashCode *src) |
342 | uint16_t salt) | ||
343 | { | 351 | { |
344 | struct IBF_Key key; | 352 | struct IBF_Key key; |
345 | 353 | uint16_t salt = 0; | |
346 | /* FIXME: Ensure that the salt is handled correctly. | ||
347 | This is a quick fix so that consensus works for now. */ | ||
348 | salt = 0; | ||
349 | 354 | ||
350 | GNUNET_CRYPTO_kdf (&key, sizeof (key), | 355 | GNUNET_CRYPTO_kdf (&key, sizeof (key), |
351 | src, sizeof *src, | 356 | src, sizeof *src, |
@@ -396,7 +401,7 @@ op_has_element (struct Operation *op, | |||
396 | int ret; | 401 | int ret; |
397 | struct IBF_Key ibf_key; | 402 | struct IBF_Key ibf_key; |
398 | 403 | ||
399 | ibf_key = get_ibf_key (element_hash, op->spec->salt); | 404 | ibf_key = get_ibf_key (element_hash); |
400 | ret = GNUNET_CONTAINER_multihashmap32_get_multiple (op->state->key_to_element, | 405 | ret = GNUNET_CONTAINER_multihashmap32_get_multiple (op->state->key_to_element, |
401 | (uint32_t) ibf_key.key_val, | 406 | (uint32_t) ibf_key.key_val, |
402 | op_has_element_iterator, | 407 | op_has_element_iterator, |
@@ -429,7 +434,7 @@ op_register_element (struct Operation *op, | |||
429 | struct IBF_Key ibf_key; | 434 | struct IBF_Key ibf_key; |
430 | struct KeyEntry *k; | 435 | struct KeyEntry *k; |
431 | 436 | ||
432 | ibf_key = get_ibf_key (&ee->element_hash, op->spec->salt); | 437 | ibf_key = get_ibf_key (&ee->element_hash); |
433 | k = GNUNET_new (struct KeyEntry); | 438 | k = GNUNET_new (struct KeyEntry); |
434 | k->element = ee; | 439 | k->element = ee; |
435 | k->ibf_key = ibf_key; | 440 | k->ibf_key = ibf_key; |
@@ -441,6 +446,30 @@ op_register_element (struct Operation *op, | |||
441 | } | 446 | } |
442 | 447 | ||
443 | 448 | ||
449 | static void | ||
450 | salt_key (const struct IBF_Key *k_in, | ||
451 | uint32_t salt, | ||
452 | struct IBF_Key *k_out) | ||
453 | { | ||
454 | int s = salt % 64; | ||
455 | uint64_t x = k_in->key_val; | ||
456 | x = (x >> s) | (x << (64 - s)); | ||
457 | k_out->key_val = x; | ||
458 | } | ||
459 | |||
460 | |||
461 | static void | ||
462 | unsalt_key (const struct IBF_Key *k_in, | ||
463 | uint32_t salt, | ||
464 | struct IBF_Key *k_out) | ||
465 | { | ||
466 | int s = -(salt % 64); | ||
467 | uint64_t x = k_in->key_val; | ||
468 | x = (x >> s) | (x << (64 - s)); | ||
469 | k_out->key_val = x; | ||
470 | } | ||
471 | |||
472 | |||
444 | /** | 473 | /** |
445 | * Insert a key into an ibf. | 474 | * Insert a key into an ibf. |
446 | * | 475 | * |
@@ -455,13 +484,15 @@ prepare_ibf_iterator (void *cls, | |||
455 | { | 484 | { |
456 | struct Operation *op = cls; | 485 | struct Operation *op = cls; |
457 | struct KeyEntry *ke = value; | 486 | struct KeyEntry *ke = value; |
487 | struct IBF_Key salted_key; | ||
458 | 488 | ||
459 | LOG (GNUNET_ERROR_TYPE_DEBUG, | 489 | LOG (GNUNET_ERROR_TYPE_DEBUG, |
460 | "[OP %x] inserting %lx (hash %s) into ibf\n", | 490 | "[OP %x] inserting %lx (hash %s) into ibf\n", |
461 | (void *) op, | 491 | (void *) op, |
462 | (unsigned long) ke->ibf_key.key_val, | 492 | (unsigned long) ke->ibf_key.key_val, |
463 | GNUNET_h2s (&ke->element->element_hash)); | 493 | GNUNET_h2s (&ke->element->element_hash)); |
464 | ibf_insert (op->state->local_ibf, ke->ibf_key); | 494 | salt_key (&ke->ibf_key, op->state->salt_send, &salted_key); |
495 | ibf_insert (op->state->local_ibf, salted_key); | ||
465 | return GNUNET_YES; | 496 | return GNUNET_YES; |
466 | } | 497 | } |
467 | 498 | ||
@@ -585,6 +616,7 @@ send_ibf (struct Operation *op, | |||
585 | msg->reserved = 0; | 616 | msg->reserved = 0; |
586 | msg->order = ibf_order; | 617 | msg->order = ibf_order; |
587 | msg->offset = htons (buckets_sent); | 618 | msg->offset = htons (buckets_sent); |
619 | msg->salt = htonl (op->state->salt_send); | ||
588 | ibf_write_slice (ibf, buckets_sent, | 620 | ibf_write_slice (ibf, buckets_sent, |
589 | buckets_in_message, &msg[1]); | 621 | buckets_in_message, &msg[1]); |
590 | buckets_sent += buckets_in_message; | 622 | buckets_sent += buckets_in_message; |
@@ -879,6 +911,7 @@ decode_and_send (struct Operation *op) | |||
879 | "# of IBF retries", | 911 | "# of IBF retries", |
880 | 1, | 912 | 1, |
881 | GNUNET_NO); | 913 | GNUNET_NO); |
914 | op->state->salt_send++; | ||
882 | if (GNUNET_OK != | 915 | if (GNUNET_OK != |
883 | send_ibf (op, next_order)) | 916 | send_ibf (op, next_order)) |
884 | { | 917 | { |
@@ -920,19 +953,21 @@ decode_and_send (struct Operation *op) | |||
920 | } | 953 | } |
921 | if (1 == side) | 954 | if (1 == side) |
922 | { | 955 | { |
923 | send_offers_for_key (op, key); | 956 | struct IBF_Key unsalted_key; |
957 | unsalt_key (&key, op->state->salt_receive, &unsalted_key); | ||
958 | send_offers_for_key (op, unsalted_key); | ||
924 | } | 959 | } |
925 | else if (-1 == side) | 960 | else if (-1 == side) |
926 | { | 961 | { |
927 | struct GNUNET_MQ_Envelope *ev; | 962 | struct GNUNET_MQ_Envelope *ev; |
928 | struct GNUNET_MessageHeader *msg; | 963 | struct InquiryMessage *msg; |
929 | 964 | ||
930 | /* It may be nice to merge multiple requests, but with CADET's corking it is not worth | 965 | /* It may be nice to merge multiple requests, but with CADET's corking it is not worth |
931 | * the effort additional complexity. */ | 966 | * the effort additional complexity. */ |
932 | ev = GNUNET_MQ_msg_header_extra (msg, | 967 | ev = GNUNET_MQ_msg_extra (msg, |
933 | sizeof (struct IBF_Key), | 968 | sizeof (struct IBF_Key), |
934 | GNUNET_MESSAGE_TYPE_SET_UNION_P2P_INQUIRY); | 969 | GNUNET_MESSAGE_TYPE_SET_UNION_P2P_INQUIRY); |
935 | 970 | msg->salt = htonl (op->state->salt_receive); | |
936 | memcpy (&msg[1], | 971 | memcpy (&msg[1], |
937 | &key, | 972 | &key, |
938 | sizeof (struct IBF_Key)); | 973 | sizeof (struct IBF_Key)); |
@@ -986,6 +1021,7 @@ handle_p2p_ibf (void *cls, | |||
986 | "Creating new ibf of size %u\n", | 1021 | "Creating new ibf of size %u\n", |
987 | 1 << msg->order); | 1022 | 1 << msg->order); |
988 | op->state->remote_ibf = ibf_create (1<<msg->order, SE_IBF_HASH_NUM); | 1023 | op->state->remote_ibf = ibf_create (1<<msg->order, SE_IBF_HASH_NUM); |
1024 | op->state->salt_receive = ntohl (msg->salt); | ||
989 | if (NULL == op->state->remote_ibf) | 1025 | if (NULL == op->state->remote_ibf) |
990 | { | 1026 | { |
991 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | 1027 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, |
@@ -1004,7 +1040,8 @@ handle_p2p_ibf (void *cls, | |||
1004 | else if (op->state->phase == PHASE_EXPECT_IBF_CONT) | 1040 | else if (op->state->phase == PHASE_EXPECT_IBF_CONT) |
1005 | { | 1041 | { |
1006 | if ( (ntohs (msg->offset) != op->state->ibf_buckets_received) || | 1042 | if ( (ntohs (msg->offset) != op->state->ibf_buckets_received) || |
1007 | (1<<msg->order != op->state->remote_ibf->size) ) | 1043 | (1<<msg->order != op->state->remote_ibf->size) || |
1044 | (ntohl (msg->salt) != op->state->salt_receive)) | ||
1008 | { | 1045 | { |
1009 | GNUNET_break_op (0); | 1046 | GNUNET_break_op (0); |
1010 | fail_union_operation (op); | 1047 | fail_union_operation (op); |
@@ -1268,6 +1305,7 @@ handle_p2p_inquiry (void *cls, | |||
1268 | struct Operation *op = cls; | 1305 | struct Operation *op = cls; |
1269 | const struct IBF_Key *ibf_key; | 1306 | const struct IBF_Key *ibf_key; |
1270 | unsigned int num_keys; | 1307 | unsigned int num_keys; |
1308 | struct InquiryMessage *msg; | ||
1271 | 1309 | ||
1272 | /* look up elements and send them */ | 1310 | /* look up elements and send them */ |
1273 | if (op->state->phase != PHASE_INVENTORY_PASSIVE) | 1311 | if (op->state->phase != PHASE_INVENTORY_PASSIVE) |
@@ -1276,9 +1314,9 @@ handle_p2p_inquiry (void *cls, | |||
1276 | fail_union_operation (op); | 1314 | fail_union_operation (op); |
1277 | return; | 1315 | return; |
1278 | } | 1316 | } |
1279 | num_keys = (ntohs (mh->size) - sizeof (struct GNUNET_MessageHeader)) | 1317 | num_keys = (ntohs (mh->size) - sizeof (struct InquiryMessage)) |
1280 | / sizeof (struct IBF_Key); | 1318 | / sizeof (struct IBF_Key); |
1281 | if ((ntohs (mh->size) - sizeof (struct GNUNET_MessageHeader)) | 1319 | if ((ntohs (mh->size) - sizeof (struct InquiryMessage)) |
1282 | != num_keys * sizeof (struct IBF_Key)) | 1320 | != num_keys * sizeof (struct IBF_Key)) |
1283 | { | 1321 | { |
1284 | GNUNET_break_op (0); | 1322 | GNUNET_break_op (0); |
@@ -1286,10 +1324,14 @@ handle_p2p_inquiry (void *cls, | |||
1286 | return; | 1324 | return; |
1287 | } | 1325 | } |
1288 | 1326 | ||
1289 | ibf_key = (const struct IBF_Key *) &mh[1]; | 1327 | msg = (struct InquiryMessage *) mh; |
1328 | |||
1329 | ibf_key = (const struct IBF_Key *) &msg[1]; | ||
1290 | while (0 != num_keys--) | 1330 | while (0 != num_keys--) |
1291 | { | 1331 | { |
1292 | send_offers_for_key (op, *ibf_key); | 1332 | struct IBF_Key unsalted_key; |
1333 | unsalt_key (ibf_key, ntohl (msg->salt), &unsalted_key); | ||
1334 | send_offers_for_key (op, unsalted_key); | ||
1293 | ibf_key++; | 1335 | ibf_key++; |
1294 | } | 1336 | } |
1295 | } | 1337 | } |
@@ -1517,6 +1559,7 @@ union_evaluate (struct Operation *op, | |||
1517 | op->state->se = strata_estimator_dup (op->spec->set->state->se); | 1559 | op->state->se = strata_estimator_dup (op->spec->set->state->se); |
1518 | /* we started the operation, thus we have to send the operation request */ | 1560 | /* we started the operation, thus we have to send the operation request */ |
1519 | op->state->phase = PHASE_EXPECT_SE; | 1561 | op->state->phase = PHASE_EXPECT_SE; |
1562 | op->state->salt_receive = op->state->salt_send = 42; | ||
1520 | LOG (GNUNET_ERROR_TYPE_DEBUG, | 1563 | LOG (GNUNET_ERROR_TYPE_DEBUG, |
1521 | "Initiating union operation evaluation\n"); | 1564 | "Initiating union operation evaluation\n"); |
1522 | GNUNET_STATISTICS_update (_GSS_statistics, | 1565 | GNUNET_STATISTICS_update (_GSS_statistics, |
@@ -1576,6 +1619,7 @@ union_accept (struct Operation *op) | |||
1576 | op->state = GNUNET_new (struct OperationState); | 1619 | op->state = GNUNET_new (struct OperationState); |
1577 | op->state->se = strata_estimator_dup (op->spec->set->state->se); | 1620 | op->state->se = strata_estimator_dup (op->spec->set->state->se); |
1578 | op->state->demanded_hashes = GNUNET_CONTAINER_multihashmap_create (32, GNUNET_NO); | 1621 | op->state->demanded_hashes = GNUNET_CONTAINER_multihashmap_create (32, GNUNET_NO); |
1622 | op->state->salt_receive = op->state->salt_send = 42; | ||
1579 | /* kick off the operation */ | 1623 | /* kick off the operation */ |
1580 | send_strata_estimator (op); | 1624 | send_strata_estimator (op); |
1581 | } | 1625 | } |
@@ -1620,7 +1664,7 @@ static void | |||
1620 | union_add (struct SetState *set_state, struct ElementEntry *ee) | 1664 | union_add (struct SetState *set_state, struct ElementEntry *ee) |
1621 | { | 1665 | { |
1622 | strata_estimator_insert (set_state->se, | 1666 | strata_estimator_insert (set_state->se, |
1623 | get_ibf_key (&ee->element_hash, 0)); | 1667 | get_ibf_key (&ee->element_hash)); |
1624 | } | 1668 | } |
1625 | 1669 | ||
1626 | 1670 | ||
@@ -1635,7 +1679,7 @@ static void | |||
1635 | union_remove (struct SetState *set_state, struct ElementEntry *ee) | 1679 | union_remove (struct SetState *set_state, struct ElementEntry *ee) |
1636 | { | 1680 | { |
1637 | strata_estimator_remove (set_state->se, | 1681 | strata_estimator_remove (set_state->se, |
1638 | get_ibf_key (&ee->element_hash, 0)); | 1682 | get_ibf_key (&ee->element_hash)); |
1639 | } | 1683 | } |
1640 | 1684 | ||
1641 | 1685 | ||