[erlang-questions] Password generator in Erlang

[Zabrane Mickael]

Hi guys,

This one fires a lot of collisions (http://schemecookbook.org/Erlang/NumberRandomNumber):

------------------

test() ->

    crypto:start(),

    N = 10000,

    io:format("Generate ~p random passwords and check for collisions ...~n", [N]),

    test(N, dict:new(), 0).

test(0, _, C) ->

    io:format("Number of collisions: ~p~n", [C]);

test(N, Dict, C) ->

    Password = passwd(),

    case dict:find(Password, Dict) of

        {ok, _} -> %% collision detected

            test(N - 1, Dict, C + 1);  

        error ->

            test(N - 1, dict:append(Password, 1, Dict), C)

    end.

passwd() ->

    passwd(8).

passwd(Length) ->

    {A1,A2,A3} = now(),

    random:seed(A1, A2, A3),

    lists:flatten(lists:foldl(fun(_,AccIn) ->

                                      [random:uniform(90) + 32 | AccIn] end,

                              [], lists:seq(1,Length))).

----------------

> passwd:test().

Generate 10000 random password and check for collisions ...

Number of collisions: 1182

Anything better guys? Something with less collisions if possible.

Regards,

Zabrane

[Sverker Eriksson]

Try only call random:seed(A1, A2, A3) once at start.

For cryptographic safe random generation look at crypto module.

/Sverker

_______________________________________________
erlang-questions mailing list
erlang-q...@erlang.org
http://erlang.org/mailman/listinfo/erlang-questions

[Loïc Hoguin]

os:cmd("pwgen | cut -c 1-8").

> _______________________________________________
> erlang-questions mailing list
> erlang-q...@erlang.org
> http://erlang.org/mailman/listinfo/erlang-questions
>

--
Loïc Hoguin
Erlang Cowboy
Nine Nines
http://ninenines.eu

[Zabrane Mickael]

On Aug 14, 2012, at 5:40 PM, Loïc Hoguin wrote:

> os:cmd("pwgen | cut -c 1-8").

a portable one ;-)

[Zabrane Mickael]

Thank Serker.

Moving andom:seed(A1, A2, A3) at start fix it.

1> passwd:test().

Generate 10000 random password and check for collisions ...

Number of collisions: 0


--------------------
test() ->

{A1,A2,A3} = now(),
random:seed(A1, A2, A3),

N = 10000,
io:format("Generate ~p random password and check for collisions ...~n", [N]),

test(N, dict:new(), 0).
test(0, _, C) ->
io:format("Number of collisions: ~p~n", [C]);
test(N, Dict, C) ->
Password = passwd(),
case dict:find(Password, Dict) of
{ok, _} -> %% collision detected
test(N - 1, Dict, C + 1);
error ->
test(N - 1, dict:append(Password, 1, Dict), C)
end.

passwd() ->
passwd(8).
passwd(Length) ->

lists:flatten(lists:foldl(fun(_,AccIn) ->
[random:uniform(90) + 32 | AccIn] end,
[], lists:seq(1,Length))).

--------------------

Regards,
Zabrane

[Loïc Hoguin]

On 08/14/2012 06:09 PM, Zabrane Mickael wrote:
>
> On Aug 14, 2012, at 5:40 PM, Loïc Hoguin wrote:
>
>> os:cmd("pwgen | cut -c 1-8").
>
> a portable one ;-)

I believe pwgen and cut are available on all of win/linux/bsd/osx.

--
Loïc Hoguin
Erlang Cowboy
Nine Nines
http://ninenines.eu

[Zabrane Mickael]

Thanks for the info Loïc.

> I believe pwgen and cut are available on all of win/linux/bsd/osx.

Regards,
Zabrane

[Wes James]

Pwgen/cut are not on stock win 7 pro. Maybe add with Cygwin.

Wes

[Richard O'Keefe]

On 15/08/2012, at 4:44 AM, Loïc Hoguin wrote:

> On 08/14/2012 06:09 PM, Zabrane Mickael wrote:
>>
>> On Aug 14, 2012, at 5:40 PM, Loïc Hoguin wrote:
>>
>>> os:cmd("pwgen | cut -c 1-8").
>>
>> a portable one ;-)
>
> I believe pwgen and cut are available on all of win/linux/bsd/osx.

m% man pwgen
No manual entry for pwgen

Mac OS X 10.6.8.

v% man pwgen
No manual entry for pwgen

Linux 2.6.31.5-127.fc12.x86_64

f% man pwgen
No manual entry for pwgen.

Solaris.

Available? May be, I don't know.
Installed? NO.

[Yurii Rashkovskii]

OSX:

$ which pwgen

pwgen not found

[Raimo Niskanen]

On Wed, Aug 15, 2012 at 11:42:06AM +1200, Richard O'Keefe wrote:
>
> On 15/08/2012, at 4:44 AM, Loïc Hoguin wrote:
>
> > On 08/14/2012 06:09 PM, Zabrane Mickael wrote:
> >>
> >> On Aug 14, 2012, at 5:40 PM, Loïc Hoguin wrote:
> >>
> >>> os:cmd("pwgen | cut -c 1-8").
> >>
> >> a portable one ;-)
> >
> > I believe pwgen and cut are available on all of win/linux/bsd/osx.
>
> m% man pwgen
> No manual entry for pwgen
>
> Mac OS X 10.6.8.
>
> v% man pwgen
> No manual entry for pwgen
>
> Linux 2.6.31.5-127.fc12.x86_64
>
> f% man pwgen
> No manual entry for pwgen.
>
> Solaris.
>
> Available? May be, I don't know.
> Installed? NO.

And the same applies to Ubuntu, FreeBSD and OpenBSD...

This might be more portable:
openssl rand -base64 6 | tr +/ .,

>
>
> _______________________________________________
> erlang-questions mailing list
> erlang-q...@erlang.org
> http://erlang.org/mailman/listinfo/erlang-questions

--

/ Raimo Niskanen, Erlang/OTP, Ericsson AB

[Artem Teslenko]

One more way to generate the passwords:

random:seed(now()).
base64:encode_to_string(crypto:rand_bytes(16)).

"EbvUy9ZHTqoAOvMSZ53X5A=="

After that just remove the unnecessary characters.

[Zabrane Mickael]

Thanks for sharing this Artem. Very neat!!

Regards,
Zabrane

On Aug 16, 2012, at 4:53 PM, Artem Teslenko wrote:

> One more way to generate the passwords:
>
> random:seed(now()).
> base64:encode_to_string(crypto:rand_bytes(16)).
>
> "EbvUy9ZHTqoAOvMSZ53X5A=="

[Jeremey Barrett]

On Aug 16, 2012, at 9:53 AM, Artem Teslenko <at...@ipv6.dp.ua> wrote:

> One more way to generate the passwords:
>
> random:seed(now()).
> base64:encode_to_string(crypto:rand_bytes(16)).

Note: random:seed() is not related to crypto:rand_bytes(). Just the second line will do.

Regards,
Jeremey.

[Artem Teslenko]

Yes, you are right. The first line is unnecessary.

[Raimo Niskanen]

On Thu, Aug 16, 2012 at 04:53:01PM +0200, Artem Teslenko wrote:
> One more way to generate the passwords:
>
> random:seed(now()).
> base64:encode_to_string(crypto:rand_bytes(16)).
>
> "EbvUy9ZHTqoAOvMSZ53X5A=="
>
> After that just remove the unnecessary characters.

That is almost the same as my command line suggestion but in all erlang.
Very nice!

If you choose the number of bytes as a multiple of 6 you will not get
any trailing `=' and translate any generated Base64 characters `+'
and `/' (at least `/' is not popular by some password checkers)
into something else, see my example of using `.' and `,' below,
then it is the same suggestion.
[case X of $+ -> $.; $/ -> $,; X -> X end
|| X <- base64:encode_to_string(crypto:rand_bytes(12))]
->
"dSdCpgl.wuGaMzsr"

/ Raimo

[Anthony Kong]

Hi, Artem, 

When I use random::seed, I saw a 'undefined' output. Is it expected?

$ erl

Erlang R14B04 (erts-5.8.5) [source] [64-bit] [smp:4:4] [rq:4] [async-threads:0] [hipe] [kernel-poll:false]

Eshell V5.8.5  (abort with ^G)

1> random:seed(now()).

undefined

[Artem Teslenko]

Hello Anthony,

Yes, it's ok, from the man page:

seed(X1 :: {A1, A2, A3}) -> undefined | ran()

undefined value is returned when you run seed/1 first time.

Anyway it's unnecessary for crypto:rand_bytes(16).

[Samuel]

> Thank Serker.
>
> Moving andom:seed(A1, A2, A3) at start fix it.
>
> 1> passwd:test().
> Generate 10000 random password and check for collisions ...
> Number of collisions: 0

There are a number of problems with both implementations.

First, random:uniform is not cryptographically secure, which means is
somewhat predictable. As already mentioned use any other generator
meant to be secure as the one in crypto or the ssl library.

Even using a secure pseudrandom generator:

Your first implementation destroys the security, as you are creating a
seed for each random number an attacker just needs to guess the seed
sequence, not the pseudorandom sequence. In your case you had a side
effect of generating collisions, but that was not the worst problem.

The second implementation is more secure in that sense, but still the
original seed is guessable. An attacker can generate possible password
sequences by bruteforce just tying possible now tuples around the time
he thinks the real seed was created.

So, if you want to create passwords difficult to guess, you need at
least a cryptographically secure PRG, which will give you an
unpredictable sequence of bytes, and an unguessable seed, which will
give prevent any attacker from creating the same sequence of bytes
again an completely break all your passwords.

Best
--
Samuel

[Zabrane Mickael]

Hi Samuel,

Thanks for these useful insights.

We're not a security software company and our usage of these passwords isn't critical.

Anyway, we want to learn if possible.

First, random:uniform is not cryptographically secure, which means is
somewhat predictable. As already mentioned use any other generator
meant to be secure as the one in crypto or the ssl library.

Even using a secure pseudrandom generator:

Your first implementation destroys the security, as you are creating a
seed for each random number an attacker just needs to guess the seed
sequence, not the pseudorandom sequence. In your case you had a side
effect of generating collisions, but that was not the worst problem.

Yup. Sverker response was very clear to this regard!

The second implementation is more secure in that sense, but still the
original seed is guessable. An attacker can generate possible password
sequences by bruteforce just tying possible now tuples around the time
he thinks the real seed was created.

So, how one can generate a secure un-predicatable seeds?

So, if you want to create passwords difficult to guess, you need at
least a cryptographically secure PRG, which will give you an
unpredictable sequence of bytes, and an unguessable seed, which will
give prevent any attacker from creating the same sequence of bytes
again an completely break all your passwords.

We also moved to "Tiny Mersenne Twister" (https://github.com/jj1bdx/tinymt-erlang) instead of using

the standard random:uniform since the last Yaws security alert (http://erlang.org/pipermail/erlang-questions/2012-June/067626.html).

Is this sufficient or should we also find a way to generate a unpredicatble seed for it?

Regards,

Zabrane

[CGS]

Hi Zabrane,

If you want just a well distributed RNG with long period, you may take a look at WELL RNG (http://www.iro.umontreal.ca/~panneton/WELLRNG.html) as well. I also needed that and I had an attempt to translate it in Erlang, so, you may use it if you think fit (https://github.com/cgsmcmlxxv/WELL44497ac). It is recommended for Monte Carlo simulations and less for cryptography, though.

CGS

[Zabrane Mickael]

Hey CGS,

Let me give it a try ;-)

Regards,

Zabrane

On Aug 17, 2012, at 10:12 AM, CGS wrote:

[Samuel]

> The second implementation is more secure in that sense, but still the
> original seed is guessable. An attacker can generate possible password
> sequences by bruteforce just tying possible now tuples around the time
> he thinks the real seed was created.
>
>
> So, how one can generate a secure un-predicatable seeds?

That's the tricky part :) At least you have to avoid generating
clearly predictable seeds as the seed is your private key in this
case. With the seed anyone can reproduce the sequence.

crypto:strong_rand_bytes strives for better security properties, and I
understand it abstracts how to generate a good key for you, trying to
suck entropy from your system (so you may need to sit there banging
the keys and moving the mouse around for that ;) )

I am not a security expert by far, I just know some things that do not
work :). For things that work, the common approach is relying in
popular libraries not known to be broken. and trying not to use them
in a fancy way as the history is full of famous broken cryptographic
uses (you can read about flaws CSS, WEP, etc).

Of course, whether that approach is advisable or not is more a
philosophical question, not knowing they are not broken doesn't mean
that no one knows how to break them and has the key access information
is thought to be safely encrypted :)

> We also moved to "Tiny Mersenne Twister"
> (https://github.com/jj1bdx/tinymt-erlang) instead of using
> the standard random:uniform since the last Yaws security alert
> (http://erlang.org/pipermail/erlang-questions/2012-June/067626.html).
> Is this sufficient or should we also find a way to generate a unpredicatble
> seed for it?

As said, I am not a security expert, but as far as I can read, the
goals of that algorithm are to keep a small state with good
statistical properties, it says nothing about security (which doesn't
necessarily mean it is insecure, of course). A PRG can have good
statistical properties and still be insecure, being a secure PRG is a
stronger assumption. That is why erlang:random is fine for non
cryptographic uses, but for security you need something more complex.

Anyway, you always need a seed no one can guess. Same seed, same
sequence, so if someone guesses your seed it basically gets all your
passwords in return.

Regards

[Zabrane Mickael]

Hi Samuel,

Great feedbacks.

I'll try to find out how to generate good seeds.
May be some braves Erlangers know the answer?

Regards,
Zabrane

[Raimo Niskanen]

On Fri, Aug 17, 2012 at 04:38:06PM +0200, Zabrane Mickael wrote:
> Hi Samuel,
>
> Great feedbacks.
>
> I'll try to find out how to generate good seeds.
> May be some braves Erlangers know the answer?

The simple answer is as mentioned before in this thread
to use crypto:strong_rand_bytes/1, as it will with OS and library
support take care of the seeding itself. This will be
what is considered secure enough by the writers of OpenSSL.

strong_rand_bytes(N) -> binary()

Types:
N = integer()

Generates N bytes randomly uniform 0..255, and returns the
result in a binary. Uses a cryptographically secure prng
seeded and periodically mixed with operating system provided
entropy. By default this is the RAND_bytes method from OpenSSL.

May throw exception low_entropy in case the random generator
failed due to lack of secure "randomness".

/ Raimo

--

/ Raimo Niskanen, Erlang/OTP, Ericsson AB

[Jeremey Barrett]

Hi all... if you want pseudo-random bytes, use crypto:rand_bytes() or crypto:strong_rand_bytes(), depending on your security requirements. rand_bytes() calls OpenSSL's RAND_pseudo_bytes(), and strong_rand_bytes() calls OpenSSL's RAND_bytes(). Read up on them for more info.

strong_rand_bytes() will return an error if insufficient entropy is present. rand_bytes() will "just do it", which may not be what you want.

OpenSSL is widely deployed, trusted, etc. The built-in wrappers in Erlang are very convenient, just use them. The crypto community has been over and over this for two decades. I cannot stress enough the value of just using a trusted, open implementation vs. fretting over details that may or may not be relevant. There are so many factors you cannot account for otherwise.

Regards,
Jeremey.

[Zabrane Mickael]

Thanks guys. I'll give "crypto:strong_rand_bytes" a try ;-)

Regards,
Zabrane

[Torben Hoffmann]

One thing to keep in mind with crypto is that it depends on OpenSSL
which means that if you want to create a binary version of your
application you need to make sure that the execution platform has OpenSSL.

If you are developing a server for your own use - no problem.

If you want to break the dependency you can - on Un*x-like platforms -
resort to getting a seed from /dev/urandom - there is an example of this
in https://github.com/lehoff/cryptographic, it is ages since I worked on
that and I cannot remember the state of that, but the general principle
should be sound.

There is a way to do this in Windows too, but we never got around to
implementing that back then.

Cheers,
___
/orben

--
http://www.linkedin.com/in/torbenhoffmann

[Zabrane Mickael]

Hi Torben,

On Aug 17, 2012, at 9:33 PM, Torben Hoffmann wrote:

One thing to keep in mind with crypto is that it depends on OpenSSL which means that if you want to create a binary version of your application you need to make sure that the execution platform has OpenSSL.

If you are developing a server for your own use - no problem.

That's the case for us.

If you want to break the dependency you can - on Un*x-like platforms - resort to getting a seed from /dev/urandom - there is an example of this in https://github.com/lehoff/cryptographic, it is ages since I worked on that and I cannot remember the state of that, but the general principle should be sound.

There is a way to do this in Windows too, but we never got around to implementing that back then.

From the source code:

/* entropy.c - C code for generating random numbers using the internal windows entropy library. */

https://github.com/lehoff/cryptographic/blob/master/c_src/entropy.c

Regards,

Zabrane

[Torben Hoffmann]

Ups, forgot about the addition of the Windows code. As far as my bad memory serves me I think the Windows code does not work. 

And it is /dev/random, not /dev/urandom. 

Must remember to read up on old code before talking about it :-$

___

 /orben

Sent from my iPhone

[Zabrane Mickael]

On Aug 17, 2012, at 11:59 PM, Torben Hoffmann wrote:

> Ups, forgot about the addition of the Windows code. As far as my bad memory serves me

you're not alone ;-)

> I think the Windows code does not work.
> And it is /dev/random, not /dev/urandom.
> Must remember to read up on old code before talking about it :-$

Thanks,
Zabrane

[Kenji Rikitake]

Samuel is right. SFMT is NOT cryptographically safe.

Kenji Rikitake

[Kenji Rikitake]

Just FYI to you all:

An interesting paper how /dev/(u)random could fail
in an environment where external entropy is
very much restricted or biased.

https://factorable.net/paper.html
(Two PDF files available; I suggest you to read
the extended version of the paper.)

If you really want to make a secure password generator,
always think about how to get enough entropy,
preferably using a trustable hardware true RNG.

(And I suggest you to check your SSH host keys
and SSL/TLS certs as well, at:
https://factorable.net/keycheck.html

Kenji Rikitake
(Excuse me that this is not necessarily an Erlang topic,
but I think this is enough related to the thread)

[Zabrane Mickael]

Thanks for sharing these valuable information Kenji.

Regards,
Zabrane