On Sun, May 24, 2020 at 06:49:03PM -0700, Kevin wrote in
<20200525014903.ga1...@afu.lan>:
On Sun, May 24, 2020 at 04:59:24PM -0400, Remco Rijnders wrote:
By implementing the LFSR113 function by Pierre L'Ecuyer mutt gets a fast
and high quality PRNG that, given the same seeds, results in the same
output no matter the environment mutt is running on.
I'm not knowledgeable about PRNGs. The generation code below looks
the same as other LFSR113 generators I searched around for, but I
can't vouch for how "good" the generator itself is. Still, I'm
inclined to apply the patch (with fixes) so please chime in if you
think this is a bad idea.
I am not knowledgable in this field either, and as such I am almost
inclined to agree with Petr to not try and reinvent the wheel
myself. I will note though that Pierre L'Ecuyer is a bit of an
authority in this field and that, as far as I understand it, this
algorithm does not leak any state information as its output is based
on the XOR'ed values of four different PRNG algorithms which we also
seed independently of each other.
More comments below.
diff --git a/configure.ac b/configure.ac
index 7906ce35..0f65fc56 100644
--- a/configure.ac
+++ b/configure.ac
@@ -34,7 +34,6 @@ AC_PROG_CPP
AC_PROG_MAKE_SET
AC_PROG_INSTALL
AC_PROG_MKDIR_P
-AC_PROG_RANLIB
AC_CHECK_TOOL(AR, ar, ar)
Ranlib is a library tool, and is still used (in some way) in the intl
and m4 directories. Regardless, this kind of change should not be in
this commit (unless it was a mistaken assumption that it meant "random
library" or something).
Yes, I do fear I was mistaken here in thinking this was what defines
the HAVE_SRAND48 definition being set or not. I should not have
included this without being more certain about its function.
diff --git a/mutt_random.c b/mutt_random.c
+/* Initialize the four seeds for our PRNG algorithm */
+void mutt_srandom(void)
+{
+ struct timeval tv;
+ gettimeofday(&tv, NULL);
+ /* POSIX.1-2008 states that seed is 'unsigned' without specifying its width.
+ * Use as many of the lower order bits from the current time of day as the
seed.
+ * If the upper bound is truncated, that is fine.
+ *
+ * tv_sec is integral of type integer or float. Cast to 'u_int32_t' before
+ * bitshift in case it is a float.
+ */
+ z1 = ((u_int32_t) tv.tv_sec << 20) | tv.tv_usec;
+ z2 = getpid();
+ z3 = getppid();
+ z4 = (intptr_t) &z4;
+}
Comments on the seed choices would be quite welcome. This first three
seem okay to me, but the fourth choice is probably a bit weak. I
don't know that it will vary much.
Well, the idea for z4 is really to pick another seed than any other
user running mutt on the same system would have. I agree that it is
not the strongest seed, which is also true for z2 and z3 which are low
in entropy by themselves (and might be observable for others on the
same system). Given the nature of the algorithm, an attacker would have
to know all four seeds for this to have an impact though.
Other than picking different seeds, a possible mitigant could be
periodical reseeding. I am not sure how necessary this is given the
preceeding?
diff --git a/mutt_random.h b/mutt_random.h
+#include <sys/time.h>
+#include <sys/types.h>
+#include <string.h>
+#include <unistd.h>
Mutt traditionally puts these inside the .c file. So I'd prefer to
see them moved there.
Ok, agreed.
+extern void mutt_to_base64 (unsigned char*, const unsigned char*, size_t,
size_t);
Include "mutt.h" inside mutt_random.c instead.
Ok!
+void mutt_srandom(void);
+u_int32_t mutt_random32(void);
+void mutt_base64_random96(char output_B64[static 17]);
+
+u_int32_t z1, z2, z3, z4;
z1-z4 should be moved inside mutt_random.c and declared static. The
latest gcc won't even compile duplicate global variable definitions.
Ok!
I appreciate your review and will make the recommended changes.
Kind regards,
Remco
