Integration of Kryptos with NIST Statistical Test Suite System Configurations Statistical BackgroundChandrika Lanka, Swetha Manne, and Harini Vasudevan Integration of Kryptos with NIST Statistical Test Suite Abstract— We integrate an existing statistical test suite (NIST) with KRYPTOS, educational software available for students taking advanced level cryptography courses in GMU. Additionally, we utilize the integrated version to test existing implementations of several Pseudo-Random Number Generators (PRNG) developed by NIST and explain interpretation approaches. Index Terms— Random Numbers, PRNGs Introduction The need for random and pseudorandom numbers arises in many cryptographic applications. Common cryptosystems and cryptographic protocols employ keys that must be generated in a random fashion. Their purpose as a premium security parameter need not be restated in most applications in wide use today, such as digital signatures and various authentication protocols. As random numbers are used in diverse operations, designers of random number generators cannot predict the user’s requirements in advance. For example, large samples compared to period length can be used, or consecutive random numbers can be combined to generate random vectors, or different substreams of a random number generator can be assigned to different processors on parallel machines. A partial solution to this dilemma is theoretical analysis of the randomness sources in the form of empirical testing. The goal of this project was to investigate one such empirical testing procedure: the NIST Statistical Test Suite. Our major objective was to integrate the test suite with KRYPTOS. The integrated version would not only provide a base for understanding statistical tests, but also help in analyzing the various cryptographic operations such as encryption, decryption and key generation. In addition, we test the existing implementations of various pseudorandom number generators and explain how to extend the interpretation of these results to other random sources. System Configurations To integrate the software and gather tests results for the PRNGS, we used two systems with the following configurations: Processor: Intel Pentium 4, 3 GHz RAM: 1 GB OS: Windows XP Professional Programming languages: The KRYPTOS software was coded using VC ++ 7.1 version 7.1.0. NIST Suite source code is written VC++ version 6 For the purpose of integration we used Visual .net 2003 VC ++ 7.1 which is compatible with the versions of both softwares. NIST Statistical Test Suite The NIST Statistical Test Suite is the result of collaborations between the Computer Security Division and the Statistical Engineering Division at NIST. Statistical tests in the package include the: frequency, block frequency, cumulative sums, runs, long runs, Marsaglia's rank, spectral (based on the Discrete Fourier Transform), nonoverlapping template matchings, overlapping template matchings, Maurer's universal statistical, approximateentropy, random excursions, Lempel-Ziv complexity, linear complexity, and serial. Any statistical analysis includes study of period length, analysis of intrinsic structures of the numbers and points and assessment of correlations between random numbers and points. This table in briefly describes each of the statistical tests, and the types of defects that these statistical tests were designed to detect. Statistical Test Defect Detected 1. Frequency Proportion of zeroes and ones for the entire sequence 2. Cumulative Sums Determine whether cumulativesum of partial sequences is too large or too small relative to the expected behavior 3. Longest Runs Of Ones Deviation of the distribution of long runs of ones 4.Runs Total number of zero and one runs, where run is an uninterrupted sequence of identical bits 5. Rank Deviation of the rank distribution from a corresponding random sequence. 6. Spectral(DFT) Periodic features in the bit stream. 7. Non-overlapping Template Matchings Too many occurrences of non-periodic templates 8. Overlapping Template Matchings Too many occurrences of m-bit runs of ones. 9. Universal Statistical Compressibility(regularity) 10. Random Excursions Deviation from the distribution of the number of visits of a random walk8 to a certain state.11. Random Excursion Variant Deviation from the distribution of the total number of visits (across many random walks) to a certain state. 12. Approximate Entropy Non-uniform distribution of m-length words. Small values of ApEn(m) imply strong regularity 13. Serial Non-uniform distribution of m-length words. Similar to Approximate Entropy. 14.Frequency Test within a block test the proportion of ones within M-bit blocks. 15. Linear Complexity Deviation from the distribution of the linear complexity for finite length (sub) strings. Validation of Test Suite In order to validate that the statistical test suite is operating properly, we tested the software against the five sample files that have been provided by NIST. As the results returned matched the values provided by NIST, we could verify that the suite was functionally sound. Integration with KRYPTOS Changes to KRYPTOS GUI • Add an extra pop-up menu to the menu of KRYPTOS. • Include options for selecting user-generated files or existing Pseudorandom Generators Integration The major task to be performed in the integration was to be able to test the encrypted files Pseudo Code 1. Open the input file as Bits in Binary File Format 2. Run a loop from beginning of file till EOF 3. Allocate buffer to hold 4 bytes of long data 4. READ 4 bytes of data from the file 5. CHECK for ENDIAN - if the file has been binary encoded in another system like some unix systems or mac the byte order has to be reversed to properly interpret data 6. Iterate through the 32 bits of the buffer read to determine each bit (AND each bit with 1 to determine if the bit is a 1 or 0) 7. Use the bits read for further processing8. Repeat 2 till end of file and all bits are read Statistical Background The objective of integration with KRYPTOS was to enable empirical testing of random number sources. The first task was to modify the user interface to enable ease of usage and understanding the software. The next step was to help easy interpretation of results. At this point it would be appropriate to introduce some definitions and their significance to empirical testing. A