Nonce-misuse resistance seems to have two standard notions:

  1. The stronger notion: this reveals nothing unless the exact same nonce is used to encrypt the exact same message twice. In this case, the only information that is revealed is that the same message was encrypted twice. This can be used to notice that a message is resent.

    • AES-GCM-SIV has known to have strong nonce-misuse resistance.
  2. The weaker notion uses some prefix of the message to achieve nonce-misuse resistance. Nonce misuse occurs if a nonce-key-message-prefix triple is reused. A crib-dragging can be used to reveal the rest of the messages - not the encryption key!

  • Is there any encryption scheme that has weak nonce-misuse resistance?
  • Is there any other encryption scheme that has strong nonce-misuse resistance other than SIV mode?

Note: The weak notion is not to be confused with another weak notion of nonce-misuse resistance which allows leakage of the length of the common prefix for two messages encrypted under the same key-nonce pair.

  • 1
    $\begingroup$ Idea for a weakly-secure scheme: PRF the preferred prefix of the message with $k_1$ (along with the given nonce), use the PRF result as a nonce for a standard AE scheme like AES-GCM, append both the PRF result as well as the AE tag to the ciphertext. Though I fear this is less efficient than you probably hoped for. $\endgroup$
    – SEJPM
    Commented Jul 26, 2020 at 14:52
  • $\begingroup$ Does the weaker notation mean the attack lead to key recovery ? $\endgroup$
    – hardyrama
    Commented Jul 27, 2020 at 7:34
  • 1
    $\begingroup$ @hardyrama Not necessarily. Crib-Dragging doesn't reveal the key. Not sure about the authentication key since no example. GCM, which doesn't have weak nonce-misuse resistance, cn lead to Even a single AES-GCM nonce reuse can be catastrophic. $\endgroup$
    – kelalaka
    Commented Jul 27, 2020 at 7:49
  • $\begingroup$ Couldn't you turn the weaker notion into the stronger notion, by using the prefix as the nonce? $\endgroup$ Commented Jul 28, 2020 at 11:34
  • 1
    $\begingroup$ @user253751 the strong use all of the messages, the weak use only the prefix to produce the nonce. To be strong one must process all of the message before the encryption in order to produce the nonce. If you consider this performance penalty for large files, you may want to go weaker one. $\endgroup$
    – kelalaka
    Commented Jul 28, 2020 at 11:40


Your Answer

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

Browse other questions tagged or ask your own question.