Cleaning stone fireplace surround

[metalspinner]

I am painting the living room/kitchen this week. And have been noticing the fireplace surround is looking quiet dingy.
We had the fireplace box repaired last season. You can see that the fireplace had a bad draw and smoke would escape out the front of the box.
I'm wondering if I should scrub the whole face to brighten this up. And if so with what product?

[beenthere]

Mix up some muriatic acid. 

[newoodguy78]

I second beentheres suggestion. That and a wire brush is what I've used with good results. 

[florida]

Muriatic acid is an extremely dangerous and caustic chemical and should never be used in your house. Not only will the vapors cause serious lung problems the invisible fumes will corrode everything metal. If you're want ting to clean the smoke deposits a cleaner like 409 will work and if that doesn't do it a spray-on oven cleaner should work.

I keep muriatic acid in a plastic jug under an upturned garbage can back under some trees in my backyard. When I kept it by my pool equipment it corroded the electrical panel.

[SawyerTed]

Tri-sodium Phosphate and a stiff brush