Efficient distribution of computation in key agreement

• US 8,331,568 B2
• Filed: 05/28/2009
• Issued: 12/11/2012
• Est. Priority Date: 05/28/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ferguson, Niels Thomas
• Primary Examiner(s): Chea, Philip
• Assistant Examiner(s): Traore, Fatoumata
• Application Number:
  US12/474,265
• Publication Number:
  US 20100306525A1
• Time in Patent Office: 1,293 Days
• Field of Search: None
• US Class Current: 380/285
• CPC Class Codes: H04L 63/0442 wherein the sending and receiving network entities apply asymmetric encryption, i.e. different keys for encryption and decryption cryptographic mechanisms or cryptographic arrangements for public-key encryption H04L9/30
• CPC Class Codes: H04L 63/06 for supporting key management in a packet data network cryptographic mechanisms or cryptographic arrangements for key management H04L9/08
• CPC Class Codes: H04L 63/166 at the transport layer

Abstract

In Transport Layer Security (TLS) or other communication protocols, the load on the server may be lowered by reducing the number of expensive decryption operations that the server has to perform. When a client contacts a server, the client sends the server the client'"'"'s public key. The server chooses a secret value, encrypts the value with the client'"'"'s public key, and sends the encrypted value to the client. When the client decrypts the secret, the server and client share a secret value, which may be used to derive an encryption key for further messages. In many key agreement schemes, the client chooses and encrypts the secret value, and the server recovers the value with an expensive decryption operation. By instead having the server choose the value and send it to the client, an expensive decryption operation is redistributed from the server to the client, thereby freeing server resources.

Claims

1. A method of participating in communication with a client, the method comprising:

using a processor to perform acts comprising;

receiving, at a server, a first public key from a client;

choosing a first value;

encrypting said first value with said first public key of said client to produce an encrypted value;

using a key pair of said server to sign (a) said encrypted value, or a second value derived from said encrypted value and (b) data received by said server from said client, or a third value derived from said data, thereby creating a signature;

sending said encrypted value, a second public key of said key pair, and said one or more signatures to said client; and

engaging in encrypted communication with said client using a secret key that comprises, or is derived from, said first value,

wherein creation of said one or more signatures is performed with a first algorithm in which a number of multiplications to be performed is determined by a number of bits set to one in a fourth value that is derived from the data to be signed, and wherein said acts further comprise;

creating an n-bit fifth value that is derived from said fourth value;

encoding said n-bit fifth value in an m-bit encoding in which no more than k bits are set to one, wherein k<

n<

m;

wherein at least one of said one or more signatures is calculated using said m-bit encoding.

2. The method of claim 1, wherein said use of said key pair to sign is performed using a Feige-Fiat-Shamir signature scheme.

3. The method of claim 1, wherein said use of said key pair to sign is performed using a Guillou-Quisquater signature scheme.

4. The method of claim 1, wherein said first public key is received by said server as part of a ClientHello message in a TLS communication session.

5. The method of claim 1, wherein said server supports a plurality of cipher suites, wherein each of said cipher suites implements a particular procedure of key agreement between said server and said client, and wherein said acts further comprise:

receiving, at said server from said client, a list of one or more cipher suites that said client requests to use;

identifying, from said list, a first one of said cipher suites that said server supports, said first one of said cipher suites implementing a key agreement procedure that makes use of said first public key from said client as part of its key agreement procedure, said server also supporting at least one cipher suite that does not make use of said first public key from said client as part of its key agreement procedure; and

communicating to said client that said first one of said cipher suites has been chosen.

6. The method of claim 1, wherein said secret key is derived from said first value, and wherein said acts further comprise:

determining a choice of cipher suite to use for communication with said client, said cipher suite defining a second algorithm that is used to derive said secret key from said first value;

communicating said choice of cipher suite to said client; and

using said second algorithm to derive said secret key from said first value.

7. A method of participating in communication with a client, the method comprising:

using a processor to perform acts comprising;

receiving, at a server, a first public key from a client;

choosing a first value;

encrypting said first value with said first public key of said client to produce an encrypted value;

using a key pair of said server to sign (a) said encrypted value, or a second value derived from said encrypted value and (b) data received by said server from said client, or a third value derived from said data, thereby creating a signature;

sending said encrypted value, a second public key of said key pair, and said one or more signatures to said client; and

engaging in encrypted communication with said client using a secret key that comprises, or is derived from, said first value,

wherein creation of said one or more signatures is performed with a first algorithm in which a number of multiplications to be performed is determined by a number of bits that are set to one in a fourth value that is derived from the data to be signed, and wherein said acts further comprise;

creating an n-bit fifth value that is derived from the data to be signed, wherein the data to be signed comprises, or is derived from, said encrypted value;

dividing said n-bit fifth value into d segments of b bits each;

creating an m-bit encoding that comprises d blocks each of which has 2^b bits; and

for each of the d blocks in the m-bit encoding, setting exactly one of the bits in the block to one based on a corresponding b-bit segment in the n-bit fifth value, wherein at least one of said one or more signatures is calculated on said m-bit encoding.

8. The method of claim 7, wherein said use of said key pair to sign is performed using a Feige-Fiat-Shamir signature scheme.

9. The method of claim 7, wherein said use of said key pair to sign is performed using a Guillou-Quisquater signature scheme.

10. The method of claim 7, wherein said first public key is received by said server as part of a ClientHello message in a TLS communication session.

11. The method of claim 7, wherein said server supports a plurality of cipher suites, wherein each of said cipher suites implements a particular procedure of key agreement between said server and said client, and wherein said acts further comprise:

receiving, at said server from said client, a list of one or more cipher suites that said client requests to use;

identifying, from said list, a first one of said cipher suites that said server supports, said first one of said cipher suites implementing a key agreement procedure that makes use of said first public key from said client as part of its key agreement procedure, said server also supporting at least one cipher suite that does not make use of said first public key from said client as part of its key agreement procedure; and

communicating to said client that said first one of said cipher suites has been chosen.

12. The method of claim 7, wherein said secret key is derived from said first value, and wherein said acts further comprise:

determining a choice of cipher suite to use for communication with said client, said cipher suite defining a second algorithm that is used to derive said secret key from said first value;

communicating said choice of cipher suite to said client; and

using said second algorithm to derive said secret key from said first value.

13. One or more computer-readable memories that store executable instructions to participate in communication with a client, executable instructions, when executed by a computer, causing the computer to perform acts comprising:

receiving, at a server, a first public key from a client;

choosing a first value;

encrypting said first value with said first public key of said client to produce an encrypted value;

using a key pair of said server to sign (a) said encrypted value, or a second value derived from said encrypted value and (b) data received by said server from said client, or a third value derived from said data, thereby creating a signature;

sending said encrypted value, a second public key of said key pair, and said one or more signatures to said client; and

engaging in encrypted communication with said client using a secret key that comprises, or is derived from, said first value,

wherein creation of said one or more signatures is performed with a first algorithm in which a number of multiplications to be performed is determined by a number of bits set to one in a fourth value that is derived from the data to be signed, and wherein said acts further comprise;

creating an n-bit fifth value that is derived from said fourth value;

encoding said n-bit fifth value in an m-bit encoding in which no more than k bits are set to one, wherein k<

n<

m;

wherein at least one of said one or more signatures is calculated using said m-bit encoding.

14. The one or more computer-readable memories of claim 13, wherein said use of said key pair to sign is performed using a Feige-Fiat-Shamir signature scheme.

15. The one or more computer-readable memories of claim 13, wherein said use of said key pair to sign is performed using a Guillou-Quisquater signature scheme.

16. The one or more computer-readable memories of claim 13, wherein said first public key is received by said server as part of a ClientHello message in a TLS communication session.

17. The one or more computer-readable memories of claim 13, wherein said server supports a plurality of cipher suites, wherein each of said cipher suites implements a particular procedure of key agreement between said server and said client, and wherein said acts further comprise:

receiving, at said server from said client, a list of one or more cipher suites that said client requests to use;

identifying, from said list, a first one of said cipher suites that said server supports, said first one of said cipher suites implementing a key agreement procedure that makes use of said first public key from said client as part of its key agreement procedure, said server also supporting at least one cipher suite that does not make use of said first public key from said client as part of its key agreement procedure; and

communicating to said client that said first one of said cipher suites has been chosen.

18. The one or more computer-readable memories of claim 13, wherein said secret key is derived from said first value, and wherein said acts further comprise:

determining a choice of cipher suite to use for communication with said client, said cipher suite defining a second algorithm that is used to derive said secret key from said first value;

communicating said choice of cipher suite to said client; and

using said second algorithm to derive said secret key from said first value.