3
$\begingroup$

In FIPS 186-4, page 32, about FFC crypto it is required that the length of $p$ will be exactly 1024 bit and the length of $q$ will be exactly 160 bit. Why is the requirement not stated in terms of lower bounds?

For instance, any $p$ with length greater than 1024 bit would be good, and any $q$ with length greater than 160 bit would be good. For instance, if $q$ is 170 bit, would that harm security?

$\endgroup$
  • $\begingroup$ Larger sizes certainly won't hurt security. But restricting the sizes might simplify some implementations. $\endgroup$ – CodesInChaos Sep 6 '14 at 22:12
  • $\begingroup$ A.1.1.1 on p32 is for validation of parameters generated under 186-2 cn1 which was exact 1024 and 160 (and also required SHA-1 for the hash making q other than 160 useless). Since 186-3 June 2009 there have been three other (larger) options for p with q 224 or 256, which is matched to SHA-2 but not actually requiring it and 4.6 specifies how to handle hash longer than q; the new algs in A.1.1.2-3 and A.1.2.1-2 handle those. But a few exact values instead one exact value is still not a range, and doesn't really change the answer. $\endgroup$ – dave_thompson_085 Sep 8 '14 at 5:08
2
$\begingroup$

I don't remember whether there is an official NIST publication on the topic, but there are definitely advantages to having a small set of possible key sizes. Contrasting RSA and DSA is instructive in this respect. A 170-bit $q$ wouldn't be less secure than a 160-bit $q$ if implemented correctly, but offering the choice is less secure.

Security strength

The lack of guidance on choosing an RSA key size has led to some users picking insecurely low sizes, or occasionally, conversely, needlessly high (and thus slow) sizes. The original DSA standard (FIPS 186-1) allowed a range of $p$ sizes from 512 to 1024; the current version imposes the higher end of the range and does not allow going further. NIST now publishes a list of correspondence between key size and security strength in SP 800-57.

Interoperability

When an algorithm may be instantiated with different key sizes, interoperability requires that all cooperating implementations support compatible key sizes. For example, with a signature algorithm, all verifies must support key sizes that are generated by any signer. This means additional implementation complexity (never a good thing for security, and a pain for implementers anyway) imposed on everyone. This also means that communication protocols may need an extra step to negociate key sizes, which is both extra overhead and a risk of security downgrade if one party is malicious (or due to a man-in-the-middle, but that would mean the protocol is flawed).

Implementation flaws

Allowing variable key sizes means additional implementation complexity, and more complexity means more risk of bugs. FIPS 186-1 already restricted $p$ sizes to a multiple of 32, the word size on many machines, to avoid bugs that were not all that uncommon with RSA implementations in computing the size of intermediate values, the memory requirements, etc. For example, there have been (and probably still are) RSA implementations that don't produce the expected modulus size when that expected size is odd, or that calculate the byte size from the word size by dividing by 4 and rounding down instead of up; DSA is not prone to these particular bugs.

Testing

Given the risk of bugs, every size must be tested, or at least a sufficient sample. Testing every RSA size, for example, is impractical. Testing schemes generally require testing an algorithm at each size they will be used for. This is again extra work which is not required if there is a single standard size.

$\endgroup$
  • $\begingroup$ verifies $\mapsto$ verifiers $\;$ $\endgroup$ – user991 Sep 7 '14 at 7:08
  • $\begingroup$ I wish NIST would do the same for KDF's. It's a mess with multiple MB of test vectors, that still don't cover all the options, and all the verified implementations (CAVP) implement a different KDF's. $\endgroup$ – Maarten Bodewes Sep 8 '14 at 16:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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