Borrar en que sentido? Limpiar la imagen del color rojo que has pintado con el Paint?

Mmh, en realidad no se podría, asumiendo obviamente que eso lo hayas hecho en el paint y que lo hayas borrado completamente de tal manera que no se pueda deducir lo que hay abajo, no se podría recuperar, ya que habrías reemplazado los pixeles que representaban la informacion oculta por pixeles rojos.
Claro que si es una imagen multi-capa editada en un editor con soporte multi-capa, entonces podría llegar a ser borrada la capa que cubre la información, revelandola.
Esteganografía, es ocultar en un archivo cierta información, de tal manera que no se afecte de manera perceptible el flujo principal del archivo contenedor.
Por ejemplo, si es una imagen, no se debería poder ver la alteración en ella, si es un sonido, no se podría poder percibir los cambios en este. Se utiliza para esto la deficiencia en los sentidos, que no nos permite diferenciar un color de otro, cuando en realidad son diferentes o no nos permite escuchar un sonido demasiado agudo (> 20000 Hz) o demasiado grave (< 20 hz).
Esos "blind spots" sirven para esconder información.

Hola

Andar tocando el bit menos significativo es un método válido para incrustar algo en una imagen, pero no es el único.

Pongamos un ejemplo: quiero insertar un texto en un PNG y que no se note.

Una forma de hacerlo es efectivamente buscar la estructura del archivo PNG para encontrar donde están los bits menos significativos. Para averiguar eso me voy a la RFC que define el formato

RFC 2083
http://www.rfc-editor.org/rfc/rfc2083.txt

Y efectivamente curioseando por allí encuentro donde están y como acceder a esos datos, pero me encuentro con algo que no esperaba. Resulta que el formato PNG tiene una cabecera con un formato específico y luego unas secciones. Esas secciones contienen diversos datos, pero lo curioso es que para que los distintos programas puedan ampliar capacidades (y por capacidades futuras del formato PNG) se pueden agregar secciones a voluntad que serán ignoradas por los programas gráficos pero que pueden contener bloques de hasta 64k y puedes usar cuantos bloques quieras.

Así que todo el problema consiste en ver como se hace una sección y escribir en ella lo que me de la santa gana.

En la RFC pone que una sección se compone de así:
4 bytes para longitud de datos
4 bytes para su nombre
los datos (aquí meteré mi texto)
4 bytes para el crc

El nombre de una sección (4 letras) debe cumplir las siguientes reglas
1ª letra ---> Si es mayúscula el bloque es CRITICO. En mi caso no, es un bloque opcional osea que mi nombre empezará por minúscula
2ª letra ---> Si es mayúscula el bloque es PUBLICO (descrito en la rfc). En mi caso no. Es un bloque privado así que la segunda letra será minúscula.
3ª letra ---> Es un valor reservado para el futuro. Actualmente debe ser siempre mayúscula
4ª letra ----> Si es mayúscula un editor de png que grabe este código guardará también este bloque. Si no lo es no lo guardará. En mi caso prefiero que si la imagen la pilla alguien con un editor de png y comete el error de guardar el bloque se pierda así que usaré un nombre con mayúscula.

Así que me invento un nombre que cumpla esas condiciones por ejemplo "abCD"

Así que primero grabo en los primeros cuatro bytes la longitud de lo que quiero escribir, luego el nombre que le daré a la sección "abCD", luego lo que quiero escribir (que podría tener algún tipo de cifrado obviamente) y luego el CRC-32 que utiliza PNG y que ocupa 4 bytes.

La forma de hacerlo por tanto es leer la imagen. Primero el bloque cabecera, luego el bloque IHDR, grabar mi sección y luego continuar leyendo y grabando secuencialmente el PNG.

Hay que tener cuidado que PNG utiliza bigendian.

Como veis es mas dificil de explicar que de hacer porque en realidad lo único que haces es leer un determinado número de bits (cabecera y bloque IHDR), luego escribir tu bloque y luego escribir secuencialmente todo el PNG original para que tu bloque quede debidamente insertado donde tu quieras. Lo único "dificil" es crear un string que tenga 4 bytes con la longitud del mensaje, 4 bytes con el nombre, los datos que quieras y 4 bytes con su crc.

Para leerlo solo hay que buscar el nombre de su sección. Los cuatro bytes anteriores son la longitud del mensaje.

Para quien tenga interes en saber como funciona eso del CRC también le puedo explicar. Todo se reduce a una división polinómica en módulo dos (que también suena a algo terrible pero es una chorrada). Hay diversos CRC según el uso que se va a dar.

¡Cuanto tiempo que no venía yo por aquí!