25

I'm working on a cryptosystem that uses colour pictures as keys for encryption. I'm trying to guess what is the key size of my cryptosystem in order to find the feasibility of a brute force attack. My cryptosystem uses RGB pictures of any size M x N.

The picture is also generated by a chaotic attractor which is sensitive to initial values, so each picture generated is different. These pictures are an example:

colourful generated images

I haven't found a paper that tries to do the same calculation yet. Any idea on what the key size is?

psmears
  • 900
  • 7
  • 9
  • 49
    Why would you want to use a picture as an encryption key? – Anders Nov 05 '18 at 21:55
  • 76
    Your pictures being M x N in RGB would only be a useful metric if each pixel were to be randomly generated, which obviously is not the case given all the pretty gradients in your pics above. Instead, you should mention or link the algorithm used to generate them in the first place, so we can know the actual source of entropy used. – Will Nov 05 '18 at 23:52
  • 63
    In a comment on an answer, you wrote "basically the picture will be generated by both users given an initial condition, i'm still thinking on the way to make this exchange secure." If the picture is generated by **both users,** they have to have some shared knowledge already. You're raising more red flags here. The pictures are really cool, but coolness does not improve the security of a cryptosystem. :) – Wildcard Nov 06 '18 at 00:19
  • 28
    And the pictures have patterns. You do NOT want patterns in your cryptographic keys. – Nelson Nov 06 '18 at 01:31
  • I agree with Anders, why would you ever look at another person's key or show yours to anyone else? The visual aspect of a key isn't appealing in the slightest. Why do you think door keys haven't changed design over the years? Because no one cares, it's just a stick in the hole. – insidesin Nov 06 '18 at 08:04
  • 3
    @insidesin Door keys have changed design dramatically over the years. From [ancient Roman keys](http://www.sadighgallery.com/assets/images/30000/35780.jpg) to [medieval keys](https://is.gd/dHJjoV) to [20th century brass keys](https://www.vandykes.com/images/xl/206677.jpg) (still in use in England) to [modern simple keys](https://www.ddlc.co.uk/storage/app/media/single-key.jpg) to electronic keys. Walking through an old English town you can often see doors with 3–4 generations of locks (and thus keys) on them. – gerrit Nov 06 '18 at 10:50
  • 3
    Passing the 3D *object* as the key might be interesting, but an image is just an image (and your examples have a lot of patterns). Why does the image need to be recognisable? Why not a visual representation of a real, and cryptographically secure key? – schroeder Nov 06 '18 at 10:52
  • @insidesin See [The history of the key](http://www.slate.com/articles/arts/design/2012/05/the_evolution_of_everyday_objects_the_key_the_book_the_phone_and_more_.html), for example. – gerrit Nov 06 '18 at 10:54
  • 1
    Does your system actually use the pictures as the key, or does it use the input parameters of the generator as the key? What does it do if you give it a photo that was not generated in this way? (A picture generation system like this might be better off used for fingerprint verification a la randomart/bubble-babble, rather than as a key) – Random832 Nov 06 '18 at 15:08
  • 1
    @Random832 The system uses it as a key, in fact the system operates the pixels of the generated image with the image i'm encrypting. If you give it a photo that wasn't generated that way it will still work, but the idea is to just limit it to the pictures generated by the attractor. – Daniel Esteban Ladino Torres Nov 06 '18 at 21:02
  • @schroeder it doesn't need to be recognisable, my system operates the pixels of the original image and the key pixels to encrypt the information, i'm only encrypting multimedia. – Daniel Esteban Ladino Torres Nov 06 '18 at 21:04
  • @gerrit yes that proves my point. – insidesin Nov 06 '18 at 23:11
  • @gerrit No you're wrong, they haven't changed design at all. They have and will always be a decorated stick with an undercoated end... – insidesin Nov 06 '18 at 23:12
  • 3
    In addition to all other mentioned concerns, generating something in 3D with a certain entropy, and then flattening it to 2D may have an unpredictable impact on the entropy. (You may get the same 2D picture from numerous different 3D shapes). – Dennis Jaheruddin Nov 07 '18 at 13:31
  • At least one commercial software system already use images for product registration keys, but I don't know anything about the steganography which includes the security code in the image. The images themselves look similar to a credit card, with the unsecure information (owner's name, etc) plainly visible. http://ploguearia.pairserver.com/faq/index.php?solution_id=1097 A brute force attack on a 476x308 pixel image, when you have no idea what you are looking for in the image, doesn't seem feasible unless the implementation was really "intellectually challenged"). – alephzero Nov 07 '18 at 18:15

6 Answers6

99

Your most recent edit indicates that your pictures are procedurally-generated, so your key size will therefore be bounded by the amount of state required to generate an image. Yours seem to be parameterized by four floats for the initial conditions (and fixed output image size, camera location, point light location, convergence conditions, etc).

Those 128-bits of state will then be transformed into an image by an algorithm that depends solely on your provided state, so your image "key" cannot contain more than 128 bits of information. In fact, I think that entire classes of initial values produce identical outputs (e.g. when all four floats are extremely small), so your image "key" size will be strictly less than 128-bits.

There's really no benefit to touching the 128 bits of state by turning it into an image (and then somehow back) if you only reduce the size of the key by doing so.

Blender
  • 1,406
  • 3
  • 10
  • 10
  • 15
    *"...if you only reduce the size of the key by doing so."* Might be worth emphasizing that he will *always* be reducing the size of the key by doing so. – Wildcard Nov 06 '18 at 00:13
  • 5
    @Wildcard He won't reduce the size of the key if and only if the image generating function is injective. – Vaelus Nov 06 '18 at 06:10
  • 3
    This. Additionally, a roughly 65kB key isn't very useful (unless the image itself was to be used as OTP, which would be _most unwise_ seeing how it's procedural), so the image would have to be processed to output a... whatever, 128 or 256 bit key (also to account for compression artefacts or missing parts / cropping which isn't uncommon stuff to happen with images). So that's an _awful lot_ of processing, room for error, and more or less zero net gain over just "key". – Damon Nov 06 '18 at 10:55
  • 1
    There is potentially some benefit to mapping the state space $[1, \ldots, 2^{128}]$ bijectively to some $A \subset B$ where $|B| >> |A|$ and $B$ is known (say, all 256x256 images) but $A$ is not. For example, it may be infeasible to iterate $A$ directly and if the bijection is slow then iterating $A$ would be slow. But images are probably not the best way to do it - iterating a slow hash would suffice. – Reinstate Monica Nov 06 '18 at 15:16
22

A picture is far too large to use as an encryption key directly, you'll want to run it through a KDF first.

It also depends entirely on the picture whether it will have enough entropy to be useful. You could have a 1000x1000 image that's solid white, but it would be useless as a key as it contains no entropy. Pictures from cameras tend to have a fair amount of entropy in the lower bits, so that could be ok, but your users would need to understand that not just any picture is a good key.

Pictures as keys is in general not a great idea. Pictures are usually taken to be shared, and keys are something you don't want to show to everyone. Using a picture as a key also sounds to me like it could be relying on security through obscurity (i.e. you just use an image from the thousands you have on your computer, but that's effectively very low entropy, probably under 20 bits unless you have an insane number of pictures).

Feel free to continue developing this for the sake of learning, but until you have a much better grasp of cryptography it's better to leave this sort of thing to the experts (see Why shouldn't we roll our own?).

AndrolGenhald
  • 15,506
  • 5
  • 45
  • 50
  • 1
    I get you point, my bad I didn't mention which kind of picture I'm using as a key, actually I'm using 3d images generated from a chaotic attractor, such as the quaternion julia set. – Daniel Esteban Ladino Torres Nov 05 '18 at 21:26
  • 21
    @DanielEstebanLadinoTorres: That's as low-entropy as the amount of entropy that gets fed into your generation process, which is probably far too low to be safe. – user2357112 Nov 05 '18 at 22:55
  • 10
    @DanielEstebanLadinoTorres I'm guessing you're not fully understanding what entropy really means. Learn that first and then try to understand why people are advising you to not use pictures. The pictures are **cool**, yes, but they're **not good for encryption**. You need to understand why. – Nelson Nov 06 '18 at 01:32
  • 8
    @DanielEstebanLadinoTorres A chaotic attractor does not _generate_ entropy, and is still a deterministic process. A chaotic attractor can only be useful if the initial state is perfectly random. – forest Nov 06 '18 at 11:44
10

Any cryptosystem should have keys with keysizes at the 128, 192, and 256 bit-of-entropy security levels.

So the question comes back to you: where are these images coming from and how much entropy do they contain? If they are completely random bit streams that are being interpreted as an image, then (ignoring entropy loss from lossy compression codecs), you get log_base2(256x256x256) = 24 bits of entropy per pixel, so you'd need 6 / 8 / 11 pixels respectively for the 128 / 192 / 256 bit security strengths.

If you're not generating completely random images and instead allowing people to use, like, photos, then I have no idea how you'd even begin estimating the amount of entropy in one of those.


Bottom line: using images as key material seems like a really odd thing to do and conflicts with the common practice that key material be completely random data from a cryptographic-strength RNG.

Also, from the information in your question, I'm not convinced that brute-force is the attack you need to worry about; I'd be more concerned with the "get access to their laptop and try every image on their hard drive" attack.

Mike Ounsworth
  • 58,107
  • 21
  • 154
  • 209
  • My bad, i'm using quaternion julia sets to generate the image, since they are sensible to initial conditions. So the pictures are like 3D shapes – Daniel Esteban Ladino Torres Nov 05 '18 at 21:24
  • 1
    @DanielEstebanLadinoTorres I have no idea what that means in terms of entropy. Link? – Mike Ounsworth Nov 05 '18 at 21:26
  • Ounsorth here is an example: https://www.cs.cmu.edu/~kmcrane/Projects/QuaternionJulia/teaser.png https://www.cs.cmu.edu/~kmcrane/Projects/QuaternionJulia/ – Daniel Esteban Ladino Torres Nov 05 '18 at 21:28
  • @DanielEstebanLadinoTorres Hmm, how strong are your statistics skills? The question here is basically "On average, how many do you need to generate before you get two identical?" Once you know how to estimate that, then you're free to adjust image size, complexity of the shape, etc so that you can safely generate 2^128 / 2^192 / 2^256 before you get a collision, and there are no exploitable short-cuts that an attacker can take to reduce how many guesses. – Mike Ounsworth Nov 05 '18 at 21:35
  • Well my statistics skills are just average, but i get your point, i'll keep it in mind, now i'll just focus on the entropy of the chaotic attractor. Thanks for your help! – Daniel Esteban Ladino Torres Nov 05 '18 at 22:51
  • 29
    @DanielEstebanLadinoTorres "now i'll just focus on the entropy of the chaotic attractor" - looks like you are missing the point. If your attractor generates an image based on 3 random bytes, you've got 24 bits of entropy at most. Any fault in the attractor which would make the result somewhat predictable may only make this worse, never better. So, you are ALWAYS better off just passing the initial random values to a well-tested cryptography algorithm. Nice pictures though, but putting them to a bad use kinda devalues them. – IMil Nov 05 '18 at 23:40
  • @IMil What stops the attacker making the exact same image you made, and using it to decrypt your messages? – user253751 Nov 08 '18 at 00:31
7

I can tell from the images that your key size is significantly less than the size of the images (because otherwise most of them would look like random coloured static).

Your key size is less than or equal to the base 2 logarithm of the total number of different images your chaotic attractor program can generate.*

That's another way of saying your key size is less than or equal to (probably less than) the amount of bits it takes to specify all of the inputs to your chaotic attractor program.

If you hash the image and use the hash as a crypto key, your key size is equal to or less than the size of the hash.

*That's your exact key size if your encryption algorithm is something like "XOR each bit of the image with the corresponding bit of the plaintext" (don't use that algorithm for important secrets, BTW, because parts of the message covered by the grey areas in your images could be super easy to decrypt).

Robyn
  • 501
  • 3
  • 4
3

tl;dr- You're proposing a key-stretching algorithm that turns 128 bits of input into a much larger key. This isn't as good as simply using a much larger key of the same size, though it's not necessarily as weak as the 128 bits of input. That said, your bitmap looks very ordered, which strongly suggests that it's far weaker than a randomly generated bitmap.


According to @Blender's answer, you're just using 128 bits to generate the picture. I'm guessing that you want the picture itself to count as a key larger than the 128 bits that you put into the algorithm that generated it. And it might.

Specifically, what you're trying to do is create a key-stretching algorithm that attempts to stretch 128 bits of input into a much larger key. This isn't necessarily fruitless, but there're things to be aware of:

  1. A key-stretching algorithm can be vulnerable to brute-force of the input. For example, even if someone couldn't reverse-engineer the picture-generation algorithm, they could try all $2^{128}$ possible inputs to generate all possible $2^{128}$ possible pictures, then try each. To guard against this, you'd need to ensure that the picture-generation algorithm is too expensive for such an attack to be feasible.

  2. Your picture looks far from random at local scales. This is, anyone looking at a few pixels of it can probably guess the neighboring pixels with better-than-random odds of success. This means that the algorithm isn't pseudo-random, even against an attacker who can't reverse-engineer the picture-generation algorithm.

  3. Your picture looks far from random at the global scale. This is, the displayed shapes have global geometry, plus the images waste pixels on a well-behaved background. This significantly weakens the pseudo-randomness again, potentially suggesting that it might be easy to fully break.

  4. There's no real advantage in a key-stretching algorithm producing a picture as opposed to any other representation of the same data. Granted, the stretched key does look pretty as a picture, but that prettiness merely reflects its weakness vs. a randomly generated bitmap.

This website seems to generate random black-and-white bitmaps with specified dimensions. For example, here's a $250 \times 250$-pixel bitmap:
                              .
This bitmap is (supposed to be) random in that an attacker looking at any combination of its pixels shouldn't have better-than-even odds of guessing what another pixel might be.


How much entropy?

Unfortunately this site doesn't have MathJax enabled, so it's hard to answer your question directly without it looking weird. Here I'll write a response as-though MathJax were available.

The set of randomly generated RGB images of a given length-and-width contains$${\left(n_\text{Red} \, n_\text{Green} \, n_\text{Blue}\right)}^{n_\text{width} \, n_\text{height}} \, \text{members} \,,$$where:

  • $n_\text{Red}$ is the number of possible values for a pixel's "red" dimension;

  • $n_\text{Green}$ is the number of possible values for a pixel's "green" dimension;

  • $n_\text{Blue}$ is the number of possible values for a pixel's "blue" dimension;

  • $n_\text{width}$ is the number of pixels in the width; and

  • $n_\text{length}$ is the number of pixels in the length.

Then since entropy is the $\log_2{\left(n_\text{members}\right)} ,$ this'd be$$ \begin{align} \left[ \text{entropy} \right] & ~=~ \log_2{\left( {\left( n_\text{Red} \, n_\text{Green} \, n_\text{Blue} \right)} ^{n_\text{width} \, n_\text{height}} \right)} \[5px] & ~=~ {n_\text{width} \, n_\text{height}} \, \log_2{\left(n_\text{Red} \, n_\text{Green} \, n_\text{Blue}\right)} \,.\end{align} $$

In the case of a black-and-white image:

  • $n_\text{Red}=2 ,$ since there're two possible values for the red channel;

  • $n_\text{Green}=n_\text{Blue}=1 ,$ since the values of the green and blue channels is defined to equal the red channel (such that all pixels are either black or white;

so the entropy'd be$$ \left[ \text{entropy} \right] ~=~ {n_\text{width} \, n_\text{height}} \, \log_2{\left(2 \times 1 \times 1\right)} ~=~ {n_\text{width} \, n_\text{height}} \,. $$

Nat
  • 1,443
  • 2
  • 11
  • 13
0

So, if you can manage to get past the inital problems involved in too small of keysize and too much loss, and use KDF after, there's a benefit to using these keys for auth after all.

The generation of that stuff must take forever in relation to a traditional hash, so if the initial parameters are treated like a password, password attack times will be slow.

But there's easier ways to get that. bcrypt() and friends scale up well.

Joshua
  • 1,090
  • 7
  • 11
  • This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post. - [From Review](/review/low-quality-posts/127636) – Vilican Nov 08 '18 at 11:43
  • I'd considered the time the generation takes as potentially adding "effective entropy", but that's only the case if there isn't a more efficient way to generate the image. It would need more study before use in cryptography, and of course as you mention Argon2 or bcrypt would be better anyway. – AndrolGenhald Nov 08 '18 at 14:09
  • @Vilican Nobody else mentioned bcrypt and friends yet. I'll withdraw mine for a better one. – Joshua Nov 08 '18 at 15:10