Re: Spritz
Ronald L. Rivest dixit: There is no spritz mailing list or the like (yet); I'll let you know if we create one. We plan to publish an updated paper on Spritz within the next couple of weeks on the IACR eprint site: http://eprint.iacr.org/ OK, thank you. Keep an eye for this. The algorithm will be the same, but the analysis and discussion should be improved, over the version that is now posted on my web site... Okay. What did you think about this: This could probably be improved by changing SHUFFLE to: ⒈ local tmp1 = DRIP() ⒉ local tmp2 = DRIP() ⒊ local tmp3 = DRIP() ⒋ WHIP(2*N + tmp1) ⒌ tmp2 += DRIP() ⒍ tmp3 += DRIP() ⒎ CRUSH() ⒏ WHIP(2*N + tmp2) ⒐ tmp3 += DRIP() ⒑ CRUSH() ⒒ WHIP(2*N + tmp3) ⒓ a = 0 I think (intuition, not science; I’ve written down the idea basically as soon as I had it) that it should reduce loss of entropy in the state, which would benefit use of Spritz as RNG, and not harm use of it as hash and stream cipher other than a slight speed reduction. bye, //mirabilos -- I believe no one can invent an algorithm. One just happens to hit upon it when God enlightens him. Or only God invents algorithms, we merely copy them. If you don't believe in God, just consider God as Nature if you won't deny existence. -- Coywolf Qi Hunt
Re: Spritz
Ronald L. Rivest dixit: I'm not sure why your proposed variation should produce reduced loss of entropy? CRUSH always reduces by 128 bit, but by changing the amount of WHIP calls before a CRUSH, we shuffle things around a bit more. This matches the random skips we currently use in arc4random. In any case, I don't think loss of entropy is a problem. The key space will be much much smaller than the state space, Not if using this as RNG, postprocessing output from something with 8192 bit of internal state, and more-or-less continuously feeding input into it. In this case, the “key” is much larger than the state. bye, //mirabilos -- igli exceptions: a truly awful implementation of quite a nice idea. igli just about the worst way you could do something like that, afaic. igli it's like anti-design. mirabilos that too… may I quote you on that? igli sure, tho i doubt anyone will listen ;)
Re: Spritz
Dixi quod… 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 OK. I slept over it, and I think that a Spritz-based stretching RNG, to replace aRC4 in arc4random(), has a bit more than 1476 bit and no more than 1604 bit of entropy in its state, due to use of CRUSH. This could probably be improved by changing SHUFFLE to: ⒈ local tmp1 = DRIP() ⒉ local tmp2 = DRIP() ⒊ local tmp3 = DRIP() ⒋ WHIP(2*N + tmp1) ⒌ tmp2 += DRIP() ⒍ tmp3 += DRIP() ⒎ CRUSH() ⒏ WHIP(2*N + tmp2) ⒐ tmp3 += DRIP() ⒑ CRUSH() ⒒ WHIP(2*N + tmp3) ⒓ a = 0 This is similar to the arc4random modifications we have in MirBSD, which not only skips 12*256 bytes of output after reseeding but also a somewhat random amount, and skips randomly 1‥2 bytes for every call to arc4random() and 1‥4 bytes for every 256 output bytes in a call to arc4random_buf(), just to further randomise (just like multiple readers of one pool, such as the kernel /dev/arandom, improve the “pool size” for every reader separately). Since this is deterministic, it could probably be also used in Spritz as stream cipher and hash ☺ @Ronald, Jacob: where can I keep informed about the state of Spritz, e.g. review/cryptanalysis (just the human-readable results please, not the academic details)? I see it has potential to simplify our RNG setup, especially due to the sponge construction, the ability to mix reading and writing (which Keccak does not really provide), and the AbsorbStop() function (nice!). This way, I can get rid of the temporary 128-bit “round hash” to spool incoming data, and just feed data straight into Spritz. bye, //mirabilos -- Yay for having to rewrite other people's Bash scripts because bash suddenly stopped supporting the bash extensions they make use of -- Tonnerre Lombard in #nosec
Re: Spritz
On 09/21/2014 10:02 PM, Thorsten Glaser wrote: Lorenzo dixit: Wait, wait - 1. MirBSD? Of course. tldr: this + the mention of slow computers made me misunderstand your previous message. 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. Oh, ok! When I read about slow machines I misunderstood and thought you considered using rs14 to make a portable arc4random() for use with $RANDOM and rejected the idea because it was too slow; I went wtf? and - well, if you reread my mail knowing what I had in mind it should make sense now :) 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) https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=c6e9d6f38894798696f23c8084ca7edbf16ee895 The real problem is that you can't count on getrandom() being there - eg it's too new for my machine running debian sid... why they removed the sysctl() without providing an alternative is beyond me instead. Oh, btw - I can't find the link right now, but someone took the pain to look at (and compare) many broken versions of portable functions, including arc4random. It was just plain horrible. • 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
Re: Spritz
Lorenzo dixit: The real problem is that you can't count on getrandom() being there - eg it's too new for my machine running debian sid... why they removed the sysctl() without providing an alternative is beyond me instead. Also, it’s Linux-specific, and not suitable for mksh anyway since mksh is early userspace. Oh, btw - I can't find the link right now, but someone took the pain to look at (and compare) many broken versions of portable functions, including arc4random. Oh, too bad. Do share once you know it ;) It was just plain horrible. I can fully imagine. OK, thanks for all the feedback. I have a rough idea where I want to go to now, and will do this once I have some hacking time for mksh again. bye, //mirabilos -- igli exceptions: a truly awful implementation of quite a nice idea. igli just about the worst way you could do something like that, afaic. igli it's like anti-design. mirabilos that too… may I quote you on that? igli sure, tho i doubt anyone will listen ;)
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
Spritz (was Re: Bug#760857: mksh shoould not export $RANDOM)
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 -- dileks ch: good, you corrected yourself. ppl tend to tweet such news immediately, sth. like grml devs seem to be buyablech dileks: we _are_. if you throw enough money in our direction, things will happen mika everyone is buyable, it's just a matter of price mrud and now comes [mira] and uses this as a signature ;0 -- they asked for it…
