This idea is inspired by a recent question about sending 32 byte messages, encrypted, without a MAC but still achieving the equivalent protection of a MAC just by using a block cipher, extra invocations of this block cipher and extra bandwidth (for example, since message is small and sending any number of bytes up to a single IP packet is "free").

Professional cryptographers, given AES and wanting AE (or AEAD), would create CBC-MAC, OMAC, CMAC, CCM, EAX, etc.

But is there a simpler way that would work, for certain values of "work"?

I present an impractical block cipher mode.

There is no IV or nonce.

Start with an AES key and a 64bit counter initiated at 0.

Assume cleartext message is evenly divisible by 8.

Break message into 8 byte pieces.

For each 8 byte piece of the cleartext input message:

  • Create a block from 8 bytes of the input and 8 bytes of counter.
  • Encrypt the block using AES.
  • Increment the counter.
  • Send the encrypted block.
  • Repeat for the next 8 bytes of input.

Obviously this scheme needs rekeying after 2^64 blocks or 2^67 bytes sent.

Obviously padding can be added for messages that are not evenly divisible by 8.

Obviously if message size is not a constant known in advance, length of the message has to be sent too.

But just for sending 32 byte messages, and no more than 2^67 bytes with a single key, is this secure?

I thought of three things:

  1. Does it encrypt same cleartext to same ciphertext like ECB? No.

  2. Can the attacker remove, duplicate or reorder blocks without the decrypter noticing? No.

  3. Can the attacker flip bits in the ciphertext without the decrypter noticing? I think no.

What am I missing? Is this "secure" but silly when CCM and EAX (and GCM, and Poly1305, and HMAC) exist?

Meta question: is there a tag for "recreational cryptography", i.e. something no one will ever use? Or is that against the rules?

Implementation in python3:

import binascii
import struct
from hmac import compare_digest
from Crypto.Cipher import AES

class Encrypter:
    def __init__(self, key):
        assert type(key) == bytes
        assert len(key) == 16
        self.cipher = AES.new(key, AES.MODE_ECB)
        self.counter = 0
    def encrypt(self, cleartext):
        assert type(cleartext) == bytes
        len_cleartext = len(cleartext)
        assert (len_cleartext % 8) == 0
        ciphertext = b''
        while len(cleartext) > 0:
            piece_8_bytes = cleartext[:8]
            cleartext = cleartext[8:]
            counter_8_bytes = struct.pack('<Q', self.counter)
            cleartext_block = piece_8_bytes + counter_8_bytes
            self.counter += 1
            ciphertext_block = self.cipher.encrypt(cleartext_block)
            ciphertext += ciphertext_block
        assert len(ciphertext) == len_cleartext * 2
        return ciphertext

class Decrypter:
    def __init__(self, key):
        assert type(key) == bytes
        assert len(key) == 16
        self.cipher = AES.new(key, AES.MODE_ECB)
        self.counter = 0
    def decrypt(self, ciphertext):
        assert type(ciphertext) == bytes
        len_ciphertext = len(ciphertext)
        assert (len_ciphertext % 16) == 0
        cleartext = b''
        all_good = True
        while len(ciphertext) > 0:
            ciphertext_block = ciphertext[:16]
            ciphertext = ciphertext[16:]
            cleartext_block = self.cipher.decrypt(ciphertext_block)
            piece_8_bytes = cleartext_block[:8]
            expected_counter_bytes = struct.pack('<Q', self.counter)
            self.counter += 1
            actual_counter_bytes = cleartext_block[8:]
            all_good &= compare_digest(expected_counter_bytes, actual_counter_bytes)
            cleartext += piece_8_bytes
        assert len(cleartext) * 2 == len_ciphertext
        if all_good is True:
            return cleartext
            cleartext = None
            raise ValueError("bad ciphertext")

e = Encrypter(key)
message1 = b'Four score and seven years ago o'
message2 = b'ur fathers brought forth on this'
ciphertext1 = e.encrypt(message1)
ciphertext2 = e.encrypt(message2)

d = Decrypter(key)
message1_back = d.decrypt(ciphertext1)
message2_back = d.decrypt(ciphertext2)
print(message1_back, message2_back)

1 Answer 1

  • The success probability of a single one-block forgery attempt is $2^{-64}$, which is the square root of what you can attain with AES-GCM, $2^{-128}$.
  • The ciphertext expansion is a linear doubling of the size, not a constant addition of 16 bytes as you attain with AES-GCM.

So, it's an astonishingly inefficient use of bandwidth and provides worse security than AES-GCM.

But if you were talking about 8-byte messages, you were constrained to 16 bytes of bandwidth per message, and the forgery probability of $2^{-64}$ were small enough for your needs, then this more or less does work as a deterministic authenticated cipher—details. (Note that a deterministic authenticated cipher necessarily cannot conceal a repeated message.)

As a cipher for >8-byte messages, it's broken. Here's a trivial distinguisher: ask for the ciphertext of the 8-byte all-zero message; then submit for the challenge (a) any message whose first block is 8-byte all-zeros, and (b) any message whose first block is not 8-byte all-zeros. Telling whose ciphertext you got, between (a) and (b), is trivial, so it fails to provide IND-CPA, let alone IND-CCA2 or authenticated encryption.

  • $\begingroup$ So if 2^-64 is good enough and double the bandwidth is ok, it's safe to use even for a lot of data sent in messages each a few hundred bytes long? $\endgroup$
    – Z.T.
    Commented Apr 28, 2019 at 22:32
  • $\begingroup$ @Z.T. No—my answer is only about 8-byte messages. I'm not addressing longer messages because the premise of a deterministic authenticated cipher for longer messages is already adequately handled by systems that don't have an obscene ciphertext expansion and that have much lower forgery probability. $\endgroup$ Commented Apr 28, 2019 at 22:42
  • $\begingroup$ You're saying it's too inefficient so no one would use it so it's not worth attacking. But if it were used, how would it be attacked? If there are no trivial attacks, that's enough. $\endgroup$
    – Z.T.
    Commented Apr 28, 2019 at 22:51
  • $\begingroup$ In my construction, duplicate message is concealed by the counter, why do you write that repeated message cannot be concealed? If I send messages until counter overflows, how would attacker know whether two messages are same? $\endgroup$
    – Z.T.
    Commented Apr 28, 2019 at 22:53
  • $\begingroup$ ‘if there are no trivial attacks’ is far from the standards of security you should be concerned with. I'm not saying your system is broken (it may be, it may not be); I'm saying that if you're willing to tolerate 16-byte ciphertext expansion for any message of 16 bytes or larger, as you seem to be, you can easily get a faster, smaller, safer system just by using AES-GCM, so there's little reason to spend any further effort studying it. $\endgroup$ Commented Apr 28, 2019 at 23:01

Your Answer

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

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