Cumulative schemes for network path proof of transit

Patent metadata

Field	Value
Publication number	US-10187209-B2
Application number	US-201614992112-A
Country	US
Kind code	B2
Filing date	Jan 11, 2016
Priority date	Apr 27, 2015
Publication date	Jan 22, 2019
Grant date	Jan 22, 2019

Abstract

A system and methods are provided for verifying proof of transit of network traffic through a plurality of network nodes in a network. In one embodiment, each network node reads a first value and a second value from in-band metadata of packet, and generates, using a cryptographic key that is unique to each respective network node, an encryption result based on the first value. An updated second value is generated based on the second value read from the packet and the encryption result. Each network node writes the updated second value to the in-band metadata of the packet, and forwards the packet in the network. In another embodiment, a secret sharing scheme is employed by each network node computes a portion of verification information using a unique share of a secret and based on the packet specific information.

First claim

What is claimed is:

1. A system comprising:
a plurality of network nodes including one or more processors and a memory, each network node associated with a path in a network and configured to:
obtain information about a packet, the information including in-band metadata that includes one or more fields for at least a first value and a second value, the first value being based on a number or a timestamp generated at an initial network node of the plurality of network nodes of the path in the network, and the second value being cumulatively updated as the packet passes through the plurality of network nodes of the path in the network;
read the first value and the second value from the in-band metadata of the packet;
generate, using a cryptographic key that is unique to each respective network node, an encryption result based on the first value, wherein a uniqueness of the cryptographic key for each respective network node is based on one or more points of a polynomial;
generate an updated second value based on the second value read from the packet and the encryption result;
write the updated second value to the in-band metadata of the packet; and
forward the packet in the network; and

an egress node configured to:
compute encryption results for each of the plurality of network nodes using the cryptographic keys for each of the plurality of network nodes;
compute an accumulated verification value based on the encryption results computed for each of the plurality of network nodes; and
compare the second value read from the packet with the accumulated verification value resulting in when the second value read from the packet matches the accumulated verification value, the packet is determined to have passed through the plurality of network nodes of the path and otherwise the packet is determined not to have passed through the plurality of network nodes of the path.

2. The system of claim 1 , wherein the initial network node is configured to:
generate an initial encryption result using the cryptographic key of the initial network node and based on the number or the timestamp;
generate an initial second value based on the initial encryption result;
write the initial second value to the packet; and
forward the packet in the network.

3. The system of claim 2 , wherein the egress node is further configured to:
receive and store the cryptographic keys for the plurality of network nodes;
receive the packet; and
read the first value and the second value from the in-band metadata of the packet.

4. The system of claim 3 , wherein each network node is configured to generate the updated second value using an Exclusive-OR operation of the second value read from the packet and the encryption result, and the egress node is configured to compute the accumulated verification value using an Exclusive-OR operation of the encryption results computed for each of the plurality of network nodes.

5. The system of claim 3 , further comprising a server configured to distribute each unique cryptographic key to a corresponding one of the plurality of network nodes and to the egress node.

6. A system comprising:
a plurality of network nodes including one or more processors and a memory, each network node associated with a path in a network, wherein the path is associated with a secret, and wherein each network node is configured to:
obtain information about a packet, the information including in-band metadata of the packet;
read the in-band metadata;
compute a portion of verification information using a unique share of the secret and based on the in-band metadata, wherein the unique share of the secret for each respective network node is based on one or more points of a first polynomial;
write the portion of verification information to the in-band metadata of the packet; and
forward the packet in the network; and

an egress node that has access to the secret and is configured to:
read the portions of verification information, written by the plurality of network nodes, from the in-band metadata; and
verify that the packet passed through the plurality of network nodes of the path using the secret and the portions of verification information read from the in-band metadata of the packet.

7. The system of claim 6 , wherein the egress node is further configured to:
receive the packet.

8. The system of claim 7 , wherein each unique share of the secret is distributed in accordance with a secret sharing scheme.

9. The system of claim 7 , wherein each network node is configured to compute the portion of verification information by:
computing points of a second polynomial based on the in-band metadata;
adding the points of the second polynomial to the points of the first polynomial to produce a summation result; and
writing the summation result to the in-band metadata of the packet;
wherein the egress node is configured to verify that the packet passed through the plurality of network nodes by attempting to construct a third polynomial from the summation results generated by the plurality of network nodes resulting in if it is possible to generate a sufficient number of points of the third polynomial the packet is determined to have passed through the plurality of network nodes and otherwise the packet is determined to not have passed through the plurality of network nodes.

10. The system of claim 9 , wherein for k plurality of network nodes, the first polynomial has degree k+1 and is of a form RND-1+ax+bx 2 +cx 3 +nx k ′ with RND-1 being a random number and a, b, c . . . n being other coefficients of the first polynomial, wherein the unique share of the secret comprises a (share-index, share) pair corresponding to points of the first polynomial and the egress node being provided with a unique (share-index, share) pair as well as an entirety of the first polynomial.

11. The system of claim 10 , wherein each network node is provided with coefficients a 1 , b 1 , c 1 . . . n 1 of a second polynomial RND-2+a 1x +b 1x 2 +c 1x 3 + . . . n 1x k+1 , and wherein each network node is configured to compute the portion of verification information by:
computing a share of RND-2 based on RND-2 read from the in-band metadata of the packet and the coefficients of the second polynomial; and
adding the share of RND-2 to RND-1 to produce a share of RND-3 for the third polynomial.

12. The system of claim 11 , wherein the egress node is configured to verify by:
reading from the packet all shares of RND-3 and all shares of RND-2 generated by the plurality of network nodes;
combining all shares of RND-3 generated by the plurality of network nodes to produce a sum value of RND-3;
computing a share of RND-2 of the second polynomial and adding that share to all shares of RND-2 generated by the plurality of network nodes to produce a sum value of RND-2; and
determining whether the sum value of RND-3 is equal to the sum value of RND-2 plus a value for RND-1 that is known at the egress node.

13. The system of claim 11 , wherein each network node generates an updated cumulative share value of RND-3 from a cumulative share value of RND-3 read from the in-band metadata of the packet, and writes the updated cumulative share value of RND-3 to the in-band metadata of the packet.

14. The system of claim 11 , wherein the secret is RND-1 and each unique share of the secret is split using Shamir's Secret Sharing Scheme and is represented as (i, share-i), where i is an index of a share, and a zero degree term of a Lagrange basis polynomial is computed as a constant corresponding to the index.

15. The system of claim 11 , wherein all num

Assignees

• Cisco Tech Inc

Inventors

• Dara Venkata Krishna Sashank
• Bhandari Shwetha Subray
• Yourtchenko Andrew
• Vyncke Eric
• Brockners Frank

Classifications

• H04L69/22

  Parsing or analysis of headers · CPC title

• H04L63/12

  Applying verification of the received information (cryptographic mechanisms or cryptographic arrangements for data integrity or data verification H04L9/32) · CPC title

• H04L12/4633

  Interconnection of networks using encapsulation techniques, e.g. tunneling · CPC title

• H04L41/0246

  Exchanging or transporting network management information using the Internet; Embedding network management web servers in network elements; Web-services-based protocols · CPC title

• H04L63/06

  for supporting key management in a packet data network (cryptographic mechanisms or cryptographic arrangements for key management H04L9/08) · CPC title