Exclusive encryption

• US 20050066185A1
• Filed: 11/10/2004
• Published: 03/24/2005
• Est. Priority Date: 01/17/2001
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Douceur, John R., Adya, Atul, Benaloh, Josh D., Yuval, Gideon A.
• Granted Patent: US 7,555,656 B2
• Time in Patent Office: Days
• 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 computing device to generate an encrypted directory name based on a plaintext name that conforms to a syntax; and

a recipient computing device, coupled to the source computing device, to receive the encrypted directory name, to verify that the encrypted directory name is an encryption of a plaintext name that conforms to the syntax without decrypting the encrypted directory name, and to verify that the directory name is an encryption of a plaintext name that is not a duplicative name without decrypting the encrypted directory name.

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

3. A system as recited in claim 1, wherein the source computing device is to generate the encrypted directory name by:

receiving a plaintext name;

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

encoding the mapped name; and

encrypting the encoded name.

4. A system as recited in claim 3, 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.

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

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

7. A system as recited in claim 3, 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.

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

9. A system as recited in claim 3, 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.

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

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

12. A system as recited in claim 9, 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.

13. A system as recited in claim 9, 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.

14. A system as recited in claim 3, 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.

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

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

17. 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.

18. 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.

19. A computing device comprising:

a client component 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; and

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

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 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.

22. 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.

23. A system comprising:

a server component;

a client component coupled to the server component; and

wherein the server component and the client component together ensure that multiple entries in a directory cannot have the same name, that all entries in the directory are syntactically legal, and that the server component does not have access to the unencrypted names of entries in the directory.

24. A system as recited in claim 23, wherein the server component and the client component are implemented on two different computing devices.

25. A system as recited in claim 23, wherein each of the server component and the client component comprise one or more software modules.

26. One or more computer readable 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:

encrypt only directory entries that are syntactically legal;

encrypt the directory entries 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;

receive additional encrypted directory entries;

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

verify that the received additional encrypted directory entries are not encryptions of directory entries identical to any other directory entries maintained by the device.

27. One or more computer readable media as recited in claim 26, wherein the received additional encrypted directory entries are received from the other device.

28. One or more computer readable media as recited in claim 26, wherein to encrypt one of the directory entries is to:

receive a plaintext name of the one directory entry;

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

encode the mapped name; and

encrypt the encoded name.

29. One or more computer readable media as recited in claim 26, wherein to verify that the received additional encrypted directory entries are encryptions of syntactically legal directory entries is to, for each of the additional encrypted directory entries:

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

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

30. A method, implemented in a device, comprising:

encrypting only directory entries that are syntactically legal;

encrypting the directory entries 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;

receiving additional encrypted directory entries;

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

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

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

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

33. A method as recited in claim 30, 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.

34. A method as recited in claim 30, 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.

35. A system comprising:

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;

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.

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

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

38. A system as recited in claim 35, 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.

39. A system as recited in claim 35, 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.