Subject: [AVTCORE] Randomly-generated CNAMEs

From: Eric Rescorla <[email-masked]>
Date: Wed, 20 Jun 2012 19:04:17 -0700

RFC 6222 specifies two CNAME generation algorithms:

- Persistent CNAMEs based on UUIDs
- Short-term CNAMEs based on a digest of the MAC address and time of day.

However, reading this document and the security considerations it seems like
both methods produce CNAMEs which aren't unlinkable. Obviously the
persistent CNAMEs are linkable, and it doesn't look like short-term CNAMEs
have enough entropy to be unlinkable either. Specifically, the inputs are
(Section 5):

1. The MAC address (or EUI-64)
2. The time of day (NTP-style)
3. Initial SSRC, and IP/port quartet

(3) is known to the other side, (2) is at most 48-bits (and
practically much less)
and (2) is known to within a fairly narrow margin (and, it appears, communicated
in the RTP timestamp).

The upshot is that it seems likely that I can link two RTP sessions
from the same
person. Note that RFC 6222 doesn't say otherwise. Rather, it says:

 This document uses a hash function to ensure the uniqueness of RTCP
   CNAMEs.  A cryptographic hash function is used because such functions
   provide the randomness properties that are needed.  However, no
   security assumptions are made on the hash function.  The hash
   function is not assumed to be collision resistant, preimage
   resistant, or second preimage resistant in an adversarial setting; as
   described above, an attacker attempting an impersonation attack could
   merely set the RTCP CNAME directly rather than attacking the hash
   function.  Similarly, the hash function is not assumed to be a one-
   way function or pseudorandom in a cryptographic sense.

For privacy reasons, it would be nice to be able to generate CNAMEs randomly
so that they're not linkable. Unfortunately, 6222 seems to require
that short-term
credentials be generated via the above mechanism. Is there any reason why
that shouldn't be allowed?

-Ekr

---

From: Colin Perkins <[email-masked]>
Date: Thu, 21 Jun 2012 11:22:02 +0100

Ekr,

I'm not sure I understand what problem you're trying to solve: the point of the CNAME is to allow different RTP sessions to be linked. 

Colin

On 21 Jun 2012, at 03:04, Eric Rescorla wrote:
> However, reading this document and the security considerations it seems like both methods produce CNAMEs which aren't unlinkable. Obviously the persistent CNAMEs are linkable, and it doesn't look like short-term CNAMEs have enough entropy to be unlinkable either. Specifically, the inputs are (Section 5):
> 
> (3) is known to the other side, (2) is at most 48-bits (and practically much less) and (2) is known to within a fairly narrow margin (and, it appears, communicated in the RTP timestamp).
> 
> The upshot is that it seems likely that I can link two RTP sessions from the same person. Note that RFC 6222 doesn't say otherwise. Rather, it says:
> 
> For privacy reasons, it would be nice to be able to generate CNAMEs randomly so that they're not linkable. Unfortunately, 6222 seems to require that short-term credentials be generated via the above mechanism. Is there any reason why that shouldn't be allowed?
> 
> -Ekr
> _______________________________________________
> Audio/Video Transport Core Maintenance
> [email-masked]
> https://www.ietf.org/mailman/listinfo/avt

-- 
Colin Perkins
http://csperkins.org/

---

From: Cullen Jennings <[email-masked]>
Date: Thu, 21 Jun 2012 08:39:33 -0400

One again, I think we have complete failure on the meaning of the word session :-) 

I think what EKR was getting at is that if A call B in one phone call, then day later A wants to make an anonymous call to B, B should not be able to tell the second call is coming from same devices. I think that was part of the goal of 6222 but from EKR's email it looks like it fails to provide that.

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 21 Jun 2012 05:48:12 -0700

> I think what EKR was getting at is that if A call B in one phone call, then day later A wants to make an anonymous call to B, B should not be able to tell the second call is coming from same device…

Exactly.

-Ekr

---

From: Colin Perkins <[email-masked]>
Date: Thu, 21 Jun 2012 22:54:32 +0100

On 21 Jun 2012, at 20:09, Martin Thomson wrote:
> On 21 June 2012 05:48, Eric Rescorla <[email-masked]> wrote:
> I agree with the analysis.  The idea that the same browser could be
> correlated across two independent sessions bothers me.  Within the one
> "session", fine - on the contrary, mandatory.  Outside of that, I'd
> like at least an option for anonymity.

Using SRTP to encrypt the traffic will stop third-parties correlating the sessions, and RTCWeb is mandates SRTP and encryption.

RFC 6222 does define per-session RTCP CNAME values, if you're concerned about the called party being able to correlate sessions based on the RTCP CNAME. We could mandate those instead of short-term persistent RTCP CNAME values. If that's not sufficient, then someone will need to write a draft that defines a new RTCP CNAME generation algorithm, which this draft can refer to. 

-- 
Colin Perkins
http://csperkins.org/

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 21 Jun 2012 15:10:20 -0700

> Using SRTP to encrypt the traffic will stop third-parties correlating the sessions, and RTCWeb is mandates SRTP and encryption.

I'm concerned about tracking by people who are second parties.

Consider the case where I call you from an anonymous phone at a domestic
violence shelter. I record the CNAME and then call all the DV shelters until
I determine which one has a CNAME from the same device.

> RFC 6222 does define per-session RTCP CNAME values, if you're concerned about the called party being able to correlate sessions based on the RTCP CNAME. We could mandate those instead of short-term…

The problem is that those per-session CNAME values do not appear to be
unlinkable.
I.e., they are distinct but they are generated from the same
underlying data with
insufficient entropy to prevent someone who knows two CNAMEs from determining
if they are from the same device.

As far as new algorithm goes, is there some reason "Random" isn't good enoguh?

-Ekr

---

From: Colin Perkins <[email-masked]>
Date: Thu, 21 Jun 2012 23:28:53 +0100

On 21 Jun 2012, at 23:10, Eric Rescorla wrote:
> Consider the case where I call you from an anonymous phone at a domestic violence shelter. I record the CNAME and then call all the DV shelters until I determine which one has a CNAME from the same device.
> 
> unlinkable. I.e., they are distinct but they are generated from the same underlying data with insufficient entropy to prevent someone who knows two CNAMEs from determining if they are from the same device.
> 

There's some discussion in RFC 3550 Section 6.5.1 and RFC 6222. It might be possible to use a random choice, provided the same random value is used across all sessions that need to be correlated, and the value is chosen to be unique with high probability. I haven't thought about it in detail. In any case, it's an update to RFC 3550 and RFC 6222, so someone will have to write up the draft defining this. 

-- 
Colin Perkins
http://csperkins.org/

---

From: Kevin Gross <[email-masked]>
Date: Thu, 21 Jun 2012 17:09:04 -0600

It seems like, pure random CNAMEs would have the same or better probability
of uniqueness compared to the hashed values specified in 6222. I don't
think it is difficult to prove this if you assume the hash function does
what it's designed to and makes data white. 48 is not enough bits to ensure
uniqueness of a large population of random numbers. If I remember
correctly, 64 bits is where the statistics start to get comfortable. See
http://en.wikipedia.org/wiki/Birthday_problem. Potentially there's a bigger
problem here than linkability :(

Kevin Gross

On Thu, Jun 21, 2012 at 4:28 PM, Colin Perkins <[email-masked]> wrote:

> >>>>> I think what EKR was getting at is that if A call B in one phone
> call, then day later A wants to make an anonymous call to B, B should not
> be able to tell the second call is coming from same devices. I think that
> was part of the goal of 6222 but from EKR's email it looks like it fails to
> provide that.
> >>>>
> >>>> Exactly.
> >>>
> >> Using SRTP to encrypt the traffic will stop third-parties correlating
> the sessions, and RTCWeb is mandates SRTP and encryption.
> >
> violence shelter. I record the CNAME and then call all the DV shelters
> until I determine which one has a CNAME from the same device.
> >
> >> RFC 6222 does define per-session RTCP CNAME values, if you're concerned
> about the called party being able to correlate sessions based on the RTCP
> CNAME. We could mandate those instead of short-term persistent RTCP CNAME
> values. If that's not sufficient, then someone will need to write a draft
> that defines a new RTCP CNAME generation algorithm, which this draft can
> refer to.
> >
> > unlinkable. I.e., they are distinct but they are generated from the same
> underlying data with insufficient entropy to prevent someone who knows two
> CNAMEs from determining if they are from the same device.
> >
> There's some discussion in RFC 3550 Section 6.5.1 and RFC 6222. It might
> be possible to use a random choice, provided the same random value is used
> across all sessions that need to be correlated, and the value is chosen to
> be unique with high probability. I haven't thought about it in detail. In
> any case, it's an update to RFC 3550 and RFC 6222, so someone will have to
> write up the draft defining this.
>
> --
> Colin Perkins
> http://csperkins.org/
>
>
>

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 21 Jun 2012 16:12:27 -0700

This matches my analysis.

-Ekr

On Thu, Jun 21, 2012 at 4:09 PM, Kevin Gross <[email-masked]> wrote:
> of uniqueness compared to the hashed values specified in 6222. I don't think
> it is difficult to prove this if you assume the hash function does what it's
> designed to and makes data white. 48 is not enough bits to ensure uniqueness
> of a large population of random numbers. If I remember correctly, 64 bits is
> where the statistics start to get comfortable. See
>> >>>>> call, then day later A wants to make an anonymous call to B, B should not be
>> >>>>> able to tell the second call is coming from same devices. I think that was
>> >>>>> part of the goal of 6222 but from EKR's email it looks like it fails to
>> >>>>> provide that.
>> >>>>
>> >>>> Exactly.
>> >>>

---

From: "Ali C. Begen (abegen)" <[email-masked]>
Date: Fri, 22 Jun 2012 00:46:14 +0000

Many implementors just assume "0" for any random number they need to come up with. So, saying to choose a random number may not cut it.

-acbegen

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf Of Kevin Gross
> Sent: Thursday, June 21, 2012 7:09 PM
> To: Colin Perkins
> Cc: Martin Thomson; [email-masked]; [email-masked]; Cullen Jennings
> Subject: Re: [AVTCORE] [rtcweb] Randomly-generated CNAMEs
> 
> It seems like, pure random CNAMEs would have the same or better probability of uniqueness compared to the hashed values
> specified in 6222. I don't think it is difficult to prove this if you assume the hash function does what it's designed to and makes
> data white. 48 is not enough bits to ensure uniqueness of a large population of random numbers. If I remember correctly, 64
> bits is where the statistics start to get comfortable. See  http://en.wikipedia.org/wiki/Birthday_problem. Potentially there's a
> bigger problem here than linkability :(
> 
> Kevin Gross
> 
> 
> 	>>>>> I think what EKR was getting at is that if A call B in one phone call, then day later A wants to make an
> anonymous call to B, B should not be able to tell the second call is coming from same devices. I think that was part of the
> goal of 6222 but from EKR's email it looks like it fails to provide that.
> 	>>>>
> 	>>>> Exactly.
> 	>>>
> 	> Consider the case where I call you from an anonymous phone at a domestic violence shelter. I record the CNAME
> and then call all the DV shelters until I determine which one has a CNAME from the same device.
> 	>
> 	>> RFC 6222 does define per-session RTCP CNAME values, if you're concerned about the called party being able to
> correlate sessions based on the RTCP CNAME. We could mandate those instead of short-term persistent RTCP CNAME values.
> If that's not sufficient, then someone will need to write a draft that defines a new RTCP CNAME generation algorithm, which
> this draft can refer to.
> 	>
> 	> unlinkable. I.e., they are distinct but they are generated from the same underlying data with insufficient entropy to
> prevent someone who knows two CNAMEs from determining if they are from the same device.
> 	>
> 	There's some discussion in RFC 3550 Section 6.5.1 and RFC 6222. It might be possible to use a random choice,
> provided the same random value is used across all sessions that need to be correlated, and the value is chosen to be unique
> with high probability. I haven't thought about it in detail. In any case, it's an update to RFC 3550 and RFC 6222, so someone
> will have to write up the draft defining this.
> 
> 
> 	--
> 	Colin Perkins
> 	http://csperkins.org/
> 
> 
> 
>

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 21 Jun 2012 18:02:27 -0700

> Many implementors just assume "0" for any random number they need to come up with. So, saying to choose a random number may not cut it.

I would require it to be cryptographically random. That's not an issue
since this system needs such numbers all over the place.

---

From: Kevin Gross <[email-masked]>
Date: Thu, 21 Jun 2012 21:07:42 -0600

RFC 4086 - Randomness Requirements for Security

On Thu, Jun 21, 2012 at 7:48 PM, Justin Uberti <[email-masked]> wrote:

>
>
> On Thu, Jun 21, 2012 at 9:02 PM, Eric Rescorla <[email-masked]> wrote:
>
>> > Many implementors just assume "0" for any random number they need to
>> come up with. So, saying to choose a random number may not cut it.
>>
> Right. In our implementation, we use random data for CNAMEs; it's simpler
> than performing the RFC 6222 steps and indistinguishable on the wire.
>

---

From: Martin Thomson <[email-masked]>
Date: Thu, 21 Jun 2012 12:09:09 -0700

---

From: Justin Uberti <[email-masked]>
Date: Thu, 21 Jun 2012 21:48:58 -0400