LLOOKKII - A Cryptographic Primitive for Authentication and Secrecy Applications1 _L_a_w_r_e_n_c_e _B_r_o_w_n_, _J_o_s_e_f _P_i_e_p_r_z_y_k_, _J_e_n_n_i_f_e_r _S_e_b_e_r_r_y_, Centre for Computer Security Research, Department of Computer Science, University College, UNSW, Australian Defence Force Academy, Canberra ACT 2600. Australia. AAbbssttrraacctt This paper provides an overview of the LOKI2 encryption prim- itive which may be used to encrypt and decrypt a 64-bit block of data using a 64-bit key. The LOKI primitive may be used in any mode of operation currently defined for ISO DEA-1, with which it is interface compatible [AAA83]. Also described are two modes of operation of the LOKI primitive which compute a 64-bit, and 128-bit, Message Authentication Code (or hash value). These modes of operation may be used to provide authentication of a communications session, or of data files. 11.. IInnttrroodduuccttiioonn This paper provides an overview of the LOKI2 encryption prim- itive which may be used to encrypt and decrypt a 64-bit block of data using a 64-bit key. It has been developed as a result of work analysing the existing DEA-1, with the aim of designing a new family of encryption primitives [Bro89], [BrS90a], [BrS90b], [PiF89], [Pie90], [Pie89], [PiS89]. Its overall structure has a broad resemblance to DEA-1 (see Fig. 1), however the detailed structure has been designed to remove operations which impede analysis or hinder efficient implementation, but which do not add to the cryptographic security of the algorithm. The overall structure and the key schedule has been developed from the work done in [BrS90a] and [BrS90b], whilst the design of the S-boxes was based on [Pie89]. ____________________ 1 this paper was presented at Auscrypt90, in Sydney, Aus- tralia, January 1990 2 LOKI - God of mischief and trickery in Scandinavian mythology. "He is handsome and well made, but of a very fickle mood and most evil disposition. He is of the giant race, but forced himself into the company of the gods, and seems to take pleasure in bringing them into difficulties, and in extracting them out of the danger by his cunning, wit and skill" [Bulfinch's Mythology, Avenel Books, NY 1978]. TTRR CCSS9900//11 LLOOKKII -- AA CCrryyppttooggrraapphhiiccBBPPrrrrooiiwwmmnnii,,ttiiPPvviieeeepprrzzyykk,, SSeebbeerrrryy The LOKI primitive may be used in any mode of operation cur- rently defined for ISO DEA-1, with which it is interface com- patible [AAA83]. Also described are two modes of operation of the LOKI primitive which compute a 64-bit, and 128-bit, Message Authentication Code (or hash value) respectively, from an arbitrary length of message input. The modes of use are modifications of those described in [DaP89], [Win83], and [QuG90]. These modes of operation may be used to provide authentication of a communications session, or of data files. The LOKI encryption primitive, and the above modes of use have been submitted to the European RIPE project for evalua- tion [VCF90]. 22.. TThhee LLOOKKII CCrryyppttooggrraapphhiicc PPrriimmiittiivvee 22..11.. OOvveerrvviieeww The LOKI DEA is a family of ciphers designed to encrypt and decrypt blocks of data consisting of 64 bits, under control of a 64-bit key. This Annex defines a common variant of the algorithm for use when compatibility between implementations is required. The same structure, but with alternate substitu- tion functions may be used to build private variants of this algorithm. The same key is used for both encryption and decryption, but with the schedule of addressing the key bits altered so that the decryption process is the reverse of the encryption process. A block to be encrypted is added modulo 2 to the key, is then processed in 16 rounds of a complex key- dependent computation, and finally is added modulo 2 to the key again. The key-dependent computation can be defined in terms of a confusion-diffusion function _f, and a key schedule KS. Descriptions of the encryption operation, the decryption operation, and the definition of the function _f, are provided in the following sections. The representation of the keys, key values to be avoided and guidelines for the construction of alternate private ciphers, and full results for the tests conducted to date on LOKI, are described in the Appendices. 22..22.. EEnnccrryyppttiioonn The encryption computation is illustrated in Fig 1. The 64 bits of the input block to be encrypted are added modulo 2 to the key, processed in 16 rounds of a complex key-dependent computation, and finally added modulo 2 to the key again. In detail, the 64-bit input block X is partitioned into two 32-bit blocks XL and XR. Similarly, the 64-bit key is parti- tioned into two 32-bit blocks _K_L and _K_R. Corresponding halves are added together modulo 2, to form the initial left and right halves for the following 16 rounds, thus: _L0=_X_L_X_O_R_K_L0 _K_L0=_K_L [Eq.1] _R0=_X_R_X_O_R_K_R0 _K_R0=_K_R -- 22 -- TTRR CCSS9900//11 LLOOKKII -- AA CCrryyppttooggrraapphhiiccBBPPrrrrooiiwwmmnnii,,ttiiPPvviieeeepprrzzyykk,, SSeebbeerrrryy The complex key-dependent computation consists (except for a final interchange of blocks) of 16 rounds (iterations) of a set of operations. Each iteration includes the calculation of the encryption function _f. This is a concatenation of a modulo 2 addition and three functions _E, _S, and _P. Function _f takes as input the 32-bit right data half _R_i-1 and the 32-bit left key half _K_L_i produced by the key schedule KS (denoted _K_i below), and which produces a 32-bit result which is added modulo 2 to the left data half _L_i-1. The two data halves are then interchanged (except after the last round). Each round may thus be characterised as: _L_i=_R_i-1 _R_i=_L_i-1_X_O_R_f(_R_i-1,_K_L_i) [Eq.2] _f(_R_i-1,_K_i)=_P(_S(_E(_R_i-1_X_O_R_K_i))) The component functions _E, _S, and _P are described later. The key schedule KS is responsible for deriving the sub-keys _K_i, and is defined as follows: the 64-bit key _K is parti- tioned into two 32-bit halves _K_L and _K_R. In each round _i, the sub-key _K_i is the current left half of the key _K_L_i-1. This half is then rotated 12 bits to the left, and the key halves are interchanged. This may be defined thus: _K_i=_K_L_i-1 _K_L_i=_K_R_i-1 [Eq.3] _K_R_i=_R_O_L(_K_L_i-1,12) Finally after the 16 rounds, the other key halves are added modulo 2 to the data halves to form two output block halves _Y_L and _Y_R which are then concatenated together to form the output block _Y. This is defined as follows (note the swap of data and key halves to undo the final interchange in [Eq.2] and [Eq.3]): _Y_L=_R16_X_O_R_K_R16 _Y_R=_L16_X_O_R_K_L16 [Eq.4] _Y=_Y_L|_Y_R 22..33.. DDeeccrryyppttiioonn The decryption computation is identical to that used for encryption, save that the partial keys used as input to the -- 33 -- TTRR CCSS9900//11 LLOOKKII -- AA CCrryyppttooggrraapphhiiccBBPPrrrrooiiwwmmnnii,,ttiiPPvviieeeepprrzzyykk,, SSeebbeerrrryy function _f in each round are calculated in reverse order, and the initial and final additions of key to data modulo 2 use the opposite halves of the key (interchange _K_L0 and _K_R0 in [Eq.1] and _K_L16 and _K_R16 in [Eq.3]). The calculation of the partial keys for decryption consists of first exchanging key halves, then rotating the left half 12 bits to the right, and then using the left half as the partial key. This is defined as: _K_R_i=_K_L_i-1 _K_L_i=_R_O_R(_K_R_i-1,12) [Eq.5] _K_i=_K_L_i 22..44.. FFuunnccttiioonn _f The encryption function _f is a concatenation of a modulo 2 addition and three functions _E, _S, and _P, which takes as input the 32-bit right data half _R_i-1 and the 32-bit left key half _K_L_i, and produces a 32-bit result which is added modulo 2 to the left data half _L_i-1. This is shown in Fig 2, and is defined thus: _f(_R_i-1,_K_i)=_P(_S(_E(_R_i-1_X_O_R_K_i))) [Eq.6] The modulo 2 addition of the key and data halves ensures that the output of _f will be a complex function of both of these values. The expansion function _E takes a 32-bit input and produces a 48-bit output block, composed of four 12-bit blocks which form the inputs to four S-boxes in function _f. Function _E selects consecutive blocks of twelve bits as inputs to S- boxes S(4), S(3), S(2), and S(1) respectively, as follows: [_b3_b2..._b0_b31_b30..._b24] [_b27_b26..._b16] [_b19_b18..._b8] [_b11_b10..._b0] This is shown in Table 1 in full. -- 44 -- TTRR CCSS9900//11 LLOOKKII -- AA CCrryyppttooggrraapphhiiccBBPPrrrrooiiwwmmnnii,,ttiiPPvviieeeepprrzzyykk,, SSeebbeerrrryy +----------------------------------------------------------+ | TTaabbllee 11 -- LLOOKKII EExxppaannssiioonn FFuunnccttiioonn _E | +----------------------------------------------------------+ |3 2 1 0 31 30 29 28 27 26 25 24 | |27 26 25 24 23 22 21 20 19 18 17 16 | |19 18 17 16 15 14 13 12 11 10 9 8 | |11 10 9 8 7 6 5 4 3 2 1 0 | +----------------------------------------------------------+ The substitution function _S provides the confusion component in the LOKI cipher. It takes a 48-bit input and produces a 32-bit output. It is composed of four S-boxes, each of which takes a 12-bit input and produces an 8-bit output, which are concatenated together to form the 32-bit output of _S. The 8-bit output from S(4) becomes the most significant byte (bits [31...24]), then the outputs from S(3) (bits[23...16]), S(2) (bits[15...8]), and S(1) (bits [7...0]). In this Annex, the four S-boxes are identical. The form of each S-box is shown in Fig 3. The 12-bit input is partitioned into two seg- ments: a 4-bit row value _r formed from bits [_b11_b10_b1_b0], and an 8-bit column value _c formed from bits [_b9_b8..._b3_b2]. The row value _r is used to select one of 16 S-functions Sfn_r, which then take as input the column value _c and produce an 8-bit output value. This is defined as: Sfn_r=(_c_X_O_R_r)_e_rmodgen_r, inGF(28) [Eq.7] where gen_r is an irreducible polynomial in GF(28), and _e_r is the exponent used in forming the _rth S-box. The generators and exponents to be used in the 16 S-functions Sfn_r in the standard LOKI are specified in Table 2. The permutation function _P provides diffusion of the outputs from the four S-boxes across the inputs of all S-boxes in the next round. It takes the 32-bit concatenated outputs from the S-boxes, and distributes them over all the inputs for the next round via a regular wire crossing which takes bits from the outputs of each S-box in turn, as defined in Table 3. 22..55.. TTeesstt DDaattaa A single test triplet for the LOKI primitive is listed below. # Single LOKI Certification triplet # data is saved as (key, plaintext, ciphertext) triplets # 5b5a57676a56676e 675a69675e5a6b5a 3c61fa7e2e99d048 -- 55 -- TTRR CCSS9900//11 LLOOKKII -- AA CCrryyppttooggrraapphhiiccBBPPrrrrooiiwwmmnnii,,ttiiPPvviieeeepprrzzyykk,, SSeebbeerrrryy +-------------------------------+-------+----------------------------+ | TTaabbllee 22 -- LLOOKKII SS--bbooxx | TTaabbll|ee 33 -- LLOOKKII PPeerrmmuuttaattiioonn PP | |IIrrrreedduucciibbllee PPoollyynnoommiiaallss aanndd EExxpp+oo-nn-ee-nn-tt-ss--+----------------------------+ +------------+--------------+---+-3-1----2-3+ 15 7 30 22 14 6 | | Row | gen_r | |e2_r9 21| 13 5 28 20 12 4 | +------------+--------------+---+-2-7----1-9+ 11 3 26 18 10 2 | | 0 | 375 | |3215 17| 9 1 24 16 8 0 | | 1 | 379 | +-3-1-----+----------------------------+ | 2 | 391 | 31 | | 3 | 395 | 31 | | 4 | 397 | 31 | | 5 | 415 | 31 | | 6 | 419 | 31 | | 7 | 425 | 31 | | 8 | 433 | 31 | | 9 | 445 | 31 | | 10 | 451 | 31 | | 11 | 463 | 31 | | 12 | 471 | 31 | | 13 | 477 | 31 | | 14 | 487 | 31 | | 15 | 499 | 31 | +------------+--------------+-----------+ LOKI Fig 1 here -- 66 -- TTRR CCSS9900//11 LLOOKKII -- AA CCrryyppttooggrraapphhiiccBBPPrrrrooiiwwmmnnii,,ttiiPPvviieeeepprrzzyykk,, SSeebbeerrrryy LOKI Figs 2, 3 here 33.. AAddddiittiioonnaall MMooddeess ooff UUssee The LOKI primitive may also be used in any mode of operation currently defined for ISO DEA-1, with which it is interface compatible [AAA83]. In addition, two modes of use are defined using the LOKI primitive for the purpose of providing message authentication. The Single Block Hash (SBH) mode computes a 64-bit Message Authentication Code (MAC or hash value), from an arbitrary length of message input. The Double Block Hash (DBH) mode computes a 128-bit MAC from an arbi- trary length of message input. In the following definitions, the LOKI primitive used for encryption is denoted _Y=_E_L_K(_X). That is, _Y is a 64-bit block formed by encrypting input _X using the LOKI primitive with key _K. 33..11.. SSiinnggllee BBlloocckk HHaasshh ((SSBBHH)) MMooddee The SBH mode is defined as follows. Data for which a hash is to be computed is divided into 64-bit blocks, the final block being padded with nulls if required. A 64-bit key is sup- plied, and is used as the initial hash value _I_V. For each message block _M_i: that block is added modulo 2 to the previ- ous hash value to form a key. That key is used to encrypt the previous hash value. The encrypted value is added modulo 2 to the previous hash value to form the new hash value (see Fig 4). The SBH code is the final hash value formed. This process may be summarised as: _H0=_I_V _H_i=_E_L_M_i_X_O_R_H_i-1(_H_i-1)_X_O_R_H_i-1 -- 77 -- TTRR CCSS9900//11 LLOOKKII -- AA CCrryyppttooggrraapphhiiccBBPPrrrrooiiwwmmnnii,,ttiiPPvviieeeepprrzzyykk,, SSeebbeerrrryy _S_B_H=_H_n The SBH mode is a variant of the Davies and Meyer hash func- tion described in [DaP89], [Win83]. The major extension is the addition modulo 2 of the previous hash value to the cur- rent message block before using it as key input to the LOKI primitive. This was desired to prevent weak keys being sup- plied to the primitive when the message data was constant. If the Initialization Value is chosen not to be a weak key, then the chance of generating a weak key from a given message stream should be greatly reduced. 33..22.. DDoouubbllee BBlloocckk HHaasshh ((DDBBHH)) MMooddee The DBH mode is defined as follows. Data for which a hash is to be computed is divided into pairs of 64-bit blocks _M2_i+1, _M2_i+2, the final block being padded with nulls if required. A 128-bit key is supplied, composed of two 64-bit blocks, which are used as the initial hash values _I_V-1, _I_V0. _H-1=_I_V-1 _H0=_I_V0 For each pair of message blocks _M2_i+1 _M2_i+2, the following calculation is performed (see Fig 5): _T=_E_L_M2_i+1_X_O_R_H2_i-1(_H2_i-1_X_O_R_M2_i+2)_X_O_R_M2_i+2_X_O_R_H2_i _H2_i+1=_E_L_M2_i+2_X_O_R_H2_i(_T_X_O_R_M2_i+1)_X_O_R_M2_i+1_X_O_R_H2_i-1_X_O_R_H2_i _H2_i+2=_T_X_O_R_H2_i-1 The DBH block is formed by concatenating the final two hash values as follows: _D_B_H=_H_n-1|_H_n The DBH mode is derived from that proposed by Quisquater and Girault [QuG90]. Again it was extended by the addition mod- ulo 2 of the previous hash value to the current message block before using it as key input to the LOKI primitive. -- 88 -- TTRR CCSS9900//11 LLOOKKII -- AA CCrryyppttooggrraapphhiiccBBPPrrrrooiiwwmmnnii,,ttiiPPvviieeeepprrzzyykk,, SSeebbeerrrryy LOKI Figs 4, 5 here -- 99 -- TTRR CCSS9900//11 LLOOKKII -- AA CCrryyppttooggrraapphhiiccBBPPrrrrooiiwwmmnnii,,ttiiPPvviieeeepprrzzyykk,, SSeebbeerrrryy 44.. CCoonncclluussiioonn The LOKI cryptographic primitive, and its associated modes of use for message authentication have been described. This algorithm is currently undergoing evaluation and testing by several parties. AAcckknnoowwlleeddggeemmeennttss To the members of the Centre for Computer Security Research, and the staff of the Department of Computer Science for their help and suggestions. Thankyou. BBiibblliiooggrraapphhyy [AAA83] "_I_n_f_o_r_m_a_t_i_o_n _I_n_t_e_r_c_h_a_n_g_e _- _D_a_t_a _E_n_c_r_y_p_t_i_o_n _A_l_g_o_r_i_t_h_m _- _M_o_d_e_s _o_f _O_p_e_r_a_t_i_o_n," American National Standards Institute X3.106-1983, American National Standards Institute, New York, 1983. [Bro89] L. Brown, "A Proposed Design for an Extended DES," in _C_o_m_p_u_t_e_r _S_e_c_u_r_i_t_y _i_n _t_h_e _A_g_e _o_f _I_n_f_o_r_m_a_t_i_o_n, W. J. Caelli (editor), North-Holland, Amsterdam, 1989. [BrS90a] L. Brown and J. Seberry, "On the Design of Permutation P in DES Type Cryptosystems," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y _- _E_u_r_o_c_r_y_p_t_'_8_9, Lecture Notes in Computer Science, no. 434, J. J. Quisquater and J. Vanderwalle (editors), pp. 696-705, |Springer Verlag|, Berlin, 1990. [BrS90b] L. Brown and J. Seberry, "Key Scheduling in DES Type Cryptosystems," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y_: _A_u_s_c_r_y_p_t _'_9_0, Lecture Notes in Computer Science, no. 453, pp. 221-228, |Springer Verlag|, Berlin, 1990. [DaP89] D. W. Davies and W. L. Price, _S_e_c_u_r_i_t_y _f_o_r _C_o_m_p_u_t_e_r _N_e_t_w_o_r_k_s, John Wiley and Sons, New York, 1989. (2nd edn). [Mey78] C. H. Meyer, "Ciphertext/plaintext and ciphertext/key dependence vs number of rounds for the data encryption standard," in _A_F_I_P_S _|_C_o_n_f_._| _|_P_r_o_c_._| _4_7, pp. 1119-1126, AFIPS Press, Montvale NJ, USA, |June| 1978. [MeM82] C. H. Meyer and S. M. Matyas, _C_r_y_p_t_o_g_r_a_p_h_y_: _A _N_e_w _D_i_m_e_n_s_i_o_n _i_n _D_a_t_a _S_e_c_u_r_i_t_y, |John Wiley & Sons, New York, 1982. [PiF89] J. Pieprzyk and G. Finkelstein, "Permutations that Maximize Non-Linearity and Their Cryptographic Significance," in _C_o_m_p_u_t_e_r _S_e_c_u_r_i_t_y _i_n _t_h_e _A_g_e _o_f _I_n_f_o_r_m_a_t_i_o_n, W. J. Caelli (editor), North-Holland, Amsterdam, 1989. -- 1100 -- TTRR CCSS9900//11 LLOOKKII -- AA CCrryyppttooggrraapphhiiccBBPPrrrrooiiwwmmnnii,,ttiiPPvviieeeepprrzzyykk,, SSeebbeerrrryy [Pie89] J. Pieprzyk, "Error Propagation Property and Application in Cryptography," _I_E_E _P_r_o_c_e_e_d_i_n_g_s_-_E_, _C_o_m_p_u_t_e_r_s _a_n_d _D_i_g_i_t_a_l _T_e_c_h_n_i_q_u_e_s, vol. 136, no. 4, pp. 262-270, |July| 1989. [PiS89] J. Pieprzyk and J. Seberry, "_R_e_m_a_r_k_s _o_n _E_x_t_e_n_s_i_o_n _o_f _D_E_S _- _W_h_i_c_h _W_a_y _t_o _G_o_?," Tech. Rep. CS89/4, |Dept. of Computer Science, UC UNSW, Australian Defence Force Academy|, Canberra, Australia, |February.| 1989. [Pie90] J. Pieprzyk, "Non-Linearity of Exponent Permutations," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y _- _E_u_r_o_c_r_y_p_t_'_8_9, Lecture Notes in Computer Science, no. 434, J. J. Quisquater and J. Vanderwalle (editors), pp. 80-92, |Springer Verlag|, Berlin, 1990. [QuG90] J. Quisquater and M. Girault, "2n-Bit Hash Functions Using n-Bit Symmetric Block Cipher Algorithms," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y _- _E_u_r_o_c_r_y_p_t_'_8_9, Lecture Notes in Computer Science, no. 434, J. J. Quisquater and J. Vanderwalle (editors), pp. 102-109, |Springer Verlag|, Berlin, 1990. [VCF90] J. Vandewalle, D. Chaum, W. Fumy, C. Janssen, P. Landrock and G. Roelofsen, "A European Call for Cryptographic Algorithms: RIPE RACE Integrity Primitives Evaluation," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y _- _E_u_r_o_c_r_y_p_t_'_8_9, Lecture Notes in Computer Science, no. 434, J. J. Quisquater and J. Vanderwalle (editors), pp. 267-271, |Springer Verlag|, Berlin, 1990. [Win83] R. S. Winternitz, "Producing a One-Way Hash Function from DES," in _A_d_v_a_n_c_e_s _i_n _C_r_y_p_t_o_l_o_g_y _- _|_P_r_o_c_._| _o_f _C_r_y_p_t_o _8_3, D. Chaum, R. L. Rivest and A. T. Sherman (editors), pp. 203-207, Plenum Press, New York, |August.| 22-24, 1983. -- 1111 -- TTRR CCSS9900//11 LLOOKKII -- AA CCrryyppttooggrraapphhiiccBBPPrrrrooiiwwmmnnii,,ttiiPPvviieeeepprrzzyykk,, SSeebbeerrrryy AAppppeennddiixx 11 -- KKeeyy RReepprreesseennttaattiioonn aanndd CChhooiiccee INTRODUCTION LOKI keys are 64-bit blocks, numbered as specified in section 2. These keys may be written in hexadecimal thus: hhhhhhhhhhhhhhhh, where h is one hex (4-bit) digit. All 64 bits of the key are used in the LOKI algorithm and contribute to the confusion-diffusion process. There is no concept of parity bits in the key. Valid keys may thus cover the range 000000000000000016 to ffffffffffffffff16. CHOICE OF KEYS The cryptographic strength of the LOKI algorithm is greatly reduced if only a small number of internal sub- keys are generated. Thus keys which produce such sub- keys should be avoided. Weak are those which result in only a single sub-key being formed on all 16 rounds. These keys thus form their own decryption key, and have the form: hhhhhhhhhhhhhhhh16, he[0.._f]. There are 16 such keys. Semi-Weak are those which result in two sub-keys being formed on alternate rounds. These keys thus form mutual pairs, each being the decryption key for the other, and have the form: hhhhhhhhiiiiiiii16, h,ie[0.._f], h!=i. There are 240 such keys. Demi-Semi-Weak are those which result in four sub-keys being formed on successive rounds. It is not known whether these form a security risk, but it is generally accepted that they should be avoided. They have the form: hihihihijkjkjkjk16, h,i,j,ke[0.._f], h!=i!=j!=k. There are 65280 such keys. CONCLUSION In brief, the keys to be avoided may be described as all keys of the form: hihihihijkjkjkjk16, h,i,j,ke[0.._f]; that is where both the first four bytes are identical, and the second four bytes are also identical, and thus are very easy to test for and exclude. There are a total of 65536 (ie 216) keys to be avoided out of a total key space of 264, a very small fraction of the available number of keys. -- 1122 -- TTRR CCSS9900//11 LLOOKKII -- AA CCrryyppttooggrraapphhiiccBBPPrrrrooiiwwmmnnii,,ttiiPPvviieeeepprrzzyykk,, SSeebbeerrrryy AAppppeennddiixx 22 -- DDeeppeennddeennccyy AAnnaallyyssiiss ffoorr tthhee LLOOKKII PPrriimmiittiivvee To provide a measure of the effectiveness of the derived permutations, Meyer's analysis [Mey78], [MeM82] of ciphertext dependence on key bits (CKdep) and plaintext bits (CPdep) was used in the design of the overall structure of LOKI. Briefly, following Meyer, this analysis may be described as follows. To provide a measure of the dependency of ciphertext bits on plaintext bits, a 64*64 array _G_a,_b is formed. Each element _G_a,_b(_i,_j) specifies a dependency of output bit _X(_j) on input bit _X(_i), between rounds _a and _b. The number of marked elements in _G0,_r indicates the degree to which complete dependence was achieved by round _r. Similarly, the dependency of ciphertext bits on key bits is measured by forming a 64*64 array _F_a,_b, each element of which specifies a dependency of output bit _X(_j) on key bit _K(_i). Again, the number of marked elements in _F0,_r will be examined to provide a profile of the degree of dependence achieved by round _r. Details of the derivation of these matrices, and the means by which entries are propagated, may be found in [MeM82]. The matrices found for the LOKI primitive are listed below (x specifies message dependency, - specifies autoclave dependency, * specifies dependencies via both message and autoclave inputs): LLOOKKII CCKKddeepp AAnnaallyyssiiss -- 1133 -- TTRR CCSS9900//11 LLOOKKII -- AA CCrryyppttooggrraapphhiiccBBPPrrrrooiiwwmmnnii,,ttiiPPvviieeeepprrzzyykk,, SSeebbeerrrryy Round 1: None 3276, Msg 564, Autoclave 256, Both 0, Err 0 CKdep: 0.00,20.02 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 x 11 x 12 x 13 x 14 x 15 x 16 x 17 x 18 x 19 x 20 x 21 x 22 x 23 x 24 x 25 x 26 x 27 x 28 x 29 x 30 x 31 x 32 x 33 xxxxxx-- --xxxxxxxx-- --xx 34 x --xxxxxxxx-- --xxxxxxxx-- 35 x --xxxxxxxx-- --xxxxxxxx-- 36 x --xxxxxxxx-- --xxxxxxxx-- 37 xxxxxx-- --xxxxxxxx-- --xx 38 --xxxxxxxx-- --xxxxxxxx-- 39 x --xxxxxxxx-- --xxxxxxxx-- 40 x --xxxxxxxx-- --xxxxxxxx-- 41 xxxxxx--x --xxxxxxxx-- --xx 42 --xxxxxxxx-- --xxxxxxxx-- 43 x --xxxxxxxx-- --xxxxxxxx-- 44 x --xxxxxxxx-- --xxxxxxxx-- 45 xxxxxx-- x --xxxxxxxx-- --xx 46 --xxxxxxxx-- --xxxxxxxx-- 47 --xxxxxxxx-- --xxxxxxxx-- 48 x --xxxxxxxx-- --xxxxxxxx-- 49 xxxxxx-- x --xxxxxxxx-- --xx 50 --xxxxxxxx-- x --xxxxxxxx-- 51 --xxxxxxxx-- --xxxxxxxx-- 52 x--xxxxxxxx-- --xxxxxxxx-- 53 xxxxxx-- x --xxxxxxxx-- --xx 54 --xxxxxxxx-- x --xxxxxxxx-- -- 1144 -- TTRR CCSS9900//11 LLOOKKII -- AA CCrryyppttooggrraapphhiiccBBPPrrrrooiiwwmmnnii,,ttiiPPvviieeeepprrzzyykk,, SSeebbeerrrryy 55 --xxxxxxxx-- --xxxxxxxx-- 56 --xxxxxxxx-- --xxxxxxxx-- 57 xxxxxx-- x --xxxxxxxx-- --xx 58 --xxxxxxxx-- x --xxxxxxxx-- 59 --xxxxxxxx-- x --xxxxxxxx-- 60 --xxxxxxxx-- --xxxxxxxx-- 61 xxxxxx-- --xxxxxxxx-- --xx 62 --xxxxxxxx-- x --xxxxxxxx-- 63 --xxxxxxxx-- x --xxxxxxxx-- 64 --xxxxxxxx-- --xxxxxxxx-- -- 1155 -- TTRR CCSS9900//11 LLOOKKII -- AA CCrryyppttooggrraapphhiiccBBPPrrrrooiiwwmmnnii,,ttiiPPvviieeeepprrzzyykk,, SSeebbeerrrryy Round 2: None 1260, Msg 532, Autoclave 256, Both 2048, Err 0 CKdep: 50.00,69.24 1 xxxxxx-- --xxxxxxxx-- --xx 2 x --xxxxxxxx-- --xxxxxxxx-- 3 x --xxxxxxxx-- --xxxxxxxx-- 4 x --xxxxxxxx-- --xxxxxxxx-- 5 xxxxxx-- --xxxxxxxx-- --xx 6 --xxxxxxxx-- --xxxxxxxx-- 7 x --xxxxxxxx-- --xxxxxxxx-- 8 x --xxxxxxxx-- --xxxxxxxx-- 9 xxxxxx--x --xxxxxxxx-- --xx 10 --xxxxxxxx-- --xxxxxxxx-- 11 x --xxxxxxxx-- --xxxxxxxx-- 12 x --xxxxxxxx-- --xxxxxxxx-- 13 xxxxxx-- x --xxxxxxxx-- --xx 14 --xxxxxxxx-- --xxxxxxxx-- 15 --xxxxxxxx-- --xxxxxxxx-- 16 x --xxxxxxxx-- --xxxxxxxx-- 17 xxxxxx-- x --xxxxxxxx-- --xx 18 --xxxxxxxx-- x --xxxxxxxx-- 19 --xxxxxxxx-- --xxxxxxxx-- 20 x--xxxxxxxx-- --xxxxxxxx-- 21 xxxxxx-- x --xxxxxxxx-- --xx 22 --xxxxxxxx-- x --xxxxxxxx-- 23 --xxxxxxxx-- --xxxxxxxx-- 24 --xxxxxxxx-- --xxxxxxxx-- 25 xxxxxx-- x --xxxxxxxx-- --xx 26 --xxxxxxxx-- x --xxxxxxxx-- 27 --xxxxxxxx-- x --xxxxxxxx-- 28 --xxxxxxxx-- --xxxxxxxx-- 29 xxxxxx-- --xxxxxxxx-- --xx 30 --xxxxxxxx-- x --xxxxxxxx-- 31 --xxxxxxxx-- x --xxxxxxxx-- 32 --xxxxxxxx-- --xxxxxxxx-- 33 **************************************************************** 34 **************************************************************** 35 **************************************************************** 36 **************************************************************** 37 **************************************************************** 38 **************************************************************** 39 **************************************************************** 40 **************************************************************** 41 **************************************************************** 42 **************************************************************** 43 **************************************************************** 44 **************************************************************** 45 **************************************************************** 46 **************************************************************** 47 **************************************************************** 48 **************************************************************** 49 **************************************************************** 50 **************************************************************** 51 **************************************************************** 52 **************************************************************** 53 **************************************************************** 54 **************************************************************** -- 1166 -- TTRR CCSS9900//11 LLOOKKII -- AA CCrryyppttooggrraapphhiiccBBPPrrrrooiiwwmmnnii,,ttiiPPvviieeeepprrzzyykk,, SSeebbeerrrryy 55 **************************************************************** 56 **************************************************************** 57 **************************************************************** 58 **************************************************************** 59 **************************************************************** 60 **************************************************************** 61 **************************************************************** 62 **************************************************************** 63 **************************************************************** 64 **************************************************************** -- 1177 -- TTRR CCSS9900//11 LLOOKKII -- AA CCrryyppttooggrraapphhiiccBBPPrrrrooiiwwmmnnii,,ttiiPPvviieeeepprrzzyykk,, SSeebbeerrrryy Round 3: None 0, Msg 0, Autoclave 0, Both 4096, Err 0 CKdep: 100.00,100.00 1 **************************************************************** 2 **************************************************************** 3 **************************************************************** 4 **************************************************************** 5 **************************************************************** 6 **************************************************************** 7 **************************************************************** 8 **************************************************************** 9 **************************************************************** 10 **************************************************************** 11 **************************************************************** 12 **************************************************************** 13 **************************************************************** 14 **************************************************************** 15 **************************************************************** 16 **************************************************************** 17 **************************************************************** 18 **************************************************************** 19 **************************************************************** 20 **************************************************************** 21 **************************************************************** 22 **************************************************************** 23 **************************************************************** 24 **************************************************************** 25 **************************************************************** 26 **************************************************************** 27 **************************************************************** 28 **************************************************************** 29 **************************************************************** 30 **************************************************************** 31 **************************************************************** 32 **************************************************************** 33 **************************************************************** 34 **************************************************************** 35 **************************************************************** 36 **************************************************************** 37 **************************************************************** 38 **************************************************************** 39 **************************************************************** 40 **************************************************************** 41 **************************************************************** 42 **************************************************************** 43 **************************************************************** 44 **************************************************************** 45 **************************************************************** 46 **************************************************************** 47 **************************************************************** 48 **************************************************************** 49 **************************************************************** 50 **************************************************************** 51 **************************************************************** 52 **************************************************************** 53 **************************************************************** 54 **************************************************************** -- 1188 -- TTRR CCSS9900//11 LLOOKKII -- AA CCrryyppttooggrraapphhiiccBBPPrrrrooiiwwmmnnii,,ttiiPPvviieeeepprrzzyykk,, SSeebbeerrrryy 55 **************************************************************** 56 **************************************************************** 57 **************************************************************** 58 **************************************************************** 59 **************************************************************** 60 **************************************************************** 61 **************************************************************** 62 **************************************************************** 63 **************************************************************** 64 **************************************************************** -- 1199 -- TTRR CCSS9900//11 LLOOKKII -- AA CCrryyppttooggrraapphhiiccBBPPrrrrooiiwwmmnnii,,ttiiPPvviieeeepprrzzyykk,, SSeebbeerrrryy LLOOKKII CCPPddeepp AAnnaallyyssiiss -- 2200 -- TTRR CCSS9900//11 LLOOKKII -- AA CCrryyppttooggrraapphhiiccBBPPrrrrooiiwwmmnnii,,ttiiPPvviieeeepprrzzyykk,, SSeebbeerrrryy Round 1: None 3616, Msg 352, Autoclave 128, Both 0, Err 0 CPdep: 0.00,11.72 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 x 11 x 12 x 13 x 14 x 15 x 16 x 17 x 18 x 19 x 20 x 21 x 22 x 23 x 24 x 25 x 26 x 27 x 28 x 29 x 30 x 31 x 32 x 33 x xxxxxxx-- --xx 34 x --xxxxxxxxx-- 35 x --xxxxxxxxx-- 36 x - --xxxxxxxxx- 37 x xxxxxxx-- --xx 38 x --xxxxxxxxx-- 39 x --xxxxxxxxx-- 40 x - --xxxxxxxxx- 41 x xxxxxxx-- --xx 42 x --xxxxxxxxx-- 43 x --xxxxxxxxx-- 44 x - --xxxxxxxxx- 45 x xxxxxxx-- --xx 46 x --xxxxxxxxx-- 47 x --xxxxxxxxx-- 48 x - --xxxxxxxxx- 49 x xxxxxxx-- --xx 50 x --xxxxxxxxx-- 51 x --xxxxxxxxx-- 52 x - --xxxxxxxxx- 53 x xxxxxxx-- --xx 54 x --xxxxxxxxx-- -- 2211 -- TTRR CCSS9900//11 LLOOKKII -- AA CCrryyppttooggrraapphhiiccBBPPrrrrooiiwwmmnnii,,ttiiPPvviieeeepprrzzyykk,, SSeebbeerrrryy 55 x --xxxxxxxxx-- 56 x - --xxxxxxxxx- 57 x xxxxxxx-- --xx 58 x --xxxxxxxxx-- 59 x --xxxxxxxxx-- 60 x - --xxxxxxxxx- 61 x xxxxxxx-- --xx 62 x --xxxxxxxxx-- 63 x --xxxxxxxxx-- 64 x- --xxxxxxxxx- -- 2222 -- TTRR CCSS9900//11 LLOOKKII -- AA CCrryyppttooggrraapphhiiccBBPPrrrrooiiwwmmnnii,,ttiiPPvviieeeepprrzzyykk,, SSeebbeerrrryy Round 2: None 2240, Msg 576, Autoclave 256, Both 1024, Err 0 CPdep: 25.00,45.31 1 x xxxxxxx-- --xx 2 x --xxxxxxxxx-- 3 x --xxxxxxxxx-- 4 x - --xxxxxxxxx- 5 x xxxxxxx-- --xx 6 x --xxxxxxxxx-- 7 x --xxxxxxxxx-- 8 x - --xxxxxxxxx- 9 x xxxxxxx-- --xx 10 x --xxxxxxxxx-- 11 x --xxxxxxxxx-- 12 x - --xxxxxxxxx- 13 x xxxxxxx-- --xx 14 x --xxxxxxxxx-- 15 x --xxxxxxxxx-- 16 x - --xxxxxxxxx- 17 x xxxxxxx-- --xx 18 x --xxxxxxxxx-- 19 x --xxxxxxxxx-- 20 x - --xxxxxxxxx- 21 x xxxxxxx-- --xx 22 x --xxxxxxxxx-- 23 x --xxxxxxxxx-- 24 x - --xxxxxxxxx- 25 x xxxxxxx-- --xx 26 x --xxxxxxxxx-- 27 x --xxxxxxxxx-- 28 x - --xxxxxxxxx- 29 x xxxxxxx-- --xx 30 x --xxxxxxxxx-- 31 x --xxxxxxxxx-- 32 x- --xxxxxxxxx- 33 xxxxxx-- --xx******************************** 34 --xxxxxxxx-- ******************************** 35 --xxxxxxxx-- ******************************** 36 --xxxxxxxx--******************************** 37 xxxxxx-- --xx******************************** 38 --xxxxxxxx-- ******************************** 39 --xxxxxxxx-- ******************************** 40 --xxxxxxxx--******************************** 41 xxxxxx-- --xx******************************** 42 --xxxxxxxx-- ******************************** 43 --xxxxxxxx-- ******************************** 44 --xxxxxxxx--******************************** 45 xxxxxx-- --xx******************************** 46 --xxxxxxxx-- ******************************** 47 --xxxxxxxx-- ******************************** 48 --xxxxxxxx--******************************** 49 xxxxxx-- --xx******************************** 50 --xxxxxxxx-- ******************************** 51 --xxxxxxxx-- ******************************** 52 --xxxxxxxx--******************************** 53 xxxxxx-- --xx******************************** 54 --xxxxxxxx-- ******************************** -- 2233 -- TTRR CCSS9900//11 LLOOKKII -- AA CCrryyppttooggrraapphhiiccBBPPrrrrooiiwwmmnnii,,ttiiPPvviieeeepprrzzyykk,, SSeebbeerrrryy 55 --xxxxxxxx-- ******************************** 56 --xxxxxxxx--******************************** 57 xxxxxx-- --xx******************************** 58 --xxxxxxxx-- ******************************** 59 --xxxxxxxx-- ******************************** 60 --xxxxxxxx--******************************** 61 xxxxxx-- --xx******************************** 62 --xxxxxxxx-- ******************************** 63 --xxxxxxxx-- ******************************** 64 --xxxxxxxx--******************************** -- 2244 -- TTRR CCSS9900//11 LLOOKKII -- AA CCrryyppttooggrraapphhiiccBBPPrrrrooiiwwmmnnii,,ttiiPPvviieeeepprrzzyykk,, SSeebbeerrrryy Round 3: None 640, Msg 256, Autoclave 128, Both 3072, Err 0 CPdep: 75.00,84.38 1 xxxxxx-- --xx******************************** 2 --xxxxxxxx-- ******************************** 3 --xxxxxxxx-- ******************************** 4 --xxxxxxxx--******************************** 5 xxxxxx-- --xx******************************** 6 --xxxxxxxx-- ******************************** 7 --xxxxxxxx-- ******************************** 8 --xxxxxxxx--******************************** 9 xxxxxx-- --xx******************************** 10 --xxxxxxxx-- ******************************** 11 --xxxxxxxx-- ******************************** 12 --xxxxxxxx--******************************** 13 xxxxxx-- --xx******************************** 14 --xxxxxxxx-- ******************************** 15 --xxxxxxxx-- ******************************** 16 --xxxxxxxx--******************************** 17 xxxxxx-- --xx******************************** 18 --xxxxxxxx-- ******************************** 19 --xxxxxxxx-- ******************************** 20 --xxxxxxxx--******************************** 21 xxxxxx-- --xx******************************** 22 --xxxxxxxx-- ******************************** 23 --xxxxxxxx-- ******************************** 24 --xxxxxxxx--******************************** 25 xxxxxx-- --xx******************************** 26 --xxxxxxxx-- ******************************** 27 --xxxxxxxx-- ******************************** 28 --xxxxxxxx--******************************** 29 xxxxxx-- --xx******************************** 30 --xxxxxxxx-- ******************************** 31 --xxxxxxxx-- ******************************** 32 --xxxxxxxx--******************************** 33 **************************************************************** 34 **************************************************************** 35 **************************************************************** 36 **************************************************************** 37 **************************************************************** 38 **************************************************************** 39 **************************************************************** 40 **************************************************************** 41 **************************************************************** 42 **************************************************************** 43 **************************************************************** 44 **************************************************************** 45 **************************************************************** 46 **************************************************************** 47 **************************************************************** 48 **************************************************************** 49 **************************************************************** 50 **************************************************************** 51 **************************************************************** 52 **************************************************************** 53 **************************************************************** 54 **************************************************************** -- 2255 -- TTRR CCSS9900//11 LLOOKKII -- AA CCrryyppttooggrraapphhiiccBBPPrrrrooiiwwmmnnii,,ttiiPPvviieeeepprrzzyykk,, SSeebbeerrrryy 55 **************************************************************** 56 **************************************************************** 57 **************************************************************** 58 **************************************************************** 59 **************************************************************** 60 **************************************************************** 61 **************************************************************** 62 **************************************************************** 63 **************************************************************** 64 **************************************************************** -- 2266 -- TTRR CCSS9900//11 LLOOKKII -- AA CCrryyppttooggrraapphhiiccBBPPrrrrooiiwwmmnnii,,ttiiPPvviieeeepprrzzyykk,, SSeebbeerrrryy Round 4: None 0, Msg 0, Autoclave 0, Both 4096, Err 0 CPdep: 100.00,100.00 1 **************************************************************** 2 **************************************************************** 3 **************************************************************** 4 **************************************************************** 5 **************************************************************** 6 **************************************************************** 7 **************************************************************** 8 **************************************************************** 9 **************************************************************** 10 **************************************************************** 11 **************************************************************** 12 **************************************************************** 13 **************************************************************** 14 **************************************************************** 15 **************************************************************** 16 **************************************************************** 17 **************************************************************** 18 **************************************************************** 19 **************************************************************** 20 **************************************************************** 21 **************************************************************** 22 **************************************************************** 23 **************************************************************** 24 **************************************************************** 25 **************************************************************** 26 **************************************************************** 27 **************************************************************** 28 **************************************************************** 29 **************************************************************** 30 **************************************************************** 31 **************************************************************** 32 **************************************************************** 33 **************************************************************** 34 **************************************************************** 35 **************************************************************** 36 **************************************************************** 37 **************************************************************** 38 **************************************************************** 39 **************************************************************** 40 **************************************************************** 41 **************************************************************** 42 **************************************************************** 43 **************************************************************** 44 **************************************************************** 45 **************************************************************** 46 **************************************************************** 47 **************************************************************** 48 **************************************************************** 49 **************************************************************** 50 **************************************************************** 51 **************************************************************** 52 **************************************************************** 53 **************************************************************** 54 **************************************************************** -- 2277 -- TTRR CCSS9900//11 LLOOKKII -- AA CCrryyppttooggrraapphhiiccBBPPrrrrooiiwwmmnnii,,ttiiPPvviieeeepprrzzyykk,, SSeebbeerrrryy 55 **************************************************************** 56 **************************************************************** 57 **************************************************************** 58 **************************************************************** 59 **************************************************************** 60 **************************************************************** 61 **************************************************************** 62 **************************************************************** 63 **************************************************************** 64 **************************************************************** -- 2288 --