Hey RS, thanks for your excellent input on P/RNG! There's a lot in it, let me first off sprinkle a few remarks... On Thu, Oct 05, 2017 at 09:56:51AM +0000, ringsignature(a)riseup.net wrote: What about an attacker firing endless events that cause us to generate new TMSIs and ends up exhausting the entropy pool? AFAIK that's a real possibility? It might well be possible to use RF noise as entropy, but the HLR that is generating the RAND bytes is layers away from the BTS and its antenna. If all run on the same small integrated box, somehow getting RF noise from the DSP and feeding entropy to the system which in turn gets used on the other end by the HLR is a possibility, but not really when the HLR is, as by the usual GSM design, in a central location serving numerous cells. Would be interesting to run a few tests on how quickly we can end up in entropy exhaustion. Using getrandom() always would be the easiest and safest. Saying that we prefer to be quick rather than secure sounds wrong indeed. But if we practically block because of too little entropy, then we annoy lab / testing setups that don't care about security, and we provide a DoS attack vector. ~N

On 2017-10-05 11:09, Neels Hofmeyr wrote: I'm glad it may be useful. Could you quantify that? What is the process by which an attacker would be able to cause new TMSI generation? Does it require interactivity from them or can they simply flood OpenBSC with a packet that triggers a the creation of a TMSI? If such a flood is possible, that suggests a security problem at the least and a possible entropy problem. On the topic of exhausting the entropy pool: as long as a modern GNU/Linux system is properly seeded at boot, /dev/urandom is guaranteed to not block and to continue to emit cryptographically secure random numbers. The entropy post by djb discusses the trade offs of seed-once versus seed-many-times. I think it is reasonable to seed-once at system boot and to simply always use getrandom() with the assumption that you cannot exhaust the entropy pool. The Linux kernel version 3.16 appears to be when the kernel greatly improved with regard to the random interface. I think on many modern GNU/Linux systems (2017-03-13 RANDOM(4) says so), getrandom() will block until it is initialized: The /dev/random interface is considered a legacy interface, and /dev/urandom is preferred and sufficient in all use cases, with the exception of applications which require randomness during early boot time; for these applications, getrandom(2) must be used instead, because it will block until the entropy pool is initialized. In fact, internally in the kernel, it was once and should still be the case that the entropy pool is being constantly updated with timer and interrupt information, in addition to other sources. In a sense, there is no seed-once option - only a seed once with csprng source, then seed many times with other sources including possible csprng sources. Some of those inputs may be controlled or influenced by an attacker but such an attack would be against the entire /dev/random interface. That is definitely a good research project and I'm sure Professor Heninger is already working on it. With regard to the entire PRNG being broken, this is also why I suggested to hash or transform the output bytes, just in case, something is broken as a defense in depth strategy. If an attacker can break the PRNG and also predict the preimage of H(RandomBytes), then they probably don't need the RandomBytes in the first place and the RNG is almost certainly beyond salvation. This would have stopped the *practical* exploitation of DualEC in TLS but it almost certainly wouldn't stop another Debian OpenSSL fiasco. If one is not convinced by the notion that one 128bit or 256bit seed at boot is good for say, 2^64 outputs even with these internal reseeding operations, and you expect to use that many outputs, reseeding could be done with a userspace rng daemon to hardware bridge like rng-tools. There are a few free and open hardware designs such as the Gnuk (in the NeuG configuration) that can be re-purposed as a hardware RNG. I recall that the device specifically uses a trick with an ADC that can fail very badly. It seems to me that a properly designed RNG that is cheap to build and easy to buy would be very nice as a project too. Now down to the brass tacks: How much random data does OpenBSC currently use in a given period of time, say one day? Is it really larger than the theoretical limits of the outputs for /dev/urandom? What are the system requirements for OpenBSC with regard to a hardware rng or manual seeding? Does OpenBSC only run on Linux or BSD systems with the getrandom() interface? Does OpenBSC store random seed data between boots? Could someone share the value of /proc/sys/kernel/random/entropy_avail from a typical OpenBSC machine? Understood. As a slight digression: There was once some kind of Ubuntu cloud project [1] called Pollinate to solve this for virtual machines and other systems with no direct hardware entropy source. While that seems excessive for this situation, it's a reasonably good overview of how another project shares entropy over the network. Over HTTP there are raw bytes on the network, while over HTTPS it has the problem of needing entropy to start a secure TLS session. One option might be to ensure that the devices are seeded at install time, another might be to extend the already existing protocols to share entropy data from a system which has some, and another might just be to raise the default system requirements to include one or two RNG devices. There are many strategies that seem promising and all of them require around 128 or 256 bits of entropy at boot time, every boot. It would be surprising if one was able to exhaust it. I would expect an RF denial of service for local clients before I would expect the Linux /dev/urandom PRNG to output predictable sequences based on asking for random TIMSI data. Happy Hacking, RS [0] https://www.gniibe.org/memo/development/gnuk/rng/neug.html [1] http://people.canonical.com/~kirkland/Random%20Seeds%20in%20Ubuntu%2014.04%… [2] https://launchpad.net/pollen

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

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; }

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 &lt;laforge(a)gnumonks.org&gt; http://laforge.gnumonks.org/ ============================================================================ "Privacy in residential applications is a desirable marketing option." (ETSI EN 300 175-7 Ch. A6)

Hello, On 2017-10-06 01:03, Harald Welte wrote: Might those devices be interesting as a research target for generating entropy from a radio interface? The specification suggests that the device does indeed have a radio interface. If so, perhaps it would be a useful experiment for someone to attempt to create an OsmoEntropy subproject? I would be interested in undertaking such a project, if it would be useful and especially if it would be used. Understood. Happy Hacking, RS

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

Hi Max, On Fri, Oct 06, 2017 at 06:57:03PM +0200, Max wrote: I think it should be a compile time decision for now, and the default should be "no fallback". So basically the entire fallback code is #ifdef'd out unless somebody builds libosmocore with a possibly dangerous compile option and has a good reason to do so. If the user does that, there should be a related warning at the end of the ./configure step, and we should also print runtime WARNING level messages once we actually start to fallback to insecure rand(). -- - Harald Welte &lt;laforge(a)gnumonks.org&gt; http://laforge.gnumonks.org/ ============================================================================ "Privacy in residential applications is a desirable marketing option." (ETSI EN 300 175-7 Ch. A6)

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

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