Speck (cipher)

Speck is a family of lightweight block ciphers publicly released by the National Security Agency (NSA) in June 2013.[3] Speck has been optimized for performance in software implementations, while its sister algorithm, Simon, has been optimized for hardware implementations. Speck is an add–rotate–xor (ARX) cipher.

Speck
3 rounds of Speck with 2-word key schedule
General
DesignersRay Beaulieu, Douglas Shors, Jason Smith, Stefan Treatman-Clark, Bryan Weeks, Louis Wingers NSA
First published2013
Related toSimon, Threefish
Cipher detail
Key sizes64, 72, 96, 128, 144, 192 or 256 bits
Block sizes32, 48, 64, 96 or 128 bits
StructureARX
Rounds22–34 (depending on block and key size)
Speed2.6 cpb (5.7 without SSE) on Intel Xeon 5640 (Speck128/128)
Best public cryptanalysis
No attacks are known on the full ciphers, but reduced-round versions have been attacked. Differential cryptanalysis can break about 70–75% of the rounds of most variants slightly faster than brute-force;[1][2] see #Cryptanalysis.

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.[4]

Cipher description

Speck supports a variety of block and key sizes. A block is always two words, but the words may be 16, 24, 32, 48 or 64 bits in size. The corresponding key is 2, 3 or 4 words. The round function consists of two rotations, adding the right word to the left word, xoring the key into the left word, then xoring the left word into the right word. The number of rounds depends on the parameters selected, as follows:[3]

Block size (bits) Key size (bits) Rounds
2×16 = 32 4×16 = 64 22
2×24 = 48 3×24 = 72 22
4×24 = 96 23
2×32 = 64 3×32 = 96 26
4×32 = 128 27
2×48 = 96 2×48 = 96 28
3×48 = 144 29
2×64 = 128 2×64 = 128 32
3×64 = 192 33
4×64 = 256 34

The key schedule uses the same round function as the main block cipher.

Reference code

The following is the designers' reference implementation, written in C, of the Speck variant with a 128-bit block size and key, where key = (K[1], K[0]). It is adapted from their IACR ePrint.[3]

#include <stdint.h>

#define ROR(x, r) ((x >> r) | (x << (64 - r)))
#define ROL(x, r) ((x << r) | (x >> (64 - r)))
#define R(x, y, k) (x = ROR(x, 8), x += y, x ^= k, y = ROL(y, 3), y ^= x)
#define ROUNDS 32

void encrypt(uint64_t ct[2],
             uint64_t const pt[2],            
             uint64_t const K[2])
{
   uint64_t y = pt[0], x = pt[1], b = K[0], a = K[1];

   R(x, y, b);
   for (int i = 0; i < ROUNDS - 1; i++) {
      R(a, b, i);
      R(x, y, b);
   }

   ct[0] = y;
   ct[1] = x;
}

Note that this code computes the round keys (key schedule) on-demand. In practice, as with other block ciphers it is common for implementations to compute the round keys just once and cache them, rather than recomputing them for every block encrypted or decrypted. Although, as the authors point out, "Given that small code size was a major goal of the design, it made sense to reuse the round function for round key generation. This approach enables on-the-fly round key generation for microcontroller implementations, using just the round function code, very little ROM, and no RAM beyond what is required to hold the key and plaintext." [5]

For 16-bit words (Speck32), the rotates are 7 bits right and 2 bits left; for all other word sizes, they are 8 and 3 as shown here.

If the key is more than 2 words long, there are 2 or 3 a values, which are used in rotation.

Endianness

The original Speck paper does not explicitly state the endianness of bytes when the plaintext block is interpreted as the two words used in the cipher algorithm. The test vectors given in the paper suggest big-endian order. However, the authors of the algorithm have advised some implementers[6] that little-endian byte order is to be used for keys, plaintext, and ciphertext, and the practice was accepted by others.[7]

Performance

According to ECRYPT's stream cipher benchmarks (eBASC), Speck is one of the fastest ciphers available, both for long as well as short messages. Some median performances for long messages (128-bit, 128-block size version) are: 1.99 cycles per byte (cpb) on an AMD Ryzen 7 1700; 1.27 cpb on an Intel Core i5-6600; 15.96 cpb on a Broadcom BCM2836 Cortex A7.[8] For example, on the ARMv7 platform, Speck is about 3 times faster than AES.[9]

When implemented on 8-bit AVR microcontroller, Speck encryption with 64-bit blocks and 128-bit key consumes 192 bytes of Flash, temporary variables consume 112 bytes of RAM, and takes 164 cycles to encrypt each byte in the block.[10]

Salsa20 is a stream cipher with comparable performance, but it is difficult to use stream ciphers securely in some applications where block ciphers like Speck work well. This led Google to add an implementation of Speck in Linux kernel version 4.17, planning to offer it as an option for disk encryption on low-end Android devices that would otherwise be unencrypted due to slow AES performance on processors that lack AES instructions.[11][12] Speck was later dropped from the Linux kernel due to backlash and concerns, and Google switched to the Adiantum algorithm instead.[13][14][15]

Security

Cryptanalysis

The designers claim that Speck, 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.[16]:2 No effort was made to resist attacks in the known-key distinguishing attack model, nor did the designers evaluate Speck for use as a hash function.[3]:8

As of 2018, no successful attack on full-round Speck of any variant is known. Due to interest in Simon and Speck, about 70 cryptanalysis papers have been published on them.[16]:10 As is typical for iterated ciphers, reduced-round variants have been successfully attacked. The best published attacks on Speck 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.[1][2][16]:12 The design team states that while designing Speck, 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%.[16]:12–13

Best known attacks on Speck (in standard attack model)
Variant Rounds attacked Time complexity Data complexity Space complexity Attack type
Speck128/256 25/34 (74%) 2253.35 2125.35 222 differential[1]
Speck128/192 24/33 (73%) 2189.35 2125.35 222 differential[1]
Speck128/128 23/32 (72%) 2125.35 2125.35 222 differential[1]
Speck96/144 21/29 (72%) 2143.94 295.94 222 differential[1]
Speck96/96 20/28 (71%) 295.94 295.94 222 differential[1]
Speck64/128 20/27 (74%) 2125.56 261.56 222 differential[1]
Speck64/96 19/26 (73%) 293.56 261.56 222 differential[1]
Speck48/96 17/23 (74%) 295.8 247.8 222 differential[2]
Speck48/72 16/22 (73%) 271.8 247.8 222 differential[2]
Speck32/64 15/22 (68%) 263.39 231.39 222 differential[2]

Speck 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.[17] Ciphers with small security margins are more likely to be broken by future advances in cryptanalysis. Speck'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.[16]:17

Speck includes a round counter in the key schedule. The designers state this was included to block slide and rotational cryptanalysis attacks.[16]:16 Still, rotational-XOR cryptanalysis has been used to find distinguishers against reduced-round versions of Speck.[18] Though the authors don't describe standard key-recovery attacks based on their distinguishers, their best distinguishers on Speck32 and Speck48 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.[19] However, this type of cryptanalysis assumes the related-key or even the known-key attack models,[18] which are not a concern in typical cryptographic protocols and solutions.[20]:8 The designers also state that Speck was not designed to resist known-key distinguishing attacks (which do not directly compromise the confidentiality of ciphers).[3]:8

The designers state that NSA cryptanalysis found the algorithms to have no weaknesses, and security commensurate with their key lengths.[4]: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.[16]:10 Speck's designers have been criticized for not providing more details on NSA cryptanalysis of the ciphers.[19]

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.[21]

Side-channel attacks

Being an ARX cipher, Speck does not use S-boxes or other lookup tables; it is therefore naturally immune to cache-timing attacks.[4]:12 This contrasts with ciphers that use lookup tables such as AES, which have been shown to be vulnerable to such attacks. However, like most block ciphers (including AES) Speck is vulnerable to power analysis attacks unless hardware countermeasures are taken.[22][4]:12

Block and key sizes

Although the Speck family of ciphers includes variants with the same block and key sizes as AES (Speck128/128, Speck128/192, and Speck128/256), it also includes variants with block size as low as 32 bits and key size as low as 64 bits. These small block and key sizes are insecure for general use, as they can allow birthday attacks and brute-force attacks, regardless of the formal security of the cipher.[23] The designers state that these block and key sizes were included for highly resource-constrained devices where nothing better is possible, or where only very small amounts of data are ever encrypted, e.g. in RFID protocols.[4]:2–3 Only the variant with a 128-bit block size and 256-bit key size is approved for use in U.S. National Security Systems.[21]

Standardization efforts and controversies

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.[24][19] 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.[25]

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[26]

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.

On August 7, 2018, Speck was removed from the Linux kernel 4.20 release completely.[15]

References
  1. Ling, Song; Huang, Zhangjie; Yang, Qianqian (2016-06-30). "Automatic Differential Analysis of ARX Block Ciphers with Application to SPECK and LEA" (PDF). Retrieved 2018-05-06.
  2. 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.
  3. 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.
  4. Beaulieu, Ray; Shors, Douglas; Smith, Jason; Treatman-Clark, Stefan; Weeks, Bryan; Winger, Louis (2015-07-09). "Simon and Speck: Block Ciphers for the Internet of Things" (PDF). Retrieved 2017-11-23.
  5. "Notes on the design and analysis of Simon and Speck" (PDF). eprint.iacr.org. Retrieved 2018-04-26.
  6. "Re: [PATCH 0/5] crypto: Speck support". www.mail-archive.com. Retrieved 2018-04-12.
  7. "SPECK – Crypto++ Wiki". www.cryptopp.com. Retrieved 2018-04-12.
  8. "ECRYPT Benchmarking of Stream Ciphers". Retrieved 22 June 2017.
  9. "Linux Cryptography — Re: [PATCH v2 0/5] crypto: Speck support". www.spinics.net. Retrieved 2018-08-06.
  10. "The Simon and Speck Block Ciphers on AVR 8-bit Microcontrollers" (PDF). Retrieved 25 September 2017.
  11. "crypto: speck – add support for the Speck block cipher". 2018-02-14. Retrieved 2019-01-11.
  12. "NSA's Encryption Algorithm in Linux Kernel 4.17 Leaves Users Miffed | It's FOSS". It's FOSS. 2018-08-04. Retrieved 2018-08-06.
  13. "The Controversial Speck Encryption Code Will Indeed Be Dropped From The Linux Kernel – Phoronix". www.phoronix.com. 2018-09-04. Retrieved 2018-12-08.
  14. "Adiantum Queued Ahead Of Linux 4.21 As Google's Speck Replacement". www.phoronix.com. 2018-11-29. Retrieved 2019-01-11.
  15. "kernel/git/herbert/cryptodev-2.6.git – Crypto API Dev". git.kernel.org. Retrieved 2018-12-08.
  16. "Notes on the design and analysis of Simon and Speck" (PDF). 2018-01-19. Retrieved 2018-06-13.
  17. 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.
  18. Liu, Yunwen; De Witte, Glenn; Ranea, Adrián; Ashur, Tomer (2017). "Rotational-XOR Cryptanalysis of Reduced-round SPECK" (PDF). Retrieved 2018-06-13.
  19. Ashur, Tomer. "[PATCH v2 0/5] crypto: Speck support".
  20. Bernstein, Daniel J. (2015-04-27). "Salsa20 security" (PDF). Retrieved 2018-06-13.
  21. National Security Agency (2016-11-18). "Algorithms to Support the Evolution of Information Assurance Needs".
  22. Gamaarachchi, Hasindu; Ganegoda, Harsha; Ragel, Roshan (2017-07-20). "Breaking Speck cryptosystem using correlation power analysis attack". Journal of the National Science Foundation of Sri Lanka. 45 (4): 393–404. doi:10.4038/jnsfsr.v45i4.8233. Retrieved 2018-06-13.
  23. Bhargavan, Karthikeyan; Leurent, Gaëtan (2016). On the Practical (In-)Security of 64-bit Block Ciphers: Collision Attacks on HTTP over TLS and OpenVPN (PDF). ACM Conference on Computer and Communications Security. pp. 456–467. doi:10.1145/2976749.2978423.
  24. Insights an reasons why Speck and Simon have been rejected from ISO standardization
  25. "Distrustful U.S. allies force spy agency to back down in encryption fight".
  26. The Simon and Speck Information Paper
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.