n/a / Thesis / Doctor of Philosophy (PhD)

No description available.

Proliferation of computers with varying word sizes has led to increases in software use where random number generation is required. Several techniques have been developed. Criteria of randomness, portability, period, reproducibility, variety, speed, and storage are used to evaluate developed generation methods. The Tausworthe method is the only method to meet the portability requirement, and is chosen to be implemented. A C language implementation is proposed as a possible implementation and test results are presented to confirm the acceptability of the proposed code. / Master of Science

Cryptographically secure random number generators usually require an outside seed to be initialized. Other solutions instead use a continuous entropy stream to ensure that the internal state of the generator always remains unpredictable. This thesis analyses four such generators with entropy inputs. Furthermore, different ways to estimate entropy is presented and a new method useful for the generator analysis is developed. The developed entropy estimator performs well in tests and is used to analyse entropy gathered from the different generators. Furthermore, all the analysed generators exhibit some seemingly unintentional behaviour, but most should still be safe for use. / Kryptografiskt säkra slumptalsgeneratorer behöver ofta initialiseras med ett oförutsägbart frö. En annan lösning är att istället konstant ge slumptalsgeneratorer entropi. Detta gör det möjligt att garantera att det interna tillståndet i generatorn hålls oförutsägbart. I den här rapporten analyseras fyra sådana generatorer som matas med entropi. Dessutom presenteras olika sätt att skatta entropi och en ny skattningsmetod utvecklas för att användas till analysen av generatorerna. Den framtagna metoden för entropiskattning lyckas bra i tester och används för att analysera entropin i de olika generatorerna. Alla analyserade generatorer uppvisar beteenden som inte verkar optimala för generatorns funktionalitet. De flesta av de analyserade generatorerna verkar dock oftast säkra att använda.

To be effective, a linear congruential random number generator (LCG) should produce values that are (a) uniformly distributed on the unit interval (0,1) excluding endpoints and (b) substantially free of serial correlation. It has been found that many statistical methods produce inflated Type I error rates for correlated observations. Theoretically, independently seeding an LCG under the following conditions attenuates serial correlation: (a) simple random sampling of seeds, (b) non-replicate streams, (c) non-overlapping streams, and (d) non-adjoining streams. Accordingly, 4 algorithms (each satisfying at least 1 condition) were developed: (a) zero-leap, (b) fixed-leap, (c) scaled random-leap, and (d) unscaled random-leap. Note that the latter satisfied all 4 independent seeding conditions. To assess serial correlation, univariate and multivariate simulations were conducted at 3 equally spaced intervals for each algorithm (N=24) and measured using 3 randomness tests: (a) the serial correlation test, (b) the runs up test, and (c) the white noise test. A one-way balanced multivariate analysis of variance (MANOVA) was used to test 4 hypotheses: (a) omnibus, (b) contrast of unscaled vs. others, (c) contrast of scaled vs. others, and (d) contrast of fixed vs. others. The MANOVA assumptions of independence, normality, and homogeneity were satisfied. In sum, the seeding algorithms did not differ significantly from each other (omnibus hypothesis). For the contrast hypotheses, only the fixed-leap algorithm differed significantly from all other algorithms. Surprisingly, the scaled random-leap offered the least difference among the algorithms (theoretically this algorithm should have produced the second largest difference). Although not fully supported by the research design used in this study, it is thought that the unscaled random-leap algorithm is the best choice for independently seeding the multiplicative congruential random number generator. Accordingly, suggestions for further research are proposed.

<p>Random numbers are required for cryptographic applications such as IT security products, smart cards etc. Hardwarebased random number generators are widely employed. Cryptographic algorithms are implemented on FieldProgrammable Gate Arrays (FPGAs). In this work a True Random Number Generator (TRNG) employed for spaceapplication was designed, investigated and evaluated. Several cryptographic requirements has to be satisfied for therandom numbers. Two different noise sources was designed and implemented on the FPGA. The first design wasbased on ring oscillators as a noise source. The second design was based on astable oscillators developed on a separatehardware board and interfaced with the FPGA as another noise source. The main aim of the project was to analyse theimportant requirement of independent noise source on a physical level. Jitter from the oscillators being the source forthe randomness, was analysed on both the noise sources. The generated random sequences was finally subjected tostatistical tests.</p>

Advancement in cryptography over the past few decades has enabled a spectrum of security mechanisms and protocols for many applications. Despite the algorithmic security of classic cryptography, there are limitations in application and implementation of standard security methods in ultra-low energy and resource constrained systems. In addition, implementations of standard cryptographic methods can be prone to physical attacks that involve hardware level invasive or non-invasive attacks. Physical unclonable functions (PUFs) provide a complimentary security paradigm for a number of application spaces where classic cryptography has shown to be inefficient or inadequate for the above reasons. PUFs rely on intrinsic device-dependent physical variation at the microscopic scale. Physical variation results from imperfection and random fluctuations during the manufacturing process which impact each device’s characteristics in a unique way. PUFs at the circuit level amplify and capture variation in electrical characteristics to derive and establish a unique device-dependent challenge-response mapping. Prior to this work, PUF implementations were unsuitable for low power applications and vulnerable to wide range of security attacks. This doctoral thesis presents a coherent framework to derive formal requirements to design architectures and protocols for PUFs. To the best of our knowledge, this is the first comprehensive work that introduces and integrates these pieces together. The contributions include an introduction of structural requirements and metrics to classify and evaluate PUFs, design of novel architectures to fulfill these requirements, implementation and evaluation of the proposed architectures, and integration into real-world security protocols. First, I formally define and derive a new set of fundamental requirements and properties for PUFs. This work is the first attempt to provide structural requirements and guideline for design of PUF architectures. Moreover, a suite of statistical properties of PUF responses and metrics are introduced to evaluate PUFs. Second, using the proposed requirements, new and efficient PUF architectures are designed and implemented on both analog and digital platforms. In this work, the most power efficient and smallest PUF known to date is designed and implemented on ASICs that exploits analog variation in sub-threshold leakage currents of MOS devices. On the digital platform, the first successful implementation of Arbiter-PUF on FPGA was accomplished in this work after years of unsuccessful attempts by the research community. I introduced a programmable delay tuning mechanism with pico-second resolution which serves as a key component in implementation of the Arbiter-PUF on FPGA. Full performance analysis and comparison is carried out through comprehensive device simulations as well as measurements performed on a population of FPGA devices. Finally, I present the design of low-overhead and secure protocols using PUFs for integration in lightweight identification and authentication applications. The new protocols are designed with elegant simplicity to avoid the use of heavy hash operations or any error correction. The first protocol uses a time bound on the authentication process while second uses a pattern-matching index-based method to thwart reverseengineering and machine learning attacks. Using machine learning methods during the commissioning phase, a compact representation of PUF is derived and stored in a database for authentication.

Random numbers are required for cryptographic applications such as IT security products, smart cards etc. Hardwarebased random number generators are widely employed. Cryptographic algorithms are implemented on FieldProgrammable Gate Arrays (FPGAs). In this work a True Random Number Generator (TRNG) employed for spaceapplication was designed, investigated and evaluated. Several cryptographic requirements has to be satisfied for therandom numbers. Two different noise sources was designed and implemented on the FPGA. The first design wasbased on ring oscillators as a noise source. The second design was based on astable oscillators developed on a separatehardware board and interfaced with the FPGA as another noise source. The main aim of the project was to analyse theimportant requirement of independent noise source on a physical level. Jitter from the oscillators being the source forthe randomness, was analysed on both the noise sources. The generated random sequences was finally subjected tostatistical tests.

Up to now all known efficient portable implementations of linear congruential random number generators with modulus 2^(31)-1 are working only with multipliers which are small compared with the modulus. We show that for non-uniform distributions, the rejection method may generate random numbers of bad quality if combined with a linear congruential generator with small multiplier. Therefore a method is described that works for any multiplier smaller than 2^(30). It uses the decomposition of multiplier and seed in high order and low order bits to compute the upper and the lower half of the product. The sum of the two halfs gives the product of multiplier and seed modulo 2^(31)-1. Coded in ANSI-C and FORTRAN77 the method results in a portable implementation of the linear congruential generator that is as fast or faster than other portable methods. (author's abstract) / Series: Preprint Series / Department of Applied Statistics and Data Processing

In this paper we present some variants of transformed density rejection (TDR) that provide more flexibility (including the possibility to halve the expected number of uniform random numbers) at the expense of slightly higher memory requirements. Using a synchronized first stream of uniform variates and a second auxiliary stream (as suggested by Schmeiser and Kachitvichyanukul (1990)) TDR is well suited for correlation induction. Thus high positive and negative correlation between two streams of random variates with same or different distributions can be induced. The software can be downloaded from the UNURAN project page. (author's abstract) / Series: Preprint Series / Department of Applied Statistics and Data Processing