Utilizing block cipher (AES) while saving bandwith

Question

I'm helping a company to redesign their cryptographic protocol for communication within a network of embedded devices.

So far I have discovered several insecure practices, such as using very short (6 characters) passwords to derive AES symmetric keys and so on.

When redesigning the protocol, I wanted to use stream cipher (ChaCha20) instead of AES to save bandwidth, since a low-bandwidth LoRa channel is used and encrypting 18 bytes of data with AES would mean sending 32 bytes of data.

When I suggested such a change, I got a reply from the company saying that they'd done a clever "hack" to encrypt 18 bytes with AES while only getting 18 bytes of ciphertext. My first impression (after the bad password practice experience) was that this must be a really insecure "hack" and cannot be used in production.

However, after a closer look, I couldn't find any critical security flaw in their approach - I'm sure their approach reduces the security of AES, but since their use case is not "top secret", I'm not sure whether a practical exploit could be found in a reasonable time to decrypt packets encrypted in this way.

Their approach can be demonstrated with the following python pseudocode:

def encrypt_18_bytes(key, data):
    first_part = data[0:16]
    second_part = data[16:]
    fp_encrypted = aes(key, first_part)
    sp_encrypted = aes(key, fp_encrypted[2:] + second_part)
    result = fp_encrypted[0:2] + sp_encrypted
    return result

which could be decrypted as follows

def decrypt_18_bytes(key, data):
    first_part = data[0:2]
    second_part = data[2:]
    sp_decrypted = aes_dec(key, second_part)
    fp_decrypted = aes_dec(key, first_part+sp_decrypted[0:14])
    result = fp_decrypted + sp_decrypted[14:]
    return result

My question is - is there a critical flaw in such an approach with the possibility of practical exploitation?

Answer 1

That technique from the code is known as "ciphertext stealing". We usually use it with CBC, but your client seem to be using ECB.

So yes, it has the flaw of using the insecure ECB mode.

Answer 2

This is a custom 18-byte block cipher using two 16-byte keyed substitution steps:

It has some slight flaws, the two most striking of which being:

1. if the first 16 bytes of plaintext match, then the first 2 bytes of ciphertext match
2. if the last 16 bytes of ciphertext match, then the last 2 bytes of plaintext match

If the payload is such that the first 16 bytes of plaintext are unique (for all all uses of a given key), then this is rather good crypto: 1 is not exploitable, and 2 is not exploitable until billions of billions of messages are encrypted (and then would likely not be much of a practical issue).

On the other hand, we can imagine many situations where 1 is a security issue, including a few that would be solved by using a true 18-byte block cipher (rather than increasing the payload size to add a nonce). For such construction, Format Preserving Encryption has general, robust techniques.

Adding a third AES round that re-encrypts the first 16 bytes would fix both flaws stated above, but I would not dare to state that the construction can't be distinguished from a random permutation in a chosen plaintext attack (I would if further we used different keys in the three invocations of AES).