Abstract:
Various embodiments include a network manager for managing network keys in a network having a plurality of nodes, the device including: a memory; and a processor configured to: determine N nodes to blacklist, wherein N is an integer; select a polynomial function from a plurality of polynomial functions of degree K and wherein the polynomial functions define plurality of secret network keys; generate K-N random abscissa values, wherein none of the random abscissa values are not found in a list of node abscissa values; calculate K-N polynomial function values for the K-N random abscissa values; calculate N polynomial function values for N node abscissa values associated with the N blacklisted nodes; transmit a message to nodes in the network including an indication of the selected polynomial function, the K-N random abscissa values, the N node abscissa values associated with the N blacklisted nodes, the K-N calculated polynomial function values, and the N calculated polynomial function values.

Description:
TECHNICAL FIELD 
       [0001]    Various embodiments disclosed herein relate generally to network security. 
       CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0002]    This application claims the priority under 35 U.S.C. §119 of Romania patent application no. A201600313, filed May 4, 2016 the contents of which are incorporated by reference herein. 
       BACKGROUND 
       [0003]    Key distribution in networking has many different types of networks and cryptographic systems to account for. In public key cryptography, both a public and private key pair are distributed, the private key being specific to the intended recipient. The private key may be used for decryption, while the public key may be used for encryption of data. Symmetric key encryption schemes are different in the sense that they use the same key on both sides of the communication at the recipient as well as at the sender&#39;s end. Similarly, the same key is used for both encryption as well as decryption in symmetric key algorithms. 
       SUMMARY 
       [0004]    A brief summary of various embodiments is presented below. Some simplifications and omissions may be made in the following summary, which is intended to highlight and introduce some aspects of the various embodiments, but not to limit the scope of the invention. Detailed descriptions of a preferred embodiment adequate to allow those of ordinary skill in the art to make and use the inventive concepts will follow in later sections. 
         [0005]    Various embodiments described herein relate to a network manager for managing network keys in a network having a plurality of nodes, the device comprising: a memory; and a processor configured to: determine N nodes to blacklist, wherein N is an integer; select a polynomial function from a plurality of polynomial functions of degree K and wherein the polynomial functions define plurality of secret network keys; generate K-N random abscissa values, wherein none of the random abscissa values are not found in a list of node abscissa values; calculate K-N polynomial function values for the K-N random abscissa values; calculate N polynomial function values for N node abscissa values associated with the N blacklisted nodes; transmit a message to nodes in the network including an indication of the selected polynomial function, the K-N random abscissa values, the N node abscissa values associated with the N blacklisted nodes, the K-N calculated polynomial function values, and the N calculated polynomial function values. 
         [0006]    Various embodiments described herein relate to a node in a network having a plurality of nodes, the device including: a memory; and a processor configured to: receive a message including an indication of a selected polynomial function, K abscissa values, and the K selected polynomial function values, wherein the selected polynomial function has an degree of K and wherein the selected polynomial function defines a current secret network key; determine the coefficients of the selected polynomial function based upon K abscissa values, the K selected polynomial function values, and a node abscissa value; and determine the current secret network key based upon the determined coefficients. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0007]    In order to better understand various embodiments, reference is made to the accompanying drawings, wherein: 
           [0008]      FIG. 1  illustrates a system network diagram; 
           [0009]      FIG. 2  illustrates a system diagram; 
           [0010]      FIG. 3  illustrates a provisioning; 
           [0011]      FIG. 4 a    illustrates a key update stage without blacklisting; 
           [0012]      FIG. 4 b    illustrates a key update stage with blacklisting; 
           [0013]      FIG. 5  illustrates a method for handling a key update by a manager; and 
           [0014]      FIG. 6  illustrates a method for handling a key update by a node. 
       
    
    
       [0015]    To facilitate understanding, identical reference numerals have been used to designate elements having substantially the same or similar structure or substantially the same or similar function. 
       DETAILED DESCRIPTION 
       [0016]    The description and drawings presented herein illustrate various principles. It will be appreciated that those skilled in the art will be able to devise various arrangements that, although not explicitly described or shown herein, embody these principles and are included within the scope of this disclosure. As used herein, the term, “or” refers to a non-exclusive or (i.e., and/or), unless otherwise indicated (e.g., “or else” or “or in the alternative”). Additionally, the various embodiments described herein are not necessarily mutually exclusive and may be combined to produce additional embodiments that incorporate the principles described herein. 
         [0017]    In the Internet of Things (IoT) era, sensor network nodes are sometimes resource-constrained and need reduced computational effort. Security mechanisms which ensure key updates should be light-weight, fast, and efficient. A scenario where the network key needs to be updated manually for each node might prove sometimes inefficient and even insecure. For example, even if an attacker is detected, severe damage could be inflicted until the entire network is up to date with the new network key. 
         [0018]    Embodiments enhance the development of light-weight mesh networks (including sensor networks). The necessity of fast key update and removal of compromised nodes without significant intervention from the network manager are desired since, from a security point of view, network members are identical. 
         [0019]    Embodiments include systems and methods which allow network managers to efficiently refresh the network key, including when one or more nodes may be compromised. Some embodiments include implementations on mesh networks. 
         [0020]    Embodiments may include a provisioning stage where a coordinator device, hereinafter called network manager, may supply each enrolled node with a pool of points P N  which are calculated using N polynomial splitter functions of degree k. 
         [0021]    Additional embodiments may include a key update stage where the network manager may broadcast a signed and authenticated packet into the network, containing information that allows only specific devices to derive a new network key based on a secret sharing algorithm, for example, Shamir&#39;s Secret Sharing algorithm, thus effectively blacklisting the compromised nodes without explicitly informing the network about their identity. 
         [0022]      FIG. 1  illustrates a system network diagram  100 . System network diagram  100  may include manager  102  and nodes  104 - 120 . The connections in system network diagram  100  may be any kind of telecommunications network topology such as a mesh network, ring, star, fully connected, line, or tree. Similarly, the technologies used for the network may be any kind of wired or wireless technologies such as, Local Area Network (LAN), Asynchronous Transfer Mode (ATM), Wireless LAN (WiFi), 
         [0023]    Internet Protocol (IP), and Long Term Evolution (LTE), for example. 
         [0024]    Manager  102  may be a server, computer, personal computer, data center, blade, tablet device, or personal phone, for example. Nodes  102 - 120  may similarly be any of a server, computer, personal computer, data center, blade, tablet device, or personal phone. In one example, manager  102  may be a server blade in a data center. In this non-limiting example, each of nodes  102 - 120  may be servers in data centers located in different cities. In another example, all of nodes  102 - 120  and manager  102  may be located in the same center, such as a university, while each node may reflect a different server for that university. 
         [0025]    Manager  102  may manage and distribute a key system such as a private key infrastructure. Manager  102  may store a table and/or data structure to identify current and past keys as well as nodes which are assigned to those keys. This may be applied for a public as well as a private key infrastructure. The data structures may include any of a tree, a binary tree, a hash, an array, a class or a database, for example. 
         [0026]      FIG. 2  illustrates a hardware diagram  200  for implementing a manager or a node. The hardware  200  may correspond to one or more nodes  104 - 120  or manager  102  of  FIG. 1 . As shown, the device  200  includes a processor  220 , memory  230 , user interface  240 , network interface  250 , and storage  260  interconnected via one or more system buses  210 . It will be understood that  FIG. 2  constitutes, in some respects, an abstraction and that the actual organization of the components of the device  200  may be more complex than illustrated. 
         [0027]    The processor  220  may be any hardware device capable of executing instructions stored in memory  230  or storage  260  or otherwise processing data. As such, the processor may include a microprocessor, field programmable gate array (FPGA), application-specific integrated circuit (ASIC), or other similar devices. 
         [0028]    The memory  230  may include various memories such as, for example L1, L2, or L3 cache or system memory. As such, the memory  230  may include static random access memory (SRAM), dynamic RAM (DRAM), flash memory, read only memory (ROM), or other similar memory devices. 
         [0029]    The user interface  240  may include one or more devices for enabling communication with a user such as an administrator. For example, the user interface  240  may include a display, a mouse, and a keyboard for receiving user commands. In some embodiments, the user interface  240  may include a command line interface or graphical user interface that may be presented to a remote terminal via the network interface  250 . 
         [0030]    The network interface  250  may include one or more devices for enabling communication with other hardware devices. For example, the network interface  250  may include a network interface card (NIC) configured to communicate according to the Ethernet protocol. Additionally, the network interface  250  may implement a TCP/IP stack for communication according to the TCP/IP protocols. Various alternative or additional hardware or configurations for the network interface  250  will be apparent. 
         [0031]    The storage  260  may include one or more machine-readable storage media such as read-only memory (ROM), random-access memory (RAM), magnetic disk storage media, optical storage media, flash-memory devices, or similar storage media. In various embodiments, the storage  260  may store instructions for execution by the processor  220  or data upon with the processor  220  may operate. For example, the storage  260  may store a base operating system  261  for controlling various basic operations of the hardware  200 . The storage  260  may store key management instructions  262  for managing the public or private key storage, distribution and updating. The storage  260  may store a key database  263  such as one of the data structures previously mentioned. 
         [0032]    It will be apparent that various information described as stored in the storage  260  may be additionally or alternatively stored in the memory  230 . In this respect, the memory  230  may also be considered to constitute a “storage device” and the storage  260  may be considered a “memory.” Various other arrangements will be apparent. Further, the memory  230  and storage  260  may both be considered to be “non-transitory machine-readable media.” As used herein, the term “non-transitory” will be understood to exclude transitory signals but to include all forms of storage, including both volatile and non-volatile memories. 
         [0033]    While the host device  200  is shown as including one of each described component, the various components may be duplicated in various embodiments. For example, the processor  220  may include multiple microprocessors that are configured to independently execute the methods described herein or are configured to perform steps or subroutines of the methods described herein such that the multiple processors cooperate to achieve the functionality described herein. Further, where the device  200  is implemented in a cloud computing system, the various hardware components may belong to separate physical systems. For example, the processor  220  may include a first processor in a first server and a second processor in a second server. 
         [0034]    Provisioning 
         [0035]    The number of key updates using embodiments of the method may be limited by the storage capabilities of devices participating in the mesh. The manager may use an algorithm based on Shamir&#39;s Secret Sharing method which may imply the use of (at least) a polynomial splitter function F t  of degree k. Other known secret sharing methods may be used as well with the embodiments described here. The network key that will be used at the i th  key update may be F i (0). The value of k may be selected depending on the protocol&#39;s payload limitations, security requirements and blacklisting efficiency, for example. Since multiple key updates may be required during a network&#39;s life cycle, the Manager may store a table of polynomial functions (PFT) of size N (containing, for example, F i  ranging from 1 to N). 
         [0036]    In a provisioning stage a node m may be added to the mesh network over a protocol-specific secure link. The Manager may send the current network key and iterate throughout the PFT using an abscissa value that was not previously used for any other node, to obtain a unique point on each function that resides in PFT. This operation results in a table of P N  points (PT). PT may be sent to the enrolled device, while the Manager may store an abscissa, node address pair in a separate table (AAT). 
         [0037]      FIG. 3  illustrates a provisioning  300 . Provisioning  300  may include manager  302 , example PFT  304 , example PT  306 , and example AAT  308 . In provisioning  300 , manager  302  may use a new value of 7 as an abscissa to transfer P k =[7, F k (7)]. Example PFT  304  illustrates a polynomial function table, which a manager may choose a polynomial function from. In example  304 , 3 polynomial functions are illustrated. In embodiments, a PFT such as example PFT  304  may be stored on manager  302 . Manager  302  may similarly store an address abscissa table such as example AAT  308 . In example AAT  308 , a simplified table illustrating node identifications (ID) each associated with an abscissa. 
         [0038]    Example PT  306 , illustrates a node network with 6 nodes. Example PT  306  uses 4 as an abscissa value to create a point table with several points using 4 as the abscissa. 
         [0039]    Key Updating 
         [0040]    In a mesh network key update stage, a Manager may have to renew the network key and, if needed, to blacklist a certain node. 
         [0041]    Key renewal without blacklisting may be carried out as follows:
       In a secret sharing algorithm if a polynomial function of degree k is used to protect a secret, then k+1 points must be known so that, using Lagrange&#39;s Interpolation, the splitter function can be reconstructed and therefore F i (0)=secret may be retrieved.   After secret has been retrieved, the new network key may be derived using a hash-based key derivation function: NK=KDF (secret).   To begin a key renewal procedure, a manager may broadcast a signed and authenticated message in the mesh which contains k unique points, calculated using a polynomial function from PFT, by using abscissa values which were not distributed to any node or are not present in the AAT.   Each node may now have k+1 points on F t  and may be capable of retrieving the new network key, i.e., calculating F t (0)=secret.       
 
         [0046]    Blacklisting a node a node may be carried out as follows:
       A similar procedure to that of key renewal described above may be used when a node must be blacklisted. Instead of calculating k unique points, i.e., points that are not equal to any of the abscissa values associated with a node, a manager may issue k−1 unique points. The k th  point may be calculated using the abscissa in the AAT which was provisioned to the node that should be blacklisted.   All the nodes in the mesh network may receive k+1 unique points, except that the blacklisted node will obtain k unique points and may not be capable of retrieving the new network key.       
 
         [0049]      FIG. 4 a    illustrates a key update stage without blacklisting  400 . Key update stage without blacklisting  400  may include manager  402  and nodes  404 - 414 . Manager  402  may send a data packet D including pool of points P 7  through P K+6  to node  404 . Node  404  may send the same data packet D to node  414 . Node  414  may extract the points from the pool of points and add its own point P 5 . Node  414  may generate the new key from the pool of points as applied to the relevant polynomial function for this iteration of key updates. Node  414  may then send the data packet D to node  412  for similar abscissa and point extraction, as well as key generation. This method may be used as an alternate channel to send the new network key in case the current key is considered weak and an attacker may know sufficient information to compromise network security. 
         [0050]      FIG. 4 b    illustrates a key update stage with blacklisting  450 . Key update stage with blacklisting  450  may include manager  452  and nodes  454 - 464 . In key update stage with blacklisting  450  node  462  may be blacklisted and unable to reproduce a new network key and because it is not able to evaluate the most current polynomial function. In key update stage with blacklisting  450  manager  452  may send a data packet to node  454  including a pool of points with abscissa P 4 , P 8 , . . . up to P K+6 . Similarly, node  454  may transmit to node  464  the data packet. Node  464  may be able to withdraw the pool of points P 5 , P 4 , P 8 , . . . P +6  and generate a key from the secret information related to the polynomial. Node  464  also sends the data packet D to node  462 . Because P 4  is included in the data packet, node has two copies of P 4 , and thus is not able to reconstruct the most current polynomial function (because it only has k unique points and k+1 points are needed), and hence, node  462  cannot determine the secret information needed to generate the new network key. This results in the node  462  being blacklisted. Node  462  also sends the packet D on to node  460 . 
         [0051]      FIG. 5  illustrates a method for handling a key update by a manager  500 . Manager  102  may begin in step  502  when it is determined that a key update is required and proceed to step  504 . 
         [0052]    In step  504  manager  102  may determine which polynomial function to use as indicated by x. In determining which polynomial function to use, manager  102  may access the PFT. The PFT may contain several different polynomial functions. An index may be maintained and communicated that indicates which of the polynomial functions to use. When a polynomial function has been chosen, manager  102  may proceed to step  506 . 
         [0053]    In step  506  manager  102  may determine whether to blacklist one or more nodes. When manager  102  determines to perform a key refresh without blacklisting any nodes, the manager may proceed to step  508 , and when the manager determines it should perform a node blacklisting it proceeds to step  510 . 
         [0054]    In step  508  the manager may generate k abscissa values which are not currently in its abscissa-node address table (AAT). Once the random abscissa values are generated, manager  102  may proceed to step  512 . 
         [0055]    In step  510  the manager may extract an abscissa A j+1  from the AAT based on the address of the node to be blacklisted. Additionally, the manager may generate k−1 random abscissa values which are not presently in the AAT and proceed to step  512 . 
         [0056]    In step  512  the manager may calculate the relevant polynomial splitter function value F x  for the new abscissa values A j+1 , . . . , A j+i . The manager may then proceed to step  514 . 
         [0057]    In step  514  manager  102  may create a data packet D which includes the new abscissa values A j+i , and new polynomial splitter function values for the newly abscissa values F x (A j+i . The manager may then proceed to step  516 . 
         [0058]    In step  516  manager  102  may sign and authenticate the message m, that includes D and the index x indicating the polynomial function used that corresponds to entry x in the PFT at each node. 
         [0059]    The manager may then proceed to step  518  where it may broadcast the packet into the mesh as depicted in  FIGS. 1, and 4   a - 4   b.    
         [0060]      FIG. 6  illustrates a method for handling a key update by a node  600 . Any of nodes  104 - 120  may perform method  600 . The node may begin in step  602  when a key update is required and proceed to step  604 . 
         [0061]    In step  604  the node may determine whether or not the message is authentic. When the message is determined not to be authentic the node may proceed to step  606  where it may drop the packet. When the message is determined to be authentic, it may proceed to step  608 . 
         [0062]    In step  608  the node may retrieve the index x from the message and proceed to step  610 . 
         [0063]    In step  610  the node may determine whether entry x was used. When entry x is determined to be used, then the node may proceed to step  612  where it may drop the packet. When entry x was not determined to be used, the node may proceed to step  614 . 
         [0064]    In step  614 , the node may retrieve the point P x  from the point table PT and proceed to step  616 . 
         [0065]    In step  616  the node may retrieve D from the packet generated in step  514 , and thereafter add the pool of points P x  previously retrieved. The node may then proceed to step  618 . 
         [0066]    In step  618  the node may determine whether it can deduce the polynomial function or not. When the node cannot deduce the polynomial function, this indicates that the node is blacklisted. In this case, the node may proceed to step  624  where it may drop the packet. When the node is able to decipher and calculate accurately the polynomial function, this indicates a key refresh and that the node is active. The active node proceeds to step  620 . 
         [0067]    In step  620  the node may reconstruct the new polynomial splitter function F′ and then evaluate F′(0) and therefore retrieve the new key. Once the function is calculated and the new key retrieved, the node may proceed to step  622  where it may mark the entry x used in its local storage. 
         [0068]    Collisions may be avoided by adding an index in the packet payload, resembling the index of the polynomial function from the PFT which is used at the current key update sequence. 
         [0069]    Since the key pool may be limited, scenarios where multiple nodes may be blacklisted simultaneously may desirable. The feature of blacklisting multiple nodes may be closely related to the degree of the polynomial functions, and therefore the number of points needed to reconstruct a key. For example if the function&#39;s degree is two, three points will be needed to reconstruct the key. Since each node already owns one point, at a certain key renewal stage, only two nodes may be blacklisted simultaneously. Accordingly, the degree of the polynomial functions will be selected to accommodate the number of nodes to be blacklisted. 
         [0070]    It should be apparent from the foregoing description that various exemplary embodiments of the invention may be implemented in hardware. Furthermore, various exemplary embodiments may be implemented as instructions stored on a machine-readable storage medium, which may be read and executed by at least one processor to perform the operations described in detail herein. A machine-readable storage medium may include any mechanism for storing information in a form readable by a machine, such as a personal or laptop computer, a server, or other computing device. Thus, a tangible and non-transitory machine-readable storage medium may include read-only memory (ROM), random-access memory (RAM), magnetic disk storage media, optical storage media, flash-memory devices, and similar storage media. Further, as used herein, the term “processor” will be understood to encompass a microprocessor, field programmable gate array (FPGA), application-specific integrated circuit (ASIC), or any other device capable of performing the functions described herein. 
         [0071]    It should be appreciated by those skilled in the art that any block diagrams herein represent conceptual views of illustrative circuitry embodying the principles of the invention. Similarly, it will be appreciated that any flow charts, flow diagrams, state transition diagrams, pseudo code, and the like represent various processes which may be substantially represented in machine readable media and so executed by a computer or processor, whether or not such computer or processor is explicitly shown. 
         [0072]    Although the various exemplary embodiments have been described in detail with particular reference to certain exemplary aspects thereof, it should be understood that the invention is capable of other embodiments and its details are capable of modifications in various obvious respects. As is readily apparent to those skilled in the art, variations and modifications can be effected while remaining within the spirit and scope of the invention. Accordingly, the foregoing disclosure, description, and figures are for illustrative purposes only and do not in any way limit the invention, which is defined only by the claims.