On Lightweightness

From CryptoLUX
Jump to: navigation, search

This page focuses on the complex meaning of lightweightness and the constraints it implies on a design. We also give the scope statement made by Saarinen and Engels[1] for a lightweight primitive intended to be used by the industry.


"Weighting" a Primitive

Since we talk about "lightweight" primitive, there must be a way to define the weight of an algorithm. Roughly, the weight of a primitive is the amount of ressources necessary in both time and space for it to run. This weight can be measured in two distinct contexts: in software and in hardware. Lightweightness in software does not imply lightweightness in hardware and vice-versa. Finally, a measure which is relevant in both contexts is the power consumption.

A much more thorough discussion on this topic can be found in Guo and Schaumont's The Technology Dependence of Lightweight Hash Implementation Cost[2] where issues linked with the comparison of implementation results are also studied.

Software Weight

In software, the time complexity of a primitive encompasses two ideas. First, the number of clock cycles necessary to treat one byte of data gives the speed of the algorithm. However, this data point is not sufficient: achieving a high speed at the cost of a high overhead (for instance because of a sophisticated key schedule) may not be acceptable in some use cases. Therefore latency, i.e. the number of clock cycles of overhead, is to be taken into account too.

The memory complexity is of course about the amount of RAM necessary to carry the computation. However, it also takes into account the space required to store the algorithm, for instance in a flash memory.

Hardware Weight

In hardware, the memory requirement corresponds to the number of logical gates necessary to implement the primitive. This quantity is measured using a unit called G(ate) E(quivalence): one GE corresponds to one NAND gate. The time efficiency is given using a throughput measured in bits per second at a given computation frequency (usually 100Hz) which corresponds to the amount of data processed in one second using the given clock frequency. Just like for software, the latency must also be taken into account. It corresponds to the time which must be taken e.g. to derive the subkeys before every sequence of use of the primitive.

However, the estimation of these quantities is rather complex. This task is usually devoted to proprietary software and different research teams may use different ones --- or may not be able to afford the same extensions as the others. This dependence makes it very difficult to compare the implementation results obtained by two different teams.

Power consumption

Lightweight devices only have a limited amount of energy at their disposal, for example because of the limitations of power transmission in RFID or because the device runs on a battery. Power consumption is thus another criteria. The device must have a low average power consumption (measured in Watts) as well as a reasonable peak power consumption (also measured in Watts).

Implementation-related Considerations

Regardless of the primitive considered, some elements must always be taken into account during the design process. A non-exhaustive description of such elements follows.

Hardware/Software trade-offs

As said before, lightweightness in software and hardware do not imply each one another. In fact, some design trade-offs exist between the two. For instance, the use of S-boxes can be very efficiently implemented in software using a look-up table --- provided that the S-box is not too large, hence the use of 4x4 S-boxes in most cases. However, they are not so easy to implement in hardware; that is why for instance the authors of Piccolo designed their S-box using a small Feistel Network. Conversely, bit-oriented permutations like the one used in PRESENT can be implemented in hardware using wires, i.e. virtually no cost. However, their use in software is rather tedious.

These properties make it hard to aim at both software and hardware lightweightness.

Simplifying Side-Channel Attack Resilience

In practice, one of the most realistic threat against devices using lightweight cryptography are the side-channel attacks. These can be thwarted using an appropriate masking scheme. Therefore, some designers take the likely masking of their primitive into consideration as early as possible during the design process. For instance, the designers of KLEIN explicitely took such considerations into account.

Scope Statement

Saarinen and Engels published in 2012 a description[1] of the constraints and goals a lightweight cryptographic primitive must address to be useful in the industry. Its conclusion in particular is nothing short of a scope statement:

We conclude with a set of design goals for a RFID or lightweight sensor network “Do-It-All-Cipher” (DIAC) for Internet of Things.

  • The primitive must be able to operate without significant modification as a single-pass tweakable authenticated encryption & decryption algorithm and as a cryptographically secure hash.
  • The padding and operation rules for various inputs, including IVs, Authenticated Associated Data (AAD) must be unambiguously defined. The data rate should be small to avoid message expansion.
  • Initialization vector (IV) does not have to be a nonce (secure in a repeated chosen-IV attack). The security level must be consistent with key and state size under all reasonable attack models.
  • Hardware implementation must be under 2000 GE, including state memory and both encryption and decryption functionality. Software implementation speed and size across all MCU and CPU platforms should also be a design consideration.
  • The primitive must have a latency of under 50 cycles and encryption/decryption throughput of more than 1 bit / cycle.
  • The power usage should be less than 1...10 µW/MHz average with peaks below 3μW and 30μW respectively. Thus, at 2MHz, peaks should be below 1.5 µW/MHz to 15 µW/MHz.

We hope to see proposals meeting not just a few of these goals but to simultaneously meet all of these criteria.


References

  1. 1.0 1.1 Saarinen, M. J. O., & Engels, D. W. (2012). A Do-It-All-Cipher for RFID: Design Requirements. IACR Cryptology ePrint Archive, 2012, 317. pdf at eprint.iacr.org
  2. Guo, X., & Schaumont, P. (2011, November). The Technology Dependence of Lightweight Hash Implementation Cost. In ECRYPT Workshop on Lightweight Cryptography 2011. pdf at ece.vt.edu