Password hardening encryption (PHE) is an emerging primitive in recent years. It can resist offline attack brought by keyword guessing attack from server via adding a third party with crypto services joining the decryption process. This primitive enhances the password authentication protocol and adds encryption functionality. This paper presents an active attack from server in the first scheme that introduced this primitive. This attack combines the idea from a cutting-edge threat called algorithm substitution attack which is undetectable and makes the server capable of launching offline attack. This result shows that the original PHE scheme can not resist attacks from malicious server. Then this study tries to summarize the property that an algorithm substitution attack resistant scheme should have. After that this paper presents a PHE scheme that can resist such kind of attacks from malicious server with simulation results. Finally, this study concludes the result and gives some expectation for future systematic research on interactive protocols under algorithm substitution attack.

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.