EFFICIENT DISTRIBUTION OF COMPUTATION IN KEY AGREEMENT

• US 20100306525A1
• Filed: 05/28/2009
• Published: 12/02/2010
• 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
• Granted Patent: US 8,331,568 B2
• Time in Patent Office: Days
• US Class Current: 713/151
• 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.

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 creating of said one or more signatures is performed with an 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.

5. The method of claim 1, wherein creation of said one or more signatures is performed with an 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.

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

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

8. 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 an algorithm that is used to derive said secret key from said first value;

communicating said choice of cipher suite to said client

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

9. One or more computer-readable storage media that store executable instructions that, when executed by a computer, cause the computer to perform acts comprising:

determining that a public key of a client is to be sent to a server in connection with a key agreement to be performed between said client and said server;

sending, to said server, said public key of said client and a request to use a cipher suite in which said server encrypts a value with said public key of said client;

receiving, from said server, said value encrypted by said public key;

decrypting said value with a private key of said client that corresponds to said public key; and

engaging in encrypted communications with said server using a secret key that comprises, or is derived from, said value.

10. The one or more computer-readable storage media of claim 9, wherein said determining comprises:

determining that, in the last communication between said client and said server, said server chose to use a key agreement protocol that uses said public key of said client.

11. The one or more computer-readable storage media of claim 9, wherein said determining comprises:

determining that said client has not previously communicated with said server.

12. The one or more computer-readable storage media of claim 9, wherein said determining comprises:

receiving, from said server, an error message indicating that said server has not received a public key associated with said client; and

restarting communication with said server, wherein the restarted communication includes sending, from said client to said server, said public key of said client.

13. The one or more computer-readable storage media of claim 9, wherein said determining comprises:

determining that a likelihood that said server will choose a cipher suite that uses said public key of said client exceeds a threshold.

14. The one or more computer-readable storage media of claim 9, wherein said acts further comprise:

including said public key of said client in a TLS ClientHello message; and

wherein said sending comprises;

sending said ClientHello message to said server.

15. The one or more computer-readable storage media of claim 9, wherein said acts further comprise:

deriving said secret key from said value by applying, to said value, an algorithm that is known to both said client and to said server.

16. A server for engaging in communication with a client, the server comprising:

a processor;

a data remembrance component;

server software that comprises a plurality of cipher suites, said cipher suites comprising;

a first cipher suite that implements a first key agreement protocol in which said server uses said server'"'"'s private key to decrypt an encrypted value received from said client; and

a second cipher suite that implements a second key agreement protocol in which said server chooses a value and encrypts said value with said client'"'"'s public key, wherein said server receives, from said client, a public key and a list of cipher suites that said client supports, said list comprising said second cipher suite, wherein said server chooses said value, encrypts said value with the public key received from said client, signs, with said server'"'"'s private key, a message that comprises, or is derived from, (a) the encrypted value, and (b) data received from said client, to create a signature, and sends the encrypted value and said signature to said client.

17. The server of claim 16, wherein said second cipher suite specifies a signing algorithm that said server is to use when creating said signature, and wherein said signing algorithm comprises a Feige-Fiat-Shamir signature scheme.

18. The server of claim 16, wherein said second cipher suite specifies a signing algorithm that said server is to use when creating said signature, and wherein said signing algorithm comprises a Guillou-Quisquater signature scheme.

19. The server of claim 16, wherein said server implements a TLS communication protocol, and wherein said server receives said client'"'"'s public key as part of a ClientHello message from said client.

20. The server of claim 16, wherein said server receives, from said client, a ClientHello message that does not contain said client'"'"'s public key, and wherein said server sends, to said client, an error message to indicate that said client'"'"'s public key is missing.