Re: [IPsec] [saag] trapdoor'ed DH (and RFC-5114 again)

[Antonio Sanso]

hi Peter, (one of the authors here)
thanks a lot for you comments.
As for the case with Nikos we take on board and well appreciate 
comments/feedbacks.
Will pass the message.

Thanks a lot and regards

antonio

On Oct 20, 2016, at 2:13 AM, Peter Gutmann  wrote:

> Nikos Mavrogiannopoulos  writes:
> 
>> I am not sure that the recommendations of this paper should be blindly
>> trusted. There are some inaccurate facts about a library I work on [0], but a
>> part of the abstract is also concerning: "We examine over 20 open-source
>> cryptographic libraries and applications and observe that until January 2016,
>> not a single one validated subgroup orders by default."
> 
> I've got some comments on it as well, are any of the authors on this list?
> There are no email addresses given in the paper and I'm not sure that I should
> be spamming them all, or at least the ones I know... in any case the comments
> may be of interest to others, so I've posted them here.
> 
>  Using shorter private exponents yields faster exponentiation times, and is a
>  commonly implemented optimization. The justification for matching the order
>  of the subgroup q to the exponent size rather than making subgroup order as
>  large as possible is not documented anywhere in the standards documents.
> 
> It's not in any standards doc, but it's in HAC AFAIK, and originally came from
> a paper by van Oorschot and Wiener.  My code uses a curve-fitting mechanism to
> choose the appropriate-size exponent for a given prime (implementation
> provided by Colin Plumb many years ago).  Calling it a quadratic curve
> calculation is probably over-selling it a bit, it's just a way of matching the
> exponent size to the prime size without having to include a large lookup
> table.
> 
>  For protocols like TLS and SSH that allow a server to unilaterally specify
>  the group to use, this validation step is not possible for clients to
>  perform for non-safe primes: there is no way for the server to communicate
>  to the client the intended order of the group
> 
> Actually it is for TLS, anything implementing the TLS-LTS draft [1] will
> communicate the group order and the client can then verify it.
> 
>  We observe that no implementation that we examined validated group order for
>  subgroups of order larger than two
> 
> That's kind of a tautology there, both TLS and SSH make this impossible to do.
> At the moment there's at least one implementation that does this, and possibly
> more (there are some proprietary vendor stacks doing -LTS, but since they're
> for embedded devices and tend to be as minimalistic as possible - the most
> popular ASN.1 library there is memcpy() - I wouldn't be surprised if they
> skipped this particular check).  So there's a minimum of one, and a maximum of
> n.
> 
>  In addition, we observed that nearly every implementation uses short
>  exponents by default,
> 
> Yep, because they're the most efficient.  This is what killed RFC 5114,
> they're the most inefficient (random) DH domain parameters ever published.
> Which, in the long run, was probably a good thing since it strongly
> discouraged their use.
> 
>  They have been widely implemented in IPsec and TLS
> 
> Not in TLS they ain't, for the reason given above.  I realise there are
> oddball implementations out there that use or enable their use, but I wouldn't
> say that counts as "widely used".
> 
>  This means a client has no feasible way to validate that the group sent by
>  the server has the desired level of security or that a server’s key exchange
>  value is in the correct group for a non-safe prime.
> 
> See the previous note, TLS-LTS provides this capability.  If you're using the
> RFC 3526 DH params then you can also pretty easily recreate q from them, so
> it's a simple change to apply this fix.
> 
> (TLS-LTS also fixes a number of other issues in TLS 1.2 and earlier, it's not
> only the DH fix that's in there).
> 
>  TABLE II: TLS Library Behavior
> 
> I assume this was the item that Nikos was grumbling about :-).  The two issues
> are that the "Reuses exponent" entries are rather unclear and "Validates
> Subgroup" is somewhat tautological since standard TLS (without -LTS) doesn't
> allow you to do this, so the anwer is always "No".  I assume for "Reuses
> exponent" the entry "Application dependent" means "it's not very clear from
> the code", because my code certainly never reuses DH exponents.  However, to
> see that you need to know that although each DH instance uses an { x, y } pair
> that's fixed at the time of creation, no DH instance is ever reused in a TLS
> or SSH session,
> 
> (Nikos, if you want to do the subgroup checking with GnuTLS and interop-test
> an implementation that provides subgroup info and does the required checking,
> let me know and I'll put up a server.  Same for anyone else, e.g. the OpenSSL
> guys).
> 
>  implementations should follow the guidelines outlined in RFC 7919 for
>  selecting finite field Diffie-Hellman primes
> 
> Uh, 

Re: [IPsec] [saag] trapdoor'ed DH (and RFC-5114 again)

[Peter Gutmann]

Nikos Mavrogiannopoulos  writes:

>I am not sure that the recommendations of this paper should be blindly
>trusted. There are some inaccurate facts about a library I work on [0], but a
>part of the abstract is also concerning: "We examine over 20 open-source
>cryptographic libraries and applications and observe that until January 2016,
>not a single one validated subgroup orders by default."

I've got some comments on it as well, are any of the authors on this list?
There are no email addresses given in the paper and I'm not sure that I should
be spamming them all, or at least the ones I know... in any case the comments
may be of interest to others, so I've posted them here.

  Using shorter private exponents yields faster exponentiation times, and is a
  commonly implemented optimization. The justification for matching the order
  of the subgroup q to the exponent size rather than making subgroup order as
  large as possible is not documented anywhere in the standards documents.

It's not in any standards doc, but it's in HAC AFAIK, and originally came from
a paper by van Oorschot and Wiener.  My code uses a curve-fitting mechanism to
choose the appropriate-size exponent for a given prime (implementation
provided by Colin Plumb many years ago).  Calling it a quadratic curve
calculation is probably over-selling it a bit, it's just a way of matching the
exponent size to the prime size without having to include a large lookup
table.

  For protocols like TLS and SSH that allow a server to unilaterally specify
  the group to use, this validation step is not possible for clients to
  perform for non-safe primes: there is no way for the server to communicate
  to the client the intended order of the group

Actually it is for TLS, anything implementing the TLS-LTS draft [1] will
communicate the group order and the client can then verify it.

  We observe that no implementation that we examined validated group order for
  subgroups of order larger than two

That's kind of a tautology there, both TLS and SSH make this impossible to do.
At the moment there's at least one implementation that does this, and possibly
more (there are some proprietary vendor stacks doing -LTS, but since they're
for embedded devices and tend to be as minimalistic as possible - the most
popular ASN.1 library there is memcpy() - I wouldn't be surprised if they
skipped this particular check).  So there's a minimum of one, and a maximum of
n.

  In addition, we observed that nearly every implementation uses short
  exponents by default,

Yep, because they're the most efficient.  This is what killed RFC 5114,
they're the most inefficient (random) DH domain parameters ever published.
Which, in the long run, was probably a good thing since it strongly
discouraged their use.

  They have been widely implemented in IPsec and TLS

Not in TLS they ain't, for the reason given above.  I realise there are
oddball implementations out there that use or enable their use, but I wouldn't
say that counts as "widely used".

  This means a client has no feasible way to validate that the group sent by
  the server has the desired level of security or that a server’s key exchange
  value is in the correct group for a non-safe prime.

See the previous note, TLS-LTS provides this capability.  If you're using the
RFC 3526 DH params then you can also pretty easily recreate q from them, so
it's a simple change to apply this fix.

(TLS-LTS also fixes a number of other issues in TLS 1.2 and earlier, it's not
only the DH fix that's in there).

  TABLE II: TLS Library Behavior

I assume this was the item that Nikos was grumbling about :-).  The two issues
are that the "Reuses exponent" entries are rather unclear and "Validates
Subgroup" is somewhat tautological since standard TLS (without -LTS) doesn't
allow you to do this, so the anwer is always "No".  I assume for "Reuses
exponent" the entry "Application dependent" means "it's not very clear from
the code", because my code certainly never reuses DH exponents.  However, to
see that you need to know that although each DH instance uses an { x, y } pair
that's fixed at the time of creation, no DH instance is ever reused in a TLS
or SSH session,

(Nikos, if you want to do the subgroup checking with GnuTLS and interop-test
an implementation that provides subgroup info and does the required checking,
let me know and I'll put up a server.  Same for anyone else, e.g. the OpenSSL
guys).

  implementations should follow the guidelines outlined in RFC 7919 for
  selecting finite field Diffie-Hellman primes

Uh, no.  7919 is a my-way-or-the-highway spec, or more accurately my-way-or-
no-way.  You can't say "I'd like to do DH-2048" as with SSH, you can only use
the one value that 7919 specifies and if either side chooses some other
DH-2048 value you're required to fall back to RSA.  When this was discussed on
the TLS list, the general response, from those who commented, was that they
weren't going to use it because of this and othe

Re: [IPsec] [saag] trapdoor'ed DH (and RFC-5114 again)

[John Mattsson]

I have not read the paper in detail, but I agree with the high level
conclusions. If it were not for quantum computers, I think IETF should
move to curve25519 as quickly as possible. With quantum computers the
picture is more complicated as ECC would anyway need to be replaced with
PQC in the not to distant future.

Cheers,

John

On 19/10/16 09:36, "n.mavrogiannopou...@gmail.com on behalf of Nikos
Mavrogiannopoulos"  wrote:

>On Tue, Oct 18, 2016 at 8:46 PM, John Mattsson
> wrote:
>> New paper “Measuring small subgroup attacks against Diffie-Hellman”
>> https://eprint.iacr.org/2016/995.pdf
>> “Cryptographic recommendations from standards committees are often too
>> weak or vague”
>> “However, the tangle of RFCs and standards attempting to define current
>> best practices in key generation and parameter sizing do not paint a
>>clear
>> picture, and instead describe complex combinations of approaches and
>> parameters, exposing the fragility of the cryptographic ecosystem. As a
>> result, developers often forget or ignore edge cases, leaving many
>> implementations of Diffie-Hellman too close to vulnerable"
>>
>> “As we show in this paper, finite-field based Diffie-Hellman has many
>>edge
>> cases that make its correct use difficult, and which occasionally arise
>>as
>> bugs at the protocol level.”
>>
>> “As a concrete recommendation, modern Diffie-Hellman implementations
>> should prefer elliptic curve groups over safe curves with proper point
>> validation.”
>
>I am not sure that the recommendations of this paper should be blindly
>trusted. There are some inaccurate facts about a library I work on
>[0], but a part of the abstract is also concerning:
>"We examine over 20 open-source cryptographic libraries and
>applications and observe that until January 2016, not a single one
>validated subgroup orders by default."
>
>That's objectively accurate, but the authors do not attempt to find
>out the actual issue behind it. Are all implementations bad, or there
>are obstacles in doing that? I am aware that TLS client
>implementations do not validate subgroup orders by default, because
>the group information provided by TLS is not sufficient to validate
>the subgroup order. It is simply impossible for them to do any
>validation.
>
>regards,
>Nikos
>
>[0]. 
>https://lists.gnupg.org/pipermail/gnutls-devel/2016-October/008198.html

___
IPsec mailing list
IPsec@ietf.org
https://www.ietf.org/mailman/listinfo/ipsec

Re: [IPsec] [saag] trapdoor'ed DH (and RFC-5114 again)

[Nikos Mavrogiannopoulos]

On Tue, Oct 18, 2016 at 8:46 PM, John Mattsson
 wrote:
> New paper “Measuring small subgroup attacks against Diffie-Hellman”
> https://eprint.iacr.org/2016/995.pdf
> “Cryptographic recommendations from standards committees are often too
> weak or vague”
> “However, the tangle of RFCs and standards attempting to define current
> best practices in key generation and parameter sizing do not paint a clear
> picture, and instead describe complex combinations of approaches and
> parameters, exposing the fragility of the cryptographic ecosystem. As a
> result, developers often forget or ignore edge cases, leaving many
> implementations of Diffie-Hellman too close to vulnerable"
>
> “As we show in this paper, finite-field based Diffie-Hellman has many edge
> cases that make its correct use difficult, and which occasionally arise as
> bugs at the protocol level.”
>
> “As a concrete recommendation, modern Diffie-Hellman implementations
> should prefer elliptic curve groups over safe curves with proper point
> validation.”

I am not sure that the recommendations of this paper should be blindly
trusted. There are some inaccurate facts about a library I work on
[0], but a part of the abstract is also concerning:
"We examine over 20 open-source cryptographic libraries and
applications and observe that until January 2016, not a single one
validated subgroup orders by default."

That's objectively accurate, but the authors do not attempt to find
out the actual issue behind it. Are all implementations bad, or there
are obstacles in doing that? I am aware that TLS client
implementations do not validate subgroup orders by default, because
the group information provided by TLS is not sufficient to validate
the subgroup order. It is simply impossible for them to do any
validation.

regards,
Nikos

[0]. https://lists.gnupg.org/pipermail/gnutls-devel/2016-October/008198.html

___
IPsec mailing list
IPsec@ietf.org
https://www.ietf.org/mailman/listinfo/ipsec

Re: [IPsec] [saag] trapdoor'ed DH (and RFC-5114 again)

[John Mattsson]

New paper “Measuring small subgroup attacks against Diffie-Hellman”

https://eprint.iacr.org/2016/995.pdf


“Cryptographic recommendations from standards committees are often too
weak or vague”

“However, the tangle of RFCs and standards attempting to define current
best practices in key generation and parameter sizing do not paint a clear
picture, and instead describe complex combinations of approaches and
parameters, exposing the fragility of the cryptographic ecosystem. As a
result, developers often forget or ignore edge cases, leaving many
implementations of Diffie-Hellman too close to vulnerable"

“As we show in this paper, finite-field based Diffie-Hellman has many edge
cases that make its correct use difficult, and which occasionally arise as
bugs at the protocol level.”

“As a concrete recommendation, modern Diffie-Hellman implementations
should prefer elliptic curve groups over safe curves with proper point
validation.”

/John


On 18/10/16 16:47, "IPsec on behalf of Stephen Kent"
 wrote:

>Paul,
>
>It's  been over 8 years since this RFC was published, and I have not
>looked at it since then. My recollection is that we wrote 5114 because
>an IPsec developer approached me and said that he wanted to support
>these groups in a product. He said that he wanted test vectors for the
>groups, consistent with what we have done for many other algs. I
>persuaded Matt to generate the RFC because it was a relatively easy task
>a good way for Matt to get acquainted with the RFC process.
>
>As to your question, I have no info about how the NIST DH values were
>generated. However, I do agree with Yoav and Tero that it seems unduly
>prejudicial to declare these to be a MUST NOT. The fact that one can
>generate trap-doored DH values that cannot be detected is not the same
>as having proof that a given set of values have been generated in that
>fashion. Moreover, if one interprets a MUST NOT in this context to mean
>that an implementation supporting any of these groups is non-compliant,
>then that unfairly penalizes existing implementations, as Tero noted.
>Moreover, if the concern raised by the paper (which I have read) is with
>MODP groups of size 1024 (or smaller), only 1 of the groups in 5114 fits
>that criteria (section 2.1).
>
>I have not tracked the status of these NIST groups re evaluation
>criteria like FIPS 140-2. If these groups are approved for use in
>products evaluated under that FIPS (I don't know if they are),
>deprecating them creates a possible conundrum for vendors who want to
>comply with RFCs and with FIPS evaluation criteria. Thus I suggest a
>less dramatic response than declaring all of the groups in 5114 to be
>MUST NOT.
>
>I'm not a vendor of any crypto products (these days), and I've never
>been a crypto mathematician. So my views are based only on what I recall
>about the creation of 5114 and about IETF crytpo standards practices in
>general.
>
>Steve
>
>___
>IPsec mailing list
>IPsec@ietf.org
>https://www.ietf.org/mailman/listinfo/ipsec

___
IPsec mailing list
IPsec@ietf.org
https://www.ietf.org/mailman/listinfo/ipsec

Re: [IPsec] [saag] trapdoor'ed DH (and RFC-5114 again)

[Stephen Kent]

Paul,

It's  been over 8 years since this RFC was published, and I have not 
looked at it since then. My recollection is that we wrote 5114 because 
an IPsec developer approached me and said that he wanted to support 
these groups in a product. He said that he wanted test vectors for the 
groups, consistent with what we have done for many other algs. I 
persuaded Matt to generate the RFC because it was a relatively easy task 
a good way for Matt to get acquainted with the RFC process.


As to your question, I have no info about how the NIST DH values were 
generated. However, I do agree with Yoav and Tero that it seems unduly 
prejudicial to declare these to be a MUST NOT. The fact that one can 
generate trap-doored DH values that cannot be detected is not the same 
as having proof that a given set of values have been generated in that 
fashion. Moreover, if one interprets a MUST NOT in this context to mean 
that an implementation supporting any of these groups is non-compliant, 
then that unfairly penalizes existing implementations, as Tero noted. 
Moreover, if the concern raised by the paper (which I have read) is with 
MODP groups of size 1024 (or smaller), only 1 of the groups in 5114 fits 
that criteria (section 2.1).


I have not tracked the status of these NIST groups re evaluation 
criteria like FIPS 140-2. If these groups are approved for use in 
products evaluated under that FIPS (I don't know if they are), 
deprecating them creates a possible conundrum for vendors who want to 
comply with RFCs and with FIPS evaluation criteria. Thus I suggest a 
less dramatic response than declaring all of the groups in 5114 to be 
MUST NOT.


I'm not a vendor of any crypto products (these days), and I've never 
been a crypto mathematician. So my views are based only on what I recall 
about the creation of 5114 and about IETF crytpo standards practices in 
general.


Steve

___
IPsec mailing list
IPsec@ietf.org
https://www.ietf.org/mailman/listinfo/ipsec

Re: [IPsec] [saag] trapdoor'ed DH (and RFC-5114 again)

[Watson Ladd]

On Tue, Oct 18, 2016 at 3:33 AM, Tero Kivinen  wrote:
> Yoav Nir writes:
>> I’m not entirely comfortable with calling something a MUST NOT when all we
>> have is conjecture, but I have no love and no need of those DH groups.
>
> Same here, and it also makes it so that we cannot say our
> implementation is conforming rfc4307bis, even when we do already have
> support for AES, SHA2, 2048-bit DH, i.e. all the mandatory to
> implement algorithms in the new document, but we do also have code to
> propose the RFC5114 MODP groups, if user configures them to be used.
>
> Changing that is of course is very easy to do in implementation, but
> before this is deployed etc will take some time, and there is change,
> that some customer has explictly configure RFC5114 2048-bit MODP group
> in use, and by removing that we suddenly break their existing
> configuration.

In sane protocols the default MTI ciphersuite is always ready to be
used for exactly this reason. IKE's extensively flexible configuration
knobset was not a good idea for this reason.

>
> It is always annoying to explain to customer why we explictly broke
> their existing configurations unless there is real security reason for
> it. Looking that the paper, this only applies to the 1024-bit MODP
> group in RFC5114, even the paper says that 2048-bit MODP groups are
> safe, even if they would have same backdoor.
>
> We are already downgrading normal 1024-bit MODP group to SHOULD NOT,
> and this would make it two reasons to make RFC5114 1024-bit MODP group
> to SHOULD NOT (too short, and might be backdoored), so perhaps the
> compromize can be to make RFC5114 1024-bit MODP group number 22 to
> MUST NOT, and keep the groups 23-24 as SHOULD NOTs.

This seems reasonable to me.

>
> Anyways we need to modify the rfc4307bis text and add reference to
> this paper, as one more reason why groups 22-24 MUST NOT/SHOULD NOT be
> used.
>
>> I don’t believe anyone else depends on these groups (at least in
>> IPsec), so I’m fine with such a change.
>
> I do not think people depend on them, but I assume there is quite a
> lot of implementations there that can be configured to use them if
> explictly asked, thus making them MUST NOT will make it so that those
> implementations will not be conforming rfc4307bis.

That's sort of the point. We want these implementations to NOT support
these groups, just as RC4 die-die-die meant TLS implementations no
longer support RC4.

> --
> kivi...@iki.fi
>
> ___
> saag mailing list
> s...@ietf.org
> https://www.ietf.org/mailman/listinfo/saag



-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

___
IPsec mailing list
IPsec@ietf.org
https://www.ietf.org/mailman/listinfo/ipsec

Re: [IPsec] [saag] trapdoor'ed DH (and RFC-5114 again)

[Paul Wouters]

On Tue, 18 Oct 2016, Yoav Nir wrote:


It's a little more than conjecture.

1) It has been proven that malicious 1024 bit DH values can be generated
  by academia that cannot be independantly discovered. Therefore any
  nationstate with access to the same theory and more CPU power could
  have done this years ago.


Someone can trapdoor 1024-bit values, therefore someone else can trapdoor 
2048-bit values.


2) We have the RFC 5114 values who'se original authors/sponsors are not
  disclosing how these were generated.

1) + 2) means we cannot know if these values were trapdoor’ed.


Yeah, we cannot know. That’s why it’s conjecture.


conjecture: 1. an opinion or conclusion formed on the basis of 
incomplete information.

I have complete information for "one cannot detect trapdoors without knowing 
seed"

Paul

___
IPsec mailing list
IPsec@ietf.org
https://www.ietf.org/mailman/listinfo/ipsec

Re: [IPsec] [saag] trapdoor'ed DH (and RFC-5114 again)

[Tero Kivinen]

Yoav Nir writes:
> > Same here, and it also makes it so that we cannot say our
> > implementation is conforming rfc4307bis, even when we do already have
> > support for AES, SHA2, 2048-bit DH, i.e. all the mandatory to
> > implement algorithms in the new document, but we do also have code to
> > propose the RFC5114 MODP groups, if user configures them to be used.
> 
> I don’t think that’s the right way to interpret compliance with
> RFC4307bis. If you can configure your implementation to support only
> algorithms that are MUST, SHOULD, or MAY in the document, then you
> can configure your implementation to comply with 4307bis. I don’t
> think implementation compliance requires pulling out code. 

When rfc4307bis says MUST NOT do DES, and MUST NOT do 768-bit MODP, I
assume that to be conforming to that document, user is not able to
configure DES with 768-bit MODP group.

Of course MUST NOTs are difficult as it is really hard to show where
in your code you implement this specific MUST NOT (yes, there was one
customer asking us to point out where in code we implement each MUST
NOTs).

> Our implementation allows the user to key in long hex strings to
> construct MODP groups that are not available out of the box. With
> your interpretation we can never be compliant because they can
> always make up their own 512-bit group and add that to the available
> groups. 

That is different issue, as this is SHOULD feature in the RFC7296:

   parameters, up to certain size limits.  In support of this goal, all
   implementations of IKEv2 SHOULD include a management facility that
   allows specification (by a user or system administrator) of Diffie-
   Hellman parameters (the generator, modulus, and exponent lengths and
   values) for new Diffie-Hellman groups.  Implementations SHOULD
   provide a management interface through which these parameters and the
   associated Transform IDs may be entered (by a user or system
   administrator), to enable negotiating such groups.

Also there is nothing in the rfc4307bis saying that that is MUST
NOT...

On the otherhand if someone uses that interface to configure the
768-bit MODP group 1, then he is going against MUST NOT in rfc4307bis,
and his system is longer conforming... It might be good idea to limit
that interface so it will not allow any groups which are shorter than
1024-bits, just so users cannot do stupid things... 
-- 
kivi...@iki.fi

___
IPsec mailing list
IPsec@ietf.org
https://www.ietf.org/mailman/listinfo/ipsec

Re: [IPsec] [saag] trapdoor'ed DH (and RFC-5114 again)

[Yoav Nir]

> On 18 Oct 2016, at 13:33, Tero Kivinen  wrote:
> 
> Yoav Nir writes:
>> I’m not entirely comfortable with calling something a MUST NOT when all we
>> have is conjecture, but I have no love and no need of those DH groups.
> 
> Same here, and it also makes it so that we cannot say our
> implementation is conforming rfc4307bis, even when we do already have
> support for AES, SHA2, 2048-bit DH, i.e. all the mandatory to
> implement algorithms in the new document, but we do also have code to
> propose the RFC5114 MODP groups, if user configures them to be used.

I don’t think that’s the right way to interpret compliance with RFC4307bis. If 
you can configure your implementation to support only algorithms that are MUST, 
SHOULD, or MAY in the document, then you can configure your implementation to 
comply with 4307bis. I don’t think implementation compliance requires pulling 
out code.

Our implementation allows the user to key in long hex strings to construct MODP 
groups that are not available out of the box. With your interpretation we can 
never be compliant because they can always make up their own 512-bit group and 
add that to the available groups.

Yoav

___
IPsec mailing list
IPsec@ietf.org
https://www.ietf.org/mailman/listinfo/ipsec

Re: [IPsec] [saag] trapdoor'ed DH (and RFC-5114 again)

[Peter Gutmann]

Yoav Nir  writes:

>Someone can trapdoor 1024-bit values, therefore someone else can trapdoor
>2048-bit values.

Yep, space aliens.  However I'm really not too worried about those at the
moment.

Peter.

___
IPsec mailing list
IPsec@ietf.org
https://www.ietf.org/mailman/listinfo/ipsec

Re: [IPsec] [saag] trapdoor'ed DH (and RFC-5114 again)

[Yoav Nir]

> On 17 Oct 2016, at 19:19, Paul Wouters  wrote:
> 
> On Mon, 17 Oct 2016, Yoav Nir wrote:
> 
>> I’m not entirely comfortable with calling something a MUST NOT when all we 
>> have is conjecture,
> 
> It's a little more than conjecture.
> 
> 1) It has been proven that malicious 1024 bit DH values can be generated
>   by academia that cannot be independantly discovered. Therefore any
>   nationstate with access to the same theory and more CPU power could
>   have done this years ago.

Someone can trapdoor 1024-bit values, therefore someone else can trapdoor 
2048-bit values.

> 2) We have the RFC 5114 values who'se original authors/sponsors are not
>   disclosing how these were generated.
> 
> 1) + 2) means we cannot know if these values were trapdoor’ed.

Yeah, we cannot know. That’s why it’s conjecture.

Yoav

___
IPsec mailing list
IPsec@ietf.org
https://www.ietf.org/mailman/listinfo/ipsec

Re: [IPsec] [saag] trapdoor'ed DH (and RFC-5114 again)

[Tero Kivinen]

Yoav Nir writes:
> I’m not entirely comfortable with calling something a MUST NOT when all we
> have is conjecture, but I have no love and no need of those DH groups.

Same here, and it also makes it so that we cannot say our
implementation is conforming rfc4307bis, even when we do already have
support for AES, SHA2, 2048-bit DH, i.e. all the mandatory to
implement algorithms in the new document, but we do also have code to
propose the RFC5114 MODP groups, if user configures them to be used.

Changing that is of course is very easy to do in implementation, but
before this is deployed etc will take some time, and there is change,
that some customer has explictly configure RFC5114 2048-bit MODP group
in use, and by removing that we suddenly break their existing
configuration.

It is always annoying to explain to customer why we explictly broke
their existing configurations unless there is real security reason for
it. Looking that the paper, this only applies to the 1024-bit MODP
group in RFC5114, even the paper says that 2048-bit MODP groups are
safe, even if they would have same backdoor.

We are already downgrading normal 1024-bit MODP group to SHOULD NOT,
and this would make it two reasons to make RFC5114 1024-bit MODP group
to SHOULD NOT (too short, and might be backdoored), so perhaps the
compromize can be to make RFC5114 1024-bit MODP group number 22 to
MUST NOT, and keep the groups 23-24 as SHOULD NOTs.

Anyways we need to modify the rfc4307bis text and add reference to
this paper, as one more reason why groups 22-24 MUST NOT/SHOULD NOT be
used.

> I don’t believe anyone else depends on these groups (at least in
> IPsec), so I’m fine with such a change.

I do not think people depend on them, but I assume there is quite a
lot of implementations there that can be configured to use them if
explictly asked, thus making them MUST NOT will make it so that those
implementations will not be conforming rfc4307bis.
-- 
kivi...@iki.fi

___
IPsec mailing list
IPsec@ietf.org
https://www.ietf.org/mailman/listinfo/ipsec

Re: [IPsec] [saag] trapdoor'ed DH (and RFC-5114 again)

[Paul Wouters]

On Mon, 17 Oct 2016, Yoav Nir wrote:


I’m not entirely comfortable with calling something a MUST NOT when all we have 
is conjecture,


It's a little more than conjecture.

1) It has been proven that malicious 1024 bit DH values can be generated
   by academia that cannot be independantly discovered. Therefore any
   nationstate with access to the same theory and more CPU power could
   have done this years ago.

2) We have the RFC 5114 values who'se original authors/sponsors are not
   disclosing how these were generated.

1) + 2) means we cannot know if these values were trapdoor'ed.

If BBN/NIST/NSA wants to share how they seeded these values, we can all
publicly decide if we can keep using these or not. Without such
information, it just becomes an unnecessary risk to take.

Adding Steve Kent, co-author of RFC-5114, to the CC: so that he has
the opportunity to share what he knows about the origins of these
values and their seeds.


 but I have no love and no need of those DH groups.
I don’t believe anyone else depends on these groups (at least in IPsec), so I’m 
fine with such a change.


Thanks,

Paul


Yoav

  On 17 Oct 2016, at 18:54, Daniel Migault  
wrote:

In fact is there anyone opposing their status becomes MUST NOT in rfc4307bis.

On Mon, Oct 17, 2016 at 11:30 AM, John Mattsson  
wrote:
  > I'm proposing it is time to change this to MUST NOT for 4307bis.



  +1

  On 09/10/16 23:26, "IPsec on behalf of Paul Wouters"
   wrote:

  >
  >Released a few days ago:
  >
  >       http://eprint.iacr.org/2016/961
  >
  >       A kilobit hidden SNFS discrete logarithm computation
  >       Joshua Fried and Pierrick Gaudry and Nadia Heninger and Emmanuel 
Thomé
  >
  >       We perform a special number field sieve discrete logarithm
  >       computation in a 1024-bit prime field. To our knowledge, this
  >       is the first kilobit-sized discrete logarithm computation ever
  >       reported for prime fields. This computation took a little over
  >       two months of calendar time on an academic cluster using the
  >       open-source CADO-NFS software.
  >
  >Basically, this paper shows how to make a DH group of 1024 modp
  >with a backdoor, in two months of academic computing resources,
  >
  >The paper mentions 5114 a few times:
  >
  >       RFC 5114 [33] specifies a number of groups for use with
  >       Diffie-Hellman, and states that the parameters were drawn
  >       from NIST test data, but neither the NIST test data [39] nor
  >       RFC 5114 itself contain the seeds used to generate the finite
  >       field parameters
  >
  >And concludes:
  >
  >       Both from this perspective, and from our more modern one, 
dismissing the
  >       risk of trapdoored primes in real usage appears to have been a 
mistake,
  >       as the apparent difficulties encountered by the trapdoor designer 
in
  >1992
  >       turn out to be easily circumvented. A more conservative design 
decision
  >       for FIPS 186 would have required mandatory seed publication 
instead of
  >       making it optional.  As a result, there are opaque, standardized
  >1024-bit
  >       and 2048-bit primes in wide use today that cannot be properly 
verified.
  >
  >This is the strongest statement yet that I've seen to not trust any
  >of the RFC-5114 groups.
  >
  >The latest 4307bis document has these groups (22-24) as SHOULD NOT,
  >stating:
  >
  >       Group 22, 23 and 24 or 1024-bit MODP Group with 160-bit, and
  >       2048-bit MODP Group with 224-bit and 256-bit Prime Order Subgroup
  >       have small subgroups, which means that checks specified in the
  >       "Additional Diffie-Hellman Test for the IKEv2" [RFC6989] section
  >       2.2 first bullet point MUST be done when these groups are used.
  >       These groups are also not safe-primes.  The seeds for these groups
  >       have not been publicly released, resulting in reduced trust in
  >       these groups.  These groups were proposed as alternatives for
  >       group 2 and 14 but never saw wide deployment.  It is expected
  >       in the near future to be further downgraded to MUST NOT.
  >
  >I'm proposing it is time to change this to MUST NOT for 4307bis.
  >
  >Possibly, we should do this via SAAG in general, and then follow SAAG's
  >advise in IPSECME.
  >
  >Is there _any_ reason why group 22-24 should not be MUST NOT ?
  >
  >Paul
  >
  >___
  >IPsec mailing list
  >IPsec@ietf.org
  >https://www.ietf.org/mailman/listinfo/ipsec

___
saag mailing list
s...@ietf.org
https://www.ietf.org/mailman/listinfo/saag


___
IPsec maili

Re: [IPsec] [saag] trapdoor'ed DH (and RFC-5114 again)

[Yoav Nir]

I’m not entirely comfortable with calling something a MUST NOT when all we have 
is conjecture, but I have no love and no need of those DH groups.

I don’t believe anyone else depends on these groups (at least in IPsec), so I’m 
fine with such a change.

Yoav

> On 17 Oct 2016, at 18:54, Daniel Migault  wrote:
> 
> In fact is there anyone opposing their status becomes MUST NOT in rfc4307bis.
> 
> On Mon, Oct 17, 2016 at 11:30 AM, John Mattsson  > wrote:
> > I'm proposing it is time to change this to MUST NOT for 4307bis.
> 
> 
> 
> +1
> 
> On 09/10/16 23:26, "IPsec on behalf of Paul Wouters"
> mailto:ipsec-boun...@ietf.org> on behalf of 
> p...@nohats.ca > wrote:
> 
> >
> >Released a few days ago:
> >
> >   http://eprint.iacr.org/2016/961 
> >
> >   A kilobit hidden SNFS discrete logarithm computation
> >   Joshua Fried and Pierrick Gaudry and Nadia Heninger and Emmanuel Thomé
> >
> >   We perform a special number field sieve discrete logarithm
> >   computation in a 1024-bit prime field. To our knowledge, this
> >   is the first kilobit-sized discrete logarithm computation ever
> >   reported for prime fields. This computation took a little over
> >   two months of calendar time on an academic cluster using the
> >   open-source CADO-NFS software.
> >
> >Basically, this paper shows how to make a DH group of 1024 modp
> >with a backdoor, in two months of academic computing resources,
> >
> >The paper mentions 5114 a few times:
> >
> >   RFC 5114 [33] specifies a number of groups for use with
> >   Diffie-Hellman, and states that the parameters were drawn
> >   from NIST test data, but neither the NIST test data [39] nor
> >   RFC 5114 itself contain the seeds used to generate the finite
> >   field parameters
> >
> >And concludes:
> >
> >   Both from this perspective, and from our more modern one, dismissing 
> > the
> >   risk of trapdoored primes in real usage appears to have been a 
> > mistake,
> >   as the apparent difficulties encountered by the trapdoor designer in
> >1992
> >   turn out to be easily circumvented. A more conservative design 
> > decision
> >   for FIPS 186 would have required mandatory seed publication instead of
> >   making it optional.  As a result, there are opaque, standardized
> >1024-bit
> >   and 2048-bit primes in wide use today that cannot be properly 
> > verified.
> >
> >This is the strongest statement yet that I've seen to not trust any
> >of the RFC-5114 groups.
> >
> >The latest 4307bis document has these groups (22-24) as SHOULD NOT,
> >stating:
> >
> >   Group 22, 23 and 24 or 1024-bit MODP Group with 160-bit, and
> >   2048-bit MODP Group with 224-bit and 256-bit Prime Order Subgroup
> >   have small subgroups, which means that checks specified in the
> >   "Additional Diffie-Hellman Test for the IKEv2" [RFC6989] section
> >   2.2 first bullet point MUST be done when these groups are used.
> >   These groups are also not safe-primes.  The seeds for these groups
> >   have not been publicly released, resulting in reduced trust in
> >   these groups.  These groups were proposed as alternatives for
> >   group 2 and 14 but never saw wide deployment.  It is expected
> >   in the near future to be further downgraded to MUST NOT.
> >
> >I'm proposing it is time to change this to MUST NOT for 4307bis.
> >
> >Possibly, we should do this via SAAG in general, and then follow SAAG's
> >advise in IPSECME.
> >
> >Is there _any_ reason why group 22-24 should not be MUST NOT ?
> >
> >Paul
> >
> >___
> >IPsec mailing list
> >IPsec@ietf.org 
> >https://www.ietf.org/mailman/listinfo/ipsec 
> >
> 
> ___
> saag mailing list
> s...@ietf.org 
> https://www.ietf.org/mailman/listinfo/saag 
> 
> 
> ___
> IPsec mailing list
> IPsec@ietf.org
> https://www.ietf.org/mailman/listinfo/ipsec

___
IPsec mailing list
IPsec@ietf.org
https://www.ietf.org/mailman/listinfo/ipsec

Re: [IPsec] [saag] trapdoor'ed DH (and RFC-5114 again)

[Daniel Migault]

In fact is there anyone opposing their status becomes MUST NOT in
rfc4307bis.

On Mon, Oct 17, 2016 at 11:30 AM, John Mattsson 
wrote:

> > I'm proposing it is time to change this to MUST NOT for 4307bis.
>
>
>
> +1
>
> On 09/10/16 23:26, "IPsec on behalf of Paul Wouters"
>  wrote:
>
> >
> >Released a few days ago:
> >
> >   http://eprint.iacr.org/2016/961
> >
> >   A kilobit hidden SNFS discrete logarithm computation
> >   Joshua Fried and Pierrick Gaudry and Nadia Heninger and Emmanuel
> Thomé
> >
> >   We perform a special number field sieve discrete logarithm
> >   computation in a 1024-bit prime field. To our knowledge, this
> >   is the first kilobit-sized discrete logarithm computation ever
> >   reported for prime fields. This computation took a little over
> >   two months of calendar time on an academic cluster using the
> >   open-source CADO-NFS software.
> >
> >Basically, this paper shows how to make a DH group of 1024 modp
> >with a backdoor, in two months of academic computing resources,
> >
> >The paper mentions 5114 a few times:
> >
> >   RFC 5114 [33] specifies a number of groups for use with
> >   Diffie-Hellman, and states that the parameters were drawn
> >   from NIST test data, but neither the NIST test data [39] nor
> >   RFC 5114 itself contain the seeds used to generate the finite
> >   field parameters
> >
> >And concludes:
> >
> >   Both from this perspective, and from our more modern one,
> dismissing the
> >   risk of trapdoored primes in real usage appears to have been a
> mistake,
> >   as the apparent difficulties encountered by the trapdoor designer
> in
> >1992
> >   turn out to be easily circumvented. A more conservative design
> decision
> >   for FIPS 186 would have required mandatory seed publication
> instead of
> >   making it optional.  As a result, there are opaque, standardized
> >1024-bit
> >   and 2048-bit primes in wide use today that cannot be properly
> verified.
> >
> >This is the strongest statement yet that I've seen to not trust any
> >of the RFC-5114 groups.
> >
> >The latest 4307bis document has these groups (22-24) as SHOULD NOT,
> >stating:
> >
> >   Group 22, 23 and 24 or 1024-bit MODP Group with 160-bit, and
> >   2048-bit MODP Group with 224-bit and 256-bit Prime Order Subgroup
> >   have small subgroups, which means that checks specified in the
> >   "Additional Diffie-Hellman Test for the IKEv2" [RFC6989] section
> >   2.2 first bullet point MUST be done when these groups are used.
> >   These groups are also not safe-primes.  The seeds for these groups
> >   have not been publicly released, resulting in reduced trust in
> >   these groups.  These groups were proposed as alternatives for
> >   group 2 and 14 but never saw wide deployment.  It is expected
> >   in the near future to be further downgraded to MUST NOT.
> >
> >I'm proposing it is time to change this to MUST NOT for 4307bis.
> >
> >Possibly, we should do this via SAAG in general, and then follow SAAG's
> >advise in IPSECME.
> >
> >Is there _any_ reason why group 22-24 should not be MUST NOT ?
> >
> >Paul
> >
> >___
> >IPsec mailing list
> >IPsec@ietf.org
> >https://www.ietf.org/mailman/listinfo/ipsec
>
> ___
> saag mailing list
> s...@ietf.org
> https://www.ietf.org/mailman/listinfo/saag
>
___
IPsec mailing list
IPsec@ietf.org
https://www.ietf.org/mailman/listinfo/ipsec