The KATAN/KTANTAN Family of Block Ciphers

KATAN/KTANTAN is a family of hardware oriented block ciphers designed by Chrstophe de Canniere, Orr Dunkelman, and Miroslav Knezevic. Both KATAN and KTANTAN have three variants each, of 32-bit, 48-bit, or 64-bit block. All ciphers share the same key length (of 80 bits), where the only difference between KATAN-n and KTANTAN-n is the key schedule.
The resulting ciphers are exteremly efficient in hardware, and offer a set of suitable solution for low-end devices that need encryption (such as RFID tags).

News

• 5.2.10 - The KATAN/KTANTAN family is presented at BCRYPT's workshop on RFID security.
• 14.9.09 - The KATAN/KTANTAN family is presented at ECRYPT II meeting in K.U. Leuven (slides).
• 8.8.09 - The KATAN/KTANTAN family is presented at CHES 2009 (slides or in PDF format).
• 8.5.09 - The KATAN/KTANTAN family is presented at TU-Graz (slides).

The Original Paper (CHES 2009)

Our original paper (proceedings version) can be found here.

Hardware Performance

Optimization target: Size (synthesized with Synopsys Design Vision version Y-2006.06, using UMC 0.13\mu m Low-Leakage CMOS library).

Cipher	Throughpout (Kbps @ 100 KHz)	Size (GE)
KATAN32	12.5	802
KATAN48	18.8	927
KATAN64	8.4	1027
KATAN64	25.0	1054
KATANTAN32	12.5	462
KATANTAN48	18.8	588
KATANTAN64	25.0	688

Optimization target: Speed (using UMC 0.13\mu m High-Speed CMOS library).

Cipher	Size (GE)	Frequency (GHz)	Throughpout (Mbps)
KATAN32	975	2.86	1071.4
KATAN48	1201	2.86	1611.4
KATAN64	1399	2.50	1882.5
KATANTAN32	1328	1.25	468.7
KATANTAN48	1677	1.23	696.3
KATANTAN64	1589	1.19	896.4

Security

At the moment, we are aware of one attack that can find the key of KTANTAN32 with time complexity of 2^79 (rather than 2^80). The paper by Andrey Bogdanov and Christian Rechberger was presented at Selected Areas in Cryptography 2010. The KATAN family is still secure, and the attack does not carry over to that family.

Our security goals were:

• For an n-bit block size, no differential characteristic with probability greater than 2^{-n} exists for 128 rounds (about half the number of rounds of the cipher).
• For an n-bit block size, no linear approximation with bias greater than 2^{-n/2} exists for 128 rounds.
• No related-key key-recovery or slide attack with time complexity smaller than 2^{80} exists on the entire cipher.
• High enough algebraic degree for the equation describing half the cipher to thwart any algebraic attack.

The currently best known actual security bounds we have are:

• For KATAN/KTANTAN-32:
  • Best 42-round differential characteristic has probability at most 2^{-11}.
  • Best 42-round linear approximation has probability at most 2^{-6}.
• For KATAN/KTANTAN-48:
  • Best 43-round differential characteristic has probability at most 2^{-18}.
  • Best 43-round linear approximation has probability at most 2^{-10}.
• For KATAN/KTANTAN-64:
  • Best 37-round differential characteristic has probability at most 2^{-20}.
  • Best 37-round linear approximation has probability at most 2^{-11}.

We would like to encourage people to work on KATAN/KTANTAN and try to break the block ciphers in the family. If you do so, please let us know. Of course, if you have better security bounds, we'd be happy to hear so too.

Reference Implementation

For those interested to verify their implementations, we offer a bit-sliced reference implementation, as well as a set of a few test vectors:

Cipher	Key	Plaintext	Ciphertext
KATAN32	FFFF FFFF FFFF FFFF FFFF_x	0000 0000_x	7E1F F945_x
KATAN32	0000 0000 0000 0000 0000_x	FFFF FFFF_x	432E 61DA_x
KATAN48	FFFF FFFF FFFF FFFF FFFF_x	0000 0000 0000_x	4B7E FCFB 8659_x
KATAN48	0000 0000 0000 0000 0000_x	FFFF FFFF FFFF_x	A4BD 196D 0B85_x
KATAN64	FFFF FFFF FFFF FFFF FFFF_x	0000 0000 0000 0000_x	21F2 E99C 0FAB 828A_x
KATAN64	0000 0000 0000 0000 0000_x	FFFF FFFF FFFF FFFF_x	C956 100D BEB6 4BA8_x
KATANTAN32	FFFF FFFF FFFF FFFF FFFF_x	0000 0000_x	22EA 3988_x
KATANTAN32	0000 0000 0000 0000 0000_x	FFFF FFFF_x	432E 61DA_x
KATANTAN48	FFFF FFFF FFFF FFFF FFFF_x	0000 0000 0000_x	936D 0FA3 3A05_x
KATANTAN48	0000 0000 0000 0000 0000_x	FFFF FFFF FFFF_x	A4BD 196D 0B85_x
KATANTAN64	FFFF FFFF FFFF FFFF FFFF_x	0000 0000 0000 0000_x	C02D E05B FA19 4B16_x
KATANTAN64	0000 0000 0000 0000 0000_x	FFFF FFFF FFFF FFFF_x	C956 100D BEB6 4BA8_x