Chrsitophe de Canniere
Orr Dunkelman
Miroslav Knezevic

Valid HTML 4.01 Transitional

Valid CSS!

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).

The KATAN/KTANTAN Block Cipher

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

Contact Orr regarding this website.
The design of the website is based on the design of the Haifa Linux Club website we would like to thank the webmasters of that website (besides Orr) for the design.