Skip to main content
main-content

Über dieses Buch

The two-volume set LNCS 12726 + 12727 constitutes the proceedings of the 19th International Conference on Applied Cryptography and Network Security, ACNS 2021, which took place virtually during June 21-24, 2021.

The 37 full papers presented in the proceedings were carefully reviewed and selected from a total of 186 submissions. They were organized in topical sections as follows:

Part I: Cryptographic protocols; secure and fair protocols; cryptocurrency and smart contracts; digital signatures; embedded system security; lattice cryptography;

Part II: Analysis of applied systems; secure computations; cryptanalysis; system security; and cryptography and its applications.

Inhaltsverzeichnis

Frontmatter

Analysis of Applied Systems

Frontmatter

Breaking and Fixing Third-Party Payment Service for Mobile Apps

Abstract
Riding on the widespread user adoption of mobile payment, a growing number of mobile apps have integrated the service from third-party payment service providers or so-called Cashiers. Despite its prevalence and critical nature, no existing standard can guide the secure deployment of mobile payment. Thus, the protocol designs and implementations from different Cashiers are diverse. Given the complicated multi-party interactions in mobile payment, either the Cashiers or the apps may not fully consider various threat models, which enlarges the attack surface and causes the exploits with severe consequences, ranging from financial loss to privacy violations. In this paper, we perform an in-depth security analysis of real-world third-party payment services for mobile apps. Specifically, we examine the mobile payment systems from five top-tier Cashiers that serve over one billion users globally. Leveraging insecure protocol designs and practical implementation flaws, e.g., vulnerable backend SDKs for mobile apps, we have discovered six types of exploits. These exploits enable the attacker to violate user privacy and shop for free in the victim apps, affecting millions of users. Finally, we propose the fixings to defend against these exploits. We have shared our findings with the affected Cashiers and got their positive responses.
Shangcheng Shi, Xianbo Wang, Wing Cheong Lau

DSS: Discrepancy-Aware Seed Selection Method for ICS Protocol Fuzzing

Abstract
Industrial Control System (ICS), as the core of the critical infrastructure, its vulnerabilities threaten physical world security. Mutation-based black-box fuzzing is a popular method for vulnerability discovery in ICS, and the diversification of seeds is crucial to its performance. However, the ICS devices are dedicated devices whose programs are challenging to get, protocols are unknown, and execution traces are hard to obtain in real-time. These restrictions impede seed selection, thereby reducing the efficiency of fuzzing. Therefore, it has become our primary goal to select a high-quality seed set containing as few seeds as possible with extensive triggered traces.
In this paper, we present a novel automatic seed selection method called DSS, selecting high-quality seeds for improving fuzzing efficiency. The method is based on the observation that dissimilar response messages are generated by different device execution processes in most cases, which helps us build the connection of messages discrepancy and execution traces discrepancy to guide DSS. Expressly, we point out that dissimilar messages are effective indicators of different execution paths. Therefore, choosing ICS messages with high discrepancy as seeds can bring more initial execution traces and fewer seeds with the same semantic, which are essential to black-box fuzzing. Our experiments show that the quantity of seeds selected by DSS is significantly less than the traditional method when achieving the same trace coverage.
Shuangpeng Bai, Hui Wen, Dongliang Fang, Yue Sun, Puzhuo Liu, Limin Sun

Threat for the Secure Remote Password Protocol and a Leak in Apple’s Cryptographic Library

Abstract
The Secure Remote Password protocol is a password-based authenticated key-exchange between two parties. One advantage is to prevent offline dictionary attacks from an adversary eavesdropping the communication. We present how such an attack is feasible if the modular exponentiation at the heart of the protocol is vulnerable and leaks some data related to the password.
In the case of a fixed exponent, adding randomness during the execution is a classical protection mechanism, and such a mechanism is present in Apple’s cryptographic library to randomize the exponent. Despite being intended to protect against complex side-channel attacks, we show that its usage makes the implementation vulnerable to simple side-channels such as power analysis.
This leakage observed in the library is mild but is useful for the attack we propose on the Secure Remote Password protocol.
Andy Russon

Secure Computations

Frontmatter

Privacy-Preserving Data Aggregation with Probabilistic Range Validation

Abstract
Privacy-preserving data aggregation protocols have been researched widely, but usually cannot guarantee correctness of the aggregate if users are malicious. These protocols can be extended with zero-knowledge proofs and commitments to work in the malicious model, but this incurs a significant computational cost on the end users, making adoption of these protocols less likely.
We propose a privacy-preserving data aggregation protocol for calculating the sum of user inputs. Our protocol gives the aggregator confidence that all inputs are within a desired range. Instead of zero-knowledge proofs, our protocol relies on a probabilistic hypergraph-based detection algorithm with which the aggregator can quickly pinpoint malicious users. Furthermore, our protocol is robust to user dropouts and, apart from the setup phase, it is non-interactive.
F. W. Dekker, Zekeriya Erkin

LLVM-Based Circuit Compilation for Practical Secure Computation

Abstract
Multi-party computation (MPC) allows two or more parties to jointly and securely compute functions over private inputs. Cryptographic protocols that realize MPC require functions to be expressed as Boolean or arithmetic circuits. Deriving such circuits is either done manually, or with hardware synthesis tools and specialized MPC compilers. Unfortunately, such existing tools compile only from a single front-end language and neglect decades of research for optimizing regular compilers.
In this paper, we make MPC practical for developers by automating circuit compilation based on the compiler toolchain LLVM. For this, we develop an LLVM optimizer suite consisting of multiple transform passes that operate on the LLVM intermediate representation (IR) and gradually lower functions to circuit level. Our approach supports various front-end languages (currently C, C++, and Fortran) and takes advantage of powerful source code optimizations built into LLVM. We furthermore make sure to produce circuits that are optimized for MPC, and even offer fully automated post-processing for efficient post-quantum MPC.
We empirically measure the quality of our compilation results and compare them to the state-of-the-art specialized MPC compiler HyCC (Büscher et al. CCS’2018). For all benchmarked HyCC example applications (e.g., biomatch and linear equation solving), our highly generalizable approach achieves similar quality in terms of gate count and composition.
Tim Heldmann, Thomas Schneider, Oleksandr Tkachenko, Christian Weinert, Hossein Yalame

An Efficient Passive-to-Active Compiler for Honest-Majority MPC over Rings

Abstract
Multiparty computation (MPC) over rings such as \(\mathbb {Z}_{2^{32}}\) or \(\mathbb {Z}_{2^{64}}\) has received a great deal of attention recently due to its ease of implementation and attractive performance. Several actively secure protocols over these rings have been implemented, for both the dishonest majority setting and the setting of three parties with one corruption. However, in the honest majority setting, no concretely efficient protocol for arithmetic computation over rings has yet been proposed that allows for an arbitrary number of parties.
We present a novel compiler for MPC over the ring \(\mathbb {Z}_{2^{k}}\) in the honest majority setting that turns a semi-honest protocol into an actively secure protocol with very little overhead. The communication cost per multiplication is only twice that of the semi-honest protocol, making the resultant actively secure protocol almost as fast.
To demonstrate the efficiency of our compiler, we implement both an optimized 3-party variant (based on replicated secret-sharing), as well as a protocol for n parties (based on a recent protocol from TCC 2019). For the 3-party variant, we obtain a protocol which outperforms the previous state of the art that we can experimentally compare against. Our n-party variant is the first implementation for this particular setting, and we show that it performs comparably to the current state of the art over fields.
Mark Abspoel, Anders Dalskov, Daniel Escudero, Ariel Nof

Cryptanalysis

Frontmatter

Experimental Review of the IKK Query Recovery Attack: Assumptions, Recovery Rate and Improvements

Abstract
In light of more data than ever being stored using cloud services and the request by the public for secure, privacy-enhanced, and easy-to-use systems, Searchable Encryption schemes were introduced. These schemes enable privacy-enhanced search among encrypted documents yet disclose (encrypted) queries and responses. The first query recovery attack, the IKK attack, uses the disclosed information to (partly) recover what plaintext words the client searched for. This can also leak information on the plaintext contents of the encrypted documents. Under specific assumptions, the IKK attack has been shown to potentially cause serious harm to the security of Searchable Encryption schemes.
We empirically review the IKK query recovery attack to improve the understanding of its feasibility and potential security damage. In order to do so, we vary the assumed query distribution, which is shown to have a severe (negative) impact on the accuracy of the attack, and the input parameters of the IKK attack to find a correlation between these parameters and the accuracy of the IKK attack. Furthermore, we show that the recovery rate of the attack can be increased up to 10% points, while decreasing the variance of the recovery rate up to 78% points by combining the results of multiple attack runs. We also show that the including deterministic components in the probabilistic IKK attack can increase the recovery rate up to 21% points and decrease its variance up to 57% points.
Ruben Groot Roessink, Andreas Peter, Florian Hahn

Efficient Methods to Search for Best Differential Characteristics on SKINNY

Abstract
Evaluating resistance of ciphers against differential cryptanalysis is essential to define the number of rounds of new designs and to mount attacks derived from differential cryptanalysis.
In this paper, we propose automatic tools to find the best differential characteristics on the SKINNY block cipher. As usually done in the literature, we split this search in two stages denoted by Step 1 and Step 2. In Step 1, we aim at finding all truncated differential characteristics with a low enough number of active Sboxes. Then, in Step 2, we try to instantiate each difference value while maximizing the overall differential characteristic probability. We solve Step 1 using an ad-hoc method inspired from the work of Fouque et al. whereas Step 2 is modelized for the Choco-solver library as it seems to outperform all previous methods on this stage.
Notably, for SKINNY-128 in the SK model and for 13 rounds, we retrieve the results of Abdelkhalek et al. within a few seconds (to compare with 16 days) and we provide, for the first time, the best differential related-tweakey characteristics up to 14 rounds for the TK1 model. Regarding the TK2 and the TK3 models, we were not able to test all the solutions Step 1, and thus the differential characteristics we found up to 16 and 17 rounds are not necessarily optimal.
Stéphanie Delaune, Patrick Derbez, Paul Huynh, Marine Minier, Victor Mollimard, Charles Prud’homme

Towards Efficient LPN-Based Symmetric Encryption

Abstract
Due to the rapidly growing number of devices that need to communicate securely, there is still significant interest in the development of efficient encryption schemes. It is important to maintain a portfolio of different constructions in order to enable a quick transition if a novel attack breaks a construction currently in use. A promising approach is to construct encryption schemes based on the learning parity with noise (LPN) problem as these schemes can typically be implemented fairly efficiently using mainly “exclusive or” (XOR) operations. Most LPN-based schemes in the literature are asymmetric, and there is no practical evaluation of any LPN-based symmetric encryption scheme.
In this paper, we propose a novel LPN-based symmetric encryption scheme that is more efficient than related schemes. Apart from analyzing our scheme theoretically, we provide the first practical evaluation of a symmetric LPN-based scheme, including a study of its performance in terms of attainable throughput depending on the selected parameters. As the encryption scheme lends itself to an implementation in hardware, we further evaluate it on a low-end SoC FPGA. The measurement results attest that our encryption scheme achieves high performance rates in terms of throughput on such hardware, providing evidence that symmetric encryption schemes based on hard learning problems may be constructed that can compete with state-of-the-art encryption schemes.
Sonia Bogos, Dario Korolija, Thomas Locher, Serge Vaudenay

System Security

Frontmatter

Open Access

A Differentially Private Hybrid Approach to Traffic Monitoring

Abstract
In recent years, privacy research has been gaining ground in vehicular communication technologies. Collecting data from connected vehicles presents a range of opportunities for industry and government to perform data analytics. Although many researchers have explored some privacy solutions for vehicular communications, the conditions to deploy them are still maturing, especially when it comes to privacy for sensitive data aggregation analysis. In this work, we propose a hybrid solution combining the original differential privacy framework with an instance-based additive noise technique. The results show that for typical instances we obtain a significant reduction in outliers. As far as we know, our paper is the first detailed experimental evaluation of differentially private techniques applied to traffic monitoring. The validation of the proposed solution was performed through extensive simulations in typical traffic scenarios using real data.
Rogério V. M. Rocha, Pedro P. Libório, Harsh Kupwade Patil, Diego F. Aranha

Proactive Detection of Phishing Kit Traffic

Abstract
Current anti-phishing studies mainly focus on either detecting phishing pages or on identifying phishing emails sent to victims. In this paper, we propose instead to detect live attacks through the messages sent by the phishing site back to the attacker. Most phishing attacks exfiltrate the information gathered from the victim by sending an email to a “drop”, throwaway email address. We call these messages exfiltrating emails. Detecting and blocking exfiltrating emails is a new tool to protect networks in which a number of largely unmonitored websites are hosted (universities, web hosting companies etc.) and where phishing sites may be created, either directly or by compromising existing legitimate sites. Moreover, unlike most traditional antiphishing techniques which require a delay between the attack and its detection, this method is able to block the attack as soon as it starts collecting data.
It is also useful for email providers who can detect the presence of drop mailbox in their service and prevent access to it. Gmail deployed a simple rule-based detection system and detected over 12 million exfiltrating emails sent to more than 19,000 drop Gmail addresses in one year [52].
In this work, we look at this problem from a new perspective: we use a Recurrent Neural Network to learn the structure of exfiltrating emails instead of their content. We compare our implementation, called DeepPK, against word-based and pattern-based methods, and tested their robustness against evasion techniques. Although all three models are shown to be very effective at detecting unmodified messages, DeepPK is the overall more resistant and remains quite effective even when the messages are altered to avoid detection. With DeepPK, we also introduce a new message encoding technique which facilitates scaling of the classifier and makes detection evasion harder.
Qian Cui, Guy-Vincent Jourdan, Gregor V. Bochmann, Iosif-Viorel Onut

Vestige: Identifying Binary Code Provenance for Vulnerability Detection

Abstract
Identifying the compilation provenance of a binary code helps to pinpoint the specific compilation tools and configurations that were used to produce the executable. Unfortunately, existing techniques are not able to accurately differentiate among closely related executables, especially those generated with minor different compiling configurations. To address this problem, we have designed a new provenance identification system, Vestige. We build a new representation of the binary code, i.e., attributed function call graph (AFCG), that covers three types of features: idiom features at the instruction level, graphlet features at the function level, and function call graph at the binary level. Vestige applies a graph neural network model on the AFCG and generates representative embeddings for provenance identification. The experiment shows that Vestige achieves 96% accuracy on the publicly available datasets of more than 6,000 binaries, which is significantly better than previous works. When applied for binary code vulnerability detection, Vestige can help to improve the top-1 hit rate of three recent code vulnerability detection methods by up to 27%.
Yuede Ji, Lei Cui, H. Howie Huang

SoK: Auditability and Accountability in Distributed Payment Systems

Abstract
Enforcement of policy regulations and availability of auditing mechanisms are crucial building blocks for the adoption of distributed payment systems. In this work we review a number of existing proposals for distributed payment systems that offer some form of auditability for regulators. We identify two major distinct lines of work: payment systems that are not privacy-preserving such as Bitcoin, where regulation functionalities are typically tailored for organizations controlling many accounts, and privacy-preserving payment systems where regulation functionalities are typically targeted to user level. We provide a systematization methodology over several axes of characteristics and performance, while highlighting insights and research gaps that we have identified, such as lack of dispute-resolution solutions between the regulator and the entity under audit, and the incompatibility of ledger pruning or off-chain protocols with regulatory requirements. Based on our findings, we propose a number of exciting future research directions.
Panagiotis Chatzigiannis, Foteini Baldimtsi, Konstantinos Chalkias

Defending Web Servers Against Flash Crowd Attacks

Abstract
A flash crowd attack (FCA) floods a service, such as a Web server, with well-formed requests, generated by numerous bots. FCA traffic is difficult to filter, since individual attack and legitimate service requests look identical. We propose robust and reliable models of human interaction with server, which can identify and block a wide variety of bots. We implement the models in a system called FRADE, and evaluate them on three Web servers with different server applications and content. Our results show that FRADE detects both naive and sophisticated bots within seconds, and successfully filters out attack traffic. FRADE significantly raises the bar for a successful attack, by forcing attackers to deploy at least three orders of magnitude larger botnets than today.
Rajat Tandon, Abhinav Palia, Jaydeep Ramani, Brandon Paulsen, Genevieve Bartlett, Jelena Mirkovic

Cryptography and Its Applications

Frontmatter

TurboIKOS: Improved Non-interactive Zero Knowledge and Post-quantum Signatures

Abstract
In this work, we present a zero knowledge argument for general arithmetic circuits that is public-coin and constant rounds, so it can be made non-interactive and publicly verifiable with the Fiat-Shamir heuristic. The construction is based on the MPC-in-the-head paradigm, in which the prover jointly emulates all MPC protocol participants and can provide advice in the form of Beaver triples whose accuracy must be checked by the verifier. Our construction follows the Beaver triple sacrificing approach used by Baum and Nof [PKC 2020]. Our improvements reduce the communication per multiplication gate from 4 to 2 field elements, matching the performance of the cut-and-choose approach taken by Katz, Kolesnikov, and Wang [CCS 2018] and with lower additive overhead for some parameter settings. We implement our protocol and analyze its cost on Picnic-style post-quantum digital signatures based on the AES family of circuits.
Yaron Gvili, Julie Ha, Sarah Scheffler, Mayank Varia, Ziling Yang, Xinyuan Zhang

Cryptanalysis of the Binary Permuted Kernel Problem

Abstract
In 1989, Shamir presented an efficient identification scheme (IDS) based on the permuted kernel problem (PKP). After 21 years, PKP was generalized by Lampe and Patarin, who were able to build an IDS similar to Shamir’s one, but using the binary field. This binary variant presented some interesting advantages over Shamir’s original IDS, such as reduced number of operations and inherently resistance against side-channel attacks. In the security analysis, considering the best attacks against the original PKP, the authors concluded that none of these existing attacks appeared to have a significant advantage when attacking the binary variant. In this paper, we propose the first attack that targets the binary PKP. The attack is analyzed in detail, and its practical performance is compared with our theoretical models. For the proposed parameters originally targeting 79 and 98 bits of security, our attack can recover about 100% of all keys using less than \(2^{63}\) and \(2^{77}\) operations, respectively.
Thales Bandiera Paiva, Routo Terada

Security Comparisons and Performance Analyses of Post-quantum Signature Algorithms

Abstract
Quantum computing challenges the computational hardness assumptions anchoring the security of public-key ciphers, such as the prime factorization and the discrete logarithm problem. To prepare for the quantum era and withstand the attacks equipped with quantum computing, the security and cryptography communities are designing new quantum-resistant public-key ciphers. National Institute of Standards and Technology (NIST) is collecting and standardizing the post-quantum ciphers, similarly to its past involvements in establishing DES and AES as symmetric cipher standards. The NIST finalist algorithms for public-key signatures are Dilithium, Falcon, and Rainbow. Finding common ground to compare these algorithms can be difficult because of their design, the underlying computational hardness assumptions (lattice based vs. multivariate based), and the different metrics used for security strength analyses in the previous research (qubits vs. quantum gates). We overcome such challenges and compare the security and the performances of the finalist post-quantum ciphers of Dilithium, Falcon, and Rainbow. For security comparison analyses, we advance the prior literature by using the depth-width cost for quantum circuits (DW cost) to measure the security strengths and by analyzing the security in Universal Quantum Gate Model and with Quantum Annealing. For performance analyses, we compare the algorithms’ computational loads in the execution time as well as the communication costs and implementation overheads when integrated with Transport Layer Security (TLS) and Transmission Control Protocol (TCP)/Internet Protocol (IP). Our work presents a security comparison and performance analysis as well as the trade-off analysis to inform the post-quantum cipher design and standardization to protect computing and networking in the post-quantum era.
Manohar Raavi, Simeon Wuthier, Pranav Chandramouli, Yaroslav Balytskyi, Xiaobo Zhou, Sang-Yoon Chang

Tighter Proofs for the SIGMA and TLS 1.3 Key Exchange Protocols

Abstract
We give new, fully-quantitative and concrete bounds that justify the SIGMA and TLS 1.3 key exchange protocols not just in principle, but in practice. By this we mean that, for standardized elliptic curve group sizes, the overall protocol actually achieves the intended security level.
Prior work gave reductions of both protocols’ security to the underlying building blocks that were loose (in the number of users and/or sessions), so loose that they gave no guarantees for practical parameters. Adapting techniques by Cohn-Gordon et al. (Crypto 2019), we give reductions for SIGMA and TLS 1.3 to the strong Diffie–Hellman problem which are tight, and prove that this problem is as hard as solving discrete logarithms in the generic group model. Leveraging our tighter bounds, we meet the protocols’ targeted security levels when instantiated with standardized curves and improve over prior bounds by up to over 90 bits of security across a range of real-world parameters.
Hannah Davis, Felix Günther

Improved Structured Encryption for SQL Databases via Hybrid Indexing

Abstract
We introduce a new technique for indexing joins in encrypted SQL databases called partially precomputed joins which achieves lower leakage and bandwidth than those used in prior constructions. These techniques are incorporated into state-of-the-art structured encryption schemes for SQL data, yielding a hybrid indexing scheme with both partially and fully precomputed join indexes. We then introduce the idea of leakage-aware query planning by giving a heuristic that helps the client decide, at query time, which index to use so as to minimize leakage and stay below a given bandwidth budget. We conclude by simulating our constructions on real datasets, showing that our heuristic is accurate and that partially-precomputed joins perform well in practice.
David Cash, Ruth Ng, Adam Rivkin

Backmatter

Weitere Informationen

Premium Partner