Image shredding algorithm - security through obscurity
New here? Learn about Bountify and follow @bountify to get notified of new bounties! x

I am looking to make an image shredding algorithm that will accept an image, shred it, put it back together to a single image, and then generate a key that can be used to put the image back together.

I am initially thinking we should accept an image and then break it in to squares, we can flip, rotate, and other wise change each cube to obscure both what it looks like visually as well as other algorithms that are effective at "de shredding".

Along with the algorithm i will need some way to test it, Ideally i can run as a console or web app to give it a try.

Here are a couple of relevant links
http://instagram-engineering.tumblr.com/post/12651721845/instagram-engineering-challenge-the-unshredder

http://www.newscientist.com/article/dn21922-algorithm-beats-jigsawsolving-record.html#.Uk2G0iSsh8E

We can introduce "noise" to the pieces of the images as long as with the key we can losslessly get back to the meaningful original.

I dont have language constraints on this since we will use the algorithm mainly but as long as i can test your POC by my windows desktop or a url that you can provide access to I should be good to test and accept.

Very interesting!
akshatpradhan 7 months ago
The description reminded me of GMask. The links you posted refer to algorithms that decode an image by analysing the pieces and using a brute-force method, without using any key. Why do you want to use that kind of encryption and not something like AES?
tomtoump 7 months ago
My goal is to be able to send the image in the open without needing to encrypt it, and then send the key for it encrypted. this means i can be a little more careless with the actual content/image and I just need to worry with the key since it unlocks the obscurity.
Qdev 7 months ago
Does this algorithm need to be format agnostic, can one particular format be chosen (do you have a preference of format)? These types of algorithms can suffer due to compression and rendering artifacts, so are more suited to losslessly compressed images and bitmaps. For example, if you were to create this algorithm for JPEG and the JPEG was re-compressed (even at the same size, say by a social media site), unrecoverable errors are introduced.
aydiosmio 7 months ago
Good question, for this POC , we can assume png so we are clear on what is introduced via the transformations. experimentation later on other formats can be considered out of scope.
Qdev 7 months ago
The optimal design essentially randomizes each color channel value, so if I were to properly encrypt an image, it would look like random color noise. I assume since you refer to the "shredding" style this is not aesthetically acceptable?
aydiosmio 7 months ago
Quotient: Would this (lossless) output be okay for this (1800x1200) input?
alixaxel 7 months ago
Do you have a max length for the encryption key ? must it be very resistant to decryption ?
kerncy 7 months ago
Alix- is it possible to get back to the original from your " shredded" image? Or is it resized ...basically the same but smaller?
Qdev 7 months ago
Kerncy- good question. I didn't have anything in mind just yet. Id say 1kb would be the max so I can communicate it through most message bus systems or in a single tcp packet.
Qdev 7 months ago
@Quotient: Yes, the encrypted image will yield the original image on decryption, pixel by pixel (working on the decryption now). I was only asking because it's not actually shredded, but rather encrypted.
alixaxel 7 months ago
awarded to kerncy

Crowdsource coding tasks.

3 Solutions


My solution as a command-line interface.

Usage

php imageCrypt/encrypt.php /path/to/image.EXT "secret key"

Outputs encrypted image to /path/to/image.EXT.encrypted.png on success.

php imageCrypt/decrypt.php /path/to/image.EXT.encrypted.png "secret key"

Outputs decrypted image to /path/to/image.decrypted.EXT on success.

Demo (Original Image)

$ php encrypt.php /home/alix/Desktop/gmcjXqt.jpg "heisenberg"
Image encrypted successfully to "gmcjXqt.jpg.encrypted.png".

Encrypted

$ php decrypt.php /home/alix/Desktop/gmcjXqt.jpg.encrypted.png "heisenberg"
Image decrypted successfully to "gmcjXqt.decrypted.jpg".

Decrypted

Limitations

  • Transparent PNG sections will be black.
  • Image width / height must have a maximum of 65280 pixels (each: 4,261,478,400 pixels in total).

Requirements

  • PHP 5.4+
    • GD
    • Mcrypt
I can't dive in to the code just yet, but how big is the key? Thx for the quick solution here
Qdev 7 months ago
@Quotient: The key is derived using 100 rounds of PBKDF2 and random salting. I'm using the blowfish encription algorithm in CBC mode (the most secure) and a random IV (each time you encrypt the output will be different). That makes the maximum usable key size to be 56 bytes (not bits) long (you can input more, but it won't be used).
alixaxel 7 months ago
Other q for you. I need to be able to process these on mobile. My initial fear of encryption vs "shredding" was around CPU and memory. The encrypted approach has obvious merit but I'm worried about resources on a phone when we try to implement this on native code. Do you think the process will be intensive in a resource constraintes environment?
Qdev 7 months ago
@Quotient: CPU-wise is pretty fast IMO: https://gist.github.com/anonymous/aba7bafe396562efd954, and you can reduce the number of PBKDF2 rounds as well - making the speed increase in PHP would likely require bigger blocks and thus less obfuscation. As for the RAM consumption, I can tell you that ~100MB were not enough to decrypt the 1800x1200 image, but I'm pretty sure that's PHP fault - it's garbage collection sucks when dealing with big arrays and concatenated strings (and that's what I'm doing to convert from RGBA to a hex representation). The amount of memory necessary should be (w * h * 6) bytes, with a peak memory usage about twice as that; that gives 13MiB / 26 MiB for a 1800x1200 image or 3MiB / 7 MiB for the a 695x800 one.
alixaxel 7 months ago
@Quotient: One more thing regarding the RAM usage: PHP/GD stores the image in RAM as a bitmap so just opening a big image should hog your memory quite a bit. I don't know if more efficient libraries exist for iOS / Android.
alixaxel 7 months ago
Winning solution

Here is a first version of the solution : http://www.simfonia.fr/bounty/bountify/imagePng.php
For the moment, you cannot upload an image but you can use the existing samples (or upload your image to your own server) and the png transparency is not handled. It will be solved in the next few days.

Is it something like that that you wanted ?

source code is here : https://www.dropbox.com/s/6fbapl170js907o/imageShredder.zip

Good work!
alixaxel 7 months ago
This kind of 'encryption' is vulnerable to the algorithms mentioned in Quotient's post.
tomtoump 7 months ago
Tom we are vulnerable here but our goal to make it really tough to out back together. I think this is done by making more pieces and other weird things like color replacement, color inversion etc... If it takes a big computer a few days to de-shred l 1 image then we've done a good job.
Qdev 7 months ago
I can add more pieces and other stuff to shred the image, but it will take a bigger key, as I'm storing the whole transformations in it. Do you want me to make it configurable but with a potential bigger key ?
kerncy 7 months ago
Yes, I'm fine as long as we have a 1kb key here. Do you by chance know how to run any performance metrics like the encryption submission?
Qdev 7 months ago
Sorry but i will not have time to improve the algorithm. For the key length, it depends on the number of pieces the image will be splitted. I store each transformation in the key using 2bytes convertex into HEX char (4 char for each pieces). For the moment, I use a 16x16 = 256 pieces, that results in a 256x4=1k key length. Each time you add subdivision, the key will continue to grow. I can go up to 128*128 pieces (in 2 bytes), but this will result in a 64k key.
kerncy 7 months ago
For the performance, the ram needed is low. We need the ram used to store two pictures (normal and shredded) as a bitmap - like aliaxel said - and an array of 16x16x4 int = 4kb. The memory comsuption is very low.
kerncy 7 months ago
@kerncy: There seems to be a bug with non-squared images, see http://i.imgur.com/vpKpFcL.png.
alixaxel 7 months ago
Aw I haven't seen that. It mustn't be hard to correct, but I won't have time to correct it before the bounty expiration as I am at work till 6:00PM (GMT+2).
kerncy 7 months ago
Just for information, I have uploaded a new version that corrects the bug of the non-squared images.
kerncy 7 months ago

I took a different approach. Instead of using cryptography to encrypt the pixel data of the image what I do is just scramble all the pixels when encoding and then perform the opposite operation to decode. I don't use any crypto library just python random functions.

The key is randomly calculated every time and image is encoded

The only problem is that the image loses some quality, not sure why but if your just interested in the algorithm this should be enough

Usage

python shredding.py encode in_file out_file
python shredding.py decode seed in_file out_file

Code

You can find the code here

#shredding.py
from PIL import Image
from os import urandom

import random 
import sys


def encode(in_file, out_file):
    # read pixel data from the image and put it in a flat list
    im = Image.open(in_file)
    data = list(im.getdata())

    # generate a random seed which will be the key and shuffle the data
    seed = urandom(20).encode('hex')
    random.seed(seed)
    random.shuffle(data)

    # create and save the new image
    out = Image.new(im.mode, im.size)
    out.putdata(data)
    out.save(out_file)
    return seed

def decode(seed, in_file, out_file):
    # read the pixel data from the image and put it in a flat list
    im = Image.open(in_file)
    data = list(im.getdata())

    # we need to perform the inverse operation we did in encode
    # with the seed we create a list with the original indexes
    order = range(len(data))
    random.seed(seed)
    random.shuffle(order)

    original_data = [0] * len(data)
    for index, original_index in enumerate(order):
        original_data[original_index] = data[index]

    # create and save the decoded image
    out = Image.new(im.mode, im.size)
    out.putdata(original_data)
    out.save(out_file)

def usage():
    print "usage:   shredding.py encode in_file outfile"
    print "         shredding.py decode seed in_file out_file"

if __name__ == '__main__':
    if '-h' in sys.argv or '--help' in sys.argv:
        usage()
        sys.exit(0)
    elif 'encode' in sys.argv:
        seed = encode(sys.argv[2], sys.argv[3])
        print "File successfully encoded"
        print "Seed:", seed
        sys.exit(0)
    elif 'decode' in sys.argv:
        decode(sys.argv[2], sys.argv[3], sys.argv[4])
        print "File successfully decoded"
        sys.exit(0)
    else:
        usage()
        sys.exit(0)

Sample usage

Using the same image as the first solution

Encoding

python shredding.py encode heisenberg.jpg encoded.jpg
File successfully encoded
Seed: f1db4632b925975f9f17b22635dcb35d1e4b84ae

Decoding

python shredding.py decode f1db4632b925975f9f17b22635dcb35d1e4b84ae encoded.jpg decoded.jpg
File successfully decoded

Images

Cool- Can you post a couple before/after images + the key for the function?
Qdev 7 months ago
I update the solution with a sample usage. The key is randomly chosen with each encoding (seed = urandom(20).encode('hex')) in this case a 20 byte string and is outputed when you encode the image To decode you need this same seed. Like I said the image loses some quality
rodmar 7 months ago
@rodmar: Weird, the image goes from 209KiB to 330KiB and down to 128KiB. Now that I think about it, do you think that (and the lower image quality as well) has something to do with the [en/de]coding to JPEG format? Seems like a strong possibility.
alixaxel 7 months ago
@rodmar: Also, I think the main bottleneck is the individual pixel operations and not the encryption itself.
alixaxel 7 months ago
@alixaxel: There is probably a problem with the encoding to jpeg. I didn't spend much time looking for the problem because in the description the author says is only interested in the algorithm and I only presented an alternative without encryption, just pixel manipulation, more in line with the examples presented in the description
rodmar 7 months ago
View Timeline