From: Tran Ngoc Duong on 25 Jul 2010 14:56 THE BLOCK CIPHER NSABC (Public domain) Alice Nguyenova-Stepanikova Tran Ngoc Duong <tranngocduong at gmail dot com> (corresponding author) 27th July, 2010 Abstract. We introduce NSABC/w (Near-Skipjack Algebraic Block Cipher operating on w-bit word arithmetics), a 4w-bit analogous of Skipjack [NSA98] with 5w-bit key. The Skipjack's inner 4-round Feistel structure is replaced with a w-bit, 2-round cascade of the binary operation (x,z) |-> (2*x*z + (1-2*e)*(x-z+e)) <<< (w/2), partially encrypting a data word x under control of a key word z and a round-dependent constant word e, allowing efficient decryption. Furthermore we introduce an optional secret 4w-bit "tweak", i.e. a randomization parameter, to facilitate applications such as disk encryption and hashing, that is in turn derrived from the block index and a 4w-bit [additional] key. With w=64, on a modern 64-bit processor, encryption takes about 5 clock cycles per byte and, when tweaking is unused, only 4.4 clock cycles per byte. 1. Introduction In the today's world full of cryptographic algorithms, one may cast question: "What should makes a block cipher attractive to cryptographers?" It is the authors' view that the answer is one word: elegance. If something looks elegant, there is a good chance that it is also good. An elegant specification makes it easier to memorize. Memorizability makes it easier to analyze, thus allows for fruitful cryptanalytic results. Results make greater confidence in the algorithm. The elegance comprises the following features: -- Few algebraic operations. Using of many operations such as tables of constants, S-boxes, data-dependent transpositions, data-dependent operator selections etc results in "wild", hardly-tractable and possibly undesirable interactions between operations. -- Simple and regular key schedule. A complex key schedule, such as bit transpositions, linear pseudo-random number generators, non-linear operations etc, which effectively adds another, complicated and un-related, function to the cipher, results in hardly-tractable and possibly undesirable interactions between the functions. IDEA, a secure block cipher designed by Xuejia Lai and James L. Massey [LM91], besides being elegant, is outstanding for other features: -- The use of "incompatible" operations. The incompatibility helps to exclude any [undesired] algebraic property and makes it impossible to solve the cipher algebraically. -- The use of multiplication. Multiplication is more powerful than addition and thus greatly contributes to the security of the algorithm. However, IDEA uses multiplication modulo p, where p is a prime of the form 2**w + 1 which does not exist for w=32 or w=64, making it not extendable to larger machine word lengths. Furthermore, the key schedule uses a rotation on the [primary] key, making it irregular as some key bits are re-used much more slowly than others. Skipjack, a secure block cipher designed by cryptographers of the U.S. National Security Agency [NSA98], is another example of elegant design. Furthermore Skipjack is outstanding for the following feature: -- The use of two ciphers, an *outer* (wrapper) cipher, and an *inner* (core) cipher. As explained by the authors of MARS [IBM98], a block cipher with similar design principle, this two-layer structure breaks any iterative property, makes any iterative characteristic impossible, and complements eventual weakness(s) in either layer by the other one, thus making attacks more difficult. The wrapper is designed for fast diffusion and the core for strong confusion. Here *diffusion* refers to the process of making one data or key bit to affect many data bits in very different ways, *confusion* refers to the process of making one data bit to be affected by many data or key bits in very different ways. The terms are first used by Claude E. Shannon in his pioneer work [Shannon49]. However, Skipjack uses S-boxes, making it slow, hard to implement in a secure manner, and not extendable to larger machine word lengths, as such. This article describes an atempt to combine the ideas learned from IDEA and Skipjack, where Skipjack is used as a structural framework, into a scalable and tweakable block cipher called NSABC (Near-Skipjack Algebraic Block Cipher). In cipher design there is always a trade-off between security and efficiency, and designers always have to ask "What the users want, a very strong and relatively fast cipher, or relatively strong but very fast?" If Skipjack is regarded as very secure but not very fast, then NSABC may be regarded as an atempt to re-use Skipjack with stress on the second aspect: make it very fast, but probably not very secure. For 64-bit word length, NSABC is designed to use a 320-bit key and an additional 256-bit "tweak" key, but the true level of security is yet to be determined. On the other hand, it takes only 5 clock cycles per byte (and only 4.4 clock cycles per byte with disabled tweaking) on a modern 64-bit processor. NSABC is not patented and is available for public use. As it re-uses the [overall] structure of Skipjack, excepting some [cosmetical] word re- numbering, eventual users should be aware of Skipjack patent(s) which may be held by the U.S. Government. We are not aware of eventual patent(s) related to other parts of the design. The rest of the article is organized as follows. Section 2 defines operations over machine words, mainly a multiplication-based group operation over w-bit numbers. Section 3 specifies the algorithm. Section 4 suggests an efficient implementation. Section 5 concludes the article. 2. Operation over w-bit words Let +, -, *, ~, ^ denote two-complement arithmetic/logic operations with the conventional (C programming languague) meanings. Let's define binary operations "." and "o" as follows. x . y = 2*x*y + x + y x o y = 2*x*y + x - y Note that the bivariate polynomials x.y and x o y are permutation polynomials on either variable for every fixed value of the other variable [Rivest99]. In other words, "." and "o" are quasi-group operations. Furthermore, it is easy to see that "." is an abelian group operation over the set of w-bit numbers. (Here and later, uncited facts are from the authors' unpublished work, but they are trivial so the proofs are omitted.) The group is isomorphic to the multiplicative group of odd integers modulo 2**(w +1). The isomorphism is x |-> 2*x + 1 (mod 2**(w+1)) The unit of the group is 0. The inverse element of x, denoted x', is x' = - x/(2*x + 1) where "/" denotes the inverse operation of "*", i.e. modular multiplication by the inverse of the denominator, which indeed exists for every x. The following relations hold. (~x) . y = ~(x . y) (1-x) o y = 1 - (x o y) x . y = -((-x) o y) x o y = -((-x) . y) x . a = b if and only if x = b . a' x o a = b if and only if x = b o a' Let e is an arbitrary fixed w-bit integer. Let's define trivariate polynomials p and q as follows. p(x,y,e) = (x-e).(y-e) + e = 2*x*y + (1 - 2*e)*(x + y - e) q(x,y,e) = -p(-x,y,e) = 2*x*y + (1 - 2*e)*(x - y + e) Then p and q are permutation polynomials on either variable while keeping the others fixed [Rivest99]. Thus the binary operations "(.)" and "(o)" defined by x (.) y = p(x,y,e) x (o) y = q(x,y,e) are quasigroup operations. Note that the previously defined operations "." and "o" are instances of "(.)" and "(o)", respectively, with e = 0: x . y = p(x,y,0) x o y = q(x,y,0) Furthermore, "(.)" is an abelian group operation over the set of w-bit numbers that is isomorphic to the group "." defined above. The isomorphism is x |-> x - e The unit of this group is e. The inverse element of x, denoted x('), is x(') = (x - e)' + e = ((2*e - 1)*x - 2*e*(e-1)) / (2*(x-e) + 1) The following relations hold. x (.) y = -((-x) (o) y) x (o) y = -((-x) (.) y) x (.) y = (x-e) . (y-e) + e x (o) y = (x+e) o (y-e) - e x (.) a = b if and only if x = b (.) a(') x (o) a = b if and only if x = b (o) a(') The operation "(o)" will be used for both encryption and decryption thanks to the following relation. (x (o) z) (o) z(') = x 3. Specification This section provides details of NSABC/w, where w is even. Throughout this section, X denotes a 4w-bit plaintext block, Y a 4w- bit ciphertext block, Z a 5w-bit key, T a 4w-bit secret *tweak*, i.e., a value that is used to encrypt only one block under the key, and E a 64w-bit public *bias*, i.e. a constant value that will be added to / subtracted from the intermediate data words and key words before and after every multiplication. NSABC is specified in terms of two functions: ENCRYPT(X,Z,T,E), which encrypts X under control of Z, T and E, DECRYPT(Y,Z,T,E), which decrypts Y under control of Z, T and E. Relation: DECRYPT( ENCRYPT(X,Z,T,E),Z,T,E ) = X Tweaking is optional and can be disabled by letting T constantly zero. With disabled tweaking, NSABC becomes a conventional, non-tweakable, block cipher. E is declared as a parameter, abeit a constant with well-defined value in this specification, to indicate the possibility of e.g. personalization, i.e. making other, "non-standard", variants of the algorithm. 3.1. Word and byte order A multi-component vector is written as a string in the usual comma- separated notation, i.e. the leftmost component being the first one. For example, (x0,x1,x2). A multi-digit number is written as a string in the usual notation, i.e. the rightmost digit being the least significant one. For example, x2 x1 x0. The same data entity is taken sometimes as a number and sometimes as a vector. To switch between these meanings, memory addressing is a common terminology framework. Vectors are stored in low-first order, i.e. the first component is stored at lowest address. Numbers are stored in memory in low-first order, i.e. the least significant digit is stored at lowest address. Thus for example, if V = (x0,x1,x2) and N = x2 x1 x0 then V = N. The terms "component" and "digit" above both refer to [machine] words. For multi-byte words we assume little-endian byte order. Thus, a "standard" representative of NSABC is fully determined by a single parameter: the word length w. 3.2. Operations on word strings Let R denote the transposition that reverses the word order of a word string. For example, for 8-bit words, 0x0123AB R = 0xAB2301. Let S denote the transposition that swaps the high and low halves of every word of a word string. For example, for 8-bit words, 0x0123AB S = 0x1032BA. Let ' denote the word-wise application of the inverse operator "'" on a word string. For example, (a,b,c)' = (a',b',c'). The following relations hold. xRS = xSR xR' = x'R Unless otherwise specified, operators "+" and "-" applied on multi- word strings denote word-wise modular addition and subtraction, respectively, i.e. operands are regarded as vectors of words. For example, (a0,a1,a2) + (b0,b1,b2) = (a0+b0, a1+b1, a2+b2) The following relations hold. (x + y)R = xR + yR (x - y)R = xR - yR 3.3. Functions ENCRYPT This function is specified in terms of three functions: DE, a data encryption function; KE, a key expansion function; and TE, a tweak expansion function. Input: X...4w-bit plaintext block Z...5w-bit key T...4w-bit tweak E...64w-bit bias Output: Y...4w-bit ciphertext block Relation: ENCRYPT(X,Z,T,E) = DE(X, KE(Z), TE(T), E) 3.4. Functions DE, KE and TE These functions operate on a 4-word data register (x0,x1,x2,x3) and use a 5-word key register (z0,z1,z2,z3,z4) and a 4-word tweak register (t0,t1,t2,t3). The key register is initially loaded with the key Z, in low-first order. The tweak register is initially loaded with the tweak T, in low-first order. The data register is initially loaded with the plaintext block X in low- first order, and after encryption it contains the ciphertext block Y in that order. These functions consist of 32 rounds of operations. In each round, a key- dependent permutation G applies on the word x0, an exclusive-or (XOR) operation "mixes" x0 and t0 into another word which is either x1 or x3 (see further). There are two types of rounds: A and B. In an A-typed round, the mixing takes place after G and targets x1; in a B-typed round, mixing takes place before G and targets x3. In each round, the pair of key words (z0,z3) enter G- box in that order. At the end of every round there is a rotation on the data register that circularly exchanges value of the four data words, and other rotations that do similarly for the key register and the tweak register. Encryption runs in four passes: 8 rounds of type A, then 8 rounds of type B, then 8 rounds of type A again, then 8 rounds of type B again. KE (key expansion) Input: Z...5w-bit key Output: K...64w-bit expanded key Pseudo-code: (z0,z1,z2,z3,z4) := Z for k := 0, 1, 2,..., 31 loop K(2*k) := z0 K(2*k+1) := z3 (z0,z1,z2,z3,z4) := (z1,z2,z3,z4,z0) end loop TE (tweak expansion) Input: T...4w-bit tweak Output: L...32w-bit expanded tweak Pseudo-code: (t0,t1,t2,t3) := T for k := 0, 1, 2,..., 31 loop L(k) := t0 (t0,t1,t2,t3) := (t1,t2,t3,t0) end loop DE (data encryption) Input: X...4w-bit plaintext block K...64w-bit expanded key L...32w-bit expanded tweak Output: Y...4w-bit ciphertext block Pseudo-code: (x0,x1,x2,x3) := X for k := 0, 1, 2,..., 31 loop if 0 <= k <= 7 or 16 <= k <= 23 then x0 := G( x0, (K(2*k), K(2*k+1)), (E(2*k), E(2*k+1)) ) x1 := x1 ^ x0 ^ L(k) elsif 8 <= k <= 15 or 24 <= k <= 31 then x3 := x3 ^ x0 ^ L(k) x0 := G( x0, (K(2*k), K(2*k+1)), (E(2*k), E(2*k+1)) ) end if (x0,x1,x2,x3) := (x1,x2,x3,x0) end loop Y := (x0,x1,x2,x3) Relations: (x0(0),x1(0),x2(0),x3(0)) = X (z0(0),z1(0),z2(0),z3(0),z4(0)) = Z (t0(0),t1(0),t2(0),t3(0)) = T (E(0),E(1),...,E(63)) = E Y = (x0(32),x1(32),x2(32),x3(32)) for 0 <= k <= 7 or 0 <= k <= 23: x0(k+1) = x1(k) ^ g(k) ^ L(k) x1(k+1) = x2(k) X2(k+1) = x3(k) x3(k+1) = g(k) for 8 <= k <= 15 or 24 <= k <= 31: x0(k+1) = x1(k) x1(k+1) = x2(k) x2(k+1) = x3(k) ^ x0(k) ^ L(k) x3(k+1) = g(k) for 0 <= k <= 31: g(k) = G(x0(k), (K(2*k), K(2*k+1)), (E(2*k), E(2*k+1))) K(2*k) = z0(k) K(2*k+1) = z3(k) z0(k+1) = z1(k) z1(k+1) = z2(k) z2(k+1) = z3(k) z3(k+1) = z4(k) z4(k+1) = z0(k) L(k) = t0(k) t0(k+1) = t1(k) t1(k+1) = t2(k) t2(k+1) = t3(k) t3(k+1) = t0(k) 3.5. Function G Function G, which takes as arguments a w-bit intermediate plaintext word x and a pair of w-bit subkey words (k0,k1) to return a w-bit intermediate ciphertext word, is a 2-round cascade of the quasi-group operation "(o)", each followed by a swap of half-words. The first "(o)" uses unit e0, the second "(o)" uses unit e1. In the relations below, the quasi-group operation is written in terms of the trivariate polynomial q, rather than "(o)", to specify the unit element. Relations: G(x,(k0,k1),(e0,e1)) = q( q(x,k0,e0)S, k1, e1 )S 3.6. Function DECRYPT DECRYPT can be easily derrived from the (implicit) relation with ENCRYPT. Here it is given explitly in terms of functions DE, KE and TE to emphasize similarity between encryption and decryption. Unlike Skipjack, DECRYPT cannot be expressed explicitly in terms of ENCRYPT. That's why the cipher is termed "near Skipjack". Relations: DE( DE(X, KE(Z), TE(T), E)RS, (KE(ZR) - ER)' + ER, TE(TRS), ER )RS = X DECRYPT(Y,Z,T,E) = DE( YRS, (KE(ZR) - ER)' + ER, TE(TRS), ER )RS 3.7. The bias E The 64w-bit constant E, which consist of units of the group under the operation "(.)" in function G, and which is used to bias the data words and key words from zero, may be used to personalize the algorithm. Every choice of E makes a unique tweakable block cipher. As a "standard" choice, we propose the first 64 numbers (modulo 2**w) of the Fibonacci sequence. Relations: E(0) = 1 E(1) = 2 E(k) = E(k-1) + E(k-2) for k = 2,3,4,...,63. 3.8. Tweak counter mode The 4w-bit secret tweak T is used to encrypt only one block [under a fixed key Z]. To encrypt multiple blocks the tweak is derrived from a 4w-bit [additional] key, called *tweak key*, and the block index i, as follows. Let T(i) denote the tweak used to encrypt i-th block. For zero-th block, the tweak key is used as the tweak directly: T(0) = tweak key Successive tweak is computed from the last-used tweak by the recurrent relation: T(i) = T(i-1) + 2*T(0) + 1 or, explicitly, T(i) = T(0) . i where all operators, including ".", are defined on 4w-bit modular arithmetics and all operands, including 1 and i, are regarded as 4w-bit numbers. 4. Notes on implementation (1) The polynomial q in function G can be evaluated using only one multiplication and one addition, with a modified key schedule. Indeed, q(x,z,e) = M*x + N where x is a data word, z key word, e the unit of the [quasi-]group in use, and M = 2*(z - e) + 1 N = (2*e - 1)*(z - e) is a pair of subkeys precomputed in the [modified] key schedule, which consists of 64 such pairs. (2) The cipher is partially parallelizable. The following procedure executes all 32 rounds in 20 steps, of which half performing two or three parallel evaluations of the function G. Recall that g(k) is the result of G in round k. 1. Compute g(0) 2. Compute g(1) 3. Compute g(2) 4. Compute g(3) 5. Compute g(4) 6. Compute g(5), g(11) in parallel 7. Compute g(6), g(9) in parallel 8. Compute g(7), g(10), g(13) in parallel 9. Compute g(8), g(14) in parallel 10. Compute g(12), g(15) in parallel 11. Compute g(16) 12. Compute g(17) 13. Compute g(18) 14. Compute g(19) 15. Compute g(20) 16. Compute g(21), g(27) in parallel 17. Compute g(22), g(25) in parallel 18. Compute g(23), g(26), g(29) in parallel 19. Compute g(24), g(30) in parallel 20. Compute g(28), g(31) in parallel On a modern 64-bit processor, each step should take about 8 clock cycles on average. So, for w=64 i.e. 32-byte blocks it achieves 20*8/32 = 5 clock cycles per byte encrypted. If tweak counter mode is not used we may disable tweaking completely to save about 1 clock cycle per byte per step, resulting in 20*7/32 = 4.4 clock cycles per byte. 5. Conclusion We introduced NSABC, a Skipjack-like block cipher that is defined for every even word length, allowing scalability in block length and key length. NSABC is meant to be simple. It uses no hard-to-memorize S-boxes. It makes use only two word-oriented algebraic operations that are mutually incompatible: "^" and "(o)". It re-uses the overall structure of Skipjack that has been made public for over a decade -- sufficient to become truly understood. The simplicity makes it easier to analyze, which in turn makes greater confidence in the algorithm. NSABC uses multiplication which is much more powerful than addition and should greatly contribute to the security of the algorithm. NSABC bases on some valuable design of a well-reputed agency in the branch. We therefore believe that it is worth analysis and it can withstand rigorous analysis. If this happens to be true, then we may have a strong cipher with 256-bit blocks, allowing to encrypt enormous amount of data under the same key, and with 320-bit keys, allowing to keep data secret over any imaginable time. NSABC is fast enough to be comparable with any modern block cipher. 6. References [IBM98] Burwick C., Coppersmith D., D'Avignon E., Gennaro G., Halevi S., Jutla C., Matyas S. M. Jr., O'Connor L., Peyravian M., Safford D., Zunic N.: MARS - a candidate cipher for AES. 1998. [LM91] Lai X., Massey J. L., Murphy S.: Markov Ciphers and Differential Cryptanalysis. 1991. [NSA98] National Security Agency: Skipjack and KEA specification. 1998. [Rivest99] Rivest, R. L.: Permutation polynomials modulo 2**w. 1999. [Shannon49] Shannon C. E.: Communication Theory of Secrecy Systems. 1949.
From: Tom St Denis on 26 Jul 2010 08:54 On Jul 25, 2:56 pm, Tran Ngoc Duong <tranngocdu...(a)gmail.com> wrote: > THE BLOCK CIPHER NSABC > (Public domain) I haven't read your spec because it was line-wrapped as you posted it to usenet [hint: get a website to post this, or turn it into a PDF and post it ...] But - Lack of distinct pseudo code - Lack of vectors Makes me very dis-interested in pursuing it further. Tom
From: Mok-Kong Shen on 26 Jul 2010 09:31 Tran Ngoc Duong wrote: > An elegant specification makes it easier to memorize. This is true. However, easiness is a relative concept. Are you very sure that the majority of people would agree that e.g. what you showed as pseudo-code are easy to memorize for them and hence could start rightaway from the brain to code your encryption algorithm? M. K. Shen
From: Tran Ngoc Duong on 26 Jul 2010 16:35 On Jul 26, 7:54 pm, Tom St Denis <t...(a)iahu.ca> wrote: > On Jul 25, 2:56 pm, Tran Ngoc Duong <tranngocdu...(a)gmail.com> wrote: > > > THE BLOCK CIPHER NSABC > > (Public domain) > > I haven't read your spec because it was line-wrapped as you posted it > to usenet [hint: get a website to post this, or turn it into a PDF and > post it ...] > Thank you for the hint. I'll add schemata, vectors, reformat and post it again to Usenet. > But > > - Lack of distinct pseudo code > - Lack of vectors > > Makes me very dis-interested in pursuing it further. > I'm sorry for dumb question but as English is not my nature language, what is "distinct pseudo code"?
From: Tran Ngoc Duong on 26 Jul 2010 16:58 On Jul 26, 8:31 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > Tran Ngoc Duong wrote: > > An elegant specification makes it easier to memorize. > > This is true. However, easiness is a relative concept. Are > you very sure that the majority of people would agree that > e.g. what you showed as pseudo-code are easy to memorize for > them and hence could start rightaway from the brain to code > your encryption algorithm? > I'm sure most people can start rightaway from the brain to think of (understand, analyze, attack,...) it. But I think most people must read some documents (pseudo-code, formulars, schemata, implementation notes,...) in order to implement anything. Anyway you're right that pseudo-code may not be the best way to ease memory. Schemata are.
|
Next
|
Last
Pages: 1 2 3 Prev: Chua's treatment of Wolfram's result Next: What could WYLBNIMGTHAD possibly mean? |