0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I think 8-ish bytes message expansion (per message) is the absolute minimum. But then you've gotta keep state on both sides and kill the connection as soon as you detect a forgery (or very soon thereafter). The comfortable maximum would be 28 (=16+12) bytes per message, which can be reduced by to 12 bytes depending on how much state you can keep $\endgroup$ – SEJPM Oct 6 '17 at 22:43
  • 1
    $\begingroup$ You could go as low as 1 bit with a one time pad, while hoping that something else is doing your error handling. And encryption doesn't have to increase the size. $\endgroup$ – daniel Oct 6 '17 at 23:05
  • $\begingroup$ Are there good encryption techniques that keep the block size the same? Ever heard of eg. AES? $\endgroup$ – deviantfan Oct 7 '17 at 0:16
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Format-preserving_encryption ​ ​ $\endgroup$ – user991 Oct 7 '17 at 7:26
  • $\begingroup$ @deviantfan Be warned that I have had similar questions on StackOverflow where the block size turned out the buffer size for reading / writing files, i.e. is application specific rather than being linked to the block cipher in use. $\endgroup$ – Maarten Bodewes Oct 8 '17 at 14:49
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ "the goal of encryption is to hide anything about the plaintext except its size" is opposite to "And the size of the ciphertext ... will leak some indication about the nature of plaintext, against the goal of encryption. " I think compression and also padding are both great tools when it comes to hiding the message size. $\endgroup$ – daniel Oct 9 '17 at 8:14
  • $\begingroup$ @daniel: I see the opposition, but no contradiction. Size of ciphertext leaks information about the nature of the plaintext only when compression is used. Compression can be dangerous for this reason. Example: given the compression built into audio codecs in telephony, naively enciphering the data reportedly makes it possible to identify some long words, or at least stereotyped sentences, by mere analysis of the length of packets. That seems credible, and attacks only get better; they never get worse. $\endgroup$ – fgrieu Oct 9 '17 at 9:01
  • 1
    $\begingroup$ For classical cryptography and the modern stuff padding is a reason for message expansion. I'd say there are some traps to compression (the VoIP thing, CRIME), but generally there is no reason to think one way about compressed data (it leaks data, beware!), and another way on uncompressed data (don't try to hide message size). $\endgroup$ – daniel Oct 9 '17 at 9:16
  • 1
    $\begingroup$ @daniel: In some spheres (arguably, Smart Cards) I see a trend towards moving away from padding; specifically, moving from CBC encryption (which required padding) to CTR encryption (which does not); and to provide integrity by distinct means. While the new practice leaks a little more info about the length of the plaintext, traditional padding gives only marginal protection. If we need to keep the length of the plaintext confidential to some degree, there are better methods. Often in practice (and by default in theory), that's considered pointless. $\endgroup$ – fgrieu Oct 9 '17 at 9:31
  • $\begingroup$ A few minor quibbles: 1) Stream ciphers can recover from message loss, if the receiver can tell that a message was lost and how long it was. Of course, usually detecting message loss requires something like sequential message numbers, in which case one could just use those as nonces. 2) I'm not sure the mention of PCBC/CTS at the end of the last "issues" bullet point is helpful, at least not without also explicitly noting their limitations. Still, overall this is an excellent answer. $\endgroup$ – Ilmari Karonen May 14 at 10:58
5
$\begingroup$

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.

$\endgroup$
-2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ IMHO , "History proves that malleability /authentication isn't a real problem" suffers exceptions. There are hacks where the adversary knows the position of a certain bit, changes it in the ciphertext, and gets away with it. There are variants where s/he has to change a CRC, and also succeeds. $\endgroup$ – fgrieu Oct 8 '17 at 12:29
  • 3
    $\begingroup$ For me "History proves that malleability /authentication isn't a real problem" is enough reason to vote this answer down. I don't know where you got this notion, but in my opinion it should be suppressed. $\endgroup$ – Maarten Bodewes Oct 8 '17 at 14:47
  • 4
    $\begingroup$ That may sound a bit harsh yes, but this is in my opinion a very dangerous statement to make; most of the time when eavesdropping is possible, active attacks are also possible. If internet, for instance, can be reverted through a third party for eavesdropping, it is likely that this party can also change the ciphertext. Stating that this kind of attack is usually not possible is, in my opinion, wrong and dangerous. $\endgroup$ – Maarten Bodewes Oct 8 '17 at 20:58
  • 1
    $\begingroup$ @MaartenBodewes not every attacker is Mallory, some are still Eve. The example given of making a post on twitter is fine for a present day non malleable channel (as its out in the open and the sender could anonymously observe any changes made by the sky gods later). $\endgroup$ – daniel Oct 10 '17 at 9:42
  • 1
    $\begingroup$ @forest it's ok in my mind because the sender can post from an account, visit a net cafe and check anonymously that the post is true, and the receiver can anonymously check from anywhere in the world. If the sender starts seeing his posts are being changed he can assume his connection, account or Twitter is not reliable and then stop using it. BRB looking for Twitter numbers stations $\endgroup$ – daniel May 19 at 5:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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