3
$\begingroup$

The notion of misuse-resistant authenticated encryption (MRAE) was defined in the symmetric setting by Rogaway and Shrimpton, along with the SIV mode that achieves it. The idea being that modern authenticated encryption cipher modes require a unique nonce and fail more or less catastrophically if a nonce is reused. An MRAE cipher mode maintains a strong definition of security even in this case, although not semantic security.

If we look at digital signatures, then there are also unique values that must be used. This has been a classic vulnerability in ECDSA, e.g., in the Playstation 3 hack or the attacks on Android Bitcoin wallets. The Ed25519 signature scheme is deterministic to avoid these problems, replacing the random value with a hash/PRF over the secret key and the message. RFC 6979 proposes a deterministic variant of ECDSA that is along similar lines. Both seem close in spirit to the SIV construction: replacing a random/unique value with a psuedorandom one generated from the message and a secret key.

But what about asymmetric encryption? For RSA it is common to use either PKCS#1 v1.5 or OAEP padding. Both require random elements for security, and it seems to me that both would not achieve semantic security (IND-CPA) if these repeat as RSA is otherwise deterministic. But it is not clear to me to what extent security is lost in this case. While the deterministic authenticated encryption (DAE) that SIV ensures in this case is not appropriate for public key encryption, does RSA-OAEP achieve the notion of deterministic privacy described in Appendix B of http://web.cs.ucdavis.edu/~rogaway/papers/keywrap.pdf? If not, has anyone ever considered an SIV-like construction for RSA? On the face of it, it would seem you could do the same trick and replace the random seed value in OAEP with the output of a PRF calculated over the message and the private key (and potentially a random nonce too). Would this be secure?

Improve this question
$\endgroup$
1
  • $\begingroup$ I’m also not sure how this would apply to Diffie-Hellman based encryption schemes such as ECIES. On the one hand, if you repeat an ephemeral key then it should still be secure (so long as you don’t use the same key too many times). On the other hand, if random key generation is flawed then in the worst case an attacker may be able to predict the ephemeral private values and then all security is lost. It’s not clear how you could possible apply a deterministic SIV-like approach in this case. $\endgroup$
    – Neil Madden
    Commented Jan 26, 2018 at 18:40

2 Answers 2

Reset to default
2
$\begingroup$

There has been work on this. I recommend reading the paper Nonce-Based Cryptography: Retaining Security when Randomness Fails and the references therein. In particular, references [5,9,33] within refer to "hedged public-key encryption" which maintains security as long as the entropy of the message together with the randomness is high enough (you can't really hope for much more than that).

Improve this answer
$\endgroup$
2
$\begingroup$

Both require random elements for security, and it seems to me that both would not achieve semantic security (IND-CPA) if these repeat as RSA is otherwise deterministic.

Actually, that would be true of any potentially misuse resistant system. As long as you don't fold in fresh randomness, and as long as you don't update long term state during the encryption, then encrypting the same message a second time will result in the same ciphertext.

Doing an SIV-like trick wouldn't help; if you encrypt the same message with the same private key, the PRF would generate the same nonce, and everything becomes deterministic.

What the PRF would help you if there are weak nonces (for example, in ECDSA, if you use the same nonce twice for two different messages, you leak the private key). If there was a similar weakness in the public key encryption scheme, that would help.

On the other hand, I don't believe RSA-OAEP has such a weakness; hence the PRF idea doesn't make anything better

Improve this answer
$\endgroup$
2
  • $\begingroup$ Yes, that was poorly phrased on my part. Of course neither SIV nor anything else achieves IND-CPA if it is fully deterministic. But does RSA-OAEP achieve something similar to MRAE in the case a random value repeats? E.g., would it achieve the deterministic privacy notion from Appendix B of web.cs.ucdavis.edu/~rogaway/papers/keywrap.pdf ? $\endgroup$
    – Neil Madden
    Commented Jan 26, 2018 at 19:23
  • $\begingroup$ I've edited the question to refer to the notion deterministic privacy, as it was unclear what I was asking for. $\endgroup$
    – Neil Madden
    Commented Jan 26, 2018 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.