Method and apparatus for stepping pair keys in a key-management scheme

• US 5,668,877 A
• Filed: 12/02/1994
• Issued: 09/16/1997
• Est. Priority Date: 06/10/1994
• Status: Expired due to Term

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Aziz, Ashar
• Primary Examiner(s): CANGIALOSI, SALVATORE A
• Application Number:
  US08/348,725
• Time in Patent Office: 1,019 Days
• Field of Search: 380/21, 380/23, 380/30
• US Class Current: 380/30
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 12/4604 LAN interconnection over a backbone network, e.g. Internet, Frame Relay
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• 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/061 for key exchange, e.g. in peer-to-peer networks cryptographic mechanisms or cryptographic arrangements for key agreement H04L9/0838
• CPC Class Codes: H04L 63/0823 using certificates cryptographic mechanisms or cryptographic arrangements for entity authentication involving certificates H04L9/3263
• CPC Class Codes: H04L 9/0844 with user authentication or key authentication, e.g. ElGamal, MTI, MQV-Menezes-Qu-Vanstone protocol or Diffie-Hellman protocols using implicitly-certified keys
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A method and apparatus for generating additional implicit keys from a key [K_ij ]_N without the necessity of generating a new Diffie-Helman (DH) certificate or requiring communication between nodes to change implicit master keys is disclosed. A first data processing device (node I) is coupled to a private network which is in turn coupled to the Internet. A second data processing device (node J) is coupled to the same, or to a different network, which is also coupled to the Internet, such that node I communicates with node J using the Internet protocol. Node I is provided with a secret value i and a public value. Data packets (referred to as "datagrams") are encrypted to enhance network security. Each node maintains an internal value of N which is incremented based on time and upon the receipt of a data packet from another node. The key [K_ij ]_N.sbsb.i is derived from the appropriate quantity of α^Nij by using high order key-sized bits of the respective quantity. The present invention then utilizes the key [K_ij ]_N.sbsb.i to encrypt a transient key which is referred to as K_p. Node I encrypts the IP data in K_p and encrypts K_p in [K_ij ]_N.sbsb.i. Node I transmits the encrypted IP datagram packet in the encrypted key K_p to the receiving node J. Node I further includes its current internal value of N_i in the outgoing packet. The present invention also provides for the application of one-way functions to the shared secret to enhance security. Thus, either node I or node J may change the context such that if in the future [K_ij ]_N.sbsb.i is compromised, or is not useable by a cracker to either decrypt prior encrypted packets. The present invention discloses methods and apparatus for achieving perfect forward security for closed user groups, and for the application of the SKIP methodology to datagram multicast protocols.

Claims

1. A method for a first data processing device (node I) to send data to a second data processing device (node J), comprising the steps of:

providing a secret value i and a first public value to said node I;

providing a context variable N_i to said node I;

providing a secret value j, and a second public value to said node J;

said node I performing the steps of;

obtaining a certificate for node J and determining said second public value for node J from said certificate for node J;

computing a key {K_ij }_N.sbsb.i from a shared secret derived from said second public value, said secret value i, and said context variable N_i ;

utilizing said key {K_ij }_N.sbsb.i to encrypt a randomly generated transient key K_p, and encrypting a data packet to be transmitted to node J using said key K_p ;

said node I sending said data packet encrypted using said key K_p to said node J;

said node I notifying said node J of the current value of N_i.

2. The method as defined by claim 1, further comprising the steps of:

providing a context variable N_j to said node J;

said node J performing the steps of;

receiving said encrypted data packet from node I;

obtaining a certificate for said node I and determining said first public value for node I from said certificate for node I;

comparing said context variable N_j to said context variable N_i ;

if N_i >

N_j, computing said key {K_ij }_N.sbsb.i from a shared secret derived from said first public value, said secret value j, and said context variable N_i ; and

if N_i >

N_j and said encrypted packet is valid, setting said context variable N_j to equal N_i.

3. The method as defined by claim 2, further including the steps by node J of:

utilizing said key {K_ij }_N.sbsb.i to decrypt said transient key K_p, and

decrypting said encrypted data packet using said transient key K_p, whereby node J decrypts data received from and previously encrypted by node I.

4. The method as defined by claim 3 further including the steps by node J of:

computing a key {K_ij }_N.sbsb.i from a shared secret derived from said first public value,

said secret value j, and said context variable N_j ; and

if N_i =N_j,

utilizing said key {K_ij }_N.sbsb.j to decrypt said transient key K_p, and

decrypting said encrypted data packet using said transient key K_p ;

whereby node J decrypts data received from and previously encrypted by node I.

5. The method as defined by claim 3 further including the steps by node J of discarding said encrypted data packet and signaling an error condition if N_i <

N_j.

6. The method as defined by claim 3, wherein said nodes I and J increment said N_i and N_j, respectively after a predetermined time period.

7. The method as defined by claim 6, wherein said data packet includes a context field including said context variable N_i.

8. The method as defined by claim 6, wherein said first public value is α

ⁱ mod p.

9. The method as defined by claim 8, wherein said second public value is α

^j mod p.

10. The method as defined by claim 9, wherein N_i and N_j are initially set equal to 1.

11. The method as defined by claim 6, wherein said first public value is α

.sbsp.(M.spsp.Nⁱ.sbsp.)i mod p for some integer M.

12. The method as defined by claim 11, wherein said second public value is α

.sbsp.(M.spsp.N^j.sbsp.)j mod p for some integer M.

13. The method as defined by claim 12, wherein M=2 and N_i and N_j are initially set equal to 0.

14. The method as defined by claim 6, wherein said key {K_ij }_N.sbsb.i is used as a key for a shared key cryptosystem (SKCS).

15. The method as defined by claim 14, wherein said SKCS is DES.

16. The method as defined by claim 14, wherein said SKCS is RC2.

17. The method as defined by claim 14, wherein said data packet includes a source address, a destination address and an SKCS identifier field.

18. The method as defined by claim 17, wherein said data packet further includes a message indicator field.

19. The method as defined by claim 6, wherein α

and p are system parameters, and where p is a prime number.

20. An apparatus for encrypting data for transmission from a first data processing device (node I) to a second data processing device (node J), comprising:

node I including a first storage device configured to store a secret value i, a first public value, and an internal context variable N_i ;

node J including a second storage device configured to store a secret value j, a second public value, and an internal context variable N_j ;

node I including an encrypting device configured to encrypt a data packet to be transmitted to node J, said data packet being encrypted using a first certificate for node J to determine said second public value for node J;

said encrypting device further deriving a key {K_ij }_N.sbsb.i from the value of a shared secret derived from said second public value, said secret value i, and said context variable N_i, and

said encrypting device encrypting a randomly generated transient key K_p using {K_ij }_N.sbsb.i, and encrypting said data packet using said transient key K_p ;

node I further including an interface circuit configured to transmit said encrypted data packet to said node J and to notify said node J of the value of N_i.

21. The apparatus as defined by claim 20, wherein said node J further includes:

a receiver configured to receive said encrypted data packet from node I;

a decrypting device coupled to said receiver configured to decrypt said data packet from node I.

22. The apparatus as defined by claim 21, wherein said decrypting device obtains a second certificate for said node I, determines said first public value for node I, and computes a shared value secret derived from said first public value and said secret value j.

23. The apparatus as defined by claim 22, wherein said decrypting device compares said internal context variable N_j with said context variable N_i.

24. The apparatus as defined by claim 23, wherein

if N_i >

N_j said node J computes said key {K_ij }_N.sbsb.i from a shared secret derived from said first public value, said secret value j, and said context variable N_i ;

said encrypting device utilizing said key {K_ij }_N.sbsb.i to decrypt said transient key K_p, and decrypting said received data packet using said transient key K_p, and setting N_j equal to N_i if said data packet is valid.

25. The apparatus as defined by claim 24, wherein

said node J computes said key {K_ij }_N.sbsb.i from a shared secret derived from said first public value, said secret value j, and said context variable N_i, and

if N_i =N_j said encrypting device utilizes said key {K_ij }_N.sbsb.i to decrypt said transient key K_p and decrypts said received data packet using said transient key K_p.

26. The apparatus as defined by claim 25, wherein if N_i <

N_j said node J discards said data packet.

27. The apparatus as defined by claim 26, wherein said nodes I and J increment said N_i and N_j, respectively after a predetermined time period.

28. The apparatus as defined by claim 27, wherein said data packet includes a context field storing said value of N_i to notify said node J of said value of N_i.

29. The apparatus as defined by claim 28 wherein said first public value is α

^Ni mod p.

30. The apparatus as defined by claim 29, wherein said second public value is α

^Nj mod p.

31. The apparatus as defined by claim 30, wherein N_i and N_j are initially set equal to 1.

32. The apparatus as defined by claim 31, wherein said first public value is α

.sup.(M.spsp.N.sup.)i mod p.

33. The apparatus as defined by claim 32, wherein said second public value is α

.sup.(M.spsp.N.sup.)j mod p.

34. The apparatus as defined by claim 33, wherein M=2.

35. The apparatus as defined by claim 34, wherein said key {K_ij }_N.sbsb.i is used as a key for a shared key cryptosystem (SKCS) and is derived from α

.sup.(M.spsp.N.sup.)ij.

36. The apparatus as defined by claim 35, wherein said data packet includes a source address, a destination address and an SKCS identifier field.

37. The apparatus as defined by claim 36, wherein said data packet further includes a message indicator field.

38. The apparatus as defined by claim 37, wherein α

and p are system parameters, and where p is a prime number.

39. The apparatus as defined by claim 38, wherein said SKCS is DES.

40. The apparatus as defined by claim 38, where said SKCS is RC2.