15
$\begingroup$

According to this Matasano Crypto challenge, the NIST "likes" the following prime modulus, which appears to be expressed in hexadecimal:

ffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff

I have a few questions about it:

  • Is this number specified anywhere? I tried Googling it, both in decimal and in hexadecimal, hoping to find it somewhere, maybe in a NIST document, but I couldn't find it anywhere.

  • Why was this particular number picked? I know that Diffie-Hellman requires a prime modulus, and it should be big enough to prevent certain factoring attacks, and it should also be a safe prime, also to prevent certain factoring attacks, but there are lots of numbers with these properties. Was that number chosen somewhat arbitrarily, or were there any other criteria used to pick it?

  • Is this number used for anything other than Diffie-Hellman, like maybe RSA or elliptic curve algorithms?

$\endgroup$
  • 1
    $\begingroup$ I don't know about #1 and #2 (-> no full answer), but I can say that you can't use this prime for ECC because it's too large for that use-case (unless you go super-crazy) and chances are negligible that you'll use it in RSA by accident and you won't use by intention because it's publicly known. And there are no known attacks on (finite field) group parameters that you couldn't detect nowadays (just check if it's a safe prime). $\endgroup$ – SEJPM May 9 '16 at 18:59
25
$\begingroup$

Is this number specified anywhere?

It was formally specified in this RFC as the 1536 bit MODP group (although its use predates that RFC). However, from what I've seen, the 2048 bit MODP group from that same document is actually more popular.

Why was this particular number picked?

Well, it's a safe prime; in addition, the leading 64 bits and the trailing 64 bits are all 1's; this makes certain operations somewhat more efficient.

The middle bits are (mostly) from the binary expansion of $\pi$; this was done to demonstrate that this number wasn't chosen with a secret weakness in mind; making this a 'nothing-up-my-sleeve' number.

The procedure used to select this number was created by Richard Schroeppel; the earliest reference I have for that is this RFC, appendix E

Is this number used for anything other than Diffie-Hellman?

Not to my knowledge; as a well-known prime, it's not suitable for RSA, and it's too large to be really useful for elliptic curves. And, as it doesn't have a moderate sized subgroup, it doesn't work well for DSA (as the signatures would be far larger than required). It'd work for El Gamal and IES, however those are really Diffie-Hellman being reused in a public key encryption context.

$\endgroup$
  • $\begingroup$ What does any of this have to do with NIST? The only mention of NIST I saw in that document was about something unrelated (something about AES). $\endgroup$ – Elias Zamaria May 9 '16 at 20:40
  • 5
    $\begingroup$ @EliasZamaria: not really - this group was originally created by the IETF for use in IKE (Internet Key Exchange); NIST was not involved. In addition, NIST would greatly prefer the use of a MODP group 2048 or 3072 bits in size, so the claim that NIST "likes" this particular 1536 bit group is somewhat overenthusiastic... $\endgroup$ – poncho May 9 '16 at 20:50
2
$\begingroup$

This particular prime has been widely used in implementations of the Internet Key Exchange Protocol (IKE) and commonly referred to as Group 5. Group 5 has been in many devices for over a decade. Depending on your viewpoint this fact is either good or bad. It's good if you are implementing IKE and want to interoperate with other implementations of IKE. It is bad if you are concerned about a some evil entity using its wide deployment to amortize the cost of discrete logarithm attacks. I would prefer that the evil entities that I know about spending time trying to attack a 1536-bit discrete log than doing all of the other evil things that they do to their populace - but that may just be me.

$\endgroup$

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.