To Home page

Block Mode Authentication

OCB block mode accomplishes what this accomplishes, but is under patent. Will not fall out of patent for a few years. OCB also includes the equivalent of ciphertext stealing. Hard to do ciphertext stealing in infinite garble extension

CCM mode does not save us anything, since it needs two block encryption operations per block of data, in effect one to encrypt, one to authenticate

We need a combined MAC+encryption mode for block ciphers. The cool, efficient modes are tangled in patents and therefore unusable. 

Infinite Garble Extension is broken if the combining operation is exclusive or, but works fine if the combining operation is addition modulo 2128 Be good if we extended it to be provably secure, with an extension such that Malcolm in the Middle sees all possible values as equally consistent with not knocking bob off the rails. Infinite garble extension needs fixing to support associated authenticated data (where the plaintext plus stolen ciphertext is transmitted, and the recipient regenerates the encrypted text from the plaintext, and ciphertext stealing at the end OCB is patent free for open source license.

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. 

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 you cannot get a free mac but I find his proof unconvincing.

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 is a problem if one uses XOR for then 2* T6 will always be all zeroes, but if one instead uses addition modulo 2128, no problem, or rather problems will be so rare that Malcolm in the Middle is unlikely to bother watching.

JABM: A block mode with provably secure free mac

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. In ECB mode, repetitions in the plaintext will result in repetitions in the encrypted text, which is likely to enable the attacker to make a good guess.

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−1} + xj−1 + Cj−1
    Tj = Cj + Tj-1

T0, C0 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
    Cj = Tj − Cj−1
    xj = D{Cj − xj−1 − Cj−1} − Cj−1

Bob knows the message was sent by Ann, because it was sent by someone who knows their shared secret, and he knows it was sent by someone who knows their shared secret because the final packet TN ends the way it is supposed to.

Malcolm in the Middle's fake message has to preserve the ending, has to have the same ending of 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. If he causes Bob to uses some different codebook entry, Malcolm in the Middle has no information restricting what is in that entry, so it will produce random gibberish, which will propagate causing each subsequent block to be decrypted as random gibberish.

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.

Suppose the first out of order decryption in Malcolm in the Middle's fake message substitutes the Jth block decryption for the Kth block, J≠K, whereas in the original message, it should have been the Jth decryption.

Ann's original message to Bob, intercepted by Malcolm in the Middle, started with T1, T2, T3 … TK-1, TK

Malcolm in the Middle's fake message agrees for the first M-1 blocks, but the Kth block is different: T1, T2, T3 … TK-1, T'

When Bob decrypts Malcolm in the Middle's fake message, he will decrypt:
    Cj = Tj − Cj−1
    xj = D{Cj − xj−1 − Cj−1} − Cj−1

for 0 < j < K

but for the Kth block, Bob's attempted decryption yields:
    C'K = T' − CK−1
    x'K = D{C'K − xK−1 − CK−1} − CK−1

Where:
    x'K ≠ xK
and
    C'K − xK−1 − CK−1 = CJ − xJ−1 − CJ−1

Whatever clever trick Malcolm in the Middle uses, it has to result in Bob using the same codebook entries he woud have used, though not necessarily in the same order, because what Malcolm in the Middle knows gives him no information about other codebook entries, and if he causes Bob to use a codebook entry of which he has no information, infinite garble extension will ensue.

So we want to show that depending on the random and unknown to Malcolm in the Middle values of x0, C0, and T0 there is more than one possible value for T' consistent with the known to Malcolm in the Middle values of x1, x2, x3 … xN and T1, T2, T3 … TN

Now I could prove this by elegant mathematics (that there are one too many degrees of freedom) but elegant mathematics has a habit of biting me on the ass by proving something subtly different from what I thought I was proving

So instead, proof by counter example. Let us suppose instead of a one hundred and twenty eight bit electronic codebook, we have an eight bit electronic codebook, known to Ann and Bob, but unknown to Malcolm in the Middle, except that Malcolm in the Middle can guess that Bob's message is "hello" in UTF-8, and the validation code at the end is a null byte, and thus partial information the six codebook entries used by Ann and that would have been used by Bob.

Ann's message is Hello/0

x0, C0, and T0, known to Ann and Bob, but never transmitted, are 0x47, 0x7D, and 0xE7

Ann's secret message, known to Ann and correctly guessed by Malcolm in the Middle, is
x1 = 0x48
x2 = 0x65
x3 = 0x6C
x3 = 0x6C
x3 = 0x6F
x3 = 0x00

Which is a null terminated “Hello” in UTF-8 All additions and substractions are modulo 28, whereas normally they would be 2128


******************All stuff from here on needs to be redone with the rectified algorithm. *******************

******************All stuff from here on needs to be redone with the rectified algorithm. *******************

******************All stuff from here on needs to be redone with the rectified algorithm. *******************

******************All stuff from here on needs to be redone with the rectified algorithm. *******************

******************All stuff from here on needs to be redone with the rectified algorithm. *******************

******************All stuff from here on needs to be redone with the rectified algorithm. *******************

******************All stuff from here on needs to be redone with the rectified algorithm. *******************

******************All stuff from here on needs to be redone with the rectified algorithm. *******************

******************All stuff from here on needs to be redone with the rectified algorithm. *******************

******************All stuff from here on needs to be redone with the rectified algorithm. *******************
    C1 = E{x1+C0} + x0 + C0
    T1 = C1 + T0
    C2 = E{x2+C2} + x1 + C1
    T2 = C2 + T2
    C3 = E{x3+C3} + x2 + C2
    T3 = C3 + T3
    C4 = E{x4+C4} + x3 + C3
    T4 = C4 + T4
    C5 = E{x5+C5} + x4 + C4
    T5 = C5 + T5
    C6 = E{x6+C6} + x5 + C5
    T6 = C6 + T6
    C1 = E{x1+C-1) = E{0x48+0xE7} = 0x77
    T1 = C1 + C0 = 0x77+0x7D = 0xF4
    C2 = E{x2+C0} = E{0x65+0x7D} = 0xF2
    T2 = C2 + C1 = 0xF2+0x77 = 0x69
    C3 = E{x3+C1} = E{0x6C+0x77} = 0xC4
    T3 = C3 + C2 = 0xC4+0xF2 = 0xB6
    C4 = E{x4+C2} = E{0x6C+0xF2} = 0x13
    T4 = C4 + C3 = 0x13+0xC4 = 0xD7
    C5 = E{x5+C3} = E{0x6F+0xC4} = 0x51
    T5 = C5 + C4 = 0x51+0x13 = 0x64
    C6 = E{x6+C4} = E{0x00+0x13} = 0x5F
    T6 = C6 + C5 = 0x5F+0x51 = 0xB0

Malcolm in the Middle sees all the T values, but does not see the C values.

Malcolm in the Middle intercepts and suppresses Ann's message, and replaces it with his own fake message, which begins 0xF4, 0x69, 0xB6, 0x15, …

Let us suppose that Malcolm in the Middle successfully fools Bob into using one of the decryptions about which Malcolm in the Middle has partial information, and then we will inquire if he actually has enough information to do this.

Bob decrypts:
    C1 = T1 - C0 = 0xF4 - 0x7D = 0x77
    x1 = D{C1}− C−1 = D{0x77}-0xE7
    C2 = T2 - C1 = 0x69 - 0x77 = 0xF2
    x2 = D{C2}− C0 = D{0xF2}-0x7D
    C3 = T3 - C2 = 0xB6 - 0xF2 = 0xC4
    x3 = D{C3}− C1 = D{0xC4}-0xF4
    C4 = T4 - C3 = 0x15 - 0xC4 = 0x51
And now Malcolm in the Middle fools Bob into using a codebook entry Ann used, but out of order
    x4 = D{C4}− C2 = D{0x51}-0xF2

But Malcolm in the Middle knows nothing about the code book or the secret values C0 and C-1 except what is revealed by the message. So suppose that Ann sent the exact same message as a result of different values for the code book and the secret values C0 and C-1, then Malcolm in the Middle would have to send the exact same fake message. Would it still work?

Does a successful fake message depend on stuff that Malcolm in the Middle cannot know?

Let us try it.

Ann's message is still Hello/0

And she, using a different codebook, still transmits 0xF4 0x69 0xB6 0xD7 0x64 0xB0 But C0 and C-1, known to Ann and Bob, but never transmitted, is 0x7C and 0xE7, instead of 0x7D and 0xE7

Ann encrypts her message as
    C1 = E{x1+C-1} = E{0x48+0xE7} = 0x78
    T1 = C1 + C0 = 0x78+0x7C = 0xF4
    C2 = E{x2+C0} = E{0x65+0x7C} = 0xF1
    T2 = C2 + C1 = 0xF1+0x78 = 0x69
    C3 = E{x3+C1} = E{0x6C+0x78} = 0xC5
    T3 = C3 + C2 = 0xC5+0xF1 = 0xB6
    C4 = E{x4+C2} = E{0x6C+0xF1} = 0x12
    T4 = C4 + C3 = 0x12+0xC5 = 0xD7
    C5 = E{x5+C3} = E{0x6F+0xC5} = 0x52
    T5 = C5 + C4 = 0x52+0x12 = 0x64
    C6 = E{x6+C4} = E{0x00+0x12} = 0x5E
    T6 = C6 + C5 = 0x5E+0x52 = 0xB0

We are assuming the codebook is different in a way that results in the exact same encoded message T1 … T6 being sent

So Malcolm in the Middle will send the exact same message, which begins 0xF4, 0x69, 0xB6, 0x15, …, but, invisible to Malcolm in the Middle, everything is off by one

Bob decrypts:
    C1 = T1 - C0 = 0xF4 - 0x7C = 0x78
    x1 = D{C1}− C−1 = D{0x78}-0xE7
    C2 = T2 - C1 = 0x69 - 0x78 = 0xF1
    x2 = D{C2}− C0 = D{0xF1}-0x7D
    C3 = T3 - C2 = 0xB6 - 0xF1 = 0xC5
    x3 = D{C3}− C1 = D{0xC5}-0x78
    C4 = T4 - C3 = 0x15 - 0xC5 = 0x50
And now Malcolm in the Middle “fools” Bob into using a codebook entry Ann did not use, resulting in infinite garble extension which will rapidly become glaringly obvious to Bob.
    x4 = D{C4}− C2 = D{0x50}-0xF2

That everything is off by one reflects that there are too many degrees of freedom for Malcolm in the Middle to prevent infinite garble extension

If your block size is K, where K is typically 128, there are 2K values which might give rise to Bob using a codebook entry that Ann used, but which probably will not. All values are equally possible, depending on what the initial values for C0 and C-1 are. And if Malcolm in the Middle uses the wrong one, Bob's decryption will yield random gibberish from there on. One random initial block was not provably sufficient to make all values equally likely from the information available to Malcolm in the Middle. Two are.

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