Subject: Re: [dns-privacy] Eric Rescorla's Discuss on draft-ietf-dprive-padding-policy-05: (with DISCUSS and COMMENT)

From: Alexander Mayrhofer <[email-masked]>
Date: Wed, 18 Jul 2018 16:43:07 +0200

Eric,

thanks for your review. Responses inline:

On Tue, Jun 19, 2018 at 12:00 AM, Eric Rescorla <[email-masked]> wrote:
> Eric Rescorla has entered the following ballot position for
> draft-ietf-dprive-padding-policy-05: Discuss
>
> ----------------------------------------------------------------------
> DISCUSS:
> ----------------------------------------------------------------------
>
> I am marking this DISCUSS because it appears to endorse Random
> padding, which is known to be an unsafe practice.
>
> DETAIL
> S 4.2.2.
>>      Disadvantage: This policy requires a good source of (pseudo) random
>>      numbers which can keep up with the required message rates.
>>      Especially on busy servers, this may be a hindrance.
>>
>>      According to the limited empirical data available, Random Length
>>      Padding performs slightly worse than Block Length Padding.
>
> Random padding allows an attacker who can observe a large number of
> requests to infer the length of the original value by observing the
> distribution of total lengths.

I will include your text in the description of this policy, and based
on your reasoning, change the recommendation into NOT RECOMMENDED.
Furthermore, i have recevied multiple comments that aquiring (pseudo)
random numbers is not a practical problem anymore, so i will amend
that as well. Text proposed for -06:

4.2.2.  Random Length Padding

   When using Random Length Padding, a sender pads each message with a
   random amount of padding.  Due to the size of the EDNS(0) Padding
   Option itself, each message size is hence increased by at least 4
   octets.  The upper limit for padding is the maximum message size.
   However, a client or server may choose to impose a lower maximum
   padding length.

   Options: Maximum and minimum padding length.

   Advantages: Theoretically, this policy should create a natural
   "distribution" of message sizes.

   Disadvantage: This policy requires a good source of (pseudo) random
   numbers which can keep up with the required message rates.  More
   importantly, Random Length padding allows an attacker who can observe
   a large number of requests to infer the length of the original value
   by observing the distribution of total lengths.

   According to the limited empirical data available, Random Length
   Padding performs slightly worse than Block Length Padding.  Due to
   that, and the risk outlined above, Random Length Padding is NOT
   RECOMMENDED.

Would that address your DISCUSS?

> ----------------------------------------------------------------------
> COMMENT:
> ----------------------------------------------------------------------
>
> S 4.1.
>>      consider that even the zero-length EDNS(0) Padding Option increases
>>      the length of the packet by 4 octets.
>>
>>      Options: Block Length - values between 16 and 128 octets for the
>>      queries seem reasonable, responses will require larger block sizes
>>      (see [dkg-padding-ndss] and above for a discussion).
>
> Above, you have SHOULD 128 which is very different from 16 bytes. Why
> would I ever pad to 16 bytes?

The 16 to 128 bytes stem from early discussions around "guts feeling"
of what would be sensible. Queries are mostly <100 bytes in length, so
padding to 16 byte block lengths does reduce entropy from query
lengths quite a bit.

We've heard from Android folks that they're concerned about bandwidth
usage ("every byte counts"), so based on the recommendation we gave
they did not consider padding for the upcoming introduction of
TLS-DNS. imho, padding to 16 byte boundaries on the query is still
better than not padding at all.

I do agree that language like "seems reasonable" is not what we want
to see in a standards track document - but that's one of the reasons
why the document is Experimental..

Do you have a suggestion how to change that?

> S 4.1.
>>      (see [dkg-padding-ndss] and above for a discussion).
>>
>>      Very large block lengths will have confidentiality properties similar
>>      to the "Maximal Length Padding" strategy (Section 4.2.1), since
>>      almost all messages will fit into a single block.  In that case,
>>      reasonable values may be 288 bytes for the query (the maximum size of
>
> Reasonable values of what? "block size"? You say above that up to 128
> is reasonable which implies that 288 is unreasonable

I will change that text to

Such "very large block length" values
may be 288 bytes for the query (the maximum size of a one-question
query over TCP, without any EDNS(0) options), and the EDNS(0) buffer
size of the server for the responses.

(removing "reasonable").

Does that address your concern?

> S 4.1.
>>
>>      Disadvantage: Given an unpadded message and the block size of the
>>      padding (which is assumed to be public knowledge once a server is
>>      reachable), the size of a padded message can be predicted.
>>      Therefore, minimum and maximum length of the unpadded message are
>>      known.
>
> Isn't maximum always known, because it has to fit within the message.

Right. Thanks for spotting that. I've removed "maximum" from that
sentence, changed it to:

Therefore, the minimum length of the unpadded message can be infered

> S 4.2.1.
>>      the server.  Depending on the negotiated size, this strategy will
>>      commonly exceed the MTU, and then result in a consistent number of
>>      fragments reducing delivery probability when datagram based transport
>>      (such as UDP) is used.
>>
>>      Maximal Length Padding is NOT RECOMMENDED.
>
> If this is "sensible:, why is it not recommended?

Two options:

- I can either change to "Due to resource consumption, Maximal Length
Padding is NOT RECOMMENDED"
- or remove "sensible" from the section title.

Personally, i prefer the first option, as the section title in the
Appendix is "non-Sensible..." (There's a bit of history behind that,
originally all policies were in one section, and the split was done to
address a concern that those non-sensible strategies are not seperated
well enough from the sensible ones..)

> S 4.2.2.
>>      Advantages: Theoretically, this policy should create a natural
>>      "distribution" of message sizes.
>>
>>      Disadvantage: This policy requires a good source of (pseudo) random
>>      numbers which can keep up with the required message rates.
>>      Especially on busy servers, this may be a hindrance.
>
> This does not seem like a real issue. By assumption, you are operating
> over TLS, in which case you have a secret which you can use to drive
> your PRNG. That should be rather faster than running the crypto for
> TLS.

As outlined above, i have removed the second sentence.

> S 4.2.3.
>>
>>      Disadvantage: Requires more implementation effort compared to simple
>>      Block Length Padding
>>
>>      Random Block Length Padding (as other combinations of padding
>>      strategies) requires further empirical study.
>
> This does not seem like it is a good strategy. The only advantage
> seems to be not requiring as much randomness, but as above, this is
> not a real issue.

The idea was as this requires further empirical study, we would not
include a recommendation (as in "we don't know enough yet"). The
reason that strategy is included in the document is that it was
brought up as a possible option.

Tim said he would talk to you about the DISCUSS - please let me know
if the above proposals address your DISCUSS and COMMENTS. I would post
an updated version once i've heard back.

best,
Alex

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 18 Jul 2018 07:48:52 -0700

> Would that address your DISCUSS?

Yes, but the pseudo-random text still seems to be there.

> Do you have a suggestion how to change that?

Well, I'm more concerned about "seems reasonable" but you're recommending
something else at the SHOULD level. I don't have proposed text, though.

> Does that address your concern?

Yes. Should this be "MAY"?

> well enough from the sensible ones..)

I guess my question is: "why isn't this in non-sensible" if it's NOT
RECOMMENDED.

> As outlined above, i have removed the second sentence.

There still seem to be some vestiges.

> brought up as a possible option.

I think I would just say it's not as good.

> Tim said he would talk to you about the DISCUSS

That did not happen. However, as noted above, we are good.

-Ekr

please let me know

---

From: Alexander Mayrhofer <[email-masked]>
Date: Wed, 18 Jul 2018 17:18:09 +0200

> Yes, but the pseudo-random text still seems to be there.

Understood - i'm proposing to change the section to the following:

   Disadvantage: Random Length padding allows an attacker who can
   observe a large number of requests to infer the length of the
   original value by observing the distribution of total lengths.

   According to the limited empirical data available, Random Length
   Padding exposes slightly more entropy to an attacker than Block
   Length Padding.  Due to that, and the risk outlined above, Random
   Length Padding is NOT RECOMMENDED.

>> >>      (see [dkg-padding-ndss] and above for a discussion).

[...]

> something else at the SHOULD level. I don't have proposed text, though.

I'll change it to "were discussed before empiric research was
performed"? That's a 100% neutral reflection of what happened.

> Yes. Should this be "MAY"?

I don't think it's a normative MAY. I'll change that to "are",
including the max block length for the response size ?

> I guess my question is: "why isn't this in non-sensible" if it's NOT

Hmm - The idea is that the resource consumption concerns might be gone
as soon as everyone has eg. 100Gbit/s+ to their mobiles, and DNS
traffic doesn't really matter anymore. The privacy concerns might
outweight the resource considerations then, and being the strategy
that provide perfect privacy, it might very well become feasible.

> There still seem to be some vestiges.

Removed all of it, as outlined above.

> I think I would just say it's not as good.

I'll think about text...

> That did not happen. However, as noted above, we are good.

I think he wanted to talk to you once the proposed solution is on the
table. But, based on what you wrote above, i'll prepare a new revision
once the responses from the other ADs are in.

thanks!

Alex

---

From: Ben Schwartz <[email-masked]>
Date: Wed, 18 Jul 2018 18:32:27 -0400

On Wed, Jul 18, 2018 at 10:43 AM Alexander Mayrhofer <
[email-masked]> wrote:

> TLS-DNS.

Hey, I think there's been a misunderstanding here.  Currently, Android
master (and Android P beta) is padding to 128:
https://android.googlesource.com/platform/bionic/+/refs/heads/master/libc/dns/include/resolv_params.h#39

This isn't meant as a comment on the document.

imho, padding to 16 byte boundaries on the query is still
> _______________________________________________
> dns-privacy mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/dns-privacy
>

---

From: Alexander Mayrhofer <[email-masked]>
Date: Thu, 19 Jul 2018 08:24:18 +0200

Hello Ben,

> https://android.googlesource.com/platform/bionic/+/refs/heads/master/libc/dns/include/resolv_params.h#39

Thanks for clarification, sorry for the misleading statement. My
recollection stems from a discussion we had a while ago - i think it
was Singapore. I'm very excited that there is adoption on such a broad
scale - amazing news!

I would be curious about how the 128 block length was chosen, and
whether there was research behind that. It that is the case, i'd love
to hear about it, and consider the results for a potential (Standards
Track) follow-up to the Padding Policy document.

best,

Alex

---

From: Ben Schwartz <[email-masked]>
Date: Thu, 19 Jul 2018 10:05:32 -0400

On Thu, Jul 19, 2018 at 2:24 AM Alexander Mayrhofer <
[email-masked]> wrote:

> was Singapore.

I think I can fairly say that the padding situation ended up better than I
expected at that time.

> I'm very excited that there is adoption on such a broad
> scale - amazing news!
>
> whether there was research behind that.

It's just following the recommended strategy from section 4.1.

> It that is the case, i'd love