BLIND KEY GENERATOR AND EXCHANGE
20210051006 ยท 2021-02-18
Inventors
Cpc classification
H04L9/0866
ELECTRICITY
H04L9/0825
ELECTRICITY
H04L9/006
ELECTRICITY
G06F7/588
PHYSICS
International classification
H04L9/08
ELECTRICITY
H04L9/32
ELECTRICITY
Abstract
Operationally, the invention transmits a number to a verifiable recipient which indicates to the receiver what the key will be, without sending the key, or some related key. It is an INPUT into a function that takes the inputs to arrive at a completely different key. The idea is that the partial key does not have any resemblance to the final key and does not give the attacker a clue as to what the final key will be, thus, making it far more difficult to find what appears to be a completely unrelated password/key than one that is not obscured. This is also known as using a partial key to transmit a blind key to a verifiable recipient.
Claims
1. (canceled)
2. (canceled)
3. (canceled)
4. (canceled)
5. (canceled)
6. A method of developing keys in a paired node communications comprising: performing an initialization sequence; receiving an message; determining a partial key having a unique signature, wherein the unique signature is determined using a physically unclonable function; determining a class function, wherein the class function is chosen from a predetermined list of class functions; determining an initialization vector; calculating a final key, wherein the final key is calculated using the class function and at least the initialization vector and unique signature as inputs into the class function; encrypting the message using the final key and polymorphic key progression; storing the final key on a memory; and transmitting the encrypted message to a node.
7. The method of claim 6, wherein the initialization sequence further comprises: determining a subset of the unique signature; determining an order of the unique signature; encrypting the subset and the order using a handshake protocol; mixing the encrypted subset and encrypted order using at least one cryptographic pseudo-random number generator; and transmitting the mixed subset and order to the second node.
8. The method of claim 6, wherein the physically unclonable function is derived from a static random access memory, dynamic random access memory, flash memory, resistive random access memory, and/or magneto-resistive random access memory.
9. The method of claim 6, wherein the class function is selected from a group consisting of: an identity function, XOR function, combinations of binary primitive functions, trigonometric functions, locations of portion of an irrational number sequence, and/or other functions that result in non-repeating values of at least the size of a key space.
10. The method of claim 6, wherein the class function is chosen using a handshake protocol, frequent and irregular seeding, interleaved randomized seeding data in the message, and/or using a key progression value.
11. The method of claim 7, wherein the handshake protocol is a Diffie-Hellman handshake protocol.
12. A computer readable storage medium having program instructions embodied therewith, the program instructions executable by a hardware processor to cause the hardware processor to perform a method comprising: performing an initialization sequence; receiving an message; determining a partial key having a unique signature, wherein the unique signature is determined using a physically unclonable function; determining a class function, wherein the class function is chosen from a predetermined list of class functions; determining an initialization vector; calculating a final key, wherein the final key is calculated using the class function and at least the initialization vector and unique signature as inputs into the class function; encrypting the message using the final key and polymorphic key progression; storing the final key on a memory; and transmitting the encrypted message to a node.
13. The method of claim 12, wherein the initialization sequence further comprises: determining a subset of the unique signature; determining an order of the unique signature; encrypting the subset and the order using a handshake protocol; mixing the encrypted subset and encrypted order using at least one cryptographic pseudo-random number generator; and transmitting the mixed subset and order to the second node.
14. The method of claim 12, wherein the physically unclonable function is derived from a static random access memory, dynamic random access memory, flash memory, resistive random access memory, and/or magneto-resistive random access memory.
15. The method of claim 12, wherein the processor is a Field Programmable Gate Array processor.
16. The method of claim 12, wherein the class function is selected from a group consisting of: an identity function, XOR function, combinations of binary primitive functions, trigonometric functions, locations of portion of an irrational number sequence, and/or other functions that result in non-repeating values of at least the size of a key space.
17. The method of claim 1, wherein the class function is chosen using a handshake protocol, frequent and irregular seeding, interleaved randomized seeding data in the message, and/or using a key progression value.
18. The method of claim 13, wherein the handshake protocol is a Diffie-Hellman handshake protocol.
19. A system for communicating encoded messages, comprising: a first node having a first memory; a first processor electrically coupled to the first memory, wherein the first processor is configured to: perform an initialization sequence; receive an message; determine a partial key having a unique signature, wherein the unique signature is determined using a physically unclonable function; calculate a final key, wherein the final key is calculated using a class function and at least the partial key as inputs into the class function; encrypt the message using the final key and polymorphic key progression; store the final key on the first memory; and transmit the encrypted message to a second node having at least a second memory and a second processor.
20. The system of claim 19, wherein the initialization sequence further comprises: determine a subset of the unique signature; determine an order of the unique signature; encrypt the subset and the order using a handshake protocol; mix the encrypted subset and encrypted order using at least one cryptographic pseudo-random number generator; and transmit the mixed subset and order to the second node.
21. The system of claim 19, wherein the physically unclonable function is derived from a static random access memory, dynamic random access memory, flash memory, resistive random access memory, and/or magneto-resistive random access memory.
22. The system of claim 19, wherein both the first processor and the second processor are a Field Programmable Gate Array.
23. The system of claim 19, wherein the class function is selected from a group consisting of: an identity function, XOR function, combinations of binary primitive functions, trigonometric functions, locations of portion of an irrational number sequence, and/or other functions that result in non-repeating values of at least the size of a key space.
24. The system of claim 19, wherein the class function is chosen using a handshake protocol, frequent and irregular seeding, interleaved randomized seeding data in the message, and/or using a key progression value.
25. The system of claim 20, wherein the handshake protocol is a Diffie-Hellman handshake protocol.
Description
BRIEF DESCRIPTION OF THE DRAWINGS
[0062]
[0063]
[0064]
[0065]
[0066]
[0067]
[0068]
[0069]
[0070]
[0071]
DETAILED DESCRIPTION OF THE INVENTION
[0072] The proliferation of connected machines, consumer products, automobiles, drones, and smart grids under the broad concept of Internet of Things (IoT) has created new opportunities for criminals, terrorists, and hackers which has necessitated effective cyber security solutions for commerce and national security.
[0073] There are billions of heterogeneous devices on the Internet. Securing those billions of devices is a complex and never ending task. Security is often an afterthought and is usually based on microcontroller architectures that are not necessarily flexible enough to perform and meet the diverse needs of those billions of devices.
[0074] Protecting a network interacting with IoTs does not come without its' difficulties, including: [0075] 1. Key distribution among network nodes. [0076] 2. Protection of the key within the IoTs to avoid side channel attacks. [0077] 3. Access to enough computational resources because low cost IoTs may not have the capability to process functions such as exponential modulo that are needed for the protocols.
[0078] Various methods to overcome these problems have been tried with the most viable being a type of Public Key Infrastructure (PKI),
[0079] In this invention, the Blind Key Exchange (BKE), we combine a database-free host architecture with a modular microcontroller at the client level with security built in, linked by a secure authentication protocol that uses replaceable security modules to authenticate users and data transmissions.
[0080] The BKE is implemented as a hardware function as shown in
[0081] The BKE publicly sends an encrypted message using a key that is NOT sent, but rather agreed upon without sending the key, thus, negating any efforts by an attacker to listen to the transmission and determine the key. This is accomplished by using a partial key, a number sent to indicate to the receiver what the key will be without sending the key or some related key, as INPUT into a function that takes the inputs to arrive at a completely different key. The partial key does not have any resemblance to the final key and, therefore, does not give the attacker a clue as to what the final key will be.
[0082] The BKE is either attached to a computing device,
[0083] When preparing to send an encrypted message, the BKE must, first, develop a partial key (PK) that will be used to develop the final key (FK) used in the actual encryption process prior to transmitting the encrypted message and partial key to the recipient.
[0084] The partial key is derived from Physically Unclonable Functions (PUF) which consist of physical quantities that arise from variations of manufacturing computer memory and various electronic components which are part of the signature directly associated with the hardware of a computer and remains with the unit until it is either retired or the parts burn out. Memory based PUFs are utilized and are derived from Static Random Access Memory (SRAM), Dynamic Random Access Memory (DRAM), Flash Memory (FLASH), Resistive Random-Access Memory (ReRAM) and Magnetoresistive Random-Access Memory (MRAM) memory structures, as shown in
[0085] PUFs need 128 to 256 bits to ensure an acceptable level of security and the secure memory arrays (SM) integrated within secure micro-controllers have memory densities in the mega-byte range. Challenge Response Pairs (CRPs) are generated by characterizing a particular parameter PP of the cells with the built-in-self-test (BIST) module. The values of the parameter PP vary from cell to cell and follow a distribution with a median value T. In order to generate challenge and response pairs all cells with PP quantified as 0, and all others as 1. Assuming that these measurements are reproducible, the resulting streams of data generated by the method can be used as cryptographic primitives to authenticate the memory array.
[0086] Each of these PUFs can be characterized after manufacture and the results stored for later reporting and use. Thus, PUFs can be recorded either at the time they are produced, later when they are used, or even much later when they are put into operation. That data can be used in a database or registered with a particular user or Trusted Third Party (TTP).
[0087] Once the partial key is fully developed, the BKE can utilize several different class functions to develop the final key from the partial key: [0088] 1. The identity functionThe final key is just the bits read from the PUF in the order specified during the process of data handshake/exchange between the users. [0089] 2. The XOR functionThe final key is derived by doing an XOR with the Initialization Vector and the data from the PUF in the specified order. [0090] 3. Functions consisting of combinations of binary primitive functionsThe final key is derived by applying the agreed upon function consisting of binary primitive operators with the data from the PUF in the specified order. Binary primitives include the AND, OR, and NOT (inversion) binary functions and can be combined in any order as agreed upon prior to application to derive the key. [0091] 4. Trigonometric functionsAny trigonometric function, such as sin, cos, tan, sec, cot, and cosec, as well as their hyper-trigonometric counterparts. [0092] 5. Locations of portions of an irrational number sequenceIndexing into an irrational number, such as and choosing from some starting point in the sequence to take the next K| bits as the key. Numerous irrational numbers exist and do not repeat values, any one of which (or selection from among a pool of those numbers) may be selected for use. [0093] 6. Other related functions that result in non-repeating values of at least the size of the keyAny equation or number that is known not to repeat for |K| characters is suitable, even though not specified in the preceding descriptions, may also be used to derive the final key.
[0094] Any of these functions can be selected, when agreed upon during the initialization sequence seeded by the Initialization Vector and order numbers sent by secret key between users.
[0095] The full key is derived from an initial value, an initialization vector (IV) and some subset of a signature (S) as K=((IV,S).
[0096] The signature is some value, or set of values that uniquely identifies a hardware node associated with a particular user. In order to be a valid signature, the signature must be: [0097] 1. Uniquethat is each node should have its own value that is different from other nodes. The chance of having a duplicated signature should be as close to random as is possible. [0098] 2. All components of the signature must be readable by the unit in which they exist, but not readily available to someone outside the system. [0099] 3. Records of the signature should exist ONLY in trusted, protected environments (such as a Trusted Third Party, trusted associated, or Certificate Authority), and ONLY where absolutely necessary. [0100] 4. The signature must be composed of values that are difficult, if not impossible, to change for a user. Such a value can be placed in permanently attached hardware or can be the serial number placed in the chips. All processors and communications chips have these numbers burned into them so that they can be tracked and cannot be altered. Further, the hardware and memory configuration can also be added into the full signature. [0101] 5. The size of the signature should be as large as is possible. The more bits in the total signature the harder it is to know which portions of the signature are used in any final key. [0102] 6. The signature should include as many possible byte values as possible.
[0103] Signatures are a concatenation of the various PUFs, serial numbers, and other identifying values that look like:
TABLE-US-00002 S.sub.0 S.sub.1 S.sub.2 S.sub.3 . . . S.sub.n
where each S.sub.i is one of the individual signature components making up the entire signature for the unit. For example S.sub.0 could be the processor serial number, S.sub.1 could be the memory configuration, and so on. But, the signature can have many forms. Specifically, the signature can be concatenated in a number of ways. Without having to permute each of the bits, it is easy to permute each of the components of the total signature. This gives a total of n! combinations of the constituent values. The value of n! rises very rapidlyif there are only five components of the total signature there are 125 possible combinations and with ten, there are 3,628,800 possible combinations. Once this order is created, then any number of combinations of the bits in the signature can be selected. This may be done as a set of bytes or a set of bits. The number of possible combinations of the bits/bytes of the signature is
[0104] If the choice is bytes, then n is the number of bytes or bits, as appropriate, in the composite signature and is the size of the partial key input in bytes or bits, as appropriate. Then, the combination of those bits can be chosen in any order, resulting in
choices. This gives a large number of inputs into the function that develops the final key.
[0105] Now assume that there are m functions that can be used in developing the final key. These functions are placed in a pool and are randomly chosen, but that choice is agreed upon by the users. Choice of the function can be made in the same way that the signature component order, subset of the signature, and order of the bits/bytes are selected: handshake for each exchange, frequent and irregular seeding, interleaved randomized seeding data in the message, or using a key progression value entered at the time of installation. In any case the best situation is to use a CPRNG that approximates a uniformly distributed IRV. Then we can assume that the probability of selecting any function (.sub.1) in the pool is
And the key space for a particular set of messages is the product of the probability off, n!, and |B|!, resulting in a key space of |K|=n!|B|!|P|.
[0106] However, so long as the eventually there will be a repeat of the use of keys in the key space. Assuming that the choice is random, the maximum average amount of keys selected by the users before a repeat (or collision) is governed by the Birthday paradox [McKinney 1966]. Having a larger key space will reduce the time between collisions.
[0107] Using this approach the idea is to try and achieve as uniform a selection of keys, so that the chance of picking a particular key is given by
and the probability of a collision in a particular run of key selections is
[0108] Where n is the number of items in the run (such as a run of 23) and |K| is the size of key space. Increasing n only helps to decrease the average time between collisions. Again, the number of possible keys is controlled via the functions and signature space used.
[0109] If the key space is set, then calculating the inputs for the functions rely on picking a portion of the signature and then ordering the subset of the signature. The subset of the signature and the order that it is used can be easily passed using a shared secret algorithm, such as a Diffie-Hellman handshake, or similar algorithm. This data is then passed into a series of cryptographic pseudo-random number generators (CPRNGs), or other sources, to further mix the portion of the signature used as inputs as shown in
where is the periodicity of each constituent RNG block. And v.sub.i=.sub.i the average periodicity of the RN choices used as inputs in the RNG block.
[0110] Next, the initialization vector (IV) needs to be determined. For a function that is one-to-one the IV can be determined using the relationship
[0111] The exact details will depend on the exact final key function used.
[0112] Once the final key is developed, the BKE encrypts the final message using the CipherLoc polymorphic key progression algorithmic cipher engine and the final key.
[0113] Next, the partial key is transmitted to the intended recipient followed by the transmission of the encrypted form of the final message.
[0114] When the BKE receives an encrypted message and partial key from a valid transmission source, the BKE, essentially, reverses the process used for final key development and encryption.
[0115] First, the partial key is used with the appropriate function, chosen from the list below, to develop the final key from the partial key: [0116] 1. The identity functionThe final key is just the bits read from the PUF in the order specified during the process of data handshake/exchange between the users. [0117] 2. The XOR functionThe final key is derived by doing an XOR with the IV and the data from the PUF in the specified order. [0118] 3. Functions consisting of combinations of binary primitive functionsThe final key is derived by applying the agreed upon function consisting of binary primitive operators with the data from the PUF in the specified order. Binary primitives include the AND, OR, and NOT (inversion) binary functions and can be combined in any order as agreed upon prior to application to derive the key. [0119] 4. Trigonometric functionsAny trigonometric function, such as sin, cos, tan, sec, cot, and cosec, as well as their hyper-trigonometric counterparts. [0120] 5. Locations of portions of an irrational number sequenceIndexing into an irrational number, such as and choosing from some starting point in the sequence to take the next |K| bits as the key. Numerous irrational numbers exist and do not repeat values, any one of which (or selection from among a pool of those numbers) may be selected for use. [0121] 6. Other related functions that result in non-repeating values of at least the size of the keyAny equation or number that is known not to repeat for |K| characters is suitable, even though not specified in the preceding descriptions, may also be used to derive the final key.
[0122] Any of these functions can be selected, when agreed upon during the initialization sequence seeded by the Initialization Vector and order numbers sent by secret key between users.
[0123] Note: If a combination of functions was used to develop the final key, the same combination and sequence of use of those functions is selected.
[0124] The full key is derived from an initial value, an initialization vector (IV) and some subset of a signature (S) as K=.sub.t(IV, S).
[0125] The signature is some value, or set of values that uniquely identifies a hardware node associated with a particular user. In order to be a valid signature, the signature must be: [0126] 1. Uniquethat is each node should have its own value that is different from other nodes. The chance of having a duplicated signature should be as close to random as is possible. [0127] 2. All components of the signature must be readable by the unit in which they exist, but not readily available to someone outside the system. [0128] 3. Records of the signature should exist ONLY in trusted, protected environments (such as a Trusted Third Party, trusted associated, or Certificate Authority), and ONLY where absolutely necessary. [0129] 4. The signature must be composed of values that are difficult, if not impossible, to change for a user. Such a value can be placed in permanently attached hardware or can be the serial number placed in the chips. All processors and communications chips have these numbers burned into them so that they can be tracked and cannot be altered. Further, the hardware and memory configuration can also be added into the full signature. [0130] 5. The size of the signature should be as large as is possible. The more bits in the total signature the harder it is to know which portions of the signature are used in any final key. [0131] 6. The signature should include as many possible byte values as possible.
[0132] Signatures are a concatenation of the various PUFs, serial numbers, and other identifying values that look like:
TABLE-US-00003 S.sub.0 S.sub.1 S.sub.2 S.sub.3 . . . S.sub.n
where each S.sub.i is one of the individual signature components making up the entire signature for the unit. For example S.sub.0 could be the processor serial number, S.sub.1 could be the memory configuration, and so on. But, the signature can have many forms. Specifically, the signature can be concatenated in a number of ways. Without having to permute each of the bits, it is easy to permute each of the components of the total signature. This gives a total of n! combinations of the constituent values. The value of n! rises very rapidlyif there are only five components of the total signature there are 125 possible combinations and with ten, there are 3,628,800 possible combinations. Once this order is created, then any number of combinations of the bits in the signature can be selected. This may be done as a set of bytes or a set of bits. The number of possible combinations of the bits/bytes of the signature is
[0133] If the choice is bytes, then n is the number of bytes or bits, as appropriate, in the composite signature and is the size of the partial key input in bytes or bits, as appropriate. Then, the combination of those bits can be chosen in any order, resulting in
choices. This gives a large number of inputs into the function that develops the final key.
[0134] Now assume that there are m functions that can be used in developing the final key. These functions are placed in a pool and are randomly chosen, but that choice is agreed upon by the users. Choice of the function can be made in the same way that the signature component order, subset of the signature, and order of the bits/bytes are selected: handshake for each exchange, frequent and irregular seeding, interleaved randomized seeding data in the message, or using a key progression value entered at the time of installation. In any case the best situation is to use a CPRNG that approximates a uniformly distributed IRV. Then we can assume that the probability of selecting any function (t) in the pool is
And the key space for a particular set of messages is the product of the probability of .sub.i, n!, and |B|!, resulting in a key space of |K|=n!|B|!|P|.
[0135] However, so long as the eventually there will be a repeat of the use of keys in the key space. Assuming that the choice is random, the maximum average amount of keys selected by the users before a repeat (or collision) is governed by the Birthday paradox [McKinney 1966]. Having a larger key space will reduce the time between collisions.
[0136] Using this approach the idea is to try and achieve as uniform a selection of keys, so that the chance of picking a particular key is given by
and the probability of a collision in a particular run of key selections is
Where n is the number of items in the run (such as a run of 23) and |K| is the size of key space. Increasing n only helps to decrease the average time between collisions. Again, the number of possible keys is controlled via the functions and signature space used.
[0137] If the key space is set, then calculating the inputs for the functions rely on picking a portion of the signature and then ordering the subset of the signature. The subset of the signature and the order that it is used can be easily passed using a shared secret algorithm, such as a Diffie-Hellman handshake, or similar algorithm. This data is then passed into a series of cryptographic pseudo-random number generators (CPRNGs), or other sources, to further mix the portion of the signature used as inputs as shown in
[0138] CPRNGs are chosen since they are the most uniformly random of the RNGs available. The periodicity of the key sequencing will be v.sub.sequence.sub.i=1.sup.n v.sub.i where v.sub.sequence is the periodicity of each constituent RNG block. And v.sub.i=.sub.i the average periodicity of the RN choices used as inputs in the RNG block.
[0139] Next, the initialization vector (IV) needs to be determined. For a function that is one-to-one the IV can be determined using the relationship IV=.sup.il(S, K) The exact details will depend on the exact final key function used.
[0140] Once the final key is developed, the BKE decrypts the final message using the CipherLoc polymorphic key progression algorithmic cipher engine and the final key.
[0141] Finally, the BKE passes the decrypted message to the device to which it is attached, or in which it is embodied, in the original form in which it was intended from the originating device.
CONCLUSION
[0142] The advantages of this approach are that it is possible to develop a key without sending it across a communication channel First of all, it is never sent. Second, this method uses several steps to develop the key that keeps the data well obscured. It can be automated and easily used, as well as easily implemented. Third, there is no need to store the key, so, attacks on the key management system are no longer valid. Fourth, because the PUF key pad is known to both users and is not communicated as part of the exchange, a man in the middle can receive the IV and order and still be unable to reconstruct the key. Only a brute force attack is possible. Fifth, it is extensible to any size key. The process allows for end-to-end protection and uses the CipherLoc polymorphic key progression algorithmic cipher engine to maximize protection and obscuring.
[0143] Note: There are still vulnerabilities to physical attacks. This is not within the goals and scope of the BKE and requires other hybrid measures to accomplish. As with all of the measures taken, the registration process can be vulnerable to a man-in-the-middle attack, but only the first time at registration. Any solution that shares data and needs to communicate will also be susceptible to a DoS or DDoS attack. Again, this type of attack is outside of the scope of the BKE and goals of the design effort.