Re: Spritz (was Re: Bug#760857: mksh shoould not export $RANDOM)
On 09/20/2014 07:14 PM, Thorsten Glaser wrote: Dixi quod… So, I’m most definitely n̲o̲t̲ looking for algorithms. That being said, after having read http://crypto.2014.rump.cr.yp.to/3de41b60e32a494c8f0fc9c21c67063a.pdf and the first ten pages (up to beginning of chapter 4) of http://people.csail.mit.edu/rivest/pubs/RS14.pdf I’m impressed (the stop symbol especially) and could consider making this the basis of an aRC4 replacement. The documentation appears good enough for implementing it myself, and it may be possible even to implement it in constant-time which is important in crypto nowadays. Its 1732 bit state beats the about 1700 bit of aRC4, too ;) although that is due to the increase in registers. bye, //mirabilos Glad to hear it :)
Re: Spritz
Lorenzo dixit: On 09/20/2014 07:14 PM, Thorsten Glaser wrote: appears good enough for implementing it myself, and it may be possible even to implement it in constant-time which is important Hm, or maybe not. Also, the algorithm is extremely slow as is already, and since MirBSD caters to the low-end machines, like my 80486SLC-25 and my by now seven (I got another) SPARCstations… … but then, if Spritz is really that good, I could greatly simplify the arc4random design with its several separate pools and all that, which would remove some of the speed overhead. (For example, we generate 5½ bytes of entropy to read a 4-byte quantity, all the time, which reduces speed to about ⅔ anyway.) Its 1732 bit state beats the about 1700 bit of aRC4, too ;) although that is due to the increase in registers. And some of it is lost due to the CRUSH function, at least possibly, but I think it doesn’t affect use of it as an SRNG. Glad to hear it :) Right ☺ No promise as to when I get around looking at it more; there are massively more important things to do, and I’m spread enough as is. But I’ve cached the PDFs and the bib.txt locally. bye, //mirabilos -- theftf Ich gebs zu, jupp ist cool -- theftf zu Natureshadow beim Fixen von Debian
Re: Spritz
On 09/21/2014 02:37 PM, Thorsten Glaser wrote: Lorenzo dixit: On 09/20/2014 07:14 PM, Thorsten Glaser wrote: appears good enough for implementing it myself, and it may be possible even to implement it in constant-time which is important Hm, or maybe not. Also, the algorithm is extremely slow as is already, and since MirBSD caters to the low-end machines, like my 80486SLC-25 and my by now seven (I got another) SPARCstations… Wait, wait - 1. MirBSD? 2. what did you measure exactly? 1. MirBSD (I had to google 80486SLC-25 :) Are you considering RS14 for /dev/random? Making a portable arc4random() based on RS14 should be more than good enough for the portable version of mksh, even in terms of speed - or did you stop using arc4random() for $RANDOM because of this slow machines? 2. Speed I used this script # test $RANDOM speed if [ x$N = x ] ; then N=$((1000*1000)) ; fi echo N = $N... while [ $N -gt 0 ] ; do N=$(($N - 4)) : $RANDOM $RANDOM $RANDOM $RANDOM done # RESULT: # 7% time increase with rndget() = repeat 123 times original_rndget() # Spritz-RC4 is NOT 123x slower than an LCG! # Fwiw: bash is significantly slower than mksh, but zsh is faster than mksh Ie slowing down rndget() by a factor X has an impact which is much smaller than X due to the shell having to parse over and over, not to mention that in real usage you'd actually be doing something other than generating random numbers... I'd expect the rc4/rs14 speed ratio to be more or less the same on my computer or on your 486, since the size of the state is very similar and it only uses byte operations - am I missing something? Too few registers on 486? OT I quit toying with archlinux when updating to linux3.0 broke my p3 coppermine, as in, it couldn't boot and (unlike debian) there was no older version installed. Downgraded via livecd, and waited a few kernel upgrades (break, curse,downgrade again) to see if anyone else would notice. Nope. /OT … but then, if Spritz is really that good, I could greatly simplify the arc4random design with its several separate pools and all that, which would remove some of the speed overhead. (For example, we generate 5½ bytes of entropy to read a 4-byte quantity, all the time, which reduces speed to about ⅔ anyway.) Its 1732 bit state beats the about 1700 bit of aRC4, too ;) although that is due to the increase in registers. And some of it is lost due to the CRUSH function, at least possibly, but I think it doesn’t affect use of it as an SRNG. Glad to hear it :) Right ☺ No promise as to when I get around looking at it more; there are massively more important things to do, and I’m spread enough as is. But I’ve cached the PDFs and the bib.txt locally. bye, //mirabilos
Re: Spritz
Lorenzo dixit: Wait, wait - 1. MirBSD? Of course. 2. what did you measure exactly? Nothing, I just saw the comparative measurements in the paper. Are you considering RS14 for /dev/random? Of course not. Just for both /dev/arandom and userspace arc4random(). Making a portable arc4random() No, I don’t do that because other operating systems don’t provide sensible enough kernel interfaces. The closest one is OpenBSD, but even theirs suck. based on RS14 should be more than good enough for the portable version of mksh, even in terms of speed - or did you stop using arc4random() for $RANDOM because of this slow machines? No, mksh’s $RANDOM does not need arc4random() and does not promise it – I just use it when it’s convenient. I don’t use it on most OSes because almost all OSes don’t provide good and easy to use kernel interfaces to gather entropy, and I’d rather not have several fall‐ back mechanisms. Ie slowing down rndget() by a factor X has an impact which is much smaller than X due to the shell having to parse over and over, not to mention that in real usage you'd actually be doing something other than generating random numbers... We need to separate several concerns here: • do we use arc4random() for mksh, or rather, when • what provides arc4random() • arc4random() on MirBSD may or may not be using Spritz, it currently uses aRC4 • arc4random() on OpenBSD used aRC4 and uses ChaCha20 now, but lacks an interface to push back entropy to the kernel • arc4random() is not native to any other OS, and all portable implementations suck, both in themselves and because of their underlying operating systems (e.g. Linux deprecating sysctl(), and their new proposed getentropy syscall (incompatible to OpenBSD’s new one) sucks) • what do we do in mksh if an OS absolutely cannot support arc4random() (e.g. lack of /dev/urandom and similar) The last point is actually why I’d say, we only use arc4random() if “it’s there anyway”, which is basically OpenBSD and MirBSD “period”. Everything else gets an LCG, and I’m seriously considering removing all overhead and just using dumb mode there (that can also easily be tested for). (And OpenBSD just doesn’t get the kernel feedback, period. They asked for them to not get it, even.) bye, //mirabilos -- 22:20⎜asarch The crazy that persists in his craziness becomes a master 22:21⎜asarch And the distance between the craziness and geniality is only measured by the success 18:35⎜asarch Psychotics are consistently inconsistent. The essence of sanity is to be inconsistently inconsistent
