Solution

1. The hidden quote is "Three may keep a secret, if two of them are dead", Benjamin Franklin

2. What is on the line?

• A key or a kite at the end

Code

My Python code is available on github at https://github.com/genevieve-le-houx/SO_challenge_18_hidden_in_plain_sight

My approach is fairly simple, I developped my decoder for the first task, got the hint for the second task and developped the second decoder.

from pathlib import Path
from typing import List

from PIL import Image
import numpy as np


def read_image(img_file: Path) -> np.ndarray:

    img = Image.open(img_file)
    np_img = np.array(img)

    img_flatten = np_img.flatten()

    return img_flatten


def get_all_lsb(img_flatten: np.ndarray) -> List[int]:
    result = []

    for pixel_channel in img_flatten:
        bin_str = f"{pixel_channel:08b}"
        result.append(int(bin_str[-1], 2))

    return result


def decode_msg(list_lsb: List[int]) -> str:
    header = list_lsb[0:2]
    data_size = int("".join(str(x) for x in list_lsb[2:18]), 2)

    message = ""
    buffer = ""

    for lsb in list_lsb[18:18 + data_size]:
        buffer += str(lsb)

        if len(buffer) == 8:
            message = message + chr(int(buffer, 2))
            buffer = ""

    return message


def task_0():
    img_folder = Path(__file__).parent.parent / "data/input/task_0"

    for img_name in ["black.png", "high_contrast.png", "real_image.png"]:
        img_file = img_folder / img_name

        img_flatten = read_image(img_file)
        list_lsb = get_all_lsb(img_flatten)

        msg = decode_msg(list_lsb)
        print(msg)


def task_1():
    img_folder = Path(__file__).parent.parent / "data/input"
    img_name = "image_1.png"

    img_file = img_folder / img_name

    img_flatten = read_image(img_file)
    list_lsb = get_all_lsb(img_flatten)

    msg = decode_msg(list_lsb)
    print(msg)


def get_binary_img_from_img(list_lsb: List[int]) -> np.ndarray:
    result = []
    header = list_lsb[0:2]
    width = int("".join(str(x) for x in list_lsb[2:18]), 2)
    height = int("".join(str(x) for x in list_lsb[18:34]), 2)
    img_pixels = list_lsb[34:34 + width * height]
    img = np.array(img_pixels, dtype=int).reshape(height, width)
    img[img == 1] = 255

    return img


def task_2():
    img_folder = Path(__file__).parent.parent / "data/input"
    img_name = "image_2.png"
    img_file = img_folder / img_name
    img_flatten = read_image(img_file)
    list_lsb = get_all_lsb(img_flatten)
    img = get_binary_img_from_img(list_lsb)

    img_save_path = Path(__file__).parent.parent / "data/output/output.png"
    Image.fromarray(img.astype(np.uint8)).save(img_save_path)


def main():
    print("--- Task 0 ---")
    task_0()
    print("")

    print("--- Task 1 ---")
    task_1()
    print("")

    print("--- Task 2 ---")
    task_2()
    print("")



if __name__ == "__main__":
    main()

That was a fun challenge!

Solution using R:

Really interesting challenge! Thanks!

Answers:

1. What is the hidden quote:

   "Three may keep a secret, if two of them are dead." Benjamin Franklin

2. What is on the line?

   A key. (Possible 2nd answer - a kite)

Using base R, except for the png package for reading and writing the images.

Code:

# --- Task 1 -----------------------------------------------------------------------------

# Helper function to convert binary to integer
bin_to_int <- function(bin) {
    sum(bin * rev(2 ^ (1:length(bin) - 1)))
}

# location of the cat image
cat_file <- "cat.png"

# Read the PNG data into an x * y * 3 matrix of RGB values
# The png::readPNG extracts just the image information into a  matrix
# and gives values as a fraction of 255, so multiply by 255 to get actual values
# Then get the LSB using modulo 2 operator
cat_pngimage <- png::readPNG(cat_file, info = TRUE)
cat_LSB <- (cat_pngimage * 255) %% 2

# Check the dimensions of this data
dim(cat_LSB)
# [1] 480 640   3
# So we have a 3-d array, a 480 x 640 matrix of pixels for each colour. We
# want the R, G and B values for each pixel to be in sequence so we have to
# re-shape this array

# First combine along dimension 3 (RGB) to get the 3 colour values in order
cat_combineRGB <- apply(cat_LSB, 1:2, c)

# Then combine along columns of the resulting array
cat_combineRows <- apply(cat_combineRGB, 2, c)

# finally convert to a vector of bits
cat_bits <- c(cat_combineRows)

# We now have our sequence of LSBs from the original image.

# Get the message length from bits 3-18
cat_message_length <- bin_to_int(cat_bits[3:18])

# Extract the message of the given length
cat_message_bits <- cat_bits[19:(18 + cat_message_length)]

# Reshape to an 8 * ? matrix for ease of binary conversion
dim(cat_message_bits) <- c(8, cat_message_length / 8)

# Convert each column into a digit and get the ASCII code
cat_message <- intToUtf8(apply(cat_message_bits, 2, bin_to_int))

# Show the message
cat(cat_message)
# The first part of the sentence is "Three may keep a secret, ...".
#
# ### Task 2: Decode a binary image
#
# A binary image is hidden in the least significant bits of the butterfly image, the encoding scheme is:
#
# - Simple LSB Encoding**
# - Header: `[1, 0]`
# - Next 16 bits: image `width` in pixels
# - Next 16 bits: image `height` in pixels
# - Raw pixels of the binary image
#
# Hint: Create and fill an image array of the derived `width` and `height` with the encoded hidden pixels.
# In order to view your image in classic viewers, it might be helpful to map 0 -> 0 and 1 -> 255.
# Derive the second part of the sentence and answer the question about the image.
# NULL

# --- Task 2 -----------------------------------------------------------------------------

# The first section of Task 2 will be similar to Task 1
butterfly_file <- "butterfly.png"
butterfly_pngimage <- png::readPNG(butterfly_file)
butterfly_LSB <- (butterfly_pngimage * 255) %% 2
butterfly_combineRGB <- apply(butterfly_LSB, 1:2, c)
butterfly_combineRows <- apply(butterfly_combineRGB, 2, c)
butterfly_bits <- c(butterfly_combineRows)

# This time we want width and height from the relevant bits of the stream
new_image_width <- bin_to_int(butterfly_bits[3:18])
new_image_height <- bin_to_int(butterfly_bits[19:34])

# And we can calculate the total length of the image
new_image_length <- new_image_width * new_image_height

# Extract these from the origial stream
new_image_bits <- butterfly_bits[35:(34 + 810000)]

# Convert to a matrix so we can save as PNG
new_image_pixels <- matrix(new_image_bits, nrow = new_image_height, byrow = TRUE)

# Save the image
png::writePNG(new_image_pixels, "result.png")

from PIL import Image

def decode(image_path):
    img = Image.open(image_path)
    pixels = list(img.getdata())

    bits = []
    for r, g, b in pixels:
        bits.append(r & 1)
        bits.append(g & 1)
        bits.append(b & 1)

    bits = ''.join(map(str, bits))

    # skip header
    bits = bits[2:]

    # read length
    length = int(bits[:16], 2)
    message_bits = bits[16:16+length]

    # convert to ASCII
    message = ''
    for i in range(0, len(message_bits), 8):
        byte = message_bits[i:i+8]
        message += chr(int(byte, 2))

    return message

Answers

1. What is the hidden quote?

   "Three may keep a secret, if two of them are dead."

   - Benjamin Franklin

2. Which object is on the line? Note, there are two possible correct answers here.

   A key and a kite are on the line.

Approach

My approach to solving the problem starts by writing a helper function that extracts the least significant bit (LSB) from each channel of each pixel in an image, and returns a flat array with all these pixels.

Then, the function for each task reads (or ignores, in the case of task 0) the header portion of the LSBs array and extracts the section of the array containing the bits that encode the message (or hidden image, in the case of task 2).

Next, the functions for tasks 0 and 1 read each group of 8 bits in the message array, convert it to an integer, and then to a character, which gets appended to the decoded message.

In turn, the function for task 2 creates a blank image with the dimensions specified in the header and sets each pixel to 0 or 255 based on the corresponding portion of the LSBs array.

Code

from PIL import Image

###################################################################

def extract_lsbs_from_image(image_path):
    # Open the image and convert it to RGB
    image  = Image.open(image_path).convert('RGB')
    pixels = image.load()
    width, height = image.size

    # Extract all LSBs from the image
    lsbs = []
    for y in range(height):
        for x in range(width):
            r, g, b = pixels[x, y]
            # Extract LSB of each channel
            lsbs.append(r & 1)
            lsbs.append(g & 1)
            lsbs.append(b & 1)

    return lsbs

###################################################################

def task_0(image_path):
    # Extract LSBs from the image
    bits = extract_lsbs_from_image(image_path)

    # Extract the message bits by skipping the first 2+16 = 18 bits
    message_bits = bits[18 : ]
    
    # Convert bits to ASCII characters (8 bits = 1 byte per char)
    message = ""
    for i in range(0, len(message_bits), 8):
        byte = message_bits[i : (i+8)]
        if len(byte) < 8:
            break
        ascii_code = int(''.join(map(str, byte)), 2)
        message += chr(ascii_code)

    # Display the hidden message
    print(message)

###################################################################

def task_1(image_path):
    # Extract LSBs from the image
    bits = extract_lsbs_from_image(image_path)

    # Check header
    assert bits[0 : 2] == [0, 0], "Wrong header!"

    # Read next 16 bits for message length
    length_bits = bits[2 : (2+16)]
    message_length = int(''.join(map(str, length_bits)), 2)
    
    # Extract the message bits based on the length
    message_bits = bits[18 : (18 + message_length)]
    
    # Convert bits to ASCII characters (8 bits = 1 byte per char)
    message = ""
    for i in range(0, len(message_bits), 8):
        byte = message_bits[i : (i+8)]
        if len(byte) < 8:
            break
        ascii_code = int(''.join(map(str, byte)), 2)
        message += chr(ascii_code)

    # Display the hidden message
    print(message)

###################################################################

def task_2(image_path):
    # Extract LSBs from the image
    bits = extract_lsbs_from_image(image_path)

    # Check header
    assert bits[0 : 2] == [1, 0], "Wrong header!"

    # Read next 16+16 bits for width and height
    width  = int(''.join(map(str, bits[2  : 18])), 2)
    height = int(''.join(map(str, bits[18 : 34])), 2)

    # Extract raw pixels starting from bit 2+16+16 = 34
    pixel_bits = bits[34 : (34 + width*height)]

    # Create the hidden image by mapping 0 -> 0 and 1 -> 255
    hidden_image  = Image.new('L', (width, height))
    hidden_pixels = hidden_image.load()

    bit_idx = 0
    for row in range(height):
        for col in range(width):
            # Map the bit to 0 or 255
            hidden_pixels[col, row] = 255 * pixel_bits[bit_idx]
            bit_idx += 1

    # Display the hidden image
    hidden_image.show()

###################################################################

if __name__ == "__main__":
    task_0("1RtT7h3L.png")
    task_0("EKD3bBZP.png")
    task_0("bmDwolWU.png")
    task_1("MBlXyTSp.png")
    task_2("mCeETXDs.png")

First of all, here are my answers:

1. "Three may keep a secret, if two of them are dead" - Benjamin Franklin
2. Key

The first thing I learnt from this challenge is to know your tools. I spent most of the time getting the raw image data from the PNG files.

Secondly, I was surprised at how much additional information a single image can contain without this being immediately apparent.

    internal class Program
    {
        enum ParserState
        {
            header_0,
            header_1,
            content_length,
            pixel_width,
            pixel_height,
            content,
            error,
            unknown
        }
        static void Main(string[] args)
        {
            string[] files = new string[] { "1RtT7h3L.data", "EKD3bBZP.data", "bmDwolWU.data", "MBlXyTSp.data", "mCeETXDs.data" };
            int startIndex;
            int contentLengthBits = 0;
            int contentLengthBitsCount = 0;
            int contentLengthBytes = 0;
            int contentIndex = 0;
            int pixelWidth = 0;
            int pixelHeight = 0;
            byte[] contentBytes = null;
            byte currentChar = 0;
            bool textMode = true;
            ParserState parserState = ParserState.unknown;
            foreach (string file in files)
            {
                byte[] content = File.ReadAllBytes(file);
                Console.WriteLine($"File: {file}, Size: {content.Length} bytes");
                startIndex = 0;
                parserState = ParserState.header_0;
                foreach (byte b in content)
                {
                    switch (parserState)
                    {
                        case ParserState.header_0:
                            if ((b & 1) == 0)
                            {
                                textMode = true;
                            }
                            else
                            {
                                textMode = false;
                            }
                            Console.WriteLine($"Header 0: {(textMode ? "text" : "binary")} mode");
                            parserState = ParserState.header_1;
                            break;
                        case ParserState.header_1:
                            Console.WriteLine($"{((b & 1) == 0 ? "" : "in")}valid Header 1");
                            contentLengthBits = 0;
                            parserState = textMode ? ParserState.content_length : ParserState.pixel_width;
                            break;
                        case ParserState.content_length:
                        case ParserState.pixel_width:
                        case ParserState.pixel_height:
                            // get some (16) bits
                            contentLengthBits <<= 1;
                            if ((b & 1) == 1) { contentLengthBits += 1; }
                            if (17 == startIndex)
                            {
                                if (parserState == ParserState.content_length)
                                {
                                    if ((contentLengthBits % 8) == 0)
                                    {
                                        Console.WriteLine($"Message Length: {contentLengthBits} bits");
                                        contentLengthBytes = contentLengthBits / 8;
                                        Console.WriteLine($"Message Length: {contentLengthBytes} bytes");
                                        contentBytes = new byte[contentLengthBytes];
                                        contentIndex = 0;
                                        currentChar = 0;
                                        contentLengthBitsCount = 0;
                                        parserState = ParserState.content;
                                    }
                                    else
                                    {
                                        Console.WriteLine($"Invalid Message Length: {contentLengthBits}");
                                        parserState = ParserState.error;
                                    }
                                }
                                else if (parserState == ParserState.pixel_width)
                                {
                                    pixelWidth = contentLengthBits;
                                    Console.WriteLine($"Image Width: {pixelWidth} pixel");
                                    parserState = ParserState.pixel_height;
                                    contentLengthBits = 0;
                                }
                                else
                                {
                                    Console.WriteLine($"invalid parser state (bit position {startIndex})");
                                    parserState = ParserState.error;
                                }
                            }
                            else if (33 == startIndex)
                            {
                                if (parserState == ParserState.pixel_height)
                                {
                                    pixelHeight = contentLengthBits;
                                    Console.WriteLine($"Image Height: {pixelWidth} pixel");
                                    contentLengthBytes = pixelWidth * pixelWidth;
                                    contentBytes = new byte[contentLengthBytes];
                                    contentIndex = 0;
                                    parserState = ParserState.content;
                                }
                                else
                                {
                                    Console.WriteLine($"invalid parser state (bit position {startIndex})");
                                    parserState = ParserState.error;
                                }
                            }
                            break;
                        case ParserState.content:
                        default:
                            if (textMode)
                            {
                                if (contentLengthBitsCount >= contentLengthBits)
                                {
                                    break;
                                }
                                currentChar <<= 1;
                                if ((b & 1) == 1)
                                {
                                    currentChar |= 1;
                                }
                                contentLengthBitsCount += 1;
                                if (0 == (contentLengthBitsCount % 8))
                                {
                                    contentBytes[contentIndex] = currentChar;
                                    currentChar = 0;
                                    contentIndex++;
                                }
                            }
                            else
                            {
                                // binary mode, just get the content bytes
                                if (contentIndex < contentLengthBytes)
                                {
                                    if ((b & 1) == 1)
                                    {
                                        contentBytes[contentIndex] = 0xFF;
                                    }
                                    else
                                    {
                                        contentBytes[contentIndex] = 0x00;
                                    }
                                    contentIndex += 1;
                                }
                            }
                            break;
                    }
                    startIndex++;
                }
                if ( ParserState.error == parserState)
                {
                    Console.WriteLine($"Error parsing file {file}");
                    continue;
                }
                Console.WriteLine();
                if (textMode)
                {
                    Console.WriteLine($"Message Length: {contentLengthBits} bits, {contentLengthBytes} bytes");
                    Console.WriteLine($"Message: {Encoding.ASCII.GetString(contentBytes)}");
                }
                else
                {
                    Console.WriteLine($"Image Width: {pixelWidth} pixels, Image Height: {pixelHeight} pixels");
                    Console.WriteLine($"Content Length: {contentLengthBytes} bytes");
                    File.WriteAllBytes("Hint.data", contentBytes);
                }
            }
        }
    }

the code to encrypt:

`from matplotlib import *
import io as io

gremmo = "https://images.pexels.com/photos/714258/pexels-photo-714258.jpeg"
my_image_file = io.open(gremmo)

for (i in 1:len(my_image_file)):
    my_image_file[, :, :i] = [00, 00, 01] + i

I really enjoyed this challenge. I started out trying to read the raw binary of the PNG files and was confused why it wasn't working. I then realized I needed to decompress them and found a Ruby gem (chunky_png) to do that part for me.

I turned the code into an executable ruby file that will parse both steps by reading the header. I thought it would be fun to build a tool to encode data or images in the same formats, but haven't had a chance to write it yet. Let me know if there is interest in that. I know there are some online tools already.

Answers to the questions:

1. Three may keep a secret, if two of them are dead.

2. A kite and a string.

#!/usr/bin/env ruby
begin
  require 'chunky_png'
rescue LoadError
  puts 'Unable to load chunky_png.  Try intalling it with: gem install chunky_png'
  exit 1
end

if (args = ARGV).size != 1
  puts "Please provide a file name to decode\n\n"
  exit 1
end
begin
  img = ChunkyPNG::Image.from_file args.first
rescue Errno::ENOENT
  puts "Unable to find a file with that name: #{args.first}\n\n"
  exit 2
end

width = img.width
height = img.height
puts "Image file found with dimensions #{width}x#{height}"

# TODO: Optimize this by just decoding what we need
r = (0...height).map{ |y| (0...width).map {|x| s = (img[x,y]>>8).to_s(2); [-17,-9,-1].map {|n| s[n]|| '0'}.join}.join}.join

header = r[0,2]
puts "Header: #{header}"
case header
when '00'
  puts 'Text mode'
  length_in_bits = r[2..17].to_i(2)
  puts "length in bits: #{length_in_bits}"
  bytes = (length_in_bits / 8.0).ceil
  puts "#{bytes} bytes\nDecoded text:"
  puts (0...bytes).map { |o| r[18+o*8..o*8+7+18].to_i(2).chr }.join
when '10'
  puts 'Binary image mode'
  width = r[2..17].to_i(2)
  height = r[17..33].to_i(2)
  puts "Target image: #{width}x#{height}"
  png = ChunkyPNG::Image.new(width, height, ChunkyPNG::Color::BLACK)
  (0...width).each do |x|
    (0...height).each do |y|
      png[x,y] = ChunkyPNG::Color.rgb(255, 255, 255) if r[y * width + 34 + x] == '1'
    end
  end
  file_name = 'hidden_image.png'
  puts "Saving image as: #{file_name}"
  png.save(file_name)
else
  puts 'Unknown mode, don\'t know what to do.'
  exit 3
end

1. Three may keep a secret, if two of them are dead.
2. Key / Kite

Solution in HTML/JS running in the browser and using canvas to read/write image data (requires accounting for the alpha channel)

Code:

<script>
  function decode(url) {
    const img = new Image()
    img.crossOrigin = 'anonymous'
    img.onload = () => {
      const canvas = document.createElement('canvas')
      canvas.width = img.width
      canvas.height = img.height
      const ctx = canvas.getContext('2d')
      ctx.drawImage(img, 0, 0)
      const data = ctx.getImageData(0, 0, canvas.width, canvas.height).data
      let bin = [...data.filter((b, i) => (i+1) % 4).map(b => b & 1)]
      if (bin[0] == 0) {
        bin = bin.slice(18)
    let out = ''
    while (bin.length)
      out += String.fromCharCode(parseInt(bin.splice(0, 8).join(''), 2))
    console.log(url, out)
      } else {
    bin = bin.slice(2)
    canvas.width = parseInt(bin.splice(0, 16).join(''), 2)
    canvas.height = parseInt(bin.splice(0, 16).join(''), 2)
    const out = new Uint8ClampedArray(canvas.width * canvas.height * 4)
    for (let i = 0; i < out.length; i += 4)
      out[i] = out[i + 1] = out[i + 2] = out[i + 3] = !bin[i / 4] * 128
    ctx.putImageData(new ImageData(out, canvas.width), 0, 0);
    document.body.appendChild(canvas)
      }
    }
    img.src = url
  }
    
  decode('https://i.sstatic.net/1RtT7h3L.png')
  decode('https://i.sstatic.net/EKD3bBZP.png')
  decode('https://i.sstatic.net/bmDwolWU.png')
  decode('https://i.sstatic.net/MBlXyTSp.png')
  decode('https://i.sstatic.net/mCeETXDs.png')
</script>

Run in ediKing online editor

ANS: "Three may keep a secret, if two of them are dead."

This was really fun, I have never worked with images really. Great learning experience, def going to mess around with this some more!

from PIL import Image
import numpy as np

def binary_arr_to_int(arr: list[int]) -> int:
    num = 0
    for idx, val in enumerate(arr[::-1]):
        if val == 1:
            num |= (val << idx)
    return num

def task_01(path: str):
    img = Image.open(path)
    pixels = img.load()
    bits = [channel & 1 for y in range(img.height) for x in range(img.width) for channel in pixels[x, y]]
    
    header  = bits[0:2]
    msg_len = binary_arr_to_int(bits[2:18])
    
    msg_str = "".join([chr(binary_arr_to_int(bits[idx:idx+8]))
                       for idx in range(18, 18 + msg_len, 8)])
    print(msg_str)  

def task_02(path: str):
    img = Image.open(path)
    pixels = img.load()
    bits = [channel & 1 for y in range(img.height) for x in range(img.width) for channel in pixels[x, y]]
    
    header  = bits[0:2]
    img_w = binary_arr_to_int(bits[2:18])
    img_h = binary_arr_to_int(bits[18:34])

    data = np.array([b * 255 for b in bits[34: 34 + img_w * img_h]], 
                    dtype=np.uint8).reshape((img_h, img_w))
    new_img = Image.fromarray(data, mode="L")
    new_img.save("images/output.png")


def main():
    TASK_01_PATH = "images/MBlXyTSp.png"
    TASK_02_PATH = "images/mCeETXDs.png"

    task_01(TASK_01_PATH)
    task_02(TASK_02_PATH)

    return 0

if __name__ == "__main__":
    main()

Script 1: Text Decoder

#!/usr/bin/perl

use strict;
use warnings;

use Image::PNG::Libpng ':all';

my $HEADER_SIZE = 2;
my $LENGTH_SIZE = 16;

my $png = create_read_struct();
open my $if, '<:raw', shift or die $!;
$png->init_io( $if );
$png->read_png;
$if->close;

my @bits;
for my $row ( $png->get_rows->@* ) {
    while ( $row ) {
        my ( $r, $g, $b ) = map { ord } unpack( 'aaa', $row );
        push @bits, $r & 1,
                    $g & 1,
                    $b & 1;
        $row = substr $row, 3;
    }
}

my $header;
$header += shift @bits for 1 .. $HEADER_SIZE;
if ( $header != 0 ) {
    die "invalid header";
}

my $length = 0;
for my $pos ( 1 .. $LENGTH_SIZE ) {
    my $bit = shift @bits;
    my $value = $bit << $LENGTH_SIZE - $pos;
    $length += $value;
}
print "length: $length\n";
print "==========\n";

for ( 1 .. $length / 8 ) {
    my $byte = 0;
    my $pos = 1;
    for my $bit ( splice @bits, 0, 8 ) {
        my $value = $bit << 8 - $pos;
        $byte += $value;
        $pos ++;
    }
    print chr( $byte );
}
print "\n";
print "==========\n";

exit;

Script 2: Image Decoder

#!/usr/bin/perl

use strict;
use warnings;

use Image::PNG::Libpng ':all';
use Image::PNG::Const ':all';

my $HEADER_SIZE = 2;
my $ROWS_SIZE = 16;
my $COLS_SIZE = 16;

my $png = create_read_struct();
open my $if, '<:raw', shift or die $!;
$png->init_io( $if );
$png->read_png;
$if->close;

my @bits;
for my $row ( $png->get_rows->@* ) {
    while ( $row ) {
        my ( $r, $g, $b ) = map { ord } unpack( 'aaa', $row );
        push @bits, $r & 1,
                    $g & 1,
                    $b & 1;
        $row = substr $row, 3;
    }
}

my $header = '';
$header .= shift @bits for 1 .. $HEADER_SIZE;
if ( $header ne '10' ) {
    print "invalid header";
    exit 1;
}

my $rows = 0;
for my $pos ( 1 .. $ROWS_SIZE ) {
    my $bit = shift @bits;
    my $value = $bit << $ROWS_SIZE - $pos;
    $rows += $value;
}
print "rows: $rows\n";

my $cols = 0;
for my $pos ( 1 .. $COLS_SIZE ) {
    my $bit = shift @bits;
    my $value = $bit << $COLS_SIZE - $pos;
    $cols += $value;
}
print "cols: $rows\n";
print "==========\n";

$png = create_write_struct();
open my $of, '>:raw', 'out.png';
$png->init_io( $of );
$png->set_IHDR( {
    'height'     => $rows,
    'width'      => $cols,
    'bit_depth'  => 1,
    'color_type' => PNG_COLOR_TYPE_GRAY,
} );
$png->write_info;

my @rows;
for my $x ( 0 .. $rows - 1 ) {
    my $row = '';
    for my $y ( 0 .. $cols - 1 ) {
        my $idx = $x * $rows + $y;
        my $value = $bits[ $idx ];
        $row .= $value;
    }
    push @rows, pack( 'B*', $row );
}
$png->write_image( \@rows );
$png->write_end;

exit;

Answer 1: "Three may keep a secret, if two of them are dead." Benjamin Franklin
Answer 2: A key (and a kite).

At first I tried to do the image decoder by having something like if ( $bit ) print "X" else print " ", opening it in a text editor, and zooming out to create hi-res ASCII art. And this almost worked, I could tell what the image was but couldn't read the text. Otherwise libpng made this pretty simple. Took a couple tries to get the binary row format down.

Thank you for your challenge. It is insteresting.

Answer

1. What is the hidden quote?

The hidden quote is "... if two of them are dead." So the complete sentence is "Three may keep a secret, if two of them are dead."

2. Which object is on the line? Note, there are two possible correct answers here.

There is a key and a kite on the line.

My code

My solution using rust and image = "0.25.10" library.

This is my main code.

use image::{GrayImage, ImageBuffer, ImageReader};
use std::fs;
use std::path::Path;

fn get_image_bytes(image_path: &Path) -> Result<Vec<u8>, Box<dyn std::error::Error>> {
    let message_black_bytes = fs::read(&image_path)?;
    println!(
        "Sign: {:?} {:?}",
        &message_black_bytes[0],
        std::str::from_utf8(&message_black_bytes[1..8])?
    );

    let img = ImageReader::open(&image_path)?.decode()?;
    let img_buf = img.to_rgb8();
    let img_raw = img_buf.into_raw();
    Ok(img_raw)
}

fn decode_first_image(image_path: &Path) -> Result<(), Box<dyn std::error::Error>> {
    let img_raw = get_image_bytes(&image_path)?;
    let mut offset = 2;
    let len_bytes = &img_raw[offset..offset + 16];
    let mut len: u16 = 0;
    for byte in len_bytes {
        let last_bit = byte & 0x01;
        len = (len << 1) | last_bit as u16;
    }
    println!("Length: {}", len);
    offset += 16;
    let mut total_str = String::new();
    let mut current_byte: u8 = 0;
    let mut current_bit: u8 = 0;
    for byte in &img_raw[offset..offset + len as usize] {
        let last_bit = (*byte & 0x01) as u8;
        current_byte = (current_byte << 1) | last_bit;
        current_bit += 1;
        if current_bit == 8 {
            total_str.push(current_byte as char);
            current_byte = 0;
            current_bit = 0;
        }
    }
    println!("Message: {}", total_str);
    Ok(())
}

fn decode_second_image(image_path: &Path) -> Result<(), Box<dyn std::error::Error>> {
    let img_raw = get_image_bytes(&image_path)?;
    println!("Head: {:?}, {:?}", &img_raw[0] & 0x01, &img_raw[1] & 0x01);
    let mut offset = 2;
    let mut width_u16: u16 = 0;
    for byte in &img_raw[offset..offset + 16] {
        let last_bit = *byte & 0x01;
        width_u16 = (width_u16 << 1) | last_bit as u16;
    }
    println!("Width: {}", width_u16);
    offset += 16;
    let mut height_u16: u16 = 0;
    for byte in &img_raw[offset..offset + 16] {
        let last_bit = *byte & 0x01;
        height_u16 = (height_u16 << 1) | last_bit as u16;
    }
    println!("Height: {}", height_u16);
    offset += 16;
    let total_pixels = (width_u16 as usize)
        .checked_mul(height_u16 as usize)
        .expect("Overflow");
    let mut pixels = Vec::with_capacity(total_pixels);
    for byte in &img_raw[offset..offset + total_pixels] {
        match byte & 0x01 {
            1 => pixels.push(255),
            0 => pixels.push(0),
            _ => panic!("Invalid pixel value"),
        }
    }
    let img: GrayImage =
        ImageBuffer::from_raw(width_u16 as u32, height_u16 as u32, pixels).unwrap();
    img.save(image_path.parent().unwrap().join("butterfly_decoded.png"))?;
    Ok(())
}

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let project_root_dir = Path::new(env!("CARGO_MANIFEST_DIR")).canonicalize()?;
    println!("Project root directory: {}", project_root_dir.display());
    let data_dir = project_root_dir.join("data");
    println!("Data directory: {}", data_dir.display());
    let image_path = data_dir.join("challenge_18_hidden_in_plain_sight/message_cat.png");
    decode_first_image(&image_path)?;
    let second_image_path =
        data_dir.join("challenge_18_hidden_in_plain_sight/message_butterfly.png");
    decode_second_image(&second_image_path)?;
    Ok(())
}

My project structure:

❯ tree --gitignore
.
├── Cargo.lock
├── Cargo.toml
├── data
│   └── challenge_18_hidden_in_plain_sight
│       ├── butterfly_decoded.png
│       ├── message_butterfly.png
│       ├── message_cat.png
│       ├── stamp_black.png
│       ├── stamp_contrast.png
│       └── stamp_natural.png
└── src
    ├── bin
    │   └── challenge_18_hidden_in_plain_sight.rs
    └── main.rs

What is the hidden quote?

"Three may keep a secret, if two of them are dead."

Which object is on the line?

Probably the Key

https://postimg.cc/YGbnLCFt

C# Code

ImageProcessing

internal static class ImageProcessing
{
    public static IReadOnlyList<bool> GetBits(Bitmap image)
    {
        var bits = new List<bool>();

        // row scan
        for (int y = 0; y < image.Height; y++)
        {
            for (int x = 0; x < image.Width; x++)
            {
                var pixel = image.GetPixel(x, y);
                bits.Add((pixel.R & 1) != 0);
                bits.Add((pixel.G & 1) != 0);
                bits.Add((pixel.B & 1) != 0);
            }
        }

        return bits;
    }

    public static Bitmap GetImage(IEnumerable<bool> bits, int width, int height)
    {
        var image = new Bitmap(width, height);
        var queue = new Queue<bool>(bits);

        for (int y = 0; y < height; y++)
        {
            for (int x = 0; x < width; x++)
            {
                var pixel = queue.Dequeue() ? 255 : 0;
                image.SetPixel(x, y, Color.FromArgb(pixel, pixel, pixel));
            }
        }

        return image;
    }
}

DeSerialization

internal static class DeSerializer
{
    public static string BitsToText(IReadOnlyList<bool> bits)
    {
        var length = bits
            .Skip(2)
            .GetBytes(2)
            .GetUshort();

        var bytes = bits
            .Skip(2 + 16) // skip header
            .GetBytes(length);

        return Encoding.ASCII.GetString(bytes);
    }

    public static Bitmap BitsToImage(IReadOnlyList<bool> bits)
    {
        var width = bits
            .Skip(2)
            .GetBytes(2)
            .GetUshort();

        var height = bits
            .Skip(2 + 16)
            .GetBytes(2)
            .GetUshort();

        return ImageProcessing.GetImage(bits.Skip(2 + 16 + 16), width, height);
    }

    private static byte[] GetBytes(this IEnumerable<bool> bits, int length)
    {
        return bits
        .Take(length * 8)
        .Chunk(8)
        .Select(values =>
        {
            return (byte)values
            .Reverse() // MSB is first, reverse to LSB first
            .Select((bit, index) => bit ? (int)Math.Pow(2, index) : 0)
            .Sum();
        })
        .ToArray();
    }

    private static int GetUshort(this byte[] bytes)
    {
        return bytes
            .Reverse() // MSByte is first, revrse for LSByte first
            .Select((value, index) => value * (int)Math.Pow(2, index * 8))
            .Sum();
    }
}

The quote is: "Three may keep a secret, if two of them are dead" - Benjamin Franklin. The object(s) on the line are a kite and a key.

I used C++ for this challenge and my approach is as follows:

• Read the image
  • The reader I used automatically flattens the image array
• Get the least significant bit of each colour channel
  • Simply n & 1 does this nicely
• Read the header
  • Check the first two bits are equivalent to the expected header
  • Convert 16 or 16*2 bits into integers in big endian format for the message length (task 1) and image dimensions (task 2)
  • Store the length of the header as an offset
• For task 1:
  • Convert each group of 8 bits into a character by casting them to char
• For task 2:
  • Multiply the first (width*height)+offset bits by 255 to scale from [0,1] to [0,255]
  • Save those first width*height least significant bits after the header offset as an image

The image reader and writer I used were copied from here:

• Reader: https://github.com/nothings/stb/blob/master/stb_image.h
• Writer: https://github.com/nothings/stb/blob/master/stb_image_write.h These files just need to be placed in the same directory as the code.

My program was tested on Ubuntu20.04 but there shouldn't be anything in it preventing it from running on other operating systems Compilation is simply done (I used g++ 9.4): g++ -o steg steg.cpp And can be run with ./steg

My code is here:

#include <stdio.h>
#include <iostream>
#include <string>
#include <array>

#define STB_IMAGE_IMPLEMENTATION
// Copied from https://github.com/nothings/stb/blob/master/stb_image.h
#include "stb_image.h"
#define STB_IMAGE_WRITE_IMPLEMENTATION
// Copied from https://github.com/nothings/stb/blob/master/stb_image_write.h
#include "stb_image_write.h"


/// @brief Convert from an array of binary numbers to an integer
/// @param lsb The array of numbers
/// @param start The start index of the array to convert from (inclusive)
/// @param end The end index of the array to convert till (exclusive)
/// @return An integer
int binary_to_int(uint8_t* lsb, int start, int end){
    int tot = 0;

    int shift = 0;
    for(int ii=end-1; ii >= start; ii--){  // Read as big endian
        tot += (int)lsb[ii] << shift++; 
    }

    return tot;
}

/// @brief Convert from a binary array to a string of ascii characters
/// @param lsb The binary array
/// @param start The index to start converting from (inclusive)
/// @param end The index to end converting at (exclusive)
/// @return A std::string
std::string binary_to_ascii(uint8_t* lsb, int start, int end){
    std::string result = "";

    int cnt = 0;
    for(int ii=start; ii < end; ii+=8){  // Read in blocks of 8 bits
        int ascii_index = binary_to_int(lsb, ii, ii + 8);
        result += static_cast<char>(ascii_index);  // Casting int to char results in the ascii character
    }

    return result;
}

/// @brief Gets the least significant bits (lsb) of an array
/// @param im The image array to convert from
/// @param total_len The total length of the image array
/// @return The least significant bits of im
uint8_t* get_lsb(uint8_t* im, int total_len){
    uint8_t* result = (uint8_t*) malloc(total_len * sizeof(im));  // Allocate the memory needed for the lsb

    for(int ii=0; ii < total_len; ii++){
        result[ii] = im[ii] & 1;  // We are only interested in the least significant bit
    }

    return result;
}

/// @brief Read the header of the lsb
/// @tparam num_header_datas The number of header data items (not including the check bits)
/// @param lsb The lsb array
/// @param check_bits The check bits
/// @param header_data_lengths_bits The lengths of the header data items in bits
/// @param header_datas (output). The resulting header data items
/// @param offset (output). The total header length.
/// @return 0 if the reading was a success, 1 otherwise.
template<size_t num_header_datas>
int read_header(uint8_t* lsb, std::array<int, 2> check_bits, std::array<int, num_header_datas> header_data_lengths_bits, std::array<int, num_header_datas>& header_datas, int& offset){

    int check_bits_len = check_bits.size();

    // Read header
    for(int ii=0; ii < check_bits_len; ii++){
        if(check_bits[ii] != lsb[ii])  // If the expected check bits and the actual check bits are different return an error
            return 1;
    }

    offset = check_bits_len;

    for (int ii=0; ii < header_data_lengths_bits.size(); ii++){
        int l = header_data_lengths_bits[ii];
        header_datas[ii] = binary_to_int(lsb, offset, offset + l);  // Convert the binary string to a number
        offset += l;
    }

    return 0;
}

/// @brief Convert the least significant bits to an ascii string
/// @param lsb The lsb array
/// @param offset The header offset
/// @param length The length (in bits) of the string to convert
/// @return Returns the resulting string of length: floor(length / 8)
std::string lsb_to_ascii(uint8_t* lsb, int offset, int length){
    return binary_to_ascii(lsb, offset, offset + length);
}

/// @brief Decode the image into the encoded message
/// @tparam num_header_datas The number of header data items (not including the check bits)
/// @param filename The filename of the image to decode
/// @param check_bits The check bits at the start of the message
/// @param header_data_lengths_bits The lengths of any header data in the message
/// @return 0 if the decoding was a success. 1 otherwise
template<size_t num_header_datas>
int decode_image(std::string filename, std::array<int, 2> check_bits, std::array<int, num_header_datas> header_data_lengths_bits){
    int width, height, num_channels;
    int status = 0;

    uint8_t* rgb_image = stbi_load(filename.c_str(), &width, &height, &num_channels, 3);  // Load the image. Length = width*height*num_channels

    if(rgb_image == NULL){
        std::cerr << "Failed to read image" << std::endl;
        return 1;
    }

    int total_img_len = width*height*num_channels;

    uint8_t* lsb = get_lsb(rgb_image, total_img_len);  // Get the least significant bits for every color channel

    std::array<int, header_data_lengths_bits.size()> header_datas;
    int offset;
    status |= read_header<header_data_lengths_bits.size()>(lsb, check_bits, header_data_lengths_bits, header_datas, offset);  // Read the header with the data stored in header_datas and the offset in offset

    if(status != 0){
        std::cerr << "Failed reading header" << std::endl;
        return status;
    }

    if(header_datas.size() == 1){  // If there is only a string to read
        std::string result = lsb_to_ascii(lsb, offset, header_datas[0]);  // Convert the bit string to ascii
        std::cout << result << std::endl;
    }
    else if(header_datas.size() == 2){  // If there is a sub-image to read
        int w = header_datas[0];
        int h = header_datas[1];

        for(int ii=offset; ii < w * h + offset; ii++){  // Multiply the resulting image bits by 255 to map from [0,1] to [0,255]
            lsb[ii] *= 255;
        }

        stbi_write_png("out.png", w, h, 1, &lsb[offset], w);  // Save the resulting image
    }
    else{
        std::cerr << "Number of header datas not supported" << std::endl;
        status = 1;
    }

    stbi_image_free(rgb_image);  // Free the image memory

    return status;
}

int main() {

    int status = 0;

    {
        std::string filename = "task1.png";
        std::array<int, 2> check_bits = {0,0};
        std::array<int, 1> header_data_lengths_bits = {16};

        status |= decode_image<header_data_lengths_bits.size()>(filename, check_bits, header_data_lengths_bits);
    }

    {
        std::string filename = "task2.png";
        std::array<int, 2> check_bits = {1,0};
        std::array<int, 2> header_data_lengths_bits = {16, 16};
        
        status |= decode_image<header_data_lengths_bits.size()>(filename, check_bits, header_data_lengths_bits);
    }

    return status;
}

I rarely use C/C++ so if there's anything that I missed that would have made my life easier, or any "interesting" choices I've made any feedback is appreciated.

"Three may keep a secret, if two of them are dead - Benjamin Franklin"

• On a line between earth and sky Dr. Franklin holds the key to lightning.

That was fun, altough it felt more like following a university practical work. It's a very well made challenge.

Here's my solution in python (with many thanks to old basic Stack Overflow threads with answers I never seem to remember):

# ------------------
# Imports
from PIL import Image
import numpy as np
import matplotlib.pyplot as plt


# ------------------
# Function
def decode_lsb(path):
    # Extract last bit of every pixel channel
    img = np.asarray(Image.open(path))
    bits = ''.join(str(b & 1) for b in img.flatten()) # Adapted from Mayank Shukla. Source - https://stackoverflow.com/a/41501246/30289489

    header = bits[:2]

    if header == '00': # Hidden text
        msg_length = int(bits[2:18], 2)

        # First 2+16 bits are for header and message length
        msg_bits = bits[18:18 + msg_length]
        message = ''.join(
            chr(int(msg_bits[i:i+8], 2)) # https://stackoverflow.com/q/57845175/30289489
            for i in range(0, msg_length, 8)
        ) # Adapted from mhawke. Source - https://stackoverflow.com/a/40559005

        print("Hidden message:")
        print(message)

    elif header == '10': # Hidden binary image
        width = int(bits[2:18], 2)
        height = int(bits[18:34], 2)

        print(f"Hidden image size: {width} x {height}")

        # First 2+16+16 bits are for header, width and height
        pixel_bits = bits[34:34 + width * height] # https://stackoverflow.com/q/57845175/30289489

        image = np.array(
            [int(b) for b in pixel_bits],
            dtype=np.uint8
        ).reshape(height, width)

        plt.imshow(image, cmap='gray')
        plt.axis('off')
        plt.show()

    else:
        print(f"Unknown {header}")


# ------------------
# Run decoding
decode_lsb('./cat.png')
decode_lsb('./butterfly.png')

My answer is probably going to be very standard, I use bit & 1 to get the last bit of digits without having to explicitly convert them to binary. It is then only a matter of rearranging them and converting back to ASCII characters. I must say, numpy and PIL make this challenge very easy by converting png files to arrays for us. Using matplotlib also allows us to skip the remapping 0->0, 1-> 255 when displaying the image.

Edits: Finished my sentences and removed mapping after realizing it's not necessary.

First time attending StackOverflow Challenge, not sure how exactly should I do so I'll submit in my way of a casual course lab report. Also I write all of the code as a one-off thing without any quality consideration so don't expect too much.

Task 0: Test your decoder

Information given in the Background section:

• Data is hidden in the LSB of each pixel's RGB values, bit by bit

• Data is MSB aligned (MSB in first pixel's R, second MSB in first pixel's G, etc.)

• Pixels may not align with byte boundaries, bits not up to a byte can be discarded

• First 2 + 16 bits are metadata

Implement the decoder to test it:

using System.Drawing;
using System.Text;

namespace SOCStegano
{
    internal class Program
    {
        static int GetTotalBits(Bitmap img) => img.Width * img.Height * 3;

        static bool GetBit(Bitmap img, int bitIdx)
        {
            if(bitIdx < 0 || bitIdx >= GetTotalBits(img))
                throw new ArgumentOutOfRangeException(nameof(bitIdx));

            var pixelIdx = bitIdx / 3;
            var pixelChanIdx = 2 - (bitIdx % 3);  // MSB first
            var pixel = img.GetPixel(pixelIdx % img.Width, pixelIdx / img.Width);
            return ((pixel.ToArgb() >> (pixelChanIdx * 8)) & 0x01) > 0;
        }

        static byte[] GetPayload(Bitmap img)
        {
            var payloadLenBytes = (GetTotalBits(img) - (2 + 16)) / 8;
            var ret = new byte[payloadLenBytes];
            for(int i = 0; i < payloadLenBytes * 8; ++i)
            {
                var retIdxBytes = i / 8;
                var retIdxBits = 7 - (i % 8);  // MSB first
                if (GetBit(img, 2 + 16 + i))
                {
                    ret[retIdxBytes] |= (byte)(1 << retIdxBits);
                }
            }
            return ret;
        }

        static void Main(string[] args)
        {
            var img = Image.FromFile("1RtT7h3L.png") as Bitmap;
            var payload = GetPayload(img);
            var payloadStr = Encoding.ASCII.GetString(payload);
        }
    }
}

Result:

Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test 

Task 1: Decode a simple text message

New information given:

• First 2 bits are header and should be zero, then 16 bits are the payload length in bits, then continuous payload bits

• Payload is ASCII text

Adapt the GetPayload function to check the header and read the payload length:

        static byte[] GetPayload(Bitmap img)
        {
            // Check header
            if (GetBit(img, 0) || GetBit(img, 1))
                throw new InvalidDataException("Invalid header");

            // Get length
            var payloadLenBits = 0;
            for (int i = 0; i < 16; ++i)
            {
                if (GetBit(img, 2 + i))
                {
                    var lenIdxBits = 15 - i;  // MSB first
                    payloadLenBits |= (1 << lenIdxBits);
                }
            }

            // Get payload
            var payload = new byte[payloadLenBits / 8];
            for(int i = 0; i < payloadLenBits; ++i)
            {
                var payloadIdxBytes = i / 8;
                var payloadIdxBits = 7 - (i % 8);  // MSB first
                if (GetBit(img, 2 + 16 + i))
                {
                    payload[payloadIdxBytes] |= (byte)(1 << payloadIdxBits);
                }
            }

            return payload;
        }

Result:

The first part of the sentence is "Three may keep a secret, ...".

### Task 2: Decode a binary image

A binary image is hidden in the least significant bits of the butterfly image, the encoding scheme is:

- Simple LSB Encoding**
- Header: `[1, 0]`
- Next 16 bits: image `width` in pixels
- Next 16 bits: image `height` in pixels
- Raw pixels of the binary image

Hint: Create and fill an image array of the derived `width` and `height` with the encoded hidden pixels.
In order to view your image in classic viewers, it might be helpful to map 0 -> 0 and 1 -> 255.
Derive the second part of the sentence and answer the question about the image.

Task 2: Decode a binary image

New information given:

• First two bytes are now one and zero, then 16 bits for width, 16 bits for height, then payload of a binarized image

Write a new function to read the image:

        static Bitmap GetImagePayload(Bitmap img)
        {
            // Check header
            if (!GetBit(img, 0) || GetBit(img, 1))
                throw new InvalidDataException("Invalid header");

            // Get width and height
            var widthAndHeight = 0;
            for (int i = 0; i < 32; ++i)
            {
                if (GetBit(img, 2 + i))
                {
                    var lenIdxBits = 15 - i;  // MSB first
                    widthAndHeight |= (1 << lenIdxBits);
                }
            }
            var width = (widthAndHeight >> 16) & 0xFFFF;
            var height = widthAndHeight & 0xFFFF;

            // Get payload
            var payload = new Bitmap(width, height);
            for (int i = 0; i < width * height; ++i)
            {
                var payloadPixelY = i / width;
                var payloadPixelX = i % width;
                payload.SetPixel(payloadPixelX, payloadPixelY,
                    GetBit(img, 2 + 32 + i) ? Color.White : Color.Black);
            }

            return payload;
        }

        static void Main(string[] args)
        {
            var img = Image.FromFile("mCeETXDs.png") as Bitmap;
            GetImagePayload(img).Save("q2.png", ImageFormat.Png);
        }

Result:

(Images are not allowed)

Answer

1. Three may keep a secret, if two of them are dead. - Benjamin Franklin

2. A key.

I extracted the least significant bit (LSB) from each RGB channel of every pixel to reconstruct a bitstream.

For Task 1, the first 2 bits are a header, followed by 16 bits indicating the message length. I then grouped the remaining bits into bytes (8 bits) and converted them to ASCII.

For Task 2, the header changes: after the first 2 bits, the next 16 bits represent the image width and the following 16 bits represent the height. The remaining bits form a binary image, which I reconstructed and displayed.

from PIL import Image

def to_num(b):
    n = 0
    for x in b:
        n = n*2 + (x == "1")
    return n

def decode(path):
    img = Image.open(path).convert("RGB")
    bits = ""

    for px in img.getdata():
        for c in px:
            bits += str(c & 1)

    return bits

def get_msg(bits):
    out = ""
    for i in range(0, len(bits), 8):
        out += chr(to_num(bits[i:i+8]))
    return out


def task1():
    s = decode("img1.png")
    n = to_num(s[2:18])
    print(get_msg(s[18:18+n]))


def task2():
    s = decode("img2.png")

    w = to_num(s[2:18])
    h = to_num(s[18:34])
    s = s[34:34+w*h]

    img = Image.new("RGB", (w, h))
    px = img.load()

    i = 0
    for y in range(h):
        for x in range(w):
            v = 255 if s[i] == "1" else 0
            px[x, y] = (v, v, v)
            i += 1

    img.show()


task1()
task2()

1. "Three may keep a secret, if two of them are dead."

2. A key and a kite

I already completed the tasks in bash but was surprised to see no JavaScript submissions.
Now I know why...

There is no easy way to read the PNG image-data unaltered in JavaScript, and since we are looking at single bits small errors get big quick. I was super confused and when googling I didn't find anyone else with this issue. Even ChatGPT told me I was wrong and that I had a bug somewhere in my code (though it couldn't point out where (since it wasn't in my code)). Lastly I found a github repo made by someone with the same issue as me, but instead of copying it I decided to read the PNG specification and learn something new :)

Code:

png_reader.js

function getUncompressedPNG(dataBuffer) {
    let UintArr = new Uint8ClampedArray(dataBuffer)

    // Check if PNG signature exists
    if (JSON.stringify(Array(...UintArr.slice(0, 8))) != '[137,80,78,71,13,10,26,10]') {
        console.error("PNG header is not present, malformed or wrong data");
        return;
    }

    UintArr = UintArr.slice(8); // Remove header bytes

    // Parse chunks
    let width, height, chunkLength, chunkType, chunkData, CRC, longBin = '', compressedData = [];
    while (true) {
        chunkLength = parseInt(Array(...UintArr.slice(0, 4)).map(x => x.toString(16).padStart(2, "0")).join(""), 16);
        chunkType = Array(...UintArr.slice(4, 8)).map(b => String.fromCharCode(b)).join("");
        chunkData = UintArr.slice(8, 8 + chunkLength);

        // I Don't use CRC in my code, just added this so people know why I slice on 12+length
        CRC = UintArr.slice(8 + chunkLength, 12 + chunkLength);

        UintArr = UintArr.slice(12 + chunkLength);
        // I only implemented the chunks present in the task images
        switch (chunkType) {
            case "IHDR":
                width = parseInt(Array(...chunkData.slice(0, 4)).map(x => x.toString(16).padStart(2, "0")).join(""), 16)
                height = parseInt(Array(...chunkData.slice(4, 8)).map(x => x.toString(16).padStart(2, "0")).join(""), 16)
                break;
            case "IDAT":
                compressedData.push(...chunkData);
                break;
            case "IEND":
                return {
                    height,
                    width,
                    data: pako.inflate(compressedData),
                }
        }
    }
}

let p, pa, pb, pc;
function paethPredictor(a, b, c) {
    p = a + b - c;
    pa = Math.abs(p - a);
    pb = Math.abs(p - b);
    pc = Math.abs(p - c);

    if (pa <= pb && pa <= pc) {
        return a;
    }
    
    if (pb <= pc) {
        return b;
    }

    return c;
}

function pngReader(dataBuffer) {
    const { width, height, data } = getUncompressedPNG(dataBuffer);

    const scanLines = [];

    // Loop through each filtered scanline
    let filteredLine, tempLine;
    for (let i = 0; i < height; i++) {
        filteredLine = Array(...data.slice(1 + i + (i * width * 3), (i+1) * width * 3 + 1 + i));
        switch(data[i + (i * width * 3)]) { // First byte in line determines filtertype
            case 0: // None
                scanLines.push(filteredLine);
                break;
            case 1: // Sub
                tempLine = [filteredLine[0], filteredLine[1], filteredLine[2]];
                for (let j = 3; j < width * 3; j++) {
                    tempLine.push((filteredLine[j] + tempLine[j - 3]) % 256);
                }
                scanLines.push(tempLine);
                break;
            case 2: // Up
                tempLine = [];
                for (let j = 0; j < width * 3; j++) {
                    tempLine.push((filteredLine[j] + scanLines[i - 1][j]) % 256);
                }
                scanLines.push(tempLine);
                break;
            case 3: // Avg
                console.error("Filtertype 3 'average' not implemented:");
                break;
            case 4: // Paeth
                tempLine = [];
                let raw;
                for (let j = 0; j < width * 3; j++) {

                    if (j - 3 >= 0 && i >= 1) {
                        raw = filteredLine[j] + paethPredictor(tempLine[j - 3], scanLines[i - 1][j], scanLines[i - 1][j - 3]);
                    } else if (j - 3 >= 0) {
                        raw = filteredLine[j] + paethPredictor(tempLine[j - 3], 0, 0);
                    } else if (i >= 1) {
                        raw = filteredLine[j] + paethPredictor(0, scanLines[i - 1][j], 0);
                    } else {
                        raw = filteredLine[j];
                    }
                    tempLine.push(raw % 256) 
                }
                scanLines.push(tempLine);
                break;
            default:
                console.error("Unknown filter type:", data[i + (i * width * 3)])
        }
    }

    return new Uint8Array(scanLines.flat())
}

index.html

<!-- zlib inflate from https://raw.githubusercontent.com/nodeca/pako/refs/heads/master/dist/pako_inflate.min.js -->
<script src="pako_inflate.min.js"></script>

<script src="png_reader.js"></script>
<script defer>
    function extractText(d, header) {
        const headerIndex = d.findIndex((value, index, arr) => {return (arr[index] & 1) == header[0] && (arr[index + 1] & 1) == header[1]});
        let data = d.slice(headerIndex + header.length);

        let outputString = '';
        const contentLength = parseInt(data.slice(0, 16).map(x => (x & 1)).join(""), 2)

        const longBin = data.slice(16, contentLength + 16).map(x => x & 1).join("")
        longBin.match(/.{1,8}/g).map(x => parseInt(x, 2)).forEach(charCode => {
            outputString += String.fromCharCode(charCode)
        });

        return outputString;
    }

    function printImage(ctx, d, header) {
        const headerIndex = d.findIndex((value, index, arr) => {return (arr[index] & 1) == header[0] && (arr[index + 1] & 1) == header[1]});
        let data = d.slice(headerIndex + header.length);

        const width = parseInt(data.slice(0, 16).map(x => (x & 1)).join(""), 2);
        const height = parseInt(data.slice(16, 32).map(x => x & 1).join(""), 2);
        ctx.canvas.width = width;
        ctx.canvas.height = height;
        ctx.fillStyle = "rgb(30, 30, 30)";

        data = data.slice(32);
        for (let i = 0; i < width * height; i++) {
            if ((data[i] & 1) != 1) {
                ctx.fillRect(i % width, Math.floor(i / height), 1, 1);
            }
        }

    }

    function openFile(event) {
        const file = event.target.files[0];
        const reader = new FileReader();

        reader.onload = function(e) {
            const isImage = document.querySelector('input#is-image-checkbox').checked;
            if (!isImage) {
                document.querySelector('pre#text-output').textContent = extractText(pngReader(e.target.result), [0, 0]);
            } else {
                const canvas = document.querySelector("canvas#image-output");
                const ctx = canvas.getContext("2d");

                printImage(ctx, pngReader(e.target.result), [1, 0])
            }
        }
        reader.readAsArrayBuffer(file);
    }
</script>
<body>
    <label for="is-image">decode image:</label>
    <input type="checkbox" name="is-image" id="is-image-checkbox">
    <br>
    <input type='file' accept='image/*' onchange='openFile(event)'><br>
    <pre id="text-output"></pre>
    <canvas id="image-output"></canvas>
</body>

1. "Three may keep a secret, if two of them are dead." -Benjamin Franklin

2. The object on the line is a key/the kite (at the end of the line).

I used the PIL library in Python.

I named the three stamp-size images test1.png, test2.png and test3.png, and I named the image of the cat and the image of the butterfly img1.png and img2.png respectively.

from PIL import Image

def to_8_binary(num):
    b = ""
    start = 2**7
    while len(b) < 8:
        if num >= start:
            b += "1"
            num -= start
        else:
            b += "0"
        start //= 2
    return b

def to_num(binary):
    num_bits = len(binary)
    start = 2**(num_bits-1)
    c = 0
    for b in binary:
        if b == "1":
            c += start
        start //= 2
    return c

def to_ascii(binary):
    return chr(to_num(binary))

def decode(img_path):
    img = Image.open(img_path)
    img = img.convert("RGB")
    width, height = img.size
    pixels = img.load()

    s = ""

    for y in range(height):
        for x in range(width):
            for i in pixels[x, y]:
                s += to_8_binary(i)[-1]
                # least significant bit

    return s

def get_message(s):
    return "".join([to_ascii(s[i:i+8]) for i in range(0,len(s),8)])

def task0():
    for i in [1,2,3]:
        s = decode(f"test{i}.png")[18:]
        print(get_message(s))

def task1():
    s = decode("img1.png")

    length = to_num(s[2:18])
    s = s[18:18+length]

    print(get_message(s))

def task2():
    s = decode("img2.png")

    width = to_num(s[2:18])
    height = to_num(s[18:34])
    s = s[34:34+width*height]

    rgbs = [(0, 0, 0) if i == "0" else (255, 255, 255) for i in s]

    output = Image.new('RGB', [width, height])
    pixels = output.load()

    i = 0
    for y in range(height):
        for x in range(width):
            pixels[x, y] = rgbs[i]
            i += 1

    output.show()


if __name__ == '__main__':
    task0()

    task1()
    """The first part of the sentence is "Three may keep a secret, ...".
    
    ### Task 2: Decode a binary image
    
    A binary image is hidden in the least significant bits of the butterfly image, the encoding scheme is:
    
    - Simple LSB Encoding**
    - Header: `[1, 0]`
    - Next 16 bits: image `width` in pixels
    - Next 16 bits: image `height` in pixels
    - Raw pixels of the binary image
    
    Hint: Create and fill an image array of the derived `width` and `height` with the encoded hidden pixels.
    In order to view your image in classic viewers, it might be helpful to map 0 -> 0 and 1 -> 255.
    Derive the second part of the sentence and answer the question about the image."""

    task2()
    """...if two of them are dead. -Benjamin Franklin"""
    """Object on the line: a key/kite"""

In trying out this challenge, the first mental roadblock was my unfamiliarity with PNG files and their format. As a first step, I just viewed the raw data within the file to ascertain the type of data in the "IDAT" chunk. This led me to send a feedback question as it seemed the data chunk seemed too small to hold the test message in the stamp sized files. A feedback answer alerted me to the obvious fact that the data chunk contained compressed data. Also, from what I was seeing in the feedback was that solutions seemed to tilt towards a Python programming solution. However, I still wanted to pursue a "C" program solution, so searching the stack overflow site, I found an answer to a scenario that fit for compressing and decompressing PNG file data. Following is the link - "https://stackoverflow.com/questions/1362945/how-to-decode-a-png-image-to-raw-bytes-from-c-code-with-libpng"

That information pointed me to the "libpng" library and its assortment of functions. Using that as an initial basis, I was able to discern the structure of the pixels and thus find the LSB values I was needing to construct an array of ones and zeros and subsequently parse the array to produce ASCII characters and text.

Following, it the initial decoder program.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <png.h>

#define SIZE 256000

png_bytep *row_pointers;
unsigned int width;
unsigned int height;

static void read_png_file(char *filename)
{
    FILE *fp = fopen(filename, "rb");
    png_byte bit_depth, color_type;

    png_structp png = png_create_read_struct(PNG_LIBPNG_VER_STRING, NULL, NULL, NULL);

    if (!png)
        abort();
    png_infop info = png_create_info_struct(png);

    if (!info)
        abort();

    if (setjmp(png_jmpbuf(png)))
        abort();

    png_init_io(png, fp);
    png_read_info(png, info);
    width  = png_get_image_width(png, info);
    height = png_get_image_height(png, info);
    color_type = png_get_color_type(png, info);
    bit_depth  = png_get_bit_depth(png, info);

    if (bit_depth == 16)                                        /* Read any color_type into 8bit depth, RGBA format. */
        png_set_strip_16(png);

    if (color_type == PNG_COLOR_TYPE_PALETTE)
        png_set_palette_to_rgb(png);

    if (color_type == PNG_COLOR_TYPE_GRAY && bit_depth < 8)     /* PNG_COLOR_TYPE_GRAY_ALPHA is always 8 or 16bit depth. */
        png_set_expand_gray_1_2_4_to_8(png);

    if (png_get_valid(png, info, PNG_INFO_tRNS))
        png_set_tRNS_to_alpha(png);

    /* These color_type don't have an alpha channel then fill it with 0xff. */
    if (color_type == PNG_COLOR_TYPE_RGB || color_type == PNG_COLOR_TYPE_GRAY || color_type == PNG_COLOR_TYPE_PALETTE)
        png_set_filler(png, 0xFF, PNG_FILLER_AFTER);

    if (color_type == PNG_COLOR_TYPE_GRAY || color_type == PNG_COLOR_TYPE_GRAY_ALPHA)
        png_set_gray_to_rgb(png);

    png_read_update_info(png, info);

    row_pointers = (png_bytep*)malloc(sizeof(png_bytep) * height);

    for (int y = 0; y < height; y++)
    {
        row_pointers[y] = (png_byte*)malloc(png_get_rowbytes(png,info));
    }

    png_read_image(png, row_pointers);

    fclose(fp);
}

static void process_png()
{
    int idx = 0;
    unsigned int w[SIZE];
    char chr;
    for (unsigned int y = 0; y < height; y++)
    {
        png_bytep row = row_pointers[y];

        /* Ascertain LSB from the RGB channels - disregard the A channel    */

        for (unsigned int x = 0; x < width; x++)
        {
            png_bytep px = &(row[x * 4]);
            //printf("%d%d%d", px[0] % 2, px[1] % 2, px[2] % 2);
            //printf("%5d, %5d = RGBA(%3d, %3d, %3d, %3d)  index: %d\n", y, x, px[0], px[1], px[2], px[3], idx);
            w[idx + 0] = px[0] % 2;
            w[idx + 1] = px[1] % 2;
            w[idx + 2] = px[2] % 2;
            idx += 3;

            if (idx > SIZE)
                break;
        }

        if (idx > SIZE)
            break;
    }

    printf("Header byte values: ");

    for (int i = 2; i < 18; i++)
        printf("%d", w[i]);

    printf("\n");

    idx = w[4] * 8192 + w[5] * 4096 + w[6] * 2048 + w[7] * 1024 + w[8] * 512 + w[9] * 256 + w[10] * 128 + w[11] * 64 + w[12] * 32 + w[13] * 16 + w[14] * 8 + w[15] * 4 + w[16] * 2 + w[17];

    printf("Text length.......: %d\nMESSAGE\n- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -\n", idx);

    /* Generate an ASCII character using 8 consecutive pseudo-bit values    */

    for (int i = 18; i <= idx; i = i + 8)
    {
        chr = w[i] * 128 + w[i + 1] * 64 + w[i + 2] * 32 + w[i + 3] * 16 + w[i + 4] * 8 + w[i + 5] * 4 + w[i + 6] * 2 + w[i + 7];
        printf("%c", chr);
    }

    printf("\n");
}

int main(int argc, char *argv[])
{
    char *in;

    if (argc > 1)
    {
        in = argv[1];
    }
    else
    {
        in = "a.png";
    }

    read_png_file(in);
    process_png();

    for (int y = 0; y < height; y++)
        free(row_pointers[y]);

    free(row_pointers);

    return EXIT_SUCCESS;
}

Once compiled, I tested out the first three small image files and returned the same repetitive test message.

craig@Vera:~/C_Programs/Console/Steganography/bin/Release$ ./Steganography flower.png
Header byte values: 0000101110010000
Text length.......: 2960
MESSAGE
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Tes

I then executed the decoder program over the image of the cat and got the additional hidden instructions.

craig@Vera:~/C_Programs/Console/Steganography/bin/Release$ ./Steganography Kitty.png
Header byte values: 0001010000101000
Text length.......: 5160
MESSAGE
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
The first part of the sentence is "Three may keep a secret, ...".

### Task 2: Decode a binary image

A binary image is hidden in the least significant bits of the butterfly image, the encoding scheme is:

- Simple LSB Encoding**
- Header: `[1, 0]`
- Next 16 bits: image `width` in pixels
- Next 16 bits: image `height` in pixels
- Raw pixels of the binary image

Hint: Create and fill an image array of the derived `width` and `height` with the encoded hidden pixels.
In order to view your image in classic viewers, it might be helpful to map 0 -> 0 and 1 -> 255.
Derive the second part of the sentence and answer the question about the image

However, that is where I have hit a brick wall. I was able to clone and refactor the above code a bit to ascertain the height and width values in the butterfly file, but in trying to go past that point, I have had to stop for now.

craig@Vera:~/C_Programs/Console/Steg2/bin/Release$ ./Steg2 Butterfly.png
Width: 900   Height: 900

After getting words of encouragement from Andre and to be brief, I did some further research in the "libpng" functionality and its use of pixel data, I devised a second program to read and process the "moth/butterfly" image, producing a monochrome image depicting the iconic scene of Benjamin Franklin flying a kite in a thunderstorm with a key attached to the kite string and including the closing portion of the saying "... if two of them are dead".

Following is the second program to complete task 2 sprinkled with comments in case anyone wants to reference the use of "libpng" in their future code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <png.h>

#define HEADER 34

/* Prototypes   */
void read_png_file(char *filename, unsigned int *input_width, unsigned int *input_height);
unsigned int *process_png(unsigned int *output_width, unsigned int *output_height, unsigned int input_width, unsigned int input_height);
unsigned int writeImage(char *filename, unsigned int wt, unsigned int ht, unsigned int *buffer, char *title);

png_bytep *row_pointers;

int main(int argc, char *argv[])
{
    unsigned int rx, ht, wt, hx, wx, * buffer = NULL;

    read_png_file(argv[1], &wx, &hx);
    buffer = process_png(&wt, &ht, wx, hx);

    printf("Output height: %d  Output width: %d\n", ht, wt);

    rx = writeImage(argv[2], wt, ht, buffer, "Hidden Image");

    if (rx != 0)
    {
        printf("Exit error: %d\n", rx);
        return 1;
    }

    for (int y = 0; y < hx - 1; y++)
    {
        free(row_pointers[y]);
    }

    free(row_pointers);

    free(buffer);

    return EXIT_SUCCESS;
}

void read_png_file(char *filename, unsigned int *input_width, unsigned int *input_height)
{
    FILE *fp = fopen(filename, "rb");
    png_byte bit_depth, color_type;

    png_structp png = png_create_read_struct(PNG_LIBPNG_VER_STRING, NULL, NULL, NULL);

    if (!png)
        abort();
    png_infop info = png_create_info_struct(png);

    if (!info)
        abort();

    if (setjmp(png_jmpbuf(png)))
        abort();

    png_init_io(png, fp);
    png_read_info(png, info);
    *input_width  = png_get_image_width(png, info);
    *input_height = png_get_image_height(png, info);
    color_type = png_get_color_type(png, info);
    bit_depth  = png_get_bit_depth(png, info);

    if (bit_depth == 16)                                        /* Read any color_type into 8bit depth, RGBA format.        */
        png_set_strip_16(png);

    if (color_type == PNG_COLOR_TYPE_PALETTE)
        png_set_palette_to_rgb(png);

    if (color_type == PNG_COLOR_TYPE_GRAY && bit_depth < 8)     /* PNG_COLOR_TYPE_GRAY_ALPHA is always 8 or 16 bit depth.   */
        png_set_expand_gray_1_2_4_to_8(png);

    if (png_get_valid(png, info, PNG_INFO_tRNS))
        png_set_tRNS_to_alpha(png);

    /* These color_type don't have an alpha channel then fill it with 0xff. */
    if (color_type == PNG_COLOR_TYPE_RGB || color_type == PNG_COLOR_TYPE_GRAY || color_type == PNG_COLOR_TYPE_PALETTE)
    {
        png_set_filler(png, 0xFF, PNG_FILLER_AFTER);
    }

    if (color_type == PNG_COLOR_TYPE_GRAY || color_type == PNG_COLOR_TYPE_GRAY_ALPHA)
        png_set_gray_to_rgb(png);

    png_read_update_info(png, info);

    row_pointers = (png_bytep*)malloc(sizeof(png_bytep) * *input_height);

    for (int y = 0; y < *input_height; y++)
    {
        row_pointers[y] = (png_byte*)malloc(png_get_rowbytes(png,info));
    }

    png_read_image(png, row_pointers);

    printf("Input height.: %d  Input width.: %d\n", *input_height, *input_width);

    fclose(fp);

    return;
}

unsigned int *process_png(unsigned int *output_width, unsigned int *output_height, unsigned int input_width, unsigned int input_height)
{
    int ix = 0;

    png_bytep row  = row_pointers[0];

    /* Construct width and height values using the LSB of bytes 2 - 33 to convert from binary to integer    */

    *output_width  = (row[22] % 2) + (row[21] % 2) * 2 + (row[20] % 2) * 4 + (row[18] % 2) * 8 + (row[17] % 2) * 16
        + (row[16] % 2) * 32 + (row[14] % 2) * 64 + (row[13] % 2) * 128 + (row[12] % 2) * 256 + (row[10] % 2) * 512;
    *output_height = (row[44] % 2) + (row[42] % 2) * 2 + (row[41] % 2) * 4 + (row[40] % 2) * 8 + (row[38] % 2) * 16
        + (row[37] % 2) * 32 + (row[36] % 2) * 64 + (row[34] % 2) * 128 + (row[33] % 2) * 256 + (row[32] % 2) * 512;

    unsigned int *buffer = (unsigned int *) malloc((*output_width * *output_height + HEADER) * sizeof(unsigned int));

    /* Store the LSB of each pixel as a character in a large character array    */
    /* Only go as far as the two-dimensional array size                         */

    for (unsigned int y = 0; y < input_height; y++)
    {
        png_bytep row = row_pointers[y];
        for (unsigned int x = 0; x < input_width; x++)
        {
            png_bytep px = &(row[x * 4]);

            buffer[ix] = px[0] % 2 + '0';
            ix++;
            buffer[ix] = px[1] % 2 + '0';
            ix++;
            buffer[ix] = px[2] % 2 + '0';
            ix++;

            if (ix > (*output_width * *output_height + HEADER))
                break;
        }
        if (ix > (*output_width * *output_height + HEADER))
            break;
    }

    for (int i = 0; i < (*output_width * *output_height); i++)
        buffer[i] = buffer[i + HEADER];

    return buffer;
}

unsigned int writeImage(char *filename, unsigned int wt, unsigned int ht, unsigned int *buffer, char *title)
{
    int code = 0;
    FILE *fp = NULL;
    png_structp png_ptr = NULL;
    png_infop info_ptr = NULL;
    png_bytep row = NULL;

    fp = fopen(filename, "wb"); /* Open file for writing - binary mode  */

    if (fp == NULL)
    {
        fprintf(stderr, "Could not open file %s for writing\n", filename);
        code = 1;
        goto finalise;
    }

    png_ptr = png_create_write_struct(PNG_LIBPNG_VER_STRING, NULL, NULL, NULL); /* Initialize write structure */

    if (png_ptr == NULL)
    {
        fprintf(stderr, "Could not allocate write struct\n");
        code = 1;
        goto finalise;
    }

    info_ptr = png_create_info_struct(png_ptr);     /* Initialize info structure     */

    if (info_ptr == NULL)
    {
        fprintf(stderr, "Could not allocate info struct\n");
        code = 1;
        goto finalise;
    }

    if (setjmp(png_jmpbuf(png_ptr)))                /* Set up exception handling     */
    {
        fprintf(stderr, "Error during png creation\n");
        code = 1;
        goto finalise;
    }

    png_init_io(png_ptr, fp);

    /* Write header (8 bit colour depth) */
    png_set_IHDR(png_ptr, info_ptr, wt, ht, 8, PNG_COLOR_TYPE_RGB, PNG_INTERLACE_NONE, PNG_COMPRESSION_TYPE_BASE, PNG_FILTER_TYPE_BASE);

    if (title != NULL)  /* Set the title */
    {
        png_text title_text;
        title_text.compression = PNG_TEXT_COMPRESSION_NONE;
        title_text.key = "Title";
        title_text.text = title;
        png_set_text(png_ptr, info_ptr, &title_text, 1);
    }

    png_write_info(png_ptr, info_ptr);

    row = (png_bytep) malloc(3 * wt * sizeof(png_byte)); /* Allocate memory for one row (3 bytes per pixel - RGB) */

    for (int i = 0; i < ht; i++)        /* Write the image data     */
    {
        for (int j = 0; j < wt; j++)
        {
            if (buffer[i * wt + j] == '1')
            {
                row[j * 3 + 0] = 255;   /* These RGB values could be changed to     */
                row[j * 3 + 1] = 255;   /* produce a different background colour    */
                row[j * 3 + 2] = 255;
            }
            else
            {
                row[j * 3 + 0] = 0;     /* These RGB values could be changed to     */
                row[j * 3 + 1] = 0;     /* produce a different foreground colour    */
                row[j * 3 + 2] = 0;
            }
        }

        png_write_row(png_ptr, row);
    }

    png_write_end(png_ptr, NULL);       /* Denote end of writing    */

finalise:
    if (fp != NULL)
        fclose(fp);
    if (info_ptr != NULL)
        png_free_data(png_ptr, info_ptr, PNG_FREE_ALL, -1);
    if (png_ptr != NULL)
        png_destroy_write_struct(&png_ptr, (png_infopp)NULL);
    if (row != NULL)
        free(row);

    return code;
}

Executing the above code resulted in the diagnostic information in the terminal and the subsequent monochrome image.

craig@Vera:~/C_Programs/Console/StegImage/bin/Release$ ./StegImage Moth.png ben.png
Input height.: 480  Input width.: 640
Output height: 900  Output width: 900

Thanks again. This was a nice challenge.

Three may keep a secret, if two of them are dead.

kite and key.

(I’ve seen image processing discussions before, yet this is my first attempt to code a simple demo. Thanks for this great challenge.)

def get_lsb_bits(image_path):
    img = Image.open(image_path).convert("RGB")
    width, height = img.size
    bits = []
    for y in range(height):
        for x in range(width):
            r, g, b = img.getpixel((x, y))
            bits.append(r & 1)
            bits.append(g & 1)
            bits.append(b & 1)
    return bits

from PIL import Image
import requests
from io import BytesIO

def decode_lsb(image_path):
    img = Image.open(image_path).convert("RGB")
    pixels = list(img.getdata())
    
    bits = []
    for r, g, b in pixels:
        bits.append(r & 1)
        bits.append(g & 1)
        bits.append(b & 1)
    
    # Skip the 2-bit header [0, 0]
    offset = 2
    
    # Read next 16 bits for message length
    length_bits = bits[offset:offset + 16]
    msg_length = int("".join(map(str, length_bits)), 2)
    offset += 16
    
    # Read the message bits
    msg_bits = bits[offset:offset + msg_length]
    
    # Convert groups of 8 bits to ASCII characters
    chars = []
    for i in range(0, len(msg_bits), 8):
        byte = msg_bits[i:i + 8]
        if len(byte) == 8:
            chars.append(chr(int("".join(map(str, byte)), 2)))
    
    return "".join(chars)

# Task 0 - Test
print(decode_lsb("black_square.png"))   # Should print: Test Test Test...

# Task 1 - Cat image
message = decode_lsb("cat.png")
print("Hidden message:", message)

# Task 2 - Follow instructions from Task 1
# Decoded the butterfly image using instructions found in Task 1
result = decode_lsb("butterfly.png")
print("Final message:", result)

The quote is: "Three may keep a secret, if two of them are dead." - Benjamin Franklin.

The object on the line is a kite.

The code:

using System.Drawing;
using System.Text;
using SixLabors.ImageSharp;
using SixLabors.ImageSharp.PixelFormats;

namespace ImageDecoder;

public class Program
{
    public static void Main(string[] args)
    {
        if (args.Length != 1) { Console.Error.WriteLine("Error: Expected 1 image filepath"); return; }

        var bits = ExtractBits(args[0]);

        if (!bits[0] && !bits[1])
            ProcessTask1(bits);
        else if (bits[0] && !bits[1])
            ProcessTask2(bits);
    }

    static List<bool> ExtractBits(string path)
    {
        var bits = new List<bool>();
        using var image = SixLabors.ImageSharp.Image.Load<Rgb24>(path);
        image.ProcessPixelRows(accessor =>
        {
            for (int y = 0; y < accessor.Height; y++)
            {
                Span<Rgb24> pixelRow = accessor.GetRowSpan(y);
                for (int x = 0; x < pixelRow.Length; x++)
                {
                    ref Rgb24 pixel = ref pixelRow[x];
                    bits.Add((pixel.R & 1) != 0);
                    bits.Add((pixel.G & 1) != 0);
                    bits.Add((pixel.B & 1) != 0);
                }
            }
        });
        return bits;
    }

    static byte[] BitsToBytes(List<bool> bits, int startIndex, int count)
    {
        var bytes = new List<byte>();
        for (int i = startIndex; i < startIndex + count; i += 8)
        {
            byte value = 0;
            for (int b = 0; b < 8; b++)
                value = (byte)((value << 1) | (bits[i + b] ? 1 : 0));
            bytes.Add(value);
        }
        return bytes.ToArray();
    }

    static void ProcessTask1(List<bool> bits)
    {
        var lengthBytes = BitsToBytes(bits, 2, 16);
        short length = BitConverter.ToInt16(lengthBytes);

        var messageBytes = BitsToBytes(bits, 18, length - 18);
        Console.WriteLine(Encoding.ASCII.GetString(messageBytes));
    }

    static void ProcessTask2(List<bool> bits)
    {
        var headerBytes = BitsToBytes(bits, 2, 32);
        var widthBytes = headerBytes.AsSpan(0, 2).ToArray();
        var heightBytes = headerBytes.AsSpan(2, 2).ToArray();

        if (BitConverter.IsLittleEndian) { Array.Reverse(widthBytes); Array.Reverse(heightBytes); }

        short width = BitConverter.ToInt16(widthBytes);
        short height = BitConverter.ToInt16(heightBytes);

        var imageArray = new byte[height, width];
        for (int i = 0, idx = 34; i < height; i++)
            for (int j = 0; j < width; j++)
                imageArray[i, j] = (byte)(bits[idx++] ? 0x0 : 0xFF);

        SaveGrayBmp(imageArray, "result.bmp");
    }

    static void SaveGrayBmp(byte[,] pixels, string path)
    {
        int width = pixels.GetLength(1), height = pixels.GetLength(0);
        using var bmp = new Bitmap(width, height);
        for (int y = 0; y < height; y++)
            for (int x = 0; x < width; x++)
                bmp.SetPixel(x, y, System.Drawing.Color.FromArgb(pixels[y, x], pixels[y, x], pixels[y, x]));
        bmp.Save(path);
    }
}

Requires System.Drawing.Common and SixLabors.ImageSharp NuGet packages, and only works on Windows.

Answers

1. "Three may keep a secret, if two of them are dead." (Benjamin Franklin)
2. A key (and maybe the kite can also be viewed as on the line).

Code (Java)

The code is pretty much self-explanatory. Images are converted to an integer array (containing ones and zeroes) from the channel last bits which is then used for decoding. The helper function getAsInt() returns the bits in a range as int which is more or less all that's needed to decode the messages. There is no header verification: starts with [0, 0] for the first message and [1, 0] for the 2nd message.

package so;

import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import javax.imageio.ImageIO;
import javax.swing.ImageIcon;
import javax.swing.JFrame;
import javax.swing.JLabel;

public class App {

    public static void main(String[] args) {
        System.out.println(decode1(toChannelLastBits(readImage("MBlXyTSp.png"))));
        showImage(decode2(toChannelLastBits(readImage("mCeETXDs.png"))));
    }
    
    private static BufferedImage readImage(String path) {
        try {
            return ImageIO.read(new File(path));
        } catch (IOException e) {
            throw new RuntimeException(e); // not checked = needs no try/catch
        }
    }
    
    private static int[] toChannelLastBits(BufferedImage img) {
        int[] bits = new int[img.getWidth() * img.getHeight() * 3];
        for (int y = 0, pos = 0; y < img.getHeight(); y++) {
            for (int x = 0; x < img.getWidth(); x++) {
                int pixel = img.getRGB(x, y);
                bits[pos++] = (pixel >> 16) & 1; // red
                bits[pos++] = (pixel >> 8) & 1; // green
                bits[pos++] = pixel & 1; // blue
            }
        }
        return bits;
    }
    
    private static String decode1(int[] bits) {
        int len = getAsInt(bits, 2, 18) >> 3;
        char[] message = new char[len];
        for (int i = 0; i < len; i++)
            message[i] = (char) getAsInt(bits, 18 + (i << 3), 26 + (i << 3));
        return new String(message);
    }
    
    private static BufferedImage decode2(int[] bits) {
        int w = getAsInt(bits, 2, 18);
        int h = getAsInt(bits, 18, 34);
        BufferedImage img = new BufferedImage(w, h, BufferedImage.TYPE_INT_RGB);
        for (int y = 0, i = 34; y < h; y++)
            for (int x = 0; x < w; x++)
                img.setRGB(x, y, -bits[i++]); // -1 = 0xfff... => white
        return img;
    }
    
    private static int getAsInt(int[] bits, int from, int to) {
        int r = 0;
        for (int i = from; i < to; i++)
            r = (r << 1) | bits[i];
        return r;
    }
    
        private static void showImage(BufferedImage img) {
                ImageIcon icon = new ImageIcon(img);
                JLabel label = new JLabel(icon);
                JFrame frame = new JFrame("Image Display");
                frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
                frame.getContentPane().add(label);
                frame.pack();
                frame.setLocationRelativeTo(null);
                frame.setVisible(true);
        }
    
}

Bonus (Encoder)

    public static void encode(BufferedImage img, int[] bits) {
        if (bits.length > img.getWidth() * img.getHeight() * 3)
            throw new RuntimeException("Image too small / message too long");
        for (int i = 0, x = 0, y = 0; i < bits.length; i += 3) {
            int pixel = img.getRGB(x, y);
            if (bits[i] != ((pixel >> 16) & 1))
                pixel ^= 0x10000;
            if (i + 1 < bits.length && bits[i + 1] != ((pixel >> 8) & 1))
                pixel ^= 0x100;
            if (i + 2 < bits.length && bits[i + 2] != (pixel & 1))
                pixel ^= 1;
            img.setRGB(x, y, pixel);
            if (++x >= img.getWidth()) {
                x = 0;
                y++;
            }
        }
    }

Tasks

1. Quote:

   Three may keep a secret, if two of them are dead.

2. Objects: A key or a kite, depending on how you define "on the line".

Approach

I have done some image processing in Python before, so I chose to stick with that. I used a jupyter notebook for the interactivity. It took some experimenting (and manually converting binary) to get the right ordering of bits (LSB / MSB) for each step, but otherwise the tasks worked without major problems. In the end I cleaned up the code a little to be able to post it here without having to be too ashamed.

The only thing I was slightly disappointed by was that there wasn't an easter egg hidden beyond the intended messages (or that I was not able to find it if there was one).

Code

import cv2
import matplotlib.pyplot as plt

test_b = cv2.imread("./SO-Challenge18-TestB.png") # one of the test images
img_1 = cv2.imread("./SO-Challenge18-Image1.png")
img_2 = cv2.imread("./SO-Challenge18-Image2.png")

print(f"'Test Test' should be {[c for c in "Test Test".encode("ascii")]}")
print(f"Test image shape: {test_b.shape}, total {test_b.size} bits")
print(f"Main image shape: {img_1.shape}, total {img_1.size} bits")

def get_int(bits):
    val = 0
    for i, bit in enumerate(bits[::-1]):
        val = val | (bit << i)
    return val

def get_flat_bits(img):
    return img[:, :, ::-1].flatten() % 2

def decode_text(img):
    bits = get_flat_bits(img)
    assert bits[0] == 0 and bits[1] == 0
    length = get_int(bits[2:18])
    print(length)
    chunks = bits[18:18+length].reshape((-1, 8))
    chars = [chr(get_int(chunk)) for chunk in chunks]
    return "".join(chars)

def decode_image(img):
    bits = get_flat_bits(img)
    assert bits[0] == 1 and bits[1] == 0
    width = get_int(bits[2:18])
    height = get_int(bits[18:34])
    print(f"{width} x {height}")
    image = bits[34 : 34 + width * height].reshape((width, height))
    return image

part_1 = decode_text(img_1)
print(part_1)

part_2 = decode_image(img_2)
plt.imshow(part_2, cmap="gray")
plt.show()

What is the hidden quote?

Three may keep a secret, if two of them are dead.

Which object is on the line? Note, there are two possible correct answers here.

A key and a kite

The code is written in bash, it uses convert (or magick), hexdump, sed, cut and fold. The rest should be builtins unless I'm forgetting a package...

It is surprisingly fast for being messy and written in bash. (still slow)

I think I did something wrong in part 2 because the image seems to be shifted a couple of pixels to the right. To read it I just opened my text editor and zoomed out until it didn't linebreak.

Code:

Part 1

#!/usr/bin/env bash
image='sten.png'

bin_image=$(convert $image -depth 8 RGBA:/dev/stdout | hexdump -v -e '/1 "%u\n"'| sed '0~4d')

i=0
b=''
while read c; do
    b="$b$((c % 2))"
    i=$((i + 1))

    if [[ $i -ge 18 ]]; then
        break
    fi
done <<< $bin_image


s=$(cut -c2-18 <(echo $b))

t="2#$s"

content_length=$(echo "$(($t))")

echo "Content length: $content_length"


content=''
i=0
while read line; do

    if [[ $i -ge 18 ]]; then
        content="$content$((line % 2))"
    fi

    i=$((i + 1))
    if [[ $i -gt $(($content_length+1)) ]]; then
        break
    fi
done <<< $bin_image

echo $content | fold -w 8 | while read -r line; do
    hex=$(printf "%x" $((2#$line)))
    echo -ne "\x${hex}"
done

Part 2

#!/bin/bash
image="butterfly.png"

bin_image=$(convert $image -depth 8 RGBA:/dev/stdout | hexdump -v -e '/1 "%u\n"'| sed '0~4d')

i=0
b=''
while read c; do
    b="$b$((c % 2))"
    i=$((i + 1))

    if [[ $i -ge 34 ]]; then
        break
    fi
done <<< $bin_image


s=$(cut -c2-18 <(echo $b))

t="2#$s"

width=$(echo "$(($t))")

s=$(cut -c18-34 <(echo $b))

t="2#$s"

height=$(echo "$(($t))")

echo "h: $height, w: $width"

content=''
i=0
while read line; do

    if [[ $i -ge 34 ]]; then
        content="$content$((line % 2))"
    fi

    i=$((i + 1))
    if [[ $((i % $width)) -eq 0 ]]; then
        echo $content >> out.txt
        content=''
    fi
done <<< $bin_image

1. The hidden quote is "Three may keep a secret, if two of them are dead." by Benjamin Franklin

2. The objects visible on the line in Task 2's hidden image is a key and the kite attached to that line.

My main approach for this challenge is extracting a flat pixels list using PIL to open the image and numpy for conversion, then I can loop over that flat list afterward

Below is the code snippet I made as a base for Task 0

import sys
from PIL import Image
import numpy as np

def bin_arr_to_char(arr):
    n = len(arr)
    i = 0
    r = 0
    while i < n:
        r += arr[i] * pow(2, n-i-1)
        i += 1
    return chr(r)


try:
    file = sys.argv[1]
except:
    print("You need to provide the arguments! python lsb.py [file]")

img = Image.open(file).convert('RGB')
a = np.asarray(img)
r = ""
c = []

flat_arr = [
    x
    for xss in a
    for xs in xss
    for x in xs
]

i = -1
aa = []
for b in flat_arr:
    i += 1
    if i < 18:
        continue

    aa.append(int(b % 2))
    if len(aa) >= 8:
        r += bin_arr_to_char(aa)
        aa.clear()

print(r)

And here's the code snippet for Task 1, with the cat image being named "1.png"

from PIL import Image
import numpy as np

def bin_arr_to_dec(arr):
    n = len(arr)
    i = 0
    r = 0
    while i < n:
        r += arr[i] * pow(2, n-i-1)
        i += 1
    return r

img = Image.open("1.png").convert('RGB')
a = np.asarray(img)
r = ""
c = []

flat_arr = [
    x
    for xss in a
    for xs in xss
    for x in xs
]

i = -1
aa = []
for b in flat_arr:
    i += 1
    if i < 2:
        continue

    if i < 18:
        aa.append(int(b % 2))
        if len(aa) >= 16:
            length = int(bin_arr_to_dec(aa)/8)
            aa.clear()
    else:
        aa.append(int(b % 2))
        if len(aa) >= 8:
            r += chr(bin_arr_to_dec(aa))
            aa.clear()

print(r[:length])

And finally, the code snippet for Task 2 with the butterfly image being named "2.png"

import sys
from PIL import Image
import numpy as np

def bin_arr_to_dec(arr):
    n = len(arr)
    i = 0
    r = 0
    while i < n:
        r += arr[i] * pow(2, n-i-1)
        i += 1
    return r

img = Image.open("2.png").convert('RGB')
a = np.asarray(img)
r = []

flat_arr = [
    x
    for xss in a
    for xs in xss
    for x in xs
]

i = -1
aa = []
c = []
for b in flat_arr:
    i += 1
    if i < 2:
        continue

    if i < 18:
        aa.append(int(b % 2))
        if len(aa) >= 16:
            width = bin_arr_to_dec(aa)
            aa.clear()
    elif i < 34:
        aa.append(int(b % 2))
        if len(aa) >= 16:
            height = bin_arr_to_dec(aa)
            aa.clear()
    else:
        r.append((0, 0, 0) if b % 2 == 0 else (255, 255, 255))

image = Image.new("RGB", (width, height), "white")
image.putdata(r[:width*height])
image.show()

The quote: "Three may keep a secret, if two of them are dead."

The object on the line: A key, or a kite.

The code (Common Lisp):

(ql:quickload :pngload)

(declaim (ftype (function ((unsigned-byte 8)) bit) lsb)
         (inline lsb))
(defun lsb (byte)
  "Return the least significant bit of byte"
  (declare (optimize (speed 3) (safety 0) (debug 0))
           (type (unsigned-byte 8) byte))
  (logand byte 1))

(declaim (ftype (function ((simple-array (unsigned-byte 8) *) fixnum)
                          (unsigned-byte 8))
                extract-byte))
(defun extract-byte (data start)
  "Return the byte encoded in 8 bytes of data starting at start"
  (declare (optimize (speed 3) (safety 1))
           (type (simple-array (unsigned-byte 8) *) data))
  (loop :with b of-type (unsigned-byte 8) = 0
        :for n :from start :to (+ start 7)
        :and i :from 7 :downto 0
        :do (setf (ldb (byte 1 i) b) (lsb (aref data n)))
        :finally (return b)))

(declaim (ftype (function ((simple-array (unsigned-byte 8) *) fixnum)
                          (unsigned-byte 16))
                extract-uint16))
(defun extract-uint16 (data start)
  "Return a 16 bit integer big-endian encoded in data starting at start"
  (declare (optimize (speed 3) (safety 1))
           (type (simple-array (unsigned-byte 8) *) data))
  (+ (ash (extract-byte data start) 8) (extract-byte data (+ start 8))))

(defun extract-text (data)
  "Return the text encoded in data"
  (declare (optimize (speed 3) (safety 1))
           (type (simple-array (unsigned-byte 8) *) data))
  (let ((length (extract-uint16 data 2)))
    (loop :with str = (make-string (/ length 8))
          :for i :from 18 :below (+ length 18) :by 8
          :and n :upfrom 0
          :do (setf (char str n) (code-char (extract-byte data i)))
          :finally (return str))))

(defun extract-image (data)
  "Return a 2d array of the pixels in data"
  (declare (optimize (speed 3) (safety 1))
           (type (simple-array (unsigned-byte 8) *) data))
  (let ((width (extract-uint16 data 2))
        (height (extract-uint16 data 18)))
    (loop :with img = (make-array `(,height ,width)
                                  :initial-element 0
                                  :element-type '(unsigned-byte 8))
          :for i :from 34 :below (* width height)
          :and n :upfrom 0
          :do (setf (row-major-aref img n) (lsb (aref data i)))
          :finally (return img))))

(defun print-image (img &optional (output-filename #p"image.pbm"))
  "Print out the image in PBM format"
  (declare (type (simple-array (unsigned-byte 8) (* *)) img))
  (destructuring-bind (height width) (array-dimensions img)
    (with-open-file (out output-filename
                         :direction :output :if-exists :supersede)
      (format out "P1~%~A ~A~%" width height)
      (dotimes (x height)
        (dotimes (y width)
          (if (zerop (aref img x y))
              (write-char #\0 out)
              (write-char #\1 out))
          (write-char #\space out))
        (terpri out)))))

(defun solve (filename)
  "Extract and print the hidden message from the given PNG file"
  (let* ((img (pngload:load-file filename :flatten t))
         (data (pngload:data img))
         (header (vector (lsb (aref data 0)) (lsb (aref data 1)))))
    (cond
      ((equalp header '#(0 0))
       (write-line (extract-text data)))
      ((equalp header '#(1 0))
       (print-image (extract-image data) #p"answer.pbm")
       (write-line "Image written to 'answer.pbm'"))
      (t (error "Unsupported encoding type ~S" header)))
    t))

Might have gone overboard with type declarations.

CL has a couple of functions that make extracting and setting individual bits (Or ranges of bits) a simple task - in particular LDB.

For generating the image encoded in the butterfly picture, I just cheaped out and wrote a PBM bitmap image, possibly the simplest image file format in existence. No image generation libraries needed. Used pngload for reading the images.

1. The hidden quote is "Three may keep a secret, if two of them are dead. - Benjamin Franklin".
2. A key and a kite is on the line

Solution Code:

import cv2 as cv
import numpy as np

WEIGHTS = 1 << np.arange(7, -1, -1)


def get_uint16(bits: np.ndarray) -> int:
    uint16_bytes = bits[:16].reshape(-1, 8) @ WEIGHTS
    return (uint16_bytes[0] << 8) | uint16_bytes[1]


def decode1(data: np.ndarray) -> str:
    bits = data.flatten() & np.uint8(1)
    assert bits[0] == bits[1] == 0
    length = get_uint16(bits[2:18])
    data_bytes = bits[18 : 18 + length].reshape(-1, 8) @ WEIGHTS
    return "".join(map(chr, data_bytes))


def decode2(data: np.ndarray) -> np.ndarray:
    bits = data.flatten() & np.uint8(1)
    assert bits[0] == 1 and bits[1] == 0
    width = get_uint16(bits[2:18])
    height = get_uint16(bits[18:34])
    img_bits = bits[34 : 34 + width * height]
    return (img_bits.reshape(height, width) * 255).astype(np.uint8)


def main() -> None:
    img1 = cv.imread("img1.png")
    img1 = cv.cvtColor(img1, cv.COLOR_BGR2RGB)
    print(decode1(img1))

    img2 = cv.imread("img2.png")
    img2 = cv.cvtColor(img2, cv.COLOR_BGR2RGB)
    img2 = decode2(img2)
    cv.imshow("Decoded Image", img2)
    cv.waitKey(0)
    cv.destroyAllWindows()


if __name__ == "__main__":
    main()

Decoded message:

The first part of the sentence is "Three may keep a secret, ...".

### Task 2: Decode a binary image

A binary image is hidden in the least significant bits of the butterfly image, the encoding scheme is:

- Simple LSB Encoding**
- Header: `[1, 0]`
- Next 16 bits: image `width` in pixels
- Next 16 bits: image `height` in pixels
- Raw pixels of the binary image

Hint: Create and fill an image array of the derived `width` and `height` with the encoded hidden pixels.
In order to view your image in classic viewers, it might be helpful to map 0 -> 0 and 1 -> 255.
Derive the second part of the sentence and answer the question about the image

This was fun!

1. What is the hidden quote?

   "Three may keep a secret, if two of them are dead." - Benjamin Franklin

2. Which object is on the line? Note, there are two possible correct answers here.

   1. A key

   2. A kite

I made the first function a little more complicated than it had to be because of the last bullet point under Task 1:

Followed by the message itself, ASCII characters encoded by groups of 8bit, most-significant bit (MSB) first

So I made it possible to read the header and message length bits with LSB and the body of the message with MSB. Except MSB didn't seem to work. So the option is still there but I used LSB for all of it. I'm going with the assumption that the MSB was a typo.

import requests
from PIL import Image
import numpy as np
from io import BytesIO

def extract_message(url, header_encoding='LSB', header=2, message_length_bits=16, message_encoding='LSB'):
    # header encoding
    if header_encoding.lower() == 'lsb':
        header_char_index = -1
    elif header_encoding.lower() == 'msb':
        header_char_index = 0
    else:
        raise ValueError("Header encoding must be either 'LSB' or 'MSB'")
    # message encoding
    if message_encoding.lower() == 'lsb':
        message_char_index = -1
    elif message_encoding.lower() == 'msb':
        message_char_index = 0
    else:
        raise ValueError("Message encoding must be either 'LSB' or 'MSB'")
    
    response = requests.get(url, verify=False)
    img = Image.open(BytesIO(response.content)).convert('RGB')
    width, height = img.size
    pixel_rgb_8b = [[format(z, '08b') for z in img.getpixel((x, y))] for y in range(height) for x in range(width)]
    pixel_rgb_8b_flat_list = [item for sublist in pixel_rgb_8b for item in sublist]
    
    # header
    header_ascii_string = ''.join([x[header_char_index] for x in pixel_rgb_8b_flat_list])
    if type(header) == list:
        header_index = header_ascii_string.index(''.join([str(x) for x in header]))
        if header_index == -1:
            print('header not found')
            return
        else:
            header_index += len(header)
    elif type(header) == int:
        header_index = header
    else:
        raise ValueError("Header must be either int or list")
    
    # message length
    message_length = int(header_ascii_string[header_index:header_index+message_length_bits], 2)
    
    # message
    message_ascii_string = ''.join([x[message_char_index] for x in pixel_rgb_8b_flat_list])[message_length_bits+header_index:]
    message_ascii_string = message_ascii_string[:message_length]
    message = "".join(chr(int(message_ascii_string[i:i+8], 2)) for i in range(0, len(message_ascii_string), 8))
    print(message)

And to run it:

extract_message('https://i.sstatic.net/MBlXyTSp.png', header=[0, 0], message_length_bits=16, message_encoding='LSB')

Which provided the first message:

The first part of the sentence is "Three may keep a secret, ...".

### Task 2: Decode a binary image

A binary image is hidden in the least significant bits of the butterfly image, the encoding scheme is:

- Simple LSB Encoding**
- Header: `[1, 0]`
- Next 16 bits: image `width` in pixels
- Next 16 bits: image `height` in pixels
- Raw pixels of the binary image

Hint: Create and fill an image array of the derived `width` and `height` with the encoded hidden pixels. In order to view your image in classic viewers, it might be helpful to map 0 -> 0 and 1 -> 255. Derive the second part of the sentence and answer the question about the image.

My second function for the second image:

import requests
from PIL import Image
import numpy as np
from io import BytesIO

def extract_message_two(url, header_encoding='LSB', header=2, width_bits=16, height_bits=16, message_encoding='LSB'):
    # header encoding
    if header_encoding.lower() == 'lsb':
        header_char_index = -1
    elif header_encoding.lower() == 'msb':
        header_char_index = 0
    else:
        raise ValueError("Header encoding must be either 'LSB' or 'MSB'")
    # message encoding
    if message_encoding.lower() == 'lsb':
        message_char_index = -1
    elif message_encoding.lower() == 'msb':
        message_char_index = 0
    else:
        raise ValueError("Message encoding must be either 'LSB' or 'MSB'")
    
    response = requests.get(url, verify=False)
    img = Image.open(BytesIO(response.content)).convert('RGB')
    width, height = img.size
    pixel_rgb_8b = [[format(z, '08b') for z in img.getpixel((x, y))] for y in range(height) for x in range(width)]
    pixel_rgb_8b_flat_list = [item for sublist in pixel_rgb_8b for item in sublist]
    
    # header
    header_string = ''.join([x[header_char_index] for x in pixel_rgb_8b_flat_list])
    if type(header) == list:
        header_index = header_string.index(''.join([str(x) for x in header]))
        if header_index == -1:
            print('header not found')
            return
        else:
            header_index += len(header)
    elif type(header) == int:
        header_index = header
    else:
        raise ValueError("Header must be either int or list")
    # image width
    image_width = int(header_string[header_index:header_index+width_bits], 2)
    # image height
    image_height = int(header_string[header_index+width_bits:header_index+width_bits+height_bits], 2)
    
    # image
    image_string = ''.join([x[message_char_index] for x in pixel_rgb_8b_flat_list])[header_index+width_bits+height_bits:][:image_width*image_height]
    pixels = [255 if x == '1' else 0 for x in image_string]
    img = Image.new('L', (image_width, image_height))
    img.putdata(pixels)
    img.show()

Which I ran with:

extract_message_two('https://i.sstatic.net/mCeETXDs.png', header=[1, 0], width_bits=16, height_bits=16, message_encoding='LSB')

This generated and image of Ben Franklin flying a kite, with the rest of the quote on the bottom.

In Python, using 3rd party Pillow module (pip install pillow) for processing images:

from PIL import Image
import math

def extract_lsbs(data):
    '''Extract LSBs from RGB data as a string of 1s and 0s.
    '''
    s = []
    for r,g,b in data:
        s.extend([str(r & 1), str(g & 1), str(b & 1)])
    return ''.join(s)

def decode00(bits):
    '''Decode Header: [0, 0]
       Next 16-bits: message length in bits
       Followed by the message itself, ASCII characters encoded by groups of 8bit, most-significant bit (MSB) first
       Return the decoded string
    '''
    LENGTH_START = 2
    DATA_START = 18
    if bits[:LENGTH_START] != '00':
        raise ValueError('incorrect header')
    length = int(bits[LENGTH_START:18], 2)
    if length % 8 != 0:  # Assume message length is a multiple of 8 bits given description.
        raise ValueError('length not multiple of 8 bits')
    reqlen = DATA_START + length
    if reqlen > len(bits):  # Sanity check
        raise ValueError('length exceeds data')
    databits = bits[DATA_START:reqlen]
    return int(databits, 2).to_bytes(length // 8).decode()

def decode10(bits):
    '''Decode Header: [1, 0]
       Next 16 bits: image width in pixels
       Next 16 bits: image height in pixels
       Raw pixels of the binary image
       Return the decoded image.
    '''
    WIDTH_START = 2
    HEIGHT_START = 18
    DATA_START = 34
    if bits[:WIDTH_START] != '10':
        raise ValueError('incorrect header')
    width = int(bits[WIDTH_START:HEIGHT_START], 2)
    height = int(bits[HEIGHT_START:DATA_START], 2)
    reqlen = DATA_START + width * height
    if reqlen > len(bits):
        raise ValueError('length exceeds data')
    databits = bits[DATA_START:reqlen]

    # Collect row data
    pad = 8 - width % 8  # Image requires row data to be multiple of 8 bits.
    rowbytes = math.ceil(width / 8)  # Number of bytes needed for a row
    imdata = bytearray()
    for row in range(height):
        rowbits = databits[row * width:(row + 1) * width] + '0' * pad
        imdata.extend(int(rowbits, 2).to_bytes(length=rowbytes))
    return Image.frombytes('1', (width, height), imdata)
        
for filename in ('black.png', 'contrast.png', 'flower.png', 'cat.png'):
    im = Image.open(filename)
    data = im.get_flattened_data()
    print(decode00(extract_lsbs(data)))

im = Image.open('butterfly.png')
data = im.get_flattened_data()
im2 = decode10(extract_lsbs(data))
im2.show()

Output:

Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test
Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test
Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test
The first part of the sentence is "Three may keep a secret, ...".

### Task 2: Decode a binary image

A binary image is hidden in the least significant bits of the butterfly image, the encoding scheme is:

- Simple LSB Encoding**
- Header: `[1, 0]`
- Next 16 bits: image `width` in pixels
- Next 16 bits: image `height` in pixels
- Raw pixels of the binary image

Hint: Create and fill an image array of the derived `width` and `height` with the encoded hidden pixels.
In order to view your image in classic viewers, it might be helpful to map 0 -> 0 and 1 -> 255.
Derive the second part of the sentence and answer the question about the image.

The final image is of Ben Franklin flying a kite and reaching to touch a key.

The first image has the text "Three may keep a secret, ...", and the second:

... if two of them are dead.
Benjamin Franklin

Answer:

Three may keep a secret, if two of them are dead. Benjamin Franklin

Now let's solve the challenge step by step using c#

Having the image downloaded as a file, let's obtain its hidden bits:

private static byte[] BitsFromImage(string fileName) {
  // Note, that .Net will convert png to BMP
  using var bmp = new Bitmap(fileName); 

  var bmpData = bmp.LockBits(
    new Rectangle(0, 0, bmp.Width, bmp.Height), 
    ImageLockMode.ReadOnly, 
    bmp.PixelFormat);

  var bytes = bmpData.Stride * bmp.Height;

  var rgbValues = new byte[bytes];

  Marshal.Copy(bmpData.Scan0, rgbValues, 0, bytes);

  // We want RGB order, not default BGR
  for (var i = 0; i < bytes; i += 3)
    (rgbValues[i], rgbValues[i + 1], rgbValues[i + 2]) = 
       (rgbValues[i + 2], rgbValues[i + 1], rgbValues[i]);

  // We want LSBs only 
  for (var i = 0; i < bytes; ++i)
    rgbValues[i] = (byte)(rgbValues[i] & 1);

  return rgbValues;
}

Having these bits we can easily implement a decoder for the 1st challenge:

private static string ImageToText(string fileName) {
  var rgbValues = BitsFromImage(fileName);
  var length = rgbValues.Skip(2).Take(16).Aggregate(0, (s, a) => s * 2 + a);

  return string.Concat(rgbValues
    .Skip(18)
    .Take(length)
    .Chunk(8)
    .Select(chunk => (char)chunk.Aggregate(0, (s, a) => s * 2 + a)));
}

If we call it like this:

// Put the right name 
Console.WriteLine(ImageToText(@"C:\Image1.png")); 

We will get the 1st part of the sentence and instructions for the second part:

The first part of the sentence is "Three may keep a secret, ...".

Task 2: Decode a binary image

A binary image is hidden in the least significant bits of the butterfly image, the encoding scheme is:

Simple LSB Encoding** Header: [1, 0] Next 16 bits: image width in pixels Next 16 bits: image height in pixels Raw pixels of the binary image

Hint: Create and fill an image array of the derived width and height with the encoded hidden pixels. In order to view your image in classic viewers, it might be helpful to map 0 -> 0 and 1 -> 255. Derive the second part of the sentence and answer the question about the image.

Second part is as easy as the first one:

private static Bitmap ImageToBmp(string fileName) {
  var rgbValues = BitsFromImage(fileName);

  var width = rgbValues.Skip(2).Take(16).Aggregate(0, (s, a) => s * 2 + a);
  var height = rgbValues.Skip(18).Take(16).Aggregate(0, (s, a) => s * 2 + a);

  var result = new Bitmap(width, height);
            
  for (var r = 0; r < height; ++r)
    for (var c = 0; c < width; ++c)
      result.SetPixel(c, r, rgbValues[34 + width * r + c] == 0 
        ? Color.Black 
        : Color.White);

  return result;
}

If we run the routine and save the image into a file

// Put the right file name here
using var image = ImageToBmp(@"C:\Image2.png");

image.Save(@"C:\Solution.bmp");

We will get the final image

Solution

Where we can see Key and Kite.

Three may keep a secret, ... if two of them are dead.

Benjamin Franklin

It's a modified kite with a key on the line.

The JavaScript and C++ approaches turned out to be non-productive, but PHP image processing and GD worked like a charm.

Part 1

Part 2

No real hitches to report, just the usual string parsing routine.

Source 1:

<?php

$im = imagecreatefrompng("MBlXyTSp.png");

$c=0;$v=0;
for ($i=0;$i<480;$i++) {
for ($j=0;$j<640;$j++) {
$rgb = imagecolorat($im, $j, $i);
$r = ($rgb >> 16) & 0x1;
$v<<=1;
$v+=$r;
$c++;
if ($c>18 && ($c-18)%8==0) {echo chr($v);$v=0;}
$g = ($rgb >> 8) & 0x1;
$v<<=1;
$v+=$g;
$c++;
if ($c==2) echo '<br>';
if ($c>18 && ($c-18)%8==0) {echo chr($v);$v=0;}
$b = $rgb & 0x1;
$v<<=1;
$v+=$b;
$c++;
if ($c==18) {echo '<br>';$v=0;}
if ($c>18 && ($c-18)%8==0) {echo chr($v);$v=0;}
}

}
?>

Source 2:

<?php

$im = imagecreatefrompng("mCeETXDs.png");
$imo= imagecreatetruecolor(900,900);
$bl=imagecolorallocate($imo,100,200,100);

$c=0;$ox=-34;$oy=0;
for ($i=0;$i<480;$i++) {
for ($j=0;$j<640;$j++) {
$rgb = imagecolorat($im, $j, $i);

$r = ($rgb >> 16) & 0x1;
$ox++;if ($ox>899) {$ox=0;$oy++;}
if ($r) imagesetpixel($imo,$ox,$oy,$bl);
$c++;

$g = ($rgb >> 8) & 0x1;
$ox++;if ($ox>899) {$ox=0;$oy++;}
if ($g) imagesetpixel($imo,$ox,$oy,$bl);
$c++;

$b = $rgb & 0x1;
$ox++;if ($ox>899) {$ox=0;$oy++;}
if ($b) imagesetpixel($imo,$ox,$oy,$bl);
$c++;

}
}
header("Content-type: image/png");
imagepng($imo);
?>

This challenge was fun, if a bit tedious because I had to make a few (binary) assumptions:

• First, it seems relatively obvious that the data we are interested in is stored in the actual pixels, and not the metadata. As such we want to parse the PNG format. Lucky for me, Java can read .png files and represent the data in them faithfully. Theoretically one could write their own, limited parser for PNG images that can read the images in the challenge, however, I opted for the builtin tools.

• Not obvivious for someone who doesn't work with image generation is wether the hidden data is written horizontally or vertically into those images, that means, given this code:

    for(int i = 0; i < /*...*/; i++){
      int x = i % sourceWidth;
      int y = i / sourceWidth;
    }
  

  wether the two mathematical operations for x and y need to be swapped or not. Getting it wrong will result in the extracted text becoming garbage.

• extracting the desired bit is not particularely difficult, the remainign bits can be zeroed out by anding with a suitable bitmask.

• the byte order for the message length in task 1 and the width/height in task 2 was not specified. I guessed MSB and given the result doesn't look like garbage that might have been correct.

• extracting the data is a bit of a nuisance, given that you have three values per pixel and we might need all of them (in particular for the 2nd task header, where the header <-> body border is not pixel-aligned) or only some of them (if the body doesn't end with a blue channel)

That brings us to the hidden qoute:

Three may keep a secret, if two of them are dead.

Benjamin Franklin

And the objects on the line, which appears to be a key and a kite.

Finally, the code:

package com.stackexchange.challenges.challenge18;

import java.awt.image.BufferedImage;
import java.awt.image.ColorModel;
import java.io.File;
import java.io.IOException;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.List;
import javax.imageio.ImageIO;

/**
 *
 * @author Jannik S.
 */
public class Main {

    public static final byte LSB_MASK = 0b00000001;

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws IOException {
        System.out.println("StackOverflow Challenge 18");
        System.out.println("https://stackoverflow.com/beta/challenges/79926210/challenge-18-hidden-in-plain-sight");
        if (args.length != 1) {
            System.out.println("Invalid usage, 1st arg needs to be a path!");
            System.exit(1);
            return;
        }
        BufferedImage data = ImageIO.read(new java.io.File(args[0]));
        if (data == null) {
            System.err.println("Failed to read image: unsupported image format");
        }
        HiddenMesssageHeader header = parseHeader(data);
        switch (header.type) {
            case 0:
                String value = parseContentText(data, header.interestingData[0]);
                System.out.println("the result is " + value);
                break;
            case 2:
                extractHiddenImage(data,header.interestingData[0],new java.io.File("hidden-image.png"));
                break;
            default:
                System.err.println("unrecognized header value: " + header.type);
        }

    }

    /**
     * parse the header data and return the number of bits composing the
     * message.
     *
     * @param data image to read from
     * @return
     */
    private static HiddenMesssageHeader parseHeader(BufferedImage data) {
        //header data is spread across the first 18 color channels.
        //that means the first 6 pixels. todo: find out wether it is 
        //pixelId= i * width +j or not.
        //note: we cannot safely assume that all pixels are at  y = 0!
        //check for header value
        List<Byte> sackOfValues = new ArrayList(18);
        int width = data.getWidth();
        if (data.getColorModel() != ColorModel.getRGBdefault()) {
            System.err.println("[ParseHeader] warning: possibly unsupported color model");
        }
        for (int i = 0; i < 6; i++) {
            int x = i % width;
            int y = i / width;
            java.awt.Color pixelColor = new java.awt.Color(data.getRGB(x, y));
            sackOfValues.add((byte) (pixelColor.getRed() & LSB_MASK));
            sackOfValues.add((byte) (pixelColor.getGreen() & LSB_MASK));
            sackOfValues.add((byte) (pixelColor.getBlue() & LSB_MASK));
        }
        int magicNumber = sackOfValues.get(0) << 1 | sackOfValues.get(1);
        //discard the magic number bits, these are no longer interesting
        sackOfValues.remove(0);
        sackOfValues.remove(0);
        //now parse the message length
        //note: this is ugly, but far easier to reason about with a debugger.
        String temp = "";
        for (int i = 0; i < sackOfValues.size(); i++) {
            temp += sackOfValues.get(i);
        }
        //note: we deliberately use integer here, because turnning raw bits into shorts 
        //(which is the 16-bit numeral type in java) is ugly.
        //new java.util.BitSet().
        return new HiddenMesssageHeader(magicNumber, new int[]{Integer.parseInt(temp, 2)});
    }

    private static String parseContentText(BufferedImage data, int messageLength) {
        if (messageLength < 0) {
            throw new IllegalArgumentException("messageLength < 0:" + messageLength);
        }
        int numPixels = messageLength / 3;
        int extraPixelChannels = messageLength % 3;
        if (extraPixelChannels != 0) {
            numPixels += 1;
        }
        //now read the specific number of pixels
        List<Byte> sackOfBits = new ArrayList<>(messageLength);
        int width = data.getWidth();
        for (int i = 6; i < 6 + numPixels; i++) {
            int x = i % width;
            int y = i / width;
            java.awt.Color pixelColor = new java.awt.Color(data.getRGB(x, y));
            sackOfBits.add((byte) (pixelColor.getRed() & LSB_MASK));
            sackOfBits.add((byte) (pixelColor.getGreen() & LSB_MASK));
            sackOfBits.add((byte) (pixelColor.getBlue() & LSB_MASK));
        }
        //if we just read unused channels, delete those bits
        while (sackOfBits.size() > messageLength) {
            sackOfBits.removeLast();
        }
        //now turn those bits into bytes... same trick as before.
        if (sackOfBits.size() % 8 != 0) {
            System.out.println("Warning: Bits do not cleanly divide into bytes: bitsCount % 8 = " + sackOfBits.size() % 8);
        }
        List<Byte> sackOfBytes = new ArrayList<>(messageLength / 8);
        while (!sackOfBits.isEmpty()) {
            int end = Math.min(8, sackOfBits.size());
            List<Byte> currentData = sackOfBits.subList(0, end);
            String temp = "";
            for (int i = 0; i < currentData.size(); i++) {
                temp += currentData.get(i);
            }
            //note: we need to downcast here because the lead bit might be set
            sackOfBytes.add((byte) Integer.parseInt(temp, 2));
            currentData.clear();
        }
        //now that we have bytes, this should be easy...
        byte[] dataArray = new byte[sackOfBytes.size()];
        for (int i = 0; i < dataArray.length; i++) {
            dataArray[i] = sackOfBytes.get(i);
        }
        return new String(dataArray, StandardCharsets.US_ASCII);
    }

    private static void extractHiddenImage(BufferedImage data, int targetWidth, File target) throws IOException {
        //step 1: parse the width of the embeded image (we need to do this ourselves)
        List<Byte> sackOfValues = new ArrayList<>();
        //16 bits - that means 6 pixels with two bits of the body!
        int width = data.getWidth();
        for(int i = 6; i < 12; i++){
            int x = i % width;
            int y = i / width;
            java.awt.Color pixelColor = new java.awt.Color(data.getRGB(x, y));
            sackOfValues.add((byte) (pixelColor.getRed() & LSB_MASK));
            sackOfValues.add((byte) (pixelColor.getGreen() & LSB_MASK));
            sackOfValues.add((byte) (pixelColor.getBlue() & LSB_MASK));
        }
        List<Byte> heightBits = sackOfValues.subList(0, 16);
        String temp = "";
        for (int i = 0; i < heightBits.size(); i++) {
            temp += heightBits.get(i);
        }
        int targetHeight = Integer.parseInt(temp,2);
        BufferedImage decodedImage = new BufferedImage(targetWidth, targetHeight, data.getType());
        //now extract the remaining pixels
        long totalPixels = targetWidth * targetHeight;
        long missingPixels = (totalPixels - 2) / 3;
        if((totalPixels - 2) % 3 != 0){
            missingPixels++;
        }
        for(int i = 12; i < 12 + missingPixels; i++){
            int x = i % width;
            int y = i / width;
            java.awt.Color pixelColor = new java.awt.Color(data.getRGB(x, y));
            sackOfValues.add((byte) (pixelColor.getRed() & LSB_MASK));
            sackOfValues.add((byte) (pixelColor.getGreen() & LSB_MASK));
            sackOfValues.add((byte) (pixelColor.getBlue() & LSB_MASK));
        }
        //now apply the data we have to the result image (note: seems to be black-and-white)
        for(int i = 0; i < totalPixels; i++){
            int x = i % targetWidth;
            int y = i / targetWidth;
            java.awt.Color pixelColor = sackOfValues.get(i) == 0? java.awt.Color.BLACK:java.awt.Color.WHITE;
            decodedImage.setRGB(x, y, pixelColor.getRGB());
        }
        //and now save the whole thing.
        ImageIO.write(decodedImage, "png", target);
    }

    private static record HiddenMesssageHeader(int type, int[] interestingData) {

    }
}

It was more or less straightforward after realizing that the bit counts used for the header parts are done in data space and the MSB/LSB convention for the output. Solving for an unknown steganography scheme would've been more interesting.

Read in the data with PIL

from PIL import Image
import numpy as np
fn = "/tmp/MBlXyTSp.png"
img = Image.open(fn)
arr = np.array(img)
larr = arr.reshape(-1)

and then have some primitives for decoding a hlen-bit number and an ASCII char from the steganography part (this could be one function and a converter, but w/e)

def decode_number(data, skip, hlen):
    bb = 0 
    for i in range(hlen):
        bb += int((data[skip+i] & 0x1)) << ((hlen-1)-i)
    return bb
def decode_block(data, start):
    myb = 0
    for k in range(8):
        b = data[start+k]
        lsb = b & 0x1
        myb = myb | (lsb << (7-k))
    return chr(myb)

Using them to decode the cat image:

def decode_message(data, skip, hlen):
    bskip = 2
    msglen = decode_number(data, skip,hlen)
    msg = ""
    for i in range(msglen//8):
        ch = decode_block(larr, skip+i*8)
        msg += ch
    print(msg)

gives us a partial answer to 1) "Three may keep a secret, ..." (and skipping ahead, the full one being Three may keep a secret, if two of them are dead.".

The image decoding works similarly, except I couldn't be bothered to write a new primitive for bitwise images:

def decode_img(data, skip, hlen):
    w = decode_number(data, skip, hlen)
    h = decode_number(data, skip+hlen, hlen)
    imlen = w*h
    off = skip+2*hlen
    img = np.zeros((w, h), dtype=np.int8)
    img = img.reshape(-1)
    for i in range(imlen):
        b = data[off+i]
        lsb = b & 0x1
        img[i] = lsb
    return img.reshape(w, h)

which we can plot with matplotlib directly, getting the rest of the quote. As for what's on the line, taking it to be the string to the kite, it's both the kite and a key.

Very nice challenge.

Here's my program in C++23 (using Boost Gil)

#include <boost/gil.hpp>
#include <boost/gil/extension/io/png.hpp>
#include <print>
#include <ranges>
using namespace std::string_literals;

namespace gil = boost::gil;
namespace v   = std::views;
using Pixel   = gil::rgb8_pixel_t;
using Image   = gil::rgb8_image_t;
static_assert(sizeof(Pixel) == 3);

static constexpr inline auto flatten(Pixel const& p) {
    return std::array{p.at_c_dynamic(0), p.at_c_dynamic(1), p.at_c_dynamic(2)};
}

static constexpr inline auto lsb(uint8_t c) { return c & 0b1; }

template <typename T> struct Decoder {
    constexpr inline auto operator()(auto&& bits) const {
        T value = 0;
        for (auto bit : bits)
            value = (value << 1) | (bit & 1);
        return value;
    }
};
template <typename T = char> static inline constexpr Decoder<T> decode;

void process(char const* fname) {
    std::print("==== processing {}\n\n", fname);
    Image i;
    read_image(fname, i, gil::png_tag{});

    auto bitstream = v::join(i._view | v::transform(flatten)) | v::transform(lsb);
    auto header    = decode<uint16_t>(bitstream | v::take(2));
    switch(header) {
        case 0b00: { // Task 1
            auto numbits = decode<uint16_t>(bitstream | v::drop(2) | v::take(16));
            auto bytes   = bitstream      //
                | v::drop(2 + 16)         //
                | v::take(numbits)        //
                | v::chunk(8)             //
                | v::transform(decode<>); //

            std::print("Task 1: header:{:02b} numbits: {} info: {}x{}\n", header, numbits, i.width(),
                       i.height());
            std::print("Task 1: {}\n", std::string(std::from_range, bytes));
            break;
        }
        case 0b10: { // Task 2
            using Dot = gil::gray8_pixel_t;
            static_assert(sizeof(Dot) == 1);

            auto width  = decode<uint16_t>(bitstream | v::drop(2) | v::take(16));
            auto height = decode<uint16_t>(bitstream | v::drop(18) | v::take(16));
            std::vector raw( //
                std::from_range,
                bitstream                                                          //
                    | v::drop(34)                                                  //
                    | v::take(sizeof(Dot) * width * height)                        //
                    | v::transform([](auto v) -> uint8_t { return v ? 0xff : 0; }) //
            );

            std::print("Task 2: header:{:02b} {}x{} raw size:{} (original: {}x{})\n", header, width, height,
                       raw.size(), i.width(), i.height());

            auto out= "output_"s + fname;
            write_view(out,
                       interleaved_view(width, height, reinterpret_cast<Dot const*>(raw.data()),
                                        sizeof(Dot) * width),
                       gil::png_tag{});
            std::print("Wrote steg image to {}\n", out);

            break;
        }
    }
}

int main() {
    for (auto fname : {"1RtT7h3L.png", "bmDwolWU.png", "EKD3bBZP.png", "MBlXyTSp.png", "mCeETXDs.png"})
        process(fname);
}

It's output looks like

==== processing 1RtT7h3L.png

Task 1: header:00 numbits: 2960 info: 32x32
Task 1: Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Tes
==== processing bmDwolWU.png

Task 1: header:00 numbits: 2960 info: 32x32
Task 1: Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Tes
==== processing EKD3bBZP.png

Task 1: header:00 numbits: 2960 info: 32x32
Task 1: Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Tes
==== processing MBlXyTSp.png

Task 1: header:00 numbits: 5160 info: 640x480
Task 1: The first part of the sentence is "Three may keep a secret, ...".

### Task 2: Decode a binary image

A binary image is hidden in the least significant bits of the butterfly image, the encoding scheme is:

- Simple LSB Encoding**
- Header: `[1, 0]`
- Next 16 bits: image `width` in pixels
- Next 16 bits: image `height` in pixels
- Raw pixels of the binary image

Hint: Create and fill an image array of the derived `width` and `height` with the encoded hidden pixels.
In order to view your image in classic viewers, it might be helpful to map 0 -> 0 and 1 -> 255.
Derive the second part of the sentence and answer the question about the image.

==== processing mCeETXDs.png

Task 2: header:10 900x900 raw size:810000 (original: 640x480)
Wrote steg image to output_mCeETXDs.png

• Task 1: "Three may keep a secret, ..."
• Task 2: "... if two of them are dead." -- Benjamin Franklin
• Task 3: The object on the line is a key (and a kite...)

Notes

The only step that gave me "trouble" was realizing the proper meaning of "binary image"

I wrote a function in R that handles both tasks. However, I had to manually solve Task 1 before I could write it.

I read the images in and extract the least significant bit from each channel. Then, I check the 2-bit header. If [0,0] we follow the instructions for Task 1 (which revealed the instruction for Task 2). If [1,0], read the width and height and reshape the pixel bits to an image matrix.

The part that made this efficient is as.vector(aperm(rgb_only, c(3,2,1))) %% 2 which extracts all LSBs in one vectorized operation instead of looping over the images pixel by pixel. aperm rearranges the RGB values from [row, col, channel] to [channel, col, row] so when we flatten with as.vector we get the right order.

I have a couple of other tricks here to keep everything Θ(N): %% 2 extracts all LSBs at once, matrix(..., byrow=TRUE) reshapes in one pass, and bit_matrix %*% 2^(7:0) converts all bytes to integers via matrix multiplication.

library(png)

decode_lsb <- function(image_path, output_path = "hidden_image.png") {
  img <- readPNG(image_path)

  # Convert to 0-255 and extract LSBs
  rgb_only <- round(img[,,1:3] * 255)
  bits <- as.vector(aperm(rgb_only, c(3,2,1))) %% 2
  
  
  # Check header type
  if (all(bits[1:2] == c(0, 0))) {

    msg_length <- sum(bits[3:18] * 2^(15:0))
    
    msg_bits <- bits[19:(18 + msg_length)]
    bit_matrix <- matrix(msg_bits, ncol = 8, byrow = TRUE)
    char_codes <- bit_matrix %*% 2^(7:0)
    msg <- rawToChar(as.raw(char_codes))
    
    cat("\n### DECODED MESSAGE ###\n", msg, "\n")
    ##return(msg)
    
  } else if (all(bits[1:2] == c(1, 0))) {

    width <- sum(bits[3:18] * 2^(15:0))
    height <- sum(bits[19:34] * 2^(15:0))

    # Extract pixel bits
    n_pixels <- width * height
    pixel_bits <- bits[35:(34 + n_pixels)]
    
    # Fill image matrix by rows
    hidden_img <- matrix(pixel_bits * 255, nrow = height, ncol = width, 
                         byrow = TRUE)
    
    # Save as PNG
    writePNG(hidden_img / 255, output_path)
    ##return(hidden_img)
    
  } else {
    cat("Unknown header format:", bits[1:2], "\n")
    return(NULL)
  }
}

Tests:

decode_lsb("black_box.png")
decode_lsb("rgb_confetti.png")
decode_lsb("rene.png")

All three returning:

### DECODED MESSAGE ###
 Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test Test 

Task 1:

decode_lsb("kitty.png")

returning:

### DECODED MESSAGE ###
 The first part of the sentence is "Three may keep a secret, ...".

### Task 2: Decode a binary image

A binary image is hidden in the least significant bits of the butterfly image, the encoding scheme is:

- Simple LSB Encoding**
- Header: `[1, 0]`
- Next 16 bits: image `width` in pixels
- Next 16 bits: image `height` in pixels
- Raw pixels of the binary image

Hint: Create and fill an image array of the derived `width` and `height` with the encoded hidden pixels.
In order to view your image in classic viewers, it might be helpful to map 0 -> 0 and 1 -> 255.
Derive the second part of the sentence and answer the question about the image.

Task 2:

decode_lsb("butterfly.png")

This returns/saves an image to hidden_image.png;

"Three may keep a secret, if two of them are dead." - Benjamin Franklin

And the object on the line is Key (or Kite).

1. What is the hidden quote? The quote is "Three may keep a secret, if two of them are dead."
2. Which object is on the line? (Note, there are two possible correct answers here.) A kite is on the line. Alternatively, a key is on the line.

I implemented the LSB-first image–bits decoder first. I wasted 15 minutes debugging why I got gibberish only to find I had to swap width/height.

# mylib.py
from PIL import Image
def SteganographyBitstream(path: str):
    with open(path, "rb") as f:
        image = Image.open(f)
        data = image.load()
        for y in range(image.height):
            for x in range(image.width):
                r, g, b = data[x,y]
                yield r & 1
                yield g & 1
                yield b & 1
def read_byte(bitstream):
    result: int = 0
    for _ in range(8):
        result = (result << 1) | next(bitstream)
    return result

Then task 1 was a simple bits–MSB-ASCII converter:

#!/usr/bin/env python3
# task1.py
from mylib import SteganographyBitstream, read_byte
def challenge_bytestream(bitstream):
    assert next(bitstream) == 0
    assert next(bitstream) == 0
    length: int = (read_byte(bitstream) << 8) | read_byte(bitstream)
    for _ in range(length // 8):
        yield read_byte(bitstream)
print(bytes(challenge_bytestream(SteganographyBitstream("MBlXyTSp.png"))).decode("ascii"))

Task 2 was a similar conversion as described. Knowing the Netpbm format exists allowed me to skip a "map 0 -> 0 and 1 -> 255" step and print the image directly. I tried using Unicode without Netpbm, but my terminal wouldn't let me zoom out far enough, so I used Netpbm and GIMP. I faced the challenge of debugging that Netpbm, unlike others, uses has 0 as white not black, requiring me to invert the colors back to normal.

#!/usr/bin/env python3
# task2.py
from mylib import SteganographyBitstream, read_byte
def print_pbm(bitstream):
    assert next(bitstream) == 1
    assert next(bitstream) == 0
    width: int = (read_byte(bitstream) << 8) | read_byte(bitstream)
    height: int = (read_byte(bitstream) << 8) | read_byte(bitstream)
    print("P1")
    print(width, height)
    for _ in range(height):
        for _ in range(width):
            print(1 - next(bitstream), end="")
        print()
print_pbm(SteganographyBitstream("mCeETXDs.png"))

To run those files after saving them:

python3 -m venv venv
. venv/bin/activate
pip install pillow
wget https://i.sstatic.net/MBlXyTSp.png
python3 ./task1.py
wget https://i.sstatic.net/mCeETXDs.png
python3 ./task2.py > ./part2.pbm
gimp ./task2.pbm

Task 1 output:

The first part of the sentence is "Three may keep a secret, ...".

Task 2: Decode a binary image

A binary image is hidden in the least significant bits of the butterfly image, the encoding scheme is:

• Simple LSB Encoding**
• Header: [1, 0]
• Next 16 bits: image width in pixels
• Next 16 bits: image height in pixels
• Raw pixels of the binary image

Hint: Create and fill an image array of the derived width and height with the encoded hidden pixels. In order to view your image in classic viewers, it might be helpful to map 0 -> 0 and 1 -> 255. Derive the second part of the sentence and answer the question about the image.

Task 2 image