Can data over a very low bandwidth channel still be encrypted?

Question

If you have a very low bandwidth channel, can encryption still be used?

Another way of putting this might be, does encrypting well increase the size of the data significantly?

Are there good encryption techniques that keep the block size the same?

Answer 1

Yes, encryption can be without increase of the message size, even if the ciphertext is constrained to the same character set/semantic as the plaintext (e.g. to fit the semantics imposed in the body of an email). However some features beyond encryption cost message expansion, like:

1. Allowing decryption of any message that has not been lost in transport (rather than deciphering all messages after a lost one as gibberish); that feature is so basic that it is part of the modern academic definition of a cipher.
2. Integrity check, protecting against attackers forging or altering messages.
3. Public-key encryption, which allows the party enciphering to do so without holding any long-term secret key, but rather the public key(s) of the reveiver(s).
4. Digital signature, which allows any party receiving a message to check its integrity and origin without holding any secret key, but rather the public key of the sender.

---

For information coded as arbitrary bits or octets, the simplest form of encryption that does not expand size is exclusive-OR of the message(s) with a keystream generated by a Cryptographically Secure Pseudo-Random Number Generator seeded by a shared secret key. A possible method to produce the keystream is enciphering with AES-128 a 128-bit incremental counter, starting at an agreed-upon initial balue (that needs not be secret, could just be zero, but is best random for each message or/and secret).

This basic encryption by exclusive-OR with a keystream does not round up enciphered messages to some blocksize, but has issues:

• If the sender can be tricked to reuse some keystream (for example, if the state of the above counter is restored from a backup, or an adversary can otherwise cause the counter to hick-up), confidentiality might be lost. Cryptographic states are a target for mishaps/attacks, and this is often exacerbated by desire of keeping ciphertext small (if it was not for that desire, we'd use a random public Initialization Vector at start of each message and live happy and safe).
• The ciphertext transmitted is an arbitrary sequence of bits. If the plaintext is, say, a 12-digit credit card number with one digit per octet, the ciphertext still is 12 octets, but generally won't be accepted as a credit card number. That issue is solved by Format Preserving Encryption. A general sketch is to convert the plaintext to an integer in as narrow an interval as possible given the plaintext semantic, encipher that to an integer in the same range, and convert it back to the ciphertext using that same semantic. I won't consider FPE further; nor the common practice of encoding ciphertext octets per Base64, which causes expansion by at least 1/3.
• Decryption recovers the original plaintext only if the receiver remains perfectly in sync with the sender, hence the scheme does not survive the loss of a message in transport; that's the problem stated in [1.] above, and solved by [1.] below.
• If the receiver makes a public comment or observable action based on what it received, then that can be exploited by an active attacker (able to alter ciphertext) to obtain some information about the original message, when the goal of encryption is to hide anything about the plaintext except its size. That's the case if the receiver leaks deciphered plaintext resulting from decryption of an altered ciphertext, but it can get more subtle: in the case of a credit card number in ASCII, the adversary can toggle bit 3 of the first and third octet in the ciphertext; that will change digit 0 to 8, 1 to 9, 8 to 0, and 9 to 1 at the corresponding positions in the deciphered plaintext, while digits 2 to 7 will be changed to non-digits. Thus if the receiver leaks that the credit card number is still well-formed after decryption, then its first and third digit must be among 0, 1, 8, 9. Further, a Luhn check on the credit card number still pass with odds 50%: that's when the first or third digit is 0 or 1, and the other is 8 or 9. While there are ad-hoc workarounds to this issue (like PCBC mode and ciphertext stealing), the true solution is an integrity check as in [2.].

---

Sometime, it is used (lossless) data compression before encryption; that might tend to reduce the size of what's transmitted. For small messages, a preset dictionary tailored to the use case can help. However, for any data compression accepting arbitrary bitstrings as plaintext, some messages will have their size expanded by at least one bit. And the size of the ciphertext and perhaps the duration of encryption/decryption will leak some indication about the nature of plaintext, against the goal of encryption. Further, decryption without prior integrity check can be the source of implementation vulnerabilities.

---

Sketches of how 1..4 are taken care of without too much message expansion

1. Deciphering messages independently can be made with a public incremental sequence number that never wraparounds (because it is large enough, or because it is of variable size); using that sequence number $S$ as part fo the keying material of the CSPRNG/cipher used; and putting all or part of that sequence number at an agreed position in each message. In many contexts, transferring a fixed number of the low-order bits of $S$ will enable the receiver to reconstruct the whole $S$.

   For example, if we use AES-128 noted $E_K$ where $K$ is the key, we can compute a per-message key $K'=E_K(S)$, a per-message starting counter $C=E_{K'}(0)$, then generate the keystream as $E_{K'}(C)$, $E_{K'}(C+1\bmod2^{128})$, $E_{K'}(C+2\bmod2^{128})$.. [Notice that without the $C=E_{K'}(0)$ step, there would be a multi-target attack of cost $\approx2^{127}/m$ AES-128 encryptions and as many searches among $j$ values, where $j$ is the number of messages for which a plaintext/ciphertext pair is known at a common position, with the attack allowing decryption of one message among the $j$ ].

2. Message integrity can be insured with a symmetric Message Authentication Code; that basically adds a field to the ciphertext, computed from a key, and the plaintext or (arguably, preferably) the rest of the ciphertext; the MAC is recomputed and verified by the receiver.

   For a good MAC such as HMAC, an overhead of $b$ bits for the MAC, odds of forgery are at most about $t\,2^{-b}$ for $t$ attempts. $b=32$ is enough in many contexts (if an attempt is made every 0.1s, odds of forgery in a month are 1 in 165), $b=64$ is generally aplenty. Critically, a MAC must not use the same key as the one used for confidentiality (if by exception it does so, that must be using sufficiently different algorithms).

   Message integrity is extremely useful in most applications requiring confidentiality, and when implemented with a Wegman-Carter universal hash costs significantly less than encryption. For this reason a modern trend is to bundle it with encryption, into authenticated encryption, e.g. Poly1305-AES.

3. Public-key encryption is bound to cause ciphertext expansion by at least $b$ bits if decryption is to require $O(2^b)$ work. It is possible to reach that limit in practice for messages above some size. E.g. in RSA with public key $(N,e)$ and $N$ 2048-bit, for a message $M$ of at least 240 octets (1920 bits)

   • The sender generates a random 128-bit key $K$ in range $[0\dots\lfloor N/2^{1920}\rfloor)$;
   • uses that $K$ (and perhaps a sequence number) to seed a CSPRNG and encipher $M$ using that keystream, yielding $C$ of same size as $M$;
   • splits $C$ into $C_0\|C_1$ with $C_0$ of 1920 bits;
   • computes $C_0'=(K\|C_0)^e\bmod N$ (as a 2048-bit bitstring)
   • sends $C_0'|C_1$; the total message overhead is 128-bit.
   • And the receiver splits what it receives into $C_0'$ and $C_1$,
   • computes $K\|C_0=C_0'^d\bmod N$ where $d$ is an RSA private exponent matching $e\,d\equiv1\pmod{\lambda(N)}$ ;
   • extracts $K$ and $C_0$ from that;
   • uses that $K$ (and perhaps a sequence number) to seed a CSPRNG and deciphers $C_0\|C_1$ using that keystream, yielding the original $M$.

4. Digital signature seems to be bound to cause signed message expansion by at least $2b$-bit if forgery is to require $O(2^b)$ work. Schemes approaching that limit including for small messages are an active research topic, e.g. BLS signature. Plain old Schnorr signature over an Elliptic Curve Group reaches $3b$-bit, either conjecturally, provably in some models, or provably in more models with Schnorr signature using Message Recovery (MR is a class of digital signature that reduces message expansion compared to the more traditional digital signature with appendix, at the price of transforming at least some part of the message in a way that can be undone using the public key). RSA signature with message recovery theoretically reaches the $2b$-bit limit for messages above $\log_2(N)-2b$ bits, and there is a standard for that: ISO/IEC 9796-2 scheme 3, which has an overhead of about about $2b+16$ bits.

Answer 2

If the sender and recipient can agree on the nonce of every message from existing context, so that the nonce either doesn't need to be transmitted or can be derived from metadata that must be transmitted anyway, then a stream cipher can be used to encrypt with no length expansion.

But the problem here is that you likely don't want just plain encryption, but authenticated encryption (AE), and AE algorithms generally require an authentication tag to be transmitted along with messages, which is an overhead that expands message size.

There do exist however AE algorithms that under limited circumstances could be used to encrypt and authenticate with no length expansion. One example is the still experimental CAESAR competition candidate AEZ, which claims the following property (from the v5 spec, p. 10):

Exploitation of domain-specific redundancy. In many contexts, plaintexts have a certain expected structure. This might arise because the message was produced by or for a particular protocol. We intend that if the user checks for the anticipated structure and regards messages as inauthentic if they don’t comply, then this check augments authenticity and correspondingly lessens the need for the nominal redundancy that is inserted by AEZ before enciphering (that is, the extra ABYTES zero bytes).

The following guideline is given for when a very low ABYTES (authentication tag length) value may be safely used (p. 13):

Applications should not reduce ABYTES to zero or some other small value without ensuring that, combining the ABYTES zero bytes with any decryption-verified redundancy, there remain enough total bits $r$ of redundancy that forging each message with probability $2^{−r}$ is alright.

AEZ however is still very much at an experimental, cryptographic competition phase, so if you need a solution today you're just going to have to use a well-established AE scheme, and that will require length expansion.

Answer 3

There is the one time pad (OTP) of course. A low bandwidth point to point channel is a perfect use case for it. Perfect secrecy and the cipher text is exactly the length of the plain text. 100% efficiency in that it’s bit for bit encryption.

There are some implementation issues (sometimes) with a OTP, but in certain limited point to point communication systems, it’s perfect. And are these issues for your system anyway? Malleability /authentication isn't always a real problem as long as you keep the key material safe. However a MAC/HMAC scheme can be appended creating the same degree of integrity/authenticity as any other encryption technique, but with higher secrecy.

If you imagine 1GB of key material exchanged personally (or by trusted courier), that would facilitate ~6 million Twitter messages. In your low bandwidth channel (say 1 bit /s), that’s 31 continuous years worth of nasty secrets. This fact plays into the particular requirements for the initial key exchange; you’ll never have to do it again so can be accomplished at the start of your grand scheme.

There aren’t that many low bandwidth scenarios these days (unless you’re talking to a submerged submarine in another hemisphere), so this is an extreme solution to your extreme problem.