Security for network coding file distribution

• US 8,140,849 B2
• Filed: 07/28/2005
• Issued: 03/20/2012
• Est. Priority Date: 07/02/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Rodriguez, Pablo Rodriguez, Gkantsidis, Christos, Ubeda, Stephane
• Primary Examiner(s): Arani, Taghi
• Assistant Examiner(s): Mehedi, Morshed
• Application Number:
  US11/191,761
• Publication Number:
  US 20060282677A1
• Time in Patent Office: 2,427 Days
• Field of Search: 713/176
• US Class Current: 713/176
• CPC Class Codes: H04L 2209/60 Digital content management, e.g. content distribution
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 63/12 Applying verification of the received information cryptographic mechanisms or cryptographic arrangements for data integrity or data verification H04L9/32
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/108 characterised by resources being split in blocks or fragments
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions

Abstract

A content distribution mechanism that relies on cooperative desktop PCs to distribute content is disclosed. The mechanism distributes content in a robust manner by allowing at least one intermediate network node (i.e., between a source and client) to generate and send packets that contain a linear combination of the portions of content available at the node. Such linear combinations may be created by the source and client using at least a portion of the original content file in either encoded or unencoded form. After the client has received enough linearly independent combinations of packets, the original content may be reconstructed. Further, security for network coding file distribution may be employed to maintain the efficiency and security of the content distribution mechanism. A security server may generate security information using a hashing algorithm including the property of producing security information for each block which survives the process of creating encoded blocks. The security server may generate a unique set of security information for each node participating in the content distribution which each node may then use to verify that the blocks being examined are valid and were created from a linear combination of the original blocks of the file.

Claims

1. A method for defeating a malicious node in a content distribution network of interconnected cooperative nodes, the method comprising:

creating a new encoded block from a linear combination of multiple encoded blocks corresponding to a file, the creating comprising;

choosing a coefficient vector;

multiplying individual values of the coefficient vector by individual byte values of individual bytes of the file; and

summing results produced by the multiplying to provide the new encoded block;

calculating, at a first cooperative node of the content distribution network, an expected hash of the new encoded block by applying a hash function to individual security parameters;

applying the hash function to the new encoded block to determine an actual hash;

validating the new encoded block based on a comparison of the actual hash and the expected hash, wherein the validating comprises verifying the new encoded block as invalid when the comparison indicates the actual hash and the expected hash are not equal or identifying the new encoded block as valid when the comparison indicates the actual hash and the expected hash are equal; and

when the new encoded block is verified as invalid;

performing a search to discover at least one invalid encoded block of the new encoded block, wherein performing the search comprises;

dividing individual encoded blocks of the new encoded block into sets of encoded blocks, creating newer blocks for each of the sets of encoded blocks, and verifying each of the newer blocks; and

sending, by the first cooperative node, an alert regarding the invalidity of the at least one invalid encoded block to at least one other cooperative node of the content distribution network with which the first cooperative node has been exchanging blocks.

2. The method of claim 1, wherein at least one of the individual security parameters includes a random mask corresponding to the file and a mask-based hash corresponding to an unencoded block of the file.

3. The method of claim 1, wherein the individual security parameters are received from a security authority.

4. The method of claim 1, further comprising storing the individual security parameters in a secure location.

5. The method of claim 1, further comprising storing one or more of the individual encoded blocks in a security boundary.

6. The method of claim 1, wherein at least one of the individual encoded blocks represents one or more unencoded blocks corresponding to the file.

7. The method of claim 1, further comprising discarding the at least one invalid encoded block when the new encoded block is verified as invalid.

17. The method of claim 1, wherein performing the search further comprises, after verifying each of the newer blocks, further dividing at least one newer block verified as invalid into additional sets of encoded blocks, further creating additional newer blocks for each of the additional sets of encoded blocks, and further verifying each of the additional newer blocks.

18. The method of claim 17, wherein performing the search further comprises repeating the further dividing, further creating, and further verifying until the at least one invalid encoded block is discovered.

8. A method comprising:

creating an encoded block from a file, the creating comprising;

choosing a coefficient vector;

multiplying individual values of the coefficient vector by individual byte values of individual bytes of the file; and

summing results produced by the multiplying to provide the encoded block;

storing, by a first cooperative node, the encoded block in a boundary denoted as insecure;

calculating an actual hash of the encoded block;

calculating an expected hash of the encoded block using a security parameter uniquely generated for the first cooperative node;

comparing the actual hash and the expected hash;

moving the encoded block to a boundary denoted as secure when the actual hash and the expected hash are equal; and

when the actual hash and the expected hash are unequal, sending, by the first cooperative node, an alert that the encoded block is invalid to at least one other cooperative node with which the first cooperative node has been exchanging blocks.

9. The method of claim 8, wherein a homomorphic collision-resistant hash function is used to calculate the actual hash and the expected hash.

10. The method of claim 8, wherein the security parameter includes a random mask corresponding to the file and a mask-based hash corresponding to an unencoded block of the file, the mask-based hash calculated using at least one sub-block created as a result of a further subdivision of the encoded block.

11. The method of claim 8, further comprising discarding the encoded block when the actual hash and the expected hash are unequal.

12. The method of claim 8, further comprising:

creating a new encoded block corresponding to the file from the encoded block corresponding to the file, and

storing the encoded block corresponding to the file in a boundary denoted as insecure.

13. The method of claim 12, further comprising discarding the new encoded block when the actual hash and the expected hash of the encoded block are unequal.

14. The method of claim 8, further comprising receiving the actual hash of the file.

15. A system, comprising:

a plurality of nodes, at least one of the plurality of nodes being a device comprising at least one processor;

means for storing, by a first cooperative node of the plurality of nodes, security parameters related to original blocks of a file;

means for storing encoded blocks corresponding to the file;

means for creating a newly encoded block corresponding to the file from a linear combination of the encoded blocks, the means for creating the newly encoded block comprising;

randomly choosing a set of coefficient vector values;

multiplying individual coefficient vector values by individual byte values of individual bytes of the file; and

summing results produced by the multiplying to provide the newly encoded block;

means for calculating an actual hash of the newly encoded block;

means for calculating an expected hash of the newly encoded block using the security parameters and the set of coefficient vector values;

means for validating the encoded blocks based on a comparison of the actual hash of the newly encoded block and the expected hash of the newly encoded block;

means for performing a binary search to identify at least one invalid encoded block from the encoded blocks, wherein performing the binary search comprises dividing the encoded blocks into two sets of encoded blocks and verifying each of the two sets of encoded blocks, wherein the dividing and the verifying are repeatable until the at least one invalid encoded block is identified; and

means for sending an alert regarding invalidity of the newly encoded block to at least one other cooperative node of the plurality of nodes with which the first cooperative node is configured to exchange blocks.

16. The system of claim 15, wherein the encoded blocks are stored in an insecure window, and wherein one or more of the encoded blocks identified as valid are moved to a secure window.