Project

General

Profile

Feature #4804

Signed Interest v0.3

Added by Junxiao Shi about 2 years ago. Updated 4 months ago.

Status:
Closed
Priority:
Normal
Assignee:
Category:
Base
Target version:
Start date:
Due date:
% Done:

100%

Estimated time:

Description

Implement Signed Interest as defined in NDN Packet Format v0.3.


Related issues

Blocked by NDN Specifications - Feature #4599: Redesign Signed Interest and Command Interest for packet format v0.3ClosedZhiyi Zhang

Actions
Blocked by ndn-cxx - Feature #4567: Encode Interest into v0.3 format and drop support for v0.2 formatClosedDavide Pesavento

Actions
Blocks NFD - Feature #4786: KITE implementationCode reviewZhongda Xia

Actions
Blocks NFD - Feature #4650: Accept and store PrefixAnnouncement in rib/register commandIn ProgressJunxiao Shi

Actions
#1

Updated by Junxiao Shi about 2 years ago

  • Blocked by Feature #4599: Redesign Signed Interest and Command Interest for packet format v0.3 added
#2

Updated by Junxiao Shi about 2 years ago

  • Blocked by Feature #4567: Encode Interest into v0.3 format and drop support for v0.2 format added
#3

Updated by Junxiao Shi over 1 year ago

From https://gerrit.named-data.net/5494

I had a working design earlier in the quarter where an InterestSignatureInfo was a subclass of SignatureInfo, and that worked well independently, but it became very messy in conjunction with Signature.

Given InterestSignatureInfo and DataSignatureInfo can have different fields, they should be different classes.

/// base class
class SignatureInfo
{
  // have fields that appear in both Interest and Data
};

class InterestSignatureInfo extends SignatureInfo
{
  // implicitly constructible from SignatureInfo
  // add fields that appear in Interest only
};

class DataSignatureInfo extends SignatureInfo
{
  // implicitly constructible from SignatureInfo
  // add fields that appear in Data only, ValidityPeriod and "other TLVs" should be moved there
};

The Signature type is messy and difficult to use. Deprecate it, and replace with four methods on both Interest and Data: getSignatureInfo setSignatureInfo getSignatureValue setSignatureValue.

#4

Updated by Junxiao Shi over 1 year ago

https://gerrit.named-data.net/5502 patchset3 extends ValidatorConfig with three replay checkers that verifies SignatureNonce SignatureTime SignatureSeqNum elements according to spec. They appear as a checker under a rule, along with two key name checkers.
According to rules in general section:

A packet is treated as valid if it can pass at least one of the checkers and as invalid when it cannot pass any checkers.

This means, suppose I write a rule that contains two key name checkers, one SignatureTime checker, and one SignatureSeqNum checker, a signed Interest would be treated as valid if it (1) has an untrusted key name (2) has an unacceptable SignatureTime (3) has an acceptable SignatureSeqNum, because all it takes to pass the validator is one successful checker.
This violates the signed Interest spec that requires all three checkers to pass.

Simply defining all replay checkers to have an AND relation is insufficient, because an application may want to allow the incoming signed Interest to carry either a valid SignatureTime or a valid SignatureSeqNum. This practice is permitted by the spec: the spec requires validation of both SignatureTime and SignatureSeqNum if they are present, but does not forbid an application to accept either of them.

To solve this problem, define explicit logical relation operators among checkers:

checker {
  type AND
  checker {
    type OR
    checker {
      type hierarchical
      sig-type rsa-sha256
    }
    checker {
      type hierarchical
      sig-type ecdsa-sha256
    }
  }
  checker {
    type timestamp
  }
  checker {
    type seq-num
  }
}
#5

Updated by Vladimir Vysotsky over 1 year ago

Given InterestSignatureInfo and DataSignatureInfo can have different fields, they should be different classes.

/// base class
class SignatureInfo
{
  // have fields that appear in both Interest and Data
};

class InterestSignatureInfo extends SignatureInfo
{
  // implicitly constructible from SignatureInfo
  // add fields that appear in Interest only
};

class DataSignatureInfo extends SignatureInfo
{
  // implicitly constructible from SignatureInfo
  // add fields that appear in Data only, ValidityPeriod and "other TLVs" should be moved there
};

Sounds great. Should these be in separate files? If so, should they go in a signature/ or security/signature/ subdirectory, since there would be 6 files total? I don't want to spam the top-level dir with that many related components.

#6

Updated by Junxiao Shi over 1 year ago

  • Status changed from New to In Progress
  • Assignee set to Vladimir Vysotsky
#7

Updated by Zhongda Xia over 1 year ago

#8

Updated by Davide Pesavento over 1 year ago

  • Target version changed from v0.7 to v0.8
#9

Updated by Davide Pesavento over 1 year ago

  • Assignee deleted (Vladimir Vysotsky)
#11

Updated by Junxiao Shi about 1 year ago

  • Assignee changed from Alex Afanasyev to Zhongda Xia

Since Zhongda wants this feature, I'm assigning this to him.

#12

Updated by Junxiao Shi 12 months ago

  • Blocks Feature #4650: Accept and store PrefixAnnouncement in rib/register command added
#13

Updated by Davide Pesavento 9 months ago

  • Assignee deleted (Zhongda Xia)
  • Estimated time deleted (6.00 h)
#14

Updated by Eric Newberry 9 months ago

  • Assignee set to Eric Newberry
#15

Updated by Junxiao Shi 9 months ago

#16

Updated by Davide Pesavento 9 months ago

#17

Updated by Eric Newberry 8 months ago

  • Status changed from In Progress to Code review
  • % Done changed from 0 to 50
#18

Updated by Eric Newberry 8 months ago

On the NDN platform call on May 29, 2020, it was decided to change SignatureNonce into a variable-length field with a minimum length of 1. In the spec, we will recommend a minimum length of 8.

#19

Updated by Davide Pesavento 8 months ago

  • Tags set to Packet03Transition
#20

Updated by Eric Newberry 7 months ago

  • % Done changed from 50 to 70
#21

Updated by Eric Newberry 7 months ago

  • % Done changed from 70 to 100
#22

Updated by Alex Afanasyev 7 months ago

  • % Done changed from 100 to 80

I downgraded the progress, there is more stuff involved, including signed interest helper (it may still be needed) and support inside the validators.

#23

Updated by Davide Pesavento 7 months ago

Alex Afanasyev wrote in #note-22:

signed interest helper

What's that?

#24

Updated by Alex Afanasyev 7 months ago

CommandInterestSigner. This one prepares nonce and other stuff.

#25

Updated by Eric Newberry 7 months ago

Alex Afanasyev wrote in #note-24:

CommandInterestSigner. This one prepares nonce and other stuff.

Do we need to update CommandInterestSigner to use v0.3 (do we also allow it to still generate v0.2?) or are we going to add a new SignedInterestSigner that supports v0.3?

#26

Updated by Davide Pesavento 7 months ago

  • Tags changed from Packet03Transition to Packet03Transition, API
#27

Updated by Eric Newberry 5 months ago

  • % Done changed from 80 to 100
#28

Updated by Davide Pesavento 4 months ago

While reviewing https://gerrit.named-data.net/c/ndn-cxx/+/6221 I got curious about the performance characteristics of boost::multi_index_container, specifically insert and find operations for ordered indexes vs hashed indexes, and wrote a very quick-and-dirty and probably inaccurate benchmark. I'm copying it below in case it becomes useful again in the future.

Compile it with something like: g++ -O2 -std=c++14 benchmark.cpp $(pkg-config --cflags --libs libndn-cxx) -o benchmark
and either -DBENCHMARK_ORDERED or -DBENCHMARK_HASHED or both.

#include <algorithm>
#include <chrono>
#include <cstdlib>
#include <iostream>
#include <random>
#include <vector>
#include <ndn-cxx/name.hpp>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/key_extractors.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/sequenced_index.hpp>

struct Record
{
    explicit Record(const ndn::Name& n) : name(n) {}

    ndn::Name name;
    // some junk to make the struct larger
    uint64_t pad1 = 1;
    uint64_t pad2 = 2;
    uint64_t pad3 = 3;
    uint64_t pad4 = 4;
};

using HashedContainer = boost::multi_index_container<
  Record,
  boost::multi_index::indexed_by<
    boost::multi_index::hashed_unique<
      boost::multi_index::member<Record, ndn::Name, &Record::name>,
      std::hash<ndn::Name>
    >,
    boost::multi_index::sequenced<>
  >
>;
using OrderedContainer = boost::multi_index_container<
  Record,
  boost::multi_index::indexed_by<
    boost::multi_index::ordered_unique<
      boost::multi_index::member<Record, ndn::Name, &Record::name>
    >,
    boost::multi_index::sequenced<>
  >
>;

static ndn::Name
generateName(unsigned long nComp, unsigned long compLen)
{
    using RandEngine = std::independent_bits_engine<std::mt19937, 8, unsigned char>;
    static RandEngine rng = [] {
        std::random_device rd;
        // seed with 256 bits of entropy
        std::seed_seq seeds{rd(), rd(), rd(), rd(), rd(), rd(), rd(), rd()};
        return RandEngine{seeds};
    }();

    ndn::Name n;
    for (; nComp > 0; --nComp) {
        std::vector<uint8_t> bytes(compLen);
        std::generate(bytes.begin(), bytes.end(), [&] { return rng(); });
        n.append(bytes.data(), bytes.size());
    }
    return n;
}

int
main(int argc, char *argv[])
{
    if (argc != 4) {
        std::cerr << argv[0] << " <NUM_OF_NAMES> <NUM_OF_NAME_COMPONENTS> <NAME_COMPONENT_LEN>" << std::endl;
        return 1;
    }
    auto nNames = std::strtoul(argv[1], nullptr, 0);
    auto nComp = std::strtoul(argv[2], nullptr, 0);
    auto compLen = std::strtoul(argv[3], nullptr, 0);

    std::vector<ndn::Name> names(nNames);
    std::generate(names.begin(), names.end(), [&] { return generateName(nComp, compLen); });

#ifdef BENCHMARK_HASHED
    HashedContainer hashed;
    hashed.reserve(nNames);
#endif
#ifdef BENCHMARK_ORDERED
    OrderedContainer ordered;
#endif

    size_t nSuccess = 0;
#ifdef BENCHMARK_HASHED
    auto t1 = std::chrono::steady_clock::now();
    for (size_t i = 0; i < nNames; ++i) {
        nSuccess += hashed.emplace(names[i]).second;
    }
#endif
    auto t2 = std::chrono::steady_clock::now();
#ifdef BENCHMARK_ORDERED
    for (size_t i = 0; i < nNames; ++i) {
        nSuccess += ordered.emplace(names[i]).second;
    }
    auto t3 = std::chrono::steady_clock::now();
#endif

    std::cout << "EMPLACE NEW " << nSuccess
             #ifdef BENCHMARK_HASHED
              << "\nhashed  = " << (t2 - t1).count()
             #endif
             #ifdef BENCHMARK_ORDERED
              << "\nordered = " << (t3 - t2).count()
             #endif
              << std::endl;

    nSuccess = 0;
#ifdef BENCHMARK_HASHED
    auto t4 = std::chrono::steady_clock::now();
    for (size_t i = 0; i < nNames; ++i) {
        nSuccess += hashed.emplace(names[i]).second;
    }
#endif
    auto t5 = std::chrono::steady_clock::now();
#ifdef BENCHMARK_ORDERED
    for (size_t i = 0; i < nNames; ++i) {
        nSuccess += ordered.emplace(names[i]).second;
    }
    auto t6 = std::chrono::steady_clock::now();
#endif

    std::cout << "\nEMPLACE EXISTING " << nSuccess
             #ifdef BENCHMARK_HASHED
              << "\nhashed  = " << (t5 - t4).count()
             #endif
             #ifdef BENCHMARK_ORDERED
              << "\nordered = " << (t6 - t5).count()
             #endif
              << std::endl;

    nSuccess = 0;
#ifdef BENCHMARK_HASHED
    auto t7 = std::chrono::steady_clock::now();
    for (size_t i = 0; i < nNames; ++i) {
        nSuccess += hashed.find(names[i]) != hashed.end();
    }
#endif
    auto t8 = std::chrono::steady_clock::now();
#ifdef BENCHMARK_ORDERED
    for (size_t i = 0; i < nNames; ++i) {
        nSuccess += ordered.find(names[i]) != ordered.end();
    }
    auto t9 = std::chrono::steady_clock::now();
#endif

    std::cout << "\nFIND EXISTING " << nSuccess
             #ifdef BENCHMARK_HASHED
              << "\nhashed  = " << (t8 - t7).count()
             #endif
             #ifdef BENCHMARK_ORDERED
              << "\nordered = " << (t9 - t8).count()
             #endif
              << std::endl;

    auto anotherName = generateName(nComp, compLen);
    nSuccess = 0;
#ifdef BENCHMARK_HASHED
    auto t10 = std::chrono::steady_clock::now();
    for (size_t i = 0; i < nNames; ++i) {
        nSuccess += hashed.find(anotherName) != hashed.end();
    }
#endif
    auto t11 = std::chrono::steady_clock::now();
#ifdef BENCHMARK_ORDERED
    for (size_t i = 0; i < nNames; ++i) {
        nSuccess += ordered.find(anotherName) != ordered.end();
    }
    auto t12 = std::chrono::steady_clock::now();
#endif

    std::cout << "\nFIND NON-EXISTING " << nSuccess
             #ifdef BENCHMARK_HASHED
              << "\nhashed  = " << (t11 - t10).count()
             #endif
             #ifdef BENCHMARK_ORDERED
              << "\nordered = " << (t12 - t11).count()
             #endif
              << std::endl;

    return 0;
}
#29

Updated by Eric Newberry 4 months ago

  • Status changed from Code review to Closed

Also available in: Atom PDF