Re: Noob dumb question (extending emacs)

[Michael Heerdegen]

Emanuel Berg via Users list for the GNU Emacs text editor
<help-gnu-emacs@gnu.org> writes:

> Michael Heerdegen wrote:
>
> >     48 ln(2)
> > l = -------- ~ 8.13.
> >      ln(60)
> >
> > That would mean that already for a length of 9 only a small
> > fraction of passwords are computable.
>
> Okay, why do you say/how do you know that?

Anything besides used entropy is deterministic.

If you initialize the seed with a certain entropy, it means that you
randomly get one seed out of N possible (known) seeds.  In our case N =
2^31 (or something like that).

To understand the reasoning behind the following it can help to assume a
small N, e.g. N=2, N=10 or N=100, and then think about what
fundamentally changes if N is larger (actually nothing, you only need
accordingly more tries to guess).  This is all quite trivial, only the
large numbers involved cloud a bit what is going on.

Ok.  Those possible seeds are known (computable) to everyone: You start
with a random seed out of a public list of N seeds.

With each of these seeds, `random' will generate one out of N possible
predefined sequences of numbers.  With the exception: If N is larger
than the number of possible different results of `random' (a finite
number of course), let's name it "M", then you must set N = M in the
following considerations.

So if you use a publicly known deterministic algorithm using `random',
your algorithm will generate one out of N possible publicly known
password sequences for each call.

Security of these passwords stands and falls with the size of N:

Say your algorithm calculates passwords using an alphabet consisting of
a number b of letters, e.g. b=60 for small and capital letters plus some
special characters.  Then the entropy used is enough to generate
pseudo-random passwords of a length l when b^l ~ N (where "~" means "is
approximately").

Why?  If l is smaller, b^l < N, your algorithm would often calculate the
same password for different seeds, and you would waste a portion of the
initial randomness (entropy).

If l is larger, b^l > N, the passwords per se are stronger in theory
but... that doesn't matter if you publish the algorithm that computed
the passwords (or one can guess that algorithm).  Then I still have to
try only N passwords, not more than when a smaller password length is
used.  One could say that those longer passwords contain redundancy: a
part of those password strings is determined by the rest of the password
string and doesn't offer additional security.

The situation would be similar to posting on your homepage:

  "Any of my accounts uses a password out of this list:

 { "nx4BgzrJmZq0+!YPp<O|]8k&Q"<M2-`<nSV#|CH-",
   "%d~8bqv1j^rl51\6(9#/d[!D91_X_H/=`|&S]|SQ",
   ":2A]sw=V;--q)RKLOIdoxd`9B+4#Q5[WY\8yFNl",
   "?ljGuo\-;VF"9;F$MgU~uP|Ztk$!!9kxAsv~,Lv?",
   ">%M\s=>!xHP9|EMEzR[&Wu&$,\]lS`fN1y:Bc!Ey",
   "igbf^Hlcxyg,A0MBa>d:!,}{x"j%?Qi^,P<YDP-|",
   "/iGww)fjE:*$:uv,$>)M=M?|UF2DZ4|>*Mx"&>(;!,
   "EzIRpdH|;R^1iTAG'*P5LdoJ5sS_Y2kN#S:{S_a\",
   "rLBtPlQ6Unml'5`+B*l^LA}8>/8C}=I)1(']Zqz+",
   "Zt.J$fP<$zU)^AH}<ymP-cNkwz%8#1=+A]<1XON!" }

 Those are all very strong passwords, and the method I use to choose one
 of them randomly is so clever and uses so much entropy that it's
 impossible to guess it.  Try it, Mentalist!"

But since all of those possible passwords are publicly known the
situation is not better than using a random password out of
{"0", "1",..., "9"}: not more secure than using random passwords of
length 1 (even less).

Or using the formula mentioned,

  ln(N)     ln(10)
  ------ = -------- < 1.
  ln(b)     ln(60)


Now do the same consideration with a larger N.  Whether your passwords
are secure only depends on the real value of N.  And it seems that in
our case N is simply too small for good security.

AFAIU the problem in Emacs is that the number of possible results of
`random' (I called it M) is too small.  If you initialize the random
seed with an entropy N larger than M, there will be only M instead of N
classes of different initializations of the random number generator:
each class would consist of approximately N/M different seeds which
initialize the random generator with exactly the same state.

If you initialize the seed using large strings for example, this would
be comparable to using only the first three characters of these strings
carrying high entropy to initialize the random number generator.  It
would not be, in any way, better than using only three character long
strings carrying very small entropy.


Michael.