Is there a way to cleanse a picture of information from steghide? Recently I learned of the steghide application (a command-line tool allowing the use of steganography, the art of hiding information inside other information, used in practice with JGP and WAV files primarily with gzip compression and AES encryption).

Excitedly, I hid sensitive data in my desktop background, deleting the original desktop background in it's place.

After more research, I realized that the default algorithm used (128-bit AES) is considered weak (for my standards, anyway. It's nice to be ahead of the game, using 4096-bit RSA and 256-bit AES for things).

Is there a way to cleanse this JPG file of the irrelevant bits that the embedded file is stored in?

I'm not entirely sure how the use of the passphrase (aside from encryption) is implemented to hide the file in a recoverable place using steghide, but I would assume that if you know the passphrase, you can find the exact bits that the file is located in. Is there a way to locate these bits and overwrite them in the same manner you would use to shred a file, but keeping the original image the same (to the human eye)?
Or am I boned?
As you stated steganography hide data in less important piece of information of a source (because the goal is hide data within other data affecting them less as possible).

In no way pure steganography protect the message hidden, it's only a tool for hiding.

Image you would hide message "AB" in a grey scaled bitmap 4x4 (0-255 value per pixel).

Eg :

Convert message in bit :
"AB" &gt; hex -&gt; 65 66 -&gt; 01000001 01000010

Do the same thingh with your image (0 is black 255 is white, grey between) :
 ____
|####|    0   0   0   0       00000000 00000000 00000000 00000000
| #  |--&gt; 255 0   255 255 --&gt; 11111111 00000000 11111111 11111111
| #  |    255 0   255 255     11111111 00000000 11111111 11111111
|__#_|    255 255 0   255     11111111 11111111 00000000 11111111

Foreach bit of your messaage, sobstitute the less significant bit of the
corresponding byte of the picture so :

Message  Original Picture              Resulting Picture
0        00000000                      00000000
1        00000000                      00000001
0        00000000                      00000000
0        00000000                      00000000
0        11111111                      11111110
0        00000000                      00000000
0        11111111                      11111110
1        11111111                      11111111
0        11111111                      11111110
1        00000000                      00000001
0        11111111                      11111110
0        11111111                      11111110
0        11111111                      11111110
0        11111111                      11111110
1        00000000                      00000001
0        11111111                      11111110

Original Picture                    | Picture with Message
00000000 00000000 00000000 00000000 | 00000000 00000001 00000000 00000000
11111111 00000000 11111111 11111111 | 11111110 00000000 11111110 11111111
11111111 00000000 11111111 11111111 | 11111110 00000001 11111110 11111110
11111111 11111111 00000000 11111111 | 11111110 11111110 00000001 11111110


As you can see message stored in that way (in the bitmap) does not have a great impact on the way on which human percept the image (pixels are pretty equals before and after).
The algorithm i have described is very naive but the principle is the same in every steganography algorithm.

In your case there is not bitmap but JPEG (a complicated way to represent image, complicated because there are compression algorithm), and there is a password and encription.
Encription is there for two reason, secure the message (steganograpy alone does not guarantee any confidentiality) and create a noise like distribution on less significative bits (normally less significant bits has such distribution but an hidden message may deviate that distribution in the Resulting Picture, so an attacker can identify which pictures hide a message).

If you wuold be sure that an image does not hide secret data you don't have to try to find them.
Mainly beacuse every steganograpy algorithm is particular and store information in a different way (the only limit is the immagination), secondly because if steganograpy is done properly (with robust encription) you can not distinguish between noise and hidden data.

So the only approach that seems to me pratical is try to manipulate the candidate picture (a picture that could contain hidden data but also could be a regular picuture) in a way that a side channel will be broken.

In my naive implementation a manipulation for cleanup could be a compression with JPEG, JPEG is pretty close to bitmap (to human eye), but the less significant bit will be whipped out (due to compression) and hidden information with them.

In your specific case i suppose that taking the picture and compress it again with JPEG (using a greater factor of compression) should also work.
Remember that every steganography algorithm is particular so one may store hidden data in a redundant way, tryin to be more resilent to your cleanup endeavour (see watermark tecnique : Digital Watermark).