I thought sugar solidified when they absorbed moisture, not lost it? I seem to recall hearing that a microwave was a good way to soften sugar. (Make sure the box doesn’t have metal parts.)
In addition, you can prevent this from happening in the future by transferring it from the box to a plastic ziploc. Press out all the possible air and seal well. If you have one of those hand-vac devices, so much the better.
I’ve tried sealing brown sugar in ziploc plastic bag many times and it has still turned into a rock. One of these days I’ll have to try one of the damp methods (apple, wet paper towel, etc.).
Up to now if I had a recipe that I needed to stir the brown sugar into I just bought fresh (and threw out the old rocks if I had too many). If it was a recipe where the brown sugar needed to dissolve (e.g. butterscotch), then I just beat the s—t out of it with a hammer until I got it broken down enough to put into a measuring cup. Good way to work out your frustrations!
I’ve found the fridge to be a good place for soft brown sugar, since the humidity is much higher than in your average kitchen cupboard. A tablespoon of water sprinkled on top of the sugar, taping the bag shut, and into the fridge overnight usually works for me.
Wet paper towel draped over top works for me. I learned from experience that you should always transfer brown sugar immediately to a different container upon taking it home.