Simon (cipher)

Family of lightweight block ciphers

Simon

One round of Simon

General
Designers| Ray Beaulieu, Douglas Shors, Jason Smith, Stefan Treatman-Clark, Bryan Weeks, Louis Wingers NSA
First published| 2013[1]
Related to| Speck
Cipher detail
Key sizes| 64, 72, 96, 128, 144, 192 or 256 bits
Block sizes| 32, 48, 64, 96 or 128 bits
Structure| Balanced Feistel network
Rounds| 32, 36, 42, 44, 52, 54, 68, 69 or 72 (depending on block and key size)
Speed| 7.5 cpb (21.6 without SSE) on Intel Xeon 5640 (Simon128/128)
Best public cryptanalysis
Differential cryptanalysis can break 46 rounds of Simon128/128 with 2125.6 data, 240.6 bytes memory and time complexity of 2125.7 with success rate of 0.632.[2][3][4]

Simon is a family of lightweight block ciphers publicly released by the National Security Agency (NSA) in June 2013.[5][1] Simon has been optimized for performance in hardware implementations, while its sister algorithm, Speck, has been optimized for software implementations.[6][7]

The NSA began working on the Simon and Speck ciphers in 2011. The agency anticipated some agencies in the US federal government would need a cipher that would operate well on a diverse collection of Internet of Things devices while maintaining an acceptable level of security.[8]

## Description of the cipher

[edit]

The Simon block cipher is a balanced Feistel cipher with an n-bit word, and therefore the block length is 2n. The key length is a multiple of n by 2, 3, or 4, which is the value m. Therefore, a Simon cipher implementation is denoted as Simon2n/nm. For example, Simon64/128 refers to the cipher operating on a 64-bit plaintext block (n = 32) that uses a 128-bit key.[1] The block component of the cipher is uniform between the Simon implementations; however, the key generation logic is dependent on the implementation of 2, 3 or 4 keys.

Simon supports the following combinations of block sizes, key sizes and number of rounds:[1]

Block size (bits)  | Key size (bits)  | Rounds

|
|

32  | 64  | 32
48  | 72  | 36
96  | 36
64  | 96  | 42
128  | 44
96  | 96  | 52
144  | 54
128  | 128  | 68
192  | 69
256  | 72

### Description of the key schedule

[edit]

Let  S j {\displaystyle S^{j}} notate a left circular shift by  j {\displaystyle j} bits.

The key schedule is mathematically described as

k i + m = { c ⊕ ( z j ) i ⊕ k i ⊕ ( I ⊕ S − 1 ) ( S − 3 k i + 1 ) , m = 2 c ⊕ ( z j ) i ⊕ k i ⊕ ( I ⊕ S − 1 ) ( S − 3 k i + 2 ) , m = 3 c ⊕ ( z j ) i ⊕ k i ⊕ ( I ⊕ S − 1 ) ( S − 3 k i + 3 ⊕ k i + 1 ) , m = 4 {\displaystyle k_{i+m}=\left\\{{\begin{array}{ll}c\oplus \left(z_{j}\right)_{i}\oplus k_{i}\oplus \left(I\oplus S^{-1}\right)\left(S^{-3}k_{i+1}\right),&m=2\\\c\oplus \left(z_{j}\right)_{i}\oplus k_{i}\oplus \left(I\oplus S^{-1}\right)\left(S^{-3}k_{i+2}\right),&m=3\\\c\oplus \left(z_{j}\right)_{i}\oplus k_{i}\oplus \left(I\oplus S^{-1}\right)\left(S^{-3}k_{i+3}\oplus k_{i+1}\right),&m=4\\\\\end{array}}\right.}

The key schedule structure may or may not be balanced. The key word count of  m {\displaystyle m} is used to determine the structure of the key expansion, resulting in a total bit width of  m ∗ n {\displaystyle m*n} . The key word expansion consists of a right shift, XOR and a constant sequence,  z x {\displaystyle z_{x}} . The  z x {\displaystyle z_{x}} bit operates on the lowest bit of the key word once per round.[7]

#### Description of the constant sequence

[edit]

The constant sequence,  z x {\displaystyle z_{x}} , is created by a Linear Feedback Shift Register (LFSR). The logical sequence of bit constants is set by the value of the key and block sizes. The LFSR is created by a 5-bit field. The constant bit operates on a key block once per round on the lowest bit in order to add non-key-dependent entropy to the key schedule. The LFSR has different logic for each  z x {\displaystyle z_{x}} sequence; however, the initial condition is the same for encryption. The initial condition of the LFSR for decryption varies on the round.

Constant Sequence

z 0 = 11111010001001010110000111001101111101000100101011000011100110 {\displaystyle z_{0}=11111010001001010110000111001101111101000100101011000011100110}
z 1 = 10001110111110010011000010110101000111011111001001100001011010 {\displaystyle z_{1}=10001110111110010011000010110101000111011111001001100001011010}
z 2 = 10101111011100000011010010011000101000010001111110010110110011 {\displaystyle z_{2}=10101111011100000011010010011000101000010001111110010110110011}
z 3 = 11011011101011000110010111100000010010001010011100110100001111 {\displaystyle z_{3}=11011011101011000110010111100000010010001010011100110100001111}
z 4 = 11010001111001101011011000100000010111000011001010010011101111 {\displaystyle z_{4}=11010001111001101011011000100000010111000011001010010011101111}

## Cryptanalysis

[edit]

The designers claim that Simon, though a "lightweight" cipher, is designed to have the full security possible for each block and key size, against standard chosen-plaintext (CPA) and chosen-ciphertext (CCA) attacks. Resistance against related-key attacks was also stated as a goal, though a less crucial one as attacks in that model are not relevant for typical use cases.[9]: 2 No effort was made to resist attacks in the known-key distinguishing attack model, nor did the designers evaluate Simon for use as a hash function.[10]

As of 2018, no successful attack on full-round Simon of any variant is known. Due to interest in Simon and Speck, about 70 cryptanalysis papers have been published on them.[9]: 10 As is typical for iterated ciphers, reduced-round variants have been successfully attacked. The best published attacks on Simon in the standard attack model (CPA/CCA with unknown key) are differential cryptanalysis attacks; these make it through about 70–75% of the rounds of most variants, though these best attacks are only marginally faster than brute-force.[11][12] [13][9]: 12 The design team states that while designing Simon, they found differential attacks to be the limiting attacks, i.e. the type of attack that makes it through the most rounds; they then set the number of rounds to leave a security margin similar to AES-128's at approximately 30%.[9]: 12–13

Best known attacks on Simon (in standard attack model)  Variant  | Rounds attacked  | Time complexity  | Data complexity  | Attack type

|
|
|
|

Simon128/256  | 53/72 (74%)  | 2248 | 2127.6 | Linear Hull[11]
Simon128/192  | 51/69 (74%)  | 2184 | 2127.6 | Linear Hull[11]
Simon128/128  | 49/68 (72%)  | 2120 | 2127.6 | Linear Hull[11]
Simon96/144  | 38/54 (70%)  | 2136 | 295.2 | Linear Hull[11]
Simon96/96  | 37/52 (71%)  | 288 | 295.2 | Linear Hull[11]
Simon64/128  | 31/44 (70%)  | 2120 | 263.5 | Linear Hull[11]
Simon64/96  | 30/42 (71%)  | 288 | 263.5 | Linear Hull[11]
Simon48/96  | 25/36 (69%)  | 280 | 247.9 | Linear Hull[11]
Simon48/72  | 24/36 (67%)  | 256 | 247.9 | Linear Hull[11]
Simon32/64  | 24/32 (75%)  | 263 | 232 | Integral[12]

Simon has been criticized for having too small a security margin, i.e. too few rounds between the best attacks and the full cipher, in comparison to more conservative ciphers such as ChaCha20.[14] Ciphers with small security margins are more likely to be broken by future advances in cryptanalysis. Simon's design team counters that there is a real-world cost to unnecessarily large security margins, especially on lightweight devices, that cryptanalysis during the design phase allowed the number of rounds to be set appropriately, and that they targeted AES's security margin.[9]: 17

Simon includes a round counter in the key schedule. The designers state this was included to block slide and rotational cryptanalysis attacks.[9]: 16 Still, rotational-XOR cryptanalysis has been used to find distinguishers against reduced-round versions of related ciphers like Speck.[15] Though the authors don't describe standard key-recovery attacks based on their distinguishers, their best distinguishers on Simon32 and Simon48 in the known-key distinguishing attack model for certain weak key classes make it through slightly more rounds than the best differential distinguishers. One of the authors has said that his research was resource-constrained and that rotational-XOR distinguishers on more rounds are probably possible. The designers also state that Simon was not designed to resist known-key distinguishing attacks (which do not directly compromise the confidentiality of ciphers).[10]: 8

The designers state that NSA cryptanalysis found the algorithms to have no weaknesses, and security commensurate with their key lengths.[8]: 2 The design team says that their cryptanalysis included linear and differential cryptanalysis using standard techniques such as Matsui's algorithm and SAT/SMT solvers, though a full list of techniques used is not given.[9]: 10 Simon's designers have been criticized for not providing more details on NSA cryptanalysis of the ciphers.[16]

The NSA has approved Simon128/256 and Speck128/256 for use in U.S. National Security Systems, though AES-256 is still recommended for non-constrained applications.[17]

## Standardization efforts and controversies

[edit]

Initial attempts to standardise Simon and Speck failed to meet International Organization for Standardization super-majority required by the process and the ciphers were not adopted.[18][16] Expert delegates to the ISO from several countries including Germany, Japan and Israel opposed the efforts by the NSA to standardise the Simon and Speck ciphers, citing concerns that the NSA is pushing for their standardisation with knowledge of exploitable weaknesses in the ciphers. The position was based on partial evidence of weaknesses in the ciphers, lack of clear need for standardisation of the new ciphers, and the NSA's previous involvement in the creation and promotion of the backdoored Dual_EC_DRBG cryptographic algorithm.[19][20]

In response to concerns, the NSA stated that more than 70 security analysis papers from some of the world's leading cryptographers support NSA's conclusion that the algorithms are secure and NSA affirmed that it is not aware of any cryptanalytic techniques that would allow them or anyone else to exploit Simon or Speck.

After initial attempts to standardise the ciphers failed, the ISO standardised Simon and Speck in other working groups. As of October 2018, the Simon and Speck ciphers have been standardized by ISO as a part of the RFID air interface standard, International Standard ISO/29167-21 (for Simon) and International Standard ISO/29167-22 (for Speck), making them available for use by commercial entities.

## See also

[edit]

* Balanced Boolean function
* Bent function

## References

[edit]

1. ^ a b c d The Simon and Speck Families Of Lightweight Block Ciphers (PDF). ePrint. Retrieved 2016-06-16.
2. ^ "Differential and Linear Cryptanalysis of Reduced-Round Simon". Retrieved 2014-04-16.
3. ^ Abed, Farzaneh; List, Eik; Lucks, Stefan; Wenzel, Jakob (27 March 2014). Differential Cryptanalysis of Round-Reduced Simon and Speck (PDF). FSE 2014\. conference slides. Bauhaus-Universität Weimar.
4. ^ Alkhzaimi, Hoda; Lauridsen, Martin (28 Aug 2013), Cryptanalysis of the SIMON Family of Block Ciphers (PDF), International Association for Cryptologic Research (IACR) - via Cryptology ePrint Archive
5. ^ Schneier, Bruce (July 2013). "SIMON and SPECK: New NSA Encryption Algorithms". Schneier on Security. Retrieved 2013-07-17.
6. ^ Claire Swedberg (17 July 2015). "NSA Offers Block Ciphers to Help Secure RFID Transmissions". RFID Journal. Archived from the original on July 17, 2015.
7. ^ a b Brian Degnan and Gregory Durgin (10 November 2017). "Simontool: Simulation Support for the Simon Cipher". IEEE Journal of Radio Frequency Identification. 1 (2): 195–201\. Bibcode:2017IJRFI...1..195D. doi:10.1109/JRFID.2017.2771216. S2CID 37476795.
8. ^ a b Beaulieu, Ray; Shors, Douglas; Smith, Jason; Treatman-Clark, Stefan; Weeks, Bryan; Winger, Louis. "Simon and Speck: Block Ciphers for the Internet of Things" (PDF). Retrieved 2017-11-23.
9. ^ a b c d e f g "Notes on the design and analysis of Simon and Speck" (PDF). 2018-01-19. Retrieved 2018-06-13.
10. ^ a b Beaulieu, Ray; Shors, Douglas; Smith, Jason; Treatman-Clark, Stefan; Weeks, Bryan; Wingers, Louis (2013-06-19). "The SIMON and SPECK Families of Lightweight Block Ciphers". Retrieved 2016-09-20.
11. ^ a b c d e f g h i j Chen, Huaifeng; Wang, Xiaoyun (2018-01-19). "Improved Linear Hull Attack on Round-Reduced SIMON with Dynamic Key-guessing Techniques" (PDF). Retrieved 2018-06-13.
12. ^ a b Chu, Zhihui; Chen, Huaifeng; Xiaoyun, Wang; Dong, Xiaoyang; Li, Lu (2018-01-19). "Improved Integral Attacks on SIMON32 and SIMON48 with Dynamic Key-Guessing Techniques". Security and Communication Networks. 2018: 5160237:1–5160237:11. doi:10.1155/2018/5160237.
13. ^ Lee, HoChang; Kim, Seojin; Kang, HyungChul; Hong, Deukjo; Sung, Jaechul; Hong, Seokhie (February 2018). "Calculating the Approximate Probability of Differentials for ARX-Based Cipher Using SAT Solver". Journal of the Korea Institute of Information Security and Cryptology (in Korean). 28 (1): 15–24\. doi:10.13089/JKIISC.2018.28.1.15.
14. ^ Bernstein, Daniel J. [@hashbreaker] (2016-04-12). "NSA claims that having 70% of Simon+Speck broken is ok" (Tweet). Retrieved 2018-06-13 - via Twitter.
15. ^ Liu, Yunwen; De Witte, Glenn; Ranea, Adrián; Ashur, Tomer (2017). "Rotational-XOR Cryptanalysis of Reduced-round SPECK" (PDF). Retrieved 2018-06-13.
16. ^ a b Ashur, Tomer. "[PATCH v2 0/5] crypto: Speck support".
17. ^ National Security Agency (2016-11-18). "Algorithms to Support the Evolution of Information Assurance Needs".
18. ^ Insights an reasons why Speck and Simon have been rejected from ISO standardization
19. ^ "Distrustful U.S. allies force spy agency to back down in encryption fight". Reuters. 2017-09-21.
20. ^ Ashur, Tomer; Luykx, Atul (2021-01-15). "An Account of the ISO/IEC Standardization of the Simon and Speck Block Cipher Families". In Avoine, Gildas; Hernandez-Castro, Julio (eds.). Security of Ubiquitous Computing Systems. Springer. pp. 63–78\. doi:10.1007/978-3-030-10591-4_4. ISBN 978-3-030-10590-7. S2CID 234119694.

* 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
* QARMA
* 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
* NSA Suite B
* CNSA

Utilization|

* Initialization vector
* Mode of operation
* Padding

* v
* t
* e

Cryptography

General|

* History of cryptography
* Outline of cryptography
* Classical cipher
* Cryptographic protocol
* Authentication protocol
* Cryptographic primitive
* Cryptanalysis
* Cryptocurrency
* Cryptosystem
* Cryptographic nonce
* Cryptovirology
* Hash function
* Cryptographic hash function
* Key derivation function
* Secure Hash Algorithms
* Digital signature
* Kleptography
* Key (cryptography)
* Key exchange
* Key generator
* Key schedule
* Key stretching
* Keygen
* Machines
* 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

*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template