TETRA-1: A Strengthened Four-Branch Block Cipher for Constrained Devices

TETRA-1: A Strengthened Four-Branch Block Cipher for Constrained Devices

Abdallah E. Salem

Telecom Egypt, Ismailia, Egypt

AbstractThis paper presents TETRA-1, a strengthened evolution of the HANK-1 block cipher (Eldeeb et al., ICEENG 2012). Six structural weaknesses are formally identied: passive Feistel branches; a 1-bit pre-mixing rotation; primary S-box differential uniformity of 16 (four times worse than AES); no round constants in the key schedule; an 8-round count insufcient for formal security guarantees; and a non-standard padding scheme. TETRA-1 addresses all six through: (i) a sequential 4-branch update; (ii) an 8-bit rotation; (iii) a GF(28) inverse S-box achieving

differential uniformity 4; (iv) GF(28) round constants; (v) 12 rounds bounding the best differential trail at 2360; and (vi) PKCS#7 padding. A fully validated Python REST API implementation is provided, cross-veried against an independent JavaScript engine.

Index TermsBlock cipher, Feistel network, constrained devices, GF(28), differential uniformity, MDS codes, key schedule, PKCS#7, lightweight cryptography

1. INTRODUCTION

   The proliferation of IoT devices, wireless sensor networks, and embedded systems demands cryptographic algorithms that are secure and implementable under strict resource constraints [1]. AES [2] imposes memory and computational requirements ex- ceeding the budgets of many constrained platforms.

   Eldeeb et al. introduced HANK-1 at ICEENG 2012 [1]: a 128-bit balanced Feistel cipher over four 32-bit sub-blocks, run- ning 8 rounds with a 128-bit key in CBC mode. Implemented on a Microblaze processor at 62.5 MHz, it achieves 84.1 Kbit/s

   with branch number 5 are used: M1 = circ(2, 3, 1, 1) and M2 =

   circ(4, 1, 3, 4).

   C. S-Box Construction

   S-Box A: power function x4681 over GF(28) with polynomial 0x1F5. Walsh max = 32, differential uniformity = 16. S-Box B: randomly generated, uniformity 8, Walsh max = 68.

   D. Key Expansion

   Eight sub-keys via: SK(0) = SX[MASK Key ]; SK(i) = SX[SK(i1)

   sufcient for voice encryption on smart cards. However, de-

   n n n n

   (n1)%4

   SK(i1)], where is a circular left shift by i bits and no round

   tailed cryptanalytic analysis reveals six structural weaknesses, n i

   addressed in this paper by TETRA-1.

   The remainder is organized as follows. Section II reviews HANK-1. Section III identies its weaknesses. Section IV presents TETRA-1. Section V analyzes security. Section VI gives the algorithm specication. Section VII describes the reference implementation. Section VIII discusses performance. Section IX compares with related work. Section X concludes.

2. REVIEW OF ORIGINAL HANK-1

   1. General Structure

      HANK-1 partitions plaintext P into (L0, L1, R0, R1) and each sub- key SK into (SK0, SK1, SK2, SK3). The round transformation for i {1,…, 8} is:

      constants are injected.

3. IDENTIFIED WEAKNESSES

   1. Passive Feistel Branches

      Only L0 and R1 receive round function output in (1)(2); L1 and R0 are never directly modied. Full diffusion requires 2 rounds for a single-bit change, and the cipher can be analyzed as two quasi-independent 2-branch Feistel networks.

   2. Weak Pre-Mixing: 1-Bit Rotation

      ROL(·) by 1 bit provides no byte-level permutation: 7 of 8 bit positions per byte remain in the same byte, limiting S-box input diversity.

   3. S-Box Differential Uniformity

   Denition: Differential Uniformity

   where ROL is a 1-bit left rotation. After each round, L1 and R0 are swapped. Only L0 and R1 receive round function output.

   1. Round Function

   The round function F follows: input SK S-boxes [A, B, A, B]

   MDS 4 × 4 output. Two MDS matrices over GF(28)

   (S)= maxx/=0, y #{x : S(x) S(x x)= y}. Lower values indicate stronger resistance to differential cryptanalysis.

   As shown in Table 1, S-Box A has = 16 versus AESs 4

   differential trails are 4× more probable. S-Box B Walsh

   maximum 68 vs. AESs 32 indicates high linear bias.

   TABLE 1

   S-Box Cryptographic Properties

   TABLE 3

   Avalanche Effect Comparison (64 single-bit ip tests)

   Property	S-Box A	S-Box B	AES	TETRA-1		Cipher	Avg.	Min.	Max.
   Walsh Max	32	68	32	32		HANK-1	64.0	53	80
   Diff. Uniformity	16	8	4	4		TETRA-1	64.6	56	78
   Algebraic Degree	5	6	7	7		Ideal	64.0	64	64

   TABLE 2

   Specication: HANK-1 vs. TETRA-1

   Property	HANK-1	TETRA-1
   Block / Key	128 / 128 bits	128 / 128 bits
   Rounds	8	12
   Branches / round	2 of 4	4 of 4
   Pre-mix rotation	ROL 1 bit	ROL8 8 bits
   S-box	16/8	4
   Key sched. consts	None	GF(28) powers
   Padding	Custom CTS	PKCS#7

   1. No Round Constants

      The schedule produces structural symmetry between rounds with the same shift modulus, enabling related-key attacks [6].

   2. Insufcient Rounds

      With (SA)= 16, the per-S-box differential probability is 24. Over 8 rounds with MDS branch number 5, the best trail proba- bility is (24)5 = 220 per round pair far short of 2128.

   3. Non-Standard Padding

   A non-standard CTS variant, undened when the message is shorter than one 16-byte block, without formal security analysis.

4. TETRA-1 DESIGN

   1. Design Overview

      TETRA-1preserves HANK-1s 128-bit block and key sizes, CBC mode, and four-sub-block partitioning. Six improvements address each weakness. Table 2 summarizes the specication.

   2. Improvement I: Sequential 4-Branch Update

      All 4 branches active every round

      Sequential dependency ensures invertibility without inverse S- boxes.

      The enhanced round transformation:

      L(i) = L(i1) F1(R(i1) SK0 ROL8(L(i1)), SK1) (3)

   3. Improvement II: 8-Bit Rotation

      ROL8(b3, b2, b1, b0)= (b2, b1, b0, b3) a full byte-level permu- tation, ensuring every byte enters a different S-box position.

   4. Improvement III: GF(28) Inverse S-Box

      Unied S-box: uniformity 4 and algebraic degree 7

      Matches AES SubBytes cryptographic properties. Saves 256 B table memory.

      SE (x)= A · x1 + 0x63, where A is the AES afne matrix and x1 = x254 computed in 11 multiplications. This achieves (SE )= 4, Walsh max = 32, algebraic degree = 7.

   5. Improvement IV: Round Constants

      RCi = 0x0 i in GF(28): 0 0 0 0 0 0 0 0 3 , injected as RCi « 24 into word 0 of each key expansion round.

   6. Improvement V: 12 Rounds

      With (SE )= 4 and branch number 5, the minimum active S-box count over 12 rounds is 60:

      Pr[12-round diff.] (4/256)60 = 2360

   7. Improvement VI: PKCS#7 Padding

   Appends p {1,…, 16} bytes of value p; always adds a full padding block, handling all block boundary cases unambigu- ously.

5. SECURITY ANALYSIS

   1. Differential Cryptanalysis

      With all four branches active and MDS branch number 5: A12 l12/2J× 5 × 2 = 60 active S-boxes over 12 rounds. Maximum differential probability: Pr (4/256)60 = 2360 » 2128.

   2. Linear Cryptanalysis

      Walsh max of SE is 32, giving per-S-box bias 23. By the piling- up lemma: 12 260×(3) = 2180.

   3. Key Schedule Security

      0 0 0 1

      1 1 1 0

      L(i) = L(i1) F2(R(i1) SK1 ROL8(R(i1)), SK2) (4)

      R(i) = R(i1) F3(L(i) SK2 ROL8(R(i1)), SK3) (5)

      Distinct RCi for all i ensures every round sub-key is structurally unique, breaking the linear relationship between sub-keys de-

      rived from related key pairs (K, K K).

      R(i) = R(i1) F4(L(i) SK3 ROL8(L(i)), SK0) (6)

      Equations (5)(6) use already-updated L(i), L(i). Decryption reverses the sequence with the same sub-keys.

   4. Avalanche Effect

      Table 3 compares avalanche over 64 single-bit ip tests. TETRA- 1 achieves a higher minimum (56 vs. 53 bits), indicating more uniform diffusion across all input bit positions.

      TABLE 4

      Comparison with Related Block Ciphers

      Cipher Block Key Rounds

6. ALGORITHM SPECIFICATION

   1. Encryption

   2. Key Expansion

7. REFERENCE IMPLEMENTATION

8. Python Cipher Library

   A complete reference implementation (tetra1_cipher.py) was built in Python 3 using only the standard library. It imple- ments all primitives from rst principles: GF(28) multiplication with irreducible polynomial 0x1F5; S-box construction via Fer- mat inversion (x254) and the AES afne transform; four 4 × 4 MDS transforms; 12-round key expansion with GF(28) round constant injection; and CBC-mode encryption and decryption

   with PKCS#7 padding.

9. REST API

   A REST API server (tetra1_api.py) is also provided with ve endpoints: POST /encrypt, POST /decrypt, POST /keygen, GET /info, and GET /health. All binary payloads are Base64- encoded; keys and IVs are 32-character hex strings. Wrong keys are detected via PKCS#7 padding validation.

10. Cross-Validation

The Python implementation was cross-validated against an in- dependent JavaScript implementation in Node.js. Both produce identical outputs for all test vectors. The canonical test vector encrypts the 16-byte block:

Key: 0F 15 71 C9 47 D9 E8 59 0C B7 AD D6 AF 7F

67 98

PT: 41 64 61 6D 00 00 00 00 00 00 00 00 00 00

TETRA-1 performs 3× more round function evaluations than

HANK-1 (12 vs. 8 rounds; 4 vs. 2 functions per round). Three optimizations offset this: (1) precomputed MDS tables replace 16 GF(28) multiplications with 16 XOR operations; (2) com-

bined S-box+MDS tables Tj[b]= Mj · SE (b) reduce each round

function to 4 lookups and 3 XORs; (3) a single S-box saves

256 bytes vs. HANK-1s two.

The original achieves 5944 cycles/byte at 62.5 MHz, yielding

84.1 Kbit/s [1]. With optimizations, TETRA-1 is estimated at

8916 cycles/byte (56 Kbit/s) still suitable for the targeted voice encryption application.

1. COMPARISON WITH RELATED WORK

   Table 4 positions TETRA-1 against related ciphers. TETRA-1 achieves = 4 matching AES while maintaining a 4-branch Feistel structure suited to constrained software. Unlike CLEFIA

   [3] which requires 18 rounds with = 8, TETRA-1 achieves equivalent formal security in 12 rounds.

2. CONCLUSION

This paper presented TETRA-1, systematically strengthening HANK-1 through six targeted improvements. Security gains are quantiable: differential uniformity 16 4; best differential trail 2360 vs. 280; Walsh maximum 68 32; round constants eliminate related-key symmetry; avalanche minimum 53 56 bits; and PKCS#7 handles all padding cases. At 56 Kbit/s on Microblaze, TETRA-1 remains suitable for constrained-device voice encryption. Future work includes MILP formal bounds, FPGA/ASIC implementation, side-channel analysis, and 192/256- bit key variants.

Acknowledgment: The author thanks H. M. Eldeeb, K. A. She- hata, N. H. Shaker, and A. A. Abdel Hafez whose HANK-1 design provided the foundation for this work.

REFERENCES

1. H. M. Eldeeb, K. A. Shehata, N. H. Shaker, and A. A. Abdel Hafez, HANK-1, a new efcient and secure block cipher for limited resources devices, in Proc. 8th Int. Conf. Electrical Engineering (ICEENG 2012), Cairo, May 2012, pp. EE271-1EE271-12.

2. NIST, Advanced Encryption Standard (AES), FIPS Publication 197, Nov. 2001.

3. T. Shirai, K. Shibutani, T. Akishita, S. Moriai, and T. Iwata, The 128-bit blockcipher CLEFIA, in Proc. FSE 2007, LNCS, vol. 4593, pp. 181195, 2007.

4. D. J. Wheeler and R. M. Needham, TEA, a tiny encryption algorithm, in Proc. FSE 1994, LNCS, vol. 1008 pp. 363366, 1995.

5. W. Wu and L. Zhang, LBlock: a lightweight block cipher, in

   Proc. ACNS 2011, LNCS, vol. 6715, pp. 327344, 2011.

6. E. Biham, New types of cryptanalytic attacks using related keys,

   J. Cryptology, vol. 7, no. 4, pp. 229246, 1994.

7. B. Kaliski, PKCS #7: Cryptographic Message Syntax v1.5,

   RFC 2315, IETF, Mar. 1998.

8. B. Schneier, Applied Cryptography, 2nd ed. Wiley, 1996.

9. W. Stallings, Cryptography and Network Security, 3rd ed. Prentice Hall, 2003.

10. J. Soto and J. Nechvatal, A statistical test suite for RNGs, NIST SP 800-22, 2001.