Exclusive encryption

• US 20050066184A1
• 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,685,415 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 method comprising:

receiving an encrypted identifier;

decrypting the encrypted identifier;

decoding the decrypted identifier; and

demapping the decoded decrypted identifier.

2. A method as recited in claim 1, further comprising:

receiving encrypted case information corresponding to the encrypted identifier;

decrypting the case information;

recasifying, using the decrypted case information and prior to demapping the decoded decrypted identifier, the decrypted identifier; and

wherein the demapping comprises demapping the recasified decoded decrypted identifier.

3. A method as recited in claim 2, wherein recasifying the decoded decrypted identifier comprises:

for each character in the decoded decrypted identifier that has both an upper-case and a lower-case form, obtaining the character in upper-case form from the decoded decrypted identifier, and determining from the case information whether the character should be included in the recasified decoded decrypted identifier in upper-case form or lower-case form.

4. A method as recited in claim 2, wherein the case information comprises a set of bits, each bit identifying the appropriate case for a character in the decoded decrypted identifier.

5. A method as recited in claim 1, wherein decoding the decrypted identifier comprises:

initializing a string to null;

counting a number of leading one bits that precede the first zero bit in the decrypted identifier; and

for each group of sixteen bits following the first zero bit that follows the leading one bits;

checking whether a leading eight bits of the group of sixteen bits are all zero bits;

if the leading eight bits are not all zero bits, then appending the group of sixteen bits to the string;

if the leading eight bits are all zero bits, then generating a decoded character by decoding the next eight bits after the leading eight bits using a coding table, and checking whether the decoded character is a particular character;

if the decoded character is not the particular character, then appending the decoded character to the string; and

if the decoded character is the particular character, then checking whether any more one bits remain in the encoded identifier, if any more one bits remain in the encoded identifier then appending the decoded character to the string, and if no more one bits remain in the encoded identifier, then;

appending a series of particular characters to the string, wherein the series of particular characters includes a number of particular characters equal to the number of counted leading one bits; and

reversing the order of characters in the string, wherein after the reversing the string comprises the decoded decrypted identifier.

6. A method as recited in claim 5, wherein each of the particular characters is an underscore.

7. A method as recited in claim 5, wherein the coding table comprises a Huffman coding table.

8. A method as recited in claim 5, wherein a first coding table is used for the first group of sixteen bits following the first zero bit that follows the leading one bits, and a second coding table is used for the subsequent groups of sixteen bits after the first group of sixteen bits.

9. A method 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.

10. A method as recited in claim 1, wherein demapping the decoded decrypted identifier comprises:

checking whether the decoded decrypted identifier is equal to one of a plurality of illegal identifiers followed by one or more particular characters;

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

if the decoded decrypted identifier is equal to one of the plurality of illegal identifiers followed by the one or more particular characters, then using as the demapped identifier the decoded decrypted identifier with one of the particular characters appended to the decoded decrypted identifier.

11. A method as recited in claim 10, wherein each of the one or more particular characters comprises an underscore.

12. A method as recited in claim 1, wherein decrypting the encrypted identifier comprises using a block cipher to decrypt the encrypted identifier.

13. A method as recited in claim 1, wherein decrypting the encrypted identifier comprises using cipher block chaining to decrypt the encrypted identifier.

14. A method as recited in claim 1, wherein the identifier comprises one of:

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

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

receiving an encrypted directory entry;

decrypting the encrypted directory entry;

decoding the decrypted directory entry; and

demapping the decoded decrypted directory entry.

16. One or more computer readable media as recited in claim 15, the acts further comprising:

receiving encrypted case information corresponding to the encrypted directory entry;

decrypting the case information;

recasifying, using the decrypted case information and prior to demapping the decoded decrypted directory entry, the decrypted directory entry; and

wherein the demapping comprises demapping the recasified decoded decrypted directory entry.

17. One or more computer readable media as recited in claim 16, wherein the case information comprises a set of bits, each bit identifying the appropriate case for a character in the decoded decrypted directory entry.

18. One or more computer readable media as recited in claim 15, wherein decoding the decrypted directory entry comprises:

initializing a string to null;

counting a number of leading one bits that precede the first zero bit in the decrypted directory entry; and

for each group of sixteen bits following the first zero bit that follows the leading one bits;

checking whether a leading eight bits of the group of sixteen bits are all zero bits;

if the leading eight bits are not all zero bits, then appending the group of sixteen bits to the string;

if the leading eight bits are all zero bits, then generating a decoded character by decoding the next eight bits after the leading eight bits using a coding table, and checking whether the decoded character is a particular character;

if the decoded character is not the particular character, then appending the decoded character to the string; and

if the decoded character is the particular character, then checking whether any more one bits remain in the encoded directory entry, if any more one bits remain in the encoded directory entry then appending the decoded character to the string, and if no more one bits remain in the encoded directory entry, then;

appending a series of particular characters to the string, wherein the series of particular characters includes a number of particular characters equal to the number of counted leading one bits; and

reversing the order of characters in the string, wherein after the reversing the string comprises the decoded decrypted directory entry.

19. One or more computer readable media as recited in claim 18, wherein each of the particular characters is an underscore.

20. One or more computer readable media as recited in claim 15, wherein demapping the decoded decrypted directory entry comprises:

checking whether the decoded decrypted directory entry is equal to one of a plurality of illegal directory entries followed by one or more particular characters;

if the directory entry is not equal to one of the plurality of illegal directory entries followed by the one or more particular characters, then using the decoded decrypted directory entry as the demapped identifier; and

if the directory entry is equal to one of the plurality of illegal directory entries followed by the one or more particular characters, then using as the demapped directory entry the decoded decrypted directory entry with one of the particular characters appended to the decoded decrypted directory entry.

21. One or more computer readable media as recited in claim 15, wherein decrypting the encrypted directory entry comprises using a block cipher to decrypt the encrypted directory entry.

22. One or more computer readable media as recited in claim 15, wherein decrypting the encrypted directory entry comprises using cipher block chaining to decrypt the encrypted directory entry.

23. One or more computer readable media as recited in claim 15, wherein the directory entry comprises one of:

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

24. A system comprising:

means for receiving an encrypted identifier;

means for decrypting the encrypted identifier;

means for decoding the decrypted identifier; and

means for demapping the decoded decrypted identifier.

25. A system as recited in claim 24, further comprising:

means for receiving encrypted case information corresponding to the encrypted identifier;

means for decrypting the case information;

means for recasifying, using the decrypted case information and prior to demapping the decoded decrypted identifier, the decrypted identifier; and

wherein the means for demapping comprises means for demapping the recasified decoded decrypted identifier.

26. A system as recited in claim 25, wherein the case information comprises a set of bits, each bit identifying the appropriate case for a character in the decoded decrypted identifier.

27. A system as recited in claim 24, wherein the means for decoding the decrypted identifier comprises:

means for initializing a string to null;

means for counting a number of leading one bits that precede the first zero bit in the decrypted identifier; and

means for, for each group of sixteen bits following the first zero bit that follows the leading one bits;

checking whether a leading eight bits of the group of sixteen bits are all zero bits;

if the leading eight bits are not all zero bits, then appending the group of sixteen bits to the string;

if the leading eight bits are all zero bits, then generating a decoded character by decoding the next eight bits after the leading eight bits using a coding table, and checking whether the decoded character is a particular character;

if the decoded character is not the particular character, then appending the decoded character to the string; and

if the decoded character is the particular character, then checking whether any more one bits remain in the encoded identifier, if any more one bits remain in the encoded identifier then appending the decoded character to the string, and if no more one bits remain in the encoded identifier, then;

appending a series of particular characters to the string, wherein the series of particular characters includes a number of particular characters equal to the number of counted leading one bits; and

reversing the order of characters in the string, wherein after the reversing the string comprises the decoded decrypted identifier.

28. A system as recited in claim 27, wherein each of the particular characters is an underscore.

29. A system as recited in claim 24, wherein the means for demapping the decoded decrypted identifier comprises:

means for checking whether the decoded decrypted identifier is equal to one of a plurality of illegal identifiers followed by one or more particular characters;

means for, if the decoded decrypted identifier is not equal to one of the plurality of illegal identifiers followed by the one or more particular characters, using the decoded decrypted identifier as the demapped identifier; and

means for, if the decoded decrypted identifier is equal to one of the plurality of illegal identifiers followed by the one or more particular characters, using as the demapped identifier the decoded decrypted identifier with one of the particular characters appended to the decoded decrypted identifier.

30. A system as recited in claim 24, wherein the means for decrypting the encrypted identifier comprises means for using a block cipher to decrypt the encrypted identifier.

31. A system as recited in claim 24, wherein the means for decrypting the encrypted identifier comprises means for using cipher block chaining to decrypt the encrypted identifier.

32. A system as recited in claim 24, wherein the identifier comprises one of:

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

33. A system comprising:

an interface to receive an encrypted identifier;

a decryption module, coupled to the interface, to decrypt the encrypted identifier;

a decoding module, coupled to the decryption module, to decode the decrypted identifier; and

a demapping module, coupled to the decoding module, to demap the decoded decryted identifier.

34. A system as recited in claim 33, wherein the interface is further to receive encrypted case information corresponding to the encrypted identifier, wherein the decryption module is further to decrypt the case information, and further comprising:

a recasifying module to recasify, using the decrypted case information, the decrypted identifier; and

wherein the demapping module is to demap the recasified decoded decrypted identifier.

35. A system as recited in claim 33, wherein the decoding module is to decode the decrypted identifier by:

initializing a string to null;

counting a number of leading one bits that precede the first zero bit in the decrypted identifier; and

for each group of sixteen bits following the first zero bit that follows the leading one bits;

checking whether a leading eight bits of the group of sixteen bits are all zero bits;

if the leading eight bits are not all zero bits, then appending the group of sixteen bits to the string;

if the leading eight bits are all zero bits, then generating a decoded character by decoding the next eight bits after the leading eight bits using a coding table, and checking whether the decoded character is a particular character;

if the decoded character is not the particular character, then appending the decoded character to the string; and

if the decoded character is the particular character, then checking whether any more one bits remain in the encoded identifier, if any more one bits remain in the encoded identifier then appending the decoded character to the string, and if no more one bits remain in the encoded identifier, then;

appending a series of particular characters to the string, wherein the series of particular characters includes a number of particular characters equal to the number of counted leading one bits; and

reversing the order of characters in the string, wherein after the reversing the string comprises the decoded decrypted identifier.

36. A system as recited in claim 33, wherein the demapping module is to demap the decoded decrypted identifier by:

checking whether the decoded decrypted identifier is equal to one of a plurality of illegal identifiers followed by one or more particular characters;

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

if the decoded decrypted identifier is equal to one of the plurality of illegal identifiers followed by the one or more particular characters, then using as the demapped identifier the decoded decrypted identifier with one of the particular characters appended to the decoded decrypted identifier.

37. A system as recited in claim 33, wherein the identifier comprises one of:

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