Subject: [keyassure] Efficient Mega-Queries

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 23 Dec 2010 14:02:15 +0000

One of the points Adam Langley keeps bringing up is his desire to perform
all lookups in as few round trips as possible. After thinking about the
problem, I now have a scheme that allows a complete extended discovery query
to be performed with only 1 DNS round trip occurring in the critical path.

While I am presenting this in terms of my own Extended Service Discovery
Scheme, the same approach could be applied to other schemes. So think of
this as a demonstration of an approach rather than an insistence on a
particular scheme.

In the current version of ESRV, we may require up to 3 round trips and 6
different RRSIGs to complete resolution:

ESRV ("www.example.com", "_http._tcp")

(1)
www.example.com ? RR-A
    www.example.com CNAME example.com
    www.example.com RRSIG (CNAME)
    example.com RR-A disc srv
    example.com RRSIG (RR-A)

(2)
_http._tcp.example.com ? RR-B
    _http._tcp.example.com RR-B tls "required"
    _http._tcp.example.com RRSIG (RR-B)
_http._tcp.example.com ? SRV
    _http._tcp.example.com SRV 1 1 443 host1.example.com
    _http._tcp.example.com SRV 1 1 443 host2.example.com
    _http._tcp.example.com RRSIG (SRV)

(3)
_http._tcp.host1.example.com ? RR-B
    _http._tcp.host1.example.com RR-B eekey ......
    _http._tcp.host1.example.com RRSIG (RR-B)
_http._tcp.host1.example.com ? A
    _http._tcp.host1.example.com A 10.1.1.2
    _http._tcp.host1.example.com RRSIG (A)

Using RSA 2048 the 6 RRSIG records alone add up to 1.5 Kb

But the actual data is considerably more modest. It is 7 RRs with typically
32 bytes of data. Only one of them is substantial - 80 bytes for the SHA-256
digest of the end entity key.

So we can fit all the data for the typical extended discovery case in about
300 bytes or so. The problem is the signatures.

Now imagine that we separate out delivery of the signature from delivery of
the data. So the DNS server will respond to a mega-query with the extended
discovery data and as many RRSIGs as it can fit, but no problem if they
don't all fit.

The client can start acting on the extended discovery data as soon as it is
available and start queries for the next round in parallel. Starting the
TCP/IP connection will itself take several round trips. So we should have
all the necessary information returned from DNS before we begin the TLS
connection initiation.

But in the worst case, we don't need to worry about the security of the
potential connection until we have reached the point where we start sending
data down it. If we discover that there is a problem we can (and SHOULD)
abort.

So the critical path of our connection establishment process now looks like

SEQUENTIAL
   PARALLEL
      DNS ! A (www.example.com)
      DNS ! ESRV-MEGA (www.example.com, _http._tcp)
   PARALLEL
      DNS ? A
      DNS ? ESRV-MEGA
   PARALLEL
      SEQUENTIAL
         ... build TCP socket according to indicated policy ...
      SEQUENTIAL
         PARALLEL
            SEQUENTIAL
               DNS ! ESRV (example.com)
               DNS ? ESRV (example.com)
            SEQUENTIAL
               DNS ! SRV (_http._tcp.example.com)
               ...
            ... other DNS queries
         ... check signatures
    IF
       ... policy or signature violation detected ...
          ... abort connection ...

Performance wise we have two cases of interest:

1) Server does not use extended discovery
     In this case we have to wait for a response to two DNS queries to
arrive instead of just one. But these queries are taking place in parallel.

2) Server uses the most extended discovery possible and supports mega-query
    In this case the public key operations take place in parallel with the
communications. Even if we are performing full end-client validation there
should be negligible impact on performance.

In either case there is only one DNS round trip in the critical path and
only 2 DNS round trips in total.

The other cases of interest are:

3) Server uses extended discovery but their DNS does not support mega-query.
    Well, they don't seem to care about performance, it should not be an
overriding concern for the client.

4) Server uses extended discovery but tunes response so that time sensitive
cases can be delat with in a single request-response.

5) Resolver strips out the unsigned responses
    At present the precise behavior of validating resolvers is not fully
defined. But a MegaQuery response can still return all the information that
the client requires to begin a TCP/IP connection including necessary
signatures (CNAME, SRV, A) and the remaining information can be acquired in
a single additional round trip.

Notes:

1) I left out IPv6 lookup from these examples on purpose. This is because
Extended discovery is a very big hammer that can be used to make the IPv6
transition work a lot better. Rather than blindly querying for A and AAAA
records, I would let the service direct which was appropriate. So if someone
is behind a NAT for IPv4 but has direct access for IPv6, they can
preferentially request IPv6 access.

2) I use SRV as an example of the discovery mechanism, but we can go beyond
that approach and use geo-location sensitive discovery and other
optimization techniques.

Conclusion:

Extended discovery mechanisms can be implemented in ways that offer
equivalent performance to existing methods.

-- 
Website: http://hallambaker.com/

---

From: Adam Langley <[email-masked]>
Date: Thu, 23 Dec 2010 09:49:15 -0500

> equivalent performance to existing methods.

There are a couple of assumptions that I would like to question here.

1) That doing two DNS lookups (to the same zone) in parallel costs the
same as doing a single lookup.

Firstly, ignoring caching, we can assume that the zone's nameserver is
50ms away and that the host resolver's timeout (over which we
typically have no control) is 3 seconds. Therefore the time taken to
do a single lookup is:

50ms + p*(3000ms + 50ms)  (where p is the packet loss rate)

Over the public Internet, p = 1% isn't too far off, giving a total
time of 80.5ms. (The effect of double packet loss is so small that we
can ignore it.)

Now, for two concurrent lookups, the time taken is

50ms + (1-(1-p)^2)*(3000 + 50) = 110.7ms  (again, ignoring double loss)

There are a couple of assumptions in there which can be called into
question. I've assumed that packet loss is i.i.d, although sometimes
it certainly isn't depending on the type of competing network traffic
and the queue management of the bottleneck router. If loss is
correlated in time then the concurrent requests look *better*. On the
otherhand, it's misleading to suggest that the average DNS query time
is what we should be measuring. The tail is important too and, in the
above model, the tail ends up nearly twice as fat.

Concurrent requests might have unintended consequences if we consider
caching. Since each different RR type will have its own signature, we
are increasing the pressure on the cache. This might cause the general
hit-rate to drop affecting everybody.

2) That we can overlap TCP socket creation and the TLS handshake with
DNS requests.

Currently Chrome is already capable of 0-RTT TLS handshakes. If we had
the server's public key in place at the start of the connection, we
could use it.

Also, in the lab, Chrome is capable of sending a single TCP SYN +
payload packet and, with it, setting up the TCP connection, TLS
connection and delivering application data. It would be nice not to
preclude these possibilities. Although, they are based on cached
information from the server so it may be reasonable to assume that the
client could also cache any needed DNS information.

Cheers

AGL

-- 
Adam Langley [email-masked] http://www.imperialviolet.org