Exclusive encryption

• US 7,555,656 B2
• Filed: 11/10/2004
• Issued: 06/30/2009
• Est. Priority Date: 01/17/2001
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Douceur, John R., Adya, Atul, Benaloh, Josh D., Yuval, Gideon A.
• Primary Examiner(s): Zand; Kambiz
• Assistant Examiner(s): POLTORAK, PIOTR
• Application Number:
  US10/985,202
• Publication Number:
  US 20050066185A1
• Time in Patent Office: 1,693 Days
• Field of Search: 713/165, 713/190
• US Class Current: 713/190
• CPC Class Codes: G06F 21/6209 to a single file or object, e.g. in a secure envelope, encrypted and accessed using a key, or with access control rules appended to the object itself
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 2221/2107 File encryption
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload

Abstract

An exclusive encryption system is established using multiple computing devices. The exclusive encryption system allows for the exclusion of certain plaintext (e.g., by one of the computing devices) and ciphertext (e.g., by another of the computing devices) while at the same time maintaining the privacy created by the encryption (e.g., so the other computing device cannot see the plaintext). The exclusive encryption system may be implemented as part of a serverless distributed file system with directory entries (e.g., file names or folder names) being the plaintext, or alternatively as part of other systems.

Claims

1. A system comprising:

a source processor;

a source memory;

a source computing device component to generate an encrypted directory name based on a plaintext name that conforms to a syntax,

wherein the source computing component generates the encrypted directory name by a method, the method comprising;

receiving a plaintext name;

generating, based on the plaintext name, a mapped name;

encoding the mapped name; and

encrypting the encoded name; and

a recipient processor;

a recipient memory; and

a recipient computing component, electronically coupled to the source computing component, to perform a method, the method comprising;

receiving the encrypted directory name;

verifying that the encrypted directory name is an encryption of a plaintext name that conforms to the syntax without decrypting the encrypted directory name;

verifying that the encrypted directory name is an encryption of a plaintext name that is not a duplicative name without decrypting the encrypted directory name; and

processing the encrypted directory name based on the verifying,

wherein the processing comprises storing the encrypted directory name, forwarding the encrypted directory name, or determining that the encrypted directory name is invalid.

2. A system as recited in claim 1, wherein the source computing device and the redpient computing device together implement a serverless distributed file system.

3. A system as recited in claim 1, further comprising:

generating, based on the mapped name, a decasified name and corresponding case information;

wherein the encoding comprises encoding the decasified name; and

wherein the encrypting comprises encrypting both the encoded decasified name and the case information.

4. A system as recited in claim 1, wherein the generating comprises generating the mapped name only if the received name is syntactically legal.

5. A system as recited in claim 1, wherein the encoding comprises encoding the mapped name only if the received name is syntactically legal.

6. A system as recited in claim 1, wherein generating the mapped name comprises:

checking whether the identifier is equal to one of a plurality of illegal names;

if the name is not equal to one of the plurality of illegal names, then checking whether the name is equal to one of the plurality of illegal names followed by one or more particular characters;

if the name is not equal to one of the plurality of illegal names followed by one or more particular characters, then using the name as the mapped name; and

if the identifier is equal to one of the plurality of illegal names followed by one or more particular characters, then using as the mapped name the name with one of the particular characters removed.

7. A system as recited in claim 6, wherein the particular character comprises an underscore.

8. A system as recited in claim 1, wherein encoding the mapped name comprises:

reversing the order of characters in the mapped name;

removing, from the reversed name, all trailing characters of a particular type;

initializing the encoded name with a string of one bits equal in number to a number of trailing characters removed form the reversed name followed by a zero bit;

selecting a first character from the reversed name;

encoding the first character using a first coding table;

adding, to the encoded name, a series of zero bits followed by the encoded first character;

for each additional character in the reversed name,

selecting the next character in the reversed name,

encoding the next character using a second coding table,

adding, to the encoded name, a series of zero bits followed by the encoded next character; and

removing any trailing zero bits and the one bit preceding the trailing zero bits from the encoded name.

9. A system as recited in claim 8, wherein the characters of a particular type are the characters that are coded to zero using the first coding table.

10. A system as recited in claim 8, wherein the first coding table and the second coding table are Huffman coding tables.

11. A system as recited In claim 8, wherein each coding in the first coding table is the same as a corresponding coding in the second coding table, but the second coding table codes additional characters not coded by the first coding table.

12. A system as recited in claim 8, wherein for the first character and each additional character, encoding the character only if a set of leading bits of the character are zero, and further comprising adding the character to the encoded name if the set of leading bits of the character are not zero.

13. A system as recited in claim 1, wherein encoding the mapped name comprises:

reversing the order of characters in the mapped name;

removing, from the reversed name, all trailing characters of a particular type;

initializing the encoded name with a string of one bits equal in number to a number of trailing characters removed form the reversed name followed by a zero bit;

selecting a first character from the reversed name;

encoding the first character using a first coding table;

adding, to the encoded name, a series of zero bits followed by the encoded first character;

for each additional character in the reversed name,

selecting the next character in the reversed name,

encoding the next character using one of a plurality of additional coding tables,

adding, to the encoded name, a series of zero bits followed by the encoded next character; and

removing any trailing zero bits and the one bit preceding the trailing zero bits from the encoded name.

14. A system as recited in claim 1, wherein encrypting the encoded identifier comprises using a block cipher to encrypt the encoded identifier.

15. A system as recited in claim 1, wherein encrypting the encoded identifier comprises using cipher block chaining to encrypt the encoded identifier.

16. A system as recited in claim 1, wherein the recipient computing device is to verify that the encrypted directory name conforms to the syntax by checking whether a first block of the encrypted directory name is zero, and determining that the encrypted directory name conforms to the syntax if the first block is not equal to zero.

17. A system as recited in claim 1, wherein the recipient computing device is to verify that the directory name is not a duplicative name by comparing the encrypted directory name to a plurality of other encrypted directory names, checking whether the encrypted directory name is the same as any of the other encrypted directory name, and determining that the encrypted directory name is not a duplicative name if the encrypted directory name is not the same as any of the plurality of encrypted directory names.

18. The system as recited in claim 1, wherein the source processor and the recipient processor are the same processor, and the source memory and the recipient memory are the same memory.

19. A computing device comprising:

a processor;

a memory;

a client component configured to encrypt only directory entries that are syntactically legal, and to encrypt the directory entries in a manner that allows another device to verify, without decrypting the encrypted entries, that the directory entries are not identical to any other directory entries maintained by the other device,

wherein to encrypt the directory entries is to;

receive a plaintext name of the directory entry;

generate, based on the plaintext name, a mapped name;

encode the mapped name; and

encrypt the encoded name; and

a server component configured to receive encrypted directory entries, to verify that the received encrypted directory entries are encryptions of syntactically legal directory entries, arid to verify that the received encrypted directory entries are not encryptions of directory entries identical to any other directory entries maintained by the device, and to process the encrypted directory entries based on the verifying.

20. A computing device as recited in claim 19, wherein the server component can receive directory entries encrypted by the client component of the computing device as well as client components of other computing devices.

21. A computing device as recited in claim 19, wherein to verify that the received encrypted directory entries are encryptions of syntactically legal directory entries is to check, for each of the encrypted directory entries, whether a first block of the encrypted directory entry is zero, and determine that the encrypted directory entry is syntactically legal if the first block is not equal to zero.

22. One or more computer storage media having stored thereon a plurality of instructions that, when executed by one or more processors of a device, causes the one or more processors to perform a method, the method comprising:

encrypting only directory entries that are syntactically legal in a manner that allows another device to verify, without decrypting the encrypted directory entries, that the directory entries are not identical to any other directory entries maintained by the other device,

wherein encrypting one of the directory entries further comprises;

receiving a plaintext name of the one directory entry;

generating, based on the plaintext name, a mapped name;

encoding the mapped name; and

encrypting the encoded name;

receiving additional encrypted directory entries;

verifying that the received additional encrypted directory entries are encryptions of syntactically legal directory entries;

verifying that the received additional encrypted directory entries are not encryptions of directory entries identical to any other directory entries maintained by the device; and

processing each of the received additional encrypted directory entries based on the verifying.

23. The method as recited in claim 22, wherein the received additional encrypted directory entries are received from the other device.

24. The method as recited in claim 22, wherein to verifying that the received additional encrypted directory entries are encryptions of syntactically legal directory entries, for each of the additional encrypted directory entries, further comprises:

checking whether a first block of the additional encrypted directory entry is zero; and

determining that the additional encrypted directory entry is syntactically legal if the first block is not equal to zero.

25. A method, implemented in a device, the method comprising:

encrypting only directory entries that are syntactically legal;

in a manner that allows each of one or more other devices to verify, without decrypting the encrypted directory entries, that the directory entries are not identical to any other directory entries maintained by the other device,

wherein encrypting the directory entries comprises, for each directory entry;

receiving a plaintext name of the directory entry;

generating, based on the plaintext name, a mapped name;

encoding the mapped name; and

encrypting the encoded name;

receiving additional encrypted directory entries;

verifying that the received additional encrypted directory entries are encryptions of syntactically legal directory entries;

verifying that the received additional encrypted directory entries are not encryptions of directory entries identical to any other directory entries maintained by the device; and

processing the received additional encrypted directory entries based on the verifying,

wherein a device comprises a memory and a processor.

26. A method as recited in claim 25, wherein the receiving comprises receiving the additional encrypted directory entries from one of the one or more other devices.

27. A method as recited in claim 25, wherein the receiving comprises receiving the additional encrypted directory entries from a component of the device.

28. A method as recited in claim 25, wherein verifying that the received additional encrypted directory entries are encryptions of syntactically legal directory entries comprises, for each of the additional encrypted directory entries:

checking whether a first block of the additional encrypted directory entry is zero; and

determining that the additional encrypted directory entry is syntactically legal if the first block is not equal to zero.

29. A system comprising:

a processor;

a memory;

means for encrypting only directory entries that are syntactically legal, and for encrypting the directory entries in a manner that allows each of one or more other systems to verify, without decrypting the encrypted directory entries, that the directory entries are not identical to any other directory entries maintained by the other system, wherein the means for encrypting comprises means for, for each directory entry;

receiving a plaintext name of the directory entry;

generating, based on the plaintext name, a mapped name;

encoding the mapped name; and

encrypting the encoded name;

means for receiving additional encrypted directory entries;

means for verifying that the received additional encrypted directory entries are encryptions of syntactically legal directory entries; and

means for verifying that the received additional encrypted directory entries are not encryptions of directory entries identical to any other directory entries maintained by the system; and

means for processing the received additional encrypted directory entries based of the verifying.

30. A system as recited in claim 29, wherein the means for receiving comprises means for receiving the additional encrypted directory entries from one of the one or more other systems.

31. A system as recited in claim 29, wherein the means for receiving comprises receiving the additional encrypted directory entries from a component of the system.

32. A system as recited in claim 29, wherein the means for verifying that the received additional encrypted directory entries are encryptions of syntactically legal directory entries comprises, means for, for each of the additional encrypted directory entries:

checking whether a first block of the additional encrypted directory entry is zero; and

determining that the additional encrypted directory entry is syntactically legal if the first block is not equal to zero.