# A Security Scheme for Dependable Key Insertion in Mobile Embedded Devices

Authors: Alexander Klimm; Benjamin Glas; Matthias Wachs; Sebastian Vogel; Klaus D. Müller-Glaser; Jürgen Becker
Journal: International Journal of Reconfigurable Computing
 (2011)

---

## Abstract

Public Key Cryptography enables entity authentication protocols based on a platform's knowledge of other platforms' public key. This is particularly advantageous for
embedded systems, such as FPGA platforms, with limited or none read-protected memory resources. For access control systems, an access token is authenticated by the mobile system. Only the public key of authorized tokens needs to be stored inside the mobile platform. At some point during the platform's lifetime, these
might need to be updated in the field due to loss or damage of tokens. This paper proposes a holistic approach for an automotive access control system based on Public Key Cryptography. Next to a FPGA-based hardware architecture, we focus on a secure scheme for key flashing of public keys to highly mobile systems.
The main goal of the proposed scheme is the minimization of online dependencies to Trusted Third Parties, Certification Authorities, or the like, to enable key flashing in remote locations with only minor technical infrastructure. Introducing trusted mediator devices, new tokens can be authorized and later their public key can be flashed into a mobile system on demand.


---

## Body

## 1. Introduction

Embedded systems in various safety critical application domains such as automotive, avionic, and medical care perform more and more complex tasks using distributed systems like networks of electronic control units (ECUs). Introducing Public Key Cryptography (PKC) to embedded systems provides essential benefits for the fabrication of electronic units needing to meet security requirements as well as for the logistics involved. Due to the nature of PKC, the number of keys that need to be stored in the individual platform is minimized. Only the private key of the platform itself needs to be stored secretly inside each entity—in contrast to symmetric crypto systems where a single secret key needs to be stored inside several different entities. In context of PKC, if one entity is compromised, the others remain unaffected.Besides encrypting or signing of messages, PKC can be employed to control user access to a device via electronic tokens. Examples for this are Remote Keyless Entry (RKE) systems [1] in the automotive domain or Hilti's TPS technology [2]. These systems incorporate contactless electronic tokens that substitute classical mechanical keys. The owner or authorized user identifies himself to the user device (UD) by possession of the token. UD and token are linked. Only if a linked token is presented to UD, it is enabled or access to UD is granted. In order to present a token to UD, information has to be exchanged between the two. The communication channel is usually assumed to be insecure. To prevent the usage of a device or its accessibility by an unauthorized person, the authentication has to be performed in a secure manner.Authentication schemes based on Public Key Cryptography such as the Needham-Schroeder protocol [3], Okamoto-Protocol [4], and Schnorr-Protocol [5] provide authentication procedures where no confidential data is transmitted. Secret keys are stored in the tokens only and not in UD, thus omitting the need for costly security measures in the UD. Only public keys have to be introduced into UD (see Section 2), which can usually only be done by the manufacturer (OEM) of UD. In real-world operation, the introduction of public keys is done in the field where UD is not necessarily under the control of OEM and a live online connection to OEM may not be possible. PKC is computationally very expensive, especially when aiming for high security levels. Dedicated hardware can provide the necessary speed up of cryptographic operations. With the decreasing cost of FPGAs, these devices are introduced more and more into embedded systems and mass market products. Therefore, hardware accelerators can be made available in these cost sensitive systems by adding cryptographic computation blocks on FPGA.We propose a system to introduce public keys into FPGA based user devices to pair them with a new token. The proposed key flashing method allows authorization of the flashing process byOEM. Additionally it can be carried out with UD in the field and with no active online connection to OEM while flashing a key into UD. Introduction or flashing of new keys to an embedded device can be seen as a special case of a software update. Latter focuses on protection of the intellectual property, interoperability, correctness, robustness, and security. Recent approaches for the automotive area have been developed, for example, in the german HIS [6, 7] or the EAST-EEA [8] project. A general approach considering security and multiple software providers is given in [9]. Nevertheless, general update approaches are focused on the protection of IP and the provider against unauthorized copying and less on the case that the system has to be especially protected against unwanted updates as in our key flashing scenario.The remainder of this paper is structured as follows. In Section2, we present the basic application scenario followed by a short introduction to public key cryptography in Section 3. Section 4 describes a high-speed architecture for cryptographic computations. The requirements for the keyflashing scenario are described in Section 5. Based on this, we propose our flashing concept in Section 6, followed by the according requirements (Section 6.3). Section 7 details the flashing protocol with a live online connection available and Section 8 the protocol with no online dependability. Implementation details of the prototypical flashing framework are given in Section 9. We conclude with a security analysis and an outlook to future work in Sections 10 and 11.


## 2. Application Scenario: Automotive Access  Control Systems

The target application focused on in this work is foremost automotive access control system. They comprise an entity that acts as the verifier (an ECU within the car) and an entity that acts as a prover (the traditional car key). Traditionally, a standard car key serves the sole purpose of identifying the current owner of the key as the authenticated user of the car (authentication  by  ownership). This also holds true for electronic car keys. As depicted in Figure 1, access to the car is granted by unlocking the doors only if the correct car key (prover) is presented to the car. The same procedure can be employed to disable or enable the immobilizer of the car, allowing the car's engine to start or not.Figure 1
Access control: authentication scheme.The automotive domain implies a very specific set of requirements. The industry is extremely cost driven, thus creating the need for very small hardware footprints. To comply with limited cost, OEMs tend to resort to cheap off-the-shelf components instead of specialized ASICs or complete systems-on-chip (SoC). Additionally a car’s life cycle is about 10–15 years. Within this time span, all systems should work flawlessly.Access control systems are a natural point of attack. Therefore, they need to offer very good security. To provide this, electronic car keys incorporate some kind of cryptographic algorithm. Raising security levels in this context can be achieved by adaption of the authentication protocol being used, enlarging key lengths, or substituting cryptographic primitives. All these measures tend to increase computation times. But all underlying computations and algorithms incorporated in access systems shall not be noticeable to the user of a car for best usability. Keeping the underlying hardware platform adaptable to varying interfaces and functionalities, it enables for integration of the same hardware components into a wide range of car keys for a multitude of different car models. With FPGAs dropping in cost over the last years, they also have been introduced more and more in cost driven industries such as the automotive domain. These devices are already being used in infotainment and multimedia devices. In addition to that, they can be used to provide dedicated hardware modules to accelerate cryptographic computations within user authentication in these systems. By using FPGA platforms for access control systems, they are adaptable over the lifetime of a car and offer some flexibility regarding changes in protocol and processing units.In summary, we will regard the following application scenario: an access control system is applied to a mobile user device (UD); in our case, a vehicle is depicted in Figure 2. Through the access control system, the use of the UD can be restricted by allowing only the owner or authorized user access to the device. A transponder (TRK) serves as an electronic version of a mechanical key. TRK communicates to UD over a wireless communication channel. The user device accepts a limited number of transponders. If one of these is presented to the user device, it authenticates the transponder and the device is unlocked, thus granting access. Anyone possessing a valid TRK is considered an authorized user (OWN). This setup forms an authentication chain for usage of UD. An authorized user is authenticated through the possession of a valid TRK paired to the the UD. TRK in turn is authenticated by UD.Figure 2
Entities and application scenario.In automotive systems, authentication of aTRK can be achieved through a number of methods: rolling codes, symmetric codes, one-way-functions, or asymmetric codes. As analyzed in [10], there is a major disadvantage in using rolling codes and symmetric codes since secrets have to be stored within TRK as well as in UD, demanding for highly secure key management. One-way-functions such as cryptographic hash functions can circumvent this to some extent but demand for a substantial amount of secure storage. The most wide spread method for authentication in mobile devices is probably the usage of rolling codes (such as the KeeLoq [11] algorithm) due to easy implementation, followed by one-way-functions.Asymmetric codes are very computationally expensive, although they provide extremely high security. With the advent of more and more computational power in embedded systems [12, 13], introducing such codes for user authentication is now feasible.OEM is the manufacturer of UD. Due to the mobility of UD, it may be nowhere near OEM. Therefore, a service infrastructure has been established by OEM to repair, service, or replace a UD in the field. This infrastructure consists of a number of service points SP that are OEM certified. In the depicted example from the automotive domain, this would be a dealer or a car repair shop. SP is enabled by the OEM to carry out certain work on UD and acts in a way as a substitute for the OEM in the field.In case of loss of a transponder, it is desirable to replace it, particularly if the user device itself is very costly or actually irreplaceable. Since the user device is mobile, linking a new transponder to aUD usually needs to be done in the field. This might include very secluded areas with minor to none communication infrastructure.


## 3. Basic PKC Functionalities

In 1976, Diffie and Hellman introduced the first PKC crypto system [14] for data encryption and confidential data transfer. Two different keys are used, one public (PK) and the other secret (SK). SK and corresponding PK are a fixed and unique keypair. It must be computational infeasible to deduce the secret key (SK) from the public key. With PK, a message Mp can be encrypted into Mc but not decrypted with the same key. This can only be done with knowledge of SK. If an entity Alice wants to transmit a message MAlice to an entity Bob, it encrypts it with Bobs public key PKBob. Only Bob can retrieve the plain text from the encrypted message, by applying the appropriate decryption algorithm using his own secret key SKBob.PKC can also be used to digitally sign a message. For this, a signature scheme is used that is usually different from the encryption scheme. When signing a message, the secret key is used and the signature can be verified using the according public key. In other words, if Bob wants to sign a message, he uses his own private key that is unique to him and solely known to himself. This key is used to sign a cryptographic hash value of the messageMBob. The resulting value {HASH(MBob)}sig is transmitted together with MBob. A receiver can validate the signature by using Bob’s public key to retrieve HASH(MBob). From MBob, the receiver can compute the according hash value and compare it with the retrieved value. If both match, the signature has been validated. Since in the case of signature schemes the public key is often called verification key and the secret key is called signing key, we denote them accordingly VK and SK in the following.


## 4. Cryptographic Processing Entity

Computational efforts of cryptographic functionalities for PKC are very high and time consuming if carried out on today's standard platforms (i.e., microcontrollers) for embedded applications. Integrating security algorithms into FPGA platforms can provide high speed up of demanding PKC crypto systems such ashyper  elliptic  curve  cryptography (HECC). By adding dedicated hardware modules for certain parts of a crypto algorithm, a substantial reduction of computation time can be achieved [15, 16].In [16], an FPGA platform has been introduced which allows extremely fast authentication as proven by an experimental setup with two of these platforms. For this demonstrator, both platforms have been implemented on a Xilinx Spartan-3 XC3S2000 FPGA at 33 MHz. The communication channel in the setup is a wireless automotive transmitter [17] as is currently used in keyless go systems and is clocked with 412,5 kHz. The transceiver is connected to the FPGA system over SPI. Authentication of TRK via the Schnorr-protocol [5] in this setup lasts 120 ms including communication times over the wireless channel. To enable for even faster computation, we have developed a new, lean cryptographic core for Xilinx FPGA. It enables to carry out aforementioned mutual authentication within 82 ms.Both platforms carry out calculations for public key cryptography based on hyper elliptic curves (HECC). They offer a higher security level than RSA while relying on relatively small key sizes of around 160 bit [18]. A detailed view on HECC and its underlying mathematics can be found in [19].As shown in Figure3, the automotive electronic control unit (ECU) comprises a MicroBlaze processor that handles arbitrary tasks necessary for running the car and is equipped with an appropriate interface such as CAN to communicate with other ECUs residing in the vehicle. Additionally, a coprocessing unit composes of a PicoBlaze processor [20] and a Cryptographic  Processing  Module (CPM) is included. All cryptographic computations are done within this coprocessor. When no extensive tasks need to be run and only cryptographic functionality is needed, the coprocessor can also be run  without the MicroBlaze. In this case, the PicoBlaze Controller is interfaced directly to the communication interface. This setup is very suitable for implementing a car key (TRK).Figure 3
Overview of the system design.For HECC, three types of operations are essential (Pi denoting a point on a hyperelliptic curve and k, y, a, e, r are denoting integer values):(i)
calculation on a hyperelliptic curve (k·P and P1+P2),(ii)
integer calculation with large operands (y=a·e+r),(iii)
data exchange to/from the cryptographic unit.Each arithmetic operation is assigned to a specialized hardware module to enable fast computation. At the same time, all cryptographic functionality is bound strictly to CPM, thus keeping all sensitive data on chip.


### 4.1. Cryptographic Processing Module

TheCryptographic  Processing  Module (CPM) is designed to efficiently compute k·P on a hyperelliptic curve, as well as integer multiplication with large operands. As depicted in Figure 4, the proposed architecture encompasses dedicated modules (HPU, bigINTmul) for these two operations and an additional module for generating random numbers (RNG).Figure 4
Cryptographic processing module (CPM).A small finite state machine (FSM) is implemented for control flow of the calculations and to provide data exchange over the PicoBlaze processor. It controls all modules within the CPM directly. All arithmetic modules can work fully in parallel, allowing for concurrent operations within the protocol if necessary. A set of registers is provided for data exchange that can be accessed directly by PicoBlaze. Registere acts as input whereas yi and the address space X of the CPM's internal memory DataMem are doubling as output registers. Some additional internal registers store cryptographic key material (Reg ai) or random numbers (Reg ri) and cannot be accessed from outside the CPM.


#### 4.1.1. bigINTmul

A dedicated integer unit performingy=a·b+c on large operands is included in the CPM. Input to the multiplier are two operands a and b. The result p=a·b and operand c are then input to an adder stage calculating y=p+c. A sequential multiplier as depicted in Figure 5 is provided to execute a naive shift&add algorithm. p is accumulated by bitwise shifting of the bigger operand b, evaluating the least significant bit and adding a to the intermediate result if b0=1, and then shifting p. If b0=0, p is shifted without adding a.Figure 5
Sequential multiplier.Figure 6
HECC processing unit.In our use case, the two operands do not have the same bitlength since one input is the platforms secret keyai and the other input is the challenge e.


#### 4.1.2. HECC Processing Unit

TheHECC  Processing  Unit (HPU) acts as a stand alone module for scalar multiplication Xi=ri·Pi on a hyper elliptic curve. It comprises a dedicated arithmetic logical unit dALU for finite field arithmetic (GF-operations), internal memory DataMem for storage of intermediate values such as curve parameters and points Pi, and a control entity HECC  CTRL connected to a program memory pMEM.HECC  CTRL in conjunction with pMEM implements the control flow of a dedicated algorithm for a scalar multiplication as a fixed sequence of GF-operations. The control flow is strongly optimized to execute a scalar multiplication in wMOF [21, 22]. To execute it, a highly specialized instruction set is implemented. An example of such an instruction is shiftl_2 which shifts the content of the accumulator 2 bits to the left, an operation essential in wMOF [22]. The full instruction sequence of wMOF is stored in pMEM.HPU is laid out as accumulator machine with harvard architecture. This enables to implement different data widths forDataMem and pMEM individually. This is particularly advantageous as we operate on galois fields GF(2n), n being a big prime number, resulting in data words of n-bit length being stored in DataMem, while pMEM only stores minimal instruction codes.Input to the HECC processing unit is a scalarri (bitlength of ri≤l) that is written into a dedicated register rREG of length l. Point Pi is a predetermined common point on a hyperelliptic curve and acts as a constant input decided upon during design time. Therefore, it is permanently stored in DataMem together with other curve parameters.After storingr1, HPU is triggered via the signal control to start a scalar multiplication. As soon as the result X representing the commitment is available, this is signaled by HPU over trigger. All ri are random numbers generated by RNG. Therefore r1 is loaded from the RNG module into HPU and X=r1·P1 is computed. Simultaneously, RNG generates a new random number r2. After HPU signals the end of the current operation, r2 can be loaded into rREG and HPU can calculate a new result X=r2P2.The dedicated arithmetic logical unit (dALU) can perform u+v, u·vmodp and u2 with u,v∈GF(2n). On galois fields of genus 2, addition and subtraction can be implemented very efficiently by a bitwise XOR of the two operands u and v. Modular multiplication can be implemented as shown in Algorithm 1. It is performed as a Shift&Add algorithm with modular reduction in every step by adding the irreducible polynomial P(x) if the intermediate result T(x) exceeds the field size of GF(2n). A single GF-multiplication U·VmodP will take n clock cycles since the size of the input word U is n-bit and U is examined bitwise (line 2–7 in Algorithm 1).Algorithm 1:GF multiplication of U·V  mod P by adding n times.
Requires: U(x)=un-1xn-1+⋯+u1x+u0∈GF(2n),V(x)=vn-1xn-1+⋯+v1x+u0∈GF(2n),P(x)=xn+pn-1xn-1+⋯+p1x+p0∈GF(2n+1)Ensure: U(x)V(x)modP(x)(1)T(x)=tnxn+⋯+t1x+0←0(2)for i=n-1  to 0 do(3)m←ui·V(x)(4)r←tn·P(x)(5)T(x)←(T(x)+m-r)x(6)i←i-1(7)end for(8)return  T(x)/xTo speed up the multiplication a scalable GF-Multiplier (MALU) is integrated into the HPU. Instead of examiningU a single bit at a time, a number d of neighboring bits in U are evaluated blockwise and in parallel. Algorithm 2 shows how d adder stages with modular reduction are fed with the operands U and V (line 3–6). This gives d individual intermediate results Td(x) which are then added and reduced to form the result T(x) (line 6). This addition step is done over d cascading adders, so no additional clock cycle is necessary. The final result of a GF-multiplication is available after ⌊(n+d-1)/d⌋ clock cycles.Algorithm 2:GF multiplication of U·V mod P by adding ⌊(n+d-1)/d⌋ times.
Requires: U(x)=un-1xn-1+⋯+u1x+u0∈GF(2n),V(x)=vn-1xn-1+⋯+v1x+u0∈GF(2n),P(x)=xn+pn-1xn-1+⋯+p1x+p0∈GF(2n+1)Ensure: U(x)V(x)modP(x)(1)T(x)=tnxn+⋯+t1x+0←0(2)for  i=n-1  to≤0  do(3)for  j=i  to  i-d+1  do(4)mj←uj·V(x)(5)rj←tn·P(x)(6)T(x)←(T(x)+mj-rj)x(7)end for(8)i←i-d(9)end for(10)returenT(x)/(xd-⌊(n+d-1)modd⌋)Speed up of the multiplication is achieved through the parallelization of additions, but hardware area increases as well. No additional instructions inpMEM are necessary, thus keeping this change in algorithm transparent to HECC  CTRL.Althoughu2 can be calculated by feeding u into both inputs of MALU, a dedicated HW squarer requires 25% less computation time [23]. Because HECADD and HECDBL operations depend heavily on squaring [24], we included a GF-Square module in dALU.


### 4.2. Resource Usage and Timing Results

Table1 gives a detailed view of the size of our system, and Table 2 shows the processing speed. To the best of our knowledge, no measurements of the execution time of Schnorr- and Okamoto-Authentication protocols based on HECC in the domain of embedded systems has been published. Because of this, we use the execution time of one scalar multiplication k·P as a benchmark in Table 3 to give a fair comparison of our architecture to other implementations.Table 1
Resource usage.
OkamotoSchnorrSlicesSlice FlipFlopsLUTsBRAMsSlicesSlice FlipFlopsLUTsBRAMsComplete system26512263432382439202637995IPicoBlaze38928671413892867141IICPM22751977358502039174030550II-aBigINTmul26539220102653922010II-bHECC processing16841082285571682108127594II-b-iHECCCTRL6132108061321080II-b-iidALU9536581611095365816110II-b-iiiProgramMem50709315070931II-b-ivdbus98016209801620II-b-vDataMem(singlepage)4533248386————II-b-viDataMem(doublepage)————4523246573Table 2
Performance speed.
Operation[μs]@50 MHzSchnorrOkamotoScalar multiplicationk·P8 069Complete protocol81 621132 858Table 3
Duration of 1 scalar multiplicationk·P.
No.PlatformSlicesf [MHz]t [ms]tnormalized(f)1Full Custom HW[26]≫ 160004520,21,0328051μC & CoPro[18]378112248833,893Microblaze & Coproc[16]19843326,714CrμP[27]1854 (+2379 for memory)31,2530,31,074HECC processorThis work2439508,06930,46As shown in Table1, the deviation in size of the platform synthesized for executing a single scalar multiplication and the platform synthesized for execution two of this operation is less than 10%. The increase lies in the Cryptographic  Processing  Module (CPM) due to the increase in memory needed. An additional secret key a2, as well as an additional random number r2, needs to be stored, thus adding two registers. Also a 2nd memory page is needed, reflecting directly in the doubled number of BRAMs. These in turn require some additional slices for glue logic and enlarged multiplexers.In a prototypical setup both the Schnorr- and Okamoto authentication protocols have been implemented. Table2 shows that for both variants our architecture easily beats the real-time constraint of 180 ms, which is the average human reaction time [25].When comparing our architecture with others (see Table3), we compute a single k·P in roughly 8 ms. This is more than twice as fast as the platform no. 3 and no. 4. It also outperforms platform no. 1 which is one of the first full hardware implementations of a HECC scalar multiplication.


## 4.1. Cryptographic Processing Module

TheCryptographic  Processing  Module (CPM) is designed to efficiently compute k·P on a hyperelliptic curve, as well as integer multiplication with large operands. As depicted in Figure 4, the proposed architecture encompasses dedicated modules (HPU, bigINTmul) for these two operations and an additional module for generating random numbers (RNG).Figure 4
Cryptographic processing module (CPM).A small finite state machine (FSM) is implemented for control flow of the calculations and to provide data exchange over the PicoBlaze processor. It controls all modules within the CPM directly. All arithmetic modules can work fully in parallel, allowing for concurrent operations within the protocol if necessary. A set of registers is provided for data exchange that can be accessed directly by PicoBlaze. Registere acts as input whereas yi and the address space X of the CPM's internal memory DataMem are doubling as output registers. Some additional internal registers store cryptographic key material (Reg ai) or random numbers (Reg ri) and cannot be accessed from outside the CPM.


### 4.1.1. bigINTmul

A dedicated integer unit performingy=a·b+c on large operands is included in the CPM. Input to the multiplier are two operands a and b. The result p=a·b and operand c are then input to an adder stage calculating y=p+c. A sequential multiplier as depicted in Figure 5 is provided to execute a naive shift&add algorithm. p is accumulated by bitwise shifting of the bigger operand b, evaluating the least significant bit and adding a to the intermediate result if b0=1, and then shifting p. If b0=0, p is shifted without adding a.Figure 5
Sequential multiplier.Figure 6
HECC processing unit.In our use case, the two operands do not have the same bitlength since one input is the platforms secret keyai and the other input is the challenge e.


### 4.1.2. HECC Processing Unit

TheHECC  Processing  Unit (HPU) acts as a stand alone module for scalar multiplication Xi=ri·Pi on a hyper elliptic curve. It comprises a dedicated arithmetic logical unit dALU for finite field arithmetic (GF-operations), internal memory DataMem for storage of intermediate values such as curve parameters and points Pi, and a control entity HECC  CTRL connected to a program memory pMEM.HECC  CTRL in conjunction with pMEM implements the control flow of a dedicated algorithm for a scalar multiplication as a fixed sequence of GF-operations. The control flow is strongly optimized to execute a scalar multiplication in wMOF [21, 22]. To execute it, a highly specialized instruction set is implemented. An example of such an instruction is shiftl_2 which shifts the content of the accumulator 2 bits to the left, an operation essential in wMOF [22]. The full instruction sequence of wMOF is stored in pMEM.HPU is laid out as accumulator machine with harvard architecture. This enables to implement different data widths forDataMem and pMEM individually. This is particularly advantageous as we operate on galois fields GF(2n), n being a big prime number, resulting in data words of n-bit length being stored in DataMem, while pMEM only stores minimal instruction codes.Input to the HECC processing unit is a scalarri (bitlength of ri≤l) that is written into a dedicated register rREG of length l. Point Pi is a predetermined common point on a hyperelliptic curve and acts as a constant input decided upon during design time. Therefore, it is permanently stored in DataMem together with other curve parameters.After storingr1, HPU is triggered via the signal control to start a scalar multiplication. As soon as the result X representing the commitment is available, this is signaled by HPU over trigger. All ri are random numbers generated by RNG. Therefore r1 is loaded from the RNG module into HPU and X=r1·P1 is computed. Simultaneously, RNG generates a new random number r2. After HPU signals the end of the current operation, r2 can be loaded into rREG and HPU can calculate a new result X=r2P2.The dedicated arithmetic logical unit (dALU) can perform u+v, u·vmodp and u2 with u,v∈GF(2n). On galois fields of genus 2, addition and subtraction can be implemented very efficiently by a bitwise XOR of the two operands u and v. Modular multiplication can be implemented as shown in Algorithm 1. It is performed as a Shift&Add algorithm with modular reduction in every step by adding the irreducible polynomial P(x) if the intermediate result T(x) exceeds the field size of GF(2n). A single GF-multiplication U·VmodP will take n clock cycles since the size of the input word U is n-bit and U is examined bitwise (line 2–7 in Algorithm 1).Algorithm 1:GF multiplication of U·V  mod P by adding n times.
Requires: U(x)=un-1xn-1+⋯+u1x+u0∈GF(2n),V(x)=vn-1xn-1+⋯+v1x+u0∈GF(2n),P(x)=xn+pn-1xn-1+⋯+p1x+p0∈GF(2n+1)Ensure: U(x)V(x)modP(x)(1)T(x)=tnxn+⋯+t1x+0←0(2)for i=n-1  to 0 do(3)m←ui·V(x)(4)r←tn·P(x)(5)T(x)←(T(x)+m-r)x(6)i←i-1(7)end for(8)return  T(x)/xTo speed up the multiplication a scalable GF-Multiplier (MALU) is integrated into the HPU. Instead of examiningU a single bit at a time, a number d of neighboring bits in U are evaluated blockwise and in parallel. Algorithm 2 shows how d adder stages with modular reduction are fed with the operands U and V (line 3–6). This gives d individual intermediate results Td(x) which are then added and reduced to form the result T(x) (line 6). This addition step is done over d cascading adders, so no additional clock cycle is necessary. The final result of a GF-multiplication is available after ⌊(n+d-1)/d⌋ clock cycles.Algorithm 2:GF multiplication of U·V mod P by adding ⌊(n+d-1)/d⌋ times.
Requires: U(x)=un-1xn-1+⋯+u1x+u0∈GF(2n),V(x)=vn-1xn-1+⋯+v1x+u0∈GF(2n),P(x)=xn+pn-1xn-1+⋯+p1x+p0∈GF(2n+1)Ensure: U(x)V(x)modP(x)(1)T(x)=tnxn+⋯+t1x+0←0(2)for  i=n-1  to≤0  do(3)for  j=i  to  i-d+1  do(4)mj←uj·V(x)(5)rj←tn·P(x)(6)T(x)←(T(x)+mj-rj)x(7)end for(8)i←i-d(9)end for(10)returenT(x)/(xd-⌊(n+d-1)modd⌋)Speed up of the multiplication is achieved through the parallelization of additions, but hardware area increases as well. No additional instructions inpMEM are necessary, thus keeping this change in algorithm transparent to HECC  CTRL.Althoughu2 can be calculated by feeding u into both inputs of MALU, a dedicated HW squarer requires 25% less computation time [23]. Because HECADD and HECDBL operations depend heavily on squaring [24], we included a GF-Square module in dALU.


## 4.1.1. bigINTmul

A dedicated integer unit performingy=a·b+c on large operands is included in the CPM. Input to the multiplier are two operands a and b. The result p=a·b and operand c are then input to an adder stage calculating y=p+c. A sequential multiplier as depicted in Figure 5 is provided to execute a naive shift&add algorithm. p is accumulated by bitwise shifting of the bigger operand b, evaluating the least significant bit and adding a to the intermediate result if b0=1, and then shifting p. If b0=0, p is shifted without adding a.Figure 5
Sequential multiplier.Figure 6
HECC processing unit.In our use case, the two operands do not have the same bitlength since one input is the platforms secret keyai and the other input is the challenge e.


## 4.1.2. HECC Processing Unit

TheHECC  Processing  Unit (HPU) acts as a stand alone module for scalar multiplication Xi=ri·Pi on a hyper elliptic curve. It comprises a dedicated arithmetic logical unit dALU for finite field arithmetic (GF-operations), internal memory DataMem for storage of intermediate values such as curve parameters and points Pi, and a control entity HECC  CTRL connected to a program memory pMEM.HECC  CTRL in conjunction with pMEM implements the control flow of a dedicated algorithm for a scalar multiplication as a fixed sequence of GF-operations. The control flow is strongly optimized to execute a scalar multiplication in wMOF [21, 22]. To execute it, a highly specialized instruction set is implemented. An example of such an instruction is shiftl_2 which shifts the content of the accumulator 2 bits to the left, an operation essential in wMOF [22]. The full instruction sequence of wMOF is stored in pMEM.HPU is laid out as accumulator machine with harvard architecture. This enables to implement different data widths forDataMem and pMEM individually. This is particularly advantageous as we operate on galois fields GF(2n), n being a big prime number, resulting in data words of n-bit length being stored in DataMem, while pMEM only stores minimal instruction codes.Input to the HECC processing unit is a scalarri (bitlength of ri≤l) that is written into a dedicated register rREG of length l. Point Pi is a predetermined common point on a hyperelliptic curve and acts as a constant input decided upon during design time. Therefore, it is permanently stored in DataMem together with other curve parameters.After storingr1, HPU is triggered via the signal control to start a scalar multiplication. As soon as the result X representing the commitment is available, this is signaled by HPU over trigger. All ri are random numbers generated by RNG. Therefore r1 is loaded from the RNG module into HPU and X=r1·P1 is computed. Simultaneously, RNG generates a new random number r2. After HPU signals the end of the current operation, r2 can be loaded into rREG and HPU can calculate a new result X=r2P2.The dedicated arithmetic logical unit (dALU) can perform u+v, u·vmodp and u2 with u,v∈GF(2n). On galois fields of genus 2, addition and subtraction can be implemented very efficiently by a bitwise XOR of the two operands u and v. Modular multiplication can be implemented as shown in Algorithm 1. It is performed as a Shift&Add algorithm with modular reduction in every step by adding the irreducible polynomial P(x) if the intermediate result T(x) exceeds the field size of GF(2n). A single GF-multiplication U·VmodP will take n clock cycles since the size of the input word U is n-bit and U is examined bitwise (line 2–7 in Algorithm 1).Algorithm 1:GF multiplication of U·V  mod P by adding n times.
Requires: U(x)=un-1xn-1+⋯+u1x+u0∈GF(2n),V(x)=vn-1xn-1+⋯+v1x+u0∈GF(2n),P(x)=xn+pn-1xn-1+⋯+p1x+p0∈GF(2n+1)Ensure: U(x)V(x)modP(x)(1)T(x)=tnxn+⋯+t1x+0←0(2)for i=n-1  to 0 do(3)m←ui·V(x)(4)r←tn·P(x)(5)T(x)←(T(x)+m-r)x(6)i←i-1(7)end for(8)return  T(x)/xTo speed up the multiplication a scalable GF-Multiplier (MALU) is integrated into the HPU. Instead of examiningU a single bit at a time, a number d of neighboring bits in U are evaluated blockwise and in parallel. Algorithm 2 shows how d adder stages with modular reduction are fed with the operands U and V (line 3–6). This gives d individual intermediate results Td(x) which are then added and reduced to form the result T(x) (line 6). This addition step is done over d cascading adders, so no additional clock cycle is necessary. The final result of a GF-multiplication is available after ⌊(n+d-1)/d⌋ clock cycles.Algorithm 2:GF multiplication of U·V mod P by adding ⌊(n+d-1)/d⌋ times.
Requires: U(x)=un-1xn-1+⋯+u1x+u0∈GF(2n),V(x)=vn-1xn-1+⋯+v1x+u0∈GF(2n),P(x)=xn+pn-1xn-1+⋯+p1x+p0∈GF(2n+1)Ensure: U(x)V(x)modP(x)(1)T(x)=tnxn+⋯+t1x+0←0(2)for  i=n-1  to≤0  do(3)for  j=i  to  i-d+1  do(4)mj←uj·V(x)(5)rj←tn·P(x)(6)T(x)←(T(x)+mj-rj)x(7)end for(8)i←i-d(9)end for(10)returenT(x)/(xd-⌊(n+d-1)modd⌋)Speed up of the multiplication is achieved through the parallelization of additions, but hardware area increases as well. No additional instructions inpMEM are necessary, thus keeping this change in algorithm transparent to HECC  CTRL.Althoughu2 can be calculated by feeding u into both inputs of MALU, a dedicated HW squarer requires 25% less computation time [23]. Because HECADD and HECDBL operations depend heavily on squaring [24], we included a GF-Square module in dALU.


## 4.2. Resource Usage and Timing Results

Table1 gives a detailed view of the size of our system, and Table 2 shows the processing speed. To the best of our knowledge, no measurements of the execution time of Schnorr- and Okamoto-Authentication protocols based on HECC in the domain of embedded systems has been published. Because of this, we use the execution time of one scalar multiplication k·P as a benchmark in Table 3 to give a fair comparison of our architecture to other implementations.Table 1
Resource usage.
OkamotoSchnorrSlicesSlice FlipFlopsLUTsBRAMsSlicesSlice FlipFlopsLUTsBRAMsComplete system26512263432382439202637995IPicoBlaze38928671413892867141IICPM22751977358502039174030550II-aBigINTmul26539220102653922010II-bHECC processing16841082285571682108127594II-b-iHECCCTRL6132108061321080II-b-iidALU9536581611095365816110II-b-iiiProgramMem50709315070931II-b-ivdbus98016209801620II-b-vDataMem(singlepage)4533248386————II-b-viDataMem(doublepage)————4523246573Table 2
Performance speed.
Operation[μs]@50 MHzSchnorrOkamotoScalar multiplicationk·P8 069Complete protocol81 621132 858Table 3
Duration of 1 scalar multiplicationk·P.
No.PlatformSlicesf [MHz]t [ms]tnormalized(f)1Full Custom HW[26]≫ 160004520,21,0328051μC & CoPro[18]378112248833,893Microblaze & Coproc[16]19843326,714CrμP[27]1854 (+2379 for memory)31,2530,31,074HECC processorThis work2439508,06930,46As shown in Table1, the deviation in size of the platform synthesized for executing a single scalar multiplication and the platform synthesized for execution two of this operation is less than 10%. The increase lies in the Cryptographic  Processing  Module (CPM) due to the increase in memory needed. An additional secret key a2, as well as an additional random number r2, needs to be stored, thus adding two registers. Also a 2nd memory page is needed, reflecting directly in the doubled number of BRAMs. These in turn require some additional slices for glue logic and enlarged multiplexers.In a prototypical setup both the Schnorr- and Okamoto authentication protocols have been implemented. Table2 shows that for both variants our architecture easily beats the real-time constraint of 180 ms, which is the average human reaction time [25].When comparing our architecture with others (see Table3), we compute a single k·P in roughly 8 ms. This is more than twice as fast as the platform no. 3 and no. 4. It also outperforms platform no. 1 which is one of the first full hardware implementations of a HECC scalar multiplication.


## 5. Pairing of Verifier/Prover Devices

With introduction of public-key-cryptography to automotive access control systems is advantageous for logistics. Less secret key material has to be handled. When integrating an authentication protocol such as Schnorr [5], no secret key resides in a vehicle (UD)—it only needs to be stored in the vehicle's transponder key token (TRK). Pairing of the two is done by storing a transponders public key in UD. In this paper, we mainly focus on this key flashing procedure for automotive entities and especially introduction of key material into UD during it's lifetime in the field.EveryUD has a number of public keys of transponders securely stored, thus establishing a “guest list” of legal TRKs. During production, at least two initial public keys of TRKs are written to the user device. This ensures that upon loss of one of the transponders, the remaining can be used to authenticate the owner. This initial operation certainly has to be secured against attacks to ensure that the “guest list” is not altered maliciously, otherwise illegal access to a UD might be granted.As mentioned above, it is necessary to pairTRKs with a UD. This is achieved by flashing the public key of TRK into the user device, where the key is stored securely and is protected against unauthorized alteration. A number of initial TRKs are paired during production in a secured environment by the OEM. Today pairing TRK to UD is done by introducing some kind of key material into UD, thus authorizing this token to use UD. Today's procedures either demand a live online connection to OEM or accept new TRKs if a “master” token (MTRK) is presented to the device [28, 29]. This means that such UD specific MTRK have to be stored very securely by SP and OEM has to fully entrust SP to do so. At the same time, there is no way to prevent TRKs to be flashed into a UD. Therefore, they have to be kept in secure, physical storage as well.When employing asymmetric codes, these drawbacks are inexistent. Pairing procedures in this case depend mostly on atrusted  third  party (TTP) that generates key pairs and distributes them to the different entities. Because not only public key material is transferred but also secret key material this demands for fully encrypted end-to-end communication channels. Traditionally, this is done by establishing a mutual secret key between the two communication partners (i.e., via Diffie-Hellman key exchange [14]) and using symmetric ciphers to encrypt all data over the communication channel.In our application scenario, we have the following main participants:(i)
a user deviceUD that may only be accessed or used by an authenticated user,(ii)
a human userOWN and he is authorized to access or use UD if he possesses a legitimate token,(iii)
a transponder key tokenTRKorig originally linked to UD and a second token TRKnew that shall be flashed to UD additionally,(iv)
the manufacturerOEM that produces UD.UD accepts a number of TRK to identify an authenticated user OWN of the UD. At least, two tokens are linked to a UD by storing the respective public keys  VKTRK inside the UD. The OEM is initially the only entity allowed to write public keys into any UD.Solely, the public keys stored inside theUD shall be used for any authorization check of TRKs. The OEM’s public key  VKOEM is stored in the UD as well.OEM, TRK, and UD can communicate over any insecure medium, through defined communication interfaces.


### 5.1. Goals and Security Requirements

A new transponderTRKnew should be linked to UD to substitute an original token TRKorig that has been lost or is defective. In the following, we will call the process of linking TRKnew to an UD   flashing. Introduction of a TRK should be possible anytime in the complete life cycle of the UD. When flashing the UD it is probably nowhere near the OEM's location while introducing a TRK needs to be explicitly authorized by the OEM. Also should any TRK only be flashable into a single UD. Theft or unauthorized use of the UD resulting from improper pairing of a TRK needs to be prohibited. In addition, we demand that online connection of UD and OEM during the pairing procedure must not be imperative.In summary, the protocol shall allow dependable authorized flashing under minimal assumptions while preventing unauthorized flashing reliably. Therefore, it has to guarantee the following properties, while assuming communication over an unsecured open channel.(i)
Correctness. In absence of an adversary, the protocol has to deliver the desired result, that is, after complete execution of the protocol, the flashing should be accomplished.(ii)
Authentication. The flashing should only be feasible if bothOEM and OWN have been authenticated and have authorized the operation.(iii)
No online dependency. The protocol shall not rely on any live online connection to theOEM.(iv)
Secrecy. No confidential data like secret keys should be retrievable by an adversary.


### 5.2. Adversary Model

We assume an adversary𝒜 that is polynomially bounded in processing power and memory. 𝒜 has access to all inter device communications, meaning he can  eavesdrop, delete, delay, alter, replay, or insert any messages. We assume further that the adversary is attacking on software level without tampering with the participating devices. Without choosing particular instances of the cryptographic primitives, we assume that the signature scheme used is secure against existential forgery of signatures and regard the cryptographic hash function used as a random oracle.


## 5.1. Goals and Security Requirements

A new transponderTRKnew should be linked to UD to substitute an original token TRKorig that has been lost or is defective. In the following, we will call the process of linking TRKnew to an UD   flashing. Introduction of a TRK should be possible anytime in the complete life cycle of the UD. When flashing the UD it is probably nowhere near the OEM's location while introducing a TRK needs to be explicitly authorized by the OEM. Also should any TRK only be flashable into a single UD. Theft or unauthorized use of the UD resulting from improper pairing of a TRK needs to be prohibited. In addition, we demand that online connection of UD and OEM during the pairing procedure must not be imperative.In summary, the protocol shall allow dependable authorized flashing under minimal assumptions while preventing unauthorized flashing reliably. Therefore, it has to guarantee the following properties, while assuming communication over an unsecured open channel.(i)
Correctness. In absence of an adversary, the protocol has to deliver the desired result, that is, after complete execution of the protocol, the flashing should be accomplished.(ii)
Authentication. The flashing should only be feasible if bothOEM and OWN have been authenticated and have authorized the operation.(iii)
No online dependency. The protocol shall not rely on any live online connection to theOEM.(iv)
Secrecy. No confidential data like secret keys should be retrievable by an adversary.


## 5.2. Adversary Model

We assume an adversary𝒜 that is polynomially bounded in processing power and memory. 𝒜 has access to all inter device communications, meaning he can  eavesdrop, delete, delay, alter, replay, or insert any messages. We assume further that the adversary is attacking on software level without tampering with the participating devices. Without choosing particular instances of the cryptographic primitives, we assume that the signature scheme used is secure against existential forgery of signatures and regard the cryptographic hash function used as a random oracle.


## 6. Key Flashing Definitions and Requirements

The objective of the proposed key flashing protocol is the introduction of a public keyVKTRK into UD. Main focus of it is the security aspect of the protocol itself, while it shall be usable under real world constraints as well. The protocol shall ensure the legitimacy of all entities involved as well as the security of the protocol itself to prevent misuse by a malicious attacker. Only after a correct, complete and successful flashing procedure, a new public key may be accepted and stored inside UD. If any error occurs during the flashing procedure, all previous steps in the protocol have to be revoked. All data resulting from these steps shall carry no information that can be exploited by an attacker.SinceTRKs gain their relevance only after successfully linking them to UD, they shall have no utility value before a successful key flashing procedure. This enables holding numerous TRKs in stock without an inherent need to restrict access to unflashed TRKs.Two basic flashing scenarios are conceivable. One is thatTRKs are flashed directly by the OEM, either during production or via an online connection as is addressed in Section 7. The second scenario is the flashing of TRKs through an authorized service point (SP) with no immediate online connection to the OEM (see Section 8).


### 6.1. Notations

For presentation of the protocols, we abstract from the specific algorithms and use abstract cryptographic primitives instead. Therefore, we introduce some assumptions, definitions, and notations.LetH be a collision resistant cryptographic hash function of length k that maps any input of arbitrary bit length to an output of fixed bit length k. Application of H can be seen as taking a fingerprint of the input and is often used by signature systems. Nevertheless, our notion of a signature system given in Definition 1, abstracts from any implicitly used hash function.Definition 1 (signature system).
LetΣ1,Σ2 be finite alphabets. A signature  systemSigSys is a 7-tuple
(1)SigSys=(M,S,SK,VK,f,S̃,Ṽ)
with  (1)
ℳ a nonempty set of messages ∅≠ℳ⊆Σ1* of arbitrary length over alphabet Σ1,(2)
𝒮 a nonempty set of signatures 𝒮⊆Σ2*,(3)
𝒮𝒦 a nonempty set of signature keys,(4)
𝒱𝒦 a nonempty set of verification keys,(5)
f a bijective function f:𝒮𝒦→𝒱𝒦, mapping each signature key SK∈𝒮𝒦 on the respective verification key f(SK)=VK∈𝒱𝒦, and we define a set 𝒦⊂𝒮𝒦×𝒱𝒦 of key pairs by 𝒦={(SK,VK)∈𝒮𝒦×𝒱𝒦∣f(SK)=VK},(6)
S̃:ℳ×𝒮𝒦→𝒮 a signature function,(7)
Ṽ:ℳ×𝒮×𝒱𝒦→{0,1} a verification function with the property, that for SK∈𝒮𝒦,VK∈𝒱𝒦,M,M′∈ℳ holds:
(2)Ṽ(M,S̃(M′,SK),VK)=1⟺f(SK)=VK,M′=M.To ease readability and presentation, we introduce a shortened notation. We define the signed message(3)SigSK(M)=(M,S̃(M,SK))
as the message M together with the respective signature. Let 𝒮ℳ be the set of all signed messages. In the following, we use an extended signature function
(4)S:M×SK⟶SM,(M,SK)⟼SigSK(M),
and the respective extended verification function
(5)V:SM×VK⟶{0,1},(SigSK(M),VK)⟼Ṽ(M,S̃(M,SK),VK).
For a tuple (M,S′), where either the signature or the message is altered, we define
(6)V((M,S′),VK)=Ṽ(M,S′,VK).
Furthermore, the tuple (SKX,VKX)∈𝒦 denotes the key pair of entity X.


### 6.2. Entities

In addition to the entities introduced in Section5 (UD, OWN, TRK, and OEM), we use three additional participants, namely the transponder manufacturer TRKM, a service point SP and an employee SPE of this service point conducting the flashing procedure. In the following, an overview of the entities involved as well as their required properties and abilities is given.


#### 6.2.1. OEM: Manufacturer

TheOEM manufactures the UD and delivers it to OWN. OWN issued the corresponding TRKs linked to the UD. All UDs are obviously known to the OEM. Furthermore, TRKM and all SP and the respective public verification keys are known to the OEM. We regard the entity OEM as a trusted central server with database functionality. OEM can store data, sign data with  SKOEM, and send data. It possesses all cryptographic abilities for PKC based authentication schemes and can thereby authenticate communication partners.


#### 6.2.2. TRK: Transponder

TRK possesses a keypair (VKTRK,  SKTRK) for PKC functionality. It is generated inside TRK to ensure that the secret key  SKTRK is known solely to TRK. Read access to  VKTRK is granted to any entity over a communication interface. As TRKs can be manufactured by a supplier TRKM that has been certified by OEM, the  VKTRK is signed by TRKM after generation and stored in TRK as a certificate. TRK possesses cryptographic primitives for PKC-based authentication schemes on prover's side and can thereby be authenticated by communication partners.


#### 6.2.3. TRKM: Transponder Manufacturer

TRKM is a supplier for TRKs that has been certified by OEM and manufactures TRKs that fulfill OEM's requirements. Certification of TRKM is bound to the fulfillment of the conditions of manufacturing, defined by OEM and is enforced through appropriate legal contracting. TRKM possesses cryptographic abilities to sign the public key  VKTRK of TRK. These signed keys act as certificates guaranteeing the origin of the respective TRK as well as the compliance of TRKM to all of OEM's manufacturing policies.


#### 6.2.4. UD: User Device

UD is enabled only when a linked TRK is presented by authenticating the TRK via a PKC authentication scheme. All linked TRKs' public keys  VKTRK are stored in UD. Additionally, the public key of the OEM  VKOEM is stored in UD and cannot be erased or altered in any way. UD grants read access to all stored public keys. Write access to the memory location of  VKTRK is only granted in the context of the proposed key flashing scheme. UD possesses all cryptographic abilities for PKC-based authentication schemes and can thereby authenticate communication partners.


#### 6.2.5. OWN: Legal User

OWN is the legal user of UD and can prove this by possession of a linked TRKorig.


#### 6.2.6. SP: Service Point

SP is a service point in the field such as a wholesaler or workshop, certified by the OEM. For the protocol, SP is considered to be a computer terminal at the respective institution. The terminal and access to it is secured by appropriate means as in standard PC practice. SP can communicate to the OEM as well as to UD. In addition, it is able to read the  VKTRK of any TRK.Furthermore,SP constitutes a trusted platform meaning that it always behaves in the expected manner for the flashing procedure and accommodates a trusted module responsible for:  (i)
storage ofOEM-authorized keymaterial of TRKs,(ii)
key management ofTRK keys,(iii)
secure counter.SP possesses cryptographic primitives for PKC-based authentication schemes on prover's and verifier's side and can thereby be authenticated by communication partners, while it can also actively authenticate communication partners.


#### 6.2.7. SPE: Employee of Service Point

SPE is a physical person that is operating SP and has to be authenticated prior to a flashing procedure to prevent misuse of the system. At the same time, SPE is regarded as a potential attacker of the flashing operation so that the protocol has to have a certain robustness against a compromised SPE. Access control of SPE to SP is enforced via password or similar. SPE is responsible for the system setup for the flashing application consisting of establishing the communication links of UD, SP, TRK, and OEM if needed.UD, TRKnew, and SP are under control of SPE, and the communication links to UD, TRKorig, TRKnew, SP, and OEM can be eavesdropped, but the trusted module cannot be penetrated.


### 6.3. Flashing Policies

In order to meet the goals defined in Section5, some additional requirements must be met as follows:  (1)
legitimation of the flashing procedure byOWN,(2)
legitimation ofTRKnew by a certified TRKM,(3)
only anOEM-authorized TRK may be flashed,(4)
any singleTRK may only be flashed into a single UD.Legitimation of a flashing procedure is achieved if the legal owner ofOWN has commissioned and approved a flashing procedure. Legal ownership of a UD is proven by OWN through possession of a valid TRK that is already activated in UD. If no such TRK is available, legal documents proving the ownership have to be presented to OEM. Such a document could be a deed of ownership, for example. If OWN cannot prove his legal ownership, it is mandatory to prohibit flashing in order to prevent usage of an illegally acquired UD with an unauthorized TRK.Legitimation ofTRK is first achieved by adhering to all manufacturing policies posed by OEM. This is guaranteed by TRKM which in turn certifies the manufactured TRKs by signing their respective public keys  VKTRK. A main requirement for a legitimate TRK is its uniqueness and accordingly the uniqueness of its cryptographic key material. Otherwise two identical TRKs, linked to two separate UDs would automatically be able to access both UDs. Additionally it has to be ensured and guaranteed that no secret key material of TRK is available to any entity other than to TRK itself.Authorization of a legitimateTRK to be flashed is handled through OEM. OEM verifies the identity of each individual TRK to be flashed. Identification of a TRK can be achieved directly via checking VKTRK. The identities are then stored by OEM. Only TRKs that have their identities checked and stored this way are considered to be authorized by OEM. Prove of authorization can be given by OEM through a signature SigOEM (VKTRK).


## 6.1. Notations

For presentation of the protocols, we abstract from the specific algorithms and use abstract cryptographic primitives instead. Therefore, we introduce some assumptions, definitions, and notations.LetH be a collision resistant cryptographic hash function of length k that maps any input of arbitrary bit length to an output of fixed bit length k. Application of H can be seen as taking a fingerprint of the input and is often used by signature systems. Nevertheless, our notion of a signature system given in Definition 1, abstracts from any implicitly used hash function.Definition 1 (signature system).
LetΣ1,Σ2 be finite alphabets. A signature  systemSigSys is a 7-tuple
(1)SigSys=(M,S,SK,VK,f,S̃,Ṽ)
with  (1)
ℳ a nonempty set of messages ∅≠ℳ⊆Σ1* of arbitrary length over alphabet Σ1,(2)
𝒮 a nonempty set of signatures 𝒮⊆Σ2*,(3)
𝒮𝒦 a nonempty set of signature keys,(4)
𝒱𝒦 a nonempty set of verification keys,(5)
f a bijective function f:𝒮𝒦→𝒱𝒦, mapping each signature key SK∈𝒮𝒦 on the respective verification key f(SK)=VK∈𝒱𝒦, and we define a set 𝒦⊂𝒮𝒦×𝒱𝒦 of key pairs by 𝒦={(SK,VK)∈𝒮𝒦×𝒱𝒦∣f(SK)=VK},(6)
S̃:ℳ×𝒮𝒦→𝒮 a signature function,(7)
Ṽ:ℳ×𝒮×𝒱𝒦→{0,1} a verification function with the property, that for SK∈𝒮𝒦,VK∈𝒱𝒦,M,M′∈ℳ holds:
(2)Ṽ(M,S̃(M′,SK),VK)=1⟺f(SK)=VK,M′=M.To ease readability and presentation, we introduce a shortened notation. We define the signed message(3)SigSK(M)=(M,S̃(M,SK))
as the message M together with the respective signature. Let 𝒮ℳ be the set of all signed messages. In the following, we use an extended signature function
(4)S:M×SK⟶SM,(M,SK)⟼SigSK(M),
and the respective extended verification function
(5)V:SM×VK⟶{0,1},(SigSK(M),VK)⟼Ṽ(M,S̃(M,SK),VK).
For a tuple (M,S′), where either the signature or the message is altered, we define
(6)V((M,S′),VK)=Ṽ(M,S′,VK).
Furthermore, the tuple (SKX,VKX)∈𝒦 denotes the key pair of entity X.


## 6.2. Entities

In addition to the entities introduced in Section5 (UD, OWN, TRK, and OEM), we use three additional participants, namely the transponder manufacturer TRKM, a service point SP and an employee SPE of this service point conducting the flashing procedure. In the following, an overview of the entities involved as well as their required properties and abilities is given.


### 6.2.1. OEM: Manufacturer

TheOEM manufactures the UD and delivers it to OWN. OWN issued the corresponding TRKs linked to the UD. All UDs are obviously known to the OEM. Furthermore, TRKM and all SP and the respective public verification keys are known to the OEM. We regard the entity OEM as a trusted central server with database functionality. OEM can store data, sign data with  SKOEM, and send data. It possesses all cryptographic abilities for PKC based authentication schemes and can thereby authenticate communication partners.


### 6.2.2. TRK: Transponder

TRK possesses a keypair (VKTRK,  SKTRK) for PKC functionality. It is generated inside TRK to ensure that the secret key  SKTRK is known solely to TRK. Read access to  VKTRK is granted to any entity over a communication interface. As TRKs can be manufactured by a supplier TRKM that has been certified by OEM, the  VKTRK is signed by TRKM after generation and stored in TRK as a certificate. TRK possesses cryptographic primitives for PKC-based authentication schemes on prover's side and can thereby be authenticated by communication partners.


### 6.2.3. TRKM: Transponder Manufacturer

TRKM is a supplier for TRKs that has been certified by OEM and manufactures TRKs that fulfill OEM's requirements. Certification of TRKM is bound to the fulfillment of the conditions of manufacturing, defined by OEM and is enforced through appropriate legal contracting. TRKM possesses cryptographic abilities to sign the public key  VKTRK of TRK. These signed keys act as certificates guaranteeing the origin of the respective TRK as well as the compliance of TRKM to all of OEM's manufacturing policies.


### 6.2.4. UD: User Device

UD is enabled only when a linked TRK is presented by authenticating the TRK via a PKC authentication scheme. All linked TRKs' public keys  VKTRK are stored in UD. Additionally, the public key of the OEM  VKOEM is stored in UD and cannot be erased or altered in any way. UD grants read access to all stored public keys. Write access to the memory location of  VKTRK is only granted in the context of the proposed key flashing scheme. UD possesses all cryptographic abilities for PKC-based authentication schemes and can thereby authenticate communication partners.


### 6.2.5. OWN: Legal User

OWN is the legal user of UD and can prove this by possession of a linked TRKorig.


### 6.2.6. SP: Service Point

SP is a service point in the field such as a wholesaler or workshop, certified by the OEM. For the protocol, SP is considered to be a computer terminal at the respective institution. The terminal and access to it is secured by appropriate means as in standard PC practice. SP can communicate to the OEM as well as to UD. In addition, it is able to read the  VKTRK of any TRK.Furthermore,SP constitutes a trusted platform meaning that it always behaves in the expected manner for the flashing procedure and accommodates a trusted module responsible for:  (i)
storage ofOEM-authorized keymaterial of TRKs,(ii)
key management ofTRK keys,(iii)
secure counter.SP possesses cryptographic primitives for PKC-based authentication schemes on prover's and verifier's side and can thereby be authenticated by communication partners, while it can also actively authenticate communication partners.


### 6.2.7. SPE: Employee of Service Point

SPE is a physical person that is operating SP and has to be authenticated prior to a flashing procedure to prevent misuse of the system. At the same time, SPE is regarded as a potential attacker of the flashing operation so that the protocol has to have a certain robustness against a compromised SPE. Access control of SPE to SP is enforced via password or similar. SPE is responsible for the system setup for the flashing application consisting of establishing the communication links of UD, SP, TRK, and OEM if needed.UD, TRKnew, and SP are under control of SPE, and the communication links to UD, TRKorig, TRKnew, SP, and OEM can be eavesdropped, but the trusted module cannot be penetrated.


## 6.2.1. OEM: Manufacturer

TheOEM manufactures the UD and delivers it to OWN. OWN issued the corresponding TRKs linked to the UD. All UDs are obviously known to the OEM. Furthermore, TRKM and all SP and the respective public verification keys are known to the OEM. We regard the entity OEM as a trusted central server with database functionality. OEM can store data, sign data with  SKOEM, and send data. It possesses all cryptographic abilities for PKC based authentication schemes and can thereby authenticate communication partners.


## 6.2.2. TRK: Transponder

TRK possesses a keypair (VKTRK,  SKTRK) for PKC functionality. It is generated inside TRK to ensure that the secret key  SKTRK is known solely to TRK. Read access to  VKTRK is granted to any entity over a communication interface. As TRKs can be manufactured by a supplier TRKM that has been certified by OEM, the  VKTRK is signed by TRKM after generation and stored in TRK as a certificate. TRK possesses cryptographic primitives for PKC-based authentication schemes on prover's side and can thereby be authenticated by communication partners.


## 6.2.3. TRKM: Transponder Manufacturer

TRKM is a supplier for TRKs that has been certified by OEM and manufactures TRKs that fulfill OEM's requirements. Certification of TRKM is bound to the fulfillment of the conditions of manufacturing, defined by OEM and is enforced through appropriate legal contracting. TRKM possesses cryptographic abilities to sign the public key  VKTRK of TRK. These signed keys act as certificates guaranteeing the origin of the respective TRK as well as the compliance of TRKM to all of OEM's manufacturing policies.


## 6.2.4. UD: User Device

UD is enabled only when a linked TRK is presented by authenticating the TRK via a PKC authentication scheme. All linked TRKs' public keys  VKTRK are stored in UD. Additionally, the public key of the OEM  VKOEM is stored in UD and cannot be erased or altered in any way. UD grants read access to all stored public keys. Write access to the memory location of  VKTRK is only granted in the context of the proposed key flashing scheme. UD possesses all cryptographic abilities for PKC-based authentication schemes and can thereby authenticate communication partners.


## 6.2.5. OWN: Legal User

OWN is the legal user of UD and can prove this by possession of a linked TRKorig.


## 6.2.6. SP: Service Point

SP is a service point in the field such as a wholesaler or workshop, certified by the OEM. For the protocol, SP is considered to be a computer terminal at the respective institution. The terminal and access to it is secured by appropriate means as in standard PC practice. SP can communicate to the OEM as well as to UD. In addition, it is able to read the  VKTRK of any TRK.Furthermore,SP constitutes a trusted platform meaning that it always behaves in the expected manner for the flashing procedure and accommodates a trusted module responsible for:  (i)
storage ofOEM-authorized keymaterial of TRKs,(ii)
key management ofTRK keys,(iii)
secure counter.SP possesses cryptographic primitives for PKC-based authentication schemes on prover's and verifier's side and can thereby be authenticated by communication partners, while it can also actively authenticate communication partners.


## 6.2.7. SPE: Employee of Service Point

SPE is a physical person that is operating SP and has to be authenticated prior to a flashing procedure to prevent misuse of the system. At the same time, SPE is regarded as a potential attacker of the flashing operation so that the protocol has to have a certain robustness against a compromised SPE. Access control of SPE to SP is enforced via password or similar. SPE is responsible for the system setup for the flashing application consisting of establishing the communication links of UD, SP, TRK, and OEM if needed.UD, TRKnew, and SP are under control of SPE, and the communication links to UD, TRKorig, TRKnew, SP, and OEM can be eavesdropped, but the trusted module cannot be penetrated.


## 6.3. Flashing Policies

In order to meet the goals defined in Section5, some additional requirements must be met as follows:  (1)
legitimation of the flashing procedure byOWN,(2)
legitimation ofTRKnew by a certified TRKM,(3)
only anOEM-authorized TRK may be flashed,(4)
any singleTRK may only be flashed into a single UD.Legitimation of a flashing procedure is achieved if the legal owner ofOWN has commissioned and approved a flashing procedure. Legal ownership of a UD is proven by OWN through possession of a valid TRK that is already activated in UD. If no such TRK is available, legal documents proving the ownership have to be presented to OEM. Such a document could be a deed of ownership, for example. If OWN cannot prove his legal ownership, it is mandatory to prohibit flashing in order to prevent usage of an illegally acquired UD with an unauthorized TRK.Legitimation ofTRK is first achieved by adhering to all manufacturing policies posed by OEM. This is guaranteed by TRKM which in turn certifies the manufactured TRKs by signing their respective public keys  VKTRK. A main requirement for a legitimate TRK is its uniqueness and accordingly the uniqueness of its cryptographic key material. Otherwise two identical TRKs, linked to two separate UDs would automatically be able to access both UDs. Additionally it has to be ensured and guaranteed that no secret key material of TRK is available to any entity other than to TRK itself.Authorization of a legitimateTRK to be flashed is handled through OEM. OEM verifies the identity of each individual TRK to be flashed. Identification of a TRK can be achieved directly via checking VKTRK. The identities are then stored by OEM. Only TRKs that have their identities checked and stored this way are considered to be authorized by OEM. Prove of authorization can be given by OEM through a signature SigOEM (VKTRK).


## 7. Key Flashing Protocol without Mediator

The most direct flashing scenario is depicted in Figure7, where the key flashing into a UD is done directly   through the OEM. This scenario is valid during production of the UD or if the OWN is not able to legitimize the procedure through the possession of a second TRK as is needed in the standard flashing scenario as described later in Section 8. Therefore the legitimation of the flashing procedure is done implicitly through the OEM by checking the legal credentials of OWN (i.e., billing receipts, legal records, etc.). Only if sufficient proof of ownership is presented to the OEM, the flashing procedure is carried out.Figure 7
Key flashing without mediator.The following entities are involved in the key flashing protocol:(i)
manufacturerOEM,(ii)
user deviceUD,(iii)
transponderTRKnew.As shown in Algorithm3, the direct flashing has two requirements. It is mandatory that UD has stored an immutable  VKOEM. This enables UD to verify the correctness of the OEM’s signature later in the flashing protocol. A mandatory requirement for carrying out the flashing procedure is that the OEM has verified that the commissioning of the flashing procedure has been done by the legal owner of UD.Algorithm 3:Direct flashing protocol (with online connection to OEM).
Requirements(i)UD has knowledge of VKOEM(ii)OEM has ensured, that the legal owner OWN of UD has commissioned the flashing procedureProtocolStep  1: For a new TRKnew to be flashed OEM reads out the respective certifiedverification keySigSKTRKM(VKTRKnew) and verifies that VKTRKM is inthe internal database of trusted transponder manufacturers.Step  2: OEM contacts UD and is authenticated using a PKC authentication protocol.UD sends SigSKUD(VKUD) to OEM.Step  3: OEM verifies that V(SigSKUD(VKUD),VKUD)=!1Step  4: OEM sends SigSKOEM(VKTRKnew,VKUD) to UD.Step  5: UD verifies that V(SigSKOEM(VKTRKnew,VKUD′),VKOEM)=!1.Step  6: UD verifies that VKUD′=!VKUD. Then the new transponder TRKnew can be activated.The protocol is completed by sending a DONE-message toOEM.In a first step,OEM reads out the public key of the TRK to be flashed (TRKBob). The manufacturer TRKM of TRKBob has certified the key by signing it (SigSKTRKM(VKTRKnew)). The OEM then checks if TRKM has fulfilled all legal obligations to be considered as a trusted manufacturer. If this is the case, the OEM checks if VKTRKnew is already stored in its internal database and if it has been already flashed to a UD or not. Only if VKTRKnew is a fresh key, it is stored in the OEM's database and the protocol is continued.The second step consists of theOEM triggering the start of the flashing procedure. UD authenticates the OEM by means of an appropriate public key authentication protocol, referring to the internally stored VKOEM. The protocol can only be passed successfully by the OEM since knowledge of the signing key SKOEM is mandatory for the entity being authenticated. Subsequently, UD sends its self-signed verification key SigSKUD(VKUD) to the OEM.The signature is then verified by theOEM in order to ensure that the transmitted verification key VKUD has not been tampered with. Subsequently, the OEM binds VKTRKnew to VKUD by composing an adequate data packet and signing it as a whole. This is then transmitted back to UD (Step  4 in Algorithm 3).UD verifies the correctness of the packet by checking the OEM's signature in Step  5. After that, UD verifies the correct binding of data packet to its own identity by inspecting the VKUD′ including the data packet received. Only if the received VKUD′ is identical to his own verification key VKUD, UD will accept VKTRKnew included in the received data packet as a valid, legitimate, and authorized transponder key to be flashed. UD stores VKTRKnew into internal protected memory and sends an acknowledge message back to the OEM. Storing VKTRKnew in UD turns TRKnew into an activated transponder VKTRKorig linked to UD. OEM logs the successful conclusion of the protocol and annotates the VKTRKnew (now VKTRKorig) accordingly to exempt it from future flashing attempts.


## 8. Key Flashing Protocol with Mediator

The procedure as outlined in Section7 demands a live online connection of UD to OEM. To fully comply with the flashing requirements introduced in Section 6, this online connection shall not be mandatory for the complete protocol. Therefore, an additional entity is introduced, a trusted Service Point SP that substitutes for the OEM in the field for introducing a new  VKTRK into a UD when no direct online connection to OEM is possible. The mediator and its properties are detailed in Section 8.1. The flashing procedure including a mediator comprises the following steps (see also Figure 8):  (i)
delegation of trust toSP,(ii)
authorization ofTRKnew by OEM,(iii)
introducing an authorizedTRKnew into an UD.Figure 8
Flashing scheme.The first two steps form an initialization phase to enable anSP to substitute for the OEM while flashing a new TRK into a UD. This two-step initialization will be detailed in Section 8.3. These steps form the first phase of the flashing process and can be done in advance without UD and OWN but need a communication link to OEM.The last of the three steps, the actual flashing process of a newVKTRK into an UD, do no longer depend on any direct interaction with OEM. Details will be given in Section 8.4.


### 8.1. Mediator

Because a mediator has to partly replace theOEM during the flashing protocol and UD only allows TRKs to be flashed through a trustworthy source—namely the OEM—the mediator has to be enabled to act as a trustworthy entity [30]. For this, the OEM has to delegate trust to a SP, in order to enable UD to entrust SP enough to accept a flashing request from it. It has to be ensured that the security of the overall flashing protocol is not weakened. Every mediator (SP) is evaluated by the OEM for its trustworthiness. Assessment factors can also include nontechnical aspects such as political and cultural environment, legal issues, or business models. Based on this evaluation, trust credentials (see Section 8.2) are issued to each individual SP.To restrict access to the flashing capability ofSP, as might be necessary in order to comply with the flashing policies of OEM a separate authentication of employees (SPE) working at SP is suggested. Such authorization of SPE can be done, for example, via a password (knowledge) or by biometrical identification (physical property).


### 8.2. Service Point as Trusted Platform

AnSP constitutes a trusted platform as defined in [30] meaning that SP always acts as specified at any point in the protocol. At the same time, it needs to act reliably in order to enforce trust policies. Typically, an SP might reside in a hostile environment and can be accessible to malicious attackers. Therefore, some minimal functionalities of SP must be inherently secure and are encapsulated in a Trusted  Zone (see Figure 9) as follows:  (i)
generation of trust key pairs,(ii)
storage of private keys (SKSPTD and SKSP),(iii)
signature generation,(iv)
enforcement of Trust Policy.Figure 9
Service point as trusted platform.For all key pairs that are generated to be used as temporary trust keys, it has to be ensured that aSKSPTD is never communicated to another entity. Also, it has to be ensured that SKSPTD cannot be deducted from VKSPTD. This can be ensured with a proper key generation algorithm. Signing of messages has to be secure in order to prevent manipulation of signed data packets. This means that any signing operation is always done with the proper signing key residing in SP.The main point of the trusted platform is the enforcement of trust policies.SP is issued a temporal trust key pair (SKSPTD,VKSPTD) as will be described in Section 8.3. This key pair expires after a timepoint T or after a certain amount of flashing procedures N. Expiration is enforced from within the Trusted  Zone with a secure unforgeable counter that is keeping track of the number of flashing cycles. As soon as the counter value reaches N, the trust key pair is fully deleted and the counter is reset. SP also compares its system time TSP to T. If TSP≥T the trust key pair is also fully deleted.


### 8.3. Trust Delegation and TRKnew Authorization

To be able to perform a key flashing procedure without an active link toOEM, a local representative has to be empowered by the OEM to perform the flashing, assuming that UD trusts only the OEM to flash legit keys. This is done by presenting a credential to UD accounting that flashing is authorized by OEM. The exchange of this credential is denoted in the following as trust  delegation.Algorithm4 shows the protocol for instantiating a mediator that can flash a TRK into a UD. Steps  I.1 to I.4 detail the trust delegation to SP. First of all, SPE is authenticated by SP to prevent SP abusive operations. Afterwards, SP can connect to OEM and request a trust credential (Step  I.1).Algorithm 4:Initialization step for mediated key flashing.
Requirements(i)OEM has knowledge of VKSP and VKTRKMProtocolStep  I.1: SPE presents his credential CREDSPE and SP authenticates SPE.  After that SPis activated and communication toOEM is enabled.Step  I.2: SP creates a new key pair (SKSPTD,VKSPTD) and sends its ID together with the createdverification keyVKSPTD as a signed request [SigSKSP(VKSPTD),VKSP] for a trust credential to OEM.Step  I.3: OEM verifies that SP and the respective verification key VKSP  islisted in the internal database of trusted mediators and thatV(SigSKSP(VKSPTD),VKSP)=!1.In this caseOEM creates a trust delegation credential SigSKOEM(VKSPTD,VKSP,T,N) bound to SPwith timestampT and number of granted transactions N and sends it to SP.Step  I.4: SP receives SigSKOEM(VKSP,VKSPTD,T,N) and stores it in the trusted storage.This step completes the trust delegation for flashing.Step  II.1: For a number of TRKnew to be flashed, SP reads out the respective certifiedverification keysSigSKTRKM(VKTRKnew) and sends SigSKSP(SigSKTRKM(VKTRKnew)) to OEM.Step  II.2: OEM verifies that VKSP and VKTRKM are in the internaldatabase of trusted peers and thatV(SigSKSP(SigSKTRKM(VKTRKnew)),VKSP)=!1 andV(SigSKTRKM(VKTRKnew),VKTRKM)=!1. Afterwards OEM creates SigSKOEM(VKTRKnew,VKSP)and sends it toSP.Step  II.3: SP receives SigSKOEM(VKTRKnew,VKSP) and stores it in the trusted storage.This step completes the activation of the transponderTRKnew for flashing over SP.A trust credential consists of a cryptographic temporal trust key pair(SKSPTD,VKSPTD) with the public key VKSPTD being signed by OEM. Therefore, SP creates a fresh trust key pair. From this pair, SP sends the fresh verification key VKSPTD as well as its ID as a signed data packet to the OEM, while the secret key SKSPTD never leaves SP. The ID is the standard verification key VKSP of the service point (see Algorithm 4 Step  I.2). For ease of implementation, this can be replaced with a unique identifier that can then be matched by the OEM to the appropriate VKSP stored in an internal database.Using VKSP  OEM verifies the correctness of the data packet received. If SP is considered a trustworthy entity, that is, if it adheres to all of OEMs policies, OEM issues a trust credential. As shown in Step  I.3 (Algorithm 4) it comprises the verification key of the trust key pair, the standard verification key (VKSP) of SP, as well as a timestamp T, and a maximum transaction number N in an OEM signed packet. Through inclusion of VKSP, OEM binds the trust key VKSPTD to SP. Later, this binding will be verified by UD (see Section 8.4). A trust key pair is only valid for a limited time and limited number of flashing operations after which it is deleted by SP. Step  I.4 concludes the trust delegation phase with SP storing the OEM-signed packet in trusted storage for later use in the actual flashing procedure (Section 8.4).In order to flash aTRKnew, the transponder needs to be authorized by OEM. The second part (Steps  II.1–Step  II.3) of the protocol shown in Algorithm 4 accomplishes this for a single TRKnew. If more than one TRK shall be set up for flashing, this part of the protocol is rerun for each additional TRKnew. SP reads out the verification key of TRK that previously has been certified and signed by TRKM. SP send this key as a self-signed message as shown in Step  II.1 to OEM for authorization. In Step  II.2, OEM verifies both signatures and ensures that TRKM as well as SP are trusted peers. If this is the case, OEM forms a data packet comprising the public key of TRKnew as well as the standard public key of SP and sends it as a signed message to SP. This message effectively binds TRKnew to SP, thus enabling solely SP to flash TRKnew into UD later on. The second part of the protocol in Algorithm 4 is finalized in Step  II.3 by SP storing the received, signed message in its trusted module.Only a limited number of authorizedTRKs can be stored at any given point in time. As soon as a TRK has been authorized by the OEM, physical access to the TRK needs to be controlled. The authorization process of TRKs is the only step that demands a data connection between SP and OEM. This does not necessarily need to be an online connection since data could also be transported via data carriers such as CDs, memory sticks, or the like.


### 8.4. Flashing ofTRK

The actual flashing of aTRKnew to a given UD is shown in Algorithm 5. It demands a valid new transponder TRKnew and authorization by OEM and OWN. Former either directly or delegated to SP using the credential introduced above, latter done by presenting a valid and linked TRKorig assumed to be solely accessible by OWN. If an online connection to OEM is available, the protocol can be performed by UD and OEM directly as described in Section 7, with SP only relaying communication.Algorithm 5:Indirect flashing protocol over a trusted mediator (no online connection to OEM).
Requirements(i) The initialization protocol has been completed successfully.(ii)UD has knowledge of VKOEM.(iii)SP has a valid trust key pair and has not reached the maximum quota N ofallowed flashing procedures.ProtocolStep  1: SP contacts UD and sends SigSKOEM(VKSP,VKSPTD,T,N) to UD.Step  2: UD verifies V(SigSKOEM(VKSP,VKSPTD,T,N),VKOEM)=!1and sends backSigSKUD(VKUD,VKSP) as an acknowledge.Step  3: OWN authorizes the start of a key flashing procedure by presentinga validTRKorig. UD authenticates TRKorig using the internallystoredVKTRKorig and a PKC authentication protocol.Step  4: SP sends the certified new key package SigSKSPTD(SigSKOEM(VKTRKnew,VKSP),VKUD) to UD.Step  5: UD verifies that V(SigSKSPTD(SSKOEM(VKTRKnew,VKSP),VKUD),VKSPTD)=!1 andV(SigSKOEM(VKTRKnew,VKSP),VKUD,VKOEM)=!1. Then the new transponder TRKnew can beactivated:TRKnew↦TRKorig. The protocol is completed by sending a DONE-message to SP.IfSP has to act as an offline mediator, the initialization protocol (Algorithm 4) has had to be successfully completed. From there on, the flashing protocol commences as shown in Algorithm 5 with SP contacting UD and sending the trust credentials that SP has received from OEM (Step  1). In Step  2, UD verifies these credentials using the OEM’s verification key that is already embedded in UD (Section 6.2.4). The verification key of the trusted key pair VKSPTD is stored temporarily for use in Step  6. As an acknowledge message, UD sends a self-signed packet to SP that includes its own public key as well as the standard public key of SP.SinceOWN has to authorize the flashing procedure he presents his credential in form of an original TRKorig already linked to UD. UD authenticates TRKorig by means of a public key authentication protocol (Step  3). Only if TRKorig has been successfully authenticated UD will accept a TRKnew being flashed into UD. In Step  4, SP sends the authorized data packet for the TRK to be flashed that it has received from the OEM during the second phase of the initialization procedure (Section 8.3). It is annotated with UD’s public key VKUD and additionally signed by SP using the trust key pair. That way, the TRKnew is bound to UD. To finalize the protocol, UD enforces the flashing policies in Step  5. First it verifies if the signature of SP is correct and has used the trust key pair. If that is the case, it verifies the correctness of the OEM's signature on the data packet for TRKnew. Since this data packet has been bound to UD, UD verifies if its own public key has been used to annotate VKTRKnew. Only a correctly annotated VKTRKnew will be accepted, all others are dismissed and will not be stored into UD.In the case of successful verification,UD accepts the new token TRKnew and adds  VKTRKnew to its internal list of linked tokens thus transforming TRKnew into a TRKorig. The correct and full flashing is then reported back to SP. Subsequently, SP will log this as a successful flashing procedure and decrement its internal counter for allowed flashing processes.


### 8.5. Entity Requirements

Regarding the proposed flashing protocols certain requirements for the entities' functionalities have to be satisfied. An overview is given in Table4. Data management is one of the key requirements in the protocol in the sense that public key data needs to be stored. Secure storage for delegated trust has some additional requirements such as intrusion detection to protect data from being altered in any way. At the same time, it is mandatory that this data is always changed correctly as demanded by the protocol. Also, the OEM’s public key needs to be firmly embedded into the entities and must not be altered in any way. Otherwise, the OEM cannot be identified correctly within the proposed protocols.Table 4
Entity requirements.
OEMSPUDTRKInitiate communication••Acknowledge communication••Generation of keypairs•••Signature generation•••Signature verification•••Datamanagement for suppliers•Datamanagement for user devices•Datamanagement for service points•Datamanagement forTRKs••Secure storage for delegated trust•Knowledge ofOEM's public key••


## 8.1. Mediator

Because a mediator has to partly replace theOEM during the flashing protocol and UD only allows TRKs to be flashed through a trustworthy source—namely the OEM—the mediator has to be enabled to act as a trustworthy entity [30]. For this, the OEM has to delegate trust to a SP, in order to enable UD to entrust SP enough to accept a flashing request from it. It has to be ensured that the security of the overall flashing protocol is not weakened. Every mediator (SP) is evaluated by the OEM for its trustworthiness. Assessment factors can also include nontechnical aspects such as political and cultural environment, legal issues, or business models. Based on this evaluation, trust credentials (see Section 8.2) are issued to each individual SP.To restrict access to the flashing capability ofSP, as might be necessary in order to comply with the flashing policies of OEM a separate authentication of employees (SPE) working at SP is suggested. Such authorization of SPE can be done, for example, via a password (knowledge) or by biometrical identification (physical property).


## 8.2. Service Point as Trusted Platform

AnSP constitutes a trusted platform as defined in [30] meaning that SP always acts as specified at any point in the protocol. At the same time, it needs to act reliably in order to enforce trust policies. Typically, an SP might reside in a hostile environment and can be accessible to malicious attackers. Therefore, some minimal functionalities of SP must be inherently secure and are encapsulated in a Trusted  Zone (see Figure 9) as follows:  (i)
generation of trust key pairs,(ii)
storage of private keys (SKSPTD and SKSP),(iii)
signature generation,(iv)
enforcement of Trust Policy.Figure 9
Service point as trusted platform.For all key pairs that are generated to be used as temporary trust keys, it has to be ensured that aSKSPTD is never communicated to another entity. Also, it has to be ensured that SKSPTD cannot be deducted from VKSPTD. This can be ensured with a proper key generation algorithm. Signing of messages has to be secure in order to prevent manipulation of signed data packets. This means that any signing operation is always done with the proper signing key residing in SP.The main point of the trusted platform is the enforcement of trust policies.SP is issued a temporal trust key pair (SKSPTD,VKSPTD) as will be described in Section 8.3. This key pair expires after a timepoint T or after a certain amount of flashing procedures N. Expiration is enforced from within the Trusted  Zone with a secure unforgeable counter that is keeping track of the number of flashing cycles. As soon as the counter value reaches N, the trust key pair is fully deleted and the counter is reset. SP also compares its system time TSP to T. If TSP≥T the trust key pair is also fully deleted.


## 8.3. Trust Delegation and TRKnew Authorization

To be able to perform a key flashing procedure without an active link toOEM, a local representative has to be empowered by the OEM to perform the flashing, assuming that UD trusts only the OEM to flash legit keys. This is done by presenting a credential to UD accounting that flashing is authorized by OEM. The exchange of this credential is denoted in the following as trust  delegation.Algorithm4 shows the protocol for instantiating a mediator that can flash a TRK into a UD. Steps  I.1 to I.4 detail the trust delegation to SP. First of all, SPE is authenticated by SP to prevent SP abusive operations. Afterwards, SP can connect to OEM and request a trust credential (Step  I.1).Algorithm 4:Initialization step for mediated key flashing.
Requirements(i)OEM has knowledge of VKSP and VKTRKMProtocolStep  I.1: SPE presents his credential CREDSPE and SP authenticates SPE.  After that SPis activated and communication toOEM is enabled.Step  I.2: SP creates a new key pair (SKSPTD,VKSPTD) and sends its ID together with the createdverification keyVKSPTD as a signed request [SigSKSP(VKSPTD),VKSP] for a trust credential to OEM.Step  I.3: OEM verifies that SP and the respective verification key VKSP  islisted in the internal database of trusted mediators and thatV(SigSKSP(VKSPTD),VKSP)=!1.In this caseOEM creates a trust delegation credential SigSKOEM(VKSPTD,VKSP,T,N) bound to SPwith timestampT and number of granted transactions N and sends it to SP.Step  I.4: SP receives SigSKOEM(VKSP,VKSPTD,T,N) and stores it in the trusted storage.This step completes the trust delegation for flashing.Step  II.1: For a number of TRKnew to be flashed, SP reads out the respective certifiedverification keysSigSKTRKM(VKTRKnew) and sends SigSKSP(SigSKTRKM(VKTRKnew)) to OEM.Step  II.2: OEM verifies that VKSP and VKTRKM are in the internaldatabase of trusted peers and thatV(SigSKSP(SigSKTRKM(VKTRKnew)),VKSP)=!1 andV(SigSKTRKM(VKTRKnew),VKTRKM)=!1. Afterwards OEM creates SigSKOEM(VKTRKnew,VKSP)and sends it toSP.Step  II.3: SP receives SigSKOEM(VKTRKnew,VKSP) and stores it in the trusted storage.This step completes the activation of the transponderTRKnew for flashing over SP.A trust credential consists of a cryptographic temporal trust key pair(SKSPTD,VKSPTD) with the public key VKSPTD being signed by OEM. Therefore, SP creates a fresh trust key pair. From this pair, SP sends the fresh verification key VKSPTD as well as its ID as a signed data packet to the OEM, while the secret key SKSPTD never leaves SP. The ID is the standard verification key VKSP of the service point (see Algorithm 4 Step  I.2). For ease of implementation, this can be replaced with a unique identifier that can then be matched by the OEM to the appropriate VKSP stored in an internal database.Using VKSP  OEM verifies the correctness of the data packet received. If SP is considered a trustworthy entity, that is, if it adheres to all of OEMs policies, OEM issues a trust credential. As shown in Step  I.3 (Algorithm 4) it comprises the verification key of the trust key pair, the standard verification key (VKSP) of SP, as well as a timestamp T, and a maximum transaction number N in an OEM signed packet. Through inclusion of VKSP, OEM binds the trust key VKSPTD to SP. Later, this binding will be verified by UD (see Section 8.4). A trust key pair is only valid for a limited time and limited number of flashing operations after which it is deleted by SP. Step  I.4 concludes the trust delegation phase with SP storing the OEM-signed packet in trusted storage for later use in the actual flashing procedure (Section 8.4).In order to flash aTRKnew, the transponder needs to be authorized by OEM. The second part (Steps  II.1–Step  II.3) of the protocol shown in Algorithm 4 accomplishes this for a single TRKnew. If more than one TRK shall be set up for flashing, this part of the protocol is rerun for each additional TRKnew. SP reads out the verification key of TRK that previously has been certified and signed by TRKM. SP send this key as a self-signed message as shown in Step  II.1 to OEM for authorization. In Step  II.2, OEM verifies both signatures and ensures that TRKM as well as SP are trusted peers. If this is the case, OEM forms a data packet comprising the public key of TRKnew as well as the standard public key of SP and sends it as a signed message to SP. This message effectively binds TRKnew to SP, thus enabling solely SP to flash TRKnew into UD later on. The second part of the protocol in Algorithm 4 is finalized in Step  II.3 by SP storing the received, signed message in its trusted module.Only a limited number of authorizedTRKs can be stored at any given point in time. As soon as a TRK has been authorized by the OEM, physical access to the TRK needs to be controlled. The authorization process of TRKs is the only step that demands a data connection between SP and OEM. This does not necessarily need to be an online connection since data could also be transported via data carriers such as CDs, memory sticks, or the like.


## 8.4. Flashing ofTRK

The actual flashing of aTRKnew to a given UD is shown in Algorithm 5. It demands a valid new transponder TRKnew and authorization by OEM and OWN. Former either directly or delegated to SP using the credential introduced above, latter done by presenting a valid and linked TRKorig assumed to be solely accessible by OWN. If an online connection to OEM is available, the protocol can be performed by UD and OEM directly as described in Section 7, with SP only relaying communication.Algorithm 5:Indirect flashing protocol over a trusted mediator (no online connection to OEM).
Requirements(i) The initialization protocol has been completed successfully.(ii)UD has knowledge of VKOEM.(iii)SP has a valid trust key pair and has not reached the maximum quota N ofallowed flashing procedures.ProtocolStep  1: SP contacts UD and sends SigSKOEM(VKSP,VKSPTD,T,N) to UD.Step  2: UD verifies V(SigSKOEM(VKSP,VKSPTD,T,N),VKOEM)=!1and sends backSigSKUD(VKUD,VKSP) as an acknowledge.Step  3: OWN authorizes the start of a key flashing procedure by presentinga validTRKorig. UD authenticates TRKorig using the internallystoredVKTRKorig and a PKC authentication protocol.Step  4: SP sends the certified new key package SigSKSPTD(SigSKOEM(VKTRKnew,VKSP),VKUD) to UD.Step  5: UD verifies that V(SigSKSPTD(SSKOEM(VKTRKnew,VKSP),VKUD),VKSPTD)=!1 andV(SigSKOEM(VKTRKnew,VKSP),VKUD,VKOEM)=!1. Then the new transponder TRKnew can beactivated:TRKnew↦TRKorig. The protocol is completed by sending a DONE-message to SP.IfSP has to act as an offline mediator, the initialization protocol (Algorithm 4) has had to be successfully completed. From there on, the flashing protocol commences as shown in Algorithm 5 with SP contacting UD and sending the trust credentials that SP has received from OEM (Step  1). In Step  2, UD verifies these credentials using the OEM’s verification key that is already embedded in UD (Section 6.2.4). The verification key of the trusted key pair VKSPTD is stored temporarily for use in Step  6. As an acknowledge message, UD sends a self-signed packet to SP that includes its own public key as well as the standard public key of SP.SinceOWN has to authorize the flashing procedure he presents his credential in form of an original TRKorig already linked to UD. UD authenticates TRKorig by means of a public key authentication protocol (Step  3). Only if TRKorig has been successfully authenticated UD will accept a TRKnew being flashed into UD. In Step  4, SP sends the authorized data packet for the TRK to be flashed that it has received from the OEM during the second phase of the initialization procedure (Section 8.3). It is annotated with UD’s public key VKUD and additionally signed by SP using the trust key pair. That way, the TRKnew is bound to UD. To finalize the protocol, UD enforces the flashing policies in Step  5. First it verifies if the signature of SP is correct and has used the trust key pair. If that is the case, it verifies the correctness of the OEM's signature on the data packet for TRKnew. Since this data packet has been bound to UD, UD verifies if its own public key has been used to annotate VKTRKnew. Only a correctly annotated VKTRKnew will be accepted, all others are dismissed and will not be stored into UD.In the case of successful verification,UD accepts the new token TRKnew and adds  VKTRKnew to its internal list of linked tokens thus transforming TRKnew into a TRKorig. The correct and full flashing is then reported back to SP. Subsequently, SP will log this as a successful flashing procedure and decrement its internal counter for allowed flashing processes.


## 8.5. Entity Requirements

Regarding the proposed flashing protocols certain requirements for the entities' functionalities have to be satisfied. An overview is given in Table4. Data management is one of the key requirements in the protocol in the sense that public key data needs to be stored. Secure storage for delegated trust has some additional requirements such as intrusion detection to protect data from being altered in any way. At the same time, it is mandatory that this data is always changed correctly as demanded by the protocol. Also, the OEM’s public key needs to be firmly embedded into the entities and must not be altered in any way. Otherwise, the OEM cannot be identified correctly within the proposed protocols.Table 4
Entity requirements.
OEMSPUDTRKInitiate communication••Acknowledge communication••Generation of keypairs•••Signature generation•••Signature verification•••Datamanagement for suppliers•Datamanagement for user devices•Datamanagement for service points•Datamanagement forTRKs••Secure storage for delegated trust•Knowledge ofOEM's public key••


## 9. Implementation

The protocol has been implemented as a proof of concept in a prototypical setup based on a network of standard PCs representingOEM and SP (see Figure 10). Furthermore, Digilent Spartan3E  Starter  Boards with a Xilinx XC3S500 FPGA represent TRKs and UDs. TRK, SP, and UD have to be connected when flashing the key. The OEM connection needs to be established anytime prior to the flashing according to the proposed protocol and is connected via TCP/IP to the SP.Figure 10
Component interaction.All other communication is done over RS232 interfaces that are available both on PC and the FPGA boards. These can be substituted for other communication structures if needed, that is, wireless transmitters.


### 9.1. Choice of Cryptographic Primitives

The proposed key flashing concept demands asymmetric encryption and a cryptographic hash function. RSA [31] is chosen for encryption and signing, SHA1 [32] for hash functionality. Both schemes are today’s standard and have not been broken yet, but can be substituted in our implementation for more secure schemes such as HECC if needed. RSA as well as SHA1 implementations are freely available as software and hardware modules for numerous platforms. RSA parameters used in the prototype are given in Table 5.Table 5
Parameters for RSA-System.
Key length1024 BitExponent216+1 (65537)Padding schemePKCS#1 v1.5Signature schemePKCS#1 v1.5Hashing scheme used for signingSHA1All signatures in our context are SHA1-hash values of data that has been encrypted according to the signing scheme PKCS#1 v1.5 [33]. Such a signature has a length of 128 Byte when using a key length of 1024 bit and hash values of 160 bit length.


### 9.2. OEM/Service Point-Software Platform

Both componentsOEM and SP have been implemented on a standard PC in software under the  .NET framework version 2.0 [34] using C#. The  .NET framework provides the Berkeley Socket-interface for communication over the PC’s serial interface. It also includes the Cryptography-namespace providing all needed cryptographic primitives including hash functions and a random number generator that are based on the FIPS-140-1 [35] certified Windows CryptoAPI. The software is modularized to enable easy exchange of functional blocks and seamless replacement of algorithms. Software modules communicate only over defined interfaces to enable full functional encapsulation. For ease of usage, a graphical user interface (GUI) is included as well in both entities.


### 9.3. Transponder/UserDevice—FPGA platform

The targeted user device is an FPGA. To ease reuse of functionalities the exemplaryTRK has been implemented on FPGA as well, but can also be integrated into a smart card or RFID chip as long as the appropriate cryptographic primitives are provided.In the prototypical setup, we used a MicroBlaze-based ECU (see Figure3) for both UD and TRK. We omitted the coprocessor and implemented all functionality on the MicroBlaze including cryptographic functions. Hardware peripherals such as an LCD controller have been integrated for debugging purposes. To enable handling of big numbers, as are used in the cryptographic functions of the protocol, the libraries libtommath [36] and libtomcrypt [37] are used. Only necessary components have been extracted from those libraries and are integrated into TRK and UD.


### 9.4. Resource Usage

The resource usage of the componentsOEM and SP are very similar, since almost identical functional software blocks are used in both. Table 6 gives an exemplary overview of the lines of code of the OEM implementation. The memory footprint of the compiled OEM implementation is 129 KB (139 KB for the SP implementation). At start up, 15400 KB of main memory is used. The execution times for RSA- and SHA1-operations were measured on a PC (2 GHz, 1024 MB RAM) and are all in the range of milliseconds.Table 6
Properties ofOEM component.
ModuleLines of codePercentageMain application123441.77GUI2648.94Cryptography38513.03Interaction38312.97Communication54518.45Data management1434.84Total2954100Resource usage of the FPGA-based componentsUD and TRK are given in Table 7. By implementing all functionality on a MicroBlaze softcore, the hardware usage is quite moderate. On the other hand, the software footprint is 295 KB for the UD implementation, due to the nonoptimized memory usage of the crypto library.Table 7
FPGA resources.
Slices1.791 of 4.656 (38%)Slices: FlipFlops uses1.590 of 9.312 (17%)Slices: LUTs used1.941 of 9.312 (20%)BlockRAMs used16 of 20 (80%)Equivalent logic cells1.135.468Minimal clock period18,777 nsMaximum clock frequency53,257 MHzShown in Table8 are the execution times of the diverse protocol instances. The duration of parts of the protocol that are based solely on OEM and SP is in the area of few milliseconds. As soon as mobile devices (UD, TRK) process parts of the protocol, speed is declining since all crypto operations are currently carried out on an embedded microcontroller. Main factor here is the RSA decryption operation. With appropriate hardware support, choice of parameters, cryptosystem, and substantial speedups can be achieved as shown in [16].Table 8
Protocol execution times.
Protocol instanceDuration (min:sec.ms)ReadOut of transponder01:32.000Mutual authentication ofUD and TRK03:14.000Direct keyflashingKeyflashing to transponder byOEM23:50.000Keyflashing by servicePointDelegation of trustOEM to SP00:00.350Transponderdelegation00:00.250Keyflashing to transponder bySP12:43.000


## 9.1. Choice of Cryptographic Primitives

The proposed key flashing concept demands asymmetric encryption and a cryptographic hash function. RSA [31] is chosen for encryption and signing, SHA1 [32] for hash functionality. Both schemes are today’s standard and have not been broken yet, but can be substituted in our implementation for more secure schemes such as HECC if needed. RSA as well as SHA1 implementations are freely available as software and hardware modules for numerous platforms. RSA parameters used in the prototype are given in Table 5.Table 5
Parameters for RSA-System.
Key length1024 BitExponent216+1 (65537)Padding schemePKCS#1 v1.5Signature schemePKCS#1 v1.5Hashing scheme used for signingSHA1All signatures in our context are SHA1-hash values of data that has been encrypted according to the signing scheme PKCS#1 v1.5 [33]. Such a signature has a length of 128 Byte when using a key length of 1024 bit and hash values of 160 bit length.


## 9.2. OEM/Service Point-Software Platform

Both componentsOEM and SP have been implemented on a standard PC in software under the  .NET framework version 2.0 [34] using C#. The  .NET framework provides the Berkeley Socket-interface for communication over the PC’s serial interface. It also includes the Cryptography-namespace providing all needed cryptographic primitives including hash functions and a random number generator that are based on the FIPS-140-1 [35] certified Windows CryptoAPI. The software is modularized to enable easy exchange of functional blocks and seamless replacement of algorithms. Software modules communicate only over defined interfaces to enable full functional encapsulation. For ease of usage, a graphical user interface (GUI) is included as well in both entities.


## 9.3. Transponder/UserDevice—FPGA platform

The targeted user device is an FPGA. To ease reuse of functionalities the exemplaryTRK has been implemented on FPGA as well, but can also be integrated into a smart card or RFID chip as long as the appropriate cryptographic primitives are provided.In the prototypical setup, we used a MicroBlaze-based ECU (see Figure3) for both UD and TRK. We omitted the coprocessor and implemented all functionality on the MicroBlaze including cryptographic functions. Hardware peripherals such as an LCD controller have been integrated for debugging purposes. To enable handling of big numbers, as are used in the cryptographic functions of the protocol, the libraries libtommath [36] and libtomcrypt [37] are used. Only necessary components have been extracted from those libraries and are integrated into TRK and UD.


## 9.4. Resource Usage

The resource usage of the componentsOEM and SP are very similar, since almost identical functional software blocks are used in both. Table 6 gives an exemplary overview of the lines of code of the OEM implementation. The memory footprint of the compiled OEM implementation is 129 KB (139 KB for the SP implementation). At start up, 15400 KB of main memory is used. The execution times for RSA- and SHA1-operations were measured on a PC (2 GHz, 1024 MB RAM) and are all in the range of milliseconds.Table 6
Properties ofOEM component.
ModuleLines of codePercentageMain application123441.77GUI2648.94Cryptography38513.03Interaction38312.97Communication54518.45Data management1434.84Total2954100Resource usage of the FPGA-based componentsUD and TRK are given in Table 7. By implementing all functionality on a MicroBlaze softcore, the hardware usage is quite moderate. On the other hand, the software footprint is 295 KB for the UD implementation, due to the nonoptimized memory usage of the crypto library.Table 7
FPGA resources.
Slices1.791 of 4.656 (38%)Slices: FlipFlops uses1.590 of 9.312 (17%)Slices: LUTs used1.941 of 9.312 (20%)BlockRAMs used16 of 20 (80%)Equivalent logic cells1.135.468Minimal clock period18,777 nsMaximum clock frequency53,257 MHzShown in Table8 are the execution times of the diverse protocol instances. The duration of parts of the protocol that are based solely on OEM and SP is in the area of few milliseconds. As soon as mobile devices (UD, TRK) process parts of the protocol, speed is declining since all crypto operations are currently carried out on an embedded microcontroller. Main factor here is the RSA decryption operation. With appropriate hardware support, choice of parameters, cryptosystem, and substantial speedups can be achieved as shown in [16].Table 8
Protocol execution times.
Protocol instanceDuration (min:sec.ms)ReadOut of transponder01:32.000Mutual authentication ofUD and TRK03:14.000Direct keyflashingKeyflashing to transponder byOEM23:50.000Keyflashing by servicePointDelegation of trustOEM to SP00:00.350Transponderdelegation00:00.250Keyflashing to transponder bySP12:43.000


## 10. Security Analysis

Looking at the security of the proposed concept some points can be identified where security relies on policies and implementing rules while other issues are covered by design.Using PKC primitives and trusted computing approaches, the protocol ensures confidentiality of secret keys and mutual authentication ofSP and OEM, OWN and UD, SP and UD, SP, and SPE. Due to the necessity of online independence, there are some assumptions that have to be made to guarantee security. This is mainly the trustworthiness of the SP in combination with the physical protection of any authorized TRKnew and all TRKorig.If these assumptions are broken, for example, by theft of authorizedTRK, the corresponding SP and the SPE password, unauthorized flashing may be possible. As countermeasures, the usage of the protocol can be adapted to dilute effects of such events. So, the number of allowed authorized TRK should be as low as possible and the SP should be implemented using trusted components and based on a trusted platform. Secrets should be especially protected against misuse by a physical attacker.There certainly is a tradeoff between security and usability of the flashing scheme, since the protocol has been designed for real-world implementation.


### 10.1. Security of Direct Flashing Scenario

In the flashing scenario with no mediator (Section7), an illegal flashing of TRK is not possible. The flashing procedure is authorized through the OEM directly. Only the OEM is considered trustworthy enough to accept flashing commands from. By verifying the signature on a TRK's key, it can be checked if a certain TRK has been manufactured by a certified supplier TRKM or not. Certification policy ensures that such a TRK has a unique ID, unique cryptographic keys, and secret key material is solely known to the TRK itself and is nowhere else available or reproducible.Verifying the signature ofUD and the mutual authentication phase of OEM and UD, OEM can be sure that a UD is targeted in the flashing procedure that has been manufactured by OEM. In turn, UD can be sure that its communication partner is the OEM.Binding the key material to be flashed to a dedicatedUD by incorporating a mutual signature of the key material enforces that a certain transponder is flashed only into a single UD. Also, it can be enforced that the packet containing the VKTRK is only used for a single flashing procedure, thus countermeasuring replay attacks. Neither unrecognized mutation of dedicated parts of this communication packet is possible, nor forging the signatures on data, due to the security assumptions of the cryptographic primitives. No confidential information is included in any communication packet. By activating the VKTRK inside the UD only after a successful transmission without errors, it is ensured that the TRK has no previous utility value. Readingout the TRK’s VKTRK has no benefit to an attacker. Therefore, a TRK has not to be stored away safely before linking it to a UD. Loss of an unlinked TRK does also not lead to any security issues.If all entities involved in the flashing procedure adhere to the protocol, abolish all data resulting from a disrupted flashing procedure, and implement all cryptographic primitives securely, an attacker is not able to carry out an illegal flashing procedure.


### 10.2. Security of Mediator Flashing Scenario

In the flashing scenario involving a mediator as described in Section8, the flashing procedure is legitimated through OWN directly by presenting a second TRK that is already linked to UD during the last phase of the flashing process. A UD receiving the final communication packet carrying the VKTRK to be flashed can verify if the sender of the packet is legit and trustworthy by checking the signatures of the OEM as well as checking the trust credentials of the SP. Therefore, the UD directly enforces the policy that only certified parties may flash a VKTRK by dismissing any received VKTRK as soon as a invalid signature is detected.Usage ofSP through a SPE is restricted and protected by appropriate access control, so no malicious outsider can flash a VKTRK. Since trust has to be redelegated after a certain time or amount of flashing procedures, it is not possible to haphazardly flash TRKs.No sensitive data is transmitted during the flashing protocol that might compromise the system’s security. It seems that the data packet sent byOEM to SP might be highly sensitive, but even if an attacker were able to access the keypair forming the delegation of trust, it would not be possible to authenticate new TRK’s with the OEM since this demands knowledge of SKSP known only to SP itself. TRK's already authenticated by the OEM can also not be flashed into a UD, since it will be impossible for an attacker to correctly sign the data packet containing the TRK’s public key, because the signing key SKSPTD is also known solely by SP.In this second flashing scenario, it is again ensured that theTRK has no previous utility value before finally linking it to a UD in the final step of the protocol. The loss of of an unlinked TRK does not lead to any security issues as long as it has not been authorized by the OEM. Therefore all unauthorized TRK do not pose a security risk. Authorized TRKs do need to be stored away securely since they can be flashed into a UD, but only with the SP that is linked to the TRK. As before, no attacker may be able to carry out an illegal flashing procedure as long as all entities involved in the flashing procedure adhere to the protocol, abolish all data resulting from a disrupted flashing procedure, and implement all cryptographic primitives securely.


### 10.3. Potential Risks

Although the technical aspects of the flashing protocols can be secured against manipulation and tampering, there are still some risks involved resulting from nontechnical aspects. A malicious insider such as aSPE might be able to gain access to the SP, an authenticated TRKnew as well as a UD and the corresponding TRKorig. Only if SPE has access to all aforementioned entities, then it is possible for him to flash TRKnew into UD, unknown to the legal owner OWN. Although such malicious misbehavior of SPE cannot be prohibited, it can at least be traced by logging all activity inside the SP.A similar risk is faulty implementations of security primitives that are used in the protocol leading to a leak of secret cryptographic keys, thus enabling an attacker to impersonate an entity. The two main concerns regarding security leaks lie in the nontechnical aspects of the flashing protocol through mediators.


#### 10.3.1. Social Engineering

Since the flashing of keys involves human interaction, this can offer an entry point for an attacker using social engineering [38–40]. A conceivable entry point is the SPE. If an attacker is able to extract the credentials from SPE, he can gain access to SP and therefore flash TRKs into any user device of OEM. This is a widely known issue in security systems in general that can only be countermeasured by proper training of SPE to enhance security awareness. Any misuse of the system through an SPE can be tracked if a secure log of all activities is provided within the trusted part of SP. As soon as misuse is detected, the trust delegation to SP can be revoked by OEM through not reissuing a trust keypair. Therefore, damage can be limited to flashing of the TRKnew already prepared for introduction into a UD.Since the flashing scheme demands for authentication of the procedure throughOWN, it is necessary to ensure the security of the second TRKorig to be presented at the final stage of the process. If the second TRKorig is in possession of an attacker and additionally the attacker has access to SP, he is able to flash an additional TRK into one UD. This attack is limited to a single UD, thus representing a fairly small risk, which on the other hand can easily be countermeasured.


#### 10.3.2. SP Theft Scenario

If anSP carrying a valid trust key falls into the hands of a malicious attacker, the credential of SPE must also be known to the attacker in order to use SP to flash TRKs. Additionally, it is mandatory that the attacker also has a TRKnew in his possession that has already been certified by OEM. Additionally, TRKnew has to be bound to the stolen SP. If no such TRKnew is available, the system is not compromised. Even in case of such an aggressive attack the risk to the overall system is minimized, since only a very limited number of TRKs is flashable and a trust revocation can be carried out.The risk level for such a scenario can be adapted through appropriate policies based on risk assessment throughOEM. The most aggressive policy is not to allow flashing through a mediator. A minimal risk policy is to only have a single TRK on location that can be flashed into a UD. Only after it has been flashed successfully, does the OEM authenticate another TRK. While providing higher security, such restrictive policies will naturally inhibit usability.


## 10.1. Security of Direct Flashing Scenario

In the flashing scenario with no mediator (Section7), an illegal flashing of TRK is not possible. The flashing procedure is authorized through the OEM directly. Only the OEM is considered trustworthy enough to accept flashing commands from. By verifying the signature on a TRK's key, it can be checked if a certain TRK has been manufactured by a certified supplier TRKM or not. Certification policy ensures that such a TRK has a unique ID, unique cryptographic keys, and secret key material is solely known to the TRK itself and is nowhere else available or reproducible.Verifying the signature ofUD and the mutual authentication phase of OEM and UD, OEM can be sure that a UD is targeted in the flashing procedure that has been manufactured by OEM. In turn, UD can be sure that its communication partner is the OEM.Binding the key material to be flashed to a dedicatedUD by incorporating a mutual signature of the key material enforces that a certain transponder is flashed only into a single UD. Also, it can be enforced that the packet containing the VKTRK is only used for a single flashing procedure, thus countermeasuring replay attacks. Neither unrecognized mutation of dedicated parts of this communication packet is possible, nor forging the signatures on data, due to the security assumptions of the cryptographic primitives. No confidential information is included in any communication packet. By activating the VKTRK inside the UD only after a successful transmission without errors, it is ensured that the TRK has no previous utility value. Readingout the TRK’s VKTRK has no benefit to an attacker. Therefore, a TRK has not to be stored away safely before linking it to a UD. Loss of an unlinked TRK does also not lead to any security issues.If all entities involved in the flashing procedure adhere to the protocol, abolish all data resulting from a disrupted flashing procedure, and implement all cryptographic primitives securely, an attacker is not able to carry out an illegal flashing procedure.


## 10.2. Security of Mediator Flashing Scenario

In the flashing scenario involving a mediator as described in Section8, the flashing procedure is legitimated through OWN directly by presenting a second TRK that is already linked to UD during the last phase of the flashing process. A UD receiving the final communication packet carrying the VKTRK to be flashed can verify if the sender of the packet is legit and trustworthy by checking the signatures of the OEM as well as checking the trust credentials of the SP. Therefore, the UD directly enforces the policy that only certified parties may flash a VKTRK by dismissing any received VKTRK as soon as a invalid signature is detected.Usage ofSP through a SPE is restricted and protected by appropriate access control, so no malicious outsider can flash a VKTRK. Since trust has to be redelegated after a certain time or amount of flashing procedures, it is not possible to haphazardly flash TRKs.No sensitive data is transmitted during the flashing protocol that might compromise the system’s security. It seems that the data packet sent byOEM to SP might be highly sensitive, but even if an attacker were able to access the keypair forming the delegation of trust, it would not be possible to authenticate new TRK’s with the OEM since this demands knowledge of SKSP known only to SP itself. TRK's already authenticated by the OEM can also not be flashed into a UD, since it will be impossible for an attacker to correctly sign the data packet containing the TRK’s public key, because the signing key SKSPTD is also known solely by SP.In this second flashing scenario, it is again ensured that theTRK has no previous utility value before finally linking it to a UD in the final step of the protocol. The loss of of an unlinked TRK does not lead to any security issues as long as it has not been authorized by the OEM. Therefore all unauthorized TRK do not pose a security risk. Authorized TRKs do need to be stored away securely since they can be flashed into a UD, but only with the SP that is linked to the TRK. As before, no attacker may be able to carry out an illegal flashing procedure as long as all entities involved in the flashing procedure adhere to the protocol, abolish all data resulting from a disrupted flashing procedure, and implement all cryptographic primitives securely.


## 10.3. Potential Risks

Although the technical aspects of the flashing protocols can be secured against manipulation and tampering, there are still some risks involved resulting from nontechnical aspects. A malicious insider such as aSPE might be able to gain access to the SP, an authenticated TRKnew as well as a UD and the corresponding TRKorig. Only if SPE has access to all aforementioned entities, then it is possible for him to flash TRKnew into UD, unknown to the legal owner OWN. Although such malicious misbehavior of SPE cannot be prohibited, it can at least be traced by logging all activity inside the SP.A similar risk is faulty implementations of security primitives that are used in the protocol leading to a leak of secret cryptographic keys, thus enabling an attacker to impersonate an entity. The two main concerns regarding security leaks lie in the nontechnical aspects of the flashing protocol through mediators.


### 10.3.1. Social Engineering

Since the flashing of keys involves human interaction, this can offer an entry point for an attacker using social engineering [38–40]. A conceivable entry point is the SPE. If an attacker is able to extract the credentials from SPE, he can gain access to SP and therefore flash TRKs into any user device of OEM. This is a widely known issue in security systems in general that can only be countermeasured by proper training of SPE to enhance security awareness. Any misuse of the system through an SPE can be tracked if a secure log of all activities is provided within the trusted part of SP. As soon as misuse is detected, the trust delegation to SP can be revoked by OEM through not reissuing a trust keypair. Therefore, damage can be limited to flashing of the TRKnew already prepared for introduction into a UD.Since the flashing scheme demands for authentication of the procedure throughOWN, it is necessary to ensure the security of the second TRKorig to be presented at the final stage of the process. If the second TRKorig is in possession of an attacker and additionally the attacker has access to SP, he is able to flash an additional TRK into one UD. This attack is limited to a single UD, thus representing a fairly small risk, which on the other hand can easily be countermeasured.


### 10.3.2. SP Theft Scenario

If anSP carrying a valid trust key falls into the hands of a malicious attacker, the credential of SPE must also be known to the attacker in order to use SP to flash TRKs. Additionally, it is mandatory that the attacker also has a TRKnew in his possession that has already been certified by OEM. Additionally, TRKnew has to be bound to the stolen SP. If no such TRKnew is available, the system is not compromised. Even in case of such an aggressive attack the risk to the overall system is minimized, since only a very limited number of TRKs is flashable and a trust revocation can be carried out.The risk level for such a scenario can be adapted through appropriate policies based on risk assessment throughOEM. The most aggressive policy is not to allow flashing through a mediator. A minimal risk policy is to only have a single TRK on location that can be flashed into a UD. Only after it has been flashed successfully, does the OEM authenticate another TRK. While providing higher security, such restrictive policies will naturally inhibit usability.


## 10.3.1. Social Engineering

Since the flashing of keys involves human interaction, this can offer an entry point for an attacker using social engineering [38–40]. A conceivable entry point is the SPE. If an attacker is able to extract the credentials from SPE, he can gain access to SP and therefore flash TRKs into any user device of OEM. This is a widely known issue in security systems in general that can only be countermeasured by proper training of SPE to enhance security awareness. Any misuse of the system through an SPE can be tracked if a secure log of all activities is provided within the trusted part of SP. As soon as misuse is detected, the trust delegation to SP can be revoked by OEM through not reissuing a trust keypair. Therefore, damage can be limited to flashing of the TRKnew already prepared for introduction into a UD.Since the flashing scheme demands for authentication of the procedure throughOWN, it is necessary to ensure the security of the second TRKorig to be presented at the final stage of the process. If the second TRKorig is in possession of an attacker and additionally the attacker has access to SP, he is able to flash an additional TRK into one UD. This attack is limited to a single UD, thus representing a fairly small risk, which on the other hand can easily be countermeasured.


## 10.3.2. SP Theft Scenario

If anSP carrying a valid trust key falls into the hands of a malicious attacker, the credential of SPE must also be known to the attacker in order to use SP to flash TRKs. Additionally, it is mandatory that the attacker also has a TRKnew in his possession that has already been certified by OEM. Additionally, TRKnew has to be bound to the stolen SP. If no such TRKnew is available, the system is not compromised. Even in case of such an aggressive attack the risk to the overall system is minimized, since only a very limited number of TRKs is flashable and a trust revocation can be carried out.The risk level for such a scenario can be adapted through appropriate policies based on risk assessment throughOEM. The most aggressive policy is not to allow flashing through a mediator. A minimal risk policy is to only have a single TRK on location that can be flashed into a UD. Only after it has been flashed successfully, does the OEM authenticate another TRK. While providing higher security, such restrictive policies will naturally inhibit usability.


## 11. Conclusions and Future Work

Access control systems are an important part in many systems such as vehicles or expensive machinery. Authentication protocols based on Public Key Cryptography offer advantages in logistics and key handling. These protocols are computationally very expensive but can be accelerated in hardware. In this paper, we presented a high-speed crypto architecture based on FPGA for fast authentication protocols based on HECC. Exploiting the properties of PKC, we introduced a scheme for pairing user devices (UD) and transponder tokens (TRK) by flashing public keys into UD. Compared to current key flashing procedures, our proposed protocol eliminates some logistic issues. TRKs do not have to be physically stored securely in SP any more. Also, shipment of TRKs does not have to be secured physically. Today OEM has to fully trust an SP to flash TRKs in the field. With our protocol the amount of trust in an SP can now be reduced to allow for risk management.Security of the system is guaranteed by appropriate policy enforcement and usage of secure cryptographic primitives. No online connection is mandatory for linking a new transponder (TRK) for user authentication to a user device (UD). This makes it very practical for scenarios if TRK's have to be replaced in the field with no intact communication infrastructure. It is applicable for a variety of embedded systems that need to implement and enforce access or usage restrictions in the field. We have shown the portability of the concept to non-FPGA platforms by implementing the protocol as a proof-of-concept using a combination of PC-based and FGPA-based protocol participants.Flashing speed is of utmost importance in real-world implementation. To make allowance for a real world integration of the proposed flashing schemes, optimization is needed regarding usage and speed of the computational units involved. In the current prototype, the MicroBlaze processor has been used for simplicity and to show that the protocol can already be easily deployed in microprocessor driven embedded system such as the automotive domain. With the coprocessing unit in Section7, very short computation times are achieved, and on a public key cryptosystem with a high security level than RSA. Adapting this system to the complete flashing scheme is target of future work and promises dramatic acceleration of the entire key flashing procedure.One crucial point is the protection of theTRK’s public key stored in the UD against physical attackers. Means to countermeasure attacks that might alter stored keys on a physical level need to be investigated in the future.



---

*Source: 820454-2011-04-12.xml*