A Generalised Testbed for Analysing Block and Stream Ciphers Lawrence BROWN Josef PIEPRZYK Reihaneh SAFAVI-NAINI Jennifer SEBERRY Centre for Computer Security Research, Department of Computer Science, University College, UNSW, Australian Defence Force Academy, Canberra ACT 2600. Australia. Abstract With the recent development of a number of new ciphers, especially block ciphers, there is a need for a set of tools to help analyse them, in order to obtain some comparative measure of their relative security, and to assist in identifying any shortcomings in their design. This project uses a number of tests to provide a better determination of a cipher's capabilities than previous attempts, and incorporates them into a framework to aid extension of the testbed, through both the addition of new ciphers, and new tests. The testbed will be used for a comparative analysis of some of the new families of block ciphers, including LOKI, FEAL, Khufu, Khafre, and KSX against the older generation which includes Lucifer and DES. Some preliminary results from this analysis on DES, FEAL, and LOKI are presented here. 1 Introduction With the increasing need for new ciphers for use in new communications systems, a number of new ciphers, particularly block ciphers, have been de- veloped. There is a need for a set of tools to help analyse these ciphers, in order to obtain some comparative measure of their relative security, and to assist in identifying any shortcomings in their design. Previous attempts at building such a set of tools have generally concentrated on using simple statistical tests on a bit stream produced by the cipher (cf. [1]). This project 1 uses a number of additional tests to provide a better determination of a ci- pher's capabilities and incorporates them into a framework to aid extension of the testbed, both through the addition of new ciphers, and new tests. The tests used fall into two broad classes: statistical tests; and structural tests. Statistical tests analyse the statistical and complexity properties of a stream of symbols (each symbol being a fixed number of bits), independent of knowl- edge of their origin. Tests suitable for use include the well known tests for randomness, the Berlekamp-Massey algorithm to measure linear complexity and linear complexity profile measures, and the Ziv complexity test. Struc- tural tests analyse aspects of a particular cipher's structure. Structural tests in use for Feistel style block ciphers include a generalised form of Meyer's analysis of ciphertext dependence on plaintext and key, and an analysis of avalanche propagation in the cipher. There are also several tests which eval- uate any substitution boxes used in these ciphers against some known design criteria, and which evaluate their non-linearity. In addition to developing these tools, a pair of frameworks has been de- signed to provide an overall framework in which to integrate the tools, and to assist in incorporating new ciphers or new tools into the system. The framework for the statistical tools is shown in Fig. 1, whilst the framework for the structural tools is shown in Fig. 2. These frameworks assume that the tools are separate programs or interpreted scripts, with a standard set of interfaces between them. This interface is either a bit stream represented as a series of ASCII 0 and 1s, or a tagged line to represent parameters or test results. The testbed will be used for a comparative analysis of some of the new families of block ciphers, including LOKI, FEAL, Khufu and Khafre, and KSX against the older generation which includes Lucifer and DES. 2 Testbed Framework The testbed framework provides a means by which a number of tools, each concentrating on a different aspect, or a different cipher, may be integrated into a common system. It defines the interfaces between the various tools at various stages in the framework. There are two broad catagories of tools used in analysing ciphers: statistical tests, which analyse the statistical properti* *es of a stream of bits; and structural tests; which analyse some aspects of a ciphers structure. 2.1 Statistical Tests Statistical tests may be applied to any stream of bits, whether generated by a stream cipher, or by a block cipher used in a stream mode. Such tests 2 ____________________________________________________________________ _ Tag _Usage _ _____________________________________________________________________ _ K: _a 64-bit key for the cipher used in the stream generator _ _ _ _ _ IV: _a 64-bit inital (or working) value for the stream generator _ _ _ _ _ K128: _a 128-bit key for the cipher used in the stream generator _ _ _ _ _ IV128: _a 128-bit inital (or working) value for the stream generator _ ____________________________________________________________________ _ _ ss: _chi square values from the streamstat program _ _ _ _ _ Lk: _a linear complexity value from the berle proogram _ _ _ _ _ LCP: _a linear complexity profile from the berle program _ ____________________________________________________________________ _ Table 1: Tags Used By the Statistical Test are used to analyse the properties of the stream in terms of how random, and how cryptographically secure, the stream is (ignoring for the present the arguments over the definitions of these words). The testbed framework for the statistical tools is shown in Fig. 1. The interfaces between the random key generator and the stream gen- erator, and between the stream analysis and summary tools use a common tagged line format. This consists of lines of information, each starting with a known tag identifying the information on the rest of the line. The tags currently in use are listed in Table 1. The interface between the stream generator and the analysis tools is a stream of bits, represented as ASCII `0' or `1' characters, with one stream per line. This permits a number of streams to be analysed in a single session. In more detail, the function of each of the stages, and the currently avail- able tools include: Random Key Generator The random key generator program is used to randomly create a large number of keys which may be used to control a subsequent stream generator program. The current program uses the DES cipher in OFB mode. Given a key and an initial value, it will generate the specified number of random keys (of either 64 or 128-bits in size). This _ _ _ _____________ _______________ _______________ ________________ _Random Key ______-_Stream ______-_Bit stre_______-_amSummary_ * * _ _Generator _ _ _Generator _ _ _Analysis _ _ __Tools _ * * _ ______________ ________________ ________________ __________________ * * _ _ _ _ Tagged Line Bit Stream Tagged Line Interface Interface Interface Figure 1: Statistical Testbed Framework 3 method has the advantage that the same set of keys can be regenerated at any time given the same initial value and key. This permits comparisons of several ciphers to then be conducted, based on the same set of random key values. Stream Generators The Stream Generators are programs which, given a specific key (and possibly other cipher dependent parameters), and a stream length, generate a stream of bits. These programs use a standard program shell. This supports a standard command-line interface, and also is able to read arguments such as new inital values or keys from the standard input. This permits a series of streams to be generated for analysis in a single sessi* *on. This shell is customised simply by changing the cipher library routines called. This allows new stream generators to be created very easily, once a new set of cipher library routines are available. The stream generators currently in use run the relevant cipher in OFB mode. The ciphers supported are: desrnd ANSI standard DES; lokirnd CCCSR LOKI cipher [2]; fealrnd NTT FEAL cipher [3], [4]; luciferrnd IBM's original Lucifer cipher [5]; Bit Stream Analysis Tools The Bit Stream Analysis tools take as input a stream of bits, and calculate some statistical properties of it. Tools availa* *ble at present, now adapted for the testbed environment, include: streamstat This program calculates the well known statistical tests for ran- domness on a stream from [6], [7], including the frequency, serial, poker (on blocks of 3,4, and 8 bits), run and gap tests. It forms a tagged out- put for the next stage consisting of the number of bits scanned and the chi-square values for each of these tests. berle This program performs a linear complexity analysis on a stream [8], [9]. It can produce tagged lines of either the linear complexity, or both the linear complexity and the linear complexity profile for summarising by the next stage. This analysis is computationally expensive, and hence may be used only on fairly short stream lengths. Summary Tools These tools accumulate the results from a series of streams generated from different keys, and calculate some overall statistics for each of the individual statistics measured by the previous stage. 4 A number of small scripts, tailored for specific tests, are used to accu- mulate these results. Alternatively, the tagged output can be read into a statistical package such as S [10] for further analysis and graphing. The utilities available in the testbed at present are: sstream summarises the results from the streamstat analysis program. The current script calculates, for each test, the mean and range and the percentage of results that fall under the 5% or over the 95% confidence levels. These provide an indication of how well the results of each test matches the expected distribution. sberle summarises the results from the berle analysis program. The current script calculates, for each test, the mean and range of the results. 2.2 Structural Tests _ _ _____________ _ _____________ _ ______________ _ _ _Parameter _____-__Structure_____-___Summary _ _ _Generator __ _Analysis __ __Tools _ _ _____________ __ _____________ __ ________________ _ _ _ _ _ Tagged Line Tagged Line Interface Interface Figure 2: Structural Testbed Framework Structural tests analyse the particular structure of a cipher. As such, they are specific to each cipher (or perhaps a family of ciphers with an identical structure save for variations in some permutation blocks), and need to be rewritten for each new cipher. The testbed framework for the structural tools is shown in Fig. 2. The interfaces between the parameter generator and structure analysis, and between the structure analysis and summary tools use a common tagged line format. This consists of lines of information, each starting with a known tag identifying the information on the rest of the line. The tags currently in use are listed in Table 2. Parameter Generators These programs generate sets of parameters used to create families of related ciphers. At present the main generators, used in analysing Feistel style ciphers, are for permutations P and PC2, and pos- sibly key schedules. These are used for testing variants of existing schemes, 5 ________________________________________________________ _ Tag _Usage _ _________________________________________________________ _ P: _a 32-bit permutation P _ _ _ _ _ PC2: _a 32-bit permutation P C2 _ _ _ _ _ KS: _a DES style key rotation schedule _ ________________________________________________________ _ _ CPdep: _a ciphertext dependence on plaintext analysis _ _ _ _ _ CKdep: _ a ciphertext dependence on key analysis _ ________________________________________________________ _ Table 2: Tags Used By the Structural Test especially the DES, and DES like schemes, including LOKI. They build the permutations according to some rules, and then supply them to the structure analysis programs. A generator can also be used to control different variants of the LOKI S-boxes for analysis of their relative merits. Programs currently available include: desp builds DES style permutation P using the rules from [11] lbgenp builds DES style permutations P using latin-square criteria [12] regp builds DES style permutations P using a regular structure based on a difference function from [12] despc2 builds DES style permutations P C2 using a regular distribution with excluded bits interspersed by the rules identified in [13] As well as these generators, a number of files of standard, worst case, or example permutation and key rotation schedules are available. These may be combined to form all combinations using a special tool: comb form all combinations of permutations in up to three files Structural Analysis Tools The currently available structural analysis tools fall into two major catagories. Meyer's Dependency Analysis These programs analyse the overall ci- pher structure, using Meyer's ciphertext dependency on plaintext and key [14] as a measure of effectiveness. They assume that the S-boxes are well formed, and they examine how changes in the choice of the permutations P and PC2, and the Key Schedule KS, affect the growth of the avalanche effect in the cipher [12], [13]. These programs have to be tailored for a specific cipher framework. At present the testbed includes programs for DES and LOKI. Also available, but not yet inte- grated into the testbed are programs for the KSX DES extension, and for a 128-bit variant of the DES. The testbed programs are: 6 des_cp measures the ciphertext dependence on plaintext for DES des_ck measures the ciphertext dependence on key for DES loki_cp measures the ciphertext dependence on plaintext for LOKI loki_ck measures the ciphertext dependence on key for LOKI S-Box Analysis These programs examine the effectiveness of the S-boxes in fulfilling known design criteria. The main suite of programs measure the degree to which the S-boxes meet the criteria identified in the orig- inal NBS report on DES [11]. These use a general program shell, which enables new S-boxes to be tested by supplying suitable routines and building a new test program. The tests have been extended to supply the XOR profile used by Shamir's differential cryptanalysis of ciphers [15]. The existing S-box testing programs are: des_s analyses the DES S-boxes. loki_s analyses the LOKI S-boxes (standard and variant forms). feal_s analyses the FEAL S-boxes. lucifer_s analyses the Lucifer S-boxes. Summary Tools These tools accumulate statistics from analysing the re- sults for a number of structural tests on ciphers in a given family. Again, as for the statistical tools, these results can be loaded into a statistical packa* *ge for further analysis. scandep summarises dependency results from any of the dependency anal- ysis programs. 2.3 Overall Controlling Programs As well as the various components of the testbed, some control programs have been written to assist in performing particular analysis tasks with the testbed. These include: Tbed This is the general testbed control utility. It prompts for a particular set of tests which are wanted, eg; doing a series of stream statistics on LOKI, and then sets the relevant tools running (in this case, for a month). lokiS This is a specialised tool for running a series of tests on the LOKI S-boxes in a single session. It uses all of the options provided by the loki_s program to supply an overall profile of the LOKI S-box. A similar tool for the DES S-boxes is yet to be integrated into the testbed. 7 __________________________________________________________________________ _ Cipher _ DES _ FEAL _ LOKI _ _ Range _min av max _ min av max _ min av max _ __Dist_______<_5%_5__95%__>_95%__<_5%__5__95%__>_95%__<_5%___5__95%__>_95%___ _ Num Trials _ 1000 _ 1000 _ 8161 _ __Num_bits_________640000_______________640000_______________6400000_______ _ Freq _0.00 0.98 10.73 _0.00 0.94 13.65 _0.00 0.98 17.32 _ _____________4.5___90.2____5.3____6.1____89.8____4.1____4.8___90.6____4.6_ _ _ Serial -_0.01 1.03 13.44 _-0.01 1.05 13.79 _0.00 0.99 16.10 _ _____________4.4___91.1____4.5____4.2____89.4____6.4____4.5___90.5____4.9_ _ _ Poker 3 0_.27 7.03 25.99 _0.62 6.92 22.73 _0.39 6.98 30.22 _ _____________6.1___87.9____6.0____5.0____90.0____5.0____4.9___90.0____5.2_ _ _ Poker 4 3_.11 14.94 41.23 _3.50 14.94 36.30 _1.78 14.99 45.67 _ _____________5.0___90.0____5.0____4.8____91.0____4.2____5.0___89.7____5.3_ _ _ Poker 8 18_2.54 255.38 337.60 _193.96256.55 325.71 _182.99254.98 357.20 _ _____________4.8___90.2____5.0____4.6____90.2____5.2____4.9___90.2____5.0_ _ _ Gaps _3.85 16.8 44.35 _4.00 17.06 45.94 _2.64 15.65 49.84 _ _____________1.8___88.5____9.7____2.3____86.6___11.1___3.9____89.7____6.4_ _ _ Runs _2.76 16.69 44.85 _4.64 16.75 40.03 _3.00 15.71 44.48 _ _____________2.8___87.6____9.6____2.1____88.8____9.1____3.7___89.8____6.5_ _ Table 3: Streamstat Chi-square values for DES, FEAL and LOKI _____________________________________________________________ _ Cipher _ DES _ FEAL _ LOKI _ __Test_____m_in___av___max__min___av____max__min___av___max___ _ Num Trials _ 1000 _ 1000 _ 8161 _ __Num_bits_______960______________960______________960________ __Berle_____4_77480.29_485___476_480.15_484___477_480.16_483_ _ Table 4: Berle results for DES, FEAL and LOKI 3 Initial Results from the Testbed 3.1 Some Comparative Stream Statistics A number of trials have been run to obtain some initial comparative results for the DES, FEAL, and LOKI ciphers. These results are summarised in Tables 3 and 4 for the streamstat and berle results, respectively. Note the similarity in profiles between the LOKI and the DES results. The most noticable difference is in the skew of the distributions for the gap and run tests. This was also observed when a similar small set of tests was done on LOKI and is believed to be due to the stream length being too short in these examples (these tests scan for up to 15 bit runs and gaps). As may be seen from the longer length LOKI tests, the results here also appear to match the expected random profile. These results have also been loaded into S, and QQ plots made to com- pare the DES and FEAL, and DES and LOKI distributions for each of the statistics calculated (see [10] for details). These plots indicate a fairly good match, suggesting that all of these ciphers produce bits with the same profile. Examples of these plots are given in Fig. 3. 8 3.2 XOR Profile of DES and LOKI A key component of Shamir's new differential cryptanalysis technique is the XOR profile of the S-boxes used in a cipher. This profile consists of tak- ing all possible pairs of inputs and plotting a distribution of the XOR of the input values against the XOR of their output values. Any frequency values substantially above the average may then be used in the differential cryptanalysis process. The following two tables (5, 6) present a Stem plot of the XOR profile for DES S-box 1, and the LOKI S-box. This plot represents the relative frequency of each value that occurs in the profile, with values greater than several standard deviations from the mean listed separately as high values. For more information on this plot see the S manual [10]. The most obvious difference between the two profiles is the much larger size of the LOKI profile. This makes any use of it computationally more expensive both in time and space. The next critical feature is the relative probablilities of the high values in any column. Ignoring the anomolous value in the [0,0] location for each (being 64 in the DES profile and 4096 in the LOKI one), the highest peak in the DES profile is 14, giving a probability of its occurance in the column of P r(14=64), ie; just under P r(1=4). In the case of LOKI there is a single high value of 256 (in the [1,1] location) with P r(1=16), with most of the other high values being around 70 with approx P r(1=58). These values are obviously much lower than in the DES case, and hence the differential cryptanalysis technique, which relies on these probabilities to skew the output distribution after a large number of trials, will require many more trials to be tested before an uneven distribution becomes obvious. This early analysis suggests that LOKI may be significantly less susceptible to the differential cryptanalysis method than DES. Another aspect of the XOR profile worth examining is the profile of the Figure 3: QQ-plots of DES vs FEAL and DES vs LOKI for the 4-bit Poker test 9 N = 1024 Median = 4 Quartiles = 2, 6 Decimal point is 1 place to the right of the colon 210 210 0 : zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzx 456 246 0 : 22222222222222222222222222222222222222222222222222222222222222x 232 0 : 44444444444444444444444444444444444444444444444444444444444444x 336 168 0 : 66666666666666666666666666666666666666666666666666666666666666x 168 84 0 : 88888888888888888888888888888888888888888888888888888888888888x 84 46 1 : 0000000000000000000000000000000000000000000000 38 24 1 : 222222222222222222222222 14 12 1 : 444444444444 High: 16 64 Table 5: Stem plot of the XOR Profile of DES S-box 1 N = 1048576 Median = 16 Quartiles = 12, 20 Decimal point is 1 place to the right of the colon 0 : zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzx 0 : 222222222222222222222222222222222222222222222222222222222222222222222222x 0 : 444444444444444444444444444444444444444444444444444444444444444444444444x 0 : 666666666666666666666666666666666666666666666666666666666666666666666666x 0 : 888888888888888888888888888888888888888888888888888888888888888888888888x 1 : 000000000000000000000000000000000000000000000000000000000000000000000000x 1 : 222222222222222222222222222222222222222222222222222222222222222222222222x 1 : 444444444444444444444444444444444444444444444444444444444444444444444444x 1 : 666666666666666666666666666666666666666666666666666666666666666666666666x 1 : 888888888888888888888888888888888888888888888888888888888888888888888888x 2 : 000000000000000000000000000000000000000000000000000000000000000000000000x 2 : 222222222222222222222222222222222222222222222222222222222222222222222222x 2 : 444444444444444444444444444444444444444444444444444444444444444444444444x 2 : 666666666666666666666666666666666666666666666666666666666666666666666666x 2 : 888888888888888888888888888888888888888888888888888888888888888888888888x 3 : 000000000000000000000000000000000000000000000000000000000000000000000000x 3 : 222222222222222222222222222222222222222222222222222222222222222222222222x 3 : 444444444444444444444444444444444444444444444444444444444444444444444444x 3 : 666666666666666666666666666666666666666666666666666666666666666666666666x 3 : 888888888888888888888888888888888888888888888888888888888888888888888888x 4 : 000000000000000000000000000000000000000000000000000000000000000000000000x 4 : 222222222222222222222222222222222222222222222222222222222222222222222222x 4 : 444444444444444444444444444444444444444444444444444444444444444444444444x 4 : 666666666666666666666666666666666666666666666666666666666666666666666666x 4 : 888888888888888888888888888888888888888888888888888888888888888888888888x 5 : 000000000000000000000000000000000000 5 : 222222222222222222222222222222 5 : 4444444444444444444 5 : 666666666666 5 : 8888 6 : 0000 High: 62 62 62 62 64 64 64 64 64 66 66 68 68 68 70 High: 72 76 86 256 4096 Table 6: Stem plot of the XOR Profile of the LOKI S-box 10 first column, that is, with output XOR of 0. This column indicates those input pairs which have the same output XOR. Obviously, if the two input val- ues are the same, the outputs will be the same. This leads to the anomalous value of 64 in DES, and 4096 in LOKI profiles at location [0,0]. Apart from this value, if any other of the values in the column are substantially above the average, then these particular values are of use in the cryptanalysis. As in the general profile, the profile for this column shows that the prob- ablility of getting specific high values is much lower in the LOKI profile th* *an in the DES profile. This will also hinder any cryptanalysis method. 4 Conclusions In this project we have developed the design framework for a testbed of tools needed to evaluate modern block ciphers. A number of tools have been designed within this framework, and these have been used to obtain some initial results on a comparison of the DES, FEAL and LOKI ciphers. These results show that these ciphers have similar statistical and bit propogation properties. The XOR-profile analysis though, shows a significant difference between the DES and LOKI S-boxes. A number of further tools, as well as more ciphers are to be added to the testbed in future. 5 Acknowledgements Thank you to the members of the crypt group for their support and sugges- tions, and to Paul Stokes for his assistance with programming. This work has been supported by ARC grant A48830241, ATERB, and Telecom Australia research contract 7027. 6 References [1] H. Gustafson, E. Dawson and B. Caelli, "Comparison of Block Ciphers," in Advances in Cryptology: Auscrypt '90 (Lecture Notes in Computer Sci- ence), vol. 453. Berlin: Springer Verlag, pp. , 1990. [2] L. Brown, J. Pieprzyk and J. Seberry, "LOKI - A Cryptographic Primitive for Authentication and Secrecy Applications," in Advances in Cryptol- ogy: Auscrypt '90 (Lecture Notes in Computer Science), vol. 453. Berlin: Springer Verlag, pp. , 1990. [3] A. Shimizu and S. Miyaguchi, "Fast Data Encipherment Algorithm FEAL," in Eurocrypt 87 Abstracts, 1988. 11 [4] S. Miyaguchi, "The FEAL Cipher Family," Advances in Cryptology - Crypto'90, 537, pp. , 1991. [5] A. Sorkin, "Lucifer, a Cryptographic Algorithm," Cryptologia, 8, no. 1, pp. , Jan. 1984. [6] H. Beker and F. Piper, Cipher Systems: The Protection of Communica- tions. London, Northwood Books, 1982. [7] D. E. Knuth, Seminumerical Algorithms (The Art of Computer Program- ming), vol. 2. London, Addison Wesley, 1981. [8] H. van Tilborg, An Introduction to Cryptology. Mass., Kluwer Academic Press, 1988. [9] R. A. Rueppel, Analysis and Design of Stream Ciphers. Berlin, Springer Verlag, 1986. [10] R. A. Becker and J. M. Chambers, S An Interactive Environment for Data Analysis and Graphics (Wadsworth Statistical/Probability Series). Bel- mont, CA, Wadsworth, 1984. [11] L. Brown, "A Proposed Design for an Extended DES," in Computer Se- curity in the Age of Information, W. J. Caelli, Ed. Amsterdam: North- Holland, 1989. [12] L. Brown and J. Seberry, "On the Design of Permutation P in DES Type Cryptosystems," in Advances in Cryptology - Eurocrypt'89 (Lecture Notes in Computer Science), vol. 434, J. J. Quisquater and J. Vanderwalle, Eds. Berlin: Springer Verlag, pp. , 1990. [13] L. Brown and J. Seberry, "Key Scheduling in DES Type Cryptosystems," in Advances in Cryptology: Auscrypt '90 (Lecture Notes in Computer Sci- ence), vol. 453. Berlin: Springer Verlag, pp. , 1990. [14] C. H. Meyer and S. M. Matyas, Cryptography: A New Dimension in Data Security. New York, John Wiley Sons, 1982. [15] E. Biham and A. Shamir, "Differential Cryptanalysis of DES-like Cryp- tosystems," Weizmann Institute of Science, Rehovot, Israel, Technical Re- port, 19 July 1990. 12