SYSTEM AND DEVICE FOR VERIFYING THE INTEGRITY OF A SYSTEM FROM ITS COMPONENTS FIELD OF THE INVENTION [0001] The present invention relates to integrity verification of systems comprising electronic components. REFERENCE TO RELATED APPLICATIONS [0002] This international application claims the benefit of the priority of non-provisional U.S. Patent Applications S.N. 14/704,947 ("the '947 application") filed May 5, 2015 and S.N. 14/746,090 filed June 22, 2015 (which was a continuation-in-part of the '947 application), and of U.S. Provisional Patent Applications S.N. 62/150,254 filed April 20, 2015, S.N. 62/128,920 filed March 5, 2015 ("the '920 application"), and S.N. 62/150,586 filed April 21, 2015 ("the '586 application"). The contents of the '920 and '586 applications and of U.S. Provisional Patent Application S.N. 61/988,848 filed May 5, 2014 (published in the record of prosecution of U.S. Patent Application Publication No. 20150317480) are also incorporated herein by reference. BACKGROUND OF THE INVENTION [0003] In many applications, it can be useful to employ means for verifying the integrity of a system by interrogating the components it is composed of. For example, a weapon system may require components to be internally validated during a boot process, or a vehicle may validate critical electronic control units on startup. Prior art typically accomplishes the verification of a component through a demonstration that it possesses a secret value, for example, through a zero knowledge proof of knowledge. This method of verification, however, may be associated with one or more constraints relating to hardware integrity or the security of private information. As to hardware integrity, existing component authentication protocols only verify that an entity possesses a private value, and typically just infer hardware integrity if the device has a physical construction designed to deter tampering (e.g., a hardware security module). Even with a tamper resistant physical construction, the integrity of the physical construction is not inextricably linked to the integrity of the device itself. As to the security of private information, existing component authentication protocols require that the component store and protect private information (typically a private key for cryptographic authentication protocols). If the private information is compromised, it may be possible for an adversary to masquerade as a valid component in the larger system. [0004] Asim et al. ("Physical Unclonable Functions and Their Applications to Ve- hicle System Security," Vehicular Technology Conference, VTC Spring 2009, IEEE 69th) discusses using PUFs in vehicle components as a method for regenerating pri- vate keys, which is a well-known application. However, they fail to give an enabling construction allowing a system-wide identity to be constructed from each of the in- dividual components. [0005] Rigaud (editor) in "D3.1 Report on Protocol choice and implementation," Holistic Approaches for Integrity of ICT-Systems (2014) describes applying PUFs to chips as a method for authenticating a chip (the device-under-test) to the testing equipment, which could detect fake chips. However, there is no construction that would enable a system-wide identity to be constructed from each of the individual chips. [0006] Ibrahim et al. ("Cyber-physical security using system-level pufs," Wireless Communications and Mobile Computing Conference (IWCMC), 20117th Int’l, IEEE) discusses the general concept of combining PUFs from distinct system components to form a combined identity, but they fail to give an enabling construction. In their concluding remarks, the authors specifically state that they lack a realized solution. [0007] Peeters ("Security Architecture for Things That Think," Diss. Ph. D. thesis, KU Leuven, June 2012) describes using a PUF in resource-constrained devices for regenerating a share from an external threshold system composed of a user’s devices. The PUF is applied solely as a storage mechanism, eliminating the need to store the share in plaintext on the device. However, no internal threshold application is given, nor is the challenge-helper pair ever refreshed. [0008] Krzywiecki et al. ("Coalition resistant anonymous broadcast encryption scheme based on PUF," Trust and Trustworthy Computing. Springer Berlin Heidel- berg, 2011, 48-62) describe a broadcast encryption scheme where subscribers must invoke a PUF-enabled card to regenerate shares of a threshold system. The con- struction requires an incorruptible distributor to store and protect raw PUF output. The system is designed to allow an end device to recover a symmetric key only if it has not been revoked by the broadcaster. The PUF-enabled receiving device must construct the full symmetric key from its shares in order to decrypt the incoming transmission. No internal threshold application is given, nor is the challenge-helper pair ever refreshed. [0009] Khoshroo et al. ("Design and Evaluation of FPGA-based Hybrid Physically Unclonable Functions," Diss. Western University London, 2013) describe a modified secret sharing scheme, where each player’s share is a challenge-helper pair generated from the dealer’s PUF. The actual shares for the threshold system are recovered only given both the challenge-helper pair and access to the PUF, which regenerates the share from the challenge-helper pair. As each share is worthless without access to the PUF, an adversary can compromise all of the end devices, and yet is unable to recover the secret without access to the PUF. No cryptographic operations are possible over these pseudo-shares. The shared secret may only be recovered if all of the shares are regenerated, and the dealer is assumed to be incorruptible. The dealer’s PUF is used only as a method for obfuscating the shares that are distributed to players.

SUMMARY OF THE INVENTION [0010] Various embodiments of the invention provide for the verification of a set of components of an electronic system, such that the integrity of the system as a whole is deduced therefrom. One embodiment of the invention employs physical unclonable functions (PUFs) for detecting hardware tampering in integrated circuits, and zero knowledge proof protocols for authentication. In one embodiment this is done by individual verification of components; in another embodiment, relevant components may be verified together, with each generating a local proof of validity and collaborating to combine their local proofs into a single proof that validates the integrity of the system as a whole. [0011] In another embodiment, which may be provided individually or in com- bination with one or more of the foregoing embodiments, systemic trust may be established even if the system’s components themselves are untrusted, by employing a hardware root-of-trust that iteratively extends the trust boundary as each compo- nent is verified.

BRIEF DESCRIPTION OF THE DRAWINGS [0012] Fig. 1 is a system diagram illustrating (1, 1) integrity verification of com- ponents; [0013] Fig. 2 is a system diagram illustrating (n, 1) integrity verification of com- ponents; and [0014] Fig. 3 illustrates a system establishing trust through layered security de- rived from a high assurance processor.

DETAILED DESCRIPTION OF EMBODIMENTS [0015] In one embodiment, each of a system’s n relevant components may be inter- rogated (e.g., sequentially) through an interactive or non-interactive zero-knowledge proof of knowledge. Authentication algorithms such as those disclosed in the’848 and’586 applications (elliptic curve-based) or in U.S. Patent No. 8,918,647 (discrete log-based; "the’647 patent," which is incorporated here by reference), for example, may be used to establish the hardware integrity of components having trusted means of gathering private information, such as physical unclonable functions. A PUF links the evaluation of a function with the hardware on which it is executed, such that any adversarial tampering of the hardware affects the evaluation of the function. By fur- ther linking the PUF output with the construction of the zero knowledge proof, the hardware integrity of the device can be deduced by an external verifier from its ability to successfully complete the zero knowledge proof protocol. The PUF may also be configured to dynamically generate private information from only public information, so that components need not store and protect private information. In another em- bodiment, integrity of the system may be established through a single collaborative response from all (or a subset of) the components by constructing a threshold proof that requires all or some subset of the n components to be functioning correctly. In that case, rather than construct a separate proof for each of the n components, they collaboratively construct a single proof that establishes the validity of all or a subset of the n components simultaneously. [0016] One embodiment of a component may comprise a Xilinx Artix 7field pro- grammable gate array (FPGA) platform, equipped, e.g., with 215,000 logic cells, 13 Megabytes of block random access memory, and 700 digital signal processing (DSP) slices. In an embodiment employing elliptic curve cryptography, for example, the hardware mathematics engine may be instantiated in the on-board DSP slices, with the PUF construction positioned within the logic cells, and a logical processing core including an input and output to the PUF and constructed to control those and the component’s external input and output and to perform algorithms (sending elliptic curve and other mathematical calculations to the math engine) such as those de- scribed above. A verifier may comprise Xilinx Artix 7 FPGA as described above, or server computer having an 8-core 3.1GHz processor and 16GB of RAM, or another suitable means, connected, e.g., by wire or wirelessly to the system’s components.

Component Authentication [0017] In the individual interrogation method of verification, or "(1, 1) verification," each component interacts directly with the verifier V . In interactive (1, 1) verification, the verifier V issues a nonce as part of a two message protocol with each component. In non-interactive (1, 1) verification, each component sends only a single message to the verifier V , and includes a value equivalent to a nonce (e.g., a timestamp) that cannot be manipulated by the component. In the collaborative method of verifica- tion, or "(n, 1) verification," a subset of the n components collaboratively generate a single joint proof, which convinces the verifier V of the integrity of the subset of n components. In interactive (n, 1) verification, the verifier V issues a nonce as part of a two message protocol, where a subset of components act jointly and send only a single response. In non-interactive (n, 1) verification, a subset of components send only a single message to the verifier V , which includes a value equivalent to a nonce (e.g., a timestamp) that cannot be manipulated by any subset of the components. [0018] For the purposes of providing a detailed description of an embodiment, the example of an elliptic curve-based construction is utilized, with E denoting an elliptic curve defined over afinitefield Fp where G is a base point of order q. One of ordinary skill will recognize that the invention (be it (1, 1), (n, 1), and/or layered security) can be readily implemented using various other constructions (with just one example alternative being the’647 patent’s discrete logarithm construction). Thus the invention is not limited to any particular construction, except where specifically stated in the claims. A zero knowledge authentication protocol typically requires a unique and random nonce to be issued by the verifier V during each protocol invocation. The nonce prevents the proof from the verifier from being reused in the future (i.e., a replay attack), and the proving component must not be able to influence its value. For example, the’848 application discloses a derived token-based zero knowledge proof protocol, the teachings regarding which are incorporated here by reference, summarized as follows: Interactive Authentication Algorithm for an Individual Device

for Server s do

Device d← {c, E, G, p, q, P, N} where N is a nonce and P is the helper string for PUF Device d do

for Server s do

This algorithm proceeds as follows:

• Prior to authentication, the server has issued a random challenge variable c to the device, which is used to form a PUF challenge input x. The enrollment server and device agree on an elliptic curve E defined over afinitefield Fp where G is a base point of order q. The device di returns a public commitment G to the server, which links its PUF to the challenge variable c (on which the challenge input x depends), and a public helper value P that will correct the noisy PUF output. • When the server wishes to authenticate the device, it issues an authentication request and the tuple {c, E, G, p, q, P, N} is sent to the device. • The device constructs the PUF challenge input x← H(c, E, G, p, q), which links the challenge variable c with the public parameters of the elliptic curve, and passes it to the PUF yielding output O ^′ , which is⊕’d with helper value P and the result decoded using an error decoding scheme D. • As the PUF output is noisy, when queried on challenge x again in the future, the new output O ^′ may not exactly match the previous output value O. However, it is assumed that O and O ^′ will be t-close with respect to some distance metric (e.g. Hamming distance). Thus, an error correcting code may be applied to the PUF output such that at most t errors will still recover O. During enrollment, error correction was applied over the random group element and then this value was blinded with the output of the PUF O, so that thefinal helper value reveals no information about During recovery

for authentication, computing the exclusive-or of ECC(rand)⊕ O⊕ O′ will return whenever O and O′ are t-close. This process is referred to as fuzzy extraction, and is detailed further in the’848 application (see "Gen Algorithm,", "Rep Algorithm," and Definition 3). • The device chooses a random group element r∈ Fq and computes point B = r · G. • The server’s nonce N is linked to the proof by constructing a hash c′ that also combines the base point G, the device’s nonce B, and its public key A. • The device constructs the zero knowledge proof token

mod p), and returns this tuple to the server. • The server verifies that:

(1, 1) Verification

[0020] In (1, 1) verification, the verifier individually interrogates each component in order to establish the integrity of the larger system; all (or all specified) compo- nents successfully complete a zero knowledge proof with the verifier in order for the verification of the integrity of the system as a whole to succeed. Referring to Fig. 1, the verifier is illustrated sequentially validating each of the system’s components. At first verification 1 and second verification 2, the verifier validates each critical system component. At third verification 3 and fourth verification 4, the verifier validates each non-critical system component. An interactive version of this process is set forth in Algorithm 1. [0021] The requirement for communication from the verifier V in the interactive zero knowledge proof is to obtain a nonce value specific to the current proof. This prevents an eavesdropping adversary from using previous proofs from a valid compo- nent to successfully complete an authentication protocol and masquerade as a valid component. A non-interactive zero knowledge proof removes this communication requirement. A non-interactive version of Algorithm 1 can be made by configuring the component to generate a nonce in a manner that prevents the proving compo- nent from manipulating the proof. To accomplish this, the component device di constructs the nonce N where τ is a timestamp and ||

denotes concatenation. The timestamp ensures that previous proofs constructed by the proving component cannot be replayed by an adversary in the future, while the hash function ensures that the proving component cannot manipulate the challenge in an adversarial manner. The verifier preferably checks that the timestamp is rea- sonably current (e.g., second granularity) and monotonically increasing to prevent replay attacks. Alternately, globally-synchronized clocks may be used rather than a timestamp, such as if network latency is not significant. A non-interactive version of (1, 1) verification is set forth in Algorithm 2, with each component locally choosing a current timestamp τ to construct its nonce.

(n, 1) Verification [0022] Referring to the threshold methods disclosed in the’920 application, which are incorporated by reference, for example, to satisfy the requirement that all k critical components are functioning properly, a (k, k) sharing can be constructed such that all k components must collaborate to complete a joint proof. For a system that comprises critical components as well as non-critical or redundant components, it may be desired to verify that all critical and some non-critical or redundant components are operational. One method for verifying such a system is to generate a separate sharing for each set, whereby the verifier checks two proofs. [0023] Alternately, both critical and non-critical components may be verified to- gether using a single (t, n) threshold proof in which n shares are allocated so as to ensure integrity of all critical components and a specified subset of non-critical components. For example, assume there are two critical components (both of which must be operational) and two non-critical components (at least one of which must be operational). n = 6 shares can be distributed with each critical component re- ceiving two shares and each non-critical component receiving one, and the minimum number of shares for verification t being 5 (i.e., a (5, 6) sharing). If one of the critical components fails or both of the non-critical components fail, verification fails since the remaining operational components can only contribute a total of four shares; if both critical components and at least one non-critical component are operational, the five shares necessary for successful verification can be contributed. In general, this approach is referred to as constructing a threshold access structure, which enforces a set of rules (e.g., all critical components and half of the non-critical components must be functional for the system to authenticate) through the distribution of shares. As shown in Fig. 2,first threshold proof 5 and second threshold proof 6, the criti- cal components contribute their local proofs. At third threshold proof 7 and fourth threshold proof 8, the remaining components contribute their local proofs to form a single, joint proof. At combined verification 9 the Verifier validates the joint proof (such as by Algorithm 6) to establish the validity of the system as a whole. Similarly, a (t, n) sharing can be constructed for redundant systems, such that t of the n redun- dant systems must be functioning to complete the proof. Thus, rather than complete O(n) proofs for n systems, the systems can jointly construct a single threshold proof to represent the system they compose. [0024] Algorithm 3 illustrates an example of a subset of component devices D¯⊆ D, |D¯| = m≤ n constructing a joint threshold proof for the verifier V . Although in this example the verifier combines partial proofs (thus, implying O(n) work for V as the number of partial proofs is n), a secretary could instead combine the partial shares and forward the result to the verifier. As another alternative, the components could form a ring, and pass their partial shares to the next component, which combines their own partial proof before forwarding on to the next component. The Enrollment Algorithm, Distributed Key Generation Algorithm, and PUF-Retrieve are set forth in the’920 application.

[0025] Similarly, Algorithm 3 can be performed non-interactively. This is accom- plished by replacing the verifier’s nonce N with a timestamp τ generated by the components, as illustrated in Algorithm 4. The timestamp serves as a replacement for the server’s randomness N , and prevents replay attacks by adding a temporal requirement to the proof. That is, the timestamp is monotonically increasing, and the verifier simply checks that the timestamp used in the proof is reasonably (e.g., second granularity) current.

[0026] Algorithm 5 illustrates a further refinement of Algorithm 3 that incorporates updating the challenge-helper pair and share after each operation. The PUF-Share- Update and PUF-Store algorithms are set forth in the’920 application.

Layered Security [0027] When the components themselves are unable to generate a proof of cor- rectness, the integrity of the system as a whole must be derived from a root-of-trust. An additional embodiment of the invention is a system achieving a layered security approach across all computing levels by deriving a hardware root-of-trust from a high assurance processor. The high assurance processor is used to validate all layers in a computing architecture, providing secure boot control, change detection, alarm in- dicators and audit functions. Fig. 3 illustrates the high assurance processor in an exemplary computing architecture. [0028] Secure computing architectures create a layered security approach, where the trusted boundary is iteratively extended from a core root-of-trust. For example, a trusted boot procedure assumes a minimal trust boundary (e.g., a root-of-trust, such as a trusted platform module (TPM)) and iteratively extends the trust boundary by validating each component of the system as it boots. This mitigates risk from com- ponents more susceptible to adversarial modification, such as the operating system or applications. The root-of-trust is used to detect modification to system compo- nents, and will only complete the boot sequence if all components are validated as correct. However, existing trusted boot systems typically rely on roots-of-trust that are assigned (rather than intrinsic) to the device. For example, TPMs hold a pri- vate key in protected memory that represents the identity of the system. Thus, an adversary that extracts the assigned identity is able to masquerade as the system. Further, existing systems do not provide intrinsic tamper detection, and rely on tam- per detecting hardware enclosures for security. Existing roots-of-trust are illustrated in Fig. 3 at the root of trust layer 14, which is situated above the hardware layer. [0029] One embodiment of the invention employs a high assurance processor based on a PUF that captures intrinsic and unique properties of the hardware and prefer- ably provides intrinsic hardware tamper detection. As the PUF mapping is a function of the physical properties of the hardware, it can be used to generate a hardware- intrinsic identity that represents the physical state of the system. Referring to Fig. 3, high assurance processor 10, which is at the hardware layer, is established as the root- of-trust for the system and forms a layered security architecture interaction with ap- plication layer 11, operating system layer 12, network layer 13, root of trust layer 14, and hardware layer 15. The high assurance processor 10 addresses NIST SP 800-53 Rev. 4 ("Security and Privacy Controls for Federal Information Systems and Organi- zations") Security Capability, where trust is derived from interactions among system components. The high assurance processor 10 may be used in mutual reinforcement controls within the system, where the high assurance processor 10 may validate an existing root-of-trust and vice versa. [0030] The high assurance processor 10 is preferably designed to interact with the system through common commercial standard interfaces (e.g., USB, Ethernet) to enable interaction with commercial-off-the-shelf devices without hardware modi- fication, and integration and continued support may be achieved throughfirmware and/or software upgrades. At root of trust layer 14 the high assurance processor 10 may be used to extend and/or interact with existing roots-of-trust (e.g., TPM, ARM TrustZone). This enables a system with an existing trusted boot process to remain essentially unchanged, as the high assurance processor 10 canfirst validate the existing root-of-trust (which can subsequently complete the existing trusted boot process). At application layer 11 the high assurance processor 10 may be used to validate applications prior to execution, for example by storing a cryptographic hash of the application code or binary executable when it isfirst installed from a trusted source. The high assurance processor 10 signs the cryptographic hash, which may be stored on the system. Before an application may be executed by the system, the high assurance processor 10first computes a cryptographic hash of the current application code or binary executable, validates its signature on the stored cryptographic hash, and validates that the two hash outputs match. If any of these checks fail, the high assurance processor 10 preferably halts execution of the application and issues an alarm.