Mailing List Archive: exim: dev

Re: Bug#475194: D-H parameter generation is All Wrong

Index | Next | Previous | View Threaded

sacrificial-spam-address at horizon

Apr 10, 2008, 12:04 PM

Post #1 of 5 (344 views)
Permalink

Re: Bug#475194: D-H parameter generation is All Wrong

I recently administered a stiff flaming to the Debian package maintainers
for exim4, and was rebuffed with the observation that the behaviour I was
complaing about was recommended by the exim specification, section 39.3.

Some of the original flame:

Marc Haber <mh+debian-packages[at]zugschlus.de> wrote:
> On Wed, Apr 09, 2008 at 10:34:00AM -0400, sacrificial-spam-address[at]horizon.com wrote:
>> The entire premise of the script /usr/share/exim4/exim4_refresh_gnutls-params
>> is based on a serious misapprehension of the role of Diffie-Hellman
>> parmeters in performing encryption.
>
> It is, however, in accordance with upstream's recommendations.
>
>> I wish I could come up with a polite way to put this, but the entire
>> thing smells strongly of cluon deficiency.
>
> Point taken. Please give the same advice upstream and we'll follow
> once upstream changes their recommendations.

So I'd like to suggest that the advice in that section undergo some
considerable revision.

There appears to be a fundamental misapprehension about the role of
Diffie-Hellman parameters. Section 39.3 conflates them with the the
RSA secret key, which is actual secret key material and should not be
called a "parameter". The D-H parameters are not key material, and do
not need to be protected from inspection. In fact, they are sent in the
clear to everyone who initiates a TLS session. Since the Debian package
doesn't generate an RSA key at all, the restrictive permissions looked
like blatant cluelessness.

In the Diffie-Hellman algorithm, the actual key is chosen fresh for each
connection, and not stored on disk anywhere, ever.

The only requirement for the parameters is that they must not be
maliciously chosen; an attacker who can choose the Diffie-Hellman modulus
can make an attack easier.

But there's no need to keep the values secret, any more than it's a secret
that SMTP uses port 25.

It's also not very important that the D-H parameters be changed often;
while changing them N times makes it N times as much work for an attacker
that wants to read ALL of your mail, it's better to just use a larger
prime and make it N times harder for an attacker to read ANY of your
mail.

In fact, many cryptographic standards just specify a menu of fixed
D-H parameters for all implmentations for all time (e.g. RFC3526).
Generating a set once at install time is also reasonable. Changing it
daily is silly.

I might also mention that 1024 bits (which is O(2^80) operations to
break) is considered a bit small for serious security these days.
GNU TLS defaults to 2048 bits, a more reasonable default.

(As I mentioned earlier, the Debian package no longer generates an RSA
key, and I can't find anything in src/tls-gnu.c that uses such a key,
but there does appear to be somethink in tls-openssl.c. So I'm a bit
confused about that part of things.)

--
## List details at http://lists.exim.org/mailman/listinfo/exim-dev Exim details at http://www.exim.org/ ##

bob at db

Apr 11, 2008, 1:31 PM

Post #2 of 5 (315 views)
Permalink

Re: Bug#475194: D-H parameter generation is All Wrong [In reply to]

sacrificial-spam-address[at]horizon.com wrote:
> I recently administered a stiff flaming to the Debian package maintainers
> for exim4, and was rebuffed with the observation that the behaviour I was
> complaing about was recommended by the exim specification, section 39.3.

I'm not saying you're wrong and I don't mean to sound disrespectful, but
I would recommend you also post a few words about why the Exim community
should care about your opinions on this matter.

Also, with the exception of the recommendation of using 2048 bits rather
then 1024, it sound's to me like Exim is 'erring on the side of caution'
so to speak. Hardly the worst mistake you can make in cryptography...

Bob

--
## List details at http://lists.exim.org/mailman/listinfo/exim-dev Exim details at http://www.exim.org/ ##

tom at duncanthrax

Apr 13, 2008, 4:58 AM

Post #3 of 5 (310 views)
Permalink

Re: Bug#475194: D-H parameter generation is All Wrong [In reply to]

Dear anonymous Crypto-Expert,

> There appears to be a fundamental misapprehension about the role of
> Diffie-Hellman parameters. Section 39.3 conflates them with the the
> RSA secret key, which is actual secret key material and should not be
> called a "parameter". The D-H parameters are not key material, and do
> not need to be protected from inspection. In fact, they are sent in the
> clear to everyone who initiates a TLS session. Since the Debian package
> doesn't generate an RSA key at all, the restrictive permissions looked
> like blatant cluelessness.

I've removed the references to RSA from 39.3 completely, thanks.

> It's also not very important that the D-H parameters be changed often;

So there still is some value in changing them?

> while changing them N times makes it N times as much work for an attacker
> that wants to read ALL of your mail, it's better to just use a larger
> prime and make it N times harder for an attacker to read ANY of your
> mail.

What about doing both? :)

> In fact, many cryptographic standards just specify a menu of fixed
> D-H parameters for all implmentations for all time (e.g. RFC3526).
> Generating a set once at install time is also reasonable. Changing it
> daily is silly.

39.3 does not say "daily", it says "the frequency depending on your
paranoia level". Now how paranoid should Debian be? I have no idea, and
with my limited crypto skills, I can't give them a recommendation. Stock
Exim does exacly what you want, compute D-H params exactly once.

> I might also mention that 1024 bits (which is O(2^80) operations to
> break) is considered a bit small for serious security these days.
> GNU TLS defaults to 2048 bits, a more reasonable default.

Paranoia level again :)

/tom

--
## List details at http://lists.exim.org/mailman/listinfo/exim-dev Exim details at http://www.exim.org/ ##

sacrificial-spam-address at horizon

Apr 13, 2008, 2:58 PM

Post #4 of 5 (302 views)
Permalink

Re: Bug#475194: D-H parameter generation is All Wrong [In reply to]

"B. Johannessen" <bob[at]db.org> wrote:

> sacrificial-spam-address[at]horizon.com wrote:
>> I recently administered a stiff flaming to the Debian package maintainers
>> for exim4, and was rebuffed with the observation that the behaviour I was
>> complaing about was recommended by the exim specification, section 39.3.
>
> I'm not saying you're wrong and I don't mean to sound disrespectful, but
> I would recommend you also post a few words about why the Exim community
> should care about your opinions on this matter.

Why you should care? Because I'm Napoleon Bonaparte, Emperor of France!
Oh, wait a minute... even if that were true, it wouldn't be a good reason.

Actually, the exim community *shouldn't* care about my opinions, at least the
subjective parts that are just opinion. Only the objective truths matter.
Is there actually any benefit to changing D-H parameters?

> Also, with the exception of the recommendation of using 2048 bits rather
> then 1024, it sound's to me like Exim is 'erring on the side of caution'
> so to speak. Hardly the worst mistake you can make in cryptography...

If that's a well-considered decision based on knowing all the facts,
I have no objection. It just appeared to be based on misunderstanding.

In particular, regenerating the modulus periodically causes operational
problems for a considerable number of users (although that's mostly
due to gnutls's grossly excessive entropy consumption when generating
new moduli), and doesn't give any other advantage over using a slightly
larger fixed modulus.

It's also rather computationally expensive to generate large "safe primes",
which can be a PITA for small network appliances.

So it seems like somewhat misplaced caution, strengthening the deadbolt but
not reinforcing the hinge pins.

Every security standard that I can find that uses D-H considers very
long-lived prime moduli quite reasonable. Examples:

PKCS #3: Diffie-Hellman Key-Agreement Standard
(suggests generation by central authority rather than each user)
ssh: Uses a fixed modulus, but has provision for selecting from a menu.
See the file /etc/ssh/moduli, generally shipped with the distribution.
See RFC4419 for details, and a discussion of the security of
fixed D-H parameters,
RFC 4346, the TLS specification, specifically allows the Diffie-Hellman
parameters to be specified in the long-lived server certificate.
(sect. 8.1.2)
The OpenId spec specifies a particular default modulus.
RFC 2409 (Internet Key Exchange) and RFC2412 (Oakley) use a menu of
fixed parameters, one for each possible size. RFC 3526 provides
the (unique) parameters for sizes from 1536 to 8192 bits, and has
a useful appendix of matching conventional encryption strengths.

I can't find any references that recommend periodic D-H parameter
(also called D-H group) changes.

It seems like someone changing the air in their tires preiodically. No,
it doesn't do any harm, and I suppose it might be considered "erring on
the side of caution", but it doesn't do any good, either.

The correct thing to say is "you MAY change the parameters periodically,
but there's no significant security benefit to doing so."

There is one discrete logarithm algorithm (the so-called "index calculus
algorithm") that has most of its computation depending only on the
modulus p, after which any given discrete log problem g^x = y (mod p)
can be solved rapidly, but it takes L_p[1/2, c] time, i.e.

e^(O(1)*(log p)^(1/2) * (log log p)^(1/2))

This is impractical against moduli sized to resist number field sieve
algorithms that take L_p[1/3, c] time, i.e.

e^(O(1)*(log p)^(1/3) * (log log p)^(2/3))

Even before you reach 512 bits, this is far more efficient.
(The constants c are the O(1) terms, which I don't have at my fingertips
right now.)

In theory, if an algorithm nearly as efficient as the number field sieve
but result-independent were found, there would be a security benefit to
minimizing the number of keys generated with a particular modulus.

But no such algorithm is known.

--
## List details at http://lists.exim.org/mailman/listinfo/exim-dev Exim details at http://www.exim.org/ ##

mh+exim-dev at zugschlus

May 4, 2008, 12:31 AM

Post #5 of 5 (139 views)
Permalink

Re: Bug#475194: D-H parameter generation is All Wrong [In reply to]

Dear anonymous crypto-expert,

On Sun, Apr 13, 2008 at 01:58:46PM +0200, Tom Kistner wrote:
> > It's also not very important that the D-H parameters be changed often;
>
> So there still is some value in changing them?
>
> > while changing them N times makes it N times as much work for an attacker
> > that wants to read ALL of your mail, it's better to just use a larger
> > prime and make it N times harder for an attacker to read ANY of your
> > mail.
>
> What about doing both? :)

It would help if you'd answer the question that Tom has asked three
weeks ago since you seem to have knowledge that only a few people on
this list have.

> > In fact, many cryptographic standards just specify a menu of fixed
> > D-H parameters for all implmentations for all time (e.g. RFC3526).
> > Generating a set once at install time is also reasonable. Changing it
> > daily is silly.
>
> 39.3 does not say "daily", it says "the frequency depending on your
> paranoia level". Now how paranoid should Debian be? I have no idea, and
> with my limited crypto skills, I can't give them a recommendation. Stock
> Exim does exacly what you want, compute D-H params exactly once.

And Debian has changed the DH parameter size to 2048 bits (hoping that
the patch I applied to tls-gnu.c #defining DH_BITS to 2048 and
PARAM_SIZE to 2*2048 was all that needed changing). Since generation
of 2048 bits DH parameters takes a long time even on recent systems, I
have disabled the generation of DH parameters completely, so all
Debian installations are now using a set of DH parameters generated at
packae build time. We still ship the script that was used to
regenerate the parameters daily, so local admins may choose to invoke
it on a regular basis.

I do sincerely hope that this is an acceptable compromise, I do not
have sufficient crypto knowledge to be a judge.

>
> > I might also mention that 1024 bits (which is O(2^80) operations to
> > break) is considered a bit small for serious security these days.
> > GNU TLS defaults to 2048 bits, a more reasonable default.
>
> Paranoia level again :)

I'd trust the GnuTLS people to know what they're doing and go with
their default.

Greetings
Marc

--
-----------------------------------------------------------------------------
Marc Haber | "I don't trust Computers. They | Mailadresse im Header
Mannheim, Germany | lose things." Winona Ryder | Fon: *49 621 72739834
Nordisch by Nature | How to make an American Quilt | Fax: *49 3221 2323190

--
## List details at http://lists.exim.org/mailman/listinfo/exim-dev Exim details at http://www.exim.org/ ##

Index | Next | Previous | View Threaded

Interested in having your list archived? Contact lists@gossamer-threads.com