MISTY1

Block cipher

Mitsuru Matsui,
Tetsuya Ichikawa,
Toru Sorimachi,
Toshio Tokita,
Atsuhiro Yamagishi

First published1995SuccessorsCamellia, KASUMICertificationCRYPTREC (Candidate), NESSIECipher detailKey sizes128 bitsBlock sizes64 bitsStructureNested Feistel networkRounds4×n (8 recommended)Best public cryptanalysisIntegral cryptanalysis leading to full key recovery with 2^63.9999 chosen ciphertexts and 2⁷⁹ time, or 2⁶⁴ chosen ciphertexts and 2^69.5 time.^[1]

In cryptography, MISTY1 (or MISTY-1) is a block cipher designed in 1995 by Mitsuru Matsui and others for Mitsubishi Electric.^[2]^[3]

MISTY1 is one of the selected algorithms in the European NESSIE project, and has been among the cryptographic techniques recommended for Japanese government use by CRYPTREC in 2003; however, it was dropped to "candidate" by CRYPTREC revision in 2013. However, it was successfully broken in 2015 by Yosuke Todo using integral cryptanalysis; this attack was improved in the same year by Achiya Bar-On.^[1]

"MISTY" can stand for "Mitsubishi Improved Security Technology"; it is also the initials of the researchers involved in its development: Matsui Mitsuru, Ichikawa Tetsuya, Sorimachi Toru, Tokita Toshio, and Yamagishi Atsuhiro.^[4]

MISTY1 is covered by patents, although the algorithm is freely available for academic (non-profit) use in RFC 2994, and there's a GPLed implementation by Hironobu Suzuki (used by, e.g. Scramdisk).

Security

MISTY1 is a Feistel network with a variable number of rounds (any multiple of 4), though 8 are recommended. The cipher operates on 64-bit blocks and has a key size of 128 bits. MISTY1 has an innovative recursive structure; the round function itself uses a 3-round Feistel network. MISTY1 claims to be provably secure against linear and differential cryptanalysis.

KASUMI

KASUMI is a successor of the MISTY1 cipher which was supposed to be stronger than MISTY1 and has been adopted as the standard encryption algorithm for European mobile phones. In 2005, KASUMI was broken, and in 2010 a new paper was published (explained below) detailing a practical attack on the cipher; see the article for more details.

In the paper "Block Ciphers and Stream Ciphers" by Alex Biryukov, it is noted that KASUMI, also termed A5/3, is a strengthened version of block cipher MISTY1 running in a Counter mode.^[5]

However, in 2010 Dunkelman, Keller, and Shamir showed that KASUMI is not as strong as MISTY1;^[6] the KASUMI attack will not work against MISTY1.

References

^ ^a ^b Achiya Bar-On (30 July 2015). "A 2⁷⁰ Attack on the Full MISTY1" (PDF).
^ Mitsuru Matsui (1997). Block encryption algorithm MISTY. Fast Software Encryption, 4th International Workshop, FSE '97, LNCS 1267. pp. 64–74. ISBN 9783540632474.
^ Mitsuru Matsui (July 1996). "Block encryption algorithm MISTY". Technical report of IEICE ISEC96-11 (PDF). Archived from the original (PDF) on August 23, 2000.
^ "Episodes in the development of MISTY". Archived from the original on 2005-03-22.
^ Alex Biryukov (2004). "Block Ciphers and Stream Ciphers: The State of the Art".
^ Orr Dunkelman and Nathan Keller and Adi Shamir (2010). "A Practical-Time Attack on the KASUMI Cryptosystem Used in GSM and 3G Telephony". Cryptology ePrint Archive.

External links

RFC 2994
Mitsubishi - About MISTY
MISTY1 patent statement from Mitsubishi
John Savard's description of MISTY
SCAN's entry on MISTY1

v t e Block ciphers (security summary)
Common algorithms	AES Blowfish DES (internal mechanics, Triple DES) Serpent SM4 Twofish
Less common algorithms	ARIA Camellia CAST-128 GOST IDEA LEA RC5 RC6 SEED Skipjack TEA XTEA
Other algorithms	3-Way Adiantum Akelarre Anubis Ascon BaseKing BassOmatic BATON BEAR and LION CAST-256 Chiasmus CIKS-1 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA CMEA Cobra COCONUT98 Crab Cryptomeria/C2 CRYPTON CS-Cipher DEAL DES-X DFC E2 FEAL FEA-M FROG G-DES Grand Cru Hasty Pudding cipher Hierocrypt ICE IDEA NXT Intel Cascade Cipher Iraqi Kalyna KASUMI KeeLoq KHAZAD Khufu and Khafre KN-Cipher Kuznyechik Ladder-DES LOKI (97, 89/91) Lucifer M6 M8 MacGuffin Madryga MAGENTA MARS Mercy MESH MISTY1 MMB MULTI2 MultiSwap New Data Seal NewDES Nimbus NOEKEON NUSH PRESENT Prince Q RC2 REDOC Red Pike S-1 SAFER SAVILLE SC2000 SHACAL SHARK Simon Speck Spectr-H64 Square SXAL/MBAL Threefish Treyfer UES xmx XXTEA Zodiac
Design	Feistel network Key schedule Lai–Massey scheme Product cipher S-box P-box SPN Confusion and diffusion Round Avalanche effect Block size Key size Key whitening (Whitening transformation)
Attack (cryptanalysis)	Brute-force (EFF DES cracker) MITM Biclique attack 3-subset MITM attack Linear (Piling-up lemma) Differential Impossible Truncated Higher-order Differential-linear Distinguishing (Known-key) Integral/Square Boomerang Mod n Related-key Slide Rotational Side-channel Timing Power-monitoring Electromagnetic Acoustic Differential-fault XSL Interpolation Partitioning Rubber-hose Black-bag Davies Rebound Weak key Tau Chi-square Time/memory/data tradeoff
Standardization	AES process CRYPTREC NESSIE
Utilization	Initialization vector Mode of operation Padding

v t e Cryptography
General	History of cryptography Outline of cryptography Cryptographic protocol Authentication protocol Cryptographic primitive Cryptanalysis Cryptocurrency Cryptosystem Cryptographic nonce Cryptovirology Hash function Cryptographic hash function Key derivation function Digital signature Kleptography Key (cryptography) Key exchange Key generator Key schedule Key stretching Keygen Cryptojacking malware Ransomware Random number generation Cryptographically secure pseudorandom number generator (CSPRNG) Pseudorandom noise (PRN) Secure channel Insecure channel Subliminal channel Encryption Decryption End-to-end encryption Harvest now, decrypt later Information-theoretic security Plaintext Codetext Ciphertext Shared secret Trapdoor function Trusted timestamping Key-based routing Onion routing Garlic routing Kademlia Mix network
Mathematics	Cryptographic hash function Block cipher Stream cipher Symmetric-key algorithm Authenticated encryption Public-key cryptography Quantum key distribution Quantum cryptography Post-quantum cryptography Message authentication code Random numbers Steganography
Category

Mitsubishi Electric

Mitsubishi

Divisions and
subsidiaries

Current	Green Cycle Systems Corporation Iconics Mitsubishi Electric China Mitsubishi Electric Europe Mitsubishi Electric United States Warner Bros.
Defunct	Apricot Computers¹ Diatone¹

Joint ventures and
shareholdings

Current	Mitsubishi Hitachi Home Elevator Powerex (50%) Renesas Electronics (25.05%) Shanghai Mitsubishi Elevator Shihlin Electric (20%) TMEIC
Defunct	NEC-Mitsubishi Electric Visual Systems²

Products, services
and standards

Current	Mitsubishi AAM-4 Camellia CC-Link DiamondTouch Diamond Vision KASUMI MelsecNet MISTY1 Privacy Enhanced Computer Display Saffron Type System Seam carving SERVIS-2 Superbird-C2 Type 3 Chū-SAM
Past	Diamondtron Electrohome MELCOM MOLDIS Molectron Pedion Trium