I feel an urge to re-iterate few points - see below. N. B: I'm talking about concrete code available in gerrit. On 05.10.2017 13:09, Neels Hofmeyr wrote: It still won't block. See https://gerrit.osmocom.org/#/c/1526/ Not sure either way: the attacker should deplete entropy faster than kernel gathers it. Also, it's irrelevant for RAND_bytes() vs getrandom() discussion: both use the same entropy pool, both will generate "not good enough" random bytes if out of entropy. So the context for this part of the discussion is in: https://gerrit.osmocom.org/#/c/3819/ https://gerrit.osmocom.org/#/c/3820/ https://gerrit.osmocom.org/#/c/3821/ Meaning: what do we do if we don't get "random enough" data? So far we've just logged it and carried on with insecure rand(). Could/should we do better? Should we fail? Should we let user decide via config option? I think it's more of an academic exercise at this point: even if our tests would show that we can't deplete it, it doesn't mean that attacker couldn't come up with better ways. So we should decide what should be done when this happens. So far the decision was to "log and forget". Should we change it? No, we don't. See https://gerrit.osmocom.org/#/c/1526/ The patch was initiated by the need to fix licensing issue, so it preserves all the properties of original code: - it does not block - it uses insecure random Since we're touching this part of the code anyway, we might also change the way we treat entropy depletion. But, it's somewhat orthogonal to the use of getrandom(): we can change the way we deal with RAND_bytes() failure in another unrelated patch series. Using getrandom() is not introducing any problems with the random data which are not already there. It also does not fix any of them. It's good that discussion around it attracted our attention to those problems but I think we should keep in mind that those are related but different issues. -- Max Suraev <msuraev(a)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

On 05.10.2017 14:40, ringsignature(a)riseup.net wrote: More like incomplete. We use it with *GRND_NONBLOCK parameter to make sure it never blocks.* Out of curiosity - is there a way to check for this programmatically? Not that I know of. Is it some sort of a program or some kernel sysctl knob? -- Max Suraev <msuraev(a)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 RS, On Thu, Oct 05, 2017 at 12:40:11PM +0000, ringsignature(a)riseup.net wrote: We of course have no idea on what systems people are using the related osmocom components on (such as OsmoNITB, OsmoMSC, OsmoSGSN). For some of the smaller / deeper embedded devices (like e.g. the sysmoBTS 1002) for sure there is no hardware random number generator and interrupts are the only source of randomness. However, in most realistic scenarios you would have more than one BTS and run the NITB/MSC/SGSN on some kind of (embedded?) x86 or ARM board, and most systems have had hardware random number generators for quite a long time. Yes, the question is whether you trust those, but that's completely off-topic here in this thread. Regards, Harald -- - Harald Welte <laforge(a)gnumonks.org> http://laforge.gnumonks.org/ ============================================================================ "Privacy in residential applications is a desirable marketing option." (ETSI EN 300 175-7 Ch. A6)

Hi RS, On Thu, Oct 05, 2017 at 11:16:45PM -0700, ringsignature(a)riseup.net wrote: Technically, it would of course make sense, and conceptually it's a great idea. However, specifically on the sysmoBTS (as some other devices we support), the proprietary PHY (and hence any part that directly obtains baseband samples) runs on a separate DSP core. On osmo-bts using that PHY we only have access to figures like BER, RSSI, clock drift, burst arrival timing, ... It might be possible to use some of those for generating entropy, too - if proper care is taken to avoid situations where all of those parameters are controlled by an attacker, of course. For devices using osmo-trx (the SDR based implementation of a GSM PHY), the situation is different: OsmoTRX receives the baseband samples and is performing the radiomodem function on it. osmo-bts-trx then performs the bust demodulation/decoding. One could hence possibly add some module to either of the two (probably osmo-trx). However, the much higher CPU requirements of a osmo-trx + osmo-bts-trx setup require a larger/higher-end system (like embedded PC) to run the related code, and hence the probability of having a hardware randomness source is much higher than on the deeply embedded sysmoBTS or osmo-bts-octphy / osmo-bts-litecell15 devices which all run a proprietary PHY in a DSP. I think if it existed for osmo-bts-sysmo, we'd for sure use it. I'm still not sure if it's really worth the effort, given that most non-trivial setups typically have an external computer as BSC/NITB anyway, as stated below: Regards, Harald -- - Harald Welte <laforge(a)gnumonks.org> http://laforge.gnumonks.org/ ============================================================================ "Privacy in residential applications is a desirable marketing option." (ETSI EN 300 175-7 Ch. A6)

Hi RS, On Thu, Oct 05, 2017 at 05:20:21AM -0700, ringsignature(a)riseup.net wrote: Well, it probably depends on the interface the attacker has access to (Radio/Backhaul/...) and hence the threat model. A TMSI is allocated at many possible transactions, but all of them [should, in a sane implementation!] require authentication first, so it requires interactivity and is not just a simple flood. I think for all practical installations outside of an attack scenario that we know of, it's very little. We don't publish hardware requirements. We don't officially support or build test on anything but Ubuntu >= 16.04, Debian >= 8 and FreeBSD >= 10.3. We of course don't know what people decide to run the code on, in the end. Not our code. That's a task of the OS, no? Regards, Harald -- - Harald Welte <laforge(a)gnumonks.org> http://laforge.gnumonks.org/ ============================================================================ "Privacy in residential applications is a desirable marketing option." (ETSI EN 300 175-7 Ch. A6)

Hello, I conducted some simple experiments with small C program running on a quad core Intel(R) Core(TM) i5-2520M CPU. The program is in the body of this email. It utilized only a single core at full capacity. The test runs syscall(SYS_getrandom, &buf, bufsize, flags) in a while(1) loop. The bufsize is 512 (bytes) for each call to SYS_getrandom. The program measures the system entropy as SYS_getrandom is repeatedly called. As the program uses syscall() without #defines for getrandom(), I #defined the flags manually. The name GRND_BLOCKONCE seemed appropriate though non-standard it meaningfully describes the defined behavior. The two flags I tested were: #define GRND_BLOCKONCE 0 #define GRND_RANDOM 0x0002 The first method of calling ensured that the syscall may block until the system entropy pool is initialized. It did not block on my machine as the entropy pool was initialized around two weeks ago at the last system boot. During a ~fifteen minute run with 412100000 iterations fetching 512 bytes per iteration, the entropy pool increased from ~3700 to ~3867. In another run over ~eleven minutes with 277200000 iterations, I found that the pool went from ~3920 to ~3727. During the second run, I suspect other software on my machine used the /dev/random device directly. In both cases, the output matches my expectation of a very large ratio for the estimated entropy bits to PRNG output bits. The core of the iteration was effectively this single line: actual_bytes_fetched = syscall(SYS_getrandom, &buf, bufsize, GRND_BLOCKONCE) The value of actual_bytes_fetched was always equal to the size of bufsize. It never underflowed. With GRND_BLOCKONCE, any concerns about intermittent blocking or a denial of service vectors through getrandom() should be be mitigated. GRND_BLOCKONCE seems ideal for TMSI generation even if an adversary were requesting (tens of) thousands of TMSIs a second. The second method of calling getrandom() was configured to use the actual bits of the random device pool as clarified in the documentation for getrandom(): GRND_RANDOM If this bit is set, then random bytes are drawn from the random source (i.e., the same source as the /dev/random device) instead of the urandom source. The random source is limited based on the entropy that can be obtained from environmental noise. If the number of available bytes in the random source is less than requested in buflen, the call returns just the available random bytes. If no random bytes are available, the behavior depends on the presence of GRND_NONBLOCK in the flags argument. The core of the iteration was the same with only a different flag set: actual_bytes_fetched = syscall(SYS_getrandom, &buf, bufsize, GRND_RANDOM) The value of actual_bytes_fetched varied at every iteration and did often underflow. The ratio of entropy pool bits to output bits appears to be closer to one to one. It does not seem ideal to use GRND_RANDOM for TMSI generation, especially if a possible adversary is the requesting party - they would seem to be able to drain the device entropy pool very quickly. If this mode was used and it is configured to be non-blocking, it seems that it could fail very badly. After running the above tests and reading the related documentation, my conclusion is that it would be reasonable to use syscall(SYS_getrandom, &buf, bufsize, 0) as a suitable replacement for rand() in all cases without any concrete security or performance concerns. The overhead is also significantly less than importing or otherwise depending on OpenSSL, GnuTLS, NaCL, or probably even glibc. It may make sense to use the platform's libc interface if it is available. It may also be worthwhile to try to ensure that buffer is indeed changed. The small program below could also easily be modified to test that the buffer is indeed completely filled with some new data and to additionally hash the buffer before use in any cryptographic application. Happy Hacking, RS /* * * This program is Free Software under the GPLv3. * Copyleft ringsignature 2017. * * Compile with: * gcc -Wall -std=c11 -o getrandom-exhaust getrandom-exhaust.c * * */ #define _GNU_SOURCE 1 #include <sys/types.h> #include <sys/syscall.h> #include <unistd.h> #include <stdio.h> #include <string.h> #define GRND_BLOCKONCE 0x0000 #define GRND_NONBLOCK 0x0001 #define GRND_RANDOM 0x0002 void pp(unsigned char *buf, uint s){ uint z = 0; for (z=0; z<s; z++){ printf("%x", buf[z]); } printf("\n"); } void ms(unsigned char *buf, uint s, unsigned char f){ memset(buf, f, s); } uint ea(void){ FILE *f; uint i = 0; int val = 0; f = fopen("/proc/sys/kernel/random/entropy_avail", "r"); if (f == NULL) { return -1; } i = fscanf(f, "%u", &val); if (i == EOF) { return -1; } fclose(f); return val; } void ppea(void) { uint e = -1; e = ea(); if (e != -1) { printf("Current entropy available: %u\n", e); } else { fprintf(stderr, "Error fetching currently available entropy!\n"); } } void pps(uint b, uint c) { printf("\e[1;1H\e[2J"); printf("getrandom status - byte size requested: %i iteration: %i\n", b, c); ppea(); } int main(void) { uint bufsize = 512; unsigned char buf[bufsize]; int actual_bytes = 0; int count = 0; int es = ea(); ms(buf, bufsize, 0x0); pps(actual_bytes, count); while (count != -1) { ms(buf, bufsize, 0x42); actual_bytes = syscall(SYS_getrandom, &buf, bufsize, GRND_BLOCKONCE); if (actual_bytes != bufsize) { pps(actual_bytes, count); printf("getrandom underflow!\n"); pp(buf, bufsize); } count++; if ( (count % 100000) == 0) { pps(actual_bytes, count); ms(buf, bufsize, 0x47); } } pps(actual_bytes, count); printf("Original entropy estimate: %i\n", es); return 0; }

On 2017-10-06 01:23, Harald Welte wrote: You're welcome. Thanks for writing Free Software! I really appreciate that your project is open to feedback from complete strangers! My program is not optimized in any sense and I re-ran my program for 0 to -1 iterations with the following outcome: time ./getrandom-exhaust getrandom status - byte size requested: 512 iteration: -1 Current entropy available: 2575 Original entropy estimate: 3338 real 170m44.814s user 3m50.836s sys 166m52.948s I think it would be interesting to run this on any supported system and see if the output is similar. All of the conclusions that I've reached are based on the notion that any decreases to the entropy pool are negligible. Furthermore that the entropy pool might increase during the attempted exhaustion process which is probably an unrelated systems side effect. In either case, it will never underflow and it will always return the requested number of bytes. I don't entirely disagree, however the third option creates a more complex case that I'm not sure is worth the trouble. I would very strongly resist the urge to believe that the raw device bits are _better_ than the output of the PRNG. The GRND_RANDOM flag will result in underflows of the entire systems entropy pool, which especially on an embedded system is a halt-and-catch-fire situation. The complexity around that failure mode might cause failures that are otherwise avoided entirely. I'd suggest someone examine the failure modes for glibc before making this decision. I expect it to be a completely sane interface which fails nicely - though, if it doesn't, we need to consider how it fails. Apparently it was a "long road" [0] [1] to supporting getrandom() in glibc. The 2.25 appears to be the first release to support getrandom(). Probably the most interesting thing of note for that version is "* The getentropy and getrandom functions, and the <sys/random.h> header file have been added." This almost suggests to me that getentropy() and a maximum buffer of 256 bytes is a reasonable interface to settle on. As further reading - the people implementing Rust's random [3] have the following view of the matter: Unix-like systems (Linux, Android, Mac OSX): read directly from /dev/urandom, or from getrandom(2) system call if available. OpenBSD: calls getentropy(2) FreeBSD: uses the kern.arandom sysctl(2) mib Windows: calls RtlGenRandom, exported from advapi32.dll as SystemFunction036. iOS: calls SecRandomCopyBytes as /dev/(u)random is sandboxed. PNaCl: calls into the nacl-irt-random-0.1 IRT interface. I'm not entirely sure of the best method for checking but I would expect something like this to at least fail safely in the event of a kernel failure: - allocate a fixed size buffer of 256 bytes which seems to be the most portable size among all the OS provided interfaces - memset the buffer with a known value such as #define THEMEASUREOFABYTE 0x47 - memcmp each byte of the buffer with THEMEASUREOFABYTE to ensure that each byte compared is the same - request that the OS or glibc or libc fills that same buffer with random bytes for the size of the buffer - ensure that the number of bytes written is equal to the requested size - memcmp each byte of the buffer with THEMEASUREOFABYTE to ensure that each byte compared is *not* the same - if anything has gone wrong, return -1 and 0 (is this correct?) - in one possible future, hash the buffer in place to conceal the raw outputs from the PRNG - return the number of bytes written to the buffer, return the buffer full of random bytes That may make a better unit test than an actual wrapper function. It seems that for portability, it's worth considering such a wrapper as it doesn't appear that every API has the same failure mode. There is of course the unfortunate side effect of removing all 0x47s from your buffer with such an approach, which leads to a suggestion of generating a single random byte, which well, it's 🐢🐢🐢 all the way down... :-) Such an implementation should be constant time and take into consideration other things that might leak the random data. I'm not sure if memcmp is ideal for that reason. I'll do some additional research/experimentation and share the results. For a 512 *bit* buffer, I think hashing with SHA512 would be a fine transformation. If the attacker can guess the input for an output of SHA512, there is a serious problem. In which case, the hashing might mitigate practical, casual exploitation of the problem. It might not, of course. For buffers that are 256 or 512 bytes, I think it could be hashed in two or four chunks but someone smarter than me should think about that strategy before drawing a final conclusion. There are strategies using block ciphers rather than hashing functions that might make sense for larger buffers. Such a block cipher would essentially become a user space RNG of a similar design to the one from djb that I shared in earlier in the thread. Once we're in block cipher territory, we're using additional memory, we increase complexity, we may also have concerns about internal key schedules, side channels, and so on. I suppose this is another open research question for me. I'm sure someone else knows an answer off hand but I'm not confident that I know how to do it correctly. Happy Hacking, RS [0] https://lwn.net/Articles/711013/ [1] https://sourceware.org/bugzilla/show_bug.cgi?id=17252 [2] https://doc.rust-lang.org/rand/rand/os/struct.OsRng.html

On 2017-10-06 12:50, Max wrote: Is there any reason that it isn't just called a single time on system startup? It should never again block after that point in time. A measurement that might be worth considering is if it blocks, ever, in practice? At least one of my Debian systems appears to ensure that the RNG is seeded before it has reached the run level where services run. Might that be the case here? Might it also be possible to call the wrapper for getrandom() at library init time as well as later when the random bytes are needed? Isn't it more error prone to handle errors and unfilled buffers than to block a single time? Seems tricky, though I agree that consistent behavior might be worth the trade off. If GRND_NONBLOCK ensures that no buffer is ever underfilled, that might be the middle ground that makes the most sense. That is my understanding as well. The key difference is that you were spot on about the pool being drained very seriously - to the point of underflowing, thus potentially encountering serious error states. Those error states might be a 512 byte buffer with only one random byte, for example. Happy Hacking, RS

Hello, On 2017-10-06 16:57, Max wrote: OK. That seems reasonable as a way of measuring if this is practically a problem on any production systems. If such a log message occurs, what would it mean to an end user? One might read that as those random bytes are less than ideal but beyond that, I'm not sure what it would mean in an actionable sense. Does it mean one shouldn't use an IMSI ki generated when that log message is emitted? If there is a library setup, a possible, but not certain, blocking call seems reasonable for the later promise of never blocking. It could even call the same function with a single argument change? I agree that it is slightly more complex, though I think the trade off might be worth considering. Though it sounds like you have considered it and your conclusions are all very reasonable. The documentation explicitly claims to never fail for 1 to 256 byte requests: If the urandom source has been initialized, reads of up to 256 bytes will always return as many bytes as requested and will not be interrupted by signals. No such guarantees apply for larger buffer sizes. For example, if the call is interrupted by a signal handler, it may return a partially filled buffer, or fail with the error EINTR. I think the failure on an embedded system is that the output is predictable. That's the Mining Your Ps and Qs issue all over again with GSM and related protocols. I'm curious about analysis of GSM and related protocols, specifically how they fail when there isn't sufficient entropy. Are there any useful survey papers on the topic that anyone could recommend? Ah - of course, in your patch for values of 1 to 256 bytes, I agree. The suggestion of using GRND_RANDOM does produce an occasional outcome where the buffer is less than the requested size, which does need to be handled. I think that for simplicity, it seems wise to avoid using GRND_RANDOM, regardless of the discussion around GRND_NONBLOCK. In the case of GRND_NONBLOCK, I generally agree. Understood, I agree that with GRND_NONBLOCK alone, getrandom() should both never block and never under fill a buffer of 256 bytes or less. I agree with the strategy of explicit control. Where we slightly diverge is that I would simply want to ensure that the RNG was initialized. My intuition is that on most modern systems, it will always be the case but for some embedded systems, it seems to be tempting fate. In those perhaps rare but perhaps serious cases, I think an initalizer function blocking once might save a lot of cryptographic headaches later. Yes, I agree. I'm not sure if this is portable to FreeBSD with the same guarantees, so checking seems prudent. Agreed. It is certainly better to terminate than to use insecure random numbers in the security sensitive context, especially if any of those bytes are used for anything that is long lived. The only other option is the one we've discussed and perhaps isn't worth while: initialize once in a blocking manner such that the above termination state should never happen in theory. Of course, you'll catch it when it happens in practice when it is caused by for some previously unconsidered factor. It might make sense to simply state that the OS handles this case but [0] suggests that such an approach fails badly. It's probably worse than the papers in public as those are simply the systems that attract open research and attention. Essentially, I think your conclusions are clear, and reasonable. I agree with you and I still worry that I don't have a way to measure the (probably obscure) failure case. I think this is actually a failure of the /dev/urandom interface - is any option unsafe? If so, why does it exist after so many years of failures from unsafe options? If the default is reasonably secure, it doesn't seem necessary to add a foot cannon. Thank you for all your work on this patch set and for discussing it in incredible detail. Happy Hacking, RS [0] https://factorable.net/weakkeys12.extended.pdf

I'm somewhat confused with the implementation details: placing fallback into library would mean we effectively duplicate the fallback logic: the library might or might not fallback and than the application will have to decide if it's ok with the fallback. I'd prefer to use secure only random in the library code and make insecure fallback a compile-time option in the application code. That way we can manage it on application or even case-by-case basis later on if we decide to drop it altogether. Although I might be missing smth, so looking forward for your feedback. On 07.10.2017 08:34, Harald Welte wrote: -- Max Suraev &lt;msuraev(a)sysmocom.de&gt; 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

On 2017-10-06 16:57, Max wrote: After rereading the relevant documentation, I realize that I misunderstood one critical point regarding GRND_NONBLOCK. The critical difference is that GRND_NONBLOCK controls not only blocking behavior, it also ensures that in the case of the system not being properly seeded, it fails closed by immediately returning -1 without outputting any random bytes. I apologize for completely missing this detail. It is of course the case that you are correct and if blocking is a problem, it is logical to set GRND_NONBLOCK and to handle the error case, especially by terminating. That is indeed a critical error and there should be no output. Happy Hacking, RS

On 2017-10-07 06:30, Harald Welte wrote: That suggests setting GRND_NONBLOCK for all calls except for generation of SIM card cryptographic keys, I think? In the latter case, setting a flag of '0' may be appropriate. After reading one of the latest [0] papers on the robustness of /dev/random, I think it would be wise to leave GRND_RANDOM out and only use urandom in a properly seeded state for such keys. That that paper does not inspire confidence in even that choice, sadly I don't see a better choice. Happy Hacking, RS [0] https://eprint.iacr.org/2013/338.pdf