Biblio

The RSA PKCS\#1 v1.5 signature algorithm is the most widely used digital signature scheme in practice. Its two main strengths are its extreme simplicity, which makes it very easy to implement, and that verification of signatures is significantly faster than for DSA or ECDSA. Despite the huge practical importance of RSA PKCS\#1 v1.5 signatures, providing formal evidence for their security based on plausible cryptographic hardness assumptions has turned out to be very difficult. Therefore the most recent version of PKCS\#1 (RFC 8017) even recommends a replacement the more complex and less efficient scheme RSA-PSS, as it is provably secure and therefore considered more robust. The main obstacle is that RSA PKCS\#1 v1.5 signatures use a deterministic padding scheme, which makes standard proof techniques not applicable. We introduce a new technique that enables the first security proof for RSA-PKCS\#1 v1.5 signatures. We prove full existential unforgeability against adaptive chosen-message attacks (EUF-CMA) under the standard RSA assumption. Furthermore, we give a tight proof under the Phi-Hiding assumption. These proofs are in the random oracle model and the parameters deviate slightly from the standard use, because we require a larger output length of the hash function. However, we also show how RSA-PKCS\#1 v1.5 signatures can be instantiated in practice such that our security proofs apply. In order to draw a more complete picture of the precise security of RSA PKCS\#1 v1.5 signatures, we also give security proofs in the standard model, but with respect to weaker attacker models (key-only attacks) and based on known complexity assumptions. The main conclusion of our work is that from a provable security perspective RSA PKCS\#1 v1.5 can be safely used, if the output length of the hash function is chosen appropriately.

We consider the situation, where an adversary may learn the ephemeral values used by the prover within an identification protocol, aiming to get the secret keys of the user, or just to impersonate the prover subsequently. Unfortunately, most classical cryptographic identification protocols are exposed to such attacks, which might be quite realistic in case of software implementations. According to a recent proposal from SECIT-2017, we regard a scheme to be secure, if a malicious verifier, allowed to set the prover's ephemerals in the query stage, cannot impersonate the prover later on. We focus on the Okamoto Identification Scheme (IS), and show how to make it immune to the threats described above. Via reduction to the GDH Problem, we provide security guarantees in case of insufficient control over the unit executing Okamoto identification protocol (the standard Okamoto protocol is insecure in this situation).