Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > sci.crypt > #32911 > unrolled thread

How is NSA breaking so much crypto?

Back to article view | Back to sci.crypt

Contents

  How is NSA breaking so much crypto? Rich <rich@example.invalid> - 2015-10-15 01:44 +0000
    Re: How is NSA breaking so much crypto? "Chris M. Thomasson" <nospam@nospam.nospam> - 2015-10-15 12:04 -0700
      Re: How is NSA breaking so much crypto? wizzofozz <oscxxxxxxxaas@gmail.com> - 2015-10-15 22:24 +0200
        Re: How is NSA breaking so much crypto? William Unruh <unruh@invalid.ca> - 2015-10-15 23:13 +0000
          Re: How is NSA breaking so much crypto? <william@wilbur.25thandClement.com> - 2015-10-16 18:47 -0700
        Re: How is NSA breaking so much crypto? Jan Panteltje <pNaOnStPeAlMtje@yahoo.com> - 2015-10-16 10:09 +0000
      Re: How is NSA breaking so much crypto? Rich <rich@example.invalid> - 2015-10-15 22:38 +0000
      Re: How is NSA breaking so much crypto? William Unruh <unruh@invalid.ca> - 2015-10-15 23:11 +0000
        Re: How is NSA breaking so much crypto? Jakob Bohm <jb-usenet@wisemo.com> - 2015-10-16 02:08 +0200
          Re: How is NSA breaking so much crypto? Rich <rich@example.invalid> - 2015-10-16 00:25 +0000
            Re: How is NSA breaking so much crypto? Jakob Bohm <jb-usenet@wisemo.com> - 2015-10-16 04:04 +0200
    Re: How is NSA breaking so much crypto? Jeffrey Goldberg <nobody@goldmark.org> - 2015-10-16 11:53 -0500
      Re: How is NSA breaking so much crypto? Rich <rich@example.invalid> - 2015-10-16 17:54 +0000
        Re: How is NSA breaking so much crypto? <william@wilbur.25thandClement.com> - 2015-10-16 19:14 -0700
      Re: How is NSA breaking so much crypto? Jakob Bohm <jb-usenet@wisemo.com> - 2015-10-16 20:18 +0200
      Re: How is NSA breaking so much crypto? kg <kristiag+news@math.ntnu.no> - 2015-10-16 20:59 +0000
        Re: How is NSA breaking so much crypto? Jeffrey Goldberg <nobody@goldmark.org> - 2015-10-16 23:19 -0500
          Re: How is NSA breaking so much crypto? kg <kristiag+news@math.ntnu.no> - 2015-10-18 11:37 +0000
            Re: How is NSA breaking so much crypto? Jeffrey Goldberg <nobody@goldmark.org> - 2015-10-19 00:20 -0500
    Re: How is NSA breaking so much crypto? Anonymous <nobody@remailer.paranoici.org> - 2015-10-18 22:53 +0000
      Re: How is NSA breaking so much crypto? Rich <rich@example.invalid> - 2015-10-19 01:18 +0000
    Re: How is NSA breaking so much crypto? Noob <root@127.0.0.1> - 2015-10-30 08:45 +0100

Page 1 of 2  [1] 2  Next page →

#32911 — How is NSA breaking so much crypto?

https://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-breaking-so-much-crypto/

Small quote from the URL above:

    "There have been rumors for years that the NSA can decrypt a
    significant fraction of encrypted Internet traffic. In 2012, James
    Bamford published an article quoting anonymous former NSA officials
    stating that the agency had achieved a \u201ccomputing
    breakthrough\u201d that gave them \u201cthe ability to crack
    current public encryption.\u201d The Snowden documents also hint at
    some extraordinary capabilities: they show that NSA has built
    extensive infrastructure to intercept and decrypt VPN traffic and
    suggest that the agency can decrypt at least some HTTPS and SSH
    connections on demand.

    However, the documents do not explain how these breakthroughs work,
    and speculation about possible backdoors or broken algorithms has
    been rampant in the technical community. Yesterday at ACM CCS, one
    of the leading security research venues, we and twelve coauthors
    presented a paper that we think solves this technical mystery.

    The key is, somewhat ironically, Diffie-Hellman key exchange, an
    algorithm that we and many others have advocated as a defense
    against mass surveillance. Diffie-Hellman is a cornerstone of
    modern cryptography used for VPNs, HTTPS websites, email, and many
    other protocols. Our paper shows that, through a confluence of
    number theory and bad implementation choices, many real-world users
    of Diffie-Hellman are likely vulnerable to state-level attackers.

    ..."

[toc] | [next] | [standalone]

#32960

> "Rich"  wrote in message news:mvn0el$nr4$1@dont-email.me...

> https://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-breaking-so-much-crypto/

[...]

A friend of mine advised me to give the NSA a heads up on my cipher just in
case it turns out to be "hard to crack". This in turn gave me some 
interesting
nightmares! I told him that I hope its not that hard to bust open, then he 
said
it did not matter because it could turn out to be difficult to crack...

Should I send them a link to my webpage and clearly state that this is a 
toy,
but here it is just in case?

Yikes!

Any thoughts?

;^o 

[toc] | [prev] | [next] | [standalone]

#32967

On 15-10-2015 21:04, Chris M. Thomasson wrote:
>> "Rich"  wrote in message news:mvn0el$nr4$1@dont-email.me...
> 
>> https://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-breaking-so-much-crypto/
>>
> 
> [...]
> 
> A friend of mine advised me to give the NSA a heads up on my cipher just in
> case it turns out to be "hard to crack". This in turn gave me some
> interesting
> nightmares! I told him that I hope its not that hard to bust open, then
> he said
> it did not matter because it could turn out to be difficult to crack...
> 

I don't understand this. Why would you give them a heads up? Currently
your cipher isn't widely used, I guess, so I'd imagine they wouldn't be
very interested anyway. Unless it's so strong they want to use it
themselves. Or maybe use it for their internal weekly friday afternoon
challenge ;-)

> Should I send them a link to my webpage and clearly state that this is a
> toy,
> but here it is just in case?

Maybe you could send them, if anything, your paper. Speaking of, is it
finished yet ;-)

> Any thoughts?

Yes, but slightly unrelated;

I've been wondering for some time now what would happen if I dd a bunch
of random bytes, coming from /dev/random or maybe /dev/urand say, to a 2
GB file and my computer is seized by law enforcement. Would I be able to
convince them that the 2GB file is just some bytes dd-ed from
/dev/random instead of an encrypted file or cryptocontainer of some
sort? I wouldn't be able to comply in telling the password because there
is none.

Ozz

[toc] | [prev] | [next] | [standalone]

#32978

On 2015-10-15, wizzofozz <oscxxxxxxxaas@gmail.com> wrote:
> On 15-10-2015 21:04, Chris M. Thomasson wrote:
>>> "Rich"  wrote in message news:mvn0el$nr4$1@dont-email.me...
>> 
>>> https://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-breaking-so-much-crypto/
>
> I've been wondering for some time now what would happen if I dd a bunch
> of random bytes, coming from /dev/random or maybe /dev/urand say, to a 2
> GB file and my computer is seized by law enforcement. Would I be able to
> convince them that the 2GB file is just some bytes dd-ed from
> /dev/random instead of an encrypted file or cryptocontainer of some
> sort? I wouldn't be able to comply in telling the password because there
> is none.

And if it was a 2GB encrypted file, why would you be worried? There is
no law yet in the USA that demands that you had over the key to an
encrypted file.
>
> Ozz
>
>
>
>
>

[toc] | [prev] | [next] | [standalone]

#33017

William Unruh <unruh@invalid.ca> wrote:
> On 2015-10-15, wizzofozz <oscxxxxxxxaas@gmail.com> wrote:
>> On 15-10-2015 21:04, Chris M. Thomasson wrote:
>>>> "Rich"  wrote in message news:mvn0el$nr4$1@dont-email.me...
>>> 
>>>> https://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-breaking-so-much-crypto/
>>
>> I've been wondering for some time now what would happen if I dd a bunch
>> of random bytes, coming from /dev/random or maybe /dev/urand say, to a 2
>> GB file and my computer is seized by law enforcement. Would I be able to
>> convince them that the 2GB file is just some bytes dd-ed from
>> /dev/random instead of an encrypted file or cryptocontainer of some
>> sort? I wouldn't be able to comply in telling the password because there
>> is none.
> 
> And if it was a 2GB encrypted file, why would you be worried? There is no
> law yet in the USA that demands that you had over the key to an encrypted
> file.

You don't need a law. Courts usually have the inherent authority to compel
these things.

The relevant limitation here, in the U.S. at least, would the Fifth
Amendment, which prohibits the government (including, in this case, the
courts) from compelling you to testify against yourself. In one of the early
cases a few years back, however, a federal appellate court decided that
providing a password was not compelled testimony, analogizing it to
providing the key to a lock box, which according to settled law is not
proscribed by the Fifth Amendment even if the contents of the lock box would
incriminate you.

The tide is turning and that decision is probably an outlier, but AFAIK the
question has not reached the Supreme Court.

Regardless, though, the Fifth Amendment prohibition wouldn't apply if you
were given immunity or otherwise not at risk of criminal punishment. So
theoretically you could absolutely be legally jailed indefinitely if a judge
was convinced some random data was an encrypted file and you [seemingly]
refused his order to provide the password.

There are cases where people have been jailed for years for refusing to
provide evidence or obeying some other court order; jailed not as a criminal
punishment but as inducement for obeying the order. In such situations there
would have been no trial, just the belief of a judge based. You also have
little recourse. As long the judge's belief was reasonable no appellate
court would intervene; not at least until you have been sitting in jail for
an unreasonably long time. But _years_ is not on its face unreasonable.

See, e.g., https://en.wikipedia.org/wiki/H._Beatty_Chadwick

Many of the most high-profile cases unsurprisingly involve divorce
proceedings, with one spouse refusing to provide access to off-shore bank
accounts or other investments beyond the power of the court to access
directly. Once a spouse has sat in jail for months or years, you really must
wonder whether somebody could be that spiteful. Note that obeying the order
wouldn't invite criminal punishment, so that's not the reason. Rather, in
such cases the person is either being spiteful, hoping to outlast the
patience of the spouse or court, or simply because the money doesn't
actually exist.

That said, unless the random file just happened to contain the header of a
known encryption format, or if there were evidence of encryption software on
your machine that could produce that file, you probably wouldn't have a
problem. So, you know, don't install TrueCrypt if you don't want to spend
years in jail ;) Especially if you're rich and thinking of divorcing.

[toc] | [prev] | [next] | [standalone]

#32993

On a sunny day (Thu, 15 Oct 2015 22:24:06 +0200) it happened wizzofozz
<oscxxxxxxxaas@gmail.com> wrote in <mvp1t9$loe$1@dont-email.me>:

>On 15-10-2015 21:04, Chris M. Thomasson wrote:
>>> "Rich"  wrote in message news:mvn0el$nr4$1@dont-email.me...
>> 
>>> https://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-breaking-so-much-crypto/
>>>
>> 
>> [...]
>> 
>> A friend of mine advised me to give the NSA a heads up on my cipher just in
>> case it turns out to be "hard to crack". This in turn gave me some
>> interesting
>> nightmares! I told him that I hope its not that hard to bust open, then
>> he said
>> it did not matter because it could turn out to be difficult to crack...
>> 
>
>I don't understand this. Why would you give them a heads up? Currently
>your cipher isn't widely used, I guess, so I'd imagine they wouldn't be
>very interested anyway. Unless it's so strong they want to use it
>themselves. Or maybe use it for their internal weekly friday afternoon
>challenge ;-)
>
>> Should I send them a link to my webpage and clearly state that this is a
>> toy,
>> but here it is just in case?
>
>Maybe you could send them, if anything, your paper. Speaking of, is it
>finished yet ;-)
>
>> Any thoughts?
>
>Yes, but slightly unrelated;
>
>I've been wondering for some time now what would happen if I dd a bunch
>of random bytes, coming from /dev/random or maybe /dev/urand say, to a 2
>GB file and my computer is seized by law enforcement. Would I be able to
>convince them that the 2GB file is just some bytes dd-ed from
>/dev/random instead of an encrypted file or cryptocontainer of some
>sort? I wouldn't be able to comply in telling the password because there
>is none.
>
>Ozz

In a Kafka world there is no way out,
even without that file they will state your typos were deliberate and hold secret info.
And they are right!

[toc] | [prev] | [next] | [standalone]

#32972

Chris M. Thomasson <nospam@nospam.nospam> wrote:
> > "Rich"  wrote in message news:mvn0el$nr4$1@dont-email.me...

> > https://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-breaking-so-much-crypto/

> [...]

> A friend of mine advised me to give the NSA a heads up on my cipher
> just in case it turns out to be "hard to crack". This in turn gave me
> some interesting nightmares! I told him that I hope its not that hard
> to bust open, then he said it did not matter because it could turn
> out to be difficult to crack...

There is no legal requirement for you to do so (to the best of my
knowledge).

Therefore, do not do so.

> Should I send them a link to my webpage and clearly state that this
> is a toy, but here it is just in case?

No.  They probably would not care anyway, but unless there is a legal
requirement to do so, do not do so.

[toc] | [prev] | [next] | [standalone]

#32977

On 2015-10-15, Chris M. Thomasson <nospam@nospam.nospam> wrote:
>> "Rich"  wrote in message news:mvn0el$nr4$1@dont-email.me...
>
>> https://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-breaking-so-much-crypto/
>
> [...]
>
> A friend of mine advised me to give the NSA a heads up on my cipher just in
> case it turns out to be "hard to crack". This in turn gave me some 
> interesting

And why would you need to do that? And do not worry, the chances that it
turns out to be "hard to crack" are less than the chances that you find
a 1Kg nugget of gold in your back lawn.

> nightmares! I told him that I hope its not that hard to bust open, then he 
> said
> it did not matter because it could turn out to be difficult to crack...

There is no law that says "difficult to crack" cyphers must be reported
to NSA.

>
> Should I send them a link to my webpage and clearly state that this is a 
> toy,
> but here it is just in case?
>
> Yikes!

What exactly are you worried about?

>

[toc] | [prev] | [next] | [standalone]

#32981

On 16/10/2015 01:11, William Unruh wrote:
> On 2015-10-15, Chris M. Thomasson <nospam@nospam.nospam> wrote:
>>> "Rich"  wrote in message news:mvn0el$nr4$1@dont-email.me...
>>
>>> https://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-breaking-so-much-crypto/
>>
>> [...]
>>
>> A friend of mine advised me to give the NSA a heads up on my cipher just in
>> case it turns out to be "hard to crack". This in turn gave me some
>> interesting
>
> And why would you need to do that? And do not worry, the chances that it
> turns out to be "hard to crack" are less than the chances that you find
> a 1Kg nugget of gold in your back lawn.
>
>> nightmares! I told him that I hope its not that hard to bust open, then he
>> said
>> it did not matter because it could turn out to be difficult to crack...
>
> There is no law that says "difficult to crack" cyphers must be reported
> to NSA.
>
>>
>> Should I send them a link to my webpage and clearly state that this is a
>> toy,
>> but here it is just in case?
>>
>> Yikes!
>
> What exactly are you worried about?
>
>>

Please refer to the previous thread (from June 2015) titled "Proposed
US ITAR changes would require pre-approval for all types of publication
containing "technical data" "

Enjoy

Jakob
-- 
Jakob Bohm, CIO, Partner, WiseMo A/S.  https://www.wisemo.com
Transformervej 29, 2860 Søborg, Denmark.  Direct +45 31 13 16 10
This public discussion message is non-binding and may contain errors.
WiseMo - Remote Service Management for PCs, Phones and Embedded

[toc] | [prev] | [next] | [standalone]

#32983

Jakob Bohm <jb-usenet@wisemo.com> wrote:
> On 16/10/2015 01:11, William Unruh wrote:
> > On 2015-10-15, Chris M. Thomasson <nospam@nospam.nospam> wrote:
> >>> "Rich"  wrote in message news:mvn0el$nr4$1@dont-email.me...
> >>
> >>> https://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-breaking-so-much-crypto/
> >>
> >> A friend of mine advised me to give the NSA a heads up on my cipher just in
> >> case it turns out to be "hard to crack". This in turn gave me some
> >> interesting
> >
> > And why would you need to do that? And do not worry, the chances that it
> > turns out to be "hard to crack" are less than the chances that you find
> > a 1Kg nugget of gold in your back lawn.
> >
> > What exactly are you worried about?

> Please refer to the previous thread (from June 2015) titled "Proposed
> US ITAR changes would require pre-approval for all types of publication
> containing "technical data" "

The key term above being "proposed".  Worth worrying about, yes, but
the worry would be to prevent "proposed" from becoming "enacted".

Until they are "enacted" he is under no obligation to inform the NSA of
anything.

[toc] | [prev] | [next] | [standalone]

#32988

On 16/10/2015 02:25, Rich wrote:
> Jakob Bohm <jb-usenet@wisemo.com> wrote:
>> On 16/10/2015 01:11, William Unruh wrote:
>>> On 2015-10-15, Chris M. Thomasson <nospam@nospam.nospam> wrote:
>>>>> "Rich"  wrote in message news:mvn0el$nr4$1@dont-email.me...
>>>>
>>>>> https://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-breaking-so-much-crypto/
>>>>
>>>> A friend of mine advised me to give the NSA a heads up on my cipher just in
>>>> case it turns out to be "hard to crack". This in turn gave me some
>>>> interesting
>>>
>>> And why would you need to do that? And do not worry, the chances that it
>>> turns out to be "hard to crack" are less than the chances that you find
>>> a 1Kg nugget of gold in your back lawn.
>>>
>>> What exactly are you worried about?
>
>> Please refer to the previous thread (from June 2015) titled "Proposed
>> US ITAR changes would require pre-approval for all types of publication
>> containing "technical data" "
>
> The key term above being "proposed".  Worth worrying about, yes, but
> the worry would be to prevent "proposed" from becoming "enacted".
>
> Until they are "enacted" he is under no obligation to inform the NSA of
> anything.
>

I was merely referring to the thread as previous discussion on the off
topic discussion if creators of new crypto need to advise the NSA first.

I didn't say I believed anything in this regard.

Now could we please get this thread back to the issue of DH group
parameter reuse.

Enjoy

Jakob
-- 
Jakob Bohm, CIO, Partner, WiseMo A/S.  https://www.wisemo.com
Transformervej 29, 2860 Søborg, Denmark.  Direct +45 31 13 16 10
This public discussion message is non-binding and may contain errors.
WiseMo - Remote Service Management for PCs, Phones and Embedded

[toc] | [prev] | [next] | [standalone]

#32997

On 2015-10-15 01:44:53 +0000, Rich said:

> https://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-breaking-so-much-crypto/ 
> 

The guts of this, if my skim of the presented paper is correct, is
that it is possible to perform a lot of precomputation on a DH group
in absence of data from any particular A and B from a particular use.

With this precomputation, attacks on a particular session become
easier.

Leaving aside the downgrade attacks (tricking TLS/SSL sessions to use
weaker ciphers/parameters than they would normally negotiate), I've
got a couple of questions.

1. Does this apply to elliptic curves as as well?

That is, is there precomputation that can be done on an EC group that
will make breaking any particular use of that group easier?

2. Are there good tools for generating safe primes that are available
   to developers?

That is, there is an advantage to using unpopular groups. But most
software developers will pick a group and parameters out of some
standards document. If software developers using DH want to create
new groups, how can we help them to not make bad choices of primes.

2a. Analogue of question 2 but for ECC parameters?

I am assuming that we don't need unique or unpopular curves. As long
as we stick to good curves, the analogue of (2) is to pick the right
modulus. Is this correct? And are developers going to shoot
themselves in the foot by doing so.


Cheers,

-j

[toc] | [prev] | [next] | [standalone]

#33003

Jeffrey Goldberg <nobody@goldmark.org> wrote:
> On 2015-10-15 01:44:53 +0000, Rich said:

> > https://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-breaking-so-much-crypto/ 
> > 

> The guts of this, if my skim of the presented paper is correct, is
> that it is possible to perform a lot of precomputation on a DH group
> in absence of data from any particular A and B from a particular use.

> With this precomputation, attacks on a particular session become
> easier.

My take from reading through the paper is that they are (warning, loose
analagy here) building something similar to rainbow tables, only for DH
groups.  Converting what would othewise be an infeasable computation
time wise into one that can be performed on a useful timescale.

And that this ability to "rainbow table" the DH groups is made much
easier by the number of different software packages that all use the
same group (or a small collection of the same set of groups).

> Leaving aside the downgrade attacks (tricking TLS/SSL sessions to use
> weaker ciphers/parameters than they would normally negotiate), I've
> got a couple of questions.

> 1. Does this apply to elliptic curves as as well?

> That is, is there precomputation that can be done on an EC group that
> will make breaking any particular use of that group easier?

There was a small reference in the paper that one 'foil' for this
attack would be to move to EC's.  However, if we end up with almost
every implimentation using the same curve, there still might be a
similarly feasable attack in the future for EC's as well.

> 2. Are there good tools for generating safe primes that are available
>    to developers?

> That is, there is an advantage to using unpopular groups. But most
> software developers will pick a group and parameters out of some
> standards document. If software developers using DH want to create
> new groups, how can we help them to not make bad choices of primes.

There was a tiny bit of info in the paper about this, and my takeaway
was that it was computationally difficult to verify that one did not
pick a bad prime, which is why most implimentations ended up using the
same one, or small set.  So they imply that simply 'picking your own'
is not a reasonable solution (certianly not when one means picking a
new good one with each connect, which would foil this attack).

> 2a. Analogue of question 2 but for ECC parameters?

> I am assuming that we don't need unique or unpopular curves. As long
> as we stick to good curves, the analogue of (2) is to pick the right
> modulus. Is this correct? And are developers going to shoot
> themselves in the foot by doing so.

My knowledge of EC's does not qualify as good enough to answer this
question.

[toc] | [prev] | [next] | [standalone]

#33018

Rich <rich@example.invalid> wrote:
> Jeffrey Goldberg <nobody@goldmark.org> wrote:
<snip>
>> 2. Are there good tools for generating safe primes that are available
>>    to developers?
> 
>> That is, there is an advantage to using unpopular groups. But most
>> software developers will pick a group and parameters out of some
>> standards document. If software developers using DH want to create
>> new groups, how can we help them to not make bad choices of primes.
> 
> There was a tiny bit of info in the paper about this, and my takeaway
> was that it was computationally difficult to verify that one did not
> pick a bad prime, which is why most implimentations ended up using the
> same one, or small set.  So they imply that simply 'picking your own'
> is not a reasonable solution (certianly not when one means picking a
> new good one with each connect, which would foil this attack).

My understanding it that _used_ to be the case 10 or 15 years. Back then
there was more uncertainty about safe primes. And, indeed, computers were
much slower. These days it makes eminent sense to generate your own DH
parameters. It's not even that difficult using, e.g., OpenSSL. It only takes
a few seconds or minutes.

I started avoiding common DH parameters and began generating random
parameters years ago for software and services I implement. I'm not a
cryptographer, but even I could read the writing on the wall.

One of the reasons SSL has been falling apart is because many of the
assumptions and best practives at the time of its creation--regarding cipher
agility, security of CBC, DH groups, etc--have been upended. I'm not saying
there weren't poor decisions originally. But I started reading this group
around 2000, and times sure have changed. The advice cryptographers gave
back then in many ways contradicts the advice given today. In some cases
(e.g. cipher agility, DH groups) best practice was overly cautious. In other
cases (e.g. CBC) best practice was insufficiently cautious. Notably, in 2000
this group saw more participation by practicing cryptographers--the ratio of
experts to idiots like myself was better.

Another concrete example, regarding DES:

	https://lwn.net/Articles/660486/

[toc] | [prev] | [next] | [standalone]

#33005

On 16/10/2015 18:53, Jeffrey Goldberg wrote:
> On 2015-10-15 01:44:53 +0000, Rich said:
>
>> https://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-breaking-so-much-crypto/
>>
>
> The guts of this, if my skim of the presented paper is correct, is
> that it is possible to perform a lot of precomputation on a DH group
> in absence of data from any particular A and B from a particular use.
>
> With this precomputation, attacks on a particular session become
> easier.
>
> Leaving aside the downgrade attacks (tricking TLS/SSL sessions to use
> weaker ciphers/parameters than they would normally negotiate), I've
> got a couple of questions.
>
> 1. Does this apply to elliptic curves as as well?
>
> That is, is there precomputation that can be done on an EC group that
> will make breaking any particular use of that group easier?
>
> 2. Are there good tools for generating safe primes that are available
>    to developers?
>
> That is, there is an advantage to using unpopular groups. But most
> software developers will pick a group and parameters out of some
> standards document. If software developers using DH want to create
> new groups, how can we help them to not make bad choices of primes.
>

For this one there is the ANSI X9.42 standard and its slightly
different NIST cousin (in a NIST SP, I think).  Both of these specify,
in a way directly implementable by code:

1. Start with a non-secret "seed", about the size of the desired
symmetric-equivalent strength (e.g. 128, 192 or 256 bits).

2. A specific way to use a single hash algorithm (X.9.42 specifies
SHA-1 always, the NIST cousin specifies to use the same hash algorithm
used to postprocess the raw DH shared secret after the exchange) to
generate an indexed series of candidate numbers based on the seed, but
in such a way that it is cryptographically hard to deliberately choose
a seed leading to dangerous candidate numbers.

3. Specific requirements as to the level of primality testing to be
done to candidate numbers.

4. A specific order in which candidate numbers should be used, combined
and tested.

5. A rule to stop and use *exactly* the first set of candidate numbers
(for a given seed) that pass all criteria.

6. A well defined way to compactly specify the seed and candidate
indices that lead to the chosen group parameter.

7. A requirement that trusting participants should verify that the seed
and indices match the claimed group parameters.

8. A requirement that trusting participants should repeat the primality
testing on the presented numbers (Which can be received explicitly or 
quickly reconstructed from the seed and indices).

9. A requirement that trusting participant implementations shall have
the ability to rerun the search (in any order) to confirm that the
presented group parameters were indeed the first result according to
rule 5.

10. Rules about encoding, byte order etc.  Including specific rules for
how to use this with classic DH and MQV schemes.

When following this standard, avoiding "overly popular" group
parameters is simply a matter of regularly changing the value of "seed".

For instance in a setup used only by participants in sci.crypt
discussions we could form NUMS (Nothing-Up-My-Sleeve) seed values by
hashing the string "sci.crypt" and a representation of part of the
calendar date.  All participants would then know the next seed in
advance and have plenty of time to run the parameter generation
algorithm (10s to 5 minutes on a typical PC) before new group
parameters take effect, yet each set of group parameters (prime,
subgroup and generator) would be used only for a relatively small
number of exchanges, making it economically infeasible to do the
massive precomputation attack supposed in the OP research paper.


Similarly, a web site could use seeds based on its site or company
name, plus a time varying part that limits how long each set of group
parameters are used.


A completely different approach is to simply use a random group
parameter generator, such as the command line tool "openssl dhparam" .


> 2a. Analogue of question 2 but for ECC parameters?
>
> I am assuming that we don't need unique or unpopular curves. As long
> as we stick to good curves, the analogue of (2) is to pick the right
> modulus. Is this correct? And are developers going to shoot
> themselves in the foot by doing so.
>

This depends a lot on the details of the answers to your question #1.


Enjoy

Jakob
-- 
Jakob Bohm, CIO, Partner, WiseMo A/S.  https://www.wisemo.com
Transformervej 29, 2860 Søborg, Denmark.  Direct +45 31 13 16 10
This public discussion message is non-binding and may contain errors.
WiseMo - Remote Service Management for PCs, Phones and Embedded

[toc] | [prev] | [next] | [standalone]

#33011

Jeffrey Goldberg  <jeffrey+news@goldmark.org> wrote:
>On 2015-10-15 01:44:53 +0000, Rich said:
>
>> https://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-breaking-so-much-crypto/ 
>> 
>
>The guts of this, if my skim of the presented paper is correct, is
>that it is possible to perform a lot of precomputation on a DH group
>in absence of data from any particular A and B from a particular use.

It turns out that the number field sieve can be done as a three-part
computation. First, there is a huge amount of work to generate relations
between small primes (and some similar things) in an algebraic structure
related to the finite field you are in (the prime you use). Next, there
is a huge amount of linear algebra to do in order to compute the discrete
logarithms of all these small primes. Finally, there's a relatively small
amount of work to do to find one relation between the element you are
interested in and all those small primes. Once you have that relation,
computing the discrete logarithm is trivial.

It turns out that almost all of the work lies in the first two parts,
and those parts depend only on which field you are in, not on which
element you want to compute the discrete logarithm of.

Which means that if lots of people are using the same finite field,
computing many d.log.s in that field is not that much more expensive
than computing one d.log.

Which means, if you choose your field to be big enough to resist a
well-resourced attacker, you are ok.

Choose big enough primes.

>1. Does this apply to elliptic curves as as well?
>
>That is, is there precomputation that can be done on an EC group that
>will make breaking any particular use of that group easier?

Well, most algorithms have different optimum parameters when you
are computing many d.log.s than when you are computing just one, and
typically, this reduces the per-logarithm cost. But nothing as drastic
as the number field sieve.

Choose a big enough curve.

>2. Are there good tools for generating safe primes that are available
>   to developers?

The problem isn't bad primes. It is too small primes. Choose bigger
primes. Problem solved.

>2a. Analogue of question 2 but for ECC parameters?

Again, choose big enough curves.

While many people still use 1024 bit fields, I believe few people
are using less than a 224 bit curve, which is equivalent to 2048 bit
fields. I believe most people use a 256 bit curve, which is equivalent
to 3000 bit fields.

Choose a big enough curve.

-- 
kg

[toc] | [prev] | [next] | [standalone]

#33019

On 2015-10-16 20:59:58 +0000, kg said:

> Jeffrey Goldberg  <jeffrey+news@goldmark.org> wrote:
> 
> Which means, if you choose your field to be big enough to resist a
> well-resourced attacker, you are ok.
> 
> Choose big enough primes.

Yep. I do get that.

All of the discussion of "fixes" in the paper were, "use a
bigger group, but if for some reaons you have to use
a 1024 modulus, ..."

>> 1. Does this apply to elliptic curves as as well?
> 
> Well, most algorithms have different optimum parameters when you
> are computing many d.log.s than when you are computing just one, and
> typically, this reduces the per-logarithm cost. But nothing as drastic
> as the number field sieve.

Thanks. This feels counter intuitive to me, but that just illustrates
that I don't have good intuitions about attacks on DH that don't
generally apply to d.logs.

> Choose a big enough curve.

Yeah. I do get that. I was mostly asking to help spur me on to
a better understanding of that some of the attacks on DH
are specific to integer fields.
> 
>> 2. Are there good tools for generating safe primes that are available
>> to developers?
> 
> The problem isn't bad primes. It is too small primes.

I wasn't suggesting that the attacks involve bad primes. Instead
it is that not just any prime (of sufficient size) will do for
a DH group. We want a "safe prime". And so I was asking about
tools for generating a safe prime.

> Choose bigger primes. Problem solved.

I think I am begining to detect a pattern here.

>> 2a. Analogue of question 2 but for ECC parameters?
> 
> Again, choose big enough curves.

Yes. Definitely a hint of a pattern.

> While many people still use 1024 bit fields,

Yes. This is a sad fact.

> I believe few people
> re using less than a 224 bit curve, which is equivalent to 2048 bit
> fields. I believe most people use a 256 bit curve, which is equivalent
> to 3000 bit fields.

Thanks.


So one last question. Is there some simple thing I can do to
avoid the sorts of attacks described in the paper?

> Choose a big enough curve [or primes].

There we go!

Cheers,

-j

[toc] | [prev] | [next] | [standalone]

#33036

Jeffrey Goldberg  <jeffrey+news@goldmark.org> wrote:
>I was mostly asking to help spur me on to
>a better understanding of that some of the attacks on DH
>are specific to integer fields.

So here's the basic idea of index calculus explained very briefly.

You want to compute the logarithm of x to the base g. Suppose for
simplicity that g has prime order n. If you have an equation

	x^u g^v = 1,

then the logarithm of x is simply v/u modulo n. (Simple exponent
arithmetic.)

What if you have two equations of the form

	x^u y^v g^w = 1		and	x^a y^b g^c = 1

for some y. Then we can multiply exponents by 1/v and 1/b to get two
equations

	x^(u') y g^(w') = 1	and	x^(a') y g^(b') = 1 .

Dividing by the second equation, the first equation becomes

	x^(u'-a') g^(w'-b') = 1,

which will give us the logarithm of x as above. And then we can find
the logarithm of y, too. Notice that if we write s for the logarithm of
x and t for the logarithm of y, we could rewrite these equations as

	us + vt + w = 0 (mod n)
	as + vb + c = 0 (mod n)

What we did was essentially linear algebra, solving for unknowns s and t.

What happens if you have L+1 equations of the form

	x^(u_i) g^(w_i) y_1^(v_i1) ... y_L^(v_iL) = 1

for some y_1, ..., y_L? Go ahead and do linear algebra, solve for the
unknown discrete logarithms.

What happens if you have L equations of the form

	g^(w_i) y_1^(v_i1) ... y_L^(v_iL) = 1

and one equation of the form

	x^a g^b y_1^(c_1) ... y_L^(c_L) = 1 ?

One thing you could do is use the first L equations to solve for the
logarithms of y_1, ..., y_L. And then you can insert into the final
equation to get the logarithm of x, as above.

What happens if you have L equations of the form

	g^(w_i) y_1^(v_i1) ... y_L^(v_iL) = 1

and k equations of the form

	x_i^(a_i) g^(b_i) y_1^(c_i1) ... y^(c_iL) = 1 ?

Again, use the first L equations to solve for the logarithms of y_1, ...,
y_L. And then insert into the k final equations to get the logarithms
of x_1, x_2, ..., x_k.

What happens if you don't know all of the x_i at the beginning? Well,
you can still compute the logarithms of y_1, ..., y_L. And then solve
for x_i as they become known.

In other words, if you want to compute k logarithms, you need to first
find L equations of the first type, solve the corresponding system of
L linear equations and then for each x_i find an equation of the second
type and solve the corresponding trivial linear equation.

It splits kind of nicely into a large precomputation and a much smaller
per-logarithm computation.

If you are wondering how to find equations like this, the simplest (and
slowest) way is to choose random w_i, a_i and b_i and see if the result
factors as a product of small primes (that is, y_1, ..., y_L are the L
smallest primes). There are much better methods involving number fields
and sieving.

I've skipped a number of minor details, by the way.

-- 
kg

[toc] | [prev] | [next] | [standalone]

#33055

On 2015-10-18 11:37:23 +0000, kg said:

> Jeffrey Goldberg  <jeffrey+news@goldmark.org> wrote:
>> I was mostly asking to help spur me on to
>> a better understanding of that some of the attacks on DH
>> are specific to integer fields.
> 
> So here's the basic idea of index calculus explained very briefly.

[big snip]

Excellent! Thank you.

I've got a question forming in my head, but I'm going to try to
play with it first to see if I can formulate it more clearly
(and whether my attempt to clarify it provides me with the answer).

Cheers,

-j
> 

[toc] | [prev] | [next] | [standalone]

#33052

In article <mvn0el$nr4$1@dont-email.me>
Rich <rich@example.invalid> wrote:
>
>
> https://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-breaking-so-much-crypto/
>
> Small quote from the URL above:
>
>     "There have been rumors for years that the NSA can decrypt a
>     significant fraction of encrypted Internet traffic. In 2012, James
>     Bamford published an article quoting anonymous former NSA officials
>     stating that the agency had achieved a \u201ccomputing
>     breakthrough\u201d that gave them \u201cthe ability to crack
>     current public encryption.\u201d The Snowden documents also hint at
>     some extraordinary capabilities: they show that NSA has built
>     extensive infrastructure to intercept and decrypt VPN traffic and
>     suggest that the agency can decrypt at least some HTTPS and SSH
>     connections on demand.
>
>     However, the documents do not explain how these breakthroughs work,
>     and speculation about possible backdoors or broken algorithms has
>     been rampant in the technical community. Yesterday at ACM CCS, one
>     of the leading security research venues, we and twelve coauthors
>     presented a paper that we think solves this technical mystery.
>
>     The key is, somewhat ironically, Diffie-Hellman key exchange, an
>     algorithm that we and many others have advocated as a defense
>     against mass surveillance. Diffie-Hellman is a cornerstone of
>     modern cryptography used for VPNs, HTTPS websites, email, and many
>     other protocols. Our paper shows that, through a confluence of
>     number theory and bad implementation choices, many real-world users
>     of Diffie-Hellman are likely vulnerable to state-level attackers.

I've read this entire thread so far. Does all of this relate to 
gpg? And what about Tor?

Can the NSA, and I assume any other big state actor, have a really 
good chance now of decrypting anything encrypted in gpg? Can they 
now find people who are using Tor?

I'm getting [more] paranoid.

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | sci.crypt

csiph-web