Exclusive encryption

• US 20020095590A1
• Filed: 01/17/2001
• Published: 07/18/2002
• 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,047,420 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.

20. A method as recited in claim 19, wherein the identifier comprises one of:

a file name, a folder name, and a directory name.

21. A method as recited in claim 19, further comprising:

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

wherein the encoding comprises encoding the decasified identifier; and

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

22. A method as recited in claim 21, wherein generating the decasified identifier and corresponding case information comprises:

for each character that has both an upper-case and a lower-case form, storing the character in upper-case form and recording in the case information whether the character was in upper-case form or lower-case form.

23. A method as recited in claim 22, further comprising:

storing the character in upper-case form only if the character is one of particular set of characters; and

storing the character without altering its case if the character is not one of the particular set of characters.

24. A method as recited in claim 23, wherein the particular set of characters comprises the extended ASCII character set.

25. A method as recited in claim 19, wherein the generating comprises generating the mapped identifier only if the received identifier is syntactically legal.

26. A method as recited in claim 19, wherein the encoding comprises encoding the mapped identifier only if the received identifier is syntactically legal.

27. A method as recited in claim 19, further comprising:

receiving an encrypted identifier from another device;

decrypting the encrypted identifier;

decoding the decrypted identifier; and

demapping the decoded decrypted identifier.

28. A method as recited in claim 27, further comprising:

receiving encrypted case information corresponding to the encrypted identifier;

decrypting the case information;

recasifying, using the decrypted case information, the decrypted identifier; and

wherein the demapping comprises demapping the recasified decoded decrypted identifier.

29. A method as recited in claim 19, wherein generating the mapped identifier comprises:

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

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

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

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

30. A method as recited in claim 29, wherein the particular character comprises an underscore.

31. A method as recited in claim 19, wherein encoding the mapped identifier comprises:

reversing the order of characters in the mapped identifier;

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

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

selecting a first character from the reversed identifier;

encoding the first character using a first coding table;

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

for each additional character in the reversed identifier,

selecting the next character in the reversed identifier,

encoding the next character using a second coding table,

adding, to the encoded identifier, 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 identifier.

32. A method as recited in claim 31, wherein the characters of a particular type are the characters that are coded to zero using the first coding table.

33. A method as recited in claim 31, wherein the first coding table and the second coding table are Huffman coding tables.

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

35. A method as recited in claim 31, 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 identifier if the set of leading bits of the character are not zero.

36. A method as recited in claim 19, wherein encoding the mapped identifier comprises:

reversing the order of characters in the mapped identifier;

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

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

selecting a first character from the reversed identifier;

encoding the first character using a first coding table;

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

for each additional character in the reversed identifier,

selecting the next character in the reversed identifier,

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

adding, to the encoded identifier, 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 identifier.

37. A method as recited in claim 19, wherein encrypting the encoded identifier comprises using a block cipher to encrypt the encoded identifier.

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

39. A system as recited in claim 19, wherein the encrypting comprises encrypting the encoded identifier to generate, using a block cipher, a ciphertext having a fixed size.

40. A system as recited in claim 39, further comprising indicating that the received identifier cannot be encrypted if the length of the encoded identifier exceeds the fixed size by more than one.

41. One or more computer-readable memories containing a computer program that is executable by a processor to perform the method recited in claim 19.

19. A method comprising:

receiving an identifier;

generating, based on the identifier, a mapped identifier;

encoding the mapped identifier; and

encrypting the encoded identifier.

42. A method comprising:

receiving an encrypted identifier;

verifying, without decrypting the encrypted identifier, that the encrypted identifier is an encryption of another identifier that conforms to a syntax; and

verifying, without decrypting the encrypted identifier, that the encrypted identifier is not an encryption of the same other identifier as one or more other encrypted identifiers.

43. A method as recited in claim 42, wherein verifying that the encrypted identifier is an encryption of another identifier that conforms to the syntax comprises:

checking whether a first block of the encrypted identifier is zero;

determining that the encrypted directory name conforms to the syntax if the first block is not equal to zero; and

determining that the encrypted directory name does not conform to the syntax if the first block is equal to zero.

44. A method as recited in claim 42, wherein verifying that the encrypted identifier is not an encryption of the same other identifier as one or more other encrypted identifiers comprises:

comparing the encrypted identifier to the one or more other encrypted identifiers; and

determining that the encrypted identifier is the same as one or more other encrypted identifiers if the comparing indicates that the encrypted identifier is equal to one of the other encrypted identifiers.

45. One or more computer-readable memories containing a computer program that is executable by a processor to perform the method recited in claim 42.

48. One or more computer-readable media as recited in claim 47, wherein generating the ciphertext comprises:

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

encoding the mapped identifier; and

encrypting the encoded identifier.

49. One or more computer-readable media as recited in claim 48, wherein generating the ciphertext further comprises:

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

wherein the encoding comprises encoding the decasified identifier; and

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

50. One or more computer-readable media as recited in claim 48, wherein generating the mapped identifier comprises:

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

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

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

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

51. One or more computer-readable media as recited in claim 48, wherein encoding the mapped identifier comprises:

reversing the order of characters in the mapped identifier;

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

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

selecting a first character from the reversed identifier;

encoding the first character using a first coding table;

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

for each additional character in the reversed identifier,

selecting the next character in the reversed identifier,

encoding the next character using a second coding table,

adding, to the encoded identifier, 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 identifier.

52. One or more computer-readable media as recited in claim 51, 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.

53. One or more computer-readable media as recited in claim 48, wherein encoding the mapped identifier comprises:

reversing the order of characters in the mapped identifier;

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

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

selecting a first character from the reversed identifier;

encoding the first character using a first coding table;

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

for each additional character in the reversed identifier,

selecting the next character in the reversed identifier,

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

adding, to the encoded identifier, 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 identifier.

54. One or more computer-readable media as recited in claim 48, wherein encrypting the encoded identifier comprises using a block cipher to encrypted the encoded identifier.

46. A system comprising:

a plurality of encrypted identifiers;

a syntax verifier to determine whether a newly received encrypted identifier is an encryption of a legal name without decrypting the newly received encrypted identifier; and

a duplication identifier to determine whether the newly received encrypted identifier is an encryption of the same name as any of the plurality of encrypted identifiers without decrypting either the newly received encrypted identifier or any of the plurality of encrypted identifiers.

47. One or more computer-readable media having stored thereon a plurality of instructions that, when executed by one or more processors of a computer, causes the one or more processors to perform acts including:

receiving a plaintext identifier;

generating a ciphertext by encrypting the plaintext identifier only if the plaintext identifier is syntactically legal; and

wherein the encrypting allows another device to verify, without decrypting the ciphertext, that the plaintext identifier is not identical to another plaintext identifier maintained by the other device.

55. A method comprising:

receiving an encrypted identifier;

receiving encrypted case information corresponding to the encrypted identifier;

decrypting the encrypted identifier;

decrypting the case information;

decoding the decrypted identifier;

recasifying, using the decrypted case information, the decrypted identifier; and

demapping the recasified decoded decrypted identifier.

56. One or more computer-readable memories containing a computer program that is executable by a processor to perform the method recited in claim 55.

58. One or more computer-readable memories containing a computer program that is executable by a processor to perform the method recited in claim 57.

57. A method implemented at a computing device, the method comprising:

receiving a directory entry that is encrypted, wherein the computing device does not have a key needed for decrypting the directory entry;

verifying that the directory entry is an encryption of a syntactically legal name; and

verifying that the directory entry is not an encryption of the same name as any other directory entry maintained by the computer device.

59. A system comprising:

a plurality of encrypted directory entries;

a syntax verifier to determine whether a new encrypted directory entry is an encryption of a legal name without decrypting the new encrypted directory entry; and

a duplication identifier to determine whether the new encrypted directory entry is an encryption of the same name as any of the plurality of encrypted directory entries without decrypting either the new encrypted directory entry or any of the plurality of encrypted directory entries.

60. One or more computer-readable media having stored thereon a plurality of instructions that, when executed by one or more processors of a computer, causes the one or more processors to perform acts including:

receiving a plaintext directory entry;

verifying that the plaintext directory entry is syntactically legal;

encrypting the plaintext directory entry only if the plaintext directory entry is syntactically legal;

communicating the encrypted directory entry to another device; and

wherein the encrypting allows the other device to verify, without decrypting the encrypted directory entry, that the directory entry is not identical to any other directory entry maintained by the other device.

61. One or more computer-readable media as recited in claim 60, wherein the computer is part of a serverless distributed file system.

62. One or more computer-readable media as recited in claim 60, wherein the plaintext directory entry comprises a file name.

63. One or more computer-readable media as recited in claim 60, wherein the plaintext directory entry comprises a directory name.

64. One or more computer-readable media as recited in claim 60, wherein the plaintext directory entry comprises a folder name.

65. One or more computer-readable media as recited in claim 60, wherein the plurality of instructions further cause the one or more processors to perform acts including:

receiving an encrypted directory entry from another device;

decrypting the encrypted directory entry;

decoding the decrypted identifier; and

demapping the decoded decrypted identifier.

66. One or more computer-readable media as recited in claim 65, further comprising:

receiving encrypted case information corresponding to the encrypted directory entry;

decrypting the case information;

recasifying, using the decrypted case information, the decrypted identifier; and

wherein the demapping comprises demapping the recasified decoded decrypted identifier.

67. One or more computer-readable media as recited in claim 60, wherein encrypting the plaintext directory entry comprises:

generating, based on the plaintext directory entry, a mapped identifier;

encoding the mapped identifier; and

encrypting the encoded identifier.

68. One or more computer-readable media as recited in claim 67, further comprising indicating that the received plaintext directory entry cannot be encrypted if the length of the encoded identifier exceeds a fixed encrypted directory entry size by more than one.

69. One or more computer-readable media as recited in claim 67, wherein encrypting the plaintext directory entry further comprises:

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

wherein the encoding comprises encoding the decasified identifier; and

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

70. One or more computer-readable media as recited in claim 67, wherein generating the mapped identifier comprises generating the mapped identifier only if the received plaintext directory entry is syntactically legal.

71. One or more computer-readable media as recited in claim 67, wherein the encoding comprises encoding the mapped identifier only if the received plaintext directory entry is syntactically legal.

72. One or more computer-readable media as recited in claim 67, wherein generating the mapped identifier comprises:

checking whether the plaintext directory entry is equal to one of a plurality of illegal identifiers;

if the plaintext directory entry is not equal to one of the plurality of illegal identifiers, then checking whether the plaintext directory entry is equal to one of the plurality of illegal identifiers followed by one or more particular characters;

if the plaintext directory entry is not equal to one of the plurality of illegal identifiers followed by one or more particular characters, then using the plaintext directory entry as the mapped identifier; and

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

73. One or more computer-readable media as recited in claim 72, wherein the particular character comprises an underscore.

74. One or more computer-readable media as recited in claim 67, wherein encoding the mapped identifier comprises:

reversing the order of characters in the mapped identifier;

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

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

selecting a first character from the reversed identifier;

encoding the first character using a first coding table;

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

for each additional character in the reversed identifier,

selecting the next character in the reversed identifier,

encoding the next character using a second coding table,

adding, to the encoded identifier, 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 14 bits from the encoded identifier.

75. One or more computer-readable media as recited in claim 74, 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.

76. One or more computer-readable media as recited in claim 74, wherein the characters of a particular type are the characters that are coded to zero using the first coding table.

77. One or more computer-readable media as recited in claim 74, wherein the first coding table and the second coding table are Huffman coding tables.

78. One or more computer-readable media as recited in claim 74, 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.

79. One or more computer-readable media as recited in claim 74, 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 identifier if the set of leading bits of the character are not zero.

80. One or more computer-readable media as recited in claim 67, wherein encrypting the encoded identifier comprises using a block cipher to encrypt the encoded identifier.

81. One or more computer-readable media as recited in claim 60, wherein the encrypting further comprises generating, using a block cipher, the encrypted directory entry having a fixed size.

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

83. A computing device as recited in claim 82, 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.

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

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

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

87. A system comprising:

means for verifying that a plaintext directory entry is syntactically legal;

means for encrypting the plaintext directory entry only if the plaintext directory entry is syntactically legal;

means for communicating the encrypted directory entry to another device; and

wherein the encrypting allows the other device to verify, without decrypting the encrypted directory entry, that the directory entry is not identical to any other directory entry maintained by the other device.