[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Message-ID: <20131104213237.GA31654@openwall.com>
Date: Tue, 5 Nov 2013 01:32:38 +0400
From: Solar Designer <solar@...nwall.com>
To: George Argyros <argyros.george@...il.com>
Cc: oss-security@...ts.openwall.com, Aggelos Kiayias <aggelos@...yias.com>,
Vladimir Vorontsov <vladimir.vorontsov@...ec.ru>,
gifts <gifts.antichat@...il.com>
Subject: Re: Randomness Attacks Against PHP Applications
Hi George and all,
It's been a year, and I happened to implement some enhancements to
php_mt_seed last month. Although oss-security is not meant to be a
place to announce new versions of security tools, I think having this
one posting added to the existing thread is appropriate.
php_mt_seed is now beyond PoC, and it has a homepage at:
http://www.openwall.com/php_mt_seed/
Please see below for some detail on what has changed:
> On Sun, Sep 23, 2012 at 1:14 AM, Solar Designer <solar@...nwall.com> wrote:
> > The way I'd approach this is by limiting the set of possible seeds based
> > on the first mt_rand() output (perhaps with a min-max range, so _many_
> > seeds will be potentially valid - could be millions, yet significantly
> > fewer than the full 4 billion set). This can be accomplished almost as
> > quickly as cracking the seed based on an exact mt_rand() output (full
> > 31 bits of it, no min-max range) - that is, in one minute on CPU. Then
> > slower, but more generic code may be used to filter out the impossible
> > seeds based on further mt_rand() outputs, until there's just one seed
> > value left. The slowness of that second cracker would not matter much
> > because it'd only need to search a much smaller seed space.
I've implemented this without having to store the subset of seeds
matching the first mt_rand() output. The extra checks are performed
by the same thread that finds the first output match, with the seed
still in a local variable (perhaps still in a CPU register, even).
> > A limitation, though, is that the very first mt_rand() output after
> > seeding must be among those available, even if in truncated form. If it
> > is not, then more of the state has to be maintained in the initial
> > cracking pass, thereby making it slightly slower. When the first output
> > is (at least partially) available, we only need 3 state elements, so
> > they're kept in registers nicely.
I was wrong to say that more state "has to" be maintained. In cases
like this, it's either storage/retrieval or recomputation. For the
current implementation, I chose the latter. Current php_mt_seed
recomputes just the required portions of MT's state if and when the
extra comparisons are invoked.
So current php_mt_seed is able to find seeds based on one or many,
initial or not, and exact or not mt_rand() outputs. Some examples of
this are given here:
http://www.openwall.com/lists/announce/2013/11/04/1
http://www.openwall.com/php_mt_seed/README
http://forum.insidepro.com/viewtopic.php?t=22342
I've also added AVX2 and MIC (Xeon Phi) intrinsics. In basic invocation
mode (that is, given one full and exact mt_rand() output value),
php_mt_seed 3.2 searches the full 32-bit seeds space on a Core i7-4770K
at stock clocks in 48 seconds, and on a Xeon Phi 5110P in 7 seconds. In
advanced invocation modes, these are slightly higher - e.g., 51 seconds
and 11 seconds, respectively, for the sample set of mt_rand(0, 61)
outputs given by the InsidePro forum's user.
On Thu, Sep 27, 2012 at 10:42:24PM -0400, George Argyros wrote:
> This sounds like a good approach and it would probably be faster when
> even truncated outputs are available. The problem is that we
> encountered quite a few applications with a pattern of generating
> tokens like md5(mt_rand()), and in general we found all kinds of weird
> ways to generate tokens that a random developer came up with. In the
> md5 case you won't be able to get the output of mt_rand unless you
> bruteforce the md5 in the same fashion (which would still be faster
> using code like the one you wrote, than using our approach, however
> you will need to write some application specific code for cracking and
> thats what we wanted to avoid).
Well, yes, in your example the md5() currently would not fit into
php_mt_seed's standard code and invocation modes - however, it is fairly
easy to hack into the source.
> Our goal was to provide a usable interface so that people will only
> have to deal with the application specific part of the attack, rather
> than getting the cracking done correctly. Nevertheless, I think that
> applications that leak an mt_rand output are common out there and in
> that case your cracker is a simpler and faster choice since it does
> not require the user to write any C code at all. For cases when more
> complex token generation algorithms are used I think that an approach
> that takes care of all the cracking like the one we used may be
> better. Also in case you use the option to generate some rainbow
> tables (which may take some time too, depending on the "hash" function
> used), the online search time will be a few seconds.
> Another option could be to combine these two approaches and further
> optimize the code that handles the cracking while also providing a
> basic optimized version of mt_rand like the one you wrote to use when
> writing other more complex "hash" functions.
I'm not familiar with your approach. With current php_mt_seed, the
extra md5() or whatever would need to be hacked into the diff()
function, and the MATCH_PURE flag would need to be reset. I don't see
how it can get much easier than that - well, short of providing ready to
use primitives implementing common PHP functions such as md5().
Finally, to make this posting more appropriate for oss-security: it
appears that Drupal and WordPress need to have their random password
generation fixed:
https://twitter.com/solardiz/status/397380784128270336
https://api.drupal.org/api/drupal/core!modules!user!user.module/function/user_password/8
http://core.trac.wordpress.org/ticket/25816
Alexander
Powered by blists - more mailing lists
Please check out the
Open Source Software Security Wiki, which is counterpart to this
mailing list.
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
