Session ID Management Strategies in Routers

[Emile Cormier]

Hi Everyone,

I'm currently working on a C++ WAMP router implementation and need advise concerning the management of session IDs. According to the spec, session IDs must be random and globally unique. Is there a PRNG out there (in the range of 48 to 52 bits) that is guaranteed to not repeat any numbers given any random seed?

My current strategy is to use a 64-bit PRNG and clear the most significant bits to keep the result within integers than can be represented exactly in a 64-bit IEEE floating-point number. Because of the bit clearing, there can be duplicate random numbers. I therefore keep track of the session IDs currently in use in what I call a "session ID pool". If the clamped PRNG produces a duplicate id already reserved in the pool, I discard it and pick another one.

I would prefer to do away with my session ID pool and use a PRNG that is guaranteed to produce no duplicates given any seed. Is there such a thing available?

Cheers,

Emile Cormier

CppWAMP author

[Emile Cormier]

I've found this Stack Exchange question which is similar to mine.

The accepted answer proposes to use a block cypher, but this Stack Overflow answer says there aren't any well-known good ones for 48-bit.

Another answer proposes a linear-feedback shift register (LFSR) with custom taps, but LFSRs are easy to predict.

Another possibility could be using format-preserving encryption and feed it a sequence of numbers, but it's not clear if duplicate numbers would result. I only found one C implementation of FFP1/FPP3 and it has a dependency on OpenSSL which I'm trying not to impose on my users.

Without expert-level knowledge of encryption algorithms, I guess I'm better off sticking with a well-known and secure 64-bit PRNG and simply keeping track of the session IDs in use.

I was just curious if there was an easy and secure way of generating 48-bit random numbers without duplicates, and it's no big deal if there's no easy solution.

[Tobias Oberstein]

Hi Emile,

> According to the spec, session IDs must be random and globally unique.

The spec doesn't require global uniqueness, only

"IDs in the global scope MUST be drawn randomly from a uniform
distribution over the complete range [1, 2^53]"

https://wamp-proto.org/wamp_bp_latest_ietf.html#name-ids

But actually I think the spec is really lacking, "global scope" might be
misleading, and in any case, it's nowhere explained.

If you need a globally unique session ID that is unique both in space
and in time, 53 bits aren't enough.

Practically, 128 bits should be fine, and one way to derive such a "long
term unique session ID" would be

SHA(session_id | session_started)

with session_started being the time the session joined on the router,
and SHA be SHA1 or SHA256 truncated to 128 bits, and | be the
concatenation of bytes.

Do you think discussing this stuff in the spec would be worth?

> I would prefer to do away with my session ID pool and use a PRNG that is
> guaranteed to produce no duplicates given any seed. Is there such a
> thing available?

A PRNG will necessarily repeat itself sooner or later (this time is
called the "period of the PRNG").

Since a PRNG run-time state is finite, how could it not repeat?

For run-time < period(PRNG), you can of course demand that no single
output repeats (this is different from the output sequence repeating,
which happens when the same internal state is encountered).

You can make any PRNG behave like this. You'll need period(PRNG) more
memory to store all output as internal state and then skip duplicates.

Of course the resulting program is "less random" than the original;)

Cheers,
/Tobias

[Emile Cormier]

On Friday, December 30, 2022 at 12:01:55 AM UTC-4 tobias wrote:

Hi Emile,

> According to the spec, session IDs must be random and globally unique.

The spec doesn't require global uniqueness, only

"IDs in the global scope MUST be drawn randomly from a uniform
distribution over the complete range [1, 2^53]"

https://wamp-proto.org/wamp_bp_latest_ietf.html#name-ids

Sorry, I meant "global scope" and I intend for session ids to be unique across all realms hosted by the router to facilitate logging (no duplicate session ids from different realms appearing in the log during the router's run time). I anonymize the session ids in the log using SHA256.

 

But actually I think the spec is really lacking, "global scope" might be
misleading, and in any case, it's nowhere explained.

Indeed, "global scope" should have an explanation in the spec.

 

If you need a globally unique session ID that is unique both in space
and in time, 53 bits aren't enough.

I only need them to be unique during the run time of the router. If a session is spawned every millisecond, it would take around 285 thousand years to exhaust all 2^53 unique IDs.

 

Practically, 128 bits should be fine, and one way to derive such a "long
term unique session ID" would be 

SHA(session_id | session_started)

with session_started being the time the session joined on the router,
and SHA be SHA1 or SHA256 truncated to 128 bits, and | be the
concatenation of bytes.

Well, session IDs are required to be in the range [1, 2^53] as you've mentioned previously, but I get what you're suggesting. :-) I think a problem with deriving session IDs from system time is that an attacker could possibly guess them.

 

Do you think discussing this stuff in the spec would be worth?

Except defining "global scope" and such, I don't really know, sorry.

 

> I would prefer to do away with my session ID pool and use a PRNG that is
> guaranteed to produce no duplicates given any seed. Is there such a
> thing available?

A PRNG will necessarily repeat itself sooner or later (this time is
called the "period of the PRNG").

Since a PRNG run-time state is finite, how could it not repeat?

It is my understanding that the cycle period of "good" PRNGs are orders of magnitude larger than their output space.

 

For run-time < period(PRNG), you can of course demand that no single
output repeats (this is different from the output sequence repeating,
which happens when the same internal state is encountered).

You can make any PRNG behave like this. You'll need period(PRNG) more
memory to store all output as internal state and then skip duplicates.

That's what I'm currently doing, but was hoping there was an easy way of not having to keep track of duplicates (not that keeping track is difficult). The memory required for keeping track of currently used session IDs is negligible compared to the memory needed to manage those active sessions. Keeping track of all session IDs ever used during runtime would be equivalent to a memory leak!

[Tobias Oberstein]

> Practically, 128 bits should be fine, and one way to derive such a
> "long
> term unique session ID" would be
>
>
> SHA(session_id | session_started)
>
> with session_started being the time the session joined on the router,
> and SHA be SHA1 or SHA256 truncated to 128 bits, and | be the
> concatenation of bytes.
>
>
> Well, session IDs are required to be in the range [1, 2^53] as you've
> mentioned previously, but I get what you're suggesting. :-) I think a
> problem with deriving session IDs from system time is that an attacker
> could possibly guess them.

yeah, to be more preceise, my suggestion is:

1. keep session_id as it is today
2. in a router implementation, track session_joined_at
3. have a new session_guid computed as SHA(session_id | session_joined_at)

Those new per-session attributes

session_joined_at
session_guid

may or may not be included in session details sent by the router to peer
at join time.

And those attributes could then also be used in router storage or
integration across routers etc

>
> Do you think discussing this stuff in the spec would be worth?
>
>
> Except defining "global scope" and such, I don't really know, sorry.

Filed as https://github.com/wamp-proto/wamp-proto/issues/429

>
> > I would prefer to do away with my session ID pool and use a PRNG
> that is
> > guaranteed to produce no duplicates given any seed. Is there such a
> > thing available?
>
> A PRNG will necessarily repeat itself sooner or later (this time is
> called the "period of the PRNG").
>
> Since a PRNG run-time state is finite, how could it not repeat?
>
>
> It is my understanding that the cycle period of "good" PRNGs are orders
> of magnitude larger than their output space.

Ok, I guess I'm on a different page then: after a cycle, the next output
and all subsequent are repeating the previous period. That's the
definition of period. IOW: every PRNG is producing cyclic output.

In fact, every Turing machine with repeated finite input is cyclic. I
think;)

How could a finite thing unfold and produce infinite non-cyclic output?

[Emile Cormier]

On Friday, December 30, 2022 at 2:07:41 AM UTC-4 tobias wrote:

> It is my understanding that the cycle period of "good" PRNGs are orders
> of magnitude larger than their output space.

Ok, I guess I'm on a different page then: after a cycle, the next output
and all subsequent are repeating the previous period. That's the
definition of period. IOW: every PRNG is producing cyclic output.

PRNGs are indeed cyclic, I'm not denying that. It's just that good ones like PCG will have a cycle of like 2^128, so our sun will explode before the sequence repeats!

[Tobias Oberstein]

Am 30.12.22 um 07:23 schrieb Emile Cormier:

yes, but you are asking for sth much more restrictive: the PRNG output
sequence when chunked into fixed N-length blocks won't have blocks repeated

think about it: set N=1 and toss a coin, say it turns out "number". The
next sample MUST be "heads", because of no N-repeats. more over: what's
happening with 3rd toss? "side"? ;)

>
> --
> You received this message because you are subscribed to the Google
> Groups "WAMP" group.
> To unsubscribe from this group and stop receiving emails from it, send
> an email to wampws+un...@googlegroups.com
> <mailto:wampws+un...@googlegroups.com>.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/wampws/0db15da6-d208-4a1e-9313-82b4a56f71ben%40googlegroups.com <https://groups.google.com/d/msgid/wampws/0db15da6-d208-4a1e-9313-82b4a56f71ben%40googlegroups.com?utm_medium=email&utm_source=footer>.