International Association
for Cryptologic Research

Delay-based Physically Unclonable Functions (PUFs) are a popular choice for “keyless” cryptography in low-power devices. However, they have been subjected to modeling attacks using Machine Learning (ML) approaches, leading to improved PUF designs that resist ML-based attacks. On the contrary, evolutionary search (ES) based modeling approaches have garnered little attention compared to their ML counterparts due to their limited success. In this work, we revisit the problem of modeling delaybased PUFs using ES algorithms and identify drawbacks in present state-of-the-art genetic algorithms (GA) when applied to PUFs. This leads to the design of a new ES-based algorithm called CalyPSO, inspired by Particle Swarm Optimization (PSO) techniques, which is fundamentally different from classic genetic algorithm design rationale. This allows CalyPSO to avoid the pitfalls of textbook GA and mount successful modeling attacks on a variety of delay-based PUFs, including k-XOR APUF variants. Empirically, we show attacks for the parameter choices of k as high as 20, for which there are no reported ML or ES-based attacks without exploiting additional information like reliability or power/timing side-channels. We further show that CalyPSO can invade PUF designs like interpose-PUFs (i-PUFs) and (previously unattacked) LP-PUFs, which attempt to enhance ML robustness by obfuscating the input challenge. Furthermore, we evolve CalyPSO to CalyPSO++ by observing that the PUF compositions do not alter the input challenge dimensions, allowing the attacker to investigate cross-architecture modeling. This allows us to model a k-XOR APUF using a (k − 1)-XOR APUF as well as perform cross-architectural modeling of BRPUF and i-PUF using k-XOR APUF variants. CalyPSO++ provides the first modeling attack on 4 LP-PUF by reducing it to a 4-XOR APUF. Finally, we demonstrate the potency of CalyPSO and CalyPSO++ by successfully modeling various PUF architectures on noisy simulations as well as real-world hardware implementations.

Microarchitectural attacks on computing systems often stem from simple artefacts in the underlying architecture. In this paper, we focus on the Return Address Stack (RAS), a small hardware stack present in modern processors to reduce the branch miss penalty by storing the return addresses of each function call. The RAS is useful to handle specifically the branch predictions for the RET instructions which are not accurately predicted by the typical branch prediction units. In particular, we envisage a spy process who crafts an overflow condition in the RAS by filling it with arbitrary return addresses, and wrestles with a concurrent process to establish a timing side channel between them. We call this attack principle, RASSLE 1 (Return Address Stack based Side-channel Leakage), which an adversary can launch on modern processors by first reverse engineering the RAS using a generic methodology exploiting the established timing channel. Subsequently, we show three concrete attack scenarios: i) How a spy can establish a covert channel with another co-residing process? ii) How RASSLE can be utilized to determine the secret key of the P-384 curves in OpenSSL (v1.1.1 library)? iii) How an Elliptic Curve Digital Signature Algorithm (ECDSA) secret key on P-256 curve of OpenSSL can be revealed using Lattice Attack on partially leaked nonces with the aid of RASSLE? In this attack, we show that the OpenSSL implementation of scalar multiplication on this curve has varying number of add-and-sub function calls, which depends on the secret scalar bits. We demonstrate through several experiments that the number of add-and-sub function calls can be used to template the secret bit, which can be picked up by the spy using the principles of RASSLE. Finally, we demonstrate a full end-to-end attack on OpenSSL ECDSA using curve parameters of curve P-256. In this part of our experiments with RASSLE, we abuse the deadline scheduler policy to attain perfect synchronization between the spy and victim, without any aid of induced synchronization from the victim code. This synchronization and timing leakage through RASSLE is sufficient to retrieve the Most Significant Bits (MSB) of the ephemeral nonces used while signature generation, from which we subsequently retrieve the secret signing key of the sender applying the Hidden Number Problem. 1RASSLE is a non-standard spelling for wrestle.