Contents *
A2, a new secret-key encryption algorithm, is proposed. A2 is block cipher (Feistel network) iterating variable round function 16 times. The block size is 128 bits, and the key length is variable up to 2172 bits. The algorithm has no complex initialization phase. Only simple operations are used, no s-boxes are required. The key can be generated externally or the procedure described in this thesis can be use. A2 is designed to satisfy the major requirements concerning security and efficiency. In this paper standard software implementation is described, but the algorithm can be adjust to meet all cryptographic requirements, hardware or smartcard as well as software. Maybe this particular implementation can not be used in some cases but the family of algorithms based on A2 principles possibly can. No limitations are made on secrecy level of the protected information. In this document principles of A2 design are discussed, how to implement the algorithm is described in the Implementation Manual. A2 is a unique approach to the problem of protecting data with encryption. This algorithm is much different from other algorithms available now. The difference is how the key is used during encryption; classically "data is encrypted under the key K", for A2 more suitable is to say, "data is encrypted according to the key K". There is more than a linguistic difference, "according to the key" means that the key have some deterministic rule in encryption process. A2 use the key as an active component of algorithm, not as a passive constant that is somehow glued with the plaintext. To illustrate this; classic way of key using is: Plaintext + Key = Ciphertext; A2 propose Key(Plaintext)=Ciphertext. Imagine you have 10 different encryption algorithms and you need to encrypt a certain data. First thing you should do is to choose one of the algorithms, second to chose the key and finally to encrypt the data. This is A2 approach to the encryption problem. A2 is not an encryption algorithm in classical sense of the term; it is a template that should be upgraded to an active level according to the key. So A2 can be viewed as a family of algorithms. 3. Overview of block cipher design approaches I am not sure how many "approaches" are practically in use today. Mostly used are SP network and Feistel network. The Feistel Network is not a block cipher on its own; it is a way to use an arbitrary function to encrypt data, no matter if the function is reversible. So the only approach is SP, more than 90% of symmetric ciphers use this method. Substitutions are done using substitution boxes and most of ciphers use this method. Many ciphers just copy DES design ideas. That why they are nearly identical from principle view point. Standard, DES-like, cipher looks like:
Substitution tables are used in step 2; they are the main problem in this approach because there is not exact specification what "secure S-box" means. Only thing it is known for sure is that there are "secure" and "insecure" S-boxes. Permutations are very important because they force every ciphertext bit to depend of every key and plaintext bit. Now what are the main characteristics of SP and Feistel approach in block encryption.
There are more than these properties, but these ones are important for the discussion in this thesis. In "Applied Cryptography" 20 block ciphers are described. Including standards (DES, GOST and Skipjack) 11 of them use S-boxes, if the standards are excluded only 3 of them are secure according to Bruce Schneier (Blowfish, CAST and LOKI91). The others does not use any S-boxes in their design; only MMB and FEAL are considered insecure; RC5, CRAB, 3-Way, SAFER, CA-1.1* and IDEA are secure according to Schneier. These algorithms are all unique in their design. A2 have certain similarities with RC5 and CRAB; A2 is intend to use more originally approach; here the main characteristics of A2 approach:
S-boxes are rejected because there is no exact theory about generating S-boxes in order to be "secure for cryptography use". Because this algorithm must require as less as possible memory space, usage of "random and cryptographically secure arrays bits" as an initialization for any variable is rejected. This algorithm should be fast, as possible, so low time-consuming operations are used in its design. The way the key is used is the main-stone of A2. Structure of A2 algorithm is:
(**) The implementation I propose have an additional transformation, key depend rotations are add to strength the algorithm. 5. Active use of the key principle - AUKP The main innovation in A2 is AUKP. Here is a simple example for AUKP: Consider that: Op is a set of operations { XOR, AND, OR, ADDITION } denoted as ^, &, |, + and considered to be first, second, third and forth operation. You need to encrypt some message according to a given key. Let the message be {1012,127} and the key {{1,3,4,2},{513,723,32,184}}. Now the encryption:
Using the algorithm just described and the example values the process goes as follow:
Decryption is same as encryption, only the use of key is inverted. This is a very simple implementation of AUKP principle,(This principle is very similar with VFT). The difference between this approach and the classical one is obvious; the Feistel network is completely the same: R=R^f(L,k); the difference appear in f(L,k). A2 use complex key consist of {{operation_determining component},{classic key}}. The first component of the key is called scenery because it determinate the operations that will be used in each function, the second part have a rule of classic key. A variant of this approach is used in RC5 design. RC5 use the key to drive the rotations that are the main part of the cipher. It is interesting that RC5 is considered to be very secure because of this property, this is very simple cipher but key driven rotations makes it secure. This is the only algorithm mentioned in "Applied Cryptography" that uses key driven transformations. Another algorithm that has certain similarities with A2 is CRAB (more correctly A2 has with CRAB). CRAB use a different function in every round (the famous FGHI set, used in MD5; A2 use it too), it also have more sub-blocks, 5 in every round. CRAB main idea is to use techniques from one-way hash functions (CRAB is based on MD5) to make fast and secure algorithm. I have the same idea (I didn’t know about CRAB when Anigma was developed) during Anigma and A2 development; they are based on MEX and VFT. 6. Variable function principle - VFP The function, for A2 needs, can be any expression. The number of variables can be arbitrary. Every time the function is call besides the values complex key is passed in. The function can look like: F(a,b,c,...{{op1,op2,op3...},{k1,k2,...}) = = (a op1 k1) op2 (b op3 k2) op4 (c op5 k3) . . . . How many arguments the function will accept and how many operations will be determinate by the key is a matter of design. VFP is a direct consequence of AUKP. The function is actually a template that according to the key is transformed into active form. It is very important to design good templates. Simpler way is to design certain set of functions and the key to determinate which one of them will be used in particular situation. This is more effective way than designing templates. This method is used in A2. Every round in A2 is consisting of four operations. Let N[] be the block and N[I] I-th sub-block then the round can be presented as:
F[j](...) is the j-th function from the set. A2 is not encryption algorithms in classical sense; it is family of algorithms. If the "scenery" is chose and used correctly then every "scenery" will present a unique encryption algorithm. Because the operations are determinate by the key, when different scenarios are used for every round than the rounds will not obey the definition "simple transformation repeated n number of times". They are "simple" transformation but they will not be "repeated" because every round will possibly present a unique transformation. That why A2 is (from technical viewpoint) and is not (form mathematical viewpoint) a round repeating algorithm. This is true whichever approach in VFP is used, template function or pool (set) of functions. First benefit is that the key can be of practically no limited length, depend on how many rounds are used. The key is complex and it can be managed in different ways. The scenery part can be made fix for a certain group or network so only the computers that have that scenery can inter-operate. The other part can be used as an ordinary key, it can be frequently changed or it can be unique for every message. The key can be generated externally by some secure source of randomness. For any scenery a unique encryption algorithm is generated. Warning: No one of following conclusions are proved, they are more likely to be hypothesis about A2 security. This approach of block cipher design is strong again most of cryptoanalytic attacks. It is immune to all classic attacks. Because of the nature of this algorithm it should be strong against the differential cryptoanalysis. This type of analysis is mainly used to cryptoanalyze S-boxes, A2-like algorithms does not use s-boxes. Only two algorithms, which are publicly known, RC5 and CRAB use some elements of AUKP and VFP. RC5 have some AUKP-like idea in its design. Both of them are secure. All other algorithms use static operations. The best of encryption algorithms today is that some of them use the key to create s-boxes instead using fixed ones. This prevents Differential Cryproanalysis (DCA), but this approach has long precomputation phase. The strongest weapon against DCA should be the fact that every key mathematically presents a different encryption procedure which probably have unique, or at least different, properties, so difference propagation is not the same for all keys. Linear Cryptoanalysis should be impossible because of the same reasons as differential. Both analysis are made to crack the S-boxes, I have no idea if possible to use them to recover the scenery of encryption. Because every key present different encryption transformation it should be impossible to analyze A2 in general case. Linear Cryptoanalysis is also difficult to implement because key driven rotations are used in algorithm so it is nearly impossible to find bit positions which will be used to discover part of the key. RC5 and CRAB are considered to be secure against differential and linear cryptoanalysis. A2 use key dependent rotations as RC5 (key depend rotation are considered to be non-linear function) and different functions in rounds as CRAB. One question remains if A2 SP-network? if it is that which transformation present the substitution and which ones permutation? A2 principles do not guaranty any security if they are not implemented correctly. Using all the principles described before I develop A2 block cipher. A2 block cipher has 16 rounds; use 2172 bits key; operate on 128 bits block of data. All rounds are technically identical (mathematically they are not if their scenarios are not). One round of encryption is consist of 4 steps. Let N[0..3] (4*32bit) denote the block which is currently transforming; Fext[r][0..3] (4*32bit) is the key material for r-th round; Rext[r][0..3] (4*2bit) is a scenery part of the key for r-th round; F[0..3] is set of functions that are used in this implementation. ( <<< and >>> denote rotation in left / right )
All rounds are technically identical, so it is very simple to program A2 implementation. Now the review of solutions used in my implementation. The four functions that are used in this algorithm should have these properties:
The four functions used in A2 are de-facto standard; many algorithms use them to satisfy the requests listed before:
A2 is not a classical Feistel Network, it have 4 sub-blocks. The key material used in each round is consist of two parts Rext[r][] and Fext[r][] where Rext is scenery part of the key and Fext have the rule of classical key. That how UAKP is realized in A2, A2 equant is:
A2 can be viewed as a scalar encryption, first step is concatenation of key material with the plaintext, so the primary ciphertext is produced, encrypting the primary ciphertext, according to scenery part of the key, secondary one is produced. Key depend rotations are very important part of A2. Anigma, the predecessor of A2, have no rotations so the diffusion effect is not propagated as well as it should be. Anigma require more than 100 rounds to make every bit of ciphertext to interfere with every bit of plaintext and the key. Because of this the difference between two plaintexts and the difference between their ciphertexts is nearly the same. Including key depend rotation the cipher is strength. This should make the algorithm immune to differential and linear cryptoanalysis. I chose scenery part of the key to drive sub-block rotations and classical key part to drive hole-block rotations. A2 use pretty long key, 2172 bits in total. Any random sequence can be used as a key. The key is separated in two parts: scenery and classic key. The classic key can be anything, it must not to be so random if there is no trusted source of randomness. But the scenery part must be "random" and it must obey these rules:
In the Implementation Manual of A2 a procedure is describe how to generate key using A2 algorithm. If this procedure is used then the effective length of key is 128 bit. This is enough for all practical implementation. In the Implementation Manual also how to use a key of arbitrary length, up to 2172 bits, is described. A2 is not a group. So it is possible to define addition of keys. If usage of n-bit key (greater than 128bits) is required that the following procedure described in the manual is used:
The internal key generated with this process is composite because hole key material is needed to reconstruct the internal key. During the key generation process, which is similar with the encryption, the internal key is used, Because of this it is possible to generate composite key. Internal key made equal impact on key generation process as the key material. This property of A2 enables key generation process without having external randomness source. Low entropy data can be used, like a pass-phrase, to generate the key. The entropy of English language is 1.3 bit per charter, for 128 bit key 100 charters are required. Present those charters in binary form and you can input them as a key material to run composite key generation process. The resulting key will have entropy no less than 128 bits. If maximum key length should be gain that 1671 charters are needed as a key material to run composite key generation. 10. Differences between A2 and Anigma A2 is developed as a successor of Anigma. They use the same theoretic principles and they are identical when the principles are concerned. The major differences are additional key depend transformation, the rotations, used in A2. Anigma is a very weak algorithm because the last significant bit in the plaintext has the smallest influent on the ciphertext and the most significant the biggest. Implementation of A2, that I propose, has some differences from Anigma implementation. Anigma have two modes of key generation V16 and BX; A2 use only the V16 mode which is strength with additional properties, rotations are used in key generations and scenery is generated on completely different way. A2 is mush better algorithm and it should be use as replacement of Anigma or any other cipher. In this thesis I will not specify modes of operation. A2 can be use in any mode, about modes of operation consult the ANSI and FIPS standards. In the Implementation Manual a procedure of initial vector generating is proposed I recommend using this procedure whenever IV is required. 12. Using A2 as message digest function A2 can be used as a message digest function. Because every bit of plaintext interfere with every bit of ciphertext this usage of A2 is possible. How to use A2 as message digest function is described in the Implementation Manual. 13. Using A2 as a Random Number Generator A2 can be used as a random Number generator. The main property of number is that knowledge of previous number does not give any idea what next number will be. A2 can be used to produce random numbers with running it in OFB mode, because the key is needed to generate the numbers, no prediction about next number can be made without key knowing. I don’t know why, but this method is not used at all. A2 have some unique properties that enable using more complex procedures than OFB in order to generate random numbers. Procedure I propose is very simple to implement. In the manual technical aspect is described. Here just the theory. Every user obtains a secure random seed 256 bytes long. Every time random numbers are needed he chose a random session key and run A2 generator.
Even if we know all random number up to n-th one it is impossible to find neither the previous nor the next random number if we don’t know both seed and session key. So A2 is secure both on left and right. 13. About the author and copyright notice All questions about this thesis you can send to me via e-mail kbajalc@eon.pmf.ukim.edu.mk. More information about me, my researches and links to cryptography resources can be found on my Home Page http://eon.pmf.ukim.edu.mk/~kbajalc here is also a link to A2 page where all available information about this project is presented.This document, information presented in it and copyright for them are property of Kostadin Bajalcaliev. This document is freely available to everybody, Everybody have right to distribute it use information presented in it free of charge since this copyright notice is retained. © Kostadin Bajalcaliev, 1998 This document is created on: May 11, 1998 A2 algorithm design is finished on May 4, 1998 |