Prevention of unauthorized forwarding and authentication of signatures

• US 8,090,954 B2
• Filed: 03/16/2007
• Issued: 01/03/2012
• Est. Priority Date: 03/16/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Paya, Cem, Benaloh, Josh
• Primary Examiner(s): Zand, Kambiz
• Assistant Examiner(s): GUIRGUIS, MICHAEL M
• Application Number:
  US11/687,262
• Publication Number:
  US 20080229111A1
• Time in Patent Office: 1,754 Days
• Field of Search: 713/176, 713/157, 713/180
• US Class Current: 713/180
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 2209/80 Wireless network architectures or network communication protocols for wireless network security H04W12/00
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

A forwarding signature comprises a modified digital signature, modified using a predetermined parameter between a sender and an intended recipient. An intended recipient of the forwarding signature can verify that the forwarding signature corresponds to the message, but, can neither derive the original digital signature nor generate a new forwarding signature for a different parameter. Generation and verification of the forwarding signature is accomplished with access to the public key of a public/private cryptographic key pair, the original signed message, and the predetermined parameter. Access to the private key is not needed.

Claims

1. An authentication method comprising:

receiving in a processor of a receiving node, a message and a forwarding signature (T), wherein;

the forwarding signature has been generated in a transmitting node by applying a predetermined tweak parameter (p) to a confidential signature (S), the predetermined tweak parameter having a value that is selected in the transmitting node; and

wherein the confidential signature has been generated by signing the message with a private key of a public/private key pair;

operating on the forwarding signature to generate a first value, wherein the forwarding signature is operated on utilizing a public key of the public/private key pair;

operating on the message to generate a second value, wherein the message is operated on utilizing the predetermined tweak parameter;

comparing the first value and the second value; and

authenticating the message in accordance with a result of comparing the first value and the second value.

2. A method in accordance with claim 1, wherein the predetermined tweak parameter that is selected in the transmitting node is agreed to by the receiving node.

3. A method in accordance claim 1, wherein:

the public key comprises an exponent value, and

operating on the forwarding signature comprises raising the signature to a power equal to the exponent value.

4. A method in accordance claim 1, wherein:

operating on the message comprises raising the message to a power equal to the predetermined tweak parameter modulo an integer value.

5. A method in accordance claim 1, wherein:

the confidential signature (S) is generated in accordance with a formula;

S=m^d mod N, wherein;

m represents the message;

d represent a exponent value of the private key; and

N represents an integer value; and

the forwarding signature (T) is generated in accordance with a formula;

T=S^Hash(p) mod N, wherein;

p represents the predetermined tweak parameter.

6. A method in accordance with claim 5, wherein:

the forwarding signature is operated on in accordance with a formula;

T^e mod N, wherein e represents an exponent parameter of the public key; and

the message is operated on in accordance with a formula;

m^Hash(p) mod N.

17. A method in accordance with claim 1 wherein the predetermined tweak parameter comprises an identity of the receiving node in the form of a name of a first website, and wherein the predetermined tweak parameter constitutes a first tweaked ticket usable only at the first website.

18. A method in accordance with claim 17 further comprising:

using the first tweaked ticket to derive a plurality of tweaked tickets.

19. A method in accordance with claim 1 further comprising:

tweaking the forwarding signature received at the receiving node by applying a second tweak parameter comprising an identity of a second node.

20. A method in accordance with claim 19 further comprising:

receiving at the second node, the forwarding signature upon which the second tweak parameter has been applied; and

verifying at the second node, that the forwarding signature has propagated in sequence through the first and the second nodes.

7. An authentication system comprising:

an input device of a receiving processor node configured to receive a message and a forwarding signature, wherein;

the forwarding signature has been generated in a transmitting processor node by applying a predetermined tweak parameter (p) to a confidential signature (s), the predetermined tweak parameter having a value that is determined and generated in the transmitting processor node; and

wherein the confidential signature has been generated by signing the message with a private key of a public/private key pair;

a processing unit coupled to the input device, the processing unit configured to;

operate on the forwarding signature to generate a first value, wherein the forwarding signature is operated on utilizing a public key of the public/private key pair;

operate on the message to generate a second value, wherein the message is operated on utilizing the predetermined tweak parameter;

compare the first value and the second value; and

authenticate the message in accordance with a result of comparing the first value and the second value.

8. A system in accordance with claim 7, wherein the predetermined tweak parameter that is determined and generated in the transmitting processor node is agreed to by the receiving processor node.

9. A system in accordance claim 7, wherein:

the public key comprises an exponent value, and

operating on the forwarding signature comprises raising the signature to a power equal to the exponent value.

10. A system in accordance claim 7, wherein:

the confidential signature (S) is generated in accordance with a formula;

S=m^d mod N, wherein;

m represents the message;

d represent a exponent value of the private key; and

N represents an integer value; and

the forwarding signature (T) is generated in accordance with a formula;

T=S^Hash(p) mod N, wherein;

p represents the predetermined parameter.

11. A system in accordance with claim 10, wherein:

the forwarding signature is operated on in accordance with a formula;

T^e mod N, wherein e represents an exponent parameter of the public key; and

the message is operated on in accordance with a formula;

m^Hash(p) mod N.

12. A computer-readable storage medium that is not a transient signal, the computer-readable storage medium having stored thereon computer-executable instructions for performing authentication by performing the steps of:

receiving in a first node, a message and a forwarding signature (T), wherein;

the forwarding signature has been generated in a second node by applying a predetermined tweak parameter (p) to a confidential signature (S), the

predetermined tweak parameter having a value that is determined and generated in the second node; and

wherein the confidential signature has been generated by signing the message with a private key of a public/private key pair;

operating on the forwarding signature to generate a first value, wherein the forwarding signature is operated on utilizing a public key of the public/private key pair;

operating on the message to generate a second value, wherein the message is operated on utilizing the predetermined tweak parameter;

comparing the first value and the second value; and

authenticating the message in accordance with a result of comparing the first value and the second value.

13. A computer-readable storage medium in accordance with claim 12, wherein the predetermined tweak parameter is known to both a sender and a recipient of the message.

14. A computer-readable storage medium in accordance claim 12, wherein:

the public key comprises an exponent value, and

operating on the forwarding signature comprises raising the signature to a power equal to the exponent value.

15. A computer-readable storage medium in accordance claim 12, wherein:

operating on the message comprises raising the message to a power equal to the predetermined tweak parameter modulo an integer value.

16. A computer-readable storage medium in accordance claim 12, wherein:

the confidential signature (S) is generated in accordance with a formula;

S=m^d mod N, wherein;

m represents the message;

d represent a exponent value of the private key; and

N represents an integer value; and

the forwarding signature (T) is generated in accordance with a formula;

T=S^Hash(p) mod N, wherein;

p represents the predetermined parameter; and

the forwarding signature is operated on in accordance with a formula;

T^e mod N, wherein e represents an exponent parameter of the public key; and

the message is operated on in accordance with a formula;

m^Hash(p) mod N.