From d8a65536ecc6eae026898822b58f520f5ee25ac7 Mon Sep 17 00:00:00 2001 From: Jacob Erlbeck Date: Thu, 15 Jan 2015 18:51:31 +0100 Subject: sgsn: Fix P-TMSI generator's distance of equal values Currently sgsn_alloc_ptmsi uses rand() to get a new P-TMSI and then sets to upper 2 MSB. Therefore there is no lower limit of the distance between 2 identical P-TMSI. This patch changes the implementation to discard any random value above 2^30 and to generate a new random number in that case until a fitting number is found (or a repetition limit is reached). This way, all number below 2^30 within the PRNG's period are used. Ticket: OW#1362 Sponsored-by: On-Waves ehf --- openbsc/src/gprs/gprs_sgsn.c | 28 ++++++++++++++++++++++++++-- 1 file changed, 26 insertions(+), 2 deletions(-) diff --git a/openbsc/src/gprs/gprs_sgsn.c b/openbsc/src/gprs/gprs_sgsn.c index f3da0387a..6f706642d 100644 --- a/openbsc/src/gprs/gprs_sgsn.c +++ b/openbsc/src/gprs/gprs_sgsn.c @@ -403,10 +403,34 @@ uint32_t sgsn_alloc_ptmsi(void) { struct sgsn_mm_ctx *mm; uint32_t ptmsi; - int max_retries = 23; + int max_retries = 100; restart: - ptmsi = rand() | 0xC0000000; + ptmsi = rand(); + /* Enforce that the 2 MSB are set without loosing the distance between + * identical values. Since rand() has no duplicate values within a + * period (because the size of the state is the same like the size of + * the random value), this leads to a distance of period/4 when the + * distribution of the 2 MSB is uniform. This approach fails with a + * probability of (3/4)^max_retries, only 1% of the approaches will + * need more than 16 numbers (even distribution assumed). + * + * Alternatively, a freeze list could be used if another PRNG is used + * or when this approach proves to be not sufficient. + */ + if (ptmsi >= 0xC0000000) { + if (!max_retries--) + goto failed; + goto restart; + } + ptmsi |= 0xC0000000; + + if (ptmsi == GSM_RESERVED_TMSI) { + if (!max_retries--) + goto failed; + goto restart; + } + llist_for_each_entry(mm, &sgsn_mm_ctxts, list) { if (mm->p_tmsi == ptmsi) { if (!max_retries--) -- cgit v1.2.3