2
$\begingroup$

I'm trying to develop an encryption technique for encrypting short phrases (such as reversibly-anonymized names) in text. The key-generation and ciphertext-representation details are fungible, but most of the techniques I'm envisioning would be best facilitated by a function with the following properties:

I want to encrypt multiple plaintexts with a common key (which is expected to be at least 256 bytes) in such a way that the encrypted string is no larger than the source text (which may be compressed with a short-string-compression algorithm like smaz, both keeping the data small and increasing input entropy).

I looked at common symmetric-encryption ciphers like AES and Salsa20, but the block sizes of both of these result in the output being significantly longer than our input (which may be as short as a single byte).

Since my key material is expected to be almost always longer than the input, I also considered using a one-time-pad approach like just simply XORing the input against the bytes of the key, but this is subject to a trivial known-plaintext attack: if an attacker can guess one encrypted string's input representation, they can can obtain a partial key that can decrypt any other string of that length or shorter by XORing against that plaintext.

I also considered a stream-cipher-like approach using each byte as a block, but that had the issue of inputs with the same prefix having the same prefix when encrypted (ie. if I know "John Smith" encrypts to "ABCDEFGHIJ", then I know "ABCDEKLMNOPQ" is another string beginning with "John").

Is it possible to symmetrically encrypt multiple shorter-than-the-key byte sequences (without nonces) in such a way that

  • the output is the same length as the input,
  • inputs with similar subsequences (eg. identical prefixes) don't have matching (partial) ciphertext,
  • and other plaintexts can't be derived from a known plaintext (or at least, not trivially)?

It feels like what I'm asking for is a block cipher that can operate on blocks of any width from $8$ to $n$ (where $n$ is the length of the message, or at least the length of the key). Does such an algorithm exist?

Improve this question
$\endgroup$
3

2 Answers 2

Reset to default
1
$\begingroup$

The Hasty Pudding cipher has modes that operate on blocks of any size, though ciphertext appears to always be in blocks of 64 bits.

The Speck and Simon ciphers have modes that operate on 32-bit blocks, though these modes only use 64-bit keys (meaning you'd have to truncate the rest of the key material).

For smaller block sizes, there have been a couple questions on Stack Exchange asking about 8-bit block ciphers:

However, it's pertinent to note that your block size doesn't have to dictate the size of your ciphertext: you can use ciphertext stealing with cipher block chaining and a suitable initialization vector to shorten your ciphertext to the same size as your plaintext. (The original question did specify "without nonces", but depending on your algorithm, a null IV may suffice - within sixteen bytes, I believe AES will still meet the indistinguishability criteria in this case, though beyond that, you would need to worry about identical blocks.)

Improve this answer
$\endgroup$
6
  • $\begingroup$ Ultimately, though, in practice, you rarely find yourself needing to encrypt runs of data smaller than 32 bits: if you want a way to embed small references to encrypted values in unencrypted data, rather than diving into the world of esoteric encryption methods, you should consider some kind of lookup table for your (conventionally) encrypted values, which can be referenced by partial prefixes (which, assuming sufficient cryptographic entropy, will likely be unique in far fewer bits than your original value, encrypted or not). $\endgroup$
    – Stuart P. Bentley
    Jul 30, 2019 at 7:32
  • $\begingroup$ CBC (with or without ciphertext stealing) with a null IV is not secure if the same key is used to encrypt more than one message. Also, ciphertext stealing doesn't really work for messages shorter than one block unless an explicit IV is sent as part of the ciphertext (and can be truncated to save space). $\endgroup$
    – Ilmari Karonen
    Jul 30, 2019 at 8:50
  • $\begingroup$ @IlmariKaronen Aren't null IVs only a problem when encoding more than one message in cases where the first sixteen bytes may be identical (which would be outside the scope of the small plaintexts this question is asking about)? $\endgroup$
    – Stuart P. Bentley
    Jul 30, 2019 at 9:41
  • $\begingroup$ True, CBC mode with a fixed IV can be secure if no two messages have the same first block. In particular, for single-block messages, CBC mode with a fixed IV is equivalent to just applying the raw block cipher (after possibly XORing the message with the constant IV, which has no real effect on security), which (by definition, for a secure block cipher) is secure in the sense of being indistinguishable from a random permutation of the message space. $\endgroup$
    – Ilmari Karonen
    Jul 30, 2019 at 9:52
  • $\begingroup$ ... But in that case your ciphertexts will always be (exactly) one cipher block long, and ciphertext stealing won't help since you won't have an explicit IV to steal bytes from. (If you did transmit the fixed IV alongside the ciphertext, then you could in principle steal bytes from it; but then your ciphertext plus IV would still always be at least one ciphertext block long, so that gains you nothing.) $\endgroup$
    – Ilmari Karonen
    Jul 30, 2019 at 9:54
1
$\begingroup$

Why don't you use a stream chiper like RC4? (ok, RC4 is known to be broken, but there are many others). Am I missing something from your question?

Improve this answer
$\endgroup$
2
  • $\begingroup$ See the fifth paragraph of the question. Using a stream cipher would cause inputs with identical prefixes to have identical ciphertext prefixes. $\endgroup$
    – Stuart P. Bentley
    Jul 30, 2019 at 23:28
  • 1
    $\begingroup$ @StuartP.Bentley absolutely not. A stream cipher is designed to produce a never ending sequence of pseudo random bytes which you XOR against your plaintext messages. Messages that start with the same byte sequence will get encrypted as completely different cypertexts. That's paramount for a stream cipher. Of course, if you are resetting the stream cipher for every message, then you'll get into the problem you are referring to $\endgroup$
    – Gianluca Ghettini
    Jul 31, 2019 at 8:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.