last day (17 days later) » 

6:37 PM
2
A: Can an arbitrary physical image be a key?

Meir MaorThe 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 simp...

 
I don't know a practical realization of the answer's general outline that manages to generate a key usable for a standard cryptosystem with acceptable failure rate. What I believe doable is to scan, digitally process to output a key and Error-Correction Data, so that another scan and the ECD reliably yields the same key usable for a standard cryptosystem. For a symmetric cipher and CPA security, I'm ready to believe ECD needs not be secret, and even not trusted, thus could be in ciphertext. I wonder for the condition in note 3 (or CCA), and asymmetric crypto.
 
If I scan a 5MB image and reliably produce as little as 10k biased correlated bits which are exactly the same each time. After hashing we should have enough real entropy.
 
I'm totally OK for 5MB raw scan, and 10k biased bit output as long as they have 128-bit entropy. Do you think this can be pulled (which would make ECD unnecessary)? Your comment starts with "If" thus that's unclear! I think the morphing argument in 1 of this answer implies that "Exactly the same each time" is mathematically bound to have exceptions. And I think it will have unbearably many for actual scans of natural images.
 
Let's start with something stupid, split the image into 4 squares and make it black and white. That gives us 4 poor quality bits but it is trivial to get the same bits each time with very high probablitly. The questions is how far up can we go. and my intuition is without proof we could go up with such techniques and get 10s of thousands of weak bits and after hashing still have 128bit entropy.
It's hard to be definitive without a concrete noise model for the scans. With a concrete noise model I could devise an algorithm and prove something about it.
 
The question considers an arbitrary image (and always has, though that's explicit only since version 12 of 2021-08-19). I'm OK to change that to most images a photographer would have taken and not rejected as lacking detail or something on that tune (which invalidates the morphing argument, as unstable images may be vanishingly rare). But I'm still excluding crafting the image specially to allow the system working; if we go that way, we can encode a key in a QR-code, that's common, and works just fine; or a card shuffle.
As to a noise model, I tentatively propose an 8 bit black&white scanner with 2 LSB Gaussian noise; a uniformly random rotation of the image scan within $\pm\pi/100$ (±1.8°); uniformly random de-alignment per X/Y (amount is uncritical if it exceeds a few pixels and the sides have some contrast, which we can assume); and (for lack of model, really) ignoring other blur, speckles, and deformations. I'll make a chatroom if we need to discuss that further. I'd be surprised if we can get stability without some ECD (aka FEC).
I have no doubt about getting enough entropy. What I stand unconvinced is that we can get stability of the hash from two scans, even made using the same high-quality scanner and from an original with edges that allow realignment, absent any FEC (in other ways, no communication from one scan-to-hash job and the other). I can supply two scans if you want. I do agree it's possible with FEC, or "helper" in the terminology of this extractor.
 
6:37 PM
FEC is just a form of picking a cannonical form. Picking the nearest valid vector can be seen as FEC. It can be looking for a low degree polynom matching most of the points in a a segment or it can be simpler. I think calling it FEC isn't correct when we start with arbitrary data and don't encode it. But we can use decoding methods commonly used with FEC if we want.
 
I disagree with "FEC is just a form of picking a canonical form. Picking the nearest valid vector can be seen as FEC." The problem is that noise is bound to sometime alter what's nearest. If you want to experiment, I scanned the same photo, 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 rectange of constant size. Here they are.
@Meir Maor: I really appreciate the effort you put in this.
 

  last day (17 days later) »