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?
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this communityIf 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?
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:
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:
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
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$ ].
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.
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)
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.
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.
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.
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