<div># Or, how to make storing ciphertexts cheaper for the NSA.</div><div>## (Answer: Keep using stream ciphers.)</div><div><br></div><div>Suppose that I worked for the NSA, and were tasked with storing every ECDH + symmetric key enciphered communication for eventual decryption.[^how] How could I save storage bandwidth and space, and store the maximum *information* possible?</div> <div><br></div><div>1. Chop the MAC from stored AE ciphertexts. (I trust what I know about where ciphertexts come from more than I trust the MAC.)</div><div><br></div><div>2. For any ciphertext which I believe to be padded, truncate material which is almost certainly padding. (E.g., for presumed exponentially-padded messages, truncate the last quarter.)</div> <div><br></div><div>3. For any message encrypted using a stream cipher or a block cipher in a chaining mode, use a linear code to compress the message.</div><div><br></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>3.1. *Stream ciphers*: a linear code can compress down to the entropy rate of the underlying plaintext distribution. (Trivial example, rate 8b code: presumed ASCII, truncate to 7 bits. Less trivial codes necessary for reaching the entropy rate. Entropy rate of JSON < HTML < English < .5.)</div> <div><br></div><div><span class="Apple-tab-span" style="white-space:pre"> </span>3.2. *Block ciphers in CBC or OFB mode*: use a block-level turbo code. See, e.g., Klinc's work at T.J. Watson.[^ibm] His constructions achieve -- for reasonable message lengths -- compression down to the entropy of the underlying plaintext distribution. (The story for CFB mode is more complicated.)</div> <div><br></div><div>This saves me a lot of money; the cost of decrypting everything sent today by solving discrete-log with a QC isn't the eventual computation. It's the storage costs until then.</div><div><br></div> <div>[^how]: Say, with a quantum computer, in twenty years or so.</div><div>[^ibm]: See [Klinc's thesis][klincthesis], p. 99 et seq. Or, the original paper: Klinc et al. [On compression of data encrypted with block ciphers][klincpaper]. (Note that the original *conference proceeding* does not contain a construction for CFB mode; the thesis and paper do.)</div> <div><br></div><div>## How to make storing ciphertexts more expensive.</div><div><br></div><div>Okay, so taking off my suit, bowler hat, and adorable bowtie for a moment.</div><div><br></div><div>### Preventing padding from being stripped</div> <div><br></div><div>Standard construction, proved secure by [Boyko in his thesis][boykothesis]. OAEP is an all-or-nothing transform:</div><div><br></div><div> len(packey) == len(k)</div><div> packey = randombytes(len(packey))</div> <div> ptext = keystream(packey, olen=len(plaintext)) ^ plaintext</div><div> phash = hash(ptext, olen=len(packagekey))</div><div> packagedkey = phash ^ packagekey</div><div> ciphertext = keystream(k, len(packagekey) + len(plaintext)) </div> <div> ^ concat(ptext, packagedkey)</div><div> </div><div>Except: Boyko's model is slightly too weak. The adversary here corresponds to his fully-adaptive adversary, which he doesn't prove anything about. </div> <div><br></div><div>Or are people content with the semi-adaptive proof?</div><div><br></div><div>### Preventing compression</div><div><br></div><div>Something that seems somewhat better than OAEP (more like [Rivest's original package transform][rivest97]):</div> <div><br></div><div> packagekey = randombytes()</div><div> packagetext = stream_xor([c]*32 + message, k=aontkey)</div><div> packagehash = hash(packagetext)</div><div> enckey = packagekey ^ packagehash</div><div> innertext = packagetext + enckey</div><div> ciphertext = aes_ecb(innertext, k=messagekey)</div><div><br></div><div>Is this mode's security reducible to OAEP's for message lengths below the birthday bound? (In particular, if AES-ECB is not a good block-cipher, then can AES be a good stream cipher?) </div> <div><br></div><div>As Klinc's paper notes, block ciphers in ECB mode are incompressible (or, rather, if they can be compressed, they are insecure). This would then provide a mode of operation that is an AONT with a simple proof of incompressibility.</div> <div><br></div><div>### Short messages.</div><div><br></div><div>It's not at all clear (at least to me) what to do about tag truncation, especially in the short-message case, where it's most profitable. (A tag can be >50% of an average IM message.) Perhaps one of the key-wrap modes?[^aeskw]</div> <div><br></div><div>Alternatively: Klinc's construction for CFB reaches the plaintext entropy distribution very slowly. His construction works on pairs of CFB blocks, and the compression bound on depends inversely on blocklength. (Though he doesn't prove, as best I can tell, that his construction is optimal except for the class of codes he considers.)</div> <div><br></div><div>So, his construction couldn't achieve any significant compression for the splendidly inefficient CFB-1. Thus, prefixing the tag to the ciphertext, and then encrypting both with CFB-1 seems like it would achieve prevent 'unbinding' tags with zero (space) overhead. </div> <div><br></div><div>References</div><div>------------</div><div>[coron08]: <a href="https://eprint.iacr.org/2008/24">https://eprint.iacr.org/2008/24</a></div><div>[rivest97]: <a href="http://www.csshl.net/sites/default/files/downloadable/crypto/Rivest_-_All-or-Nothing_encryption_and_the_package_transform.pdf">http://www.csshl.net/sites/default/files/downloadable/crypto/Rivest_-_All-or-Nothing_encryption_and_the_package_transform.pdf</a> "Rivest, Ronald L. *All-or-nothing encryption and the package transform.* In Fast Software Encryption, pp. 210-218. Springer, 1997."</div> <div>[boykothesis]: <a href="http://groups.csail.mit.edu/cis/theses/victor-phd.pdf">http://groups.csail.mit.edu/cis/theses/victor-phd.pdf</a></div><div>[klincthesis]: <a href="https://smartech.gatech.edu/bitstream/handle/1853/39610/klinc_demijan_201105_phd.pdf">https://smartech.gatech.edu/bitstream/handle/1853/39610/klinc_demijan_201105_phd.pdf</a></div> <div>[klincpaper]: <a href="http://arxiv.org/pdf/1009.1759.pdf">http://arxiv.org/pdf/1009.1759.pdf</a></div><div><br></div><div><div><font><span style="background-color:rgba(255,255,255,0)">[^aeskw]: It seems like AESKW prevents something like this, though it is entirely lacking when it comes to security proofs.</span></font></div> <div><font><span style="background-color:rgba(255,255,255,0)"><br></span></font></div><div><font><span style="background-color:rgba(255,255,255,0)">Curious, though: A six-round Luby-Rackoff Feistel network is an ideal cipher: What's the barrier (I assume there's an obvious one I'm missing) to assuming keyed AES is an RO, and proving that AESKW is an ideal cipher? Cf. the well-known [Coron et al.][coron08] ideal cipher construction. (I've repeatedly read that AESKW has 'resisted' analysis, but haven't found many publications analyzing it other than that Bellare-Rogaway SIV paper.)</span></font></div> </div><div><br></div>