Lenticrypt: A Provably Plausibly Deniable Cryptosystem | Hacker News Reader

Lenticrypt: A Provably Plausibly Deniable Cryptosystem

sultanik.com

53 pointsvolker4818 comments

In fact, Lenticrypt has the theoretical property that, under reasonable assumptions, there is always a near 100% probability that there exists an key in the public domain that will decrypt a given ciphertext to any desired plaintext, even if that key is not known.

This can't be true; there are more possible plaintexts than there are keys in the public domain.

Interesting miss here.

This system provides a way for someone to "comply" with a request to decrypt an encrypted file, without giving up the encrypted file. So if you had the 'books' from the drug cartel on your laptop as an encrypted spreadsheet you could also encrypt an innocent (but private) business ledger into the same file. If the border guards say "Give us the password to decrypt this file." You comply, and they see your private business ledger which you would have every reason to protect while traveling. They don't see the Cartel's ledger, which would incriminate you.

Minor pet-peeve. But we should probably refrain from immediately jumping to "drug cartel" examples. It only further perpetuates the meme that privacy is only something criminals and perverts should be concerned with.

Why not "Erotic messages with my wife", "My medical records", "My business plan", "My home videos", or any other number of things most regular people probably don't want anyone snooping around.

Fair enough. But you did understand that this tool is a way to decrypt something, under duress, which provides a credible plaintext rather than the actual plaintext right? And if someone asked you decrypt your "home videos" under duress and you used the alternate key to decrypt the "cat videos", the people forcing you to do the decryption might be suspicious that you're encrypting cat videos at all.

Can anyone who's knowledgeable about cryptography and cryptographic programming chime in on whether this is uses decent algorithms and is reasonably well-implemented? I've kicked a similar idea around in my mind, but had the good sense to know I'm not the guy to build it.

This appears to be an implementation of a 'One-time pad': http://en.wikipedia.org/wiki/One-time_pad.

The difference is that we are using publicly available streams of data (book text, encoded youtube video bytes, etc) instead of truly random data as the key.

This scheme takes advantage of the fact that with a one-time pad you can provide a key that will decode it to any possible plaintext (of the proper length).

As for the security, using non randomly generated keys makes it harder to make any security claims about this technique. One-time pads are also subject to numerous side channel attacks, including arbitrary message modification.

It's not at all an implementation of a one time pad. Though I'm not getting what extra level of plausible deniability this is supposed to add over the absurd "I can decrypt anything to anything with a one time pad, so nothing is copyright infringement" argument.

Edit: IIUC, it works like this. Let's say plaintext1[1] == 'a', and plaintext2[1] =='b'. Then ciphertext[1] = i, with i chosen such that key1[i] == 'a' and key2[i] == 'b'. Of course this means that you'll be repeatedly using the same key material which is very much not how an OTP works, and will most likely be blowing up the data by a factor of 4 on encryption (each byte becomes a word).

It seems like it doesn't work that way

>Unlike alternative plausibly deniable cryptosystems like the recently discontinued TrueCrypt—whose ciphertext size grows in proportion to the number of plaintexts (i.e., hidden volumes) it encrypts—Lenticrypt's ciphertext size is proportional to the largest plaintext it encrypts.

I'm pretty sure it works that way. Which part of what you quote conflicts with what I wrote?

If you're objecting to the claim that the ciphertext will be blown up, please note the word 'proportional' in there. Producing a word of output for every input byte of the largest input file is still proportional. All that's saying is that the bloat factor is the same whether you're encrypting 2 files or 10. (The claim they're making here seems pretty worthless anyway, since the required key size will grow absurdly quickly as the number if input files is increased).

I don't feel that the claim is even correct, that the size of the output is proportional to the largest size. I mean, assume that the largest size is 1024 bytes. Then take two files that are gigabyte each into 1024 byte chunks. Make a function that encrypts each chunk into the appropriate chunk in the second file. I don't think this is possible to do without being on the order of a gigabyte (the number of documents being encrypted).

If it behaves like a one-time pad, where f(d1, k) = d2, and you can find a d' such that f(d', k) = d3, then it means that d' is likely to be gibberish and I don't understand what this is doing.

Oh you're right. But the key must increase linearly with the size of the plaintext that is being decrypted. So I don't think it has any advantages over a one time pad.

What's the advantage of this system over a one-time pad? Does it have any properties that a OTP does not have?

I'm going to play with this to observe the behavior of the ciphertext, but I'm a priori skeptical that the ciphertext size will not approach the summed (compressed) size of the original cleartexts. Otherwise, you'd achieve theoretically impossible compression (e.g., a million 1k texts compressed into n<<1Gbyte).

I probably don't understand the requirements for the keys; do they need to be at least as long as the cleartext? Otherwise, there's a bug:

With copies of keys and cleartexts from /usr/bin, I tried

./lenticrypt.py -e eqn shotwell -e grep php -o f1

php was the largest cleartext at 4388Kb. Memory use by lenticrypt stopped growing at 474Mb. The eqn and grep keys were both about 148k. After 15 minutes (on an admittedly rather old laptop, though very high end six years ago) and 57% encrypted, the program suddenly exited with no error and status 0, and f1 at a size of 6468K. Regrettably,

    bash-4.2$ ./lenticrypt.py -d eqn f1 > shotwell.d
    Found length header. File format version is 3
    Traceback (most recent call last):
      File "./lenticrypt.py", line 773, in <module>
        for byte in decrypt(args.decrypt[1],  args.decrypt[0]):
      File "./lenticrypt.py", line 630, in decrypt
        file_length = struct.unpack("<Q", raw_length)[0]
    struct.error: unpack requires a string argument of length 8

[Edit] the 15 minutes were spent with one core at about 100% CPU use. L1 cache 32k, L2 cache 4Mb, no L3 cache. DDR2-667 memory.

Hi, I'm Evan Sultanik, author of this toy cryptosystem. (Emphasis on "toy.") My intention was never for this to be a commercial grade cryptosystem, nor was the focus ever on truly securing the ciphertext. I suggest you read the PoC||GFTO article from issue 0x04, as it goes into more detail about the motivations than my short blog post. My claims about the probability of a key existing in the public domain that decrypts a given ciphertext to any desired plaintext makes the assumption that the ciphertexts and plaintexts are all English language books. This was glazed over in my blog post (once again, cf. PoC||GTFO 0x04). The math behind that claim was first developed in an older blog post: http://www.sultanik.com/blog/copyright-quandry which itself was motivated by a much more abstract thought experiment in what it means to infringe upon a copyright.

Based on reading POC Issue #4, this looks more like "compression" with a dictionary shared "out-of-band".

For an extremely contrived example:

Intended Plaintext for Alice: HI

Intended Plaintext for Bob: BY

Communicate to Alice that the key is : HITIME

Communicate to Bob that the key is : BODYME

"Cyphertext": Index 1, Index 4

Tell the government that the key is : NOHOME

FTFA: In fact, Lenticrypt has the theoretical property that, under reasonable assumptions, there is always a near 100% probability that there exists an key in the public domain that will decrypt a given ciphertext to any desired plaintext, even if that key is not known.

Isn't that true of any cryptosystem?

EDIT: follow-up is correct; this is only true of OTP. Sorry for the noise.

no, not at all. even with a keyspace of 2^256, the number of possible plaintexts that make sense is an infinitely small portion of all plaintexts - you can say with reasonable certainty then, that only one plaintext, combined with the the key could produce that ciphertext.

the only system that has this same property (as far as i know) would be the one-time-pad.

my crypto is a bit rusty, so i may be wrong..

This system can't have that property for the same reason.

#desired plaintexts > #public domain keys

Reply on news.ycombinator.com