Lightweight crypto standards (sorry NIST)

NIST’s running a Lightweight Cryptography project in order to standardize symmetric encryption primitives that are lighter than the established NIST standards (read: AES and its modes of operations). NIST claims that “[because] the majority of current cryptographic algorithms were designed for desktop/server environments, many of these algorithms do not fit into constrained devices.” This is good motivation for the competition, however it’s factually incorrect: AES today fits in almost all IoT-ish chips and has even been used for bus and memory encryption.

But that’s not the point of this post—for more on that subject, come hear our talk at NIST’s Lightweight Cryptography Workshop in about 10 days, a talk derived from one of our previous posts, and based on a multitude of real examples. (See also this recent Twitter thread.)

Sorry NIST, this post is not about you, but about another standardization body: ISO, and specifically its ISO/IEC 29192 class of lightweight standards within the 35.030 category (“IT Security – including encryption”). This category includes no less than 9 standards relating to lightweight cryptography, which are (copying verbatim from the ISO page, links included):

ISO/IEC 29192-1:2012Information technology — Security techniques — Lightweight cryptography — Part 1: General90.93ISO/IEC JTC 1/SC 27
ISO/IEC 29192-2IT security techniques — Lightweight cryptography — Part 2: Block ciphers60.00ISO/IEC JTC 1/SC 27
ISO/IEC 29192-2:2012Information technology — Security techniques — Lightweight cryptography — Part 2: Block ciphers90.92ISO/IEC JTC 1/SC 27
ISO/IEC 29192-3:2012Information technology — Security techniques — Lightweight cryptography — Part 3: Stream ciphers90.93ISO/IEC JTC 1/SC 27
ISO/IEC 29192-4:2013Information technology — Security techniques — Lightweight cryptography — Part 4: Mechanisms using asymmetric techniques90.93ISO/IEC JTC 1/SC 27
ISO/IEC 29192-4:2013/AMD 1:2016Information technology — Security techniques — Lightweight cryptography — Part 4: Mechanisms using asymmetric techniques — Amendment 160.60ISO/IEC JTC 1/SC 27
ISO/IEC 29192-5:2016Information technology — Security techniques — Lightweight cryptography — Part 5: Hash-functions60.60ISO/IEC JTC 1/SC 27
ISO/IEC 29192-6:2019Information technology — Lightweight cryptography — Part 6: Message authentication codes (MACs)60.60ISO/IEC JTC 1/SC 27
ISO/IEC 29192-7:2019Information security — Lightweight cryptography — Part 7: Broadcast authentication protocols60.60ISO/IEC JTC 1/SC 27

Granted, few people and industries care about ISO/IEC standards, and you probably don’t, neither do we really to be honest—the fee around $100 to access the ISO standard documents probably doesn’t help in making ISO algorithms more popular.

We nonetheless think that it would be worthwhile to have a list of lightweight symmetric algorithms (whatever your weight metric) that received the blessing of allegedly some competent cryptographers, and therefore that are presumably safe to use. We’ve therefore reviewed what ISO has to offer so that you don’t have to, and summarize the fruit of our research in the remainder of this post:

Block ciphers

ISO/IEC 29192-2:2012 (thus, from 2012) standardizes these two block ciphers (literally just the block ciphers, and not any mode, which are covered in another ISO standard [nothing surprising here: ECB, CBC, OFB, CFB, CTR]):

  • PRESENT, anagram and little sister of SERPENT, designed in 2007, and the least Google-friendly cipher ever. Then marketed as ultra-lightweight, PRESENT is a simple substitution-permutation network with 4-bit S-boxes, which is more hardware-friendly than it is software-friendly, but will perform well enough almost everywhere. It has 64-bit blocks and a key of 80 or 128 bits.
  • CLEFIA, also designed in 2007, from Sony, initially aimed for DRM applications, is a boring Feistel scheme with 128-bit blocks and a key of 128, 192, or 256 bits. CLEFIA isn’t really more lightweight than AES, and I guess Sony lobbied for its standardization.

Stream ciphers

ISO/IEC 29192-3:2012 standardizes these two stream ciphers (again, one bit-oriented and one byte-oriented):

  • Trivium, one of the winners of the eSTREAM project, the favorite cipher of the DEF CON conference, is a minimalistic, bit-oriented stream cipher that is a simple combination of shift registers. Trivium is arguably the lightweightest algorithm in this post.
  • Enocoro, whose existence I had completely forgotten until writing this post. Designed by the Japanese firm Hitachi, Enocoro was submitted to the CRYPTREC contest in 2010 (see this cryptanalysis evaluation), yet ended up not being selected. Enocoro is a byte-oriented feedback shift register with a conservative design. It supports 80- and 128-bit keys, and is most probably safe (and safer with 128-bit keys).

Hash functions

This time not two but three algorithms, as defined in ISO/IEC 29192-5:2016:

  • PHOTON, designed in 2011, combines the simplicity of the sponge construction and the security guarantees of the AES permutation (no, Joan Daemen is not a designer of PHOTON). The permutation is optimized for low-end platforms, so you can’t directly reuse AES code/silicon. PHOTON comes in multiple versions, depending on the security level you want (the higher the security, the bigger the state).
  • SPONGENT, also from 2011, is to PRESENT what PHOTON is to AES. Nuff said.
  • Lesamnta-LW is different. It’s not a sponge but has a SHA-like round function and targets 120-bit security with a single version. It’s also less light than the above two.

MACs

Of the three algorithms listed in ISO/IEC 29192-6:2019, I was only familiar with one Chaskey, which is essentially a 32-bit version of SipHash. The other two are

  • LightMAC, which is actually a MAC construction rather than strictly speaking an algorithm. And since I didn’t pay the 118 CHF to read the full document, I don’t really know what ISO standardized here (the mode itself? an instantiation with a specific block cipher? Help please.)
  • “Tsudik’s keymode”, apparently from this 1992 paper by Gene Tsudik, which discussed the secret-prefix and secret-suffix MACs and proposes the hybrid version, which may or may not be what this “keymode” is about. I’ve no idea why it ended up being standardized in 2019.

AEAD

Nothing here, ISO hasn’t standardized authenticated ciphers.

Summary

All these algorithms are okay, but their being ISO standards doesn’t say much and doesn’t mean that they’re necessarily superior to others, just that some people bothered submitting them and lobbying for their standardization.

Cryptography in industrial embedded systems: our experience of the needs and constraints

A common model is that industrial embedded systems (a.k.a. IoT, M2M, etc.) need small, fast, low-energy crypto primitives—requirements often summarized by the “lightweight” qualificative. For example, a premise of NIST’s Lightweight Cryptography standardization project is that AES is not lightweight enough, and more generally that “the majority of current cryptographic algorithms were designed for desktop/server environments, many of these algorithms do not fit into constrained devices”—note the implicit emphasis on size.

In this article we share some observations from our experience working with industrial embedded systems in various industries, on various platforms and using various network protocols. We notably challenge the truism that small devices need small crypto, and argue that finding a suitable primitive is usually the simplest task that engineers face when integrating cryptography in their products. This article reviews some of the other problems one has to deal with when deploying cryptography mechanism on “lightweight” platforms.

We’re of course fatally subject to selection bias, and don’t claim that our perspective should be taken as a reference or authoritative. We nonetheless hope to contribute to a better understanding of what are the “constrained devices” that NIST refers to, and more generally of “real-world” cryptography in the context of embedded systems.

Few details can be share, alas, about our experience. Let us only say that we’ve designed, integrated, implemented, or reviewed cryptographic components in systems used in automotive, banking, content protection, satellite communications, law enforcement technology, supply chain management, device tracking, or healthcare.

AES is lightweight enough

Most of the time. Ten years ago we worked on a low-cost RFID product that had to use something else that AES, partially for performance reasons. Today many RFID products include an AES engine, as specified for example in the norm ISO/IEC 29167-10.

Systems on chips and boards for industrial application often include AES hardware, and when they don’t a software implementation of AES comes at acceptable costs. For example, chips from the very popular STM32 family generally provide readily available AES in different modes of operations.

An example perhaps of a very low-cost device that uses a non-AES primitive would be the Multos Step/One, which is EMVCo-compliant. In this case, 3DES was chosen instead. ATM Encrypting-PIN-Pads frequently use 3DES. We believe that the continued use of 3DES has more to do with compatibility and cost of replacement than the prohibitive cost of running a wider block cipher.

Of course an algorithm more compact and faster than AES wouldn’t hurt, but the benefits would have to justify the integration costs.

Choosing primitives is a luxury

More than once we faced the following challenge: create a data protection mechanism given the cryptography primitives available on the devices, which could for example be AES-GCM and SHA-256 only. We may have to use AES-GCM and SHA-256 because they’re standards, because they’re efficiently implemented (for example through hardware accelerators), or for the sake of interoperability. Note that a platform may give you access to AES-GCM, but not to the AES core directly, so you can’t use it to implement (say) AES-SIV.

If you want to use another algorithm than the ones available, you have to justify that it’s worth the cost of implementing, integrating and testing the new primitive. AES-GCM is not perfect (risk of nonce reuse, etc.), but the risk it creates is usually negligible compared to other risks. The situation may be different with AES-ECB.

Statelessness

Not all platforms are stateful, or reliably stateful. This means that you can’t always persistently store a counter, seed, or other context-dependent on the device. The software/firmware on the platform may be updatable over-the-air, but not always. The keys stored on the device may not be modifiable after the personalization phase of the production cycle.

Randomness

The platform may not offer you a reliable pseudorandom generator, or it may only have some low-entropy non-cryptographic generator, anyway that can be a severe limitation, especially if you realize this after proudly completing an implementation of ECDSA.

There are well-known workarounds of course, such as deterministic ECDSA and EdDSA for ECC signatures, or AES-SIV for authenticated encryption (this robustness to weak/non-randomness is the main reason why we chose to make it the default cipher in our company’s product). But sometimes it can get trickier, when you really need some kind of randomness yet can’t fully trust the PRNG (it’s more fun when the platform is stateless).

It’s not only about (authenticated) encryption

When no established standard such as TLS is used—and sometimes even when it is—the security layer is typically implemented at the application layer between the transport and business logic. (Authenticated) encryption is a typical requirement, but seldom the only one: you may have to worry about replay attacks or have to “obfuscate” some metadata or header information, for example to protect anonymity.

In an ideal world, you ought to use a thoroughly-designed, provably-secure, peer-reviewed protocol. But 1) such a thing likely doesn’t exist, and 2) even when it does it would probably not be suitable to your use case, for example if the said protocol requires a trusted third party or three network round-trips.

Message size limitations

True story: “Our clear payload is N bytes; the protected payload must be N bytes too, and must be encrypted and authenticated.” That’s when you have to be creative. Such a situation can occur with protocols such as Bluetooth Low-Energy or WAN protocols such as LoRaWAN or Sigfox (where the uplink payloads are 12 bytes and downlink payloads 8 bytes).

Even when you can afford some overhead to send a nonce and a tag, this may come at prohibitive cost if we’re talking of millions of messages and a per-volume pricing model. In other contexts, additional payload size can increase the risk of packet loss.

Network unreliability

It’s not just about TCP being reliable (guaranteed, in-order packet delivery) and UDP being not. Protocols running on top of TCP can have their own reliability properties caused by the way they transmit messages. For example, MQTT (when running over TCP) guarantees message delivery, but not in-order.

Whatever protocol is used, devices may have no way to transmit nor receive messages for a certain period of time. For example, communicating with satellites in non-geostationary orbit, or devices that are out of range for periods of time, such as aircraft, ships or smart meters as a measuring driver passes by.

An excellent engineering question is to ask how one would reliably transmit data from Mars, particularly where that data should be processed as quickly as possible on receipt. If not Mars, then further away. At such great distances, what is instantaneous for us starts to take seconds or minutes of time. The answer is to resend on a broadcast channel repeatedly, usually as an illustrative example of UDP/broadcast protocols. In these cases, packets are expected to be lost and round-trips are impossible—there is no way to confirm receipt.

Such limitations often prevent the use of crypto protocols adding RTTs, or requiring even a moderate level of synchronization with other devices. Unreliable network becomes particularly fun when implementing key rotation or key distribution mechanisms.

When crypto is too big

Crypto can be too big (in code size, or RAM usage) for certain platforms; the main cases we’ve encountered are when public-key operations are impossible, or when a TLS implementation takes too much resources. Although there are good TLS implementations for constrained platforms (such as ARM’s mbedTLS, wolfSSL, or BearSSL), they may include a lot of code to support the TLS standards and operations such as parsing certificates. Even the size of a TLS-PSK stack can prohibitive—and not because of AES.

Sometimes public-key cryptography is even possible within the limited capacity of the device, but the limiting factor is the protocol. An example of such a problem can be found in BearSSL’s documentation. Quoting Thomas Pornin’s TLS 1.3 Status, when streaming ASN.1 certificates, the usual order is end-entity first, CAs later. In any given object, the public key follows the certificate. EdDSA combines the public key and data when signing. Thus, in order to validate a signature, the entire certificate must be buffered until the public key can be extracted.

Now while a highly constrained device may simply use PSK and avoid this problem entirely, it is also true that the device may be capable of Ed25519 signatures even without sufficient RAM to buffer large certificates. This problem arises entirely from the choice of PureEdDSA rather than HashEdDSA in TLS 1.3.

Untrusted infrastructure

More often than you might expect, the infrastructure we use should not be trusted. In the MQTT context, this means brokers. In other context this means wireless repeaters, conversion gateways between protocols such as communication via SMS and so on. In the context of currently proposed IoT standards, these nodes are often assumed trusted and capable of re-encrypting for each hop using TLS where possible, or some other point-to-point protocol.

We believe that the implicit trust in the infrastructure by having it handle keys invites a far greater risk than the challenges of underpowered devices.

Conclusions

Cryptography on constrained devices can pose many problems, but the speed and size of symmetric primitives (ciphers, hash functions) is rarely one, at least in our experience (YMMV).

We can’t ignore that economics and risk management play into cryptography. Standard NIST cryptography primitives and NSA Suites A & B, for example, were designed to provide the US Government with an assurance that data is protected for the lifetime of the relevant classified information—on the order of magnitude of 50 years. It took time for the community to gain confidence in AES, but it’s now widely and globally trusted—anyway, safe block ciphers are easy to design; even DES nor GOST have never really been broken.

Lightweight cryptography might be suitable where such expectations of long-term security do not hold, and would allow the use of a very “lightweight” component. An extreme example is that or memory encryption, or “scrambling”, where only a handful of high-frequency cycles can be allocated.

The open question is whether we can design algorithms to match this requirement, bearing in mind that we have no ability to predict future developments. Looking back at history, requirements are driven by applications on which the public research community has little view. As highlighted in this article, said requirements often involve various components and technologies, which make the engineering problem difficult to approach to outsiders.

Introducing PQGo, experimental post-quantum cryptography in Go

TL;DR: We published cgo wrappers for post-quantum crypto at https://github.com/Teserakt-io/PQGo.

Post-quantum cryptography is about public-key algorithms that wouldn’t be broken by a quantum computer—unlike RSA, Diffie-Hellman, and elliptic curve cryptography, which all rely on the hardness of problems that are hard with a classical computer but become easy for quantum algorithms. For more on this topic, we refer to our presentation at BSides Lisbon 2017.

Quantum computers that would break our crypto aren’t coming anytime soon, but as an insurance against a breakthrough in quantum engineering, NIST is running a public competition to standardize post-quantum crypto in the next five years. This project sparked greater interest from researchers and industry, who see the opportunities from the publicity and investments around the quantum computer threat—often blatantly exaggerated.

To respond to the demand from customers and as a research interest, we at Teserakt investigated the integration of post-quantum crypto in our products. Our products’ reference code is in Go, whereas implementations of post-quantum crypto are in C. We therefore wrote a Go package using cgo to call the C code, which we adapted from reference implementations of some NIST submissions.

Our package github.com/Teserakt-io/PQGo currently supports the signature scheme Dilithium and the KEMs Kyber and Round5. As explained in the README, this choice isn’t a general endorsement nor a recommendation, but is based on some of our functional and performance requirements.

We tried to simplify the API and to hide some of its quirks, such as the fact that the C signature verification function will sometimes write at the message pointer’s address more data than the message’s actual length. Our package includes benchmark routines, but remember that we took the reference implementations rather than the optimized implementation, so an algorithm’s measured performance may be far from its optimal performance.

Please let us know your feedback by reporting issues on GitHub, submitting PRs, or writing us! We’d be happy to integrate more algorithms, please let us know your requests.

WARNING: Experimental code, don’t use in production or for anything that matters. (We know from experience that such statements don’t stop people from using the code in production or in their blockchain, but don’t say we didn’t warn you.)