Re: [TLS] draft-dkg-tls-reject-static-dh

[Nico Williams <[e-mail]>]

On Fri, Dec 07, 2018 at 03:37:25AM +0300, Daniel Kahn Gillmor wrote:
> On Wed 2018-12-05 18:59:07 +0000, Stephen Farrell wrote:
> > it's feasible and not easily defeated.
> 
> TLS endpoints can share their data (key material, cleartext, etc) with
> whoever they choose -- that's just how the universe is implemented.
> They can even do it out of band, on a channel that the peer has no
> knowledge of.
> 
> The question for TLS implementers is what to do about risks or leakage
> that they *can* become aware of.

Sure.

> > It'd be good to describe in detail a way in which one might
> > efficiently retain the client state required, e.g. via a bloom filter
> > maybe?  (Assuming an occasional false positive isn't too alarming;-)
> 
> Yes, that would be great.  the way i was going to write it that guidance
> was pretty dumb (i was thinking of just a hashtable combined with a
> fixed-size ring buffer to be constant-space and roughly constant-time,
> and hadn't even considered bloom filters), so i welcome suggested text.

False negatives are OK here.  False positives... depends on whether the
application / library can reconnect and retry.  (I doubt we'd add a TLS
extension by which the client can ask to retry with a fresher server eDH
key...)

When false positives are not OK a Bloom filter check prior to doing a
slower check that has no false positives is a good optimization.  But
let's assume the client can reconnect and retry, no?  If not then just
write all the eDH keys seen to a circular log and on Bloom filter
positive just do a linear search on the log.

Another possibility is to not fail on false positive but to mark a
server as "needs watching like a hawk" and use a more appropriate data
structure (w/o false positives) to watch it for a while.  When you catch
a server cheating with that data structure, then fail hard.

> Given that the size of the set of elements to include is effectively
> infinite, standard Bloom filters seem likely to be trouble (way too fast
> to converge onto false-positives).
> 
> Perhaps "stable bloom filters" would represent a better tradeoff:
> 
>   http://webdocs.cs.ualberta.ca/~drafiei/papers/DupDet06Sigmod.pdf

Nifty.

Another option is Scalable Bloom Filters.  Basically, when a filter gets
full-ish, you close it to additions and add a new filter, thenceforth
checking all the closed filters and the one open filter.  Delete filters
older than some number of days, and you limit storage use.

Looks like both Scalable and Stable BFs would fit the bill in terms of
limiting storage use and false positive rate.

> But hm, even a 0.1% false positive rate sounds pretty alarming too.  1
> in a thousand connections failing?  yikes!  I think we'd want to err on
> the false-negative side for this particular use case.

Depends on whether the client can retry, or whether you can do something
other than fail (see above).

> > It might also be good to outline how a survey or CT-like mechanism
> > (say logging some value as a witness for the DH public) could be used
> > to detect this kind of badness even if common TLS clients didn't
> > deploy.
> 
> oof, CT itself is *really* heavyweight, and given our overall failure to
> get any sort of monitoring that would detect abuse by the CT logs
> themselves working (gossip hasn't had the necessary traction), i'm not
> sure i have the stamina to go down that route for ephemeral DH values.

+1

> > Section 4 could probably do with some text about how not to do this,
> > e.g. keeping a list of {servername,[DH values]} would be bad if a
> > client's disk were compromised.
> 
> right, this would align with the bloom filter (or whatever)
> implementation guidance you mention above.  I've been thinking about
> this, and i'm not sure that we even need servername as part of the key.
> is there any reason that a client should ephemeral DH reuse *across*
> hosts?  If anything, ephemeral DH reuse across hosts *proves* that a DH
> secret has been shared (wittingly or unwittingly), which is one of the
> things we're trying to avoid, right?  Simpler implementations are
> probably better, and it's certainly easier to not deal with the
> servername.

You're right, the server name isn't needed.  In principle eDH keys
should be large enough and all randomly generated.  The chances of reuse
anywhere, ever, should be very small.

This would help detect RNGs with shared seeds.  Remember the bad RNG in
OpenSSL in Debian, about a decade ago?  Yeah, let's not have that happen
again.

Nico
--