An algorithm substitution attack (ASA) can undermine the security of cryptographic primitives by subverting the original implementation. An ASA succeeds when it extracts secrets without being detected. To launch an ASA on signature schemes, existing studies often needed to collect signatures with successive indices to extract the signing key. However, collection with successive indices requires uninterrupted surveillance of the communication channel and a low transmission loss rate in practice. This hinders the practical implementation of current ASAs, thus causing users to misbelieve that the threat incurred by ASA is only theoretical and far from reality. In this study, we first classify a group of schemes called extractable signatures that achieve traditional security (unforgeability) by reductions ending with key extraction, thus demonstrating that there is a generic and practical approach for ASA with this class of signatures. Further, we present the implementation of ASAs in which only two signatures and no further requirements are needed for the extraction of widely used discrete log-based signatures such as DSA, Schnorr, and modified ElGamal signature schemes. Our attack presents a realistic threat to current signature applications, which can also be implemented in open and unstable environments such as vehicular ad hoc networks. Finally, we prove that the proposed ASA is undetectable against polynomial time detectors and physical timing analysis.

Searchable functionality is provided in many online services such as mail services or outsourced data storage. To protect users privacy, data in these services is usually stored after being encrypted using searchable encryption. This enables the data user to securely search encrypted data from a remote server without leaking data and query information. Public key encryption with keyword search is one of the research branches of searchable encryption; this provides privacy-preserving searchable functionality for applications such as encrypted email systems. However, it has an inherent vulnerability in that the information of a query may be leaked using a keyword guessing attack. Most of existing works aim to make the system resistant to offline keyword guessing, but this does not protect against online attacks on real world services. In this paper, we move a step forward to present a generic framework able to resist online keyword guessing attack using a server-assisted model. Specifically, we design a novel primitive C mirrored all-but-one lossy encryption, which can prevent a specific user from generating valid encryptions. This primitive can be seen as an access control on encryption ability. Combining searchable encryption technique with the new primitive makes online keyword guessing attack impossible for the specified user, even if the attack is launched online. We further give formal security analysis for the generic framework, and a concrete implementation with efficiency analysis to show that our design is practical.