Subject: [rtcweb] 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: Martin Thomson <[email-masked]>
Date: Thu, 21 Jun 2012 12:09:09 -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 devic…

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.

---

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

> 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: 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:
> 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.
>> >
>> >> 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

On Thu, Jun 21, 2012 at 5:46 PM, Ali C. Begen (abegen) <[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.

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

---

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

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: Randell Jesup <[email-masked]>
Date: Thu, 21 Jun 2012 23:01:32 -0400

> This matches my analysis.

Mine also, and I agree a 64-bit cryptographically random number is safer 
against collision than the RFC 6222 value, unless you *want* to be able 
to reverse the operation to find the inputs.  I agree with Justin that 
there's no reason we can see to implement RFC6222 instead of using a 
64-bit random number per above, and plenty of reasons to use the 64-bit 
number.

-- 
Randell Jesup
[email-masked]

---

From: "Dan Wing" <[email-masked]>
Date: Fri, 22 Jun 2012 19:05:12 -0700

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On
> Behalf Of Randell Jesup
> Sent: Thursday, June 21, 2012 8:02 PM
> To: [email-masked]
> Subject: Re: [rtcweb] [AVTCORE] Randomly-generated CNAMEs
> 

Yeah, that's what I wrote when I became a co-author of
draft-begen-avt-rtp-cnames-02, although was 96 bits (instead of 64),
http://tools.ietf.org/rfcdiff?url2=draft-begen-avt-rtp-cnames-02.txt and
concatenated some other cruft beyond just an RFC4086 random number,

  o  To generate a unique CNAME for each RTP session, an endpoint MAY
      perform SHA1-HMAC [RFC2104] on the concatenated values of the RTP
      endpoint's initial SSRC, the source and destination IP addresses
      and ports, and a randomly-generated value [RFC4086], and then
      truncate the 160-bit output to 96 bits and finally convert the 96
      bits to ASCII using Base64 encoding [RFC4648].  This results in a
      128-bit printable CNAME.  Note that the CNAME MUST NOT change if
      an SSRC collision occurs, hence only the initial SSRC value chosen
      by the endpoint is used.

That text evolved as the document progressed, and veered farther away
from being "just a big random number".  I don't recall why it evolved.

-d

> >>>>>>> On Thu, Jun 21, 2012 at 5:39 AM, Cullen Jennings
> <[email-masked]>
> >>>>>>> wrote:
> >>>> As far as new algorithm goes, is there some reason "Random" isn't
> good
> >>>> enoguh?
> >>>
> >>>
> rtcweb mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/rtcweb

---

From: Harald Alvestrand <[email-masked]>
Date: Sat, 23 Jun 2012 15:56:53 +0200

It seems to me that we have two issues here, and it might be good to 
separate them:

- I believe RTCWEB implementations should accept a very large set of 
CNAMEs - essentially anything that isn't hopelessly long or has 
"bizarre" characters in them.

- I believe RTCWEB implementations should be allowed to generate CNAMEs 
that satisfy EKR's requirements for unlinkability.

Those two are probably worthy of separate text, and perhaps even 
separate documents.

                 Harald

---

From: Glen Zorn <[email-masked]>
Date: Sun, 24 Jun 2012 08:01:00 +0700

> that satisfy EKR's requirements for unlinkability.

s/allowed/strongly encouraged/ above & I agree.

---

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:

> 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.
> >>>
> 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.
> >

---

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

-acbegen

> 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: Kevin Gross <[email-masked]>
Date: Thu, 21 Jun 2012 21:07:42 -0600

RFC 4086 - Randomness Requirements for Security

---

From: Cullen Jennings <[email-masked]>
Date: Thu, 28 Jun 2012 07:53:06 -0700

Colin & Magnus, given this is starting to look like it is likely to get consensus, could you update draft-ietf-rtcweb-rtp-usage to have text for random generation and resonating behind it?

---

From: Colin Perkins <[email-masked]>
Date: Thu, 28 Jun 2012 19:09:35 +0100

> Colin & Magnus, given this is starting to look like it is likely to get consensus, could you update draft-ietf-rtcweb-rtp-usage to have text for random generation and resonating behind it?

As I said, write a draft, and we'll reference it. I don't think this draft is the place to update the RTP specification.

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

---

From: "DRAGE, Keith (Keith)" <[email-masked]>
Date: Fri, 29 Jun 2012 10:26:28 +0200

Colin is correct.

This is not a profiling activity.

This is an update activity to an existing AVTCORE specification.

Regards

Keith

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Colin Perkins
Sent: 28 June 2012 19:10
To: Cullen Jennings
Cc: [email-masked]
Subject: Re: [rtcweb] [AVTCORE] Randomly-generated CNAMEs

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

---

From: Cullen Jennings <[email-masked]>
Date: Fri, 29 Jun 2012 08:35:49 -0700

RFC 3550 has the words 

   To meet these requirements, the
   following format SHOULD be used unless a profile specifies an
   alternate syntax or semantics.  

what I am suggesting here is that we define a profile that specifies a alternative format but still meets all the other SHOULD and MUST in 3550 that are not part of the "following format" referred to in that sentence. 

Now several people are making the argument we need to go and deprecate 6222 and replace it with something else. But I'm not seeing any process reasons why this could not be done as profile if that was what we wanted to do. 

Thoughts?

---

From: Colin Perkins <[email-masked]>
Date: Fri, 29 Jun 2012 16:40:35 +0100

A profile is something specific in RTP. You really don't want to define a new RTP profile for this - that's a far bigger job than updating RFC3550.

Colin

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

---

From: Cullen Jennings <[email-masked]>
Date: Fri, 29 Jun 2012 08:49:06 -0700

ok - Fair enough.