Tuesday, 5 January 2016

What the heck is RFC 5114?

Mandatory Disclaimer: IANAC (I am not a cryptographer) so I might likely end up writing a bunch of mistakes in this blog post...

I already talked about Diffie–Hellman (DH from now on) in TLS in my previous post: Small subgroup attack in Mozilla NSS.
As mentioned FWIW I strongly agree with Google Chrome decision to deprecate DHE .
The reason is mainly due to the Weak Diffie-Hellman attack and related paper . If you are interested in this topic there is a really nice presentation about it at 32C3 .
This shows a really nice potential attack that anyone with enough computational power (let's say NSA) can perform against DHE 1024 bits (details in the paper).
Said that for some reason I have been looking at DHE for a while now and one day I hit RFC 5114.

Now what the heck is this specification about :S ?

I found only few references about it. One funny one from here says (emphasis mine):

There is a semi-mysterious RFC 5114 – Additional Diffie-Hellman Groups document. It introduces new MODP groups not with higher sizes, but just with different primes.
Nothing triggered this document, no one really wanted these, but no one really objected to it either, so the document (originating from Defense contractor BBN) made it to RFC status.

Now let's see for example the 1024-bit  numbers

The hexadecimal value of the prime is:

   p = B10B8F96 A080E01D DE92DE5E AE5D54EC 52C99FBC FB06A3C6
       9A6A9DCA 52D23B61 6073E286 75A23D18 9838EF1E 2EE652C0
       13ECB4AE A9061123 24975C3C D49B83BF ACCBDD7D 90C4BD70
       98488E9C 219A7372 4EFFD6FA E5644738 FAA31A4F F55BCCC0
       A151AF5F 0DC8B4BD 45BF37DF 365C1A65 E68CFDA7 6D4DA708
       DF1FB2BC 2E4A4371

   The hexadecimal value of the generator is:

   g = A4D1CBD5 C3FD3412 6765A442 EFB99905 F8104DD2 58AC507F
       D6406CFF 14266D31 266FEA1E 5C41564B 777E690F 5504F213
       160217B4 B01B886A 5E91547F 9E2749F4 D7FBD7D3 B9A92EE1
       909D0D22 63F80A76 A6A24C08 7A091F53 1DBF0A01 69B6A28A
       D662A4D1 8E73AFA3 2D779D59 18D08BC8 858F4DCE F97C2A24
       855E6EEB 22B3B2E5

   The generator generates a prime-order subgroup of size:

   q = F518AA87 81A8DF27 8ABA4E7D 64B7CB9D 49462353

Some straightforward questions comes to my mind:

  • Why the generator g is so big ? Often the generator is 2. Now I know I am aware that the generator g leaks one bit but AFAIK this is still considered safe.
  • Why (p-1)/2 is not a safe prime? (p-1)/2 is divided at least by 7,8,... (what is going one here :S?) AFAIK having (p-1)/2 being a safe prime is important for DH. Maybe in this case would not matter due the "weird" g? (Comments are welcome)
  • Is 160 bit a big enough value for q giving the fact a real generator would give a bigger number ?
Said that is this RFC 5114 used at all? A quick search showed that:

  • Bouncy Castle just changed the default to 2048 just few months ago (but still use rfc5114)
  •  OpenSSL has built-in support for these parameters from OpenSSL 1.0.2 
  • maybe more....

It would be really nice if someone can comment and answer to my questions :)


Anonymous said...

I believe the Defense Contractor that wrote the RFC was worried about compliance with NIST's Standard for Diffie-Hellman-like key exchanges: NIST Special Publication 800-56A. If you look at the original version of SP 800-56A and turn to page 28 you will find a table which REQUIRES a prime order subgroup of size 160,224, and 256 bits for 1024, 2048, and 2048 bit primes respectively. This is the requirement for DSA primes and not necessary for Diffie-Hellman The sizes are technically not optional or minimal but required to be what is specified. As far as I know NIST never enforced this requirement nor did they probably even mean to make it a requirement. They probably just copied it from the DSA standard. The Defense contractor might have thought they'd get an advantage by being the ONLY vendor with products that ACTUALLY satisfied the standard. Such is the world of marketing.

Antonio Sanso said...

well but why making those factors sooooo small and soooo many ?

JMKelley said...

"Why (p-1)/2 is not a safe prime?" If the least significant [LS] 4 bits of the original prime are xx01 (where x is either 0 or 1), the the number formed by (p-1)/2 is even, and is divisible by at least 2. If the LS four bits are 0001, as is the case here, then the result is divisible by at least 2, 4, & 8.

The fact that DH is missing rules for exceptions like these makes the whole process appear to be smoke, mirrors, and deception.

Romilda Gareth said...