Paper 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.

Note: This is the extended version of the EUROCRYPT 2024 BPA paper, "Polynomial-Time Cryptanalytic Extraction of Deep Neural Networks in the Hard-Label Setting," to appear in the Journal of Cryptology. Compared with the original version, the main additions are: i) A fully black-box, end-to-end implementation of the complete attack on an artificial 32--32--32--32--10 network. The extraction required $3.97\times10^7$ hard-label queries and 74 seconds of wall-clock computation on a 32-core machine, recovering all 96 hidden neurons and the output layer to approximately $10^{-14}$ relative parameter error. ii) An extension of the attack to settings in which the network architecture is unknown. iii) An extension of the attack to leaky-ReLU networks. iv) Techniques for handling persistent or nearly dead neurons, using cross-layer methods that avoid requiring such neurons to toggle directly and thereby bypass the potentially exponential cost of obtaining their dual points through direct sampling.