Subject: [Sip] size of temporary GRUUs

From: "Jeroen van Bemmel" <[email-masked]>
Date: Wed, 14 Mar 2007 18:30:52 +0100

All,

I did a rough test on generating a temporary GRUU:

1. Concatenate AoR "|" instance-id "|" absolute expiration time (hex) --> 
gives 83 bytes
2. Encrypt using Windows CryptProtectData API call using 128-bit salt (not 
sure which algorithm it uses, does perform MAC) --> gives 226 bytes
3. apply base64 encoding --> gives ~300 bytes

So: following appendix A in gruu-12, only the _user_ part of a temporary 
GRUU is roughly 300 bytes in size.

Regards,
Jeroen 
_______________________________________________
Sip mailing list  https://www1.ietf.org/mailman/listinfo/sip
This list is for NEW development of the core SIP Protocol
Use [email-masked] for questions on current sip
Use [email-masked] for new developments on the application of sip

---

From: Sean Olson <[email-masked]>
Date: Wed, 14 Mar 2007 10:37:35 -0700

See:  http://msdn2.microsoft.com/en-us/library/aa925034.aspx
The algorithm used in either Triple-DES or RC4 (default) depending on which you choose

From: Jeroen van Bemmel [mailto:[email-masked]]
Sent: Wednesday, March 14, 2007 10:31 AM
To: [email-masked]
Subject: [Sip] size of temporary GRUUs

All,

1. Concatenate AoR "|" instance-id "|" absolute expiration time (hex) --> gives 83 bytes
2. Encrypt using Windows CryptProtectData API call using 128-bit salt (not sure which algorithm it uses, does perform MAC) --> gives 226 bytes
3. apply base64 encoding --> gives ~300 bytes

So: following appendix A in gruu-12, only the _user_ part of a temporary GRUU is roughly 300 bytes in size.

Regards,
Jeroen

---

From: "Jeroen van Bemmel" <[email-masked]>
Date: Wed, 14 Mar 2007 18:44:20 +0100

Thanks Sean,

I compared it myself with 
http://publib.boulder.ibm.com/infocenter/idshelp/v10/index.jsp?topic=/com.ibm.sqls.doc/sqls1024.htm
The table provided there for AES with a hint (excluding MAC) shows 227 bytes 
for 100 input bytes, so I was assuming that 83 to 226 bytes could be 
indicative

I should add that I concatenated the AoR, instance-id and expiration time as 
ASCII strings - some bytes could be saved by using binary here. Perhaps this 
could be an argument to standardize more strict on the format of the 
instance-id: the uuid-format allows more compact conversion to binary

Regards,
Jeroen
  ----- Original Message ----- 
  From: Sean Olson
  To: Jeroen van Bemmel ; [email-masked]
  Sent: Wednesday, March 14, 2007 6:37 PM
  Subject: RE: [Sip] size of temporary GRUUs

  The algorithm used in either Triple-DES or RC4 (default) depending on 
which you choose

  All,

  Regards,

  Jeroen

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 14 Mar 2007 11:26:30 -0800

> instance-id: the uuid-format allows more compact conversion to binary

So, as a practical matter the stateless token format in 
draft-rescorla-stateless-tokens-01 adds a minimum of 50 bytes
of overhead, so you can add that to the size of the data
itself and then b64 it....

-Ekr

---

From: Jonathan Rosenberg <[email-masked]>
Date: Wed, 14 Mar 2007 15:20:30 -0400

So, Jeroen, I'm unsure if this is a criticism (we need to do something 
different for temp gruu), or just a statement of fact you think we 
should mention more clearly in the document. I'm personally fine with 
this; if the size bothers an implementation it can use a stateful 
technique and the size can be shorter.

-Jonathan R.

-- 
Jonathan D. Rosenberg, Ph.D.                   600 Lanidex Plaza
Cisco Fellow                                   Parsippany, NJ 07054-2711
Cisco Systems
[email-masked]                              FAX:   (973) 952-5050
http://www.jdrosen.net                         PHONE: (973) 952-5000
http://www.cisco.com

---

From: "Jeroen van Bemmel" <[email-masked]>
Date: Wed, 14 Mar 2007 23:11:33 +0100

Jonathan,

It's something I personally did not realize fully until now, and it may be 
something that renders stateless temporary gruus unusable in some 
deployments. Memory usage at the registrar is reduced, but at the cost of a 
significant increase of message size.

One aspect of this is that the draft uses examples like 
'temp-gruu="sip:[email-masked];gr', making a temp-gruu look 
about the same size as its public cousin. With a fully stateless approach it 
will be more like 
temp-gruu="sip:AQAAANCMnd8BFdERjHoAwE/Cl+sBAAAAP7dBrHt14kasd9uJd8P5jQAAAAACAAAAAAADZgAAqAAAABAAAADsbbCyhVQzsxwwz/GDtAU3AAAAAASAAACgAAAAEAAAAKQHD3/mwAK81/dl7fZgynxYAAAA5q1SG7kiK57ukwHHiiErCoopbsRQzRQtZmuMiSKbbFPIK/U0jw0LQ6sdM6X2ttM/BHpeZYGD8YdVPLNqJTRtUXArUCZhmL/SRH34GFJF4MSp8m97XR0nPBQAAABO0exx6ITfWE5uKYq9VPl49/jesA==@example.com;gr"

(Not that this would not make the example more clear, perhaps a notation 
with "..." would be better). So yes, at the very least it should be 
mentioned in the GRUU draft. It should probably be recommended that if 
message size is a problem, deployments should consider a stateful approach 
instead.

A scenario in which this adds up would be a REFER callflow. The GRUU would 
appear both in the request URI and in the To URI, and if the originator is 
also using a temp-gruu in its own Contact... anyway, you get the idea.

I am fine with just mentioning it more clearly in the document.

Regards,
Jeroen

Jonathan Rosenberg wrote:
>>> The table provided there for AES with a hint (excluding MAC) shows
>>> 227 bytes for 100 input bytes, so I was assuming that 83 to 226
>>> bytes could be indicative
>>>
>>> I should add that I concatenated the AoR, instance-id and
>>> expiration time as ASCII strings - some bytes could be saved by
>>> using binary here. Perhaps this could be an argument to standardize
>>> more strict on the format of the instance-id: the uuid-format
>>> allows more compact conversion to binary
>>
>>

---

From: Adam Roach <[email-masked]>
Date: Sat, 17 Mar 2007 10:05:52 +0000

> technique and the size can be shorter.

Not really. The problem is that, with the new way that temporary GRUUs 
work, any registrar that manages this statefully is required to maintain 
that that grows potentially without bound. For example, I have a SIP 
phone on my desk that has been diligently registering about once an hour 
for over 200 days now. It has had no reason to rotate its call ID during 
that time period. So, while I don't have an easy way to verify this, I 
suspect that it has kept a continuous registration going that entire 
time with the same Call ID.

If my registrar used a stateful technique (and my phone supported GRUU), 
I would have on the order of 5,000 valid temporary GRUUs for this single 
phone, any my registar would be required to remember each and every one 
of them until my phone finally went offline.

That's probably okay for an enterprise environment (for sufficiently 
small enterprises), but you take that and multiply it by the number of 
subscribers a typical cable company might sell their VoIP solution to, 
and it quickly becomes unmanagable.

So, we either need to commit to forcing implementations out there to 
playing nice with 300-plus-byte URIs (and basically say "registrars must 
do this statefully"), or come up with some other way to handle temporary 
GRUUs that won't require stateful implementations to keep unbounded 
quantities of state.

/a

---

From: [email-masked] (Juha Heinanen)
Date: Tue, 20 Mar 2007 19:41:01 +0200

> of them until my phone finally went offline.

this sounds VERY scary and completely un-scalable.  what other
implementation mines the i-d contains?  it would be nice to hear about
them now.

-- juha

---

From: Paul Kyzivat <[email-masked]>
Date: Wed, 21 Mar 2007 05:16:16 -0400

I haven't really thought this through, but I expect that a stateful 
algorithm for temp gruus could be constructed that kept the gruus small 
and yet didn't require actually storing all of the currently active 
gruus for a given contact and instance id.

	Paul

---

From: Jonathan Rosenberg <[email-masked]>
Date: Wed, 21 Mar 2007 05:58:03 -0400

I agree with Juha here. We need to make sure we understand the 
implications of this. I'm a bit worried that right now, the choices are:

1. a stateful algorithm which stores a potentially unbounded number of 
temp-gruu for each AOR/instance ID and has clear scale problems

2. a stateless algorithm which produces 300 byte temp-GRUU

Choice 1 is probably a non-starter as Adam has pointed out. Thinking 
about the implications of choice 2 that we need to consider:

* since GRUU are present in REGISTER responses and not requests, this 
has the consequence of making responses much larger than requests. If 
the request was approaching the ethernet MTU, this has the possibility 
of introducing the large UDP response problem, which is currently unsolved.

* temp GRUU would be present in SIP INVITE requests (possibly others) 
for anonymous calls, likely in the Contact and in From header field. 
This will make anonymous requests large and likely cause them to go over 
TCP.

* Intermediate proxies on a REGISTER or INVITE transaction that use GRUU 
need to be prepared for very long URI (300 bytes based on Christer's 
measurement). These would be elements that otherwise wouldn't support 
GRUU in any way. If those implementations aren't prepared for very long 
URI then GRUU will fail badly and somewhat unpredictably

These are all difficult issues. Noodling on this a bunch last night I 
was getting increasingly worried that this might have serious deployment 
issues since we don't have an implementable solution here.

If the group is concerned about this, I have thought of two possibilities:

APPROACH 1
----------

Adam's example has a server storing 5000 temp-gruu. This is sort of 
silly since we have no use case where the UA needs 5000 temp-gruu. So 
one solution is to introduce mechanisms to limit the number of 
temp-gruu. We could choose an upper bound (fixed by the protocol, or 
perhaps negotiated).

When the client does a register refresh, it gets a new one until the 
maximum number have been granted. At that point, the server can't give a 
new one until it gets a signal from the client that the oldest one is no 
longer in use for a dialog. So we'd put a flag in a register refresh 
from the client which 'advances the window' so to speak, freeing the 
oldest so a newer one can be allocated.

This adds more stuff into the protocol and probably complicates further 
the synchronization process. Fortunately the lowest-cseq/call-ID 
approach we discussed on the list and in the meeting supports this well.
The main question we'd have to answer is whether a client would NEED to 
support reg-event to synchronize or if it works without it. I need to 
think more about that.

APPROACH 2
----------

There might be ways to do generation of the token that require state, 
but state that doesn't scale with the number of temp-gruu or the number 
of users. I have one idea for this, not sure it works, but here is my 
thinking. The server maintains a sequence of random numbers, each random 
number being 128 bits long. This is not a per user sequence; its a 
server-wide sequence. I think you'll need a few thousand of them at a time.

Each AOR is associated with an integer, say 64 bits. Its stored in the 
database and each one points to a particular AOR. Many impelementations 
already have such identifiers as primary keys in their databases. We can 
pick a larger bitsize if it helps reuse those. Similarly, each instance 
ID seen by the system for a particular AOR are also stored in the 
database, indexed by another 64 bit integer, pointing to that instance 
ID. Again, this typically exists already.

Associated with each instance ID and AOR is the sequence number of the 
random number used for the last temp GRUU handed out for that 
AOR/instance ID. When a new temp-gruu is to be allocated, that sequence 
number is compared to the highest sequence number in the list of global 
sequence numbers. If its lower, its value is incremented, and the 
corresponding random number from the global table is selected. If it is 
equal, a new random number is pickde and added to the global list of 
sequence numbers. Then, the per aor/instance-id is incremented and that 
new random number is used. The temp-gruu is then:

sip:gruu.<seqno>.base64(<XOR(random-number,(AOR key || instance key))>)

this is actually very short, shorter than the AOR in most cases. When 
the proxy receives a request with the URI starting with gruu, it takes 
the sequence number, looks up the random number, xor's it with the rest 
of the gruu, gets and AOR and instance keys, which are then used to look 
up the gruu.

This format has the property that any two URI for a *particular* 
AOR/instance ID cannot be correlated since they are always based on a 
xor of fixed data with a different random number, which is always random 
(I believe). The big idea is that we are reusing the random number for 
multiple AOR, but as long as the random numbers cannot be guessed or 
learned by playing games (like an attacker comparing its own AOR to its 
gruu), I believe this is OK.

Even if someone learns the random number you have perfect forward 
secrecy since that random number is never reused for a particular AOR 
for any later temp-gruu, so if you expire the temp-gruu (using the 
mechanism we discussed yesterday), you get new temp-gruu and they are 
not compromised.

This format has a 'problem' that an attacker could construct a gruu that 
routes to a particular AOR by guessing values for seqno, AOR key and 
instance key. You can resolve that by increasing the bitsizes and using 
keys that are, instead of sequentially assigned, randomly assigned 
within the number space. However, even if sequentially assigned, we have 
no requirement to PREVENT people from constructing GRUU that route to an 
instance; we certainly have never had a requirement to prevent people 
from constructing AOR, which is easily done just like for email.

I'm not confident that this algorithm has the security properties 
required of a temp-gruu, someone more skilled than me would need to make 
that assessment and if it doesnt work, suggest an improvement that has 
similar properties.

Thoughts?

-Jonathan R.

---

From: Adam Roach <[email-masked]>
Date: Wed, 21 Mar 2007 11:16:06 +0100

Jonathan Rosenberg wrote:
> This will make anonymous requests large and likely cause them to go 
> over TCP.
>
> * Intermediate proxies on a REGISTER or INVITE transaction that use 
> GRUU need to be prepared for very long URI (300 bytes based on 
> Christer's measurement). These would be elements that otherwise 
> wouldn't support GRUU in any way. If those implementations aren't 
> prepared for very long URI then GRUU will fail badly and somewhat 
> unpredictably
>
>
> was getting increasingly worried that this might have serious 
> deployment issues since we don't have an implementable solution here.
>
> maximum number have been granted. At that point, the server can't give 
> a new one until it gets a signal from the client that the oldest one 
> is no longer in use for a dialog. So we'd put a flag in a register 
> refresh from the client which 'advances the window' so to speak, 
> freeing the oldest so a newer one can be allocated.
>
> This adds more stuff into the protocol and probably complicates 
> further the synchronization process. Fortunately the 
> lowest-cseq/call-ID approach we discussed on the list and in the 
> meeting supports this well.
> The main question we'd have to answer is whether a client would NEED 
> to support reg-event to synchronize or if it works without it. I need 
> to think more about that.

This approach seems a bit of a problem -- if I use a GRUU for a 
long-running subscription (and I could probably come up with valid use 
cases for this scenario), then the UA eventually gets that GRUU to the 
"stale" limit and basically ends up starving itself. Yes, it would be 
possible to rotate out for a newer GRUU with a dialog refresh, but that 
introduces another moving part. It feels like a series of patches on top 
of patches just to get things to work -- and that usually means we're 
going to miss some subtle detail.

> but state that doesn't scale with the number of temp-gruu or the 
> number of users. I have one idea for this, not sure it works, but here 
> is my thinking. The server maintains a sequence of random numbers, 
> each random number being 128 bits long. This is not a per user 
> sequence; its a server-wide sequence. I think you'll need a few 
> thousand of them at a time.

There is probably a solution in this direction, but I suspect that this 
isn't it. This sequence of random numbers (if I understand your 
proposal) is the same size as the maximum number of registrations ever 
performed within a single dialog. So, in the nominal case, it grows 
linearly with time as long as you have one phone that continually 
re-registers. But that's not the problem -- I could get along with that.

The problem is that it opens up a state exhaustion attack in which I 
register ever 20 milliseconds instead of every 3600 seconds. Yes, you'll 
know it's me (or someone who has compromised my account), but the only 
recovery path likely is rebooting the server or hoping that the server 
has some kind of very fancy administrative nerd knob that allows release 
of GRUU state sequence numbers.

I'll think about this and see if I can't propose something similar 
without these properties...

/a

---

From: Jonathan Rosenberg <[email-masked]>
Date: Wed, 21 Mar 2007 09:29:50 -0400

inline.

> going to miss some subtle detail.

Great point. I think this pretty much puts a nail in the coffin of that 
technique.

> performed within a single dialog.

It has nothing to do with the number of registrations during a 
particular dialog; its the number of registrations you would ever see 
during the 'uptime' of an endpoint. So, its actually larger than the 
number you are thinking about.

> So, in the nominal case, it grows 

Right.

> of GRUU state sequence numbers.

Ah, great point. This is easily fixed though. Instead of using the next 
sequence number anytime any endpoint registers, we increment it only 
once every T minutes, where T is the minimum registration interval you 
support on the network. Even if a client registers more frequently and 
its not an attack (who knows why), worst case is it doesn't get a new 
temp-gruu, it gets one it already had. But odds are it has a few stored 
up anyway.

So with that change, lets say we set T to 10 minutes. Thats 52,560 
random numbers if you assume a 6-month continuous uptime.

Another similar option is to time-bound these also; say, to two weeks. 
This would preclude a dialog being up for two weeks. A client with a 
really long-lived subscription would have to terminate and resubscribe 
every two weeks. Not a huge deal IMHO but it would be a limitation. To 
deal with time sync, the server keeps them around for two weeks and a 
day, so you really never run into a race failure.

Thinking aloud here to try and find something that actually works....

-Jonahtan R.

---

From: Adam Roach <[email-masked]>
Date: Wed, 21 Mar 2007 15:04:01 +0100

Jonathan Rosenberg wrote:
>> register ever 20 milliseconds instead of every 3600 seconds. Yes, 
>> you'll know it's me (or someone who has compromised my account), but 
>> the only recovery path likely is rebooting the server or hoping that 
>> the server has some kind of very fancy administrative nerd knob that 
>> allows release of GRUU state sequence numbers.
>
> Ah, great point. This is easily fixed though. Instead of using the 
> next sequence number anytime any endpoint registers, we increment it 
> only once every T minutes, where T is the minimum registration 
> interval you support on the network. Even if a client registers more 
> frequently and its not an attack (who knows why), worst case is it 
> doesn't get a new temp-gruu, it gets one it already had. But odds are 
> it has a few stored up anyway.
>

After giving this some more thought, I think the solution may lie in the 
direction of using a *random* number (not a sequence number) for the 
part that's visible, and then using a subset of bytes from a crypto hash 
of this random number plus a server secret for your xor operation.

More concretely (and this is a slight variation on your original 
proposal)...

To form a private gruu in a stateful fashion, the registrar picks a 
random number.  It then calculates a 16-byte key:

  key = substring(H(random-number, server-secret), 16)

(Where H is a crypto hash that produces at least 16 bytes of hash output)

Then, using the 64-bit AOR id and 64-bit instance id you described in 
your earlier email, the GRUU would be formed as:

  sip:gruu.hex(<random-number>).base64(XOR(key, concat(aor-id,instance-id)))

In practice, these would end up looking like:

  <sip:gruu32B507FDAax7y0SUgVke7oovDDGvUg==@example.org>

It's not exactly concise (52 bytes, including the domain), but it is 
quite unlikely to cause problems. The advantage is that it requires no 
additional state storage by the registrar beyond the key itself.

/a

---

From: Paul Kyzivat <[email-masked]>
Date: Wed, 21 Mar 2007 12:47:39 -0400

Modulo odds and ends this looks workable to me. And it only needs to be 
an existence proof. There could be alternative implementations that are 
more space and/or time efficient.

	Paul

---

From: Jonathan Rosenberg <[email-masked]>
Date: Wed, 21 Mar 2007 13:38:40 -0400

This is an excellent idea, Adam. I think this works.

One more thing we need. We need to be able to invalidate temp-GRUU when 
the call-ID changes or the registration lapses. My proposal for that is 
that the server maintains, for each AOR and instance ID, a sequence 
number. This sequence number increments by one when a brand new 
registration is made for that AOR and instance ID, and when the call-ID 
changes for that AOR and instance ID. I'm not sure how many bits we need 
for this; it needs to be big enough that a very old GRUU can't be reused 
in the future by waiting for the counter to cycle. So, if you presume a 
rotation every half day, 16 bits is more than enough. A malicious user 
that rotates it more often just hurts themself, not anyone else.

You'd include this 16 bit seqno into the XOR, adding three more 
characters to the GRUU. When you receive a GRUU, extract the seqno. If 
it matches the current stored value, the GRUU is valid. If older, its 
invalid.

The drawback to this is that the registrar needs to store the instance 
IDs it has seen even after the registration for that instance ID 
expires. If a registrar can't validate instance IDs, this opens up a DoS 
attack where I send lots of registers to fill up the table with instance 
IDs. Easiest way to handle this is to limit the number of instance IDs 
for a particular user.

-Jonathan R.

---

From: Adam Roach <[email-masked]>
Date: Wed, 21 Mar 2007 18:59:24 +0100

Okay, so you're proposing something like:

  sip:gruu.base64(concat(random-number,sequence-number,XOR(key, 
concat(aor-id,instance-id))))

With an example of:

  sip:gruuRNGBTJA/McBVMV/YKP42ALY6Zy3eyg==@example.org

(assuming 32-bit random numbers and 16-bit serial numbers) That's still 
52 characters (with the savings from moving the sequence number into the 
base-64, at Paul Kyzivat's suggestion)...

/a

Jonathan Rosenberg wrote:
> One more thing we need. We need to be able to invalidate temp-GRUU 
> when the call-ID changes or the registration lapses. My proposal for 
> that is that the server maintains, for each AOR and instance ID, a 
> sequence number. This sequence number increments by one when a brand 
> new registration is made for that AOR and instance ID, and when the 
> call-ID changes for that AOR and instance ID. I'm not sure how many 
> bits we need for this; it needs to be big enough that a very old GRUU 
> can't be reused in the future by waiting for the counter to cycle. So, 
> if you presume a rotation every half day, 16 bits is more than enough. 
> A malicious user that rotates it more often just hurts themself, not 
> anyone else.
>
> expires. If a registrar can't validate instance IDs, this opens up a 
> DoS attack where I send lots of registers to fill up the table with 
> instance IDs. Easiest way to handle this is to limit the number of 
> instance IDs for a particular user.
>
> -Jonathan R.
>
> Adam Roach wrote:
>
>>>> The problem is that it opens up a state exhaustion attack in which 
>>>> I register ever 20 milliseconds instead of every 3600 seconds. Yes, 
>>>> you'll know it's me (or someone who has compromised my account), 
>>>> but the only recovery path likely is rebooting the server or hoping 
>>>> that the server has some kind of very fancy administrative nerd 
>>>> knob that allows release of GRUU state sequence numbers.
>>>
>>>
>>> doesn't get a new temp-gruu, it gets one it already had. But odds 
>>> are it has a few stored up anyway.
>>>
>>> Another similar option is to time-bound these also; say, to two 
>>> weeks. This would preclude a dialog being up for two weeks. A client 
>>> with a really long-lived subscription would have to terminate and 
>>> resubscribe every two weeks. Not a huge deal IMHO but it would be a 
>>> limitation. To deal with time sync, the server keeps them around for 
>>> two weeks and a day, so you really never run into a race failure.
>>>
>> After giving this some more thought, I think the solution may lie in 
>> the direction of using a *random* number (not a sequence number) for 
>> the part that's visible, and then using a subset of bytes from a 
>> crypto hash of this random number plus a server secret for your xor 
>> operation.
>>
>> quite unlikely to cause problems. The advantage is that it requires 
>> no additional state storage by the registrar beyond the key itself.
>>
>> /a
>>
>

---

From: Adam Roach <[email-masked]>
Date: Wed, 21 Mar 2007 19:15:33 +0100

> instance IDs for a particular user.

This seems to be a serious drawback. Can't we avoid this (with a 
probability of 1:65536) by selecting the starting serial number for a 
new instance at a random number instead of 0? If those odds aren't good 
enough, making the seqno 32-bits long would *certainly* be good enough 
(and add only three more characters, for a total of 55 in my example).

Something else to keep in mind is that we probably need to describe this 
approach in an *exemplary* fashion, not a normative one -- we should 
allow implementations to have variations on the theme where it makes 
sense for them (e.g., 32-bit identifiers where they make sense, 
variations in hash algorithms, etc.)

/a

---

From: "Jeroen van Bemmel" <[email-masked]>
Date: Wed, 21 Mar 2007 19:44:33 +0100

This whole discussion is exactly following my line of thought, with one 
difference

I was thinking to mix in a hash of the call-id (say 32 bits), rather than a 
sequence number. This avoids having to maintain extra state, and gets what 
you want: the temp GRUU is valid exactly as long as the call-id associated 
with the registration is valid. The latter needs to be stored already anyway

Regards,
Jeroen

Adam Roach wrote:
>> The drawback to this is that the registrar needs to store the
>> instance IDs it has seen even after the registration for that
>> instance ID expires. If a registrar can't validate instance IDs,
>> this opens up a DoS attack where I send lots of registers to fill up
>> the table with instance IDs. Easiest way to handle this is to limit
>> the number of instance IDs for a particular user.
>
> new instance at a random number instead of 0? If those odds aren't
> good enough, making the seqno 32-bits long would *certainly* be good
> enough (and add only three more characters, for a total of 55 in my
> example).
> Something else to keep in mind is that we probably need to describe
> this approach in an *exemplary* fashion, not a normative one -- we
> should allow implementations to have variations on the theme where it
> makes sense for them (e.g., 32-bit identifiers where they make sense,

---

From: Jonathan Rosenberg <[email-masked]>
Date: Thu, 22 Mar 2007 04:53:50 -0400

I talked to Ekr about this after the plenary, and he had a better, much 
simpler approach that I think works very well.

The idea is that, for each registration for a particular AOR and 
instance that is currently active, the server will have a hashkey. The 
hashkey is some number of bits, say 64. You hash this hashkey into a 
hashtable and it gives you the current AOR and instance ID and/or its 
registration contents.

When the call-id changes, you pick a new hashkey. When the registration 
expires, you remove the hashkey from the hashtable.

A temp-gruu is constructed as:

sip:gruu.<encrypt(hashkey, random number)>

So when the proxy receives a request with the gruu prefix, it decrypts 
the rest, and gets the hashkey, discarding the random number. If it 
exists in the hashtable, it is a valid temp gruu, and it is bound to the 
AOR/instance ID that comes out of the hash table. If its not in the 
hashtable, the temp-gruu is invalid.

This approach doesn't constrain the number of temp-gruu in any way, or 
require the registrar to store or limit the set of instance IDs, or 
remember past instance IDs, past call-ids, or whatever.

Most likely this is easily done by adding another column to tables that 
existing registrars already have.

Ekr agreed to propose a specific 'encrypt' function, so we can measure 
how big the resulting gruu are. The good news is that the hashkey can 
probably be something like 64 bits, random number around 64, and I'm 
hopeful there is something that can encrypt a 128 bit value without much 
expansion. The main thing is that this is a 'real' encryption algorithm 
with the property that you can't correlate two pieces of ciphertext to 
each other as having similar plaintext. A lot of our complexity in the 
previous proposals was the problem that XOR as an encryption technology 
doesn't have this property.

Comments?

-Jonathan R.

Jeroen van Bemmel wrote:

> I was thinking to mix in a hash of the call-id (say 32 bits), rather 
> than a sequence number. This avoids having to maintain extra state, and 
> gets what you want: the temp GRUU is valid exactly as long as the 
> call-id associated with the registration is valid. The latter needs to 
> be stored already anyway
> 
> Regards,
> Jeroen
> 
> Adam Roach wrote:
>

---

From: EKR <[email-masked]>
Date: Fri, 23 Mar 2007 00:41:40 -0700

OK, here's my suggestion for how to do this:

- Each (AOR,instance-id,call-id) triplet gets assigned a unique 
  identifier I.
- You build a separate hash table which maps I values to 
  registrations. If the call-id corresponding to I_i
  changes, delete I_i, generate I_j, and then insert 
  I_j into the table pointing to the registration record.

I propose that I be 48 bits long and assigned as a counter, with the
current counter value stored wherever you store the registration table
(thus assuring uniqueness for the life of the registration table).
Note that if you have some kind of clustered system you can rob
the top bits for a per-server disambiguator.

You need to have a pair of local symmetric keys K_e and K_a. These are
generated afresh every time the counter is reset. This allows you
to separate GRUU values generated with counters that overlap,
e.g., if you destroy all your state and reset the counter.

In order to generate a temp GRUU, you generate a random 80-bit 
distinguisher value D. Then compute:

              M = D || I.
              E = AES-ECB-Encrypt(K_e, M)
              A = HMAC-SHA256-80(K_a, E)

      Temp-GRUU = E || A

This produces a 26-byte GRUU, with 80 bits of integrity check.

When you receive a temp GRUU, you compute:

             A' = HMAC-SHA256-80(K_a, E)

If A' != A, you reject the GRUU, so this gives you a false accept
probability of 2^(-80). You then compute:

              M = AES-ECB-Decrypt(K_e, E)

Remove D to recover I and look up I in the hash table. If it exists,
you've found the relevant registration, otherwise you reject.

This design will allow you to do 2^48 (10^14) separate (AOR,
instance-id, call-id) triplets, which is consistent with something like
10^9 AORs, 10 call-ids/AOR, and 10000 call-ids/device. It's possible
that you might exceed either of the latter two limits for individual
devices, but it's doubtful you'd exceed this limit as a whole. [0]. It
will allow you to issue 2^40 GRUUs/I, which is of course ridiculously
high.  [[NOTE: I'm optimizing for maximum distinguishing here, but we
could slide this boundary to like 2^56 I values]].

-Ekr

[0] And of course if you *do* overflow, there are techniques for dealing
with this, such as rolling the key and lengthening the MAC a bit

---

From: "Jeroen van Bemmel" <[email-masked]>
Date: Sat, 24 Mar 2007 12:38:19 +0100

I think this can work. Key thing seems to be to limit the number of bytes 
that get encrypted / signed, could provide some guidance on reasonable 
lengths in the draft

Regards,
Jeroen

EKR wrote:
> instance-id, call-id) triplets, which is consistent with something
> like 10^9 AORs, 10 call-ids/AOR, and 10000 call-ids/device. It's
> possible that you might exceed either of the latter two limits for
> individual devices, but it's doubtful you'd exceed this limit as a
> whole. [0]. It will allow you to issue 2^40 GRUUs/I, which is of
> course ridiculously high.  [[NOTE: I'm optimizing for maximum
> distinguishing here, but we could slide this boundary to like 2^56 I
> values]].
>
> -Ekr
>
> [0] And of course if you *do* overflow, there are techniques for
> dealing with this, such as rolling the key and lengthening the MAC a
> bit

---

From: Jonathan Rosenberg <[email-masked]>
Date: Tue, 27 Mar 2007 10:00:31 -0400

This looks good to me too. A couple of questions inline.

> the top bits for a per-server disambiguator.

OK, so there is no requirement for sequential assignment per se. I'm 
guessing the sequence number vs. random number is just to reduce the 
space required for collision avoidance?

> e.g., if you destroy all your state and reset the counter.

WHat happens when the counter naturally rolls over? I think you'd need 
to retain the old keys, since the old GRUU assigned somehwere in the 
previous SN space remain valid. SO then you'd need to decrypt with old 
and new keys to figure out which one was in use. We'd also need to 
assume that the rollovers happen infrequently enough (like once a year) 
that we wouldn't have temp-gruu which survive two rollovers.

>               A = HMAC-SHA256-80(K_a, E)

FOr the crypto-ignorant - what is AES-ECB-Encrypt? And how long is E and 
A respectively?

> This produces a 26-byte GRUU, with 80 bits of integrity check.

26 bytes with or without the check? Before or after base64?

> you've found the relevant registration, otherwise you reject.

Looks good overall.

> could slide this boundary to like 2^56 I values]].

Does the initial value for I need to be random? I'm not sure if you are 
depending on any randomization aspects of this value for security 
(doesn't look like it but want to be sure).

-Jonathan R.

---

From: EKR <[email-masked]>
Date: Tue, 27 Mar 2007 08:38:23 -0700

Jonathan Rosenberg <[email-masked]> wrote:

> >   changes, delete I_i, generate I_j, and then insert   I_j into the
> > table pointing to the registration record.

Yep. We might be able to move this boundary to 56 or 64 bits, but I
wanted to make sure there was enough room so that even if someone
reregistered a ridiculous # of times it woul dbe OK.

> previous SN space remain valid.

Yeah.

> SO then you'd need to decrypt with old
> and new keys to figure out which one was in use.

Yes, or stick a demux on the front.

> We'd also need to
> assume that the rollovers happen infrequently enough (like once a
> year) that we wouldn't have temp-gruu which survive two rollovers.

Yep.

> FOr the crypto-ignorant - what is AES-ECB-Encrypt? 

Encrypt with AES in cipher-block-chaining mode.

> And how long is E
> and A respectively?
 
16 bytes and 10 bytes

> 26 bytes with or without the check? Before or after base64?

Before.

> Does the initial value for I need to be random? I'm not sure if you
> are depending on any randomization aspects of this value for security

No, you can just start with 0.

-Ekr

---

From: [email-masked]
Date: Thu, 29 Mar 2007 09:54:38 -0500

From: EKR <[email-masked]>

I admit this isn't my area of expertise, but don't you mean "AES in
electronic-code-book mode"?

Dale

---

From: EKR <[email-masked]>
Date: Thu, 29 Mar 2007 07:56:10 -0700

> electronic-code-book mode"?

Gah, yes. I'm so used to writing CBC that my brain slipped.

-Ekr

---

From: Jonathan Rosenberg <[email-masked]>
Date: Thu, 29 Mar 2007 12:50:34 -0400

OK, I fixed in my working text.

-Jonathan R.