randomness of identifiers
Dear all, Max has been pushing https://gerrit.osmocom.org/#/c/1526 for quite some time, but there was still no conclusion in its review. I guess after more than 8 months in limbo, it's about time we decide how to move ahead with this. In general, we *want* secure/safe identifiers like TMSIs that are not easy to predict by an attacker. Using rand() or some other pseudo-random generator with a predictible seed like the time of the process start is probably not the best choice here. Using the rather strong entropy pool of /dev/urandom or getrandom() is apparently not a good choice either: We can exhaust the entropy pool at whch point we would have to block/wait, which we of course cannot in our architecture. So what do we do? I think we first have to differentiate on the type of randomness needed. Is it a random identifier like TMSI? Is it a random challenge used in cryptographic authentication? Is it random data used for a key? Those require different levels of randomness. For TMSI allocation, my "cryptographic gut feeling"[tm] is that something like rand() or any other pseudo-random generator of significantly large period is sufficient *if* it is seeded by a non-predictable value. So something like seeding with getrandom() result should be fine? For random challenges in authentiation I would probably go for direct use of urandom / getrandom(). If the entropy is exhausted, the quality of the random numbers will get lower, but getrandom() will always return up t 256 bytes. For long-term stable key (Ki/Op) generation for provisioning SIM cards + populating a HLR, I would certainly opt for using stronger randomness sources. However, I don't think we actually implement that anywhere, do we? What do you guys think? Is there somebody on this list more cryptographically qualified to give us proper guidance? If you know somebody skilled who might want to help but is not on this list, would you invite them to join this discussion? -- - Harald Welte <laforge@gnumonks.org> http://laforge.gnumonks.org/ ============================================================================ "Privacy in residential applications is a desirable marketing option." (ETSI EN 300 175-7 Ch. A6)
On Wed, Sep 27, 2017 at 07:57:43PM +0800, Harald Welte wrote:
For TMSI allocation, my "cryptographic gut feeling"[tm] is that something like rand() or any other pseudo-random generator of significantly large period is sufficient *if* it is seeded by a non-predictable value. So something like seeding with getrandom() result should be fine?
Also matches my gut feeling there. Might also make sense to periodically re-seed from /dev/urandom / getrandom(), like every 100 TMSIs, or based on a timeout might be easier to implement.
For long-term stable key (Ki/Op) generation for provisioning SIM cards + populating a HLR, I would certainly opt for using stronger randomness sources. However, I don't think we actually implement that anywhere, do we?
what does openssh use for public/private keypair generation?
What do you guys think? Is there somebody on this list more cryptographically qualified to give us proper guidance? If you know somebody skilled who might want to help but is not on this list, would you invite them to join this discussion?
I don't count myself as one of them, help is still appreciated. ~N
Hi Neels, On Wed, Sep 27, 2017 at 06:06:48PM +0200, Neels Hofmeyr wrote:
On Wed, Sep 27, 2017 at 07:57:43PM +0800, Harald Welte wrote:
For TMSI allocation, my "cryptographic gut feeling"[tm] is that something like rand() or any other pseudo-random generator of significantly large period is sufficient *if* it is seeded by a non-predictable value. So something like seeding with getrandom() result should be fine?
Might also make sense to periodically re-seed from /dev/urandom / getrandom(), like every 100 TMSIs, or based on a timeout might be easier to implement.
I would try to avoid any predictability here. Having a fixed time interval would be known to an attackers. So if he was somehow able to reduce/exhaust the entropy at the known time for re-seeding, it would be bad. Similar for "every 100 TMSIs", which is something under control of any attacker as he can control the number of location updates via the public radio interface [to some extent] and thus control the time at whcih re-seeding is done. Maybe I'm going overboard here, but I think if you want to re-seed, you want to ideally do it at a non-predictable and non-controllable point in time. Like a random time interval ;)
For long-term stable key (Ki/Op) generation for provisioning SIM cards + populating a HLR, I would certainly opt for using stronger randomness sources. However, I don't think we actually implement that anywhere, do we?
what does openssh use for public/private keypair generation?
I'm not sure you can compare the requirements for generation of RSA public/private keys with those for generation of symmetric keys. You can find different recommendations in the literature. But I guess that's mainly due to the fact that people usually assume you have long-term stable public/private keys and short-lived symmetric session keys. In our case, it's long-lived symmetric keys. But as indicated, I think our focus is to find a proper solution for generation of TMSIs and for random numbers used in authentication challenges. K/OPc pair generation is not supported in current Osmocom tools anyway, as we presume the SIM cards already have sufficiently random key material and those keys are entered into the HLR. Regards, Harald -- - Harald Welte <laforge@gnumonks.org> http://laforge.gnumonks.org/ ============================================================================ "Privacy in residential applications is a desirable marketing option." (ETSI EN 300 175-7 Ch. A6)
On 27. Sep 2017, at 19:57, Harald Welte <laforge@gnumonks.org> wrote:
For TMSI allocation, my "cryptographic gut feeling"[tm] is that something like rand() or any other pseudo-random generator of significantly large period is sufficient *if* it is seeded by a non-predictable value. So something like seeding with getrandom() result should be fine?
GLIBC rand() maybe but "any other" not. E.g. if it is a Mersenne Twister than observing ~624 TMSIs could be enough to predict past and future state. Picking something like RAND_bytes of OpenSSL for TMSIs seems to be the best way. It will re-seed itself (and we are not forking). If the OpenSSL dependency is too bad (license compatibility, the move to the Apache license could help us here for GPLv3+ software) then maybe the second best option is to take a "Fortuna"[1] implementation from somewhere? holger [1] https://en.wikipedia.org/wiki/Fortuna_(PRNG)
Hi Holger, On Thu, Sep 28, 2017 at 12:04:04PM +0800, Holger Freyther wrote:
On 27. Sep 2017, at 19:57, Harald Welte <laforge@gnumonks.org> wrote:
For TMSI allocation, my "cryptographic gut feeling"[tm] is that something like rand() or any other pseudo-random generator of significantly large period is sufficient *if* it is seeded by a non-predictable value. So something like seeding with getrandom() result should be fine?
GLIBC rand() maybe but "any other" not. E.g. if it is a Mersenne Twister than observing ~624 TMSIs could be enough to predict past and future state.
thanks for your input.
Picking something like RAND_bytes of OpenSSL for TMSIs seems to be the best way. It will re-seed itself (and we are not forking).
Ok, then let's do that.
If the OpenSSL dependency is too bad (license compatibility, the move to the Apache license could help us here for GPLv3+ software)
Yes, the new apache-style license makes this less of a headache. So then we conclude for now: * TMSIs and other temp identifiers: openssl RAND_bytes() * random challenges for authentication: also RAND_bytes, or getrandom()? * secret key generation (which we don't implement, so far: ? Regards, Harald -- - Harald Welte <laforge@gnumonks.org> http://laforge.gnumonks.org/ ============================================================================ "Privacy in residential applications is a desirable marketing option." (ETSI EN 300 175-7 Ch. A6)
On 5. Oct 2017, at 15:35, Harald Welte <laforge@gnumonks.org> wrote:
Hi Holger,
Hi,
Picking something like RAND_bytes of OpenSSL for TMSIs seems to be the best way. It will re-seed itself (and we are not forking).
Ok, then let's do that.
Maybe to expand on the "forking" part. OpenSSL didn't (and might not do it right now) re-seed on fork. This created some security issues on other platforms (maybe the most noticeable was Android, e.g. two processes generating the same random numbers).
If the OpenSSL dependency is too bad (license compatibility, the move to the Apache license could help us here for GPLv3+ software)
Yes, the new apache-style license makes this less of a headache.
So then we conclude for now:
* TMSIs and other temp identifiers: openssl RAND_bytes() * random challenges for authentication: also RAND_bytes, or getrandom()? * secret key generation (which we don't implement, so far: ?
I would use RAND_bytes() in all of these cases
On 05.10.2017 09:35, Harald Welte wrote:
Yes, the new apache-style license makes this less of a headache.
The process of relicensing is not finished yet and it's unclear when it'll be. Also, I'm not sure when (if at all) newly licensed version will hit all the .deb distributions which we support.
So then we conclude for now:
* TMSIs and other temp identifiers: openssl RAND_bytes() * random challenges for authentication: also RAND_bytes, or getrandom()?
Both RAND_bytes() and getrandom() might fail to generate random data. Both use /dev/urandom and might deplete entropy pool. Both are non-blocking. RAND_bytes() creates licensing problem (which might be fixed eventually on some of the supported distributions). Which argument for preferring RAND_bytes() over getrandom() have I missed?
* secret key generation (which we don't implement, so far: ? Do we have any plans implementing it in foreseeable future?
-- Max Suraev <msuraev@sysmocom.de> http://www.sysmocom.de/ ======================================================================= * sysmocom - systems for mobile communications GmbH * Alt-Moabit 93 * 10559 Berlin, Germany * Sitz / Registered office: Berlin, HRB 134158 B * Geschaeftsfuehrer / Managing Director: Harald Welte
Hi. Thanks for bringing it up. I think some clarifications about the current implementation are required - see below. On 27.09.2017 13:57, Harald Welte wrote:
Using the rather strong entropy pool of /dev/urandom or getrandom() is apparently not a good choice either: We can exhaust the entropy pool at whch point we would have to block/wait, which we of course cannot in our architecture.
Note: current implementation available in https://gerrit.osmocom.org/#/c/1526/ will never ever block. It will fallback to insecure rand() if there's not enough entropy in the pool and let caller know about it. This is exactly what the existing code does.
So what do we do? I think we first have to differentiate on the type of randomness needed. Is it a random identifier like TMSI? Is it a random challenge used in cryptographic authentication? Is it random data used for a key? Those require different levels of randomness.
I think before adding all this complexity we should first check how realistic the entropy exhaustion in practice? The implementation in https://gerrit.osmocom.org/#/c/1526/ does not allow you to request more than 16 bytes of random data at once. And such requests could not come at arbitrary speed either - attacker have to trigger certain events which would result in random identifier generation. Linux kernel constantly gather entropy. Is it possible for an attacker to exhaust it faster than kernel gathers it? Also, it's important to remember that the consideration above are for "the ideal system we want to build". If we compare it with the current implementation, than https://gerrit.osmocom.org/#/c/1526/ can be merged right away: - it uses secure random data if it's available - it falls back to insecure random generator if not - it gives exactly the same log messages about it as the current code So there are actually 2 questions in here: - can we merge gerrit #1526? - can we do even better? IMHO, the answers are "yeah" and "should we?" :) -- Max Suraev <msuraev@sysmocom.de> http://www.sysmocom.de/ ======================================================================= * sysmocom - systems for mobile communications GmbH * Alt-Moabit 93 * 10559 Berlin, Germany * Sitz / Registered office: Berlin, HRB 134158 B * Geschaeftsfuehrer / Managing Director: Harald Welte
participants (4)
-
Harald Welte -
Holger Freyther -
Max -
Neels Hofmeyr