Can an arbitrary physical image be a key?

Question

Assume an arbitrary secret physical image¹, such as a privately made chemical Polaroid™ similar to this

Is there a feasible and secure way that this physical image could be used as cryptographic key, functionally equivalent to an AES key or RSA private key, without "accompanying² other digital data" beyond the physical image? We'll assume a scanner digitizes the physical image at each use, and all the rest is handled digitally.

We may want to distinguish 4 use cases

• Symmetric message encryption and decryption
• Symmetric message authentication and verification
• Asymmetric decryption of a ciphertext for a secret message, encrypted using a previously made public key
• Asymmetric/Digital signature of a message, publicly verifiable using a public key assumed authentic.

For asymmetric, there is the issue that contrary to traditional private keys, the physical image can't contain the public key, which needs to be prepared separately (from an independent scan).

Assume we want at least³ CPA security and EUF-CMA signature security; and we are ready to tolerate that cryptograms and public keys are large, the algorithms slow, and that legitimate decryption or signature verification fails with some low yet noticeable probability.

If that's not possible (I don't know a method⁴), can the necessary "accompanying² other digital data" be public? Does it's integrity need to be trusted? How large does it needs to be for various kinds of physical image, perhaps including biometric data (assumed private)? What standard name(s) does this "other data" have?

Late update (2021-09-08): I now wonder if for symmetric crypto we could use the combination of

• image preprocessing as in this answer;
• Ran Canetti, Benjamin Fuller, Omer Paneth, Leonid Reyzin, Adam Smith: Reusable Fuzzy Extractors for Low-Entropy Distributions, originally in proceedings of EuroCrypt 2016;
• AES-GCM with the "helper" in the above passed as associated data, and key the "extract".

---

¹ The question was initially asked for biometric data assumed private and acquired in a socially acceptable way. Say, a retina scan, and there's an unfalsifiable method to recognize safe retina scanners from those that will keep a copy of the scan or burn the user blind, and eye doctors did not keep archives, and key rotation was unnecessary. The main reason I mentioned biometry was to repel it for use as straight replacement of a cryptographic key, with hard security argument rather than just poorly meeting the functional goals.

² By "accompanying" I mean kept along the image, with the same secrecy and integrity. The question is thus excluding e.g. making marks on the physical image. But embedding in the ciphertext some data generated from a scan of the physical image would be game.

³ We'd additionally like that encryption remains secure under the assumption that an adversary can submit arbitrary ciphertexts to a decryption oracle, and gain knowledge of if the decryption was successful or not. This is tantamount to CCA security.

⁴ Main problem is that the outcome of a scan varies, and no algorithm can fix (in both senses of the term) it (at least, for all arbitrary images) into something directly usable as key in a standard cryptosystem, without some "other data". I suspect (robust?)fuzzy extractors may help to a degree, but I admit that my knowledge about them is itself fuzzy. It thus seems impossible to define a function that turn scans into a key for a standard unmodified symmetric cryptosystem like AES-CTR or AES-GCM, and have it secure and working acceptably reliably. To illustrate the difficulty I scanned a photo (not the one above), 5 times, using the same scanner with same setting (B&W 8-bit), just moving the image at each scan and manually moving a selection rectangle of constant size. Here are the scans. I believe that any deterministic algorithm that turns these scans into a stable key will either need to contain data extracted from one of the scans in order to get stable output for the others (and won't work reliably for most other set of scans made from different images), or will have insufficient entropy in it's output.

Answer 1

Please let me confirm the major problem to be noisy reading of private key information, so that most (all well-known) crypto schemes would fail. Error correction is the well-established area having proper math/tools to handle such a problem.

For a "noisy private key" signature, one would avoid actual correction, concentrating on "small distance/metric" decisions over private data while verification. One particular error correction scheme, Goppa codes, might be convenient to combine with Schnorr protocol to achieve such a signature, IACR 2008/359.

Sequence similarity might be another metric sometimes called Short Tandem Repeat (STR), and there are some forensic STR-identification databases around. One could approach such a metric with a sequence characteristic polynomial model and insertion/deletion counting (set membership). Having sequences replaced with polynomials, one would combine it with Schnorr achieving a proof of DNA similarity, IACR 2008/357.

Polynomial graph representation was a precursor for sequence characteristic polynomial (IACR 2008/363 and MFCS 2012), achieving graph isomorphism, hamiltonicity and coloring proofs with "large" challenges (not binary like 0 or 1); no errors or similarity metrics yet.

Secret polynomials would invite a Schnorr-like protocol with higher degree (more that linear, degree-1) polynomials in the challenge of verifier. Finally, all the results mentioned would require some computer algebra helper/library implemented to handle that higher-degree polynomials.

Answer 2

If you use at least 7 riffle shuffles to randomize a deck of 52 cards, and take a photo of the deck spread out just enough such that each letter/suite is clearly visible, that will give you a (log₂ (52!)) == 225 bit secret key for use in symmetric encryption. Then you could use key stretching to take you a little higher if necessary.

You could come up with similar schemes as long as you have enough control over the items being photographed to ensure there was no ambiguity. For example, you could drop a box of toothpicks on the floor, and then manually adjust each toothpick so it is roughly only at a 0, 45, or 90 degree angle prior to taking a photo. Key extraction would then use the angle of each toothpick to the nearest 45 degrees.

Answer 3

The challenging part is mostly about image processing, and not a lot about crypto. You want to extract from the image sufficient entropy in a reliable fashion.

It has a lot to do with how you use the image and your adversary model. If your adversary knows nothing at all about the image, some simple coarse features could be sufficient, if your adversary knows a lot about the image, e.g has gotten a glance at it, or knows aproximately where it was taken you need to be more careful on what information is extracted from the image and will need to use finer grained image features which will be hard to extract in a stable fashion.

If each time the image is used it is scanned in the same high quality scanner, and between usages it is kept safely so it doesn't fade, wrinkle or accumulate dust it would be easier to get scans very close to each other and have only simple auto alignment and discretization (spatial and color) to get almost the same bit sequence each time.

Then the question is what the error model we have for the scan results? Do we expect gaussian noise? salt and peper? alignment noise? rotation? addition of large continious pieces of noise? lighting noise? Each type of noise can be dealt with differently.

A general outline for a solution: We use image processing techniques to minimize the noise to move to a representation which eliminates most of them then you limit the space to only certain valid points and pick the nearest valid point to what we have to bring noise down to zero.

We will discretize aggessively enough and pick sparse enough valid points to allow us to get to zero noise reliably. At this point we should still have much more than the required key length but in a space still closely related to the original image and as such the bits will be be biased and correlated. Applying a cryptographic hash to that data should sort it out and allow us to have sufficient high quality key material derived reliably, and get the same key exactly any time you scan. This could be used as e.g an AES key.

If you want to create an RSA key you will need many more random bits. You can however extract as many bits as you can extract while still reliably getting same bits every time and use that to seed a cryptographic PRNG and use it to generate an RSA private key.

Edit: I didn't try to implement a full solution, but I did open a notebook and play with the noise model suggested, gaussian noise and shifts I believe are corrected easily, so I checked what happens if I rotate the image (with fancy interpolations) by 2 degrees and rotate back by 1.8 degrees I got a maximal diff (on the image above) of 33%, this is supportaive of my claim that by identifying best counter rotation and shift, lowering resolution and quantizing aggressively ignoring edges we should be able to get 1-2 bits per channel per ~25 pixel regions. For the above image it comes out at least 36K bits, and after hashing I bet this will have 128 bits of actual entropy

Edit2: I downloaded the provided images of grey scale scans, and played with them, I semi-automatically aligned at rotated the first two image.

img = io.imread("scans/scan078.tif")
img2 = io.imread("scans/scan079.tif")
imgr = transform.rotate(img,angle = -0.78)
imgr2 = transform.rotate(img2,angle = -0.805)
tr1=transform.rescale(imgr[:-10,:-6],0.1)[20:-20,20:-20]
tr2=transform.rescale(imgr2[10:,6:],0.1)[20:-20,20:-20]

This reads rotates each aligns and crops, downsamples 10x and crops to get rid of edges which may have artifacts. This gives a Maximal difference of less than 6% per pixel value. Which is pretty good. However this 6% diff can easily be around any cut-off we choose so even quantizing aggressively doesn't give 0 errors.

bin1 = tr1> 0.5
bin2 = tr2> 0.5

This gave a difference in 103 bits out of 27248 bits or 0.37% These errors appear to be reasonably spread out. This aggressive resizing and quantizing looses a lot of information but we probably still have enough. This is what the image looks like:

The errors are fairly well spread out(and we can always apply a fixed permutation or use larger symbols if needed). So now we can apply any error correction step (e.g Reed solomon) we will just take the decoding step (didn't actually do this) and we should get the same output from either image with high likelyhood and still have ~20K bits.

If we down scale 5x instead of 10x we get 816 differing bits. but get 4x as many bits, at 0.6% difference. Can play with this and find optimum.

We can also probably do better at the quantization step and preserve more information reliably. The aggressive quantization I used will work only for reasonably balanced photos, an over exposed picture will come out all a single value. We could add preprocessing to handle this scenario.