silly possibly original AE construction

Question

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
        else:
            cleartext = None
            raise ValueError("bad ciphertext")


key = b'YELLOW SUBMARINE'
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)

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.