[erlang-questions] Yaws security alert - Yaws 1.93

[Claes Wikstrom]

I just posted the following note on the Yaws list, all of you
using Yaws for production with cookie based auth need to take action.
Actually, anyone using random:uniform/1 for anything security related
need to pay attention.

/klacke

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


Folks,

New yaws release which contains a fix to pretty serious security hole.
The relevant relnote entry is:

Use crypto:rand_bytes() instead of the cryptographically weak random module.
Swedish security consultant and cryptographer Kalle Zetterlund discovered a way
to - given a sequence of cookies produced by yaws_session_server - predict the
next session id. Thus providing a gaping security hole into yaws servers that
use the yaws_session_server to maintain cookie based HTTP sessions (klacke/kallez)


It's been almost 6 months since the last release, so this one also contains
a long series of good fixes and improvements from a lot of good people.

Thanks everyone !!


Code, release, relnotes, docs etc at http://yaws.hyber.org/

Yaws team -

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

[Geoff Cant]

Hi Klake,

Is the problem related to predictable seeding of random (set to {A,B,C} = erlang:now() at some point) or is it a bigger break in taking a series of outputs from random:uniform and working out the internal state from that? Just trying to figure out if kallez's attack is a brute force discovery of a weak seed, or if it's a more complete break of the generator itself given an unknown seed.

Cheers,
-Geoff

--
Geoff Cant

[Claes Wikstrom]

On 06/20/2012 11:10 PM, Geoff Cant wrote:
> Hi Klake,
>
> Is the problem related to predictable seeding of random (set to {A,B,C} =
> erlang:now() at some point) or is it a bigger break in taking a series of
> outputs from random:uniform and working out the internal state from that?
> Just trying to figure out if kallez's attack is a brute force discovery of a
> weak seed, or if it's a more complete break of the generator itself given an
> unknown seed.
>
> Cheers,

It's not, Yaws was using the seed as in


{X,Y,Z} = seed(),

...


seed() ->
case (catch list_to_binary(
os:cmd("dd if=/dev/urandom ibs=12 count=1 2>/dev/null"))) of
<<X:32, Y:32, Z:32>> ->
{X, Y, Z};
_ ->
now()
end.


The problem is much deeper, it's the random algorithm itself. It's said that
it's cryptographically weak - now I've seen how weak. Very weak.

/klacke

[Geoff Cant]

On 2012-06-20, at 14:17 , Claes Wikstrom wrote:

> On 06/20/2012 11:10 PM, Geoff Cant wrote:
>> Hi Klake,
>>
>> Is the problem related to predictable seeding of random (set to {A,B,C} =
>> erlang:now() at some point) or is it a bigger break in taking a series of
>> outputs from random:uniform and working out the internal state from that?
>> Just trying to figure out if kallez's attack is a brute force discovery of a
>> weak seed, or if it's a more complete break of the generator itself given an
>> unknown seed.
>>
>> Cheers,
>
>
> It's not, Yaws was using the seed as in
>
>
> {X,Y,Z} = seed(),
>
> ...
>
>
> seed() ->
> case (catch list_to_binary(
> os:cmd("dd if=/dev/urandom ibs=12 count=1 2>/dev/null"))) of
> <<X:32, Y:32, Z:32>> ->
> {X, Y, Z};
> _ ->
> now()
> end.
>
>
> The problem is much deeper, it's the random algorithm itself. It's said that
> it's cryptographically weak - now I've seen how weak. Very weak.

That's pretty neat indeed then (as an attack, not so great for anyone using random:uniform for any crypto-ish purpose). I'd love to look at a description of the break if one becomes available.

Cheers,
--
Geoff Cant

[Pablo Platt]

What are the alternatives?

---

From: Geoff Cant <n...@erlang.geek.nz>
To: Claes Wikstrom <kla...@hyber.org>
Cc: erlang-questions <erlang-q...@erlang.org>
Sent: Thursday, June 21, 2012 12:37 AM
Subject: Re: [erlang-questions] Yaws security alert - Yaws 1.93

[Bob Ippolito]

The random module is *very* weak, it has less than 48 bits of state (Wichmann-Hill 1982). It doesnt really generate results appropriate for double precision float, and it fails modern test suites for PRNGs, so it's basically unsuitable for most modern applications. Also, I haven't looked at Yaws' implementation but the random module only ensures that you have a good seed if you are using the process dictionary version of the API, otherwise you have to ensure that each component is non-zero and not an integer multiple of the prime for that component yourself.

The best alternative is what this version appears to use: the crypto module. If you need something faster that doesn't have to be safe for cryptographic purposes you'll have to look outside of OTP.

[Richard O'Keefe]

On 21/06/2012, at 9:17 AM, Claes Wikstrom wrote:
> The problem is much deeper, it's the random algorithm itself. It's said that
> it's cryptographically weak - now I've seen how weak. Very weak.

The algorithm is AS183, the Wichmann-Hill 3-cycle generator.
It is antique, designed to cope with machines with limited arithmetic
(like the Xerox D-machines XQP ran on), have a tolerably long period
(in the days when 1MHz was fast), and serve the needs of simulations
(small ones, by today's standards).

It was *never* intended to be suitable for cryptography.
Even the modern 4-cycle algorithm from the same authors has not the
faintest claim to suitability for cryptography.

[Michael Truog]

On 06/20/2012 05:00 PM, Bob Ippolito wrote:

The random module is *very* weak, it has less than 48 bits of state (Wichmann-Hill 1982). It doesnt really generate results appropriate for double precision float, and it fails modern test suites for PRNGs, so it's basically unsuitable for most modern applications. Also, I haven't looked at Yaws' implementation but the random module only ensures that you have a good seed if you are using the process dictionary version of the API, otherwise you have to ensure that each component is non-zero and not an integer multiple of the prime for that component yourself.

The best alternative is what this version appears to use: the crypto module. If you need something faster that doesn't have to be safe for cryptographic purposes you'll have to look outside of OTP.

If you are interested in an alternative to the random module which does not need to be safe for cryptographic purposes, there is an implementation of a newer algorithm done by the same authors (Wichmann-Hill 2006) which has an implementation here https://github.com/jj1bdx/sfmt-erlang/blob/master/src/random_wh06_int.erl .  I believe this implementation is faithful to the original algorithm and avoids precision problems by leveraging Erlang's big integers support.  However, I haven't gotten to providing tests for the algorithm yet, because I haven't needed it yet.

A simple application, is a quicker way to do a v4 UUID (i.e., quicker than crypto), where you are not forced to call the random module multiple times (since random only provides 45 bits of pseudo-randomness, but the newer 2006 algorithm provides 124 bits of pseudo-randomness).

So, if anyone is interested, that is a place to look if you need more pseudo-randomness for non-cryptographic purposes.

- Michael

[Claes Wikstrom]

On 06/21/2012 02:45 AM, Richard O'Keefe wrote:
>
> On 21/06/2012, at 9:17 AM, Claes Wikstrom wrote:
>> The problem is much deeper, it's the random algorithm itself. It's said that
>> it's cryptographically weak - now I've seen how weak. Very weak.
>
> The algorithm is AS183, the Wichmann-Hill 3-cycle generator.
> It is antique, designed to cope with machines with limited arithmetic
> (like the Xerox D-machines XQP ran on), have a tolerably long period
> (in the days when 1MHz was fast), and serve the needs of simulations
> (small ones, by today's standards).
>
> It was *never* intended to be suitable for cryptography.

Indeed, that being said, I think there is quite a few Erlang applications
out there that use the OTP random module, some, probably quite a few, of
those applications use the random module in what could be considered
a security related setting. It could be anything, the original author
needed a random number, picked the random module, and now years later, it turns
out that these random numbers are security related.

Not good, a good solution would be to replace the current random module with
a backwards compat implementation that use a better algorithm.

/klacke

[Tuncer Ayaz]

On Thu, Jun 21, 2012 at 10:03 AM, Claes Wikstrom wrote:
> On 06/21/2012 02:45 AM, Richard O'Keefe wrote:
> >
> >
> > On 21/06/2012, at 9:17 AM, Claes Wikstrom wrote:
> > >
> > > The problem is much deeper, it's the random algorithm itself.
> > > It's said that it's cryptographically weak - now I've seen how
> > > weak. Very weak.
> >
> >
> > The algorithm is AS183, the Wichmann-Hill 3-cycle generator. It is
> > antique, designed to cope with machines with limited arithmetic
> > (like the Xerox D-machines XQP ran on), have a tolerably long
> > period (in the days when 1MHz was fast), and serve the needs of
> > simulations (small ones, by today's standards).
> >
> > It was *never* intended to be suitable for cryptography.
>
> Indeed, that being said, I think there is quite a few Erlang
> applications out there that use the OTP random module, some,
> probably quite a few, of those applications use the random module in
> what could be considered a security related setting. It could be
> anything, the original author needed a random number, picked the
> random module, and now years later, it turns out that  these random
> numbers are security related.
>
> Not good, a good solution would be to replace the current random
> module with a backwards compat implementation that use a better
> algorithm.

It should probably be replaced with Kenji's sfmt-erlang or an
implementation of (C)MWC.

https://groups.google.com/group/comp.soft-sys.math.mathematica/msg/95a94c3b2aa5f077

[Richard O'Keefe]

On 21/06/2012, at 8:03 PM, Claes Wikstrom wrote:
> Indeed, that being said, I think there is quite a few Erlang applications
> out there that use the OTP random module, some, probably quite a few, of
> those applications use the random module in what could be considered
> a security related setting. It could be anything, the original author
> needed a random number, picked the random module, and now years later, it turns out that these random numbers are security related.
>
> Not good, a good solution would be to replace the current random module with
> a backwards compat implementation that use a better algorithm.

Was it the Erlang thread or the SWI Prolog thread where we had a lengthy
discussion about this not so long ago? I remember writing a version of
the 4-cycle algorithm for one of those groups.

Java makes a clear distinction between java.util.Random and
java.Security.SecureRandom, and for good reason.

A pseudo-random number generator to be used for generating test cases and
doing simulations has *different* quality goals from a prng to be used
for security applications. There are plenty of better algorithms for
the first purpose; the Web is full of them. But they *still* are not going
to be trustworthy for cryptographic purposes, and it is *still* going to be
a mistake for anyone to use them so.

We need a secure_random module, and I leave designing that to people
who know something about the area.

[Park, Sungjin]

Thanks for invaluable info.

Anyways, what would be an alternative for random:uniform/1?

Or is there any patch for the problem?

/Sungjin

--
Park, Sungjin

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

Peculiar travel suggestions are dancing lessons from god.

  -- The Books of Bokonon

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

[Kenji Rikitake]

FYI:

* Mersenne Twister PRNGs are NOT cryptographically safe either, although
the random number generation period is much much longer (approx. 2^43
on AS183, (2^19937) - 1 for SFMT) and the state space is far less
easier to be exploited.

* sfmt-erlang is now runable on non-NIF environment (though it's slow)

* I've been working on a lightweight variant of MT called TinyMT (period:
(2^127) - 1, internal state: 28 bytes), including compatibility
functions to the random module, and is capable of generating ~2^58
different RNG streams. It's at
https://github.com/jj1bdx/tinymt-erlang

++> Tuncer Ayaz <tunce...@gmail.com> [2012-06-21 12:47:46 +0200]:

> It should probably be replaced with Kenji's sfmt-erlang or an
> implementation of (C)MWC.
>
> https://groups.google.com/group/comp.soft-sys.math.mathematica/msg/95a94c3b2aa5f077

Kenji Rikitake

[Robert Virding]

The original random module was never meant to be cryptographically safe, it was just a simple and reasonably fast PRNG. The bug, if there is one, was that this was never explicitly stated in the documentation. And as Kenji said even the MT are not cryptographically safe either, and were never meant to be, even though they are much better PRNG.

The best solution is Richard's to create an explicit module for cryptographically safe random numbers. And include a better "normal" PRNG than random, for example Kenji's. Which can be made drop-in compatible with the existing one.

Robert