A technique to design high entropy chaos-based true random bit generators

A Technique to Design High Entropy Chaos-Based True Random Bit Generators Tommaso Addabbo, Massimo Alioto, Ada Fort, Santina Rocchi, Valerio Vignoli Information Engineering Dept. - University of Siena Via Roma, 56 – 53100 Siena, Italy [email protected], [email protected], [email protected], [email protected], vignoli@ dii.unisi.it Abstract—In this paper the theoretical bases to design a true random bit generator (TRBG) circuit with a predefined minimum entropy are discussed. The approach is tailored to TRBGs based on a one-dimensional piecewise-linear chaotic map, and it is based on a feedback control procedure that allows to dynamically changing the system parameters. For this purpose, the procedure just exploits the TRBG output observation without requiring bit throughput reduction. The design approach was validated by an hardware prototype implemented on a Field Programmable Analog Array (FPAA).

I.

circuit implementation (Section II). These results are then used to derive a fast and reliable correction procedure to significantly reduce the effect of the non-idealities and thus to increase the ASE of the TRBG output sequences (Section III). Finally, a hardware implementation of the complete system is presented with statistical test results and conclusions (Section IV). II.

Let us consider the following dynamical system: xn ≥ 0 ⎧ B xn − A xn +1 = f ( xn ) = ⎨ xn < 0 ⎩ B xn + A

INTRODUCTION

Ideal True Random Bit Generators (TRBGs) are discrete time memoryless binary sources with unbiased symbols that present an Average Shannon Entropy (ASE) of 1 bit/timestep [1]. In practical circuit implementations, the ASE of a TRBG is lower than 1 bit/time-step, and it is a parameter strictly dependent on the unpredictability and the randomness degree of the generated sequences. Since postprocessing algorithms cannot increase this parameter without decimation or compression (that is without lowering the TRBG throughput), design approaches that achieve an adequate ASE at full throughput are of practical interest [2]. In most of the chaos-based TRBGs (see e.g. [2]-[4]), the theoretical knowledge of the chaotic system information generation mechanism allows for setting the nominal ASE arbitrarily close to the ideal maximum Shannon limit [5]. Nevertheless, the behaviour of chaotic circuits is in general sensitive to the tolerances involved in practical implementations, and therefore the actual ASE of the TRBG circuits results often lower than its nominal value [5], [6]. In this paper, a feedback strategy that preserves the circuit full throughput is proposed to improve the entropy of TRBG circuits based on the one-dimensional piecewise linear map used for random bit generation in [2], [5]. In detail, an analytical model is proposed for this map, which relates the stochastic properties of the TRBG (in terms of both the ASE and the statistical characteristics of the generated bit sequences) to the non-idealities associated with the actual

CHAOS-BASED TRBG CIRCUIT MODEL

(1)

where x∈ Λ ⊂ R, A ∈ R+, B ∈ R+. The function f: Λ→Λ is the one dimension piecewise linear map in [2], that can be implemented as in Fig. 1. In this diagram five different ideal analog blocks are present: one comparator, one gain block B, one adder, one ±A constant generator, and one delay block. The comparator output Sn is a variable that assumes the logic value ‘1’ if xn ≥0, and ‘0’ otherwise. In [2], [5] it was shown that random bit sequences {bn} can be obtained by just picking out the binary sequence defined by the comparator output Sn. Since the parameter A represents just a scaling factor, the stochastic properties of the system generating {bn}, hereafter indicated as TRBG, are dependent only on the parameter B, which must assume values greater than 1 for the system to be chaotic and not greater than 2 to avoid the state x being attracted to either +∞ or -∞. For B∈[√2,2] the two unstable fixed points π1=A/(1-B) and π2=A/(B-1) define an interval I⊂R such that any initial state x0∈I triggers a sequence {xn} eventually attracted into the chaotic attractor Λ=[-A,A)⊆I. Under these hypotheses, different binary sequences are related to different initial states x0∈Λ, and their generation probabilities are related to the state invariant probability density function of the chaotic dynamical system [2], [7]. As mentioned in the introduction, if a discrete time binary source is considered, the amount of supplied information

This work was supported by Marconi Communication under the MIUR FIRB project PRIMO (2003).

0-7803-9390-2/06/$20.00 ©2006 IEEE

1183

ISCAS 2006

Fig. 1. Block diagram of a possible implementation of (1).

Fig. 2. Block diagram of fig. 1 with non-ideal effects included.

and its grade of redundancy are expressed by the ASE. Let be On={b0,.., bn} an n-bit length generated sequence, where bn∈{0,1}. If P{On} is the generation probability of the sequence On, the ASE in bit/time-steps is given by: ⎛ 1 ⎞ (2) ASE = lim ⎜ − P{On }log 2 P{On }⎟ ⎟ n → ∞⎜ n On ⎝ ⎠ where the summation extends over all the sequences and the limit is approached from above [7]. Kocarev and Stojanovski showed that the ASE of the TRBG is an increasing function of the parameter B, and that it reaches the upper ASE limit of 1 bit/time-step when the slope B is set to 2 [5]. This result focuses the trade-off imposed to the TRBG circuit designer: to avoid the B value being greater than 2 (also accounting for the actual circuit tolerances) while trying to achieve a B value as close as possible to this limit in order to maximize the ASE. On these bases, in what follows an analytical model that allows establishing a connection between the stochastic properties of the TRBG and the non-idealities of the real circuit is discussed. A modified block diagram that accounts for the nonidealities of circuit implementations of (1) is shown in fig. 2, and the correspondent modified map f ′ is defined in (3): ⎧ B xn + B OS B + A′ + OS A xn < OS C (3) xn +1 = f ′(xn ) = ⎨ ⎩ B xn + B OS B − A′ + OS A xn ≥ OSC

∑

In fig. 2 and in (3) the quantities A′, OSA, OSB, and OSC have the following meaning: A′, OSA: any actual implementation of the ±A generator of fig. 1 is not perfectly symmetric, and issues two quantities +A1 and –A2; A′ is defined as (A1 +A2)/2, whereas OSA is defined as (A1 -A2 )/2. OSB: any actual implementation of the gain block B suffers from non-linearity and the presence of an offset. Non-linearity can be reduced by proper design techniques to non-influent values, as it was also verified by the authors [6]. Only the gain block offset, OSB, was therefore taken into account in the model. OSC: this quantity accounts for the offset of the comparator, which modifies its threshold to OSC. Therefore the comparator output S’n assumes the logic value ‘1’ if xn≥ OSC, and ‘0’ otherwise.

Equation (3) can be rearranged as: xn < P ⎧ B xn + W + Z xn +1 = f ′(xn ) = ⎨ (4) xn ≥ P ⎩ B xn − W + Z where W =A’, Z=B·OSB +OSA, and P=OSC. The parameters (W, Z, P) determines the map scale factor and the map position in the plane (xn, xn+1), while the parameter B sets the slope of the map (fig. 3).

Fig. 3. The map f’ reported in (4).

In this paper two different dynamical systems (4) are said equivalent if they define two TRBGs characterized by the same stochastic properties (i.e. for each binary sequence On the probability P{On} is equal for both the TRBGs). From this point of view, it was already proved by the authors [8] that two systems (4) are equivalent (and therefore the statistical properties of the output bit sequences {bn} are equal) if they have the same central distance D, where D is defined as: P (B − 1) + Z (5) D= . W 2 From fig. 3, the absolute value of D is the Euclidean distance of the point C = (P, BP+Z), in the plane (xn, xn+1), from the bisector of the first and third quadrants, normalized to W (the normalization to W has no influence on the dynamic behaviour of the map, being it just a scale factor). From the above discussion it is evident that, given B, systems (1) and (4) are equivalent if the ‘central distance’ of (4) is zero, that is if the two offsets cancel each other. This

1184

condition is expressed by the following relationship: P (1 − B ) = Z . III.

(6)

MAP CORRECTION IN REAL SYSTEMS

The properties of D that, together with parameter B, completely determines the stochastic properties of a TRBG based on (4), can be exploited for its ASE maximization, as it is discussed hereafter. First of all, from (6), if B is kept constant, D can be zeroed by changing either the parameter P or the parameter Z, that is, referring to fig. 2, by injecting just one correction offset either in the adder Σ1 or in the adder Σ2. Once minimized D a further correction procedure for B is necessary to make the TRBG working properly. Indeed, if D≠0, to avoid the state x of (4) to jump beyond the fixed points π1′ and π2′ (fig. 3) and to be attracted toward infinity (with a consequent electronic saturation in practical implementations), B must satisfy the following relationship: 2 (7) 1< B ≤ ≤2 1+ D 2

From (7), if D→ 0, the maximum allowable B value → 2. In practical systems the required exact values of the correction signal for D and B are not available, since the quantities OSA, OSB, and OSC (fig. 2) are not known. Nevertheless, the values of the correction signals for D and B can be obtained from the statistic properties of the generated binary sequences, as it was demonstrated by the authors in [8]. In particular, if P{bn=1} is the probability for the n-th binary output to take the ‘1’ logic value, and if µ=(P{bn=1}-0.5) for n→+∞, the authors showed that for each B value the parameter µ is a monotonic function of D, and that µ=0 when D=0. As a consequence, the µ sign estimation can be used to mimize D, as it will be discussed in what follows. Anyway, since the upper ASE limit of 1 bit/time-step is reached when B=2 (see [2], where the relationship between the ASE and B is reported), and due to the upper limit on B given by (7), the ASE is maximized if both D→0 and B→2. Summarizing, the simplest way to drive the system (4) to a desired operating point (Bmax, ⎜D⎜min), where Bmax is the maximum value of B according to (7) given ⎜D⎜min, is to iteratively minimize the central distance magnitude ⎜D⎜and then increase B, that is possible by estimating the µ sign according to the scheme of fig. 4 [8]. In fig. 4, SB and SD are the correction signals for B and D, obtained from the sign estimation of µ. In this work SB and SD are supposed to be quantized signals. Even if D can be changed by injecting SD either in the node Σ1 or Σ2 of fig. 2, the relationships reported hereafter are obtained supposing to inject SD in Σ1. In this case, with SD2=0, (3) must be modified as follows:

Fig. 4. The complete TRBG block structure.

⎧ B x n + BOS B + A′ + OS A ( x n < OS C + S D ) x n+1 = ⎨ (8) ⎩ B x n + BOS B − A′ + OS A ( x n ≥ OS C + S D ) According to (5), D for the system (8) is: D = k[OS C ( B − 1) + (OS A + BOS B + S D ( B − 1)] (9) where k = 1/(A′√2). From (9) D is zeroed if: OS C (B − 1) + (OS A + BOS B ) (10) SD = (1 − B ) If LSBD is the resolution of the digital system generating SD, it can be assumed that the SD actual value differs from (10) by a quantity related to the quantization error lower than LSBD/2. Therefore D results ≠0, and in particular: (B − 1) LSBD = D D min ≤ (11) 0 2 A′ 2 If, once minimized D, also the B value is corrected by SB, the value of ⎪D⎪changes due to (5). In detail, if B is increased by one LSBB (that is the resolution of the digital system generating SB), (11) is modified according to: LSB B ⎛⎜ OS B max + OS A max LSBD ⎞⎟ (12) ≤ D0 + + D min 2 ⎟⎠ (B − 1) A′ 2 ⎜⎝ The relationships (7) and (12) represent the worst case limit for the correction and control system. In other words two values for LSBD and LSBB can be set on the basis of (7) and (13) to ensure the system (8) to reach any target operating point (Bmax, ⎪D⎪min), with Bmax < 2. On these bases, it is now possible to introduce the ASE maximization procedure for the TRBGs based on (4). The algorithm is designed for leading the system to work with ⎪D⎪≤⎪D⎪min, and consequently with B≥Bmax, with the worst case condition (Bmax, ⎪D⎪min) fixed by the digital resolution of the control signals. At the start-up, an iterative procedure forces the central distance ⎪D⎪ to be minimized, according to the resolution of the correction signal SD (phase I), and subsequently increases B to the maximum value that avoid the system diverging (phase II). Once reached the desired status, the system start-up is finished, and the system normal operation begins. During normal operation the control procedure maintains the parameter values unchanged unless the system output diverges. In fact, if B is maximized according to (7), a further increasing drift of B or ⎪D⎪ causes the system to diverge. Moreover, the control system periodically check if a further increase in B is allowed, to

1185

counteract a possible decreasing drift of this parameter. In phase I, if SD is a ND bit word, its value is set in ND steps with a successive approximation strategy on the basis of the µ sign estimation obtained with a predefined number of samples. About this issue, both from simulation and from experimental data, the sign estimation of the polarization level for this TRBG has turned out to quickly converge with increasing the observed sequence length (the experimental results commented hereafter were obtained estimating the µ sign from the mean of 8192 contiguous bits). In phase II the same successive approximation strategy is adopted to set the SB value. The critical issue of this phase is the divergence detection which indicates a B has value higher than the limit set by (7). Since in case of divergence the state dynamic is led by saturation to a parasitic fixed stable point [2], the correction procedure can easily detect the divergence of the state orbit by checking for the presence in {bn} of fixed sequences of identical bits, while just paying the non-generation of a set of extremely improbable bit patterns (for the TRBG prototype described hereafter the test was performed on 128 contiguous bits: an ideal TRBG based on (1), with B = 2, generates a sequence of 128 equal output bits with a probability of 1/2127). Once a divergence event is detected, the procedure decreases B step by step, while forcing the system to restart from an initial state x0 ∈ I until the divergence condition is eliminated. IV

EXPERIMENTAL RESULTS AND CONCLUSIONS

The proposed strategy for the ASE maximization was tested on a prototype TRBG circuit implemented by a Field Programmable Analog Array (FPAA Anadigm AN212E04). These SRAM based devices can be dynamically reconfigured by an host processor while the old configuration is still active and running. The activation of the new configuration happens in real time in a single clock cycle, allowing for an easy implementation of the ASE maximization strategy proposed in this paper. The gain block B in fig. 2 was implemented using a FPAA library adjustable gain block, whose profile of gain versus control voltage was specified to linearly vary within the nominal range 1.4 ÷ 2.08, and that is controlled by the digital input SB value, with an experimentally verified resolution of 5 bits for the working frequency of 250 kHz. The actual structure of the system is reported in Fig. 5. The control and correction procedure for the ASE maximization is software implented on a PC equipped with an acquisition board (National PCI MIO64E) for acquiring the TRBG output, and whose 12 bit D/A converters, with a proper scaling, provide the analog controls SB and SD. The correction system was tested for different combinations of the quantization resolutions for SD and SB , within the range 4-6 bits and 4-5 bits respectively starting from different initial values of B and D. These initial values were forced by adding random offsets, obtained from a software pseudorandom number generator, to the SD and SB digital

Fig. 5. Scheme of the system used to test the correction algorithm.

correction signals. The resolution of the random offsets was finer than the actual resolution of the correction signals. The aim was to simulate a random combined effect of OSA, OSB, OSC with values uniformly distributed, disregarding the actual values of OSA, OSB, OSC, in the range ±7mV with respect to the FPAA internal voltage reference, and a random shift of the actual gain B, with values uniformly distributed in the range ±0.07. Partial ASE values as high as 0.99 bit/time-step (for word lengths up to 16 bit) were experimentally achieved at the maximum allowed speed of 250 kHz, without performing any kind of digital post-processing on the output bit sequences. Without post-processing, the proposed generator was able to issue sequences passing the FIPS 140.2 tests with a success rate higher than 98%, while typically failing only 4 of 18 Diehard tests, at the maximum resolution adopted for the two digital control signals SD and SB. On the other hand, with the direct bit-by-bit XOR with the output of a 8 bit Linear Feedback Shift Register, the sequences of the proposed TRBG passes all of the considered tests at full throughput for the whole set of resolutions adopted for SD and SB (from 4 to 6 bits, and to 4 to 5 bits, respectively). The effectiveness of the proposed technique, proved from a theoretical point of view, is not tied to the specific implementation presented in this paper, and can be successfully applied also to integrated designs (e.g. like the one proposed in [6]) with an increase in the output bit rate of up to two order of magnitude, with state of the art CMOS technologies, with respect to the FPAA implementation. REFERENCES [1] [2] [3] [4] [5] [6] [7] [8]

1186

G. Györgyi and P. Szépfalusy, “Calculation of the entropy in chaotic systems”, Phys. Rev. A, vol. 31, no. 5, pp. 3477-3479, May 1985. T. Stojanovski and L. Kocarev, “Chaos based random number generators Part I: Analysis,” IEEE Trans. Circuits Syst. I, vol. 48, no. 3, pp. 281-288, Mar. 2001. M. E. Yalçin, J. A. K. Suykens and J. Vandewalle, “True Random Bit Generation From a Double-Scroll Attractor”, IEEE Trans. Circuits Syst. I, vol. 51, no. 7, pp. 1395-1404, July 2004. M. Delgado-Restituto and A. Rodriguez-Vazquez, “Integrated Chaos Generators”, Proc. IEEE , vol. 90, pp. 747-767, May 2002 T. Stojanovski and L. Kocarev, “Chaos based random number generators Part II: Practical Realization,” IEEE Trans. Circuits Syst. I, vol. 48, no. 3, pp. 382-385, Mar. 2001. A. Fort, F. Cortigiani, S. Rocchi, V. Vignoli, “High-Speed True Random Noise Generator,” Analog Integrated Circuits and Signal Processing, vol. 34, pp. 97-105, 2003 A. Boyarsky and P. Gora, Laws of Chaos: Invariant Measures and Dynamical Systems in One Dimension, Boston : Birkhäuser, 1997. T. Addabbo, M. Alioto, A. Fort, S. Rocchi, V. Vignoli, “A Feedback Strategy to Improve the Entropy of a Chaos-Based Random Bit Generator”, accepted for publication in IEEE Trans. Circuits Syst. I.