Hiding information in Cats

24

5

You are a secret agent trying to communicate with your fatherland. Of course the information needs to be hidden so no one eaves drops your message. What would be better suited than a cat? Everyone loves funny pictures of cats [citation needed], so they won't suspect secret information hiding in there!


Inspired by the algorithm the game Monaco uses to save the level information of shared levels it is your tasks to write a program that encoded information into the least significant bit of the colors of an image.

Encoding format:

  • The first 24 bits determine the length of the remaining encoded byte-string in bits
  • The image is read from left to right and from top to bottom, obviously starting in the upper left pixel
  • The channels are read from red to green to blue
  • The least significant bit from each channel is read
  • Bits are saved in Big Endian order

Rules:

  • Your program takes a single byte-string to be encoded and a single image filename for the base image
  • The resulting image must be come out as a true color PNG file
  • You may use I/O in whatever form you like (ARGV, STDIN, STDOUT, writing / reading from a file), as long as you state how to use your program
  • You must choose a random image of a funny cat and encode your program into it to show that your program works
  • You may assume that you are only provided valid input, if the amount of bits are not sufficient, the image is not in true color format, the image does not exist or similar problems you may do what you want
  • You may assume that the provided image does not contain any alpha channel
  • Length is counted in UTF-8 bytes without BOM

You may use this PHP script to test your solution, provide the name of the PNG file as the first command line argument:

<?php
if ($argc === 1) die('Provide the filename of the PNG to read from');
$imageSize = @getimagesize($argv[1]);

if ($imageSize === false) die('Not a PNG file');
list($width, $height) = $imageSize;

$image = imagecreatefrompng($argv[1]);
$read = 0;
$bits = '';
for ($y = 0; $y < $height; $y++) {
    for ($x = 0; $x < $width; $x++) {
        $colorAt = imagecolorat($image, $x, $y);
        $red = ($colorAt >> 16) & 0xFF;
        $green = ($colorAt >> 8) & 0xFF;
        $blue = ($colorAt >> 0) & 0xFF;

        $bits .= ($red & 1).($green & 1).($blue & 1);
        $read += 3;
        if ($read == 24) {
            $length = (int) bindec($bits);
            $bits = '';
        }
        else if ($read > 24 && ($read - 24) > $length) {
            $bits = substr($bits, 0, $length);
            break 2;
        }
    }
}
if (strlen($bits) !== $length) die('Not enough bits read to fulfill the length');
$parts = str_split($bits, 8);
foreach ($parts as $part) {
    echo chr(bindec($part));
}

TimWolla

Posted 2014-04-07T20:07:11.403

Reputation: 1 878

@TimWolla Would it be valid to get the cat to swallow a memory stick then take a picture of it? – Sonic Atom – 2016-01-07T12:19:24.107

@SonicAtom Can you get the information back, afterwards? – TimWolla – 2016-01-07T15:56:29.150

1@TimWolla From the cat? Keep it indoors and monitor the litter tray. From the photo? If you take a high enough resolution X-ray photo you may be able to see the state of the individual transistors in the flash chip. I'm certain this must be the most efficient method of passing secret information ever devised, although the cat may have other ideas. – Sonic Atom – 2016-01-07T18:18:13.847

Your specification says "your program takes a single image as a base". In Mathematica an image is actually just an expression like everything else, so technically this specification would allow me to do the file-loading outside of the code that performs the computation (with the input parameter being an actual image instead of the image's file name). If you don't want stuff like that, you might want to specify that the program needs to take an image's file name as input. – Martin Ender – 2014-04-07T20:42:04.313

4ME helpimtrappedinacatfactory OW – TheDoctor – 2014-04-07T20:43:48.680

Also, do the bits not used for encoding need to remain untouched? Or can we set them to whatever we want (since that won't really affect image quality and doesn't matter for decoding)? – Martin Ender – 2014-04-07T20:47:55.517

@m.buettner Do whatever you want with the unused bits. About the Mathematica issue: Thanks, I'll see what I do. – TimWolla – 2014-04-07T20:57:41.373

@TimWolla cheers. Another question: you only said we may assume the input image is true colour. May we also assume it has an alpha channel? – Martin Ender – 2014-04-07T21:12:24.440

@m.buettner I don't see how this helps, would you explain it? – TimWolla – 2014-04-07T21:24:20.933

@TimWolla well if there is already an alpha channel I have to skip it during encoding (assuming we're only encoding in the RGB channels as in the article you linked). If there is no alpha channel, I don't have to skip any channels. That does make a difference in my implementation. It also kind of matters for the output. Does the output need to preserve alpha channel? Is it allowed to introduce a alpha channel filled with all 255 if there was no alpha channel in the input? And so on... Of course it would be easiest if we could assume that there is never any alpha present. – Martin Ender – 2014-04-07T21:30:11.797

@m.buettner I see. I just added „- You may assume that the provided image does not contain any alpha channel“ – TimWolla – 2014-04-07T21:32:38.167

To be explicit, you're expecting us to write an encoder and not a decoder? And what's the endianness of the conversion between bitstream and bytes? – Peter Taylor – 2014-04-07T21:32:59.010

@PeterTaylor An encoder, yes. My decoder assumes Big Endian. – TimWolla – 2014-04-07T21:34:00.067

1Can I use a non-built-in library to load and save the png file, eg PIL in Python? – Claudiu – 2014-04-07T23:45:09.997

@Claudiu Yes, you don't have to build PNG writing by hand. (I am using GD library in PHP myself) – TimWolla – 2014-04-08T09:24:51.543

Answers

3

Perl & ImageMagick (Linux), 198 190

Edit: By some coincidence, earlier I tested on a computer with Q8 (8 bit depth) version of ImageMagick installed. 'Standard' Q16 version requires explicit -depth 8 on command line. On Linux, identify result requires newline to be removed, too. Both factors lead to code size increase, therefore I post Linux (probably Mac too) version as an answer, with fixes applied, and also with some Windows-only stuff removed (cr-lf conversion, binary vs text etc.). Portable (slightly longer) version is posted near the end.

With newlines for readability:

$/=$1;
<>=~/\n/;
$_=`identify -format %wx%h $\``;
chop;
open O,"|convert -size $_ -depth 8 rgb: $`.png";
$_=`convert $\` rgb:`;
print O$_&y//\376/cr|unpack('B*',pack(NX,2048*length$').$')&y//\1/cr

Run:

perl cat.pl

It reads from STDIN, image file name on first line, 'secret' message follows, terminated with ctrl-D. Output file name is original with .png appended - not very nice, it's only done for brevity.

Here's an image with some very secret information hidden within:

enter image description here

And with some comments:

# Undef input record separator, because we'll slurp input.

$/=$1;

# Read from STDIN, separate first line. 
# $` (prematch) contains image file name,
# $' (postmatch) - text to encode.

<>=~/\n/;

# Get IM's 'identify' output, width and height of the image. 
# Note: we don't have to separate them, \d+x\d+ string will 
# do just fine.

$_=`identify -format %wx%h $\``;
chop;

# Open output pipe - IM's 'convert' command that takes raw RGB data from 
# STDIN and writes output to PNG file. Interpolated into this command
# line is previous IM's 'identify' result. Convert wants '-size' command
# option in case of raw RGB input - for obvious reason.

open O,"|convert -size $_ -depth 8 rgb: $`.png";

# Get raw RGB data into $_.

$_=`convert $\` rgb:`;

# Last line does all the job. 

# y//\376/cr --- create string same length as $_, fill with 0xFE
# $_&y//\376/cr --- zero least significant bit for all image bytes (1).
# pack(NX,2048*length$') --- multiply by 8 (bytes to bits count) and 
#         shift left by 8 (because we'll pack long integer into 3 bytes) -
#         i.e. multiply by 2048.
# unpack('B*',pack(NX,2048*length$').$') ---- append 'secret text' to 
#       its encoded length and convert to 'binary' (consisting of 1 and 
#       0 characters) string.
# ... &y//\1/cr --- equivalent of tr/01/\0\1/. We don't have to worry 
#       that raw RGB length is larger than encoded text length, because
#       '&' truncates longer string argument (2).
# Then bitwise-'or' (1) and (2) strings.

print O$_&y//\376/cr|unpack('B*',pack(NX,2048*length$').$')&y//\1/cr

Next is portable version, runs on both Windows (use ctrl-Z to terminate input) and Linux, byte count is 244.

$_=do{local$/;<>};
/\n/;
$_=`identify -format %wx%h $\``;
chomp;
open I,'-|:raw',"convert $` rgb:";
open O,'|-:raw',"convert -size $_ -depth 8 rgb: $`.png";
$_=do{local$/;<I>};
print O$_&y//\376/cr|unpack('B*',pack(NX,2048*length$').$')&y//\1/cr

user2846289

Posted 2014-04-07T20:07:11.403

Reputation: 1 541

10

Mathematica, 255 234 206 bytes

I've seen so many 255s while testing this, I'm unreasonably happy about the size of the code. :) And then my ambition to golf it down even further got the best of me...

f=(j=ImageData[Import@#2,t="Byte"];k=(d=IntegerDigits)[j,2,8]~Flatten~2;n=1;(k[[n++,-1]]=#)&/@d[Length@#,2,24]~Join~#&[Join@@d[ToCharacterCode@#,2,8]];ArrayReshape[#~FromDigits~2&/@k,Dimensions@j]~Image~t)&

It's technically a function and not a "program", but then again this is pretty much how you write "programs" in Mathematica, if that concept is even valid there. Call it like

f["my secret", "fully/qualified/cat.png"]

It will return an actual image expression (because that's the most natural way to return an image in Mathematica), so if you want a file, you need to export it:

Export["output-cat.png", f["my secret", "input-cat.png"]]

Here is the required example:

enter image description here

I'd love to show you the decoded message here, but it doesn't fit... so run it through the OP's decoder. ;)

Btw, I could make it work with UTF-8 secrets for just 7 bytes (change ToCharacterCode@# into #~ToCharacterCode~"utf8").

Ungolfed code:

f[secret_, filename_] := (
  bits = Join @@ IntegerDigits[ToCharacterCode[secret], 2, 8];
  bits = Join[d[Length @ bits, 2, 24], bits];
  data = ImageData[Import@#2, "Byte"];
  dims = Dimensions@data;
  data = Flatten[IntegerDigits[data, 2, 8], 2];
  m = n = 1;
  While[m <= Length @ bits,
    data[[n++, -1]] = bits[[m++]]
  ];
  Image[ArrayReshape[FromDigits[#, 2] & /@ data, dims], "Byte"]
)

Martin Ender

Posted 2014-04-07T20:07:11.403

Reputation: 184 808

"I'd love to show you the decoded message here, but it doesn't fit... so run it through the OP's decoder. ;)" - I did and it gives me "????????????+++++++??++++++++++++++++++++=================~===~============~::::~~~~~=[... for 9773 characters]" – TessellatingHeckler – 2014-04-08T03:26:41.390

1@TessellatingHeckler, that's correct. try it in a monospaced font and be aware that there are UNIX-style new lines in there (e.g. try in a terminal or PowerShell with at least 180 characters width, or if you're running it in as a web script in your browser, then view the source) ;) – Martin Ender – 2014-04-08T07:45:16.403

2I see! Very meta. Helps that I'm in the KiTTY version of PuTTY, too – TessellatingHeckler – 2014-04-08T09:21:06.707

5

PHP, 530 byte

<?php function p($i,$j){return str_pad(decbin($i),$j,0,0);}extract(getopt("i:o:t:"));$t=file_get_contents($t);$_=imagecreatefrompng($i);list($w,$h)=getimagesize($i);$b="";for($i=0;$i<strlen($t);)$b.=p(ord($t[$i++]),8);$l=strlen($b);$b=p($l,24).$b;$l+=24;for($i=$x=$y=0;$y<$h;$y++){for(;$x<$w;){$C=imagecolorat($_,$x,$y);$R=($C>>16)&0xff;$G=($C>>8)&0xff;$B=$C&0xff;$i<$l&&$R=$b[$i++]|$R&~1;$i<$l&&$G=$b[$i++]|$G&~1;$i<$l&&$B=$b[$i++]|$B&~1;imagesetpixel($_,$x++,$y,imagecolorallocate($_,$R,$G,$B));if($i>$l){imagepng($_,$o);die;}}}

Run like php 25443.php -i<input image> -o<output image> -t<file to hide>.

And here's a sample image.

http://i.imgur.com/hevnrbm.png

Ungolfed code is hidden in the sample image. Tested with OP's decoder. Sorry for not funny cat picture.

Snack

Posted 2014-04-07T20:07:11.403

Reputation: 2 142

1Please add the ungolfed code in your answer. – A.L – 2014-04-08T13:03:50.480

1You can shorten 0xff to 255. – TimWolla – 2014-04-08T14:05:24.580

You can save 4 bytes if you assume short tags: <?function. – nyuszika7h – 2014-04-29T18:12:19.917