# Towards Electrical, Integrated Implementations of SIMPL Systems

Ulrich Rührmair, Qingqing Chen, Martin Stutzmann, Paolo Lugli, Ulf Schlichtmann, György Csaba

► To cite this version:

Ulrich Rührmair, Qingqing Chen, Martin Stutzmann, Paolo Lugli, Ulf Schlichtmann, et al. Towards Electrical, Integrated Implementations of SIMPL Systems. 4th IFIP WG 11.2 International Workshop on Information Security Theory and Practices: Security and Privacy of Pervasive Systems and Smart Devices (WISTP), Apr 2010, Passau, Germany. pp.277-292, 10.1007/978-3-642-12368-9_22. hal-01056078

HAL Id: hal-01056078

https://inria.hal.science/hal-01056078

Submitted on 14 Aug 2014

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Towards Electrical, Integrated Implementations of SIMPL Systems

Ulrich Rührmair *, Qingqing Chen †, ‡, Martin Stutzmann ◦, Paolo Lugli ‡, Ulf Schlichtmann †, and György Csaba ‡

* Computer Science Department, † Institute for Electronic Design Automation,
‡ Institute for Nanoelectronics, ◦ Walter Schottky Institute
TU München, Germany

ruehrmai@in.tum.de, stutz@wsi.de,

{qingqing.chen,lugli,ulf.schlichtmann,csaba}@tum.de

http://www.pcp.in.tum.de

**Abstract.** This paper discusses strategies for the electrical, integrated imple-
mentation of a novel security tool termed SIMPL system, which was introduced
in [1]. SIMPL systems are a public key version of Physical Unclonable Func-
tions (PUFs). Like a PUF, each SIMPL system $S$ is physically unique and non-
reproducible, and implements an individual function $F_S$. In opposition to a PUF,
every SIMPL system $S$ possesses a publicly known numerical description $D(S)$,
which allows its digital simulation and prediction. However, any such simulation
must work at a detectably lower speed than the real-time behavior of $S$. As ar-
gued in [1], SIMPL systems have practicality and security advantages over PUFs,
Certificates of Authenticity (COAs), Physically Obfuscated Keys (POKs), and
also over standard mathematical cryptotechniques. This manuscript focuses on
electrical, integrated realizations of SIMPL systems, and proposes two potential
candidates: SIMPL systems derived from special SRAM-architectures (so-called
"skew designs" of SRAM cells), and implementations based on analog comput-
ing arrays called Cellular Non-Linear Networks (CNNs).

**Key words:** Physical Cryptography, Physical Unclonable Functions, SIMPL Systems, Public Key Systems

# 1 Introduction

Physical Unclonable Functions (PUFs) are a relatively young, emerging cryptographic primitive [2] [3] [4] [5] [6] [7]. However, one potential downside of PUF-based protocols is that they usually require a previously shared piece of information (typically some challenge-response-pairs) that was established in a joint set-up phase between the communicants. Alternatively, an online connection to a trusted authority at the time of the protocol execution must be employed. In this particular structural aspect, PUFs are resembling of classical private key systems.

In this paper, we are concerned with an alternative security tool called SIMPL systems, which is a public key version of standard PUFs. SIMPL systems have been introduced in [1]. The acronym SIMPL stands for "SIMulation Possible, but Laborious", and
hints at the critical security feature of these structures. A physical system $S$ is called a SIMPL system if the following holds:

1. It is possible for everyone to numerically simulate and, thus, to predict the physical behaviour of $S$ with very high accuracy. The basis of the simulation is an individual description $D(S)$ of $S$, and a generic simulation algorithm *Sim*, which are both publicly known.

2. Any sufficiently accurate numerical simulation — as well as any arbitrary physical emulation of $S$ — is slower than the real-time behavior of $S$. Determining the system's behavior by an actual measurement on the original system $S$ works detectably quicker than any other approach.

3. It is difficult to physically reproduce or clone $S$.

Put together in one sentence, the holder of a SIMPL system $S$ can compute a publicly known, publicly computable individual function $F_S$ faster than anyone else. Applying the familiar public key terminology to this situation, one could state that the numeric description $D(S)$ essentially serves as a public key, while the physical system $S$ constitutes an equivalent to a private key. This “private key”, however, is a physically irreproducible structure, which contains no secret information at all. This leads to several significant security advantages, which have been discussed in [1].

One critical question is certainly how SIMPL systems can be implemented in practice. We suggest two variants based on integrated electrical circuits in this publication: Firstly, special SRAM-memories based on a newly developed “skew” design, which leads to fuzzy memory cell behavior at quickly varied operational voltages. Secondly, we propose analog circuits known as Cellular Non-Linear Networks (CNN), whose cells evolve over time in an analog, highly parallel fashion. This can help them to outperform classical architectures on certain computational tasks, as is required from SIMPL systems.

*Organization of the Paper.* The rest of this manuscript is organized as follows: In section 2 we cite and discuss the formal specifications of SIMPL systems of [1]. Section 3 provides one example protocol and briefly discusses applications and advantages of SIMPL systems. In section 4 we treat the implementation of SIMPL systems by Cellular Non-Linear Networks. Section 5 introduces SIMPL systems based on special SRAM architectures. We conclude the paper in section 6.

## 2 SIMPL Systems

The following specification of SIMPL systems has been provided in [1].

**Specification 1** ($(t_C, t_{Ph}, \epsilon)$-SIMPL Systems). Let $S$ be a physical system mapping challenges $C_i$ to responses $R_i$, with $C$ denoting the finite set of all possible challenges. Let furthermore $t_{max}$ be the maximum time (over all challenges $C_i \in C$) which it takes until the system has generated the corresponding response $R_i$. $S$ is called a $(t_C, t_{Ph}, \epsilon)$-SIMPL SYSTEM if there is a numerical string $D(S)$, called the description of $S$, and a generic computer algorithm *Sim* such that the following conditions are met:
1. For all challenges $C_i \in \mathbf{C}$, the algorithm Sim on input

$$ (C_i, D(S)) $$

outputs $R_i$ in feasible time.

2. Any cryptographic adversary Eve will succeed in the following security experiment with a probability of at most $\epsilon$:

(a) For a time period of length $t_C$, Eve is given the numerical description $D(S)$ and the code of the algorithm Sim.

(b) Within this time period $t_C$, Eve is furthermore granted adaptive physical access to the system $S$ at adaptively chosen time points. However, her overall access times must add up to a total of at most $t_{Ph}$.

(c) After the time period $t_C$ has expired, Eve can still access $D(S)$ and Sim, but has no physical access to $S$ any more. She is presented with a challenge $C_{i0}$ that was chosen uniformly at random from the set $\mathbf{C}$, and must output a value $V_{Eve}$.

We say that Eve succeeded in the above experiment if the following conditions are met:

(i) $V_{Eve} = R_{i0}$.

(ii) The time that Eve needed to output $V_{Eve}$ after she was presented with $C_{i0}$ is at most $2 \cdot t_{max}$.

The said probability of $\epsilon$ is taken over the uniformly random choice of $C_{i0} \in \mathbf{C}$, and the random choices or actions that Eve might take in steps 2a, 2b and 2c.

Some remarks on the specification are in order.

**Security Model.** Let us start by briefly discussing the security model of the specification. In practice, an adversary Eve can gather information about $S$ in essentially two ways. Firstly *computationally*, by analyzing challenge-response-pairs $(C_i, R_i)$ and by analyzing the algorithm Sim and the description $D(S)$. The CRPs may either stem from eavesdropping on protocols, or they may be computed by the adversary himself via the algorithm Sim and the description $D(S)$. These possibilities are reflected in item 2a of the specification. Secondly, Eve may *physically* measure arbitrary features of the system $S$ at some point. For example, she might try to obtain some physical characteristics or internal parameters of the system which are not easily deducable from knowing many CRPs, but which could speed up her simulation. This possibility is covered in item 2b. The model tries to reflect real-world situations, for example if $S$ was used in mobile systems for identification purposes.

**Immunity against Full Read-Out.** It follows from Specification 1 that for any SIMPL system $S$, it must be impossible to measure the values $R_i$ for all possible parameters $C_i \in \mathbf{C}$ within the timeframe $t_{Ph}$. Otherwise, Eve could create an exhaustive lookup-table for all possible values $R_i$ during step 2b, which would enable her to succeed in the described experiment. Hence, for any SIMPL system either the set of possible measurement parameters $\mathbf{C}$ must be very large (for example exponential in some system parameter) and/or successive read-outs can only be carried out relatively slowly.
*Immunity Against Cloning.* Please note further that Specification 1 implies that previous physical access and a number of known Challenge-Response-Pairs of *S* must not enable Eve to do one of the following:

1. Build an *exact physical clone* $S'$ of the system *S*, for which

$$R_i = R'_i \quad \text{for (almost) all } C_i \in \mathbb{C},$$

and for which the evaluation of the $R'_i$ works comparably quickly as by an experiment on *S*.

2. Build a *functional physical clone* $S'$ of *S*, which may be a physical system of a possibly very different structure or different lengthscales than *S*, that enables Eve to determine the values $R_i$ for (almost) all $C_i \in \mathbb{C}$ correctly and comparably quickly as by experiment on *S*.

3. Build a *digital clone*, which is a computer algorithm *Alg* that numerically computes the values

$$Alg(C_i) = R_i$$

for (almost) all $C_i \in \mathbb{C}$ comparably quickly as by an experiment on *S*.

The inability for *digital cloning* implies a number of non-trivial requirements: Firstly, it logically includes the immunity against full read-out that we discussed earlier. Secondly, it implies that the behaviour of *S* cannot be learned by a machine learning algorithm that has a very rapid prediction phase, which works on a comparable timescales as the real-time behavior of *S*. Thirdly, and most generally, it implies that the simulation of *S* on the basis of $D(S)$ cannot be split into a possibly laborious precomputation phase independent of a concrete challenge, and a specific computation phase that very rapidly determines $R_i$ once $C_i$ is given.

In the sequel, we will sometimes refer to the immunity of *S* against cloning also as the unreproducibility or the uniqueness of *S*.

*Feedback Loops and Security Margin.* Specification 1 stipulates that the time gap between Eve and the real SIMPL system must be at least a factor of 2. This seems surprising: One might expect a polynomial vs. exponential distinction here. However, such asymptotic notions cannot be applied directly to the finite function which a SIMPL system implements without rising contradictions [9]. Furthermore, it is not clear whether a unique, non-reproducible hardware system with a truly exponential speed up exists at all: Quantum computers or quantum hardware are clonable, and other *practical* physical system with an exponential speed up over classical Turing machines currently are not known [19] [20] [21].

Nevertheless, in the application protocols which we suggest (identification and on-the-fly message authentication), a *detectable* time difference at the time of the protocol execution suffices. No security properties similar to the long-term confidentiality of encryption are required, that would make a polynomial vs. exponential time gap necessary.

Furthermore, the absolute (but not the relative!) time difference between the original system and Eve can be amplified via feedback loops. There, the SIMPL systems successively determines a sequence of challenge-responses-pairs $(C_{i_1}, R_{i_1}), (C_{i_2}, R_{i_2}), \dots,$
$(C_{i_k}, R_{i_k})$, in which later challenges $C_{i_m}$ are determined by earlier results $R_{i_l}$, with $m > l$. In this context, $(C_{i_1}, R_{i_k})$ can be regarded as the overall challenge-response pair determined by the structure, and the set $C$ and $t_{max}$ can be adjusted accordingly. Such feedback loops shift us into a region of absolute delay values (e.g. seconds) where we can maintain security even in the face of unwanted side effects, such as network and transmission delays.

*Different Adversarial Scenarios.* The specification leaves to some extent open which specific resources Eve may employ during her attack. There are several meaningful scenarios, leading to different security notions.

1. **CONSUMER SECURITY:** Eve is assumed to be a private person, possibly very educated in cryptographic and security matters, but with a budget not exceeding one million dollars.

2. **TECHNOLOGICAL SECURITY:** We assume that Eve is allowed to use basically unlimited financial resources, and faces no restrictions other than those induced by current technology.

When we say that a SIMPL system is secure in one of the above scenarios, we mean that it remains secure in the sense of Specification 1 if Eve is allowed the described resources. Which type of security we seek strongly depends on the intended application. A SIMPL system that is not technologically secure, but consumer secure might still find very fruitful applications in the consumer market. One should have this fact in mind, and not aim for technological security only when designing SIMPL systems.

# 3 Protocols and Applications

We will now quote one exemplary protocol that can be realized by SIMPL systems in order to illustrate their working principle [1]. A few applications and the advantages of SIMPL systems are briefly discussed, too.

## 3.1 Identification by SIMPL Systems

We assume that Alice, who holds an individual SIMPL system $S$, has put $D(S)$, Sim, $t_{max}$ and a description of $C$ in a public register. Now, she can prove her identity to an arbitrary second party Bob as follows [1]:

**Protocol 2: IDENTIFICATION OF ENTITIES BY SIMPL SYSTEMS**

1. Bob obtains the information $D(S)$, Sim, $t_{max}$, and $C$ associated with Alice from the public register.

2. Bob sends a number of randomly chosen challenges $C_1, \dots, C_k \in C$ to Alice.

3. Alice determines the corresponding responses $R_1, \dots, R_k$ by experiment on her SIMPL system $S$, and returns them immediately to Bob.

4. Bob receives values $V_1, \dots, V_k$, and measures Alice's response time (i.e. the time between the two events of sending $C_1, \dots, C_k$ and receiving $V_1, \dots, V_k$). If this time is above the threshold $2 \cdot t_{max}$, he aborts the protocol.
5. Bob checks through simulation by the algorithm Sim if for all $i = 1, \dots, k$,

$$V_i = R_i.$$

If this is the case, Bob believes Alice's identity, otherwise not.

*Security.* As usual, $k$ is the security parameter of the protocol. In a nutshell, the protocol works because Eve is unable to determine the values $R_i$ for randomly chosen $C_i$ comparably quickly as Alice, provided that: (i) The lifetime of the system $S$ (and the period since $D(S)$ was made public) does not exceed $t_C$, and (ii) Eve's accumulated physical access times to $S$ do not exceed $t_{Ph}$. In that case, Eve's probability to succeed in the protocol without possessing $S$ are less or equal to $\epsilon^k$.

*Practicality.* Bob can improve his computational efficiency by verifying the correctness of the responses $R_i$ merely for a randomly chosen, smaller subset of $\{1, \dots, k\}$. If necessary, possible network and transmission delays can be compensated for in advance by amplifying the absolute time gap between Eve and $S$ through feedback loops (see discussion in section 2). Also the asymmetry between checking a solution and computing a solution may be exploited in future protocols (see section 6.3 of [1]).

## 3.2 Applications and Advantages of SIMPL Systems

Straightforward applications of the above identification protocol include [1]:

(i) Identification of hardware and computer systems.

(ii) Secure labeling of valuable items, such as branded products, pharmaceuticals, passports, bank notes, credit cards, and the like.

(iii) Unclonable (copy protected) representations of digital content and software, digital rights management.

(iv) Tamper sensitive hardware environments.

The upside of using SIMPL systems in these situations over standard mathematical cryptotechniques or alternative approaches such as Certificates of Authenticity [11] or PUFs has been discussed in detail in [1]. It includes: (i) SIMPL systems do neither contain nor constitute any sort of secret binary information. This makes them naturally immune against any side channel, invasive or malware attack. (ii) They allow protocols that are independent of the standard, unproven number theoretic assumptions (factoring, discrete log). (iii) They have strong practicality advantages over COAs and PUFs, due to their public key nature. (iv) They allow new DRM techniques, or unforgeable labels that can be read out digitally over long distances, and which can be verified offline at the same time [1].

These assets make them a worthwhile target for future investigations. In particular, it would be important to find electrical, integrated implementations — an issue which was left open in [1].
# 4 SIMPL Systems from Cellular Non-Linear Networks

## 4.1 Introduction and General Idea

A first electrical and on-chip candidate for SIMPL systems are Cellular Non-Linear Networks (CNNs) [22]. If successfully implemented, they would result in a technologically secure SIMPL system (see page 5).

CNNs are analog computing arrays with a regular, periodic, cellular structure. The cells are characterized by a dynamical state variable, and their time evolution depends on their own internal state and on the inputs from their neighbouring cells. On an abstract level, their behavior is given and determined by so-called templates, which in the simplest case are real-valued matrices. On a circuit level, it is given by the transistor architecture of a cell, which implements the behavior specified by the templates.

More specifically, each cell is characterized by a dynamical state variable $x$, which obeys the following, ordinary differential equation (ODE):

$$ \dot{x}_{ij} = -x_{ij} + \sum_{k,l} A_{i,j,k,l} y_{kl} + \sum_{k,l} B_{i,j,k,l} u_{kl} + z_{ij} $$

i.e. the time derivative of the state variable (for the cell with $i, j$ indices) depends on the $y$ output of the neighboring cells (denoted by the $k, l$ indices) via the $A$ cloning templates. Each cell has a bias ($z$) and inputs, which are coupled by the $B$ template to the equation.

As a mathematical model, CNNs are very general; for example, cellular automata [13] can be interpreted as a special CNN which operates on discrete variables in discrete time (and where rules replace the ODE-based description). CNNs are also known to be Turing-complete [14]. CNNs often have multiple layers, and these layers are also coupled to each other via $B$ templates.

Due to their analog and highly parallel architecture, CNNs have a remarkable computing power and efficiency. Already in 2004, a state-of-the-art programmable, commercially available CNN in a 0.35-µm standard CMOS technology exhibited peak computing figures of 330 GOPS [23] (or 3.6 GOPS/mm² and 82.5 GOPS/W in terms of area and power consumption). These numbers are yet excelled by non-programmable CNNs, which we propose for use as SIMPL systems. In specialized tasks, it is known that CNNs can outperform digital computers by a factor of up to 1,000 [24] [25]. CNNs are the largest analog circuits, with the CNN referred to above [23] containing 3.75 million transistors.

A further important property of CNNs is that their functionality is especially sensitive to the inevitable variations in the fabrication process, unless special countermeasures are taken. This can make the function $F_S$ computed by a CNN $S$ truly unique. At the same time, since CNNs are integrated electrical systems, dedicated on-chip measurement circuitry can determine the fabrication mismatches, and deliver a sufficiently detailed description $D(S)$ to simulate $F_S$. Such types of self-measuring cells are already today in standard use for calibration purposes [26]. Furthermore, it is known that there is a stable regime where the fabrication mismatches determine the CNN behavior, and where they override circuit noise and temperature variations [27] [28]. Altogether, said properties make CNNs quite interesting candidates for SIMPL systems.
## 4.2 Implementation

We propose two concrete candidates for CNN-based SIMPL systems. Firstly, CNNs employed for specialized tasks (see above), for example image processing tasks, where they are known to outperform classical architectures by factors of 10 – 1,000 [24] [25] [30].

Another attractive option, which we discuss in greater detail, is a template and circuit-design that has been recently devised in our group [29]. It is inspired by the high internal complexity of optical PUFs [2], in whose time evolution many internal scattering components interact in parallel, leading to a high computational complexity and to laborious simulatability.

Our template has the remarkable property that it effectively transfers optical behavior onto a CNN (i.e. onto an electrical integrated circuit), which then behaves quasi-optical, that is, similar to an optical system. In particular, the electrical current flowing through a certain reference point in each CNN-cell is equivalent to the local light intensity in an optical interference reference system.

The upcoming figures provide the templates and cell architecture of this 3-layer CNN, as well as simulation results that confirm the quasi-optical behavior. Figure 1 shows the templates and the interaction structure of the proposed 3-layer CNN. Figure 2 illustrates the circuit-level design. Figure 3 provides simulation data which shows the quasi-optical interference patterns in the linear (left) and non-linear/mismatched case (right). Figure 4 illustrates that local changes in the structure propagate globally. This further illustrates the quasi-optical nature and the high computational complexity of the structure: Its evolution involves many interacting subunits in parallel.

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Templates and interaction structure of our 3-layer CNN-SIMPL system.</figcaption></figure>

The described CNN-design seems particularly suited as SIMPL system because its quasi-optical behavior fosters pairwise interaction between the cells throughout the
<figure><img src="image_3.png" /><figcaption>Fig. 2. Circuit level design of our proposed CNN-SIMPL system.</figcaption></figure>

<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /><figcaption>**Fig. 3.** Simulated behavior of the CNN-SIMPL system. The brightness levels illustrate the currents at a fixed reference point in each cell within a 100 × 100 cell structure. Left: Linear case, without fabrication mismatches, and with two excitation sources. Right: Non-linear case, resulting from fabrication mismatches, again two excitation sources. The left picture nicely shows the quasi-optical interference behavior. The non-linear case obviously provides a much more complex and richer regime, which is preferable for our purposes.</figcaption></figure>
<figure><img src="image_6.png" /><figcaption>**Fig. 4.** A difference map that illustrates the global sensitivity of our CNN design to a local change in the structure. We changed only a single template at a particular position (denoted by *B* in the figure), which was even located far away from the input exciting the structure (marked as ln). This altered the global behavior of the circuit detectably. The figure shows the difference of the values $E_z^{(1)}$ and $E_z^{(2)}$ obtained by two simulations, one for the original value of the templates, the other for one template value in position *B* altered.</figcaption></figure>

structure. This leads to a particularly strong, inherent parallelism, which will be costly to simulate on digital architectures. Furthermore, as we could show in simulations, the behavior of the quasi-optical SIMPL automatically shifts into a non-linear, highly complex regime through the occurring manufacturing mismatches, which can be exploited even better for our purposes. In opposition to three-dimensional optical PUFs, its description $D(S)$ can be determined by in-built on chip measurement circuitry.

Another very important characteristics of our circuit that its behavior is sensitive, but not chaotic. Chaotic circuits are well known [15] and several CNN templates are known to realize chaos [16] [17] [18]. The time trajectories of a chaotic system are irreproducible in a real physical environment and are hence unsuited as a SIMPL system.

*Security Aspects*. A 100 × 100 cell CNN with our architecture leads to the following specific numbers: It requires a description $D(S)$ containing about $10^4 \cdot 19$ template values, which is about 100 kB of information. In order to simulate the real-time evolution which the CNN undergoes in a few microsecond time frame, $10^4$ coupled differential equations need to be solved (i.e., one for each cell). We estimate that this gives us a speed advantage of 10 – 100 to comparable digital computing machines. Please note also that CNNs are very small and energy efficient, allowing their integration into small devices, while classical architectures with comparable computing power will often be distinguishable already by their size on mobile devices such as smart cards or security tokens.
# 5 SIMPL Systems from Special SRAM Memories

## 5.1 Introduction and General Idea

One practical and stable, but only consumer secure SIMPL candidate will be presented in this section. It is based on a special design of SRAM memories, which we call “skew design”. Its basic idea is to design the SRAM-cells such that they exhibit varying behavior in different operational voltage regions. Some of the cells (cells of type 1) will function properly over the whole operational voltage range. Others, of type 2, will possess stable read operations, but exhibit (intended) write failures whenever the operational voltage VDD is below a certain threshold. This means that in these VDD regions, the content of the cell is not changed or affected by write procedures. Below the threshold, however, the write operation in cells of type 2 functions properly. Finally, there are cells of type 3, which contain a fixed bit value (0 or 1). It has been hardwired into them already in their fabrication, and their content cannot be changed by any write operation at all, regardless of the applied operational voltage.

Now, imagine an SRAM-memory *M* where cells of the described three types are randomly distributed or mixed. We call such a memory a “skew memory”. Imagine further that on the basis of *M*, we build a larger hardware system *S*, which repeats the following feedback loop *l* times at maximal operational speed.

**Feedback loop, iteration *i*:**

1. Write bitvalues $b_1^i, \dots, b_k^i$ into the addresses $WR_1^i, \dots, WR_k^i$ of *M*

2. Read out the bit values $B_1^i, \dots, B_m^i$ from the addresses $READ_1^i, \dots, READ_m^i$

3. Switch to operational voltage VDD(*i*)

4. Determine the parameters necessary for the next iteration, namely $b_1^{i+1}, \dots, b_k^{i+1}, WR_1^{i+1}, \dots, WR_k^{i+1}, READ_1^{i+1}, \dots, READ_m^{i+1}, VDD(i+1)$, as a pseudorandom function of the values $B_1^i, \dots, B_m^i$ obtained in step 2.

*S* is depicted schematically in Fig. 5. In order to associate a global input and a global output with *S*, we may say that the values $b_1^0, \dots, b_k^0, WR_1^0, \dots, WR_k^0, READ_1^0, \dots, READ_m^0, VDD(0)$ that are necessary to start the loop, constitute its global input. After the last of the *l* iterations, the values $B_1^l, \dots, B_m^l$ can serve as the global output of *S*. Alternatively, one may define the global output to be a function (e.g. a hash function) of the values $B_1^{l-q+1}, \dots, B_m^{l-q+1}, B_1^{l-q+2}, \dots, B_m^{l-q+2}, \dots, B_1^l, \dots, B_m^l$ that occured in the last *q* iterations of the loop. In this sense, we can interpret the behavior of *S* as a function $F_S$ mapping global inputs to outputs.

Then, $F_S$ has the following properties:

(i) $F_S$ can be individualized by changing the design of the memory *M*. To that aim, for example memory cells of type 3 (fixed bitvalues) can be distributed randomly over the memory in a final fabrication step.

(ii) If the distribution of the cells of type 1, 2 and 3 is known, the function $F_S$ can be simulated digitally.
<figure><img src="image_7.png" /><figcaption>**Fig. 5.** Schematic illustration of the input–output behavior of *S* and of the function *F*<sub>S</sub>.</figcaption></figure>

(iii) The simulation of $F_S$ on a standard architecture will be slower than the real-time computation of $F_S$ by $S$. Also configurable hardware or ASICs that are not based on a skew design will have a speed disadvantage. In both cases, the speed gap will only be a constant factor, however.

(iv) If the special skew design of SRAM cells is legally protected, then an adversary needs his own chip foundry to produce a hardware system that implements $F_S$ comparably quickly, since ordering ASICs with a skew design will be legally prohibited.

The above properties qualify *S* as a consumer secure SIMPL system. We will discuss the practical implementation over the next section.

## 5.2 Implementation

A concrete skew design developed in our group [12] is illustrated in Fig. 1a), with width and length specified beside each transistor. The functionality of the design based on TSMC 0.18 µm technology has been successfully verified with Spectre [31] simulations. The corresponding results are illustrated in Figure 7. In our case, $VDD_{min} = 1.4$ V, $VDD_{max} = 1.7$ V, and $VDD_{funcmin} = 1.58$ V.

<figure><img src="image_8.png" /><figcaption>**Fig. 6.** (a) The SRAM cell layout. (b) The basic operation cycle of the SRAM-SIMPL system.</figcaption></figure>
<figure><img src="image_9.png" /><figcaption>**Fig. 7.** Spectre Simulations confirm the desired behavior: Write failures occur at certain voltages, meaning that the content of the SRAM cell remains unchanged in the WRITE operation. At the same time, the READ operation functions properly at all voltages.</figcaption></figure>

The memories, which will all share the same layout, can be individualized towards the end of manufacturing by fixing the content of some individually chosen cells to certain values. This means that the resulting structure will not be *manufacturer resistant* in the sense of [4], but will at least require a fraudster to possess its own chip foundry. The common SRAM-cell arrangement will be contained in the general simulation algorithm *Sim*, and the individual description *D(S)* consists of the cells that have been fixed to certain values. Please note that the described individualization can be carried out on the basis of a pseudorandom number sequence, which means that a *short, few-hundred bit long random seed s* suffices as *D(S)*.

The basic implementation of the feedback-loop is sketched in Fig. 1b). The imple-
mentation of the pseudo-random generator is carried out by an LSFR, since a LSFR
works very quickly. Computationally more laborious PRNGs could perhaps be imple-
mented more quickly by a fraudster in his hardware. He would thereby regain some of
his speed disadvantage. Please note that we do not require a PRNG with cryptographic
security in this application, but merely a PRNG with a long periodicity, such that as
many memory cells as possible are at least once written to or read from in the feedback
loop.

The *relative* speed advantage of the real system can be further amplified by acti-
vating and writing into multiple word lines during one write cycle. Due to the skew
design, the same value written in several lines will not necessarily result in the same
cell content. Based on the simulation data we obtained, we estimate that the relative
speed advantage of a SIMPL SRAM memory will be a factor on the order of 10, even
compared to dedicated, configurable hardware such as FPGAs. At the same time, since
all operations on the SRAM-memory are fully digital and well-defined, the content of
the memory can be precisely simulated and predicted.

Compared to optical SIMPLs [1] and CNN-SIMPLs, the great advantage of the SRAM-variant is its practicality and stability. It can be implemented relatively cheaply, integrated in existing systems, and requires only very short descriptions D(S). This comes at the cost of losing their technological security, and exchanging it against consumer security (see page 5). Nevertheless, this seems acceptable in many applications.

*Security Aspects*. Let us discuss a few security relevant aspects. A fraudster who wants to imitate the skew SIMPL systems without a skew architecture has a number of basic possibilities.

First of all, he may try to implement the feedback loop in full logic, that is, without
any memory cells at all. His hope may be that pure logic operations work faster than
memory read and write steps, and that he can so outperform (or at least match) the
speed of the original SIMPL. However, if the memory is sufficiently large, then the
construction of such a pure logic will be prohibited by size and complexity constraints.

This means that the faker needs to employ some sort of memory in his attempts. SRAM memories are, in general, the fastest currently available technology, meaning that the faker should use SRAM cells, too. If he cannot rely on skew cells, however, he cannot obtain the result of the WRITE operation in a skew cell (which is a function of the WRITE value, the actual operational voltage and the type of the cell) within one WRITE step.

The faker rather needs to compute the resulting value “by hand” before he writes
it into a classical cell. To that end, he needs to look up the type of the cell before
writing the value. That costs him one extra read operation before he executes the write
procedure. Furthermore, computing the resulting write value “by hand” also costs time.

Overall, a faker without a skew memory requires one read operation, some compu-
tation and one write operation in order to emulate what happens within one write step
of the skew memory. This provides a speed advantage of a factor around 2, as desired.

As said earlier, our group currently investigates designs where the SIMPL memory
allows to write the same bit block into more than one word line simultaneously. The
values that arrive in the multiple lines eventually differ due to the individual skew design
of the cells. This could rise the speed advantage to a constant factor on the order of 10.

**6 Conclusions**

SIMPL Systems are a novel security concept, which can be regarded as a public key
version of Physical Unclonable Functions [1]. Structurally, they function like a pri-
vate/public key cryptosystem, with the notable difference that the equivalent to the pri-
vate key is a physically hard-to-reproduce structure, which does not contain any secret
information at all. This leads to critical security and practicality advances. In this pa-
per, we reviewed the basic concepts presented in [1], but mainly focused on promising
IC-based implementations of SIMPL systems.
Our first idea was to employ large, analog computing arrays as SIMPL systems. They evolve in parallel and by exchanging analog signals between their subunits, creating a significant computational power and complexity. At the same time, the arrays can be designed to strongly depend on fabrication mismatches, making the function which they implement individual and unique. We suggested to use cellular, non-linear networks with special templates, since they are the largest currently known analog circuits with up to millions of transistors. We proposed one concrete design on the template and circuit level, and evaluated its functionality in several simulations. One important asset of CNN-based SIMPL systems was that they can eventually lead to technologically secure SIMPL systems.

Our second idea was to use special ASICs as SIMPL systems, whose circuit design implements one specific digital function more efficiently than a standard architecture. We suggested special SRAM designs, where the dimensions of the SRAM-cells are varied in such a fashion that their functionality depends on the applied operational voltage. This creates a small, constant computational overhead in the simulation of the cells, especially in the case where many subsequent read and write operations are applied at maximal speed and at quickly varied operational voltages in a feedback loop. The feedback loop also allows us to extend the relative, small computational overhead to larger absolute (but not relative!) time margins.

Future work will focus on implementing these structures in silicon, and on the analysis of their concrete time margins over cryptographic adversaries.

## Acknowledgements

This work was conducted in the course of the Physical Cryptography Project at the TU München. Support by the Institute for Advanced Study and the International Graduate School of Science and Engineering of the TU München is gratefully acknowledged. We thank Peter Vogl, Tamas Roska, and Wolfgang Porod for helpful discussions.

## References

1. U. Rührmair: *SIMPL Systems: On a Public-Key Variant of Physical Unclonable Functions*. Available from IACR Preprint Archive, http://eprint.iacr.org. Report 2009/255.

2. R. Pappu, B. Recht, J. Taylor, N. Gershenfeld, *Physical One-Way Functions*, Science, vol. 297, pp. 2026-2030, 20 September 2002.

3. R. Pappu, *Physical One-Way Functions*, PhD Thesis, MIT.

4. Blaise Gassend, *Physical Random Functions*, MSc Thesis, MIT, 2003.

5. Pim Tuyls, Geert Jan Schrijen, Boris Skoric, Jan van Geloven, Nynke Verhaegh, Rob Wolters *Read-Proof Hardware from Protective Coatings*. CHES 2006: 369-383

6. G. Edward Suh, Srinivas Devadas: *Physical Unclonable Functions for Device Authentication and Secret Key Generation*. DAC 2007: 9-14

7. P. Tuyls, B. Skoric. *Strong Authentication with PUFs*. In: Security, Privacy and Trust in Modern Data Management, M. Petkovic, W. Jonker (Eds.), Springer, 2007.

8. P. Tuyls, B. Skoric, T. Kevenaar (Eds.) *Security with Noisy Data*. Springer 2007.

9. U. Rührmair, J. Sölter, F. Sehnke. *On the Foundations of Physical Unclonable Functions*. Submitted, 2009. Available from http://eprint.iacr.org/
10. Richard P. Feynman, *Simulating Physics with Computers*. International Journal of Theoretical Physics, Vol. 21, No. 6&7, pp. 467-488, 1982.

11. Gerald DeJean, Darko Kirovski: *RF-DNA: Radio-Frequency Certificates of Authenticity*. CHES 2007: 346-363.

12. Srinivas B N: *SRAM for use in Physical Cryptography*. MSc Thesis, Department for Electrical Engineering and Information Technology, TU München, 2009.

13. S. Wolfram: *Statistical mechanics of cellular automata*, Rev. Mod. Phys. 55, 601 - 644 (1983)

14. Roska, T.; Chua, L.O., *The CNN universal machine: An analogic array computer*. Circuits and Systems II: IEEE Transactions on Analog and Digital Signal Processing, vol.40, no.3, pp.163-173, Mar 1993

15. Kennedy, M.P.: *Three steps to chaos. II: A Chua's circuit primer*. IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, vol.40, no.10, pp.657-674, Oct 1999

16. Zou, F. and J.A. Nossek. *A chaotic attractor with cellular neural networks*. IEEE Transaction on Circuits and Systems, Vol. 38, pp. 811-812, 1991.

17. Maciej J. Ogorzalek, Zbigniew Galias, Andrzej M. Dqbrowski, Wladyslaw R. Dqbrowski: *Chaotic Waves and Spatio-Temporal Patterns in Large Arrays of Doubly-Coupled Chua's Circuits*. IEEE Transactions on Circuits and Systems-I: Fundamental Theory and Applications, Vol. 42, No. 10, October 1995

18. M. Gomez-Gesteira, M. de Castro, V. Perez-Villar, L. O. Chua: *Experimental Chua's Circuit Arrays As an Autowave Simulator*, IEEE Transactions on Circuits and Systems-I: Fundamental Theory and Applications, Vol. 46, No. 4, April 1999.

19. Andrew Chi-Chih Yao: *Classical physics and the Church-Turing Thesis*. Journal of the ACM 50(1), 100-105, 2003.

20. Scott Aaronson: *NP-complete Problems and Physical Reality*. Electronic Colloquium on Computational Complexity (ECCC), 026, 2005.

21. Peter W. Shor: *Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer*. SIAM J. Comput. 26(5): 1484-1509 (1997)

22. L. O. Chua and T. Roska: *Cellular Neural Networks and Visual Computing: Foundations and Applications*. Cambridge University Press, 2005.

23. A. Rodriguez-Vazquez, G. Linan-Cembrano, L. Carranza, E. Roca-Moreno, R. Carmona-Galan, F. Jimenez-Garrido, R. Dominguez-Castro, and S. Meana: *ACE16k: The Third Generation of Mixed Signal SIMD-CNN ACE Chips Toward VSoCs*. IEEE Trans. on Circuits and Systems - I, 51(5): 851-863, 2004.

24. L. O. Chua, T. Roska, T. Kozek, A. Zarandy: *CNN Universal Chips crank up the computing power*. Circuits and Devices Magazine, IEEE, Vol. 12, no. 4, pp. 18-28, July 1996.

25. Cellular Wave Computers for Nano-Tera-Scale Technology - beyond spatial-temporal logic in million processor devices. Electronics Letters, April 12, 2007, Vol. 43, No. 8.

26. Tamas Roska, private communication.

27. S. Xavier de Souza, M. Yalcin, J. Suykens, and J. Vandewalle: *Toward CNN Chip-Specific Robustness*. IEEE Trans. on circuits and systems - I, 51(5): 892-902, 2004.

28. D. Hillier, S. Xavier de Souza, J. Suykens, J. Vandewalle: *CNNOPT Learning CNN Dynamics and Chip-Specific Robustness*. International Workshop on Cellular Neural Networks and Their Applications, 2006.

29. G. Csaba, X. Ju, Q. Chen, W. Porod, J. Schmidhuber, P. Lugli, U. Rührmair: *On-Chip Electric Waves: An Analog Circuit Approach to Physical Uncloneable Functions*, 2009. Available from http://eprint.iacr.org/. Report No. 2009/246.

30. T. Roska: *Cellular Wave Computers for Brain-Like Spatial-Temporal Sensory Computing*. IEEE Circuits and Systems Magazine, Vol. 5, No. 2, pp- 5-19, 2005.

31. Virtuoso Spectre Circuit Simulator, Cadence Design Systems, www.cadence.com.