Security for network coding file distribution

• US 20060282677A1
• Filed: 07/28/2005
• Published: 12/14/2006
• Est. Priority Date: 07/02/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Gkantsidis, Christos, Rodriguez, Pablo Rodriguez, Ubeda, Stephane
• Granted Patent: US 8,140,849 B2
• Time in Patent Office: Days
• US Class Current: 713/181
• 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, comprising:

calculating an expected hash of an encoded block corresponding to a file by applying a hash function to a security parameter and a coefficient vector used to encode the encoded block;

applying the hash function to the encoded block to determine the hash; and

verifying validity of the encoded block based on a comparison of the hash and the expected hash.

2. The method of claim 1, 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.

3. The method of claim 1, wherein the encoded block corresponding to the file is considered valid when comparison indicates the hash and the expected hash are equal.

4. The method of claim 1, wherein the security parameter is received from a security authority.

5. The method of claim 1, further comprising storing the security parameter in a secure location.

6. The method of claim 1, further comprising storing the encoded block in a security boundary.

7. The method of claim 1, wherein the encoded block represents one or more unencoded blocks corresponding to the file.

8. The method of claim 1, further comprising discarding the encoded block corresponding to the file if the verifying determines the block is invalid.

9. At least one computer-readable medium having one or more executable instructions that, when read, cause one or more processors to:

store an encoded block corresponding to a file in a boundary denoted as insecure;

calculate a hash of the encoded block;

calculate an expected hash of the encoded block using a security parameter and a coefficient vector used to encode the encoded block;

compare the hash and the expected hash; and

move the encoded block to a boundary denoted as secure when results of the one or more instructions to compare indicate that the hash and the expected hash are equal.

10. The at least one computer-readable medium of claim 9, wherein a homomorphic collision-resistant hash function is used to calculate the hash and the expected hash.

11. The at least one computer-readable medium of claim 9, 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 result of a further subdivision of the encoded block.

12. The at least one computer-readable medium of claim 9, further comprising one or more executable instructions that, when read, further cause the one or more processors to receive the security parameter from a security server.

13. The at least one computer-readable medium of claim 9, further comprising one or more executable instructions that, when read, further cause the one or more processors to discard the encoded block when results of the one or more instructions to compare indicate that the hash and the expected hash are unequal.

14. The at least one computer-readable medium of claim 9, further comprising one or more executable instructions that, when read, further cause the one or more processors to:

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

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

15. The at least one computer-readable medium of claim 14, further comprising one or more executable instructions that, when read, further cause the one or more processors to discard the newly encoded block when results of the one or more instructions to compare indicate that the hash and the expected hash of the encoded block are unequal.

16. The at least on computer-readable medium of claim 9, further comprising executable instruction that, when read, cause the one or more processors to receive the hash of the file.

17. A system, comprising:

means for storing security parameters related to original blocks of a file;

means for storing one or more encoded blocks corresponding to the file;

means for creating a newly encoded block corresponding to the file from the one or more encoded blocks, the means for creating the newly encoded block further comprising means for choosing a new set of coefficients;

means for calculating a hash of (?) the newly encoded block;

means for calculating an expected hash of the newly encoded block using the security parameters and the new set of coefficients; and

means for validating the encoded blocks based on a comparison of the hash and the expected hash.

18. The system of claim 17, wherein the means for choosing a new set of coefficients chooses the coefficients at random.

19. The system of claim 17, wherein the one or more encoded blocks are stored in an insecure window and are moved to a secure window when the newly encoded block is validated.

20. The system of claim 17, further comprising means for performing a binary search to identify which of the one or more encoded block is invalid.