Re: hap.random: a new random number library for D
On Thursday, 19 June 2014 at 21:27:17 UTC, Joseph Rushton Wakeling wrote: I realized that it ought to be possible to allow a more direct drop-in replacement for std.random by adding static opCalls to the classes which were previously structs. Thoughts on this, in favour, against ... ? I'd say do it and make it @deprecated ... in general, I think allowing a struct like constructor for a class is bad style (at least for std, anyway) and should be discouraged, but deprecating it makes it an easy upgrade initially and will make it easier for people to compare the old vs new way with their code.
Re: hap.random: a new random number library for D
On Wednesday, 11 June 2014 at 16:35:31 UTC, Kagamin wrote: In some scenarios impredictability is not enough. For example, when you generate a session id, an attacker doesn't have to predict it ahead of time, he can guess it at any time later. And if they listen to radio waves - that's an open protocol, an attacker can setup antenna near their antenna and get the same readings. Cryptographic PRNG and quantum TRNG are better isolated, so it's harder to read them. That's an interesting thought on a potential attack. I wouldn't say same readings but similar readings is possible and might make attacks easier. It might not be a bad idea as part of a solution though, since it can be used to supplement other sources of local-machine crypto-grade entropy (since often such sources are exhaustible). But yes, just straight up using it alone appears to have a few critical problems.
Re: hap.random: a new random number library for D
On Wednesday, 11 June 2014 at 06:41:34 UTC, Joseph Rushton Wakeling wrote: Done :) ... if I get a response, I'll make sure to incorporate everything said. Great, let me know how that goes. :-) Well, the ultimate conclusion of the conversation with the guy is that: 1. ISAAC probably isn't cryptographically secure. Despite not having found any attacks, it just isn't proof of security. It's not been looked at enough to really approve of its usage for that purpose (I'm kind of agreeing with this) 2. ISAAC in his opinion probably isn't appropriate for non secure uses for much the same reason. I don't agree with that because everything I've seen for ISAAC shows that it has some really good statistical properties. Even if it's not cryptographically secure, it appears to produce better pseudorandom numbers to me than something like MT19937 or Well* (and ISAAC is really fast after the initial cost has been paid back) Ultimately, I think ISAAC (and ISAAC-64) _will_ get more scrutiny in the future as it's a PRNG used in Rust, for instance. I would not suggest it for default purposes, but I think having it as a non-crypto RNG in D wouldn't be a bad idea for those who want to choose to use it. 3. Better ideas for crypto PRNGs are AES-CTR or Salsa20. I agree with this approach for the crypto section of std.random. I'd also suggest Blum Blum Shub as another thing to add. It's awfully slow, but it's probably one of the few PRNGs that is provably strong (that is, it's been reduced to a known hard problem). Also, he suggested me to refer to a presentation he made last year: http://aumasson.jp/data/talks/randomness_hackepfl13.pdf I've gone through it and it looks like excellent reference material. Note slide 76 saying: Don't use RaaS (things like random.org) - random bits may be shared or reused. Also, it has suggestions for entropy on Windows (CryptGenRandom) which is something that will be necessary as well. Overall, very enlightening.
Re: hap.random: a new random number library for D
On Thursday, 12 June 2014 at 17:35:39 UTC, Nick Sabalausky wrote: Naturally, it doesn't yet exist in hap.random because, as Joseph said, hap.random's step one is to match the current std.random as closely as possible. I'd be happy to put together a PR to adapt my RNG stuff above to hap.random whenever it would be desired. Wow! Looks great :) Thanks for all the work on that.
Re: hap.random: a new random number library for D
On Wednesday, 11 June 2014 at 06:41:34 UTC, Joseph Rushton Wakeling wrote: That would be very cool. Can you point me at your code examples? It's written in Nimrod (in a way that someone who learned Nimrod the day before would write them, because I learned Nimrod the day before and worked on it for something like 17 hours straight to produce everything): https://github.com/Zshazz/Ramrod/blob/master/util.nim I'd like to make this concept a range in D. Not sure what exactly to call it but it's an adaptor. Honestly, I wouldn't be surprised if something like this didn't already exist in D in some form, but it didn't seem like Nimrod had anything like it. The paranoiac in me feels that anything that involves getting random data via HTTPS is probably insecure crypto-wise :-) Paranoia is good in this case. I appreciate the caution. However, I think sourcing random.org is a perfect case for an entry in hap.random.device. I think the best thing to do would probably be to offer a RandomOrgClient (which offers a very thin API around the random.org HTTP API) and then to wrap that in a range type that uses the client internally to generate random numbers with particular properties. This sounds like it would be beautiful. As a note, if we expose this via a part of the standard library, we would have to make certain that we follow the guidelines outlined on random.org (in particular, I'm concerned about having an internal locking mechanism to prevent multiple threads from asking for bits at the same time because that will cause clients to be banned ... global state, impurity, and all the nasty things will likely have to be a natural part of such a thing). Also a very interesting suggestion. Is there a standard name for this kind of procedure? I'm not really aware if there is. I remember hearing about the concept when talking with my cryptography professor awhile back (it may have even been in a lecture). IIRC, the description used was mixing in entropy, so my first thought is to call it a mix/remix function. Just for clarity, here's how I see things rolling out for the future: * First goal is to ensure the existing codebase plays nice with people's programs and that it works OK with dub, rdmd, etc. and doesn't have any serious architectural or other bugs. The 1.0.0 release will not have any new functionality compared to what is in place now. * Once it seems to be reasonably stable then work can begin on a 1.x release series that brings in successive pieces of new functionality. I like this procedure. Definitely confidence inspiring.
Re: hap.random: a new random number library for D
Awesome! I'll definitely check this out :) Would there be any chance of additional contributions, such as an ISAAC RNG implementation, being accepted? I wouldn't go as far as to guarantee it for crypto purposes, but I've been messing around with an implementation recently and wouldn't mind porting it over to D (it's based on the public domain implementation found on this website: http://burtleburtle.net/bob/rand/isaacafa.html ) So far the numbers it puts out appear to be pretty good from my observations, PLUS it's really fast for a large number of outputs (it costs a lot up-front, however). I also have a variation of ISAAC+ as described by the paper here: http://eprint.iacr.org/2006/438.pdf The problem I have with ISAAC+, though, is that the paper incorrectly describes the original ISAAC algorithm (Algorithm 1.1 fails to `xor a` at line 6) so it's unclear whether the paper actually solves a problem. Furthermore, I'd really prefer to keep that xor regardless (because it may have simply been an oversight but intended) so it's hard (I don't want to) to really call it ISAAC+ since it is notably different than the paper's description. That said, it's a paper that comes up often enough in discussions about ISAAC that people suggest a desire for it.
Re: hap.random: a new random number library for D
Hey again Joe, I had an opportunity to give the entire code a good once over read and I have a few comments. 1. Biggest thing about the new hap.random is how much nicer it is to actually READ. The first few times I went through the current std.random, I remember basically running out of breath. hap.random was almost a refreshing read, in contrast. I'm guessing it has a lot to do with breaking it down into smaller, more manageable pieces. Regardless, good work on that. I suspect it'll make it easier to contribute to in the future. 2. Something I'd really like to see is for the seed-by-range functions to take the range by reference instead of by value to ensure that the seed values used are less likely to be used in another RNG inadvertently later. Basically, I envision a similar problem with seedRanges as we currently have with RNGs where we have to make sure people are careful with what they do with the ranges in the end. This should cover use cases where users do things like `blah.seed(myEntropyRange.take(3))` as well, so that might take some investigation to figure out how realistic it would be to support. 3. I'd also REALLY like to see seed support ranges/values giving ANY type of integer and guarantee that few bytes are wasted (so, if it supplies 64-bit ints and the generator's internal state array only accepts 32-bit ints, it should spread the 64-bit int across two cells in the array). I have working code in another language that does this, and I wouldn't mind porting it to D for the standard library. I think this would greatly simplify the seeding process in user code (since they wouldn't have to care what the internal representation of the Random state is, then). 4. I'd just like to say the idea of using ranges for seeds gets me giddy because I could totally see a range that queries https://random.org for true random bits to seed with, wrapped by a range that zeroes out the memory on popFront. Convenient and safe (possibly? Needs review before I get excited, obviously) for crypto purposes! 5. Another possible improvement would be something akin to a remix function. It should work identically to reseeding, but instead of setting the internal state to match the seed (as I see in https://github.com/WebDrake/hap/blob/master/source/hap/random/generator.d#L485), remixing should probably be XOR'd into the current state. That way if you have a state based on some real entropy, you can slowly, over time, drip in more entropy into the state. 6. I'd like to see about supporting xorshift1024 as well (described here: http://xorshift.di.unimi.it/ and it's public domain code, so very convenient to port ... I'd do it too, of course, if that seems like an okay idea). This is a really small thing because xorshift1024 isn't really much better than xorshift128 (but some people might like the idea of it having significantly longer period). Why not write to the paper's author and ask about it? Done :) ... if I get a response, I'll make sure to incorporate everything said.