Paper 2024/1580 Original: eprint.iacr.org/2024/1580 ↗

Polynomial Time Cryptanalytic Extraction of Deep Neural Networks in the Hard-Label Setting (Extended Version)

Abstract

Deep neural networks (DNNs) are valuable assets, yet black-box access to them raises security concerns about parameter extraction by malicious adversaries. Recent work by Carlini et al. (Crypto’20) and Canales-Martínez et al. (Eurocrypt’24) drew a parallel between model extraction and block-cipher key recovery via chosen-plaintext attacks. Using tools from differential cryptanalysis, they showed that all weights and biases of black-box ReLU-based DNNs can be recovered with a polynomial number of queries and polynomial-time post-processing. However, their attacks assume access to the exact numerical values of the output logits, enabling the computation of derivatives. To overcome this limitation, Chen et al. (Asiacrypt’24) studied the more realistic hard-label setting in which the attacker observes only the final classification label (e.g., “dog” or “car”). They proposed an extraction method that uses a polynomial number of oracle queries but has exponential running time. Moreover, their algorithm applies only to a restricted family of architectures, handles only binary classifiers, and is demonstrated only on very small networks with at most four neurons across up to two hidden layers. In this paper, we introduce new techniques that, for the first time, achieve cryptanalytic extraction of DNN parameters in the hardest hard-label setting using both a polynomial number of queries and polynomial-time computation for a broad class of ReLU-based networks. We validate our approach on a DNN trained on CIFAR-10 with 832 neurons in four hidden layers and nearly one million parameters in total. We further present an end-to-end black-box implementation of our attack, which we evaluate on a smaller artificial network, and extend our methods to leaky-ReLU activations. Our results show that, for our scenarios, all weights of a ReLU-based DNN can be efficiently recovered by analyzing only the geometric shape of its decision boundaries.