2
$\begingroup$

In the context of the NIST PQC standardization process, NIST has defined the following five security categories:

  1. Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for key search on a block cipher with a 128-bit key (e.g. AES128)
  2. Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for collision search on a 256-bit hash function (e.g. SHA256/ SHA3-256)
  3. Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for key search on a block cipher with a 192-bit key (e.g. AES192)
  4. Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for collision search on a 384-bit hash function (e.g. SHA384/ SHA3-384)
  5. Any attack that breaks the relevant security definition must require computational resources comparable to or greater than those required for key search on a block cipher with a 256-bit key (e.g. AES 256)

In which category does XMSS fall when instantiated with SHA256 or SHAKE256?

$\endgroup$
1

1 Answer 1

3
$\begingroup$

In which category does XMSS fall when instantiated with SHA256 or SHAKE256?

Well, XMSS is as strong as the second preimage resistance of the underlying hash function - with either SHA256 or SHAKE256, a second preimage can't be found (to the best of our knowledge, of course) any easier than finding an AES-256 key; hence it is NIST level 5.

For the IETF-defined parameter sets, XMSS uses SHAKE-128 for 256 bit hashes, which reduces the security level significantly (if not practically). On the other hand, the parameter sets defined in NIST SP 800-208 all use SHAKE-256, so the above logic applies.

$\endgroup$
6
  • $\begingroup$ @kelalaka: I hadn't realized that the IETF RFC8391 and NIST SP 800-208 differed... $\endgroup$
    – poncho
    Commented Dec 21, 2021 at 21:33
  • $\begingroup$ Does XMMS have real-life usage? Do you know anything about it? Note: the permutation property was good to include in the answer. $\endgroup$
    – kelalaka
    Commented Dec 21, 2021 at 21:40
  • 1
    $\begingroup$ @kelalaka: I do believe that XMSS is used on occasion to authenticate software updates (which is the ideal use case for it - we have tight control of the signer, we don't have to sign that many times, and we don't care if the signatures are largish...) $\endgroup$
    – poncho
    Commented Dec 21, 2021 at 22:00
  • $\begingroup$ Tight control, could you expand it a little? $\endgroup$
    – kelalaka
    Commented Dec 21, 2021 at 22:04
  • 1
    $\begingroup$ @kelalaka: well, with stateful hashes (such as XMSS), you have to be careful about remembering state (essentially, how many signatures you've generated so far) - if you sign two different things with the same state, well, bad things happen. A centralized signer for software updates can presumably be careful about that (and make sure that, say, a database backup and restore doesn't back up the state) - with other scenarios, we can't state this with such confidence. $\endgroup$
    – poncho
    Commented Dec 21, 2021 at 22:07

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.