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.
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.
> 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.
> 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.
> 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.
> 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.
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.
> > 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.
> > 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.
> 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.
> 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... . 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.
> 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.
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.
> 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.
On Thu, Jun 21, 2012 at 5:58 AM, Claes Wikstrom <kla...@hyber.org> wrote:
> 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.
-- Park, Sungjin
--------------------------------------------------------------------------- ----------------------------------------
Peculiar travel suggestions are dancing lessons from god.
-- The Books of Bokonon
--------------------------------------------------------------------------- ----------------------------------------
* 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
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.
> * 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 <tuncer.a...@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.
