To Home page

Block Mode Authentication

We need a combined MAC+encryption mode for block ciphers. The cool, efficient modes are tangled in patents and therefore unusable. The unpatented CCM requires that the message length be known beforehand which severely limits it usefulness. 

A block cipher such as Rijndael encrypts a single block, typically 128 bits.  But messages are typically a fair bit longer, so a block cipher must be used in a block mode. This turns out to be surprisingly tricky.  Even if the block cipher is as strong as it can be, indistinguishable from a random permutation, encoding longer messages using the cipher is apt to make various attacks possible. 

So a block cipher needs to be used in a block mode, a block mode being a method for encrypting longer messages, given a block cipher that encrypts short fixed length messages. 

JABM: A block mode with provably secure free mac

Authentication

Suppose Ann sends Bob a message, and Malcolm knows or can make a good guess what the message is.  We not only do not want Malcolm to be able to confirm his guess, we also don't want Malcolm to be able to intercept Ann's message and construct a modified message that appears to Bob to come from Ann. 

An encrypted message not only needs to leak as little information as possible to the attacker, but also needs to be authenticated.  The recipient needs to know that this message did indeed come from the person who possesses the shared secret – that the message is authentic. 

This is usually done by appending a mac to the message, a value that depends sensitively on every packet in the message and a shared secret, thereby proving the message comes from a person possessing the shared secret.  But generating a mac costs about as much computation as encryption.  Cannot we get authentication from encryption alone, a free mac?  The way to costlessly piggy back integrity on top of confidentiality is to have error propagation, so that any fiddling with the message will cause all packets after the fiddling to be random noise. 

In this article I examine a previous, insecure, attempt to generate a mac without additional overhead, examine why it failed, and present a new block mode with a proof the block mode is secure  I call this block mode JABM, James Authenticating Block Mode. 

IGE: Free Mac

One proposal for obtaining a free-mac, is IGE mode, infinite garble extension.  The idea is that if Malcolm changes any packet, every subsequent packet will be garbage.  So if the message ends with a known standard affix, that will be garbled, producing an invalid message.

Let the jth transmitted block be Tj

Let the block mode encryption of x be E{x} and the block mode decryption of y be D{y}, so that
    D{E{x}} = x

Let x1, x2, x3 … xN be the data packets of the message.

Then in IGE mode, Ann generates T1, T2, T3 … TN by
    Tj = E{xj+Tj−1} + xj−1

T0 and x0 are not transmitted, nor part of the the message, but are shared secrets, large random numbers known in advance to both Ann and Bob.

Typically these random numbers are generated by means of a public key protocol, usually based on Diffie Hellman

Bob generates x1, x2, x3 … xN by
    xj = D{Tj − xj−1}− Tj−1

Unfortunately, there is an attack on this mode.

Suppose Malcolm wants to create a false message, xj which should agree with xj for j less than n-1, and j greater than n+1, but x5, and x6 should be different.  For definiteness, let us suppose it should agree for j less than five, and j greater than seven, but x5, and x6 should be different.  If the original plaintext T6 has a certain value, then the decoded plaintext, the false plaintext, will agree with the true plaintext for j sufficiently large, thus the message will appear to be valid to Bob, because it will have the expected affix.

We assume Malcolm can see T1, T2, T3 … TN and has guessed x1, x2, x3 … xN.  He cannot guess x0 and T0, since these are shared secrets.  Unfortunately, with the proposed mode, these shared secrets don't actually give us anything.  As we shall see, fixing the problem will require making sure these shared secrets are actually useful, which in the proposed IGE mode they are not. 

Watson has constructed what he believes is a proof that there is no simple way of getting a free mac, but I interpret his proof as showing that that one has to make sure the shared secrets actually earn the their keep and do something useful if one is to get a free mac. 

The proposed attack is that Malcolm reads and suppresses Ann's authentic message, and, knowing the plaintext xj, constructs a message where Bob will use the same block decode for the fifth block as Ann intended that he use for the seventh, the same block decode for the sixth block as Ann intended,  the same decode for the seventh as Ann intended he use for the fifth, and same decode for all subsequent blocks as Ann intended. 

The same decodes occur in Malcom's message as occur in Ann's, these being the only decodes he has access to, but they occur in a different order. 

Infinite Garble Extension means that Malcolm must use the same decodes as occur in the original message, for if his message contains a decode he has not seen, he has insufficient information to know what the outcome will be, thus the outcome will be effectively random, thus all subsequent decodes will be random, thus the final decode will be random, thus the message will not pass as legitimate. But this is not quite enough to secure the message against tampering. We also need to protect the order of the decodes. 

Malcolm encodes:
    T5 = T7 − x6 + x4
    T6 = 2* T6 − x5 + x7 − T4
    T7 = T5 − x4 + x6 + T5T5

Bob then decodes
    x5 = D{T5 −x4}
        = D{T7 − x6 + x4 − x4}− T4
        = D{T7 − x6}− T4
        = x7 + T6 − T4
    x6 = D{T6x5} − T5
        = D{T6 − x5 + x7 + T6 − T4x5} − T5
        = D{T6 − x5} − T5
        = x6 + T5T5
    x7 = D{T7x6} − T6
        = D{T5 − x4 + x6 + T5T5x6} − T6
        = D{T5 − x4} − T6
        = x5 + T4T6
        = x5 + T4 − 2* T6 − x5 + x7 − T4
        = x7 − 2* T6

If the 2* T6 is all zeros, then the garble fails to propagate, and Malcolm has undetectably introduced garbage into a message at a chosen point without the recipient detecting it, though he cannot control the content of the garbage. 

This problem becomes considerably worse if one uses XOR, instead of addition, +.  Then Malcolm can undetectably introduce random garbage at any point into any message, for two of anything adds to zero using XOR. 

Provably secure free Mac

One is tempted to think that if we have the right operation mingling the data, something nastier than addition, all will be well, and very likely that is true, but its not obvious how to prove it to be true.  To have a mode that is provably secure, we must ensure that Malcolm does not have enough information to reliably construct a message whose decoding he can control. 

The codebook is the mapping between encrypted and cleartext blocks.  Since Malcolm can guess messages, since not all messages are equally likely, any encrypted message will give Malcolm some information about the codebook.  But the codebook is very large. For 128 bit blocks, it is a mapping of 2128 different blocks. 

We require our encryption mode to make it unlikely that that we will ever reuse a block for messages and groups of messages of reasonable length, so that the information that we must inevitably leak about the codebook does not leak any information about the content of the message – which is why ECB mode is deprecated.

We require our encryption mode to make it unlikely that that we will ever reuse a block for messages and groups of messages of reasonable length, so that the information that we must inevitably leak about the codebook does not leak any information about the content of the message – which is why ECB mode is deprecated.

We may assume that knowing some mappings between encrypted and cleartext blocks does not enable Malcolm to guess anything about any other mappings, about any blocks that have not yet been used, for if he did, that would be a defect of the block encryption algorithm, not the block encryption mode, and the algorithm, not the mode, would be changed. 

We may therefore pretend that that the codebook is random from Malcom's point of view, treat it as if it was generated at random, as if Bob and Alice had a great big book of mappings, generated by selecting a random 128 bit block for the block 0000…000, and then selecting another random 128 bit block from the remaining blocks for the block 0000…001, and so forth. 

To prove that our block mode provides security, assuming the block encryption algorithm to be good, we must therefore prove that if Malcolm could discriminate between two alternate messages of the same length, he would be able to know something about mappings not yet seen from mappings seen, and to prove that our block mode provides authentication, to prove that Malcolm cannot generate a seemingly good message from an actual good message, we again must prove that if Malcolm could do this, he would be able to know something about mappings not yet seen from mappings seen. 

JABM: Free Mac

Again, the idea is that if Malcolm changes any packet, every subsequent packet will be garbage.  So if the message ends with a known standard affix, that affix will be garbled, producing an invalid message.

Let the jth transmitted block be Tj

Let the block mode encryption of x be E{x} and the block mode decryption of y be D{y}, so that
    D{E{x}} = x

Let x1, x2, x3 … xN be the data packets of the message.

Then in JABM mode, Ann generates T1, T2, T3 … TN by
    Cj = E{xj+Cj−2}

    Tj = Cj + Cj-1

C0 and C-1 are shared secrets, large random numbers known in advance to both Ann and Bob.

Bob generates x1, x2, x3 … xN by
    Cj = Tj - Cj-1

    xj = D{Cj}− Cj−2

Mallocs fake message has to preserve the ending, has to have the same xN as the true message.

Since the only decryptions and encryptions he has information about are those in the original message, he has to use the same encryptions and decryptions, but in a different order.

So we have to prove that given a known message, and the encryption of that message, there is more than one possible value that could yield, or fail to yield an out of order decryption - that the adversary cannot know what value would work.

These documents are licensed under the Creative Commons Attribution-Share Alike 3.0 License