Efficient authentication for mobile and pervasive computing

• US 9,166,793 B2
• Filed: 12/04/2012
• Issued: 10/20/2015
• Est. Priority Date: 12/05/2011
• Status: Expired due to Fees

• Current Assignee: University of Washington
• Original Assignee: University of Washington
• Inventors: Poovendran, Radha, Alomair, Basel
• Primary Examiner(s): PYZOCHA, MICHAEL J
• Application Number:
  US13/705,068
• Publication Number:
  US 20130145169A1
• Time in Patent Office: 1,050 Days
• Field of Search: 713/181, 726/4
• US Class Current: 1/1
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 9/0643 Hash functions, e.g. MD5, SHA, HMAC or f9 MAC
• CPC Class Codes: H04L 9/3242 involving keyed hash functions, e.g. message authentication codes [MACs], CBC-MAC or HMAC

Abstract

A method and system for authenticating messages is provided. A message authentication system generates an encrypted message by encrypting with a key a combination of a message and a nonce. The message authentication system generates a message authentication code based on a combination of the message and the nonce modulo a divisor. To decrypt and authenticate the message, the message authentication system generates a decrypted message by decrypting with the key the encrypted message and extracts the message and the nonce. The message authentication system then regenerates a message authentication code based on a combination of the extracted message and the extracted nonce modulo the divisor. The message authentication system then determines whether the regenerated message authentication code matches the original message authentication code. If the codes match, then the integrity and authenticity of the message are verified.

Claims

1. A method performed by a computing device to provide authentication for a message, the method comprising:

generating by the computing device an encrypted message by encrypting with an encryption key an encryption combination of the message and a nonce;

generating by the computing device an authentication code based on a result of an authentication combination of the message and the nonce modulo a divisor;

sending by the computing device the encrypted message and the authentication code to another computing device with access to the encryption key wherein upon receiving the encrypted message and the authentication code, the other computing device decrypts the received encrypted message with the encryption key and extracts the message and the nonce, regenerates the authentication code based on the authentication combination of the extracted message and the extracted nonce modulo the divisor, and when the generated authentication code matches the regenerated authentication code, verifies integrity and authenticity of the extracted message; and

receiving the encrypted message and authentication code at the other computing device and verifying the integrity and authenticity of the encrypted message by decrypting the message, extracting the nonce, regenerating the authentication code, and comparing the regenerating authentication code to the generated authentication code.

2. The method of claim 1 wherein the encryption combination of the message and the nonce is a concatenation of the message and the nonce.

3. The method of claim 2 wherein the authentication combination of the message and the nonce is an addition of the nonce to the message multiplied by an authentication key.

4. The method of claim 3 wherein the divisor is a prime number.

5. The method of claim 1 wherein the authentication combination of the message and the nonce is an addition of the nonce to the message multiplied by an authentication key.

6. The method of claim 5 wherein the divisor is a prime number.

7. The method of claim 1 further comprising:

receiving by the other computing device the encrypted message and the authentication code;

decrypting by the other computing device the received encrypted message with the encryption key;

extracting by the other computing device the decrypted message and the decrypted nonce;

regenerating by the other computing device the authentication code based on the authentication combination of the extracted message and the extracted nonce modulo the divisor; and

determining by the other computer device the integrity and the authenticity of the extracted message when the received authentication code matches the regenerated authentication code.

8. A method performed by a computing device to provide authentication for a message, the method comprising:

generating by the computing device an encrypted message by encrypting with a key an encryption combination of the message and a nonce, the encrypting being based on a block cipher;

generating by the computing device an authentication code based on a result of an authentication combination of the message and the nonce modulo a divisor;

sending by the computing device the generated encrypted message and the generated authentication code to another computing device with access to the key and the divisor so that the other computing device can verify the integrity and authenticity of encrypted message; and

receiving the encrypted message and authentication code at the other computing device and verifying the integrity and authenticity of the encrypted message.

9. The method of claim 8 wherein the encryption combination of the message and the nonce is a concatenation of the message and the nonce that is encrypted as a block.

10. The method of claim 9 wherein the authentication combination is a sum of the message and the nonce modulo a power of two.

11. The method of claim 8 wherein the authentication combination is a sum of the message and the nonce modulo a power of two.

12. The method of claim 8 wherein the encrypting is based on cipher-block chaining.

13. The method of claim 12 wherein the encryption combination includes an encrypted nonce part based on encrypting with the key an exclusive OR of an initialization vector and a nonce.

14. The method of claim 13 wherein the encryption combination includes an encrypted message part based on encrypting with the key an exclusive OR of the encrypted nonce part and the message.

15. The method of claim 14 wherein the encrypted message includes the initialization vector, the encrypted nonce part, and the encrypted message part.

16. The method of claim 15 wherein the authentication combination is a sum of the message and the nonce modulo a power of two.

17. The method of claim 14 wherein the authentication combination is a sum of the message and the nonce modulo a power of two.

18. The method of claim 12 wherein the authentication combination is a sum of the message and the nonce modulo a power of two.

19. One or more computer-readable storage media that are not a transitory, propagating signal storing computer-executable instructions for controlling a device to generate an authentication code for a message, the instructions comprising:

instructions that generate an encrypted message by encrypting with an encryption key a concatenation of the message and a nonce;

instructions that generate an authentication code by generating a dividend by multiplying the message by an authentication key and adding the nonce and setting the authentication code to the dividend modulo a divisor that is a prime number;

instructions that send to another device the generated encrypted message and the generated authentication code so that the other device can decrypt the generated encrypted message using the encryption key to generate a decrypted message and a decrypted nonce and regenerate the authentication code using the decrypted message, the decrypted nonce, and the divisor to verify integrity and authenticity of the decrypted message; and

instructions that verify the integrity and authenticity of an encrypted message.

20. One or more computer-readable storage media that are not a transitory, propagating signal storing computer-executable instructions for controlling a device to generate an authentication code for a message, the instructions comprising:

instructions that generate an encrypted message using a key as a concatenation of an initialization vector, an encrypted nonce part, and an encrypted message part, the encrypted message being encrypted with a block cipher;

instructions that generate an authentication code by generating a dividend by adding the message and a nonce and setting the authentication code to the dividend modulo a divisor that is a power of two;

instructions that send to another device the generated encrypted message and the generated authentication code so that the other device can decrypt the generated encrypted message using the key to generate a decrypted message and a decrypted nonce and regenerate the authentication code using the decrypted message, the decrypted nonce, and the divisor to verify integrity and authenticity of the decrypted message; and

instructions that verify the integrity and authenticity of an encrypted message.

21. The one or more computer-readable storage media of claim 20 wherein the block cipher is based on cipher-block chaining.

22. The one or more computer-readable storage media of claim 20 wherein the instructions that verify the integrity and authenticity of the encrypted message decrypt the generated encrypted message using the key to generate a decrypted message and a decrypted nonce and regenerate the authentication code using the decrypted message, the decrypted nonce, and the divisor.

23. One or more computer-readable storage media that are not a transitory, propagating signal storing computer-executable instructions for controlling a device to verify the integrity and authenticity of an encrypted message, the instructions comprising:

instructions that receive the encrypted message and an authentication code;

instructions that decrypt the received encrypted message with an encryption key;

instructions that extract a message and an nonce from the decrypted message;

instructions that generates an authentication code based on an authentication combination of the extracted message and the extracted nonce modulo a divisor; and

instructions that, when the generated authentication code matches the received authentication code, verifies the integrity and authenticity of the extracted message.

24. The one or more computer-readable storage media of claim 23 wherein the encrypted messages is an encryption of a concatenation of the message and the nonce.

25. The one or more computer-readable storage media of claim 24 wherein the authentication combination of the message and the nonce is an addition of the nonce to the message multiplied by an authentication key.

26. The one or more computer-readable storage media of claim 23 wherein the divisor is a prime number.

27. The one or more computer-readable storage media of claim 23 wherein the authentication combination is a sum of the message and the nonce modulo a power of two.