Design (high-level ideas)

Spook is exploiting various design ideas in order to ensure low-energy side-channel security (primary implementation target) and low-energy unprotected implementations (secondary implementation target), while also ensuring strong black box security guarantees.

Energy is our main performance metric given its increasing importance with battery-operated devices possibly exploiting energy harvesting. Side-channel security is also a central design goal since IoT applications generally enable an increased physical access to the devices by adversaries.

Low-energy side-channel security

The primary target of the Spook design is side-channel security at low energy cost. This goal is ensured by the following high-level ideas:

• Leveled implementations. Spook is amenable to leveled implementations: two tweakable block ciphers (depicted by the gray boxes in the figure above) need a strong and energy demanding level of protection against side-channel attacks but are only used twice per message, independently of the message length, and the bulk of the computation is performed by a permutation (depicted by the regular boxes) whose implementation only requires basic and energy efficient protection. This strategy leads to considerable energy gains when high security against side-channel attacks is required. This gain directly materializes in a reduced cycle count in case of software implementations, or when the overheads of hardware side-channel protections are mostly in clock cycles. It is only visible in the energy per bit metric in case the overheads of hardware side-channel protections are mostly in area. We note that, when considering leveled implementations, the reliance on two primitives (a TBC and a permutation) is of limited inconvenience since the strongly protected and weakly protected parts of the design would be implemented separately even in case of identical primitives.

• Strong integrity guarantees in the presence of leakage in encryption and decryption. Spook guarantees the integrity of its ciphertexts as long as the long-term key manipulated by its tweakable block cipher remains protected: all its ephemeral secrets processed by the permutation can be leaked in full, during encryption and during decryption, without losing integrity guarantees. Security against decryption leakage is obtained by decrypting Z with the final TBC, rather than recomputing it: this guarantees that the correct authentication tag is never computed when attempting the decryption of an invalid ciphertext. Our security proof shows that the integrity of Spook in the presence of leakage reduces to the security of its tweakable block ciphers against Differential Power Analysis (DPA). If DPA attacks against the authentication tag are not a practical concern, then Spook can also be implemented in an inverse-free manner, that is, by recomputing Z during decryption.

• Strong confidentiality guarantees in the presence of leakage in encryption. Spook takes advantage of the nonce and of its initial TBC to derive a fresh state, which is refreshed again for each message block using a duplex sponge strategy. This constantly refreshed state supports the confidentiality of plaintexts with encryption leakage, by removing the possibility of recovering the internal state of the system through DPA. Given the security of the long-term key (as for integrity guarantees with leakage), our security proof informally shows that the confidentiality of the messages encrypted with Spook in the presence of leakage reduces to the Simple Power Analysis (SPA) security of one iteration of its permutation. We note that confidentiality in the presence of decryption leakage is possible but would require a two-pass decryption process, which would be too demanding for many lightweight applications.

• Primitives that are efficient to mask. The tweakable block cipher used in Spook is a (bitslice) LS-design with low multiplicative complexity and low multiplicative depth, which generally allows efficient masked implementations. The permutation is based on similar components, aimed to enable low latency / low energy implementation. The use of a TBC as initial and final primitive (rather than a permutation) is also expected to be slightly more efficient from the energy viewpoint, since it benefits from a smaller state size.

• Possibility to precompute and amortize costs. The ephemeral key (B on the figure) can be precomputed, halving the online overheads of the side-channel protections of Spook in encryption. Large messages, or multiple messages of a single conversation, can also be processed segment by segment and only require a single TBC call per extra segment.

A general motivation for these advanced physical security features can be found next:

• F.-X. Standaert, Towards and Open Approach to Secure Cryptographic Implementations (Invited Talk), in the proceedings of Eurocrypt 2019, Lecture Notes in Computer Science, vol 11478, pp xv, Darmstadt, Germany, May 2018, Springer (slides, IACR youtube link).

Note that one important aspect of our security claims is that we consider security definitions that allow every computation (including the computation of the “challenge ciphertext”) to leak, a requirement that we call leakage-resistance. This is in contrast with common leakage-resilience definitions excluding the leakage of the challenge ciphertexts.

Low-energy unprotected implementations

Besides its features for strong security against side-channel attacks, Spook is a flexible design also offering good implementation properties in general:

• Efficient bitslice structure. Being based on the LS-design strategy, Spook is expected to lead to efficient implementation on a wide-range of software platforms (especially those for which the manipulation of 32-bit operands is easy). It is also expected to be efficient in hardware, due to the limited gate count and gate depth of its underlying primitives.

• Inverse-free version. If security against side-channel analysis is not required by the intended case study, Spook can be implemented in an inverse-free manner (as previously mentioned). Indeed, the decryption-based tag verification of Spook is only needed to obtain strong integrity guarantees in the presence of leakage.

• Variable tag lengths (of the inverse-free version). In a similar context, it is also possible to truncate the tags of Spook, enabling a standard tradeoff between integrity guarantees and performance.

• Similar primitives. Despite being based on two different primitives (i.e., a tweakable block cipher and a permutation), these primitives are using the similar underlying components (e.g., S-boxes, diffusion layers) in order to facilitate resources sharing, especially in hardware implementations.

• Single running primitive. The execution of Spook only uses its tweakable block cipher for initialization/finalization. This is what allows the reduced energy reductions in the presence of strong side-channel countermeasures for the tweakable block cipher. But even in the context of unprotected implementations, it implies that one primitive can always be switched off, enabling a low energy per bit. So the overheads due to this pair of primitives is only a slighlty increased area (in hardware) or code size (in software), and should not appear for our main target metric, the energy per bit.

• Possibility to precompute. (Same as when considering side-channel countermeasures).

Black box security

• Misuse-resilience. Spook is misuse-resilient: it guarantees that nonce misuse does not have an impact on the security of the messages encrypted with a fresh nonce. It is not misuse-resistant since it would require a two-pass encryption scheme, which we deemed too expensive for a lightweight algorithm.

• Beyond-birthday security with respect to the tweakable block cipher size. Spook leverages its initialization phase in order to achieve tight security bounds with respect to the size of its tweakable block cipher.

• Multi-user security with public tweak. Since dedicated to use in IoT applications where billions of devices are expected to be deployed, Spook was also designed to ensure multi-user security. For this purpose, it only uses a public tweak (P on the figure).