Last Comment Bug 619594 - (CVE-2010-4568) [SECURITY] Tokens generated from weak source of randomness, allowing an attacker to guess a password change token and change the password of any account
(CVE-2010-4568)
: [SECURITY] Tokens generated from weak source of randomness, allowing an attac...
Status: RESOLVED FIXED
[infrasec:auth][ws:critical]
: wsec-authorization, wsec-crypto, wsec-impersonation
Product: Bugzilla
Classification: Server Software
Component: User Accounts (show other bugs)
: 2.14
: All All
: P1 critical (vote)
: Bugzilla 3.2
Assigned To: Max Kanat-Alexander
: default-qa
Mentors:
Depends on:
Blocks: 835424 620540 621591 646578
  Show dependency treegraph
 
Reported: 2010-12-15 18:43 PST by willem
Modified: 2015-12-15 14:48 PST (History)
11 users (show)
LpSolit: approval+
LpSolit: approval4.0+
LpSolit: blocking4.0+
LpSolit: approval3.6+
mkanat: blocking3.6.4+
LpSolit: approval3.4+
mkanat: blocking3.4.10+
LpSolit: approval3.2+
mkanat: blocking3.2.10+
rforbes: sec‑bounty+
See Also:
QA Whiteboard:
Iteration: ---
Points: ---


Attachments
v1 (2.40 KB, patch)
2010-12-16 00:42 PST, Max Kanat-Alexander
glob: review+
Details | Diff | Splinter Review
v2 (3.59 KB, patch)
2010-12-16 12:03 PST, Max Kanat-Alexander
no flags Details | Diff | Splinter Review
Simplest Patch That Defeats Randfindclean (356 bytes, patch)
2010-12-16 15:23 PST, Max Kanat-Alexander
no flags Details | Diff | Splinter Review
generate_random_password (1.82 KB, patch)
2010-12-22 01:04 PST, Byron Jones ‹:glob›
no flags Details | Diff | Splinter Review
RNG Speed Test (2.38 KB, text/plain)
2010-12-22 13:32 PST, Max Kanat-Alexander
no flags Details
Crypt::Random::Source::Win32, Work In Progress (3.97 KB, text/plain)
2010-12-22 17:42 PST, Max Kanat-Alexander
no flags Details
trunk, v1 (1.79 KB, patch)
2010-12-28 16:09 PST, Max Kanat-Alexander
LpSolit: review+
Details | Diff | Splinter Review
Calling Windows Perl's srand more than once is bad (373 bytes, text/plain)
2010-12-29 02:01 PST, Max Kanat-Alexander
no flags Details
Better Windows Demonstration Script (457 bytes, text/plain)
2010-12-29 02:13 PST, Max Kanat-Alexander
no flags Details
The Real Windows Problem (335 bytes, text/plain)
2010-12-29 02:45 PST, Max Kanat-Alexander
no flags Details
compare CORE::rand() and Math::Random::Secure::rand() (508 bytes, text/plain)
2010-12-29 09:38 PST, Frédéric Buclin
no flags Details
Patch for 3.2, v1 (3.96 KB, patch)
2010-12-29 16:06 PST, Max Kanat-Alexander
no flags Details | Diff | Splinter Review
Test generate_random_password (375 bytes, text/plain)
2010-12-29 16:09 PST, Max Kanat-Alexander
no flags Details
Patch for 3.4, v1 (3.98 KB, patch)
2010-12-29 16:31 PST, Max Kanat-Alexander
no flags Details | Diff | Splinter Review
Patch for 3.6, v1 (4.55 KB, patch)
2010-12-29 16:39 PST, Max Kanat-Alexander
LpSolit: review+
Details | Diff | Splinter Review
Patch For 4.0, v1 (4.55 KB, patch)
2011-01-10 14:55 PST, Max Kanat-Alexander
no flags Details | Diff | Splinter Review
Patch for 4.0, v2 (6.63 KB, patch)
2011-01-14 06:07 PST, Max Kanat-Alexander
no flags Details | Diff | Splinter Review
Patch for trunk, v2 (3.82 KB, patch)
2011-01-14 06:18 PST, Max Kanat-Alexander
LpSolit: review+
Details | Diff | Splinter Review
Patch for 3.6, v2 (4.55 KB, patch)
2011-01-14 06:31 PST, Max Kanat-Alexander
no flags Details | Diff | Splinter Review
Patch for 3.6, v2 (Actual) (5.32 KB, patch)
2011-01-14 06:33 PST, Max Kanat-Alexander
no flags Details | Diff | Splinter Review
Patch for 3.4, v2 (4.75 KB, patch)
2011-01-14 06:36 PST, Max Kanat-Alexander
mkanat: review-
Details | Diff | Splinter Review
Patch for 3.6, v3 (6.70 KB, patch)
2011-01-14 06:43 PST, Max Kanat-Alexander
no flags Details | Diff | Splinter Review
Patch for 3.4, v3 (6.09 KB, patch)
2011-01-14 06:49 PST, Max Kanat-Alexander
no flags Details | Diff | Splinter Review
Patch for 3.2, v2 (6.79 KB, patch)
2011-01-14 07:07 PST, Max Kanat-Alexander
no flags Details | Diff | Splinter Review
Use Win32::GuidGen() (1.14 KB, text/plain)
2011-01-16 04:48 PST, Frédéric Buclin
no flags Details
Patch for 3.2, v4 (6.27 KB, patch)
2011-01-18 00:17 PST, Max Kanat-Alexander
no flags Details | Diff | Splinter Review
Patch for 3.4, v4 (5.56 KB, patch)
2011-01-18 00:19 PST, Max Kanat-Alexander
LpSolit: review+
Details | Diff | Splinter Review
Patch for 3.6, v4 (6.05 KB, patch)
2011-01-18 00:21 PST, Max Kanat-Alexander
LpSolit: review+
Details | Diff | Splinter Review
Patch for 4.0, v4 (6.05 KB, patch)
2011-01-18 00:24 PST, Max Kanat-Alexander
LpSolit: review+
Details | Diff | Splinter Review
Patch for 4.0, v5 (6.05 KB, patch)
2011-01-21 17:09 PST, Max Kanat-Alexander
mkanat: review+
Details | Diff | Splinter Review
Patch for 3.6, v5 (6.12 KB, patch)
2011-01-21 17:16 PST, Max Kanat-Alexander
mkanat: review+
Details | Diff | Splinter Review
Patch for 3.4, v5 (5.63 KB, patch)
2011-01-21 17:21 PST, Max Kanat-Alexander
LpSolit: review+
Details | Diff | Splinter Review
Patch for 3.2, v5 (6.27 KB, patch)
2011-01-21 17:27 PST, Max Kanat-Alexander
LpSolit: review+
Details | Diff | Splinter Review

Description willem 2010-12-15 18:43:27 PST
User-Agent:       Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.2.13) Gecko/20101212 Gentoo Firefox/3.6.13
Build Identifier: Bugzilla-3.6.3, as well as the version running on bugzilla.mozilla.org

To Whom It May Concern,

the Bugzilla 3.6.3, the bugzilla.mozilla.org website, and likely other versions and instances of Bugzilla contain a critical vulnerability that can be used to recover a password reset token for any account. An attacker with an account on the bugzilla system can request a password reset for any other account and through efficient bruteforce recover the token, the attacker can use the token to changethe password of the victim's account and login as the victim.

A Quick explanation.

Bugzilla uses rand and srand in perl, which are based on srand48 and drand48 on Linux (and possibly other OS's) srand48 is seeded with at most 32 bit of entropy. Using a modern machine one can go through these 32bits in a very short amount of time, less than 10 minutes on my machine.

Bugzilla uses (s)rand to generate their tokens and to generate their login cookie. When accessing token.cgi with the attackers login credentials Bugzilla will login the attacker and send him a login cookie made using generate_random_password, the attacker can recover the seed used for srand from this, and use it to know the full internal state of the random number generator.

The same request is used by the attacker to request a password reset for the account the attackers wants to take over. For the reset procedure a token will be generated and send to the victim, if the attacker can find this token he can reset the victims password. Since the token is also created using generate_random_password and uses the internal random state that was left after making the login cookie the attacker can easily deduce the token send to the victim.


Steps for a succesful attack:

request a password reset for the victim account, while logging into to Bugzilla:

POST /token.cgi
---
Bugzilla_login=<ATTACKER_LOGIN>&Bugzilla_password=<ATTACKER_PASSWORD>&Bugzilla_remember=on&loginname=<VICTIMLOGINNAME>&a=reqpw



the response from the server will contain:

Set-Cookie: Bugzilla_logincookie=LPfN86mTdY; path=/; expires=Fri, 01-Jan-2038 00:00:00 GMT; secure; HttpOnly

while the victim will be sent an email with a token in it.


Next the attacker finds the random state used to generate his login Cookie and calculates the next token that BugZilla generated:

./randfindclean LPfN86mTdY
found at seed: -43631713 // fd663b9f
YKWG0y4oQT

(randfindclean finds the seed used to make the logincookie, and then calculates the token based on rand state)

and uses the token to login as the victim and change their password.

---- copy paste from the victims email ---
You have (or someone impersonating you has) requested to change your
Bugzilla password. To complete the change, visit the following link:

https://bugzilla.mozilla.org/token.cgi?t=YKWG0y4oQT&a=cfmpw
-----

If there are any questions, please don't hesitate to contact me,
   Willem Pinckaers.



Reproducible: Always

Steps to Reproduce:
1.login while requestion a password change for the victim
2.based on logincookie, calculate the password token
3.change the victim password and login as the victim
Actual Results:  
Got access to the victim's account

Expected Results:  
r
Comment 4 Max Kanat-Alexander 2010-12-15 22:43:28 PST
This is an extremely impressive security bug. I haven't tested it yet to reproduce, but I am fairly confident that the description is correct and the vulnerability is valid.

The solution, I suspect, is to use a better system than Perl's rand(), which should be fairly simple. I wasn't aware that Perl's rand was so weak; that's very unfortunate.
Comment 5 Max Kanat-Alexander 2010-12-15 22:46:04 PST
Due to the severity of this issue, the security process for this bug will be different than previous bugs. We will patch the problem by fixing rand, but with an innocuous commit message, something like "use a better random number generator than Perl's built-in rand()", keep this bug closed, and release the fixed versions. We will probably also send out a security advisory with the release, but without too many details. Then we will open up this bug between a week and a month later.
Comment 6 Bradley Baetz (:bbaetz) 2010-12-15 22:57:59 PST
This is quite impressive.

The fact that we use the same random generator for the login cookie and the token makes this easier to exploit, but we'd be vulnerable even without this.
Comment 7 Reed Loden [:reed] (use needinfo?) 2010-12-15 23:00:39 PST
http://wellington.pm.org/archive/200704/randomness/ has some information on Perl's RNG and possible alternatives.
Comment 8 Byron Jones ‹:glob› 2010-12-15 23:25:11 PST
other mozilla perl tools should be audited for this issue too; from what i can see despot, litmus and mozbot may all be affected.
Comment 9 Max Kanat-Alexander 2010-12-15 23:39:51 PST
So, it looks like the best solution that I've found, so far, is to use Math::Random::MT::Auto to generate random numbers instead of Perl's built-in rand(). I'd like to find a module that would just do all our random string generation for us, but I don't see any module on CPAN that will do that securely.

I believe that we will also have to seed the module's random number generator the PerlChildInitHandler for each httpd child, also, just like we do with Perl's core srand() now.
Comment 10 Max Kanat-Alexander 2010-12-15 23:44:59 PST
Due to the way that release schedules work, I'm pretty sure I won't be able to block 4.0 on this. When we do major releases, we want to release *just* that release in the release announcement. What this means is that we'll do 4.0 and then we'll do 4.0.1 shortly after with this fix. I also really don't want to spring a fix like this on administrators during the holidays when they aren't around to patch their Bugzillas. 

Unfortunately this means that the fix for this probably won't be released until January, as terrifically painful as that is for me to say, and even though I'd like to have a patch for it tonight.
Comment 11 Reed Loden [:reed] (use needinfo?) 2010-12-15 23:48:31 PST
I disagree. The holidays are generally some of the *best* times to get downtime in order do upgrades such as this. This is too important to hold until January.
Comment 12 timeless 2010-12-15 23:56:10 PST
i agree w/ reed's comment 11.

further, i'd much rather bury this fix in a major release upgrade than let people notice it in a minor release.
Comment 13 Max Kanat-Alexander 2010-12-16 00:09:54 PST
Reed and timeless: I see where you're coming from, but I don't think that the holidays are good times for the large majority of the 10,000 or so Bugzilla installations in the world, particularly many small-to-medium shops where there are 0 or 1 IT people who are certainly on vacation over the holidays.
Comment 14 Max Kanat-Alexander 2010-12-16 00:10:33 PST
We could do all the releases simultaneously with 4.0, though, and just send out separate emails and do a separate news announcement. That would probably be OK.
Comment 15 Max Kanat-Alexander 2010-12-16 00:42:00 PST
Created attachment 498053 [details] [diff] [review]
v1

This switches us to using Math::Random::MT::Auto for token generation. I also made the tokens longer while I was at it, for good measure.
Comment 16 Byron Jones ‹:glob› 2010-12-16 01:22:34 PST
Comment on attachment 498053 [details] [diff] [review]
v1

r=glob: this looks good to me, and works as advertised.
Comment 17 Gervase Markham [:gerv] 2010-12-16 09:27:30 PST
The docs for M::R::M::A say:

"You don't even need to bother seeding the PRNG (i.e., you don't need to call "srand"), as that gets done automatically when the module is loaded by Perl."

http://search.cpan.org/~jdhedden/Math-Random-MT-Auto-6.15/lib/Math/Random/MT/Auto.pm#QUICKSTART

Gerv
Comment 18 Frédéric Buclin 2010-12-16 09:30:16 PST
Comment on attachment 498053 [details] [diff] [review]
v1

Instead of requiring another Perl module, why not simply encrypt the token generated by rand() with SHA256 using our site_wide_secret local parameter? I doubt the attacker can crack that.
Comment 19 Frédéric Buclin 2010-12-16 10:21:06 PST
(In reply to comment #14)
> We could do all the releases simultaneously with 4.0, though

... or release 4.0rc2 instead, if we have tons of security bugs, and release 4.0 final alone 10 days later if no regression is found.
Comment 20 Max Kanat-Alexander 2010-12-16 11:07:06 PST
(In reply to comment #17)
> "You don't even need to bother seeding the PRNG (i.e., you don't need to call
> "srand"), as that gets done automatically when the module is loaded by Perl."

  Each httpd child must be seeded separately or all children have the same random seed. There was a critical security bug filed about it a few years back.

(In reply to comment #18)
> Instead of requiring another Perl module, why not simply encrypt the token
> generated by rand() with SHA256 using our site_wide_secret local parameter? I
> doubt the attacker can crack that.

  There are various problems with that:

  1) There are only 2^32 (on Linux/BSD) possible random strings that generate_random_password can generate. So, hashing them would make the attack take a few milliseconds more, but not help.

  2) On Windows, there are only 32768 possible random strings that generate_random_password can generate. This means that there are only 2^15 possible site_wide_secret values on Windows.

  3) We need to generate secure random strings that are longer than a SHA1 hash sometimes--for example, for site_wide_secret. Also, secure random strings that are shorter than a SHA1 hash--for example, for the multipart separator in Bugzilla::CGI.

  4) A SHA1 hash is longer than tokens.token, so we would have to do a schema change on the stable branches.

  It's also possible that extensions or customizations are dependent upon the security of generate_random_password.

  More or less, I don't want to have to figure out explicitly everywhere that we use generate_random_password and make the call points secure. I just want to make generate_random_password itself secure.
Comment 21 Max Kanat-Alexander 2010-12-16 11:28:28 PST
(In reply to comment #19)
> ... or release 4.0rc2 instead, if we have tons of security bugs, and release
> 4.0 final alone 10 days later if no regression is found.

  Ah, yeah, that's probably the best plan.
Comment 22 Gervase Markham [:gerv] 2010-12-16 11:36:28 PST
Do you think we need to make people regenerate their site_wide_secret then, if there are only a few possible values it can have (even though it's very long)? 

I agree we should wait for the storm of bounty-fuelled security bugs to die down, then release a 4.0rc2 along with stable releases with the fixes, then 4.0 final a little later.

Gerv
Comment 23 Max Kanat-Alexander 2010-12-16 11:40:41 PST
(In reply to comment #22)
> Do you think we need to make people regenerate their site_wide_secret then, if
> there are only a few possible values it can have (even though it's very long)? 

  Yes. I'll post a new patch that does that.

> I agree we should wait for the storm of bounty-fuelled security bugs to die
> down, then release a 4.0rc2 along with stable releases with the fixes, then 4.0
> final a little later.

  Or release 4.0.1 with all the bounty-fueled issues. I'd really like to get 4.0 out as soon as is reasonably possible, and since we don't know when the filing storm will die down, I think it might just be best to wait, but to inform selected large, public installations about this particular issue and let them patch it quietly themselves.

  This particular bug has been in Bugzilla as long as we've used token-based resets (several years), and nobody had reported it to us before yesterday, so I don't think we're in much danger of it being discovered again and exploited before January.
Comment 24 Dave Miller [:justdave] (justdave@bugzilla.org) 2010-12-16 12:01:46 PST
I don't like the idea of making a new release with known security issues in it that we have patches for.  When the security release does come out, that's telling everyone "we didn't care enough about this to fix it in this release, even though we knew about it."  Schedule be damned, unfortunately.  This is a good reason to break the schedule.
Comment 25 Max Kanat-Alexander 2010-12-16 12:03:51 PST
Created attachment 498181 [details] [diff] [review]
v2

This one also forcibly regenerates site_wide_secret.
Comment 26 Frédéric Buclin 2010-12-16 12:05:19 PST
(In reply to comment #23)
>   Or release 4.0.1 with all the bounty-fueled issues. I'd really like to get
> 4.0 out as soon as is reasonably possible

I also would like to release 4.0 asap, but I have several concerns:

1) Releasing 4.0rc2 means we will also release 3.2.10. Releasing 4.0 alone first, then 4.0.1 with the security fixes means we won't, as 3.2 would have reached EOL. This is not a minor thing, IMO (even if they should upgrade to a newer version).

2) Releasing 4.0rc2 first means that when 4.0 final comes out, we won't then require another new module. I much prefer that we don't ask admins to again install a new one, if possible. We have to do that for stable branches already, that is very unfortunate.

3) If several other sec bugs are filed in the coming weeks, I would prefer the rc2 -> final -> .1 way (if we missed some), than final -> .1 -> .2 in a quick cycle. I feel bad about it as the QA lead.
Comment 27 Frédéric Buclin 2010-12-16 12:06:06 PST
(In reply to comment #24)
> I don't like the idea of making a new release with known security issues in it
> that we have patches for.  When the security release does come out, that's
> telling everyone "we didn't care enough about this to fix it in this release,
> even though we knew about it."  Schedule be damned, unfortunately.  This is a
> good reason to break the schedule.

+1
Comment 28 Max Kanat-Alexander 2010-12-16 12:21:46 PST
I see where both of you are coming from. However, we need to also give some admins at least a few weeks to apply this patch before we can even release. So we'd be missing our release window for 4.0 without doing any release at all. 

This vulnerability has been around for years; it's not going to start radioactively mutating and become The Blob and eat us all in a few weeks.

Also, we don't want to rush out a fix for this if the fix isn't going to be right. We should give admins time to test this patch and respond, and make sure that we have a really solid fix.
Comment 29 Richard Soderberg [:atoll] 2010-12-16 12:41:33 PST
I advise bundling Math::Random::MT::Perl into Bugzilla and supporting an optional dependency Math::Random::MT::Auto, so that a secure RNG is available to all users immediately, and those that install the optional XS dependency (MT::Auto) gain improved RNG performance.
Comment 30 Max Kanat-Alexander 2010-12-16 13:04:46 PST
Okay, I just looked at Math::Random::MT::Perl, and its default seeding system is not adequate. We'd have to re-implement sections of Math::Random::MT::Auto, and re-implementing anything involving or surrounding security is something I'd rather not do unless it's necessary.

Also, Math::Random::MT::Perl requires Time::HiRes, which is an XS module, so we can't bundle Time::HiRes. I thought that we required Time::HiRes already, but we actually don't seem to. So even though I thought we could bundle MT::Perl, we can't.
Comment 31 Frédéric Buclin 2010-12-16 13:11:40 PST
Time::HiRes is in the core modules of Perl, see e.g.:

 http://perldoc.perl.org/5.8.8/Time/HiRes.html
Comment 32 Max Kanat-Alexander 2010-12-16 13:18:09 PST
Ah, indeed it is. It was missing from my 5.8.1 installation for some reason.

I still feel more comfortable with the auto-seeding algorithm of MT::Auto than I do with the usage of MT::Perl. After all, it's the seed that's our problem here, not the RNG itself.
Comment 33 Bradley Baetz (:bbaetz) 2010-12-16 13:50:05 PST
(In reply to comment #32)
> I still feel more comfortable with the auto-seeding algorithm of MT::Auto than
> I do with the usage of MT::Perl. After all, it's the seed that's our problem
> here, not the RNG itself.

not really - the problem is that we have two consecutive queries being run on the same seed. The attack doesn't rely on knowing the seed as much as it relies on the RNG being effectively deterministic.

And I agree with Dave, BTW. And we should release 3.2 as well.

(The alternate way of doing this is to hash the id and timestamp and have the cookie contain (id,timestamp,hash) and not use a token at all)
Comment 34 Gervase Markham [:gerv] 2010-12-16 13:50:44 PST
I know it's a shame to miss a release date we were hoping to hit, but this seems to be rather an unusual situation. Max: you talk about a "release window" - is that just "when we were hoping to release", or is there some other reason why the window has an "end"?

This discussion isn't just about this bug - it's about the four others we already have, and the others which will be filed over the coming days and weeks. We should plan for getting more, and that means the wisest thing IMO is to delay the 4.0 release.

Gerv
Comment 35 Max Kanat-Alexander 2010-12-16 14:00:26 PST
(In reply to comment #33)
> not really - the problem is that we have two consecutive queries being run on
> the same seed.

  The fact that Perl's srand is poorly seeded *is* the underlying vulnerability. If it weren't, this vulnerability would not be a vulnerability. For example, with MT::Auto, I believe you'd be running randfindclean until the end of time.

> (The alternate way of doing this is to hash the id and timestamp and have the
> cookie contain (id,timestamp,hash) and not use a token at all)

  That's not a valid method of session persistence. It contains a timestamp.
Comment 36 Max Kanat-Alexander 2010-12-16 14:04:25 PST
(In reply to comment #34)
> I know it's a shame to miss a release date we were hoping to hit, but this
> seems to be rather an unusual situation. Max: you talk about a "release window"
> - is that just "when we were hoping to release", or is there some other reason
> why the window has an "end"?

  The current planned release date of Bugzilla 4.0 is Tuesday, December 21. 

  For PR reasons, the best days to do major releases are Tuesdays.

  So our next Tuesday after that would be the 28th. No good--everybody's on vacation, including a lot of journalists.

  After that would be January 4. Possibly decent, but not great, because everybody's just gotten back from vacation and is super-busy.

  So then we'd be looking at January 11, realistically.

  By the way, all of these reasons are also reasons that we should not be doing a security release in this timeframe. So I'd like to release 4.0 on December 21 and our security releases on January 11, which is a time when people are actually likely to be around and available to do the installation.

> We should plan for getting more, and that means the wisest thing IMO is
> to delay the 4.0 release.

  No, actually if we plan to get more, the wisest thing to do would be to release 4.0 instead of delaying it by some uncertain amount of time. Bugzilla's release history shows that it is much better to release soon than to wait for an uncertain period.
Comment 37 Max Kanat-Alexander 2010-12-16 14:06:37 PST
  Also, I'd like two separate press focuses--one that is "Hey, we've released Bugzilla 4.0! Hooray!" and another that is, "Hey, there is a serious issue that you need to patch!"

  Both of those really deserve their own media period.

  Remember that we are interested not just in this very important security issue, but also the long-term success of the Bugzilla Project and the culmination of the work that we've been doing for this past year.
Comment 38 Max Kanat-Alexander 2010-12-16 14:24:57 PST
  Ah, MT::Auto may not be sufficient for our purposes. From the Wikipedia page on the Mersenne Twister:

  "The algorithm in its native form is not suitable for cryptography (unlike Blum Blum Shub). Observing a sufficient number of iterates (624 in the case of MT19937) allows one to predict all future iterates."

  Under mod_perl it might be possible to get 624 iterates from one httpd child, if one worked cleverly at it.
Comment 39 Max Kanat-Alexander 2010-12-16 14:58:38 PST
  So far, the only reasonable alternative I see on CPAN is Math::Random::ISAAC. However, to get reasonable performance out of it, you have to install Math::Random::ISAAC::XS also. Also, Math::Random::ISAAC doesn't seed itself, so we'd have to basically re-implement the seeding code from Math::Random::MT::Auto.
Comment 40 Gervase Markham [:gerv] 2010-12-16 15:13:28 PST
I'm sure there must be a way of using Math::Random::MT::Auto which avoids the "624" problem. Can we combine values? Can we reseed periodically using one of the random values? Or the current time?

Are there really no Perl modules which provide cryptographic randomness? What's wrong with Crypt::OpenSSL::Random? Dependencies too large? Does Crypt::Random not run on Windows?

Gerv
Comment 41 Max Kanat-Alexander 2010-12-16 15:16:34 PST
(In reply to comment #40)
> Are there really no Perl modules which provide cryptographic randomness? 

  Math::Random::ISAAC should.

> What's wrong with Crypt::OpenSSL::Random? 

  It doesn't compile on Windows.

> Does Crypt::Random not run on Windows?

  It doesn't support Windows in its randomness sources.
Comment 42 Max Kanat-Alexander 2010-12-16 15:23:46 PST
Created attachment 498238 [details] [diff] [review]
Simplest Patch That Defeats Randfindclean

This is the simplest possible patch that defeats randfindclean. Perl seeds from /dev/urandom if it is available, so this is probably actually a secure solution, on Linux. Every string that we send to the user will have a different seed, so no string is guessable from the previous seed.

However, on Windows, I believe that Perl's rand() may still be critically weak, if it does indeed have a period of 2^15.
Comment 43 Max Kanat-Alexander 2010-12-16 16:17:11 PST
So, on Windows the first solution that I would think of would be to use MT::Auto *and* call srand() on every generate_random_password() call.

However, this turns out to be really very slow, particularly compared to just using Math::Random::ISAAC with MT::Auto's seeding code:

Benchmark: timing 10000 iterations of isaac_pp, isaac_xs, mt_auto...
  isaac_pp:  1 wallclock secs ( 0.40 usr +  0.00 sys =  0.40 CPU) @ 25000.00/s
  isaac_xs:  0 wallclock secs ( 0.12 usr +  0.00 sys =  0.12 CPU) @ 83333.33/s
  mt_auto: 11 wallclock secs ( 4.73 usr +  6.26 sys = 10.99 CPU) @ 909.92/s

Because ISAAC is a secure PRNG, we don't have to re-seed it on every generate_random_password call, making it considerably faster than using MT::Auto in our case. Even the pure-perl version of ISAAC is fast enough for us. 

The only thing we'd have to do is to take all the seeding code from MT::Auto, which would probably be good to do anyway, since then we could also eliminate MT::Auto's possibility of calling out to random.org for bits.

The only remaining question is--does ISAAC work on ActiveState and Strawberry?
Comment 44 Max Kanat-Alexander 2010-12-16 16:19:34 PST
And for those curious, the speed of doing Perl's built-in srand before every generate_random_password call is:

  builtin_sr:  0 wallclock secs ( 0.09 usr +  0.07 sys =  0.16 CPU) @ 62500.00/s

So it's much faster than ISAAC still, but I don't think that the speed difference is going to be really significant to us. On most page loads, we call generate_random_password once or twice at most. There are some places that may call it more often, and I'd still like those to be fast, but we don't need it to be super-instantaneous.
Comment 45 Frédéric Buclin 2010-12-16 16:36:17 PST
(In reply to comment #43)
> The only remaining question is--does ISAAC work on ActiveState and Strawberry?

I cannot find it in ActivePerl.
Comment 46 Byron Jones ‹:glob› 2010-12-16 16:52:54 PST
(In reply to comment #43)
> The only remaining question is--does ISAAC work on ActiveState and Strawberry?

strawberry:  yes (including XS module)

activestate: core is in activestate's repo, but the XS module isn't
http://searchcpan.activestate.com/module/Math::Random::ISAAC
http://searchcpan.activestate.com/module/Math::Random::ISAAC::XS
Comment 47 Frédéric Buclin 2010-12-16 17:01:31 PST
(In reply to comment #36)
>   The current planned release date of Bugzilla 4.0 is Tuesday, December 21. 

The "current planned release date" is only a few days old. We initially planned to release 4.0 on Tuesday, Dec 13, i.e. last week, but we delayed it because QA is not done yet, and we still have one open blocker (which got a patch after Dec 13). So nothing is written in stone here. And despite you see where we "are coming from", your arguments are not better than ours, and there are several votes in favor of 4.0rc2, including justdave, who remains our project lead, AFAIK. Much better is to come to a consensus than impose an unilateral decision.
Comment 48 Byron Jones ‹:glob› 2010-12-16 17:03:21 PST
for what it's worth, rc2 gets my vote too.
Comment 49 Frédéric Buclin 2010-12-16 17:06:01 PST
(In reply to comment #46)
> activestate: core is in activestate's repo, but the XS module isn't
> http://searchcpan.activestate.com/module/Math::Random::ISAAC
> http://searchcpan.activestate.com/module/Math::Random::ISAAC::XS

ISAAC is only available on Perl 5.8 and 5.10, not on 5.12, AFAICS.
Comment 50 Byron Jones ‹:glob› 2010-12-16 17:14:44 PST
(In reply to comment #49)
> ISAAC is only available on Perl 5.8 and 5.10, not on 5.12, AFAICS.

ah, right.  sorry about that.
Comment 51 Frédéric Buclin 2010-12-16 18:03:58 PST
http://search.cpan.org/~jawnsy/Math-Random-ISAAC-1.002/lib/Math/Random/ISAAC.pm#USAGE_WARNING says that Time::HiRes is as good as /dev/random as seed. The advantage of using Time::HiRes over /dev/random is that it is available on Windows too. rsoderberg suggested to combine it e.g. with our site_wide_secret key to make the seed even harder to crack.

If we call srand() right before rand(), this means we wouldn't need any other dependency, right?
Comment 52 Bradley Baetz (:bbaetz) 2010-12-16 21:34:27 PST
(In reply to comment #35)
> (In reply to comment #33)
> > not really - the problem is that we have two consecutive queries being run on
> > the same seed.
> 
>   The fact that Perl's srand is poorly seeded *is* the underlying
> vulnerability. If it weren't, this vulnerability would not be a vulnerability.
> For example, with MT::Auto, I believe you'd be running randfindclean until the
> end of time.

No, that's not the seeding. If srand seeded using /dev/urandom we'd still be vulnerable because the algorithm used is predictable. Its the search-space of the algorithm.

> > (The alternate way of doing this is to hash the id and timestamp and have the
> > cookie contain (id,timestamp,hash) and not use a token at all)
> 
>   That's not a valid method of session persistence. It contains a timestamp.

which is used as an expiry time. We can use a token instead/as well, but still have the signed hash.
Comment 53 Max Kanat-Alexander 2010-12-16 23:46:07 PST
(In reply to comment #51)
> http://search.cpan.org/~jawnsy/Math-Random-ISAAC-1.002/lib/Math/Random/ISAAC.pm#USAGE_WARNING
> says that Time::HiRes is as good as /dev/random as seed.

  That is not true. The seed needs to be composed of far more than 32 (or even 51/64) bits to be secure. I am sure that the writing in that POD is a typo, and it meant "the same as option 3" (which is "localtime").

> If we call srand() right before rand(), this means we wouldn't need any other
> dependency, right?

  Unfortunately, on Windows, we still need another module. The problem is that rand() on Windows can only produce 32768 random values, no matter what.

  So what we will do, for the branches, is:

  * If we're on Windows, require Math::Random::ISAAC and use it.
  * If we're not on Windows, use Math::Random::ISAAC if it's available,
    otherwise do an "srand" at the start of generate_random_password and
    use the system rand().

  For trunk (and probably 4.0) we will just always use Math::Random::ISAAC, possibly even requiring the XS version if we can get it into ActiveState and there's no cross-platform barrier in general with it.

  This will involve creating a new module, something like Bugzilla::RNG or Bugzilla::Random, that includes the seed-gathering code from Math::Random::MT::Auto and uses it to properly seed Math::Random::ISAAC.
Comment 54 Max Kanat-Alexander 2010-12-16 23:49:14 PST
(In reply to comment #52)
> which is used as an expiry time. We can use a token instead/as well, but still
> have the signed hash.

  Yeah, that's true, we could do that actually. I don't feel too confident about using site_wide_secret for things that are that critically important though--I don't want the exposure of site_wide_secret to allow you to log in as anybody.
Comment 55 Bradley Baetz (:bbaetz) 2010-12-17 01:20:56 PST
Its an extra layer not a replacement if you sign the token. But separate bug to this.
Comment 56 Frédéric Buclin 2010-12-18 07:16:06 PST
(In reply to comment #54)
>   Yeah, that's true, we could do that actually. I don't feel too confident
> about using site_wide_secret for things that are that critically important
> though--I don't want the exposure of site_wide_secret to allow you to log in as
> anybody.

You mean you fear that someone could crack site_wide_secret and use it?

I'm marking this bug as blocking 4.0 as we are going to release 4.0rc2 which will contain various security fixes, including this one I hope.
Comment 57 Frédéric Buclin 2010-12-18 07:21:10 PST
Comment on attachment 498181 [details] [diff] [review]
v2

Cancelling reviews as it seems we won't use this patch, per the recent comments.

I would like bbaetz and mkanat to agree on the root cause(s) of the problem. From my own understanding (which is pretty limited in this area), it seems that the problem is that once the seed is known, it's currently easy to guess the next random token. But maybe the problem is also that it's currently too easy to guess the seed? In which case the problem is on both sides: make it harder to guess the seed, and make it harder to guess the next token even if the seed is known.
Comment 58 Frédéric Buclin 2010-12-18 07:51:29 PST
(In reply to comment #42)
> This is the simplest possible patch that defeats randfindclean. Perl seeds from
> /dev/urandom if it is available, so this is probably actually a secure
> solution, on Linux. Every string that we send to the user will have a different
> seed, so no string is guessable from the previous seed.

Is it really the right thing to do? Per http://perldoc.perl.org/functions/srand.html, we shouldn't call srand() more than once:

"Do not call srand() (i.e., without an argument) more than once per process. The internal state of the random number generator should contain more entropy than can be provided by any seed, so calling srand() again actually loses randomness."
Comment 59 Bradley Baetz (:bbaetz) 2010-12-18 22:59:55 PST
Its a bit of both. On unix, the seed isn't guessable (it uses /dev/urandom), but the search-space is small enough that that we can just try them all.

As well, there's basically only one seed that gives the first string, so once you've found it you know that you're right. Even if the search space was 2^64

> Is it really the right thing to do? Per
> http://perldoc.perl.org/functions/srand.html, we shouldn't call srand() more
> than once:

I *suspect* it doesn't hurt in this case, because we're generating a single string and then stopping, and outside of this issue we're only going to generate one per seed anyway. But this stuff isn't something I'm exactly an expert on...

perl-Math-Random-MT-Auto is packaged by Fedora, which is a plus. But it looks like that module auto-seeds using random.org if it can't find anything else. That's an Interesting designing choice, and we should probably turn that "feature" off.

Note that for windows, the function it uses is only available in XP and win2003 or greater. Do we support win2000? (Its also documented as deprecated - http://msdn.microsoft.com/en-us/library/aa387694%28VS.85%29.aspx)
Comment 60 Frédéric Buclin 2010-12-19 04:48:30 PST
(In reply to comment #59)
> As well, there's basically only one seed that gives the first string, so once
> you've found it you know that you're right. Even if the search space was 2^64

Ah ok, so that's a problem. ISAAC is not affected by this problem, right? i.e. different seeds can generate the same string at some point and then differ again, which makes it impossible to know the seed for sure?


> I *suspect* it doesn't hurt in this case, because we're generating a single
> string and then stopping, and outside of this issue we're only going to
> generate one per seed anyway.

But if the seed becomes too easy to guess, you could also guess the generated string. At least, that's how I understand it.


> Note that for windows, the function it uses is only available in XP and win2003
> or greater. Do we support win2000?

Windows 2000 and Windows XP SP2 reached EOL earlier this year. Now, I wouldn't want to break compatibility with these OSes as probably some older Bugzilla installations still run on these OS (especially Bugzilla 3.2 and 3.4). In that case, we should make these extra modules optional.
Comment 61 Max Kanat-Alexander 2010-12-19 14:52:20 PST
Hey hey. I've been away for a few days, but I just read all the recent comments and I can clarify what the problem is and what the solution is:

The way randfindclean works is that it determines the seed used to generate the cookie. It does this by trying every number between 0 and 2^32 as the seed for srand(), and seeing which one generates that cookie. Then, it knows exactly how many times rand() was called after that, so it can just regenerate the password-reset token by essentially doing generate_random_password itself, using that found seed. Adding in an srand() at the start of generate_random_password means that the token is generated from a different seed than the cookie was, so knowing the cookie's seed doesn't help you, and randfindclean is defeated. This isn't a perfect solution, but it keeps Bugzilla effectively secure, as long as Bugzilla isn't running on Windows. 

On Windows, there is another problem: there are only 32768 seeds. This mean there are only about 32768 possible tokens that Bugzilla could generate, making it far too easy to guess even with brute force. This happens because the random number generator in Windows is bad, and Perl uses that bad random number generator.

MT::Auto is a reasonable solution, because it uses something like 19973 bits as its seed, so you can't just try all the seeds. However, MT auto is not considered suitable for cryptographic purposes--even the authors of the Mersenne Twister algorithm (which is what MT::Auto uses--that's what MT stands for) say so in their original paper on the algorithm.

So, I want to use ISAAC, an algorithm that is considered appropriate for cryptographic purposes, and also has a very large seed--256 32-bit integers. The advantage of ISAAC is that even if I gave you the entire sequence of numbers it generated, you couldn't guess the next number unless you already knew the seed, which is unguessable.
Comment 62 Max Kanat-Alexander 2010-12-19 15:01:00 PST
As far as Windows 2000 support, yes, this fix will end Windows 2000 support. There is no reasonable way to have a secure Bugzilla on any version of Windows that lacks RtlGenRand.

To be clear, here is my plan:

* On the branches, for Windows we will require and use ISAAC.
* On the branches, for non-Windows installations we will simply call srand at the start of generate_random_password, or optionally, if ISAAC is installed, use it.
* On trunk, we will require and use ISAAC always.


The only problem is that the ISAAC module on CPAN does not know where to get a proper random seed from. The MT::Auto module *does* know where to get a proper random seed from. So, I need to copy the seeding code from MT::Auto and modify it to seed ISAAC. This will probably involve creating and publishing an ISAAC::Auto CPAN module, which could take some time, so I may just include that code directly in Bugzilla for the branches.
Comment 63 Frédéric Buclin 2010-12-19 15:09:17 PST
(In reply to comment #62)
> As far as Windows 2000 support, yes, this fix will end Windows 2000 support.

This is a problem. We cannot throw Windows 2000 users in the dust on stable branches, especially security ones. Moreover, Bugzilla will notify Windows 2000 admins that a new version is available, respectively 3.2.10 and 3.4.10, and when installing it, it will miserably fail. What do you plan to do with them? Just don't care?
Comment 64 Frédéric Buclin 2010-12-19 15:21:47 PST
Hum, this is weird:

 http://msdn.microsoft.com/en-us/library/aa387694%28VS.85%29.aspx

says that you need at least Windows XP to use RtlGenRandom, but it also recommends to use CryptGenRandom, which is available on Windows 2000:

 http://msdn.microsoft.com/en-us/library/aa379942%28v=VS.85%29.aspx

Maybe we could ask the maintainer of the ISAAC Perl module to use CryptGenRandom instead. This would save installations still running on Windows 2000.
Comment 65 Frédéric Buclin 2010-12-19 15:24:33 PST
(In reply to comment #64)
> Maybe we could ask the maintainer of the ISAAC Perl module

err.... I meant of Math::Random::MT::Auto.
Comment 66 Frédéric Buclin 2010-12-19 15:32:41 PST
I filed https://rt.cpan.org/Public/Bug/Display.html?id=64058 about this.
Comment 67 Bradley Baetz (:bbaetz) 2010-12-19 17:40:48 PST
Its times like this I prefer python....

So ISAAC, seeded with Crypt::Random on unix and CryptGenRandom on windows?
Comment 68 Max Kanat-Alexander 2010-12-19 23:24:39 PST
(In reply to comment #64)
> Maybe we could ask the maintainer of the ISAAC Perl module to use
> CryptGenRandom instead.

  The ISAAC perl module doesn't seed itself at all. The seeding is work that I would be doing. But yes, I would be basing it on the code from MT::Auto.

  I would need a Windows 2000 installation that I had personal access to in order to test this, and the fix would delay the fixes for all the other branches, possibly by a significant amount (working with Win32::API is not easy).

  Also, CryptGenRandom is not the ideally recommended method for generating this data, because apparently it pulls in the whole crypto API code, which may not be what's wanted. I'm not sure if that's just a memory issue, or if the problem is that the code might not be in the library, or if it's just a disk space issue, though.

(In reply to comment #67)
> So ISAAC, seeded with Crypt::Random on unix and CryptGenRandom on windows?

  Yes, that's pretty much the solution. Except I really think it would be better to use RtlGenRandom when we can.
Comment 69 Byron Jones ‹:glob› 2010-12-20 01:11:27 PST
it seems to me the problem is the //predictability// of generated tokens... is there anything wrong with using the existing code to generate a random value, but have the token module return a MD5 of the random value + salt as the token?
Comment 70 Frédéric Buclin 2010-12-20 11:12:12 PST
(In reply to comment #68)
>   Also, CryptGenRandom is not the ideally recommended method for generating
> this data, because apparently it pulls in the whole crypto API code

Yeah, I checked, and it's fine to use RtlGenRandom, see the discussion in bug 504270. So forget my suggestion. :) This is still a problem to throw all Windows 2000 installations into the dust, though.
Comment 71 Max Kanat-Alexander 2010-12-20 13:22:55 PST
(In reply to comment #69)
> it seems to me the problem is the //predictability// of generated tokens... is
> there anything wrong with using the existing code to generate a random value,
> but have the token module return a MD5 of the random value + salt as the token?

  There are a few problems:

  1) An MD5 hash is longer than the tokens.token column, so would require a schema change on the branches.

  2) It somewhat depends on what the salt is that you use, but because there are only 2^32 seeds, almost anything you pick that's based on srand/rand will be crackable. Basically, no matter how many contortions you put the token through, the cracker can put the token through the same contortions simply by trying all 2^32 possibilities. Even squaring it and making it 2^64 would mean that the token could be cracked in about six months, which is still too short of a time period. Imagine the resources that an attacker would dedicate to immediately know every non-public security flaw in both Firefox and WebKit.

  3) Any solution that doesn't have a mathematical proof that's stood up to the test of time is likely to have hidden flaws that we can't predict.
Comment 72 Daniel Veditz [:dveditz] 2010-12-21 15:30:48 PST
CVE-2010-4568
Comment 73 Max Kanat-Alexander 2010-12-21 16:26:20 PST
I've been working on this, today. I provided a patch to Crypt::Source::Random on CPAN to have it use Any::Moose instead of Moose, so that we can use it. Then I'm going to write and upload a Crypt::Source::Random::Win32. Finally, I'm going to write and upload a Math::Random::ISAAC::Auto module that uses Math::Random::ISAAC but seeds itself properly with Crypt::Source::Random (using and requiring the proper Win32 module on Windows). 

Trunk and 4.0 will use and require Math::Random::ISAAC::Auto.

For the branches, I'm not sure--I may just integrate a bunch of seed-generation code into Bugzilla itself.
Comment 74 Frédéric Buclin 2010-12-21 16:38:45 PST
(In reply to comment #73)
> I've been working on this, today. I provided a patch to Crypt::Source::Random
> on CPAN to have it use Any::Moose instead of Moose, so that we can use it. 

Crypt::Source::Random has many dependencies, including either Moose or Mouse. I see no reason to use this module, especially because it has never been discussed nor suggested above. I had the feeling that there was an agreement to copy the seed code used by Math::Random::MT::Auto, which requires no other dependencies.
Comment 75 Max Kanat-Alexander 2010-12-21 22:15:53 PST
(In reply to comment #74)
> Crypt::Source::Random has many dependencies, including either Moose or Mouse.

  That's fine. Understand that I am updating it with a new version that uses Any::Moose instead of Moose.

> I
> see no reason to use this module, especially because it has never been
> discussed nor suggested above.

  Because it's better to use an existing module than to create our own. Also, it's better to re-use library code than to copy code around. In fact, copying code around is, in general, a really terrible thing to do. Also, using a purpose-built crypto library will give us more reliability. Finally, setting up these modules this way will allow me to pull in the right dependencies on the right platforms, meaning that Win32 users won't have to pull in Unix-specific things, and Unix users won't have to pull in the Win32 modules. Also, I would have had to re-write a lot of the MT::Auto code to be more appropriate for our uses, and I won't have to, this way.

  There are lots of other good reasons to do this, but I sort of figure that the advantage of using libraries and publishing code as individual modules on the CPAN should be self-evident.

  Using libraries is good software design. "This library has a lot of dependencies" is not, by itself, an argument that stands up in any form of software design, particularly given that we have install-module.pl, which does an excellent job of installing all dependencies no matter how many of them there are.
Comment 76 Byron Jones ‹:glob› 2010-12-21 23:49:34 PST
while i'm hesitant to turn this into another moose argument; i have concerns about making moose mandatory, due to the massive performance hit it imposes on mod_cgi clients.

while using any::moose may //seem// better, "there's a VERY strong recommendation from the maintainers of Mouse itself to *not use it*", which leaves us with with no viable option for production mod_cgi environments.
Comment 77 Byron Jones ‹:glob› 2010-12-22 01:04:27 PST
Created attachment 499252 [details] [diff] [review]
generate_random_password

note using RtlGenRandom isn't recommended by microsoft, and has caused problems in firefox before (see bug 501605); CryptGenRandom should be used instead.

here's sample code which calls CryptGenRandom on windows, and uses /dev/urandom or /dev/random on unix.  it's a dependency free pure-perl solution using proven prng's.

right now it's slim on error checking and fallback, but that can be added if we agree to do this instead of pulling in more cpan modules.
Comment 78 Reed Loden [:reed] (use needinfo?) 2010-12-22 01:12:59 PST
Comment on attachment 499252 [details] [diff] [review]
generate_random_password

>+        my $chars = 
>+            [ qw/ a b c d e f g h i j k l m n o p q r s t u v w x y z
>+                  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
>+                  1 2 3 4 5 6 7 8 9                                 / ];

You're missing '0' (zero).
Comment 79 Bradley Baetz (:bbaetz) 2010-12-22 01:15:14 PST
I agree that this is simpler.

Don't eval 'use'; just require.

Doesn't Solaris need to do something fancy with having egd running, or something?

/dev/random blocks, which will be a problem. I'm not sure if having that as a fallback is a good idea.
Comment 80 Max Kanat-Alexander 2010-12-22 12:47:28 PST
(In reply to comment #76)
> i have concerns
> about making moose mandatory,

  We're not making Moose mandatory, or even used.

  http://search.cpan.org/dist/Any-Moose/lib/Any/Moose.pm

> while using any::moose may //seem// better, "there's a VERY strong
> recommendation from the maintainers of Mouse itself to *not use it*",

  I talked to the Moose folks themselves before switching over Crypt::Random::Source to use Any::Moose.
Comment 81 Max Kanat-Alexander 2010-12-22 12:50:15 PST
(In reply to comment #79)
> Doesn't Solaris need to do something fancy with having egd running, or
> something?

  Does Solaris lack /dev/random?

> /dev/random blocks, which will be a problem. I'm not sure if having that as a
> fallback is a good idea.

  On platforms where there is no /dev/urandom, /dev/random usually acts just like urandom.
Comment 82 Max Kanat-Alexander 2010-12-22 12:53:38 PST
glob: re RtlGenRandom, see bug 504270, which was the follow-up bug created after the bug you linked to.
Comment 83 Max Kanat-Alexander 2010-12-22 13:10:12 PST
Comment on attachment 499252 [details] [diff] [review]
generate_random_password

>--- Bugzilla/Util.pm	2010-09-30 00:54:55 +0000
>+{
>+    my($context, $genRandom);

  That won't work on mod_perl. Only "our" variables will persist across calls.

  It would also be interesting to know whether or not doing this is thread-safe (for mod_perl support on Windows).

>+        my $chars = 
>+            [ qw/ a b c d e f g h i j k l m n o p q r s t u v w x y z
>+                  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
>+                  1 2 3 4 5 6 7 8 9                                 / ];

  You know, these can probably be in a constant. Also, the map() solution (or just doing ('A'..'Z')) is a little cleaner to read.

>+        if ($^O =~ /win32/i) {

  Use ON_WINDOWS instead.

>+            eval 'use Win32::API';

  Agreed with an above commenter, you should "require Win32::API" here (and we should throw an error if it is not installed).

>+            $context ||= Win32::API->new("advapi32", "CryptAcquireContextA", "PNNNN", "N")
>+                or die "$^E\n";

  That is $^E?

>+            $genRandom ||= Win32::API->new("advapi32", "CryptGenRandom", "NNP", "N")
>+                or die "$^E\n";

  There are comments on various blogs and bugs that using CryptGenRandom will pull in the entire CryptoAPI. Does this mean that Bugzilla process will use significantly more memory on Windows than they do now? Also, does this take any extra time?

>+            $random = "\0" x $length;
>+            my $h = "\0" x 4;
>+            my $r = $context->Call($h, 0, 0, 1, 0xF0000000);
>+            $h = unpack('L', $h);

  I'm sure you were going to do this anyhow (and I understand that this patch is just a PoC) but if these lines could get some comments explaining them, that would be pretty great.

>+            my $dev;
>+            if (-e "/dev/urandom") {
>+                $dev = "/dev/urandom";
>+            } elsif (-e "/dev/random") {
>+                $dev = "/dev/random";
>+            } else {
>+                # current token code
>+            }

  Ah, the current token code is insecure. I would just suggest dying if we don't have a valid source of entropy.

  One of the nice things about Crypt::Source::Random is that it has a ton of plugins that provide various sorts of random-data sources for various platforms and situations, that people could install if they need to.

>+            open(DEV, $dev) or die $!;
>+            read(DEV, $randomBytes, $length);
>+            close(DEV);

  It would be best to do:

  open(my $dev_fh, '<', $dev) or die $!;

>+        my $token = '';
>+        foreach my $byte (split(//, $randomBytes)) {

  So, you're only reading in eight bits of entropy for each character. At larger bit sizes this isn't as important, but I think you're going to generate non-uniform tokens, dividing 256 by 62.

  I'll also test the performance of this vs. the current solution.

  Finally, I'm not entirely sure of the mathematical characteristics of generating each character out of eight bits of entropy.

  If all of these could be resolved, though, I think this could be a reasonable solution for the branches.
Comment 84 Frédéric Buclin 2010-12-22 13:16:18 PST
(In reply to comment #83)
> >+    my($context, $genRandom);
> 
>   That won't work on mod_perl. Only "our" variables will persist across calls.

Simply store them in Bugzilla->request_cache.


>   If all of these could be resolved, though, I think this could be a reasonable
> solution for the branches.

This looks like a reasonable solution even on trunk, to generate the seed for ISAAC.
Comment 85 Max Kanat-Alexander 2010-12-22 13:32:09 PST
Created attachment 499377 [details]
RNG Speed Test

Here's the script that I'm using to do timing tests. The current results that I get from this are:

   builtin:  1 wallclock secs ( 0.07 usr +  0.00 sys =  0.07 CPU) @ 142857.14/s
builtin_sr:  0 wallclock secs ( 0.09 usr +  0.06 sys =  0.15 CPU) @ 66666.67/s
      glob:  6 wallclock secs ( 0.25 usr +  5.97 sys =  6.22 CPU) @ 1607.72/s
  isaac_pp:  0 wallclock secs ( 0.40 usr +  0.00 sys =  0.40 CPU) @ 25000.00/s
  isaac_xs:  1 wallclock secs ( 0.12 usr +  0.00 sys =  0.12 CPU) @ 83333.33/s
   mt_auto:  0 wallclock secs ( 0.09 usr +  0.00 sys =  0.09 CPU) @ 111111.11/s
mt_auto_sr: 11 wallclock secs ( 4.87 usr +  6.10 sys = 10.97 CPU) @ 911.58/s

  As we can see, reading from /dev/urandom for every generate_random_password call is significantly slower than using a PRNG, provided that we don't have to seed the PRNG on every call.

  However, on most calls we only do generate_random_password once--this means that in the most common case under mod_cgi, glob's solution will actually be faster than using ISAAC, because ISAAC has to seed itself with 256 32-bit integers (1024 bytes) and glob's solution only reads out about 10 bytes per invocation. Since we're doing only one invocation, usually (which will require seeding ISAAC) reading 10 bytes is faster than reading 1024 bytes (although I suspect the general difference will be negligible in practice).

  Also, 1607 calls per second is fast enough--that means that a single generate_random_password call happens in under 1ms on my machine (a Core 2 Duo 2.66Ghz). /dev/urandom may have varying performance characteristics on various platforms, though--I don't know.

  Really what we probably need is secure_random_string() for tokens, site_wide_secret, etc., and fast_random_string() (or just random_string()) for places where were just happen to need randomness (like in the tests) and would rather have something fast than something secure.

  I'd be interested to know what numbers this test does on Windows, also.
Comment 86 Max Kanat-Alexander 2010-12-22 13:33:24 PST
  Note that under mod_perl, using ISAAC will always be faster--srand happens during PerlChildInitHandler (meaning that it happens when Apache spawns a new httpd process) and will never affect any performance that the user can perceive.
Comment 87 Max Kanat-Alexander 2010-12-22 13:40:38 PST
(In reply to comment #84)
> This looks like a reasonable solution even on trunk, to generate the seed for
> ISAAC.

  Ahh, the problem with that is that we become forever responsible for seed-generation on all platforms and under all possible configurations. I'd rather have a CPAN module do seed-generation, and then it can be updated independently for newer configurations or to be more secure.
Comment 88 Max Kanat-Alexander 2010-12-22 13:43:34 PST
And by the way, for anybody who's concerned about Mouse:


time perl -MAny::Moose -e1
real	0m0.028s
user	0m0.023s
sys	0m0.004s

time perl -MCGI -e1
real	0m0.025s
user	0m0.021s
sys	0m0.003s


So if you're concerned about the performance aspects of Mouse, I suppose we'd better stop using CGI.pm too. :-)

Also, using Any::Moose generally alleviates the concerns about using Mouse. I still would only use Any::Moose for smaller systems like Crypt::Random::Source that are unlikely to run into any Mouse bugs or Moose/Mouse incompatibilities. (Those are the real worries with using Any::Moose in larger systems--the strange things that may happen when a Moose module extends a Mouse module, if they have complex relationships, which thankfully Crypt::Source::Random does not.)
Comment 89 Max Kanat-Alexander 2010-12-22 15:26:48 PST
Just to record this information, here are all the Perl platforms that do not have /dev/urandom (as determined by a careful analysis of the Perl source code):

  * Windows
  * OS/2
  * DOS
  * Netware
  * Symbian (and its predecessor, EPOC)

  I'm pretty sure we don't need to support OS/2, DOS, Netware, or Symbian (I doubt anybody's running Bugzilla on their clamshell phone). So we should be covered by using /dev/urandom on all platforms except for Windows, at least currently.
Comment 90 Richard Soderberg [:atoll] 2010-12-22 15:40:00 PST
Comment on attachment 499252 [details] [diff] [review]
generate_random_password

>--- Bugzilla/Util.pm	2010-09-30 00:54:55 +0000
>+++ Bugzilla/Util.pm	2010-12-22 08:53:25 +0000
>+            my $dev;
>+            if (-e "/dev/urandom") {
>+                $dev = "/dev/urandom";
>+            } elsif (-e "/dev/random") {
>+                $dev = "/dev/random";
>+            } else {
>+                # current token code
>+            }

If open and read fails on /dev/urandom but works on /dev/random, will we choose the latter?

Will users be permitted to select an alternate random device such as /dev/egd?
Comment 91 Max Kanat-Alexander 2010-12-22 17:29:21 PST
  Ah, problem: Win32::API doesn't compile on 64-bit Perls.

  https://rt.cpan.org/Public/Bug/Display.html?id=55660
Comment 92 Max Kanat-Alexander 2010-12-22 17:42:29 PST
Created attachment 499438 [details]
Crypt::Random::Source::Win32, Work In Progress

This is a WIP Win32 provider for Crypt::Random::Source. I don't even know if it compiles yet, though, because I'm still working on getting a 32-bit Perl on my machine.

I do know that Crypt::Random::Source itself doesn't pass tests on Windows, but I can provide a patch to fix that.
Comment 93 Max Kanat-Alexander 2010-12-23 00:27:19 PST
Comment on attachment 499438 [details]
Crypt::Random::Source::Win32, Work In Progress

I finished the Win32 crypto provider. When it finishes uploading, it will be at:

  http://search.cpan.org/dist/Crypt-Random-Source-Strong-Win32/

Because I felt like it would be fun, I also made it support CryptGenRandom for Windows 2000. So I suppose we may end up continuing support for Win2K on the branches.

This doesn't solve the "Win32::API doesn't work on 64-bit Perl" problem though.
Comment 94 Bradley Baetz (:bbaetz) 2010-12-23 01:40:23 PST
(In reply to comment #90)
> If open and read fails on /dev/urandom but works on /dev/random, will we choose
> the latter?

I think we shouldn't, because I can't think of any case where that would happen, and more importantly /dev/random blocks. Using /dev/random is thus a dos - you can hit MaxChild just by generating enough tokens.

> Will users be permitted to select an alternate random device such as /dev/egd?

I tihnk we've gone with Crypt::Random, in which case it'll be available, I guess, although I tihnk making this user-selectable is asking for problems. 

I don't suppose Win32::API not working on 64-bit perl also breaks any other module we already depend on?
Comment 95 Frédéric Buclin 2010-12-23 16:45:26 PST
I think this bug depends on bug 599539 on trunk and 4.0 as it already adds Win32::API to the requirement list.
Comment 96 Max Kanat-Alexander 2010-12-27 14:30:17 PST
token.cgi was added on 2001-07-11, which is before 2.14, so I'm assuming Bugzilla has been vulnerable to this since 2.14.
Comment 97 Max Kanat-Alexander 2010-12-27 17:24:23 PST
I've finished the code and POD of Math::Random::Secure. Now I just have to write tests for it, package it up, and ship it to CPAN.
Comment 98 Max Kanat-Alexander 2010-12-28 02:39:29 PST
I have uploaded Math::Random::Secure to CPAN:

  http://search.cpan.org/dist/Math-Random-Secure/

Security-related review (and possibly other review) would be welcome.
Comment 99 Frédéric Buclin 2010-12-28 06:43:51 PST
(In reply to comment #98)
> I have uploaded Math::Random::Secure to CPAN:

We now need it available with ActivePerl, including all its dependencies.
Comment 100 Max Kanat-Alexander 2010-12-28 16:09:55 PST
Created attachment 500123 [details] [diff] [review]
trunk, v1

Here's a patch to use Math::Random::Secure on trunk and 4.0.

Right now Crypt::Random::Source causes a warning during END every time it's used, but I've submitted a patch for that to the maintainer and it should be out in 0.07.

Also, Crypt::Random::Source doesn't pass tests on Windows, but it works fine anyway. It will pass tests as of 0.07 (I wrote the code and it's pending review by the maintainer).

Finally, there's the problem of Win32::API not working with 64-bit Perls. In response, Jan Dubois, the Windows ActivePerl maintainer, has offered to either fix Win32::API or to create a separate Win32:: module to just call the functions that we need. So we'll see how that plays out.
Comment 101 Gervase Markham [:gerv] 2010-12-29 01:14:36 PST
Comment on attachment 500123 [details] [diff] [review]
trunk, v1

> sub generate_random_password {
>     my $size = shift || 10; # default to 10 chars if nothing specified
>-    return join("", map{ ('0'..'9','a'..'z','A'..'Z')[rand 62] } (1..$size));
>+    return join("", map{ ('0'..'9','a'..'z','A'..'Z')[irand 62] } (1..$size));
> }

This seems like a pretty inefficient use of randomness to me. irand creates a 32-bit random integer, and mods it down to the limit. So we are taking 32 bits of randomness and modding them down to 6 bits. In other words, generating a 10-character random password should take 60 bits of randomness, but actually draws 320 from the generator. If this function is called a lot, is there a risk of running out of entropy? One somewhat better implementation would be to call irand for a 32-bit number and then convert 5 lots of six bits to an index each, discarding the value if it's 62 or 63.

> # This loads most of our modules.
> use Bugzilla ();
>@@ -61,7 +62,7 @@
> my $server = Apache2::ServerUtil->server;
> my $conf = <<EOT;
> # Make sure each httpd child receives a different random seed (bug 476622)
>-PerlChildInitHandler "sub { srand(); }"
>+PerlChildInitHandler "sub { Math::Random::Secure::srand(); srand(); }"

Do we now only support Apache? If not, where is srand() called for non-Apache servers?

Gerv
Comment 102 Max Kanat-Alexander 2010-12-29 01:25:31 PST
(In reply to comment #101)
> This seems like a pretty inefficient use of randomness to me.

  It's not--ISAAC is highly efficient, and is optimized to generate 32 bit integers, specifically, using particular CPU instructions that are known to be fast.

> If this function is called a lot, is there a risk
> of running out of entropy? 

  No, cycles in ISAAC are minimally 2^40 values, and average 2^8295 values.

> One somewhat better implementation would be to call
> irand for a 32-bit number and then convert 5 lots of six bits to an index each,
> discarding the value if it's 62 or 63.

  That's an overly complex implementation with no cryptographic advantage.

> Do we now only support Apache?

  No, that's just the mod_perl code.

> If not, where is srand() called for non-Apache servers?

  It doesn't have to be called, irand() and rand() call it automatically. (See the docs of Math::Random::Secure.)
Comment 103 Richard Soderberg [:atoll] 2010-12-29 01:27:52 PST
(In reply to comment #101)
> Comment on attachment 500123 [details] [diff] [review]
> trunk and 4.0, v1
> > # Make sure each httpd child receives a different random seed (bug 476622)

this comment should be updated to clarify why we're calling srand twice, to prevent well-intended corrections later
Comment 104 Gervase Markham [:gerv] 2010-12-29 01:29:59 PST
OK, fair enough :-)

Gerv
Comment 105 Max Kanat-Alexander 2010-12-29 01:42:40 PST
(In reply to comment #103)
> this comment should be updated to clarify why we're calling srand twice, to
> prevent well-intended corrections later

  Agreed.
Comment 106 Max Kanat-Alexander 2010-12-29 02:01:35 PST
Created attachment 500172 [details]
Calling Windows Perl's srand more than once is bad

Here's a short Perl script that proves the problem on Windows. It shows that, given a million attempts to generate a seed, only a very small number of different seeds are generated.

This script actually shows an even worse problem than Windows has, because the data that srand() is using on Windows won't change very much during the script. A better demonstration could possibly be done by putting "sleep 0.01" into the for loop, but brief experiments with that show that it does not improve the randomness at all.
Comment 107 Max Kanat-Alexander 2010-12-29 02:13:59 PST
Created attachment 500174 [details]
Better Windows Demonstration Script

This script starts a whole new Perl process for each sequence generated. This is just like what would actually be happening in a CGI environment. This is MUCH slower, though, so I haven't been able to run it to completion. Running it in short numbers so far indicates that the Windows Perl RNG may actually not be as weak as we thought, but I'll have to do more testing to be sure.

Anybody with a very fast Windows machine is welcome to test this with a million loops and see how it does.
Comment 108 Max Kanat-Alexander 2010-12-29 02:38:30 PST
Comment on attachment 500172 [details]
Calling Windows Perl's srand more than once is bad

Okay, this script actually just demonstrates that calling srand() more than once in the same process on Windows is not a good solution, and in fact is VERY bad--far far worse than it is on *nix.

A real script to demonstrate the "Windows problem" is forthcoming.
Comment 109 Max Kanat-Alexander 2010-12-29 02:45:26 PST
Created attachment 500176 [details]
The Real Windows Problem

Here's the real Windows problem. On Windows Perl (Strawberry or ActiveState both, I believe--I tested Strawberry), this script will generate the same output every single time it is run. Perl's rand() on Windows is only capable of generating 2^15 values, period. They do come in different orders every time, based on the seed, though.
Comment 110 Gervase Markham [:gerv] 2010-12-29 02:50:14 PST
That is really quite serious. However, Googling suggests it's not a new discovery:
http://www.perlmonks.org/?node_id=803632

However, have people realised the security implications? I suspect there are quite a lot of web apps out there which use Perl's rand() to generate random session cookies or stuff like that...

Gerv
Comment 111 Frédéric Buclin 2010-12-29 03:18:55 PST
As calling srand() several times is bad, couldn't we do the following on branches (as we don't plan to require new dependencies) to mitigate the problem:

1) append the login name to the URL to change the new password, to avoid brute force. So, instead of (sample stolen from comment 0):

---- copy paste from the victims email ---
You have (or someone impersonating you has) requested to change your
Bugzilla password. To complete the change, visit the following link:

https://bugzilla.mozilla.org/token.cgi?t=YKWG0y4oQT&a=cfmpw
-----

you would now have:

---- copy paste from the victims email ---
You have (or someone impersonating you has) requested to change your
Bugzilla password. To complete the change, visit the following link:

https://bugzilla.mozilla.org/token.cgi?l=foo@bar.com&t=YKWG0y4oQT&a=cfmpw
-----

This way, you cannot just try all tokens randomly. You would have to know which email address you want to attack. Else, even when calling srand() every time generate_random_password() is called, you would still have a limited set of tokens to try, and one will probably succeed (though maybe not with the expected credentials, if you managed to crack a powerless user account).

2) If we append the login name to the URL, then we can use the same lock system as we use for login attemps, i.e. reject any new request after 5 attempts. So if an attacker tries 5 incorrect tokens against some given user account, then we don't validate new tokens for this user account from this IP address anymore for the next 30 minutes.

Note that my two proposals above aren't a replacement for srand() being called every time generate_random_password() is called, because without these calls to srand(), an attacker could still use the attack described in comment 0. But without my proposals, and with no other alternative than calling srand(), you still get a limited set of tokens which you can try randomly, and hope one will work.
Comment 112 Bradley Baetz (:bbaetz) 2010-12-29 03:40:56 PST
(In reply to comment #99)
> We now need it available with ActivePerl, including all its dependencies.

and Fedora, Debian, Ubuntu, etc.

I think that for non-trunk we really need to use the patch from comment 77, at least for non-windows.
Comment 113 Frédéric Buclin 2010-12-29 03:43:45 PST
(In reply to comment #112)
> (In reply to comment #99)
> > We now need it available with ActivePerl, including all its dependencies.
> 
> and Fedora, Debian, Ubuntu, etc.

This is less of a problem for Linux distros, because you can call ./install-module.pl, and it will get missing modules from CPAN. Also, once these distros package Bugzilla 4.0, they will be forced to include these modules anyway. But ActiveState doesn't package Bugzilla, AFAIK. ;)
Comment 114 Bradley Baetz (:bbaetz) 2010-12-29 04:55:32 PST
That's fine for people who roll their own, but not for distributions. A new package has to be created, approved, built, etc. Yes, its needed for 4.0, but that's a (planned) upgrade not a critical security fix.

Or is the plan for 3.6 to just do the srand thing for non-windows?
Comment 115 Frédéric Buclin 2010-12-29 06:40:44 PST
(In reply to comment #111)
> This way, you cannot just try all tokens randomly. You would have to know which
> email address you want to attack.

I take that back. We don't display anywhere in the page which user account we are talking about. So even if the token is valid, the attacker won't know which user account to abuse.
Comment 116 Frédéric Buclin 2010-12-29 09:38:46 PST
Created attachment 500216 [details]
compare CORE::rand() and Math::Random::Secure::rand()

Something bothers me with Math::Random::Secure. My script shows than calling rand() 10 million times gives some duplicated numbers when using Math::Random::Secure::rand(), while they are all distinct when using CORE::rand():

# ./rand.pl
Results for core_rand:
1: 10000000
10000000 distinct seeds

Results for math_random_secure_rand:
1: 9976495
2: 11724
3: 19
9988238 distinct seeds

"3: 19" means that 19 numbers appeared 3 times.
Comment 117 Gervase Markham [:gerv] 2010-12-29 09:48:55 PST
A stream where no number reoccurs is not random. There are 4 294 967 296 possible results (2^32). You are generating 1/429th of the space - I'm not at all surprised that there are some repeats. In fact, I'd expect it.

Gerv
Comment 118 Max Kanat-Alexander 2010-12-29 14:43:37 PST
(In reply to comment #110)
> That is really quite serious. However, Googling suggests it's not a new
> discovery:
> http://www.perlmonks.org/?node_id=803632

  Yes. However, for our case, 16 bits of randomness *per character* is enough for us, at least on the branches, as long as each generated token has a different seed (so that you can't work back to the seed from any generated token). The seeds are still 32 bits on Windows--I was afraid that they were only 16 bits.

  If anybody doesn't understand how or why this is okay, ask me on IRC.
Comment 119 Frédéric Buclin 2010-12-29 14:44:59 PST
(In reply to comment #117)
> A stream where no number reoccurs is not random. There are 4 294 967 296
> possible results (2^32). You are generating 1/429th of the space - I'm not at
> all surprised that there are some repeats. In fact, I'd expect it.

Yes, you are right. Some maths tells me that the probability to get at least twice the same number in my sample is... 100%. :) The probability is already 70% with 100,000 iterations.
Comment 120 Max Kanat-Alexander 2010-12-29 14:55:35 PST
(In reply to comment #111)
> Else, even when calling srand() every time
> generate_random_password() is called, you would still have a limited set of
> tokens to try, and one will probably succeed (though maybe not with the
> expected credentials, if you managed to crack a powerless user account).

  I suspect that the time required to do 2^32 web requests against a remote server is a rather significant amount of time. 

  I actually went and tested this using "ab", the Apache web performance tool (it's short for ApacheBench). I used this command line:

  ab -n 1000 -c 10 'http://localhost/bugzilla-tip/token.cgi?t=abcdefg&a=cfmpw'

  It took about 60 seconds to do 1000 requests with 10 concurrent requests, and that's without any network latency, on a mod_perl host. That gives us an average of 0.06 seconds per request. This means that trying 2^32 tokens would take 257698038 seconds, which is 71582 hours, which is 2982 days, which is about eight years.

  Since password reset tokens are only valid for three days, and any admin would notice that level of activity, I think we're safe.

  As such, we are not in danger from brute force attacks against tokens, even from somebody who is on the local host.
Comment 121 Max Kanat-Alexander 2010-12-29 14:59:40 PST
(In reply to comment #120)
> That gives us an average of 0.06 seconds per request. 

  Oh actually, there was an error in my testing. It turns out that 0.06 seconds is just the time it takes to return a "301 Moved Permanently" when calling an "ssl: always" installation over http://.

  With a real token.cgi call, I could do about 4.5 requests per second, which is considerably slower, making a brute-force attack even less likely.
Comment 122 Max Kanat-Alexander 2010-12-29 15:00:47 PST
I have a planned patch for the branches that I think will work just fine, and even a likely-decent solution for Windows on the branches.
Comment 123 Frédéric Buclin 2010-12-29 16:01:37 PST
Comment on attachment 500123 [details] [diff] [review]
trunk, v1

When trying to log in, Bugzilla crashes with:

Software error:

Attribute (weak_source) does not pass the type constraint because: Validation failed for 'ClassName' failed with value undef at lib/Crypt/Random/Source/Factory.pm line 76
	Crypt::Random::Source::Factory::_build_any_source('Crypt::Random::Source::Factory=HASH(0xa0d2cf8)') called at /usr/lib/perl5/vendor_perl/5.10.1/i386-linux-thread-multi/Mouse/Meta/Method/Delegation.pm line 36
	Crypt::Random::Source::Factory::new_any('Crypt::Random::Source::Factory=HASH(0xa0d2cf8)') called at lib/Crypt/Random/Source/Factory.pm line 27
	Crypt::Random::Source::Factory::get('Crypt::Random::Source::Factory=HASH(0xa0d2cf8)') called at lib/Math/Random/Secure/RNG.pm line 22
	Math::Random::Secure::RNG::_build_seeder('Math::Random::Secure::RNG=HASH(0xa0d2b88)') called at lib/Math/Random/Secure/RNG.pm line 33
	Math::Random::Secure::RNG::_build_seed('Math::Random::Secure::RNG=HASH(0xa0d2b88)') called at lib/Math/Random/Secure.pm line 45
	eval {...} called at lib/Math/Random/Secure.pm line 45
	Math::Random::Secure::srand() called at lib/Math/Random/Secure.pm line 51
	Math::Random::Secure::_srand_if_necessary() called at lib/Math/Random/Secure.pm line 26
	Math::Random::Secure::irand(62) called at Bugzilla/Util.pm line 541
	Bugzilla::Util::generate_random_password() called at Bugzilla/Token.pm line 255
	Bugzilla::Token::GenerateUniqueToken('logincookies', 'cookie') called at Bugzilla/Auth/Persist/Cookie.pm line 63
	Bugzilla::Auth::Persist::Cookie::persist_login('Bugzilla::Auth::Persist::Cookie=HASH(0x9fd1580)', 'Bugzilla::User=HASH(0xa0883d0)') called at Bugzilla/Auth.pm line 155
	Bugzilla::Auth::_handle_login_result('Bugzilla::Auth=HASH(0x9fc2c20)', 'HASH(0x97e1d70)', 2) called at Bugzilla/Auth.pm line 95
	Bugzilla::Auth::login('Bugzilla::Auth=HASH(0x9fc2c20)', 2) called at Bugzilla.pm line 336
	Bugzilla::login('Bugzilla', 0) called at /var/www/html/bugzilla/index.cgi line 40
 at lib/Crypt/Random/Source/Factory.pm line 76
	Crypt::Random::Source::Factory::_build_any_source('Crypt::Random::Source::Factory=HASH(0xa0d2cf8)') called at /usr/lib/perl5/vendor_perl/5.10.1/i386-linux-thread-multi/Mouse/Meta/Method/Delegation.pm line 36
	Crypt::Random::Source::Factory::new_any('Crypt::Random::Source::Factory=HASH(0xa0d2cf8)') called at lib/Crypt/Random/Source/Factory.pm line 27
	Crypt::Random::Source::Factory::get('Crypt::Random::Source::Factory=HASH(0xa0d2cf8)') called at lib/Math/Random/Secure/RNG.pm line 22
	Math::Random::Secure::RNG::_build_seeder('Math::Random::Secure::RNG=HASH(0xa0d2b88)') called at lib/Math/Random/Secure/RNG.pm line 33
	Math::Random::Secure::RNG::_build_seed('Math::Random::Secure::RNG=HASH(0xa0d2b88)') called at lib/Math/Random/Secure.pm line 45
	eval {...} called at lib/Math/Random/Secure.pm line 45
	Math::Random::Secure::srand() called at lib/Math/Random/Secure.pm line 51
	Math::Random::Secure::_srand_if_necessary() called at lib/Math/Random/Secure.pm line 26
	Math::Random::Secure::irand(62) called at Bugzilla/Util.pm line 541
	Bugzilla::Util::generate_random_password() called at Bugzilla/Token.pm line 255
	Bugzilla::Token::GenerateUniqueToken('logincookies', 'cookie') called at Bugzilla/Auth/Persist/Cookie.pm line 63
	Bugzilla::Auth::Persist::Cookie::persist_login('Bugzilla::Auth::Persist::Cookie=HASH(0x9fd1580)', 'Bugzilla::User=HASH(0xa0883d0)') called at Bugzilla/Auth.pm line 155
	Bugzilla::Auth::_handle_login_result('Bugzilla::Auth=HASH(0x9fc2c20)', 'HASH(0x97e1d70)', 2) called at Bugzilla/Auth.pm line 95
	Bugzilla::Auth::login('Bugzilla::Auth=HASH(0x9fc2c20)', 2) called at Bugzilla.pm line 336
	Bugzilla::login('Bugzilla', 0) called at /var/www/html/bugzilla/index.cgi line 40
 at lib/Math/Random/Secure.pm line 45
	Math::Random::Secure::srand() called at lib/Math/Random/Secure.pm line 51
	Math::Random::Secure::_srand_if_necessary() called at lib/Math/Random/Secure.pm line 26
	Math::Random::Secure::irand(62) called at Bugzilla/Util.pm line 541
	Bugzilla::Util::generate_random_password() called at Bugzilla/Token.pm line 255
	Bugzilla::Token::GenerateUniqueToken('logincookies', 'cookie') called at Bugzilla/Auth/Persist/Cookie.pm line 63
	Bugzilla::Auth::Persist::Cookie::persist_login('Bugzilla::Auth::Persist::Cookie=HASH(0x9fd1580)', 'Bugzilla::User=HASH(0xa0883d0)') called at Bugzilla/Auth.pm line 155
	Bugzilla::Auth::_handle_login_result('Bugzilla::Auth=HASH(0x9fc2c20)', 'HASH(0x97e1d70)', 2) called at Bugzilla/Auth.pm line 95
	Bugzilla::Auth::login('Bugzilla::Auth=HASH(0x9fc2c20)', 2) called at Bugzilla.pm line 336
	Bugzilla::login('Bugzilla', 0) called at /var/www/html/bugzilla/index.cgi line 40
Comment 124 Max Kanat-Alexander 2010-12-29 16:06:53 PST
Created attachment 500276 [details] [diff] [review]
Patch for 3.2, v1

This is a patch for 3.2.

If Math::Random::Secure is installed, we use it.

If Math::Random::Secure is not installed:

  * On non-Windows platforms, we just do "srand", like the "Simplest Patch"
    above.
  * On Windows, we have our own routine to generate a random-enough seed for
    srand. It's not cryptographically ideal (because both Time::HiRes::time
    and refaddr({}) are not perfectly random--they always increase) but it
    does generate a unique seed every time, even when called in a very 
    tight loop, and that's all we need.

I'll also attach a test script that anyone can use on their platform to make sure that any generate_random_password implementation does in fact produce unique tokens every time (or almost every time).
Comment 125 Max Kanat-Alexander 2010-12-29 16:09:06 PST
Created attachment 500278 [details]
Test generate_random_password

Here's a script to test generate_random_password.
Comment 126 Max Kanat-Alexander 2010-12-29 16:25:24 PST
(In reply to comment #124)
> Created attachment 500276 [details] [diff] [review]
> Patch for 3.2, v1

  And I just ran the tests on Windows and I can confirm that this patch works fine there.
Comment 127 Max Kanat-Alexander 2010-12-29 16:31:58 PST
Created attachment 500280 [details] [diff] [review]
Patch for 3.4, v1

Identical approach to 3.2, just requires a different patch for Util.pm because of conflicts.
Comment 128 Max Kanat-Alexander 2010-12-29 16:39:34 PST
Created attachment 500281 [details] [diff] [review]
Patch for 3.6, v1

This is the same as the other branch patches, in spirit, but it uses Bugzilla->feature, since that's available on 3.6, and adds a string to strings.txt.pl, for the feature.
Comment 129 Frédéric Buclin 2010-12-29 17:18:59 PST
Reduced testcase for comment 123:

perl -I "lib" -MMath::Random::Secure -T -we 'Math::Random::Secure::srand'

Attribute (weak_source) does not pass the type constraint because: Validation failed for 'ClassName' failed with value undef at lib/Crypt/Random/Source/Factory.pm line 76
        Crypt::Random::Source::Factory::_build_any_source('Crypt::Random::Source::Factory=HASH(0x8e17770)') called at /usr/lib/perl5/vendor_perl/5.10.1/i386-linux-thread-multi/Mouse/Meta/Method/Delegation.pm line 36
        Crypt::Random::Source::Factory::new_any('Crypt::Random::Source::Factory=HASH(0x8e17770)') called at lib/Crypt/Random/Source/Factory.pm line 27
        Crypt::Random::Source::Factory::get('Crypt::Random::Source::Factory=HASH(0x8e17770)') called at lib/Math/Random/Secure/RNG.pm line 22
        Math::Random::Secure::RNG::_build_seeder('Math::Random::Secure::RNG=HASH(0x8b637b8)') called at lib/Math/Random/Secure/RNG.pm line 33
        Math::Random::Secure::RNG::_build_seed('Math::Random::Secure::RNG=HASH(0x8b637b8)') called at lib/Math/Random/Secure.pm line 45
        eval {...} called at lib/Math/Random/Secure.pm line 45
        Math::Random::Secure::srand() called at -e line 1

If you remove -T, then it works correctly.

<mkanat> LpSolit: Ahh, I bet Crypt::Random::Source is not taint-safe.
Comment 130 Max Kanat-Alexander 2010-12-29 17:26:16 PST
(In reply to comment #129)
> <mkanat> LpSolit: Ahh, I bet Crypt::Random::Source is not taint-safe.

  I've submitted a fix for Crypt::Random::Source to its maintainer. It should be out in Crypt::Random::Source 0.07.
Comment 131 Frédéric Buclin 2011-01-02 05:31:53 PST
Comment on attachment 500276 [details] [diff] [review]
Patch for 3.2, v1

>=== modified file 'Bugzilla/Util.pm'

>+sub _do_srand {
>+    # On Windows, calling srand over and over in the same process produces
>+    # very bad results. We have to create our own seed by a somewhat-random
>+    # process. This is not perfect, cryptographically, but it should be
>+    # random-enough to generate a reasonable seed in a 32-bit space.
>+    if (ON_WINDOWS) {

IMO, if Math::Random::Secure is not installed, we should fall back to calling the Crypto API ourselves using Win32::API if we are using Perl 32-bits. We should only fall back to this custom seed generator on Windows 64-bits (as we have no guarantee it's crypto-safe).
Comment 132 Max Kanat-Alexander 2011-01-02 22:42:12 PST
(In reply to comment #131)
> IMO, if Math::Random::Secure is not installed, we should fall back to calling
> the Crypto API ourselves using Win32::API if we are using Perl 32-bits. We
> should only fall back to this custom seed generator on Windows 64-bits (as we
> have no guarantee it's crypto-safe).

  Well, I thought about that, yeah, but the only barrier to installing Math::Random::Secure is whether or not you can install Win32::API. If you can install Win32::API, you can install Math::Random::Secure. So I don't really want to duplicate code between Bugzilla and Math::Random::Secure. I'll see if I can work with ActiveState to get Math::Random::Secure packaged, too, once it's available.

  FWIW, the _do_srand() code is not *cryptographically* secure, in a mathematically-provable way. But as long as it generates separate seeds for every call to generate_random_password, it shouldn't matter, because reverse-engineering the seed from one generate_random_password call won't allow you to figure out the seed used in other generate_random_password calls. That is, we only have to worry about the cryptographic security of our algorithms if we use the same seed for different generate_random_password calls, which I'm pretty sure is impossible (or nearly impossible) with the _do_srand() code as it is now.
Comment 133 Max Kanat-Alexander 2011-01-02 23:16:52 PST
Also, just to elaborate a bit more--we *know* the RNG shipped with Perl is not cryptographically secure. srand() is only getting 32 bits no matter what, and the rand() algorithm used is not that awesome. That's why we're calling srand every time, when Math::Random::Secure isn't installed--so that it doesn't matter how secure rand() is, because cracking the seed used for one token doesn't get youanything.

As long as we reliably generate separate seeds with each _do_srand() call, that's all we care about, and as far as I can see in my testing, we do. It could use some testing on a faster Windows machine than mine, though.
Comment 134 Frédéric Buclin 2011-01-03 05:42:24 PST
(In reply to comment #132)
>   Well, I thought about that, yeah, but the only barrier to installing
> Math::Random::Secure is whether or not you can install Win32::API. If you can
> install Win32::API, you can install Math::Random::Secure.

But the difference is that not everybody has or will have Math::Random::Secure installed, while Win32::API is installed by default, at least with ActivePerl (in fact, you cannot even uninstall it).
Comment 135 Frédéric Buclin 2011-01-06 04:51:20 PST
Comment on attachment 500123 [details] [diff] [review]
trunk, v1

This patch doesn't apply cleanly on the 4.0 branch due to bug 599552 which landed on trunk only. You will have to attach a separate patch for 4.0. Also, you have to require Math::Random::Secure 0.04 at minimum due to the taint issue in older versions of Crypt::Random::Source.

I tested your patch in 4.1 on Linux, and it's working fine. Let's see if I can test it on Windows. Byron, help wanted for Windows (ActivePerl + Strawberry Perl). :)
Comment 136 Frédéric Buclin 2011-01-07 17:48:19 PST
Comment on attachment 500123 [details] [diff] [review]
trunk, v1

Tested on Linux and Windows 7 (using Strawberry Perl 5.12.1) + Math::Random::Secure 0.05. r=LpSolit

Byron, do you have Windows XP in hands?
Comment 137 Byron Jones ‹:glob› 2011-01-08 04:23:02 PST
(In reply to comment #136)
> Byron, do you have Windows XP in hands?

sorry, not until monday (i'm still on my christmas leave, and only have win7/64 at home).
Comment 138 Max Kanat-Alexander 2011-01-10 14:55:41 PST
Created attachment 502620 [details] [diff] [review]
Patch For 4.0, v1

I went with a 3.6-like method for 4.0. I don't want to *require* Math::Random::Secure just yet for 4.0. We have no idea if or when Win32::API will work on 64-bit Windows Perl, which means we have no idea when those users will be able to install Math::Random::Secure. Also, I want to give packagers more time to be able to package M::R::S so that people can have packages available for it when they install 4.0.
Comment 139 Frédéric Buclin 2011-01-10 17:20:02 PST
Comment on attachment 500281 [details] [diff] [review]
Patch for 3.6, v1

Tested on Linux and Windows 7, both with and without Math::Random::Secure, and seems to work fine. r=LpSolit
Comment 140 Max Kanat-Alexander 2011-01-14 04:56:59 PST
Okay, there is a problem with the branch version of this patch:

* There are still only 2^32 possible site_wide_secret values if you're using _do_srand.
* When generating hash tokens, the only secret component is the site_wide_secret.

So, site_wide_secret can be cracked in the same way as a token can be cracked in comment 0, using _do_srand. I have an idea for a patch that should make this better.
Comment 141 Max Kanat-Alexander 2011-01-14 06:07:41 PST
Created attachment 503819 [details] [diff] [review]
Patch for 4.0, v2

This changes generate_random_password to re-generate a new seed every 8 characters if we are using _do_srand. Mathematically, this adds 32 to the total key size every time we grab a new key. (I'm sure there are limiting mathematical factors, though.) So if we call _do_srand twice in one generate_random_password call, we effectively have a 64-bit key. Calling it three times, we have a 96-bit key, etc.

I set it to regenerate every five characters. This makes the seed bit size and the string bit strength roughly equal. Here's a clearer explanation of what I mean:

With a 5-character string, we'd have roughly the equivalent of a 30-bit key. 10 characters gets us 60 bits, 15 would be 90, etc. So for a 5-character string we have a 32-bit seed and 30 bits of actual randomness in the string itself. For a 10-character string we have a 64-bit seed and 60 bits of randomness in the string itself, and so on.

I'm sure that in reality, the solution is slightly weaker than that due to various factors. All I *really* care about, though, is that this will give us roughly a 384-bit key strength for our site_wide_secret now.

The patch also forces a regeneration of the site_wide_secret.

Now that I understand more about key sizes, I see that a 256-character key was unnecessary, and 64 characters is plenty.

I also added a comment to generate_random_password explaining how to calculate the strength of strings it generates.

Some of these pieces I will have to forward-port to trunk.
Comment 142 Max Kanat-Alexander 2011-01-14 06:10:42 PST
(In reply to comment #141)
> This changes generate_random_password to re-generate a new seed every 8
> characters

  That should say "every 5 characters".
Comment 143 Max Kanat-Alexander 2011-01-14 06:18:43 PST
Created attachment 503820 [details] [diff] [review]
Patch for trunk, v2

This makes checksetup forcibly generate a new site_wide_secret if we're using an old-style site_wide_secret, and also adds the comment to Bugzilla::Util about calculating key strength.
Comment 144 Max Kanat-Alexander 2011-01-14 06:31:56 PST
Created attachment 503824 [details] [diff] [review]
Patch for 3.6, v2

Updated 3.6 patch, same updates as the 4.0 patch.
Comment 145 Max Kanat-Alexander 2011-01-14 06:33:12 PST
Created attachment 503826 [details] [diff] [review]
Patch for 3.6, v2 (Actual)

Attached the wrong patch the first time.
Comment 146 Max Kanat-Alexander 2011-01-14 06:36:32 PST
Created attachment 503828 [details] [diff] [review]
Patch for 3.4, v2

Same updates.
Comment 147 Max Kanat-Alexander 2011-01-14 06:38:26 PST
Comment on attachment 503826 [details] [diff] [review]
Patch for 3.6, v2 (Actual)

Oh wait, this is missing the localconfig-update code.
Comment 148 Max Kanat-Alexander 2011-01-14 06:38:44 PST
Comment on attachment 503828 [details] [diff] [review]
Patch for 3.4, v2

And so is this one.
Comment 149 Max Kanat-Alexander 2011-01-14 06:43:46 PST
Created attachment 503831 [details] [diff] [review]
Patch for 3.6, v3

Now this properly updates localconfig with the new site_wide_secret.
Comment 150 Max Kanat-Alexander 2011-01-14 06:49:04 PST
Created attachment 503833 [details] [diff] [review]
Patch for 3.4, v3
Comment 151 Max Kanat-Alexander 2011-01-14 07:07:22 PST
Created attachment 503836 [details] [diff] [review]
Patch for 3.2, v2

This has some extra Localconfig-related code compared to the other patches. Bugzilla 3.2 didn't re-write localconfig when it added new variables, so without this extra code, I was ending up with "$site_wide_secret" twice in "localconfig". Technically that was okay--it didn't affect the system's functionality. But since this has to do with security, I didn't want to leave the old one lying around and risk the chance that users might edit the file in some way that makes them continue to use the old one.

This does result in there being an extra comment in localconfig, but really, this is a very old branch at this point, and all I really think we need to do is to make it work.
Comment 152 Frédéric Buclin 2011-01-14 07:19:21 PST
Also, please fix the minimum version of Math::Random::Secure required. We want 0.04 as a minimum.
Comment 153 Max Kanat-Alexander 2011-01-14 07:30:37 PST
(In reply to comment #152)
> Also, please fix the minimum version of Math::Random::Secure required. We want
> 0.04 as a minimum.

  Oh, right, arrrgh. Since this is holding up one of our most important releases ever and is one of the most critical security issues we've ever had, do you think that you could review the patches as they are and then I can just carry forward r+ on to some patches that have the updated Requirements? (Since it only requires editing the patch.)
Comment 154 Frédéric Buclin 2011-01-15 14:59:25 PST
Comment on attachment 503820 [details] [diff] [review]
Patch for trunk, v2

>=== modified file 'Bugzilla/Install/Requirements.pm'

>+        package => 'Math-Random-Secure',
>+        module  => 'Math::Random::Secure',
>+        version => 0,

0 => 0.04. r=LpSolit with this fix.
Comment 155 Reed Loden [:reed] (use needinfo?) 2011-01-15 15:02:43 PST
(In reply to comment #154)
> Comment on attachment 503820 [details] [diff] [review]
> Patch for trunk, v2
> 
> >=== modified file 'Bugzilla/Install/Requirements.pm'
> 
> >+        package => 'Math-Random-Secure',
> >+        module  => 'Math::Random::Secure',
> >+        version => 0,
> 
> 0 => 0.04. r=LpSolit with this fix.

Why then is the 4.0 patch requiring 0.05?

From the 4.0 patch:
+        # This is the first version that installs properly on Windows.
+        version => '0.05',
Comment 156 Frédéric Buclin 2011-01-15 15:08:10 PST
(In reply to comment #155)
> Why then is the 4.0 patch requiring 0.05?

Because I remembered that 0.05 fixed a bug on Windows *after* I clicked "Submit", and I wrote an updated comment for s/0.04/0.05/, got distracted, and forgot to submit it. But yes, it should be "0.05". :)
Comment 157 Frédéric Buclin 2011-01-15 15:17:13 PST
Also, note that Math::Random::ISAAC 1.002 and older do not pass tests on Windows with Perl 5.12, see https://rt.cpan.org/Public/Bug/Display.html?id=64536. This means ActivePerl 5.12.2 doesn't provide this package via ppm. This problem has been fixed in Math::Random::ISAAC 1.003, which has been uploaded to CPAN today. Maybe should Math::Random::Secure require this version as a minimum, to be sure to work with Perl 5.12 on Windows. This would mean a new version of Math::Random::Secure (0.06?). :(
Comment 158 Frédéric Buclin 2011-01-15 20:26:39 PST
Comment on attachment 503819 [details] [diff] [review]
Patch for 4.0, v2

>=== modified file 'Bugzilla/Util.pm'

>+sub _do_srand {
>+    # On Windows, calling srand over and over in the same process produces
>+    # very bad results. We have to create our own seed by a somewhat-random
>+    # process. This is not perfect, cryptographically, but it should be
>+    # random-enough to generate a reasonable seed for our uses.
>+    if (ON_WINDOWS) {
>+        # We start with the process id.
>+        # Then we add the current hi-res timestamp.
>+        # And finally we throw in the address of a just-created hashref, which
>+        # is fairly random (depends a lot upon timing).
>+        my @seed_data = ($$, Time::HiRes::time(), refaddr({}));
>+        # Then we hash all of these together.
>+        my $seed = join('*', @seed_data);
>+        $seed = md5($seed);
>+        # And take the first four bytes of the md5 as a 32-bit integer.
>+        $seed = unpack('L', $seed);
>+        srand($seed);
>+        return;
>+    }

OK, I definitely don't trust too much what is done here. My opinion for Bugzilla 4.0 is that we should require Math::Random::Secure on *nix. Linux packagers will add the missing dependencies when packaging Bugzilla 4.0. Once 4.0rc2 is out, we can notify them so that they have time before 4.0 final is out. Also, sysadmins who only want to depend on packages provided by their distro won't install Bugzilla 4.0 themselves, and if they do, then this means that they are fine to also install Math:Random::Secure themselves. Again, not a reason to not make it mandatory. For Bugzilla 3.6.4 and older, I agree to make it optional.

About Windows, and due to the fact that Win32::API doesn't work on Windows 64-bit, we unfortunately cannot make Math::Random::Secure mandatory (though it's now available on Windows 32-bit, see my previous comment). *But* there is IMO a better alternative than your hack (which gives us no guarantee of being cryptographically strong). On

 [1] http://msdn.microsoft.com/en-us/library/ff358862%28v=PROT.10%29.aspx
 [2] http://msdn.microsoft.com/en-us/library/d12e9f49-9aeb-40f8-95e7-5901e73836fb%28v=PROT.10%29#id16
 [3] http://tools.ietf.org/html/rfc4122#section-4.4

you can read (from note #16 in [2]):
"For reasons of increased privacy protection for our customers, Microsoft systems, beginning with Windows 2000, prefer to generate version 4 GUIDs in which the 122 bits of nonformat information are random. Although only a small minority of version 4 GUIDs require cryptographic randomness, the random bits for all version 4 GUIDs built in Windows are obtained via the Windows CryptGenRandom cryptographic API or the equivalent, which is the same source that is used for the generation of cryptographic keys. This source is FIPS 140-certified in various versions of Windows"

The version 4 GUIDs mentions in this document is described in RFC 4122 [3], see section 4.4. As these randomly-generated GUIDs are available thanks to Win32::GuidGen(), which calls CoCreateGuid(), we can simply use them when generate_random_password() is called.
Comment 159 Reed Loden [:reed] (use needinfo?) 2011-01-15 20:47:48 PST
(In reply to comment #158)
> OK, I definitely don't trust too much what is done here. My opinion for
> Bugzilla 4.0 is that we should require Math::Random::Secure on *nix. Linux
> packagers will add the missing dependencies when packaging Bugzilla 4.0. Once
> 4.0rc2 is out, we can notify them so that they have time before 4.0 final is
> out. Also, sysadmins who only want to depend on packages provided by their
> distro won't install Bugzilla 4.0 themselves, and if they do, then this means
> that they are fine to also install Math:Random::Secure themselves. Again, not a
> reason to not make it mandatory. For Bugzilla 3.6.4 and older, I agree to make
> it optional.

I agree. We shouldn't be making MRS optional for 4.0. For the branches, that's fine, but *nix packagers are already going to have to do work to get 4.0 packaged, so they can deal with adding a new package for MRS if needed.

> About Windows, and due to the fact that Win32::API doesn't work on Windows
> 64-bit, we unfortunately cannot make Math::Random::Secure mandatory (though
> it's now available on Windows 32-bit, see my previous comment). *But* there is
> IMO a better alternative than your hack (which gives us no guarantee of being
> cryptographically strong).
....
> As these randomly-generated GUIDs are available thanks to
> Win32::GuidGen(), which calls CoCreateGuid(), we can simply use them when
> generate_random_password() is called.

Note that Win32::GuidGen() still doesn't help the Win64 case, as it uses Win32::API to call CoCreateGuid(). However, it is probably a better alternative to MRS if MRS is not available on a Win32 machine (in the case of the branches).
Comment 160 Frédéric Buclin 2011-01-15 20:50:09 PST
(In reply to comment #158)
> section 4.4. As these randomly-generated GUIDs are available thanks to
> Win32::GuidGen(), which calls CoCreateGuid(), we can simply use them when
> generate_random_password() is called.

Some more info:

Win32::GuidGen returns GUIDs of the form:
{AE74EF6C-0854-4DC9-8635-C3B6CD65B68E}
{              4    y                }

Only the 2 characters I marked above (4 and y) aren't random. All others are usable.
Comment 161 Frédéric Buclin 2011-01-15 20:52:28 PST
(In reply to comment #159)
> Note that Win32::GuidGen() still doesn't help the Win64 case, as it uses
> Win32::API to call CoCreateGuid().

Win32 doesn't depend on Win32::API.
Comment 162 Frédéric Buclin 2011-01-16 03:03:24 PST
(In reply to comment #161)
> Win32 doesn't depend on Win32::API.

... which also means that Crypt::Random::Source::Strong::Win32 could fallback to Win32::GuidGen to call CryptGenRandom when Win32::API is not available, making it work with Windows 64-bit too.
Comment 163 Frédéric Buclin 2011-01-16 04:48:13 PST
Created attachment 504237 [details]
Use Win32::GuidGen()

Here is a script which generates random passwords on Windows using Win32::GuidGen (no need for Win32::API). I wrote it in a way which makes it easy to integrate in the real generate_random_password() subroutine of Bugzilla::Util.

That's the code I would like to see being used for Windows. This also means that we no longer need to call srand() ourselves. On *nix, I still don't think there is a need to call srand() every 5 characters, first because it's bad to call srand() several times, and 2nd because this would only be critical to generate the site wide secret. In all other cases, this is IMO useless. This reseeding should either be removed or only happen every 16 characters (which is the usual upper limit used for tokens, which do not need reseeding).

And as we are no longer affected by the Win32::API problem on Windows 64-bit, it makes even more sense to make Math::Random::Secure mandatory for Bugzilla 4.0.
Comment 164 Max Kanat-Alexander 2011-01-16 21:22:43 PST
(In reply to comment #157)
> Maybe should
> Math::Random::Secure require this version as a minimum, to be sure to work with
> Perl 5.12 on Windows.

  There wouldn't be any reason to update Math::Random::Secure. The test that failed had nothing to do with the functionality of Math::Random::ISAAC, it was just an author-only test that should not have been being run during installation.
Comment 165 Max Kanat-Alexander 2011-01-16 21:34:10 PST
(In reply to comment #158)
> OK, I definitely don't trust too much what is done here. 

  Have you actually tested it? Try gen-test.pl on Windows with this patch.

> My opinion for
> Bugzilla 4.0 is that we should require Math::Random::Secure on *nix.

  This seems unrelated to your comment above, since your comment above is about the Windows code.

> Linux
> packagers will add the missing dependencies when packaging Bugzilla 4.0. Once
> 4.0rc2 is out, we can notify them so that they have time before 4.0 final is
> out. 

  You're making assumptions about things that you can't actually know, such as the configuration of every Bugzilla server in existence.

> Also, sysadmins who only want to depend on packages provided by their
> distro won't install Bugzilla 4.0 themselves,

  That's not true. Many organizations install Bugzilla from the tarball but require all other things to be from packages.

> For Bugzilla 3.6.4 and older, I agree to make it optional.

  Why is it okay for one stable branch but not for another? I understand why it would make a difference on trunk--it has to do with the ongoing maintenance of that code *forever*.

> your hack (which gives us no guarantee of being cryptographically strong).

  I have explained this many times now, including several times in this bug. If you don't understand my explanation, please tell me and I will clarify it. I'll say it again (without the explanation): there is absolutely no need for that code to be cryptographically strong--it only has to generate unique values every single time it is called, even if called in a tight loop. In my tests on Windows, it does. Does it do so in your tests? If it doesn't, then we definitely need to fix that.

> The version 4 GUIDs mentions in this document is described in RFC 4122 [3], see
> section 4.4. As these randomly-generated GUIDs are available thanks to
> Win32::GuidGen(), which calls CoCreateGuid(), we can simply use them when
> generate_random_password() is called.

  If this works on 64-bit Perl, then I agree that this is a good idea.
Comment 166 Max Kanat-Alexander 2011-01-16 21:40:05 PST
Comment on attachment 504237 [details]
Use Win32::GuidGen()

  Cool! :-)

>    my $rand = sub {
>        $data = _get_guids($size) unless $data;
>        # Extract 8 hexadecimal characters (= 32 bits) and convert it
>        # into a random number.
>        return hex(substr($data, 0, 8, "")) / 2**32 * $_[0];

  Instead of this we should just be using 32 bits of a GUID for srand, which will make things simpler. Real security comes from Math::Random::Secure--I don't want to otherwise make statements about our security.

>    my @guids = map { Win32::GuidGen() } (1..$calls);

  So that means that all we'd have to do is call Win32::GuidGen, remove the hyphens and brackets, and use the first six characters as a 32-bit integer in hex. Can the first 8 characters span the entire width from 0 - 2^32?
Comment 167 Byron Jones ‹:glob› 2011-01-16 22:10:46 PST
>   If this works on 64-bit Perl, then I agree that this is a good idea.

works with 64-bit activeperl
Comment 168 Max Kanat-Alexander 2011-01-16 22:36:55 PST
  Sweet! In that case I will soon post a new patch that uses GuidGen for Windows instead of that custom code.
Comment 169 Frédéric Buclin 2011-01-17 00:15:14 PST
(In reply to comment #166)
>   Instead of this we should just be using 32 bits of a GUID for srand, which
> will make things simpler. Real security comes from Math::Random::Secure--I
> don't want to otherwise make statements about our security.

We don't need to call srand() as CrytGenRandom() already returns cryptographically strong data. This code is precisely for when Math::Random::Secure is not available, else M::R::S already does the job for us.



(In reply to comment #165)
>   Have you actually tested it? Try gen-test.pl on Windows with this patch.

I don't need to try gen-test.pl. All it does is to tell you if generated passwords have dupes or not. This doesn't tell you how hard they are to guess, which is precisely what this bug is about.



>   This seems unrelated to your comment above, since your comment above is about
> the Windows code.

Right, this comment about *nix is independent on how things work on Windows. It's easy to make a module mandatory on *nix only thanks to "if ON_WINDOWS". That's what I meant. :)


>   You're making assumptions about things that you can't actually know, such as
> the configuration of every Bugzilla server in existence.

Which assumptions am I making which is incorrect? That's it's harder to use Math::Random::Secure with 4.0 than with 4.2? That the lack of time is the critical point here? That the distros planning to ship Bugzilla 4.0 won't necessarily have the ability to provide missing or up-to-date dependencies? I admit I know nothing about the process to ship new packages in Linux distros. But what I also know is that Bugzilla 4.0 doesn't exist yet, so why is it suddenly a problem? If there are stable Linux distros or beta Linux distros which are past "feature freeze" and which already ship 4.0rc1, then I fully agree that this would be a problem for them in case they cannot ship missing dependencies or update them, because they would be blocked with 4.0rc1 "forever" in these releases. If that's the case, then I totally agree to make Math::Random::Secure optional for 4.0; but that's something which worth being checked first, IMO.


>   Why is it okay for one stable branch but not for another?

Because we didn't release 4.0 yet. It's not yet what I call a stable branch. It's a branch being stabilized and finalized. For 3.6 and older, we already released minor releases on each branch, and we shouldn't suddenly require a new module.


> say it again (without the explanation): there is absolutely no need for that
> code to be cryptographically strong--it only has to generate unique values
> every single time it is called, even if called in a tight loop.

Correct me if I'm wrong, but "unique values" doesn't mean "unguessable". A good example is comment 0. You are saying that we should trust your code more than what is returned by CryptGenRandom, on Windows. That's what I have a problem with.
Comment 170 Max Kanat-Alexander 2011-01-17 00:42:07 PST
(In reply to comment #169)
> We don't need to call srand() as CrytGenRandom() already returns
> cryptographically strong data. This code is precisely for when
> Math::Random::Secure is not available, else M::R::S already does the job for
> us.

  As I have learned while writing Math::Random::Secure, you do not want to be writing your own rand() implementation if you can help it. There are too many ways for it to go wrong. There are other good reasons to keep the code as consistent as possible across platforms, too (which I'm sure that you know, since we've seen the problems that can come from code that most of us don't interact with, since we're not using Windows).

  I agree that GuidGen is a good way to get a small piece of random data, though. On Windows, all we need that for is to seed the random number generator.

> I don't need to try gen-test.pl. All it does is to tell you if generated
> passwords have dupes or not. This doesn't tell you how hard they are to guess,
> which is precisely what this bug is about.

  This bug is about being able to guess a seed by brute force. In any case, I don't care about my _do_srand implementation, because you are right that using GuidGen is a better way to get a seed.


> Which assumptions am I making which is incorrect? That's it's harder to use
> Math::Random::Secure with 4.0 than with 4.2? That the lack of time is the
> critical point here? That the distros planning to ship Bugzilla 4.0 won't
> necessarily have the ability to provide missing or up-to-date dependencies?

  More or less. But also that we've already released an RC, and people will have made plans. They have existing Bugzilla servers that they want to continue to use, and since this will be an important security update (to an RC in particular) they will want to update to it immediately if they are using the previous RC or earlier 3.7.x code. However, if they can't install M::R::S, they will be vulnerable because they will be totally unable to upgrade.

  Also, 4.0 is a very important release and I don't want new barriers suddenly popping up to its adoption. This bug has been around for a few weeks now, so it's not new to us, but this M::R::S requirement will be new *instantly* upon the release of rc2, and I don't like to spring things like that on people if I can help it. And we can help it, in this case.

  Also, if people *do* choose to install M::R::S, they can. Also, as far as we are aware, the code that *isn't* using M::R::S is actually still secure.


  I do want to be clear here, though, that I think that using the Win32 GUID generator was a really clever idea and definitely better than my _do_srand implementation. I definitely want to use the GUID generator to generate a seed.
Comment 171 Max Kanat-Alexander 2011-01-17 11:20:52 PST
For everybody's information, here is what the Perl team says:

"Our goal is to have a new randomness implementation in the core in 5.13.10 (currently due on February 20), for a stable production release as part of 5.14.0 this spring."

I'm talking with the implementor about how it's going to work.
Comment 172 Max Kanat-Alexander 2011-01-18 00:17:42 PST
Created attachment 504640 [details] [diff] [review]
Patch for 3.2, v4

Okay, here's a patch for 3.2 that uses GuidGen to generate the seed. I've tested this on my local copy of XP-64 and it seems to work fine.
Comment 173 Max Kanat-Alexander 2011-01-18 00:19:53 PST
Created attachment 504641 [details] [diff] [review]
Patch for 3.4, v4

Updated patch for 3.4 that uses GuidGen.
Comment 174 Max Kanat-Alexander 2011-01-18 00:21:31 PST
Created attachment 504642 [details] [diff] [review]
Patch for 3.6, v4
Comment 175 Max Kanat-Alexander 2011-01-18 00:24:13 PST
Created attachment 504643 [details] [diff] [review]
Patch for 4.0, v4
Comment 176 Frédéric Buclin 2011-01-21 16:42:43 PST
Comment on attachment 504643 [details] [diff] [review]
Patch for 4.0, v4

r=LpSolit. Note that I didn't test your code with mod_perl, though. Please do it (with and without Math::Random::Secure) just to make sure there is no problem with it.
Comment 177 Frédéric Buclin 2011-01-21 16:51:22 PST
Comment on attachment 504642 [details] [diff] [review]
Patch for 3.6, v4

r=LpSolit
Comment 178 Max Kanat-Alexander 2011-01-21 17:09:06 PST
Created attachment 506019 [details] [diff] [review]
Patch for 4.0, v5

The branch patches have an error in mod_perl.pl--semicolons are in the wrong places. This fixes it.

I've now tested this on mod_perl and am sure that it works, both with MRS installed and with it not installed.
Comment 179 Max Kanat-Alexander 2011-01-21 17:10:46 PST
Comment on attachment 506019 [details] [diff] [review]
Patch for 4.0, v5

LpSolit says I can carry forward r+ here.
Comment 180 Frédéric Buclin 2011-01-21 17:16:02 PST
Comment on attachment 504641 [details] [diff] [review]
Patch for 3.4, v4

r=LpSolit
Comment 181 Max Kanat-Alexander 2011-01-21 17:16:54 PST
Created attachment 506022 [details] [diff] [review]
Patch for 3.6, v5

Same mod_perl fix for the 3.6 branch.
Comment 182 Max Kanat-Alexander 2011-01-21 17:21:28 PST
Created attachment 506023 [details] [diff] [review]
Patch for 3.4, v5

Fixes mod_perl for 3.4
Comment 183 Max Kanat-Alexander 2011-01-21 17:27:35 PST
Created attachment 506025 [details] [diff] [review]
Patch for 3.2, v5

Fixes mod_perl for 3.2.
Comment 184 Frédéric Buclin 2011-01-21 18:08:32 PST
Comment on attachment 506025 [details] [diff] [review]
Patch for 3.2, v5

r=LpSolit
Comment 185 Max Kanat-Alexander 2011-01-24 13:50:19 PST
Committing to: bzr+ssh://bzr.mozilla.org/bugzilla/trunk/                       
modified mod_perl.pl
modified Bugzilla/Util.pm
modified Bugzilla/Install/Localconfig.pm
modified Bugzilla/Install/Requirements.pm
Committed revision 7676.

Committing to: bzr+ssh://bzr.mozilla.org/bugzilla/4.0/                         
modified mod_perl.pl
modified Bugzilla/Util.pm
modified Bugzilla/Install/Localconfig.pm
modified Bugzilla/Install/Requirements.pm
modified template/en/default/setup/strings.txt.pl
Committed revision 7533.

Committing to: bzr+ssh://bzr.mozilla.org/bugzilla/3.6/                         
modified mod_perl.pl
modified Bugzilla/Util.pm
modified Bugzilla/Install/Localconfig.pm
modified Bugzilla/Install/Requirements.pm
modified template/en/default/setup/strings.txt.pl
Committed revision 7226.

Committing to: bzr+ssh://bzr.mozilla.org/bugzilla/3.4/                         
modified mod_perl.pl
modified Bugzilla/Util.pm
modified Bugzilla/Install/Localconfig.pm
modified Bugzilla/Install/Requirements.pm
Committed revision 6793.

Committing to: bzr+ssh://mkanat%40bugzilla.org@bzr.mozilla.org/bugzilla/3.2/   
modified mod_perl.pl
modified Bugzilla/Util.pm
modified Bugzilla/Install/Localconfig.pm
modified Bugzilla/Install/Requirements.pm
Committed revision 6415.
Comment 186 Frédéric Buclin 2011-08-09 14:31:13 PDT
This bug has been fixed more than 6 months ago. Bugzilla 4.0 and 4.2 are not vulnerable to this issue, and Bugzilla 3.6 has been patched since version 3.6.4. We also released 3.6.5 and 3.6.6 meanwhile so admins had a plenty of time to upgrade or patch their installation.

The initial description of this bug contains all the details related to the vulnerability, and will probably be useful to many other Perl installations across the world. So I'm removing the security flag, making this bug public. 

On behalf of the Bugzilla team, I would like to thank you again Willem for the quality of your bug report and analysis. It was definitely the best security bug report we have ever seen.

Note You need to log in before you can comment on or make changes to this bug.