Reducing unwanted and unsolicited electronic messages by exchanging electronic message transmission policies and solving and verifying solutions to computational puzzles

• US 7,552,176 B2
• Filed: 10/10/2003
• Issued: 06/23/2009
• Est. Priority Date: 03/12/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Rounthwaite, Robert L., Goodman, Joshua T., Williams, Roy, Ahmed, Khaja E., Goldberg, Andrew V., Katz, Harry Simon, Atkinson, Robert George, Lyon, James M., Dwork, Cynthia
• Primary Examiner(s): DENNISON, JERRY B
• Application Number:
  US10/683,624
• Publication Number:
  US 20040181585A1
• Time in Patent Office: 2,083 Days
• Field of Search: 709/206, 709/224, 709/227, 726/3, 726/4
• US Class Current: 709/206
• CPC Class Codes: G06Q 10/107 Computer-aided management of electronic mailing [e-mailing]
• CPC Class Codes: H04L 51/212 using filtering or selective blocking

Abstract

The present invention provides for generating inputs that can be provided to a message classification module to facilitate more reliable classification of electronic messages, such as, for example, as unwanted and/or unsolicited. In one embodiment, a sending messaging server provides an appropriate response to address verification data thereby indicating a reduced likelihood of the sending messaging server using a forged network address. In another embodiment, it is determined if a messaging server is authorized to send electronic messages for a domain. In yet another embodiment, electronic message transmission policies adhered to by a domain are identified. In yet a further embodiment, a sending computer system expends computational resources to solve a computational puzzle and includes an answer document in an electronic message. A receiving computer system receives the electronic message and verifies the answer document.

Claims

1. In a sending domain that is network connectable to one or more receiving domains, the sending domain including a sending messaging server configured to send electronic messages to the receiving domains, a method for indicating to a receiving side domain that the sending messaging server expended computational resources to solve a predetermined computational puzzle before sending an electronic message to the receiving side domain, the method comprising:

an act of the sending messaging server receiving electronic message data that is to be contained in an electronic message sent from the sending messaging server to the receiving side domain;

an act of the sending messaging server generating puzzle input from one or more components of the electronic message, the one or more components selected from a group consisting of;

a message body, a message attachment, and a message header, and wherein the act of generating puzzle input includes one or more of;

extracting portions of at least one of the one or more components, hashing portions of at least one of the one or more components, and concatenating portions of at least one of the one or more components;

an act of the sending messaging server identifying an answer document by applying a hashing algorithm to different answer documents until the hashing algorithm produces an answer hash value that is a solution to the predetermined computational puzzle,

wherein the answer hash value is calculated by;

combining one of the different answer documents and the puzzle input; and

hashing the combination of the one of the different answer documents and the puzzle input using the hashing algorithm, wherein the hashing algorithm alters a standard application of SHA-1 sub functions; and

an act of sending the electronic message from the sending messaging server to the receiving side domain, wherein the electronic message includes the identified answer document and the electronic message data enabling verification by the receiving side domain that the sending messaging server expended computational resources without further communication with the sending messaging server.

2. The method as recited in claim 1, wherein the act of the sending messaging server receiving electronic message data that is to be contained in an electronic message comprises an act of receiving electronic message data that is to be contained in an electronic mail message.

3. The method as recited in claim 1, further comprising an act of generating an initial document from at least one of the one or more components, wherein the act of generating the initial document comprises extracting data from at least one field of the electronic message data wherein the at least one field is selected from a From field, a To field, a NotBefore field, a NotAfter field, a Date field, a Body field, an Attachment field, a Subject field, and a Message-Id field.

4. The method as recited in claim 3, wherein the act of generating an initial document from at least one of the one or more components comprises an act of extracting data from one or more date range fields.

5. The method as recited in claim 3, wherein the act of generating an initial document from at least one of the one or more components comprises an act of extracting data wherein the data is text data, graphical data, Uniform Resource Identifier (“

URI”

) data, or executable data.

6. The method as recited in claim 1, wherein the act of the sending messaging server identifying an answer document comprises an act of identifying an answer document that, when combined with the puzzle input and the combination of the answer document and puzzle input is hashed, results in a hash value having a specified value in a plurality of fixed bit positions.

7. The method as recited in claim 6, wherein the act of the sending messaging server identifying an answer document comprises an act of identifying an answer document that, when prepended to the puzzle input and the concatenation of the answer document and puzzle input is hashed, results in a hash value having a value of zero in at least a first specified number of bits.

8. The method as recited in claim 1, wherein the act of the sending messaging server identifying an answer document comprises an act of identifying an answer document that, when concatenated to the puzzle input and the concatenation of the answer document and puzzle input is hashed, results in a hash value having specified bit values in a first plurality of bit positions and having bit values equal to the corresponding bit values of the hashes resulting from other answer documents in a second plurality of bit positions.

9. The method as recited in claim 8, wherein the act of the sending messaging server identifying an answer document comprises an act of identifying an answer document that, when concatenated to the puzzle input and the concatenation of the answer document and puzzle input is hashed, results in a hash value having specified values in each bit position of a hash value prefix and a value equal to corresponding hash bit values resulting from other answer documents in a hash value suffix.

10. The method as recited in claim 1, wherein the act of the sending messaging server identifying an answer document comprises an act of using a puzzle hash algorithm, the puzzle hash algorithm being specifically designed to increase the difficulty of implementing hardware acceleration of the puzzle hash algorithm.

11. The method as recited in claim 1, wherein the act of sending an electronic message that includes the identified answer document and the electronic message data to the receiving side domain comprises an act of sending an electronic message that includes a plurality of answer documents.

12. The method as recited in claim 1, further comprising:

an act of querying a server to determine if the receiving domain is configured to verify answers to computational puzzles; and

an act of receiving one or more DNS TXT records that contain electronic message configuration information for the receiving domain.

13. The method as recited in claim 12, wherein the act of querying a server comprises an act of querying a server in response to the sending domain not supporting electronic mail transmission policy certificates.

14. The method as recited in claim 12, wherein the act of receiving one or more DNS TXT records comprises an act of receiving one or more DNS TXT records that encode the electronic message configuration information in XML instructions.

15. In a receiving domain that is network connectable to one or more sending domains, the receiving domain including one or more receiving messaging servers configured to receive electronic messages from the sending domains, a method for determining if a sending messaging server solved a predetermined computational puzzle before sending an electronic message, the method comprising:

an act of receiving an electronic message that includes electronic message data and an answer document;

an act of reproducing a puzzle input from one or more predetermined components of the electronic message, the one or more predetermined components selected from a group consisting of;

a message body, a message attachment, and a message header, wherein reproducing puzzle input includes one or more of;

extracting portions of at least one of the one or more predetermined components, hashing portions of at least one of the one or more predetermined components, and concatenating portions of at least one of the one or more predetermined components, and wherein the act of reproducing a puzzle input from one or more predetermined components of the electronic message further comprises an act of applying a hashing algorithm that alters the standard application of SHA-1 sub-functions;

an act of determining if a verifying hash value, is a solution to the predetermined computational puzzle, the verifying hash value being calculated by combining the answer document and the puzzle input and hashing the combination of the answer document and puzzle input using the hashing algorithm; and

an act of providing results of the determination to a message classification module wherein the message classification module determines, based on the results, whether the received electronic message is spam.

16. The method as recited in claim 15, wherein the act of receiving an electronic message that includes electronic message data and an answer document comprises an act of receiving an electronic mail message.

17. The method as recited in claim 15, wherein the act of receiving an electronic message that includes electronic message data and an answer document comprises an act of receiving an electronic message that includes a plurality of answer documents.

18. The method as recited in claim 15, further comprising an act of reproducing an initial document from at least one of the one or more predetermined components of the electronic message, wherein the act of reproducing the initial document comprises an act of extracting data from a field of the electronic message data wherein the field is selected from among a From field, a To field, a NotBefore field, a NotAfter field, a Date field, a Body field, an Attachment field, a Subject field, and a Message-ID field.

19. The method as recited in claim 18, wherein the act of reproducing an initial document from at least one of the one or more predetermined components of the electronic message comprises an act of extracting data from the electronic message data wherein the data is text data, graphical data, Uniform Resource Identifier (“

URI”

) data, or executable data.

20. The method as recited in claim 15, wherein the act of reproducing a puzzle input from one or more predetermined components of the electronic message comprises an act of applying the hashing algorithm, the hashing algorithm being specifically designed to increase the difficulty of implementing hardware acceleration used to enhance efficiency of the hashing algorithm.

21. The method as recited in claim 15, wherein the act of determining if a verifying hash value, calculated from a combination of an answer document and the puzzle input, is an answer value indicative of a solution to the predetermined computational puzzle comprises an act of determining if the verifying hash value has a specified value in a plurality of fixed bit positions interspersed throughout the verifying hash value.

22. The method as recited in claim 15, wherein the act of determining if a verifying hash value, calculated from a combination of an answer document and the puzzle input, is an answer value indicative of a solution to the predetermined computational puzzle comprises an act of determining if the verifying hash value has a specified value in a first plurality of bit positions and has a value equal to other verifying hash values resulting from other answer documents in a second plurality of bit positions.

23. A computer program product for use in a sending domain that is network connectable to one or more receiving domains, the sending domain including a sending messaging server configured to send electronic messages to the receiving domains, the computer program product for implementing a method for indicating to a receiving side domain that the sending messaging server expended computational resources to solve a predetermined computational puzzle before sending an electronic message to the receiving side domain, the computer program product comprising one or more computer storage media having stored thereon computer executable instructions that, when executed by a processor, cause the sending domain to perform the following:

receive electronic message data that is to be contained in an electronic message;

generate puzzle input from one or more components of the electronic message, the one or more components selected from a group consisting of;

a message body, a message attachment, and a message header, and wherein puzzle input generation includes one or more of;

extracting portions of at least one of the one or more components, hashing portions of at least one of the one or more components, and concatenating portions of at least one of the one or more components;

identify an answer document by applying a hashing algorithm to different answer documents until the hashing algorithm produces an answer hash value that is a solution to the predetermined computational puzzle,

wherein the answer hash value is calculated by;

combining one of the different answer documents and the puzzle input; and

hashing the combination of the one of the different answer documents and the puzzle input using the hashing algorithm. wherein the hashing algorithm alters a standard application of SHA-1 sub functions; and

send the electronic message to the receiving side domain, wherein the electronic message includes the identified answer document and the electronic message and enables verification by the receiving side domain that the sending messaging server expended computational resources without further communication with the sending messaging server.

24. A computer program product for use in a receiving domain that is network connectable to one or more sending domains, the receiving domain including one or more receiving messaging servers configured to receive electronic messages from the sending domains, the computer program product for implementing a method for determining if a sending messaging server solved a predetermined computational puzzle before sending an electronic message, the computer program product comprising one or more computer storage media having stored thereon computer executable instructions that, when executed by a processor, cause the receiving domain to perform the following:

receive an electronic message that includes electronic message data and an answer document;

reproduce a puzzle input from one or more predetermined components of the electronic message, the one or more predetermined components selected from a group consisting of;

a message body, a message attachment, and a message header, wherein reproducing puzzle input includes one or more of;

extracting portions of at least one of the one or more predetermined components, hashing portions of at least one of the one or more predetermined components, and concatenating portions of at least one of the one or more predetermined components, and wherein reproducing a puzzle input from one or more predetermined components of the electronic message comprises an act of applying a hashing algorithm that alters the standard application of SHA-1 sub-functions;

determine if a verifying hash value, is a solution to the predetermined computational puzzle, the verifying hash value being calculated by combining the answer document and the puzzle input and hashing the combination of the answer document and the puzzle input using the hashing algorithm; and

provide results of the determination to a message classification module such that the message classification module determines, based on the results, whether the received electronic message is spam.