Project

General

Profile

Feature #3333

Design Interest digest

Added by Junxiao Shi almost 4 years ago. Updated over 1 year ago.

Status:
New
Priority:
Normal
Assignee:
-
Category:
Protocol
Target version:
-
Start date:
Due date:
% Done:

0%

Estimated time:
9.00 h

Description

With a Data packet, add a digest of the Interest to be satisfied in the NDNLPv2 header.

Motivation
As shown in #3000-27, mobility with forwarding hint is subject to cache poisoning attack. Having an Interest digest with the Data packet allows a downstream node to associate a Data packet with the Interest including the forwarding hint used to forward that Interest. This is an attempt to reduce the risk of cache poisoning attack to the same or lesser level before forwarding hints were introduced.

Additional Benefits and Implications
Having an Interest digest allows a downstream node to index its PIT by Interest digest. To determine what Interest(s) an incoming Data can satisfy, the downstream node only needs to perform an exact match lookup on the PIT using the Interest digest, instead of a longest prefix match. Selector processing is still necessary on edge nodes, but is probably optional on core routers.
An implication of this solution is that each Data packet can only match one Interest.

This issue is to design the solution, including investigating how well it mitigates the cache poisoning attack, and what other benefits and implications it may bring.
After the design is approved, implementation shall be in separate issues.


Related issues

Related to NFD - Feature #3000: Design mobility with forwarding hintFeedback

Related to NFD - Feature #4290: Give strategy authority over DataClosed

History

#1 Updated by Junxiao Shi almost 4 years ago

  • Related to Feature #3000: Design mobility with forwarding hint added

#2 Updated by Junxiao Shi over 3 years ago

20160112 conference call schedules a discussion about this issue on 20160119.
Alex is expected to prepare slides for this discussion, but everyone should be prepared.

Beichuan talked about one implication of one Data satisfying only one Interest: "I only get one Data and upstream is down. I have three pending Interests, but only one can be satisfied. When downstream retransmits, I can satisfy them from the cache."

#3 Updated by Junxiao Shi over 3 years ago

20160128 conference call decides that during v0.5 timeline we should proceed with the design of this idea, but the implementation, if any, cannot be merged into master branch.

#4 Updated by Junxiao Shi about 3 years ago

20160816 conference call identifies three major issues:

  • How to make sure everyone use the same hash function, and be able to replace the hash function in the future?
  • Is the Interest digest required or optional with return Data?
  • How is CS organized? still partition by Link, or require exactly same Interest?

For the third question:

  • Requiring exactly same Interest to match a CS entry has the potential of improving CS performance, but it effectively disables name discovery in the CS.
  • Partitioning the CS by Link keeps CS semantics unchanged, but every Interest (including retransmission after Data loss) would still require a full CS lookup.

#5 Updated by Junxiao Shi over 2 years ago

  • Target version changed from v0.5 to v0.6

20170201 call approved the general direction. In particular, it's agreed that "one Data can satisfy only one Interest" is acceptable.

It's agreed that a universal hash function is not needed. Instead, the hash function can be a hop-by-hop decision. A negotiation mechanism is needed, but it is not required since day one.

A proposed alternative to using a hash function is Interest identifier, since all we need is a unique number to identify a PIT entry. Examples of this approach include using a memory index of the PIT entry. However, Alex pointed out that this would not work well on a multi-access link, since every downstream node can choose a different Interest identifier, and the upstream node would have to attach all these identifiers along with each downstream's address (or other identifier) onto the Data packet.

It's believed that a cryptographic hash function is not needed.

#6 Updated by Junxiao Shi over 2 years ago

Below is my opinion.

the hash function can be a hop-by-hop decision

An implication is that, a forwarder whose downstream and upstream links use different hash function would have to perform a potentially expensive hash computation.

It's believed that a cryptographic hash function is not needed.

Using a non-cryptographic hash function leads to Link crafting attack:

Alice--\    /----Bob
        R--S
Chuck--/    \-Mallet
  1. Alice expresses an Interest /Bob/1 with Link object delegating to Bob's network.
  2. Chuck expresses an Interest /Bob/1 with Link object delegating to Mallet's network. The Link object is crafted such that Chuck's Interest has the same digest as Alice's Interest.
  3. Mallet returns bogus Data /Bob/1. Router R is unable to distinguish whether this Data is in reply to Chuck's or Alice's Interest.

Crafting a Link object to cause a hash collision is possible, because the Link object name contains a version component which can be chosen by Chuck. This attack is cheap as long as the hash function lacks "it is infeasible to generate a message from its hash value except by trying all possible messages" property: Chuck can compute a suitable value to put into the version component from the desired Interest digest.

Link crafting attack would become difficult or impossible if every hop uses a different hash function or a different "salt". However, that would require a negotiation protocol to bootstrap.

#7 Updated by Junxiao Shi over 2 years ago

20170208 call confirms Link crafting attack is indeed possible and trivial with non-cryptographic hash function. The choice of hash function needs additional studies.

#8 Updated by Junxiao Shi about 2 years ago

  • Description updated (diff)

#9 Updated by Junxiao Shi about 2 years ago

Crafting a Link object to cause a hash collision is possible, because the Link object name contains a version component which can be chosen by Chuck. This attack is cheap as long as the hash function lacks "it is infeasible to generate a message from its hash value except by trying all possible messages" property: Chuck can compute a suitable value to put into the version component from the desired Interest digest.

#4055 replaces Link object in the Interest with a forwarding hint. However, forwarding hint crafting attack is still possible with an insecure hash function.
Chuck can make a forwarding hint like [{<preference>,/Mallet/<extra-components>}], and choose <preference> and <extra-components> to cause a hash collision. No matter what <extra-components> is, the Interest still goes to Mallet because the delegation name starts with /Mallet.

#10 Updated by Klaus Schneider about 2 years ago

  • Blocks Feature #3797: Congestion Control: generic congestion marks added

#11 Updated by Junxiao Shi about 2 years ago

  • Related to Feature #4290: Give strategy authority over Data added

#12 Updated by Junxiao Shi about 2 years ago

  • Blocks deleted (Feature #3797: Congestion Control: generic congestion marks)

#13 Updated by Davide Pesavento over 1 year ago

  • Target version deleted (v0.6)

Also available in: Atom PDF