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 2^{128}
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.

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.

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 T_{j}

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 x_{1}, x_{2}, x_{3} …
x_{N} be the data packets of the message.

Then in IGE mode, Ann generates T_{1}, T_{2}, T_{3} … T_{N} by

T_{j} = E{x_{j}+T_{j−1}} + x_{j−1}

T_{0} and x_{0} 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 x_{1}, x_{2}, x_{3}
… x_{N} by

x_{j} = D{T_{j} −
x_{j−1}}− T_{j−1}

Unfortunately, there is an attack on this mode.

Suppose Malcolm wants to create a false message,
*x*_{j} which should agree with x_{j}
for j less than n-1, and j greater than n+1, but
*x*_{5}, and *x*_{6} should be
different. For definiteness, let us suppose it should agree for j less than five, and j greater than seven, but
*x*_{5}, and *x*_{6} should be
different. If the original plaintext T_{6} 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 T_{1},
T_{2}, T_{3} … T_{N} and has
guessed x_{1}, x_{2}, x_{3} …
x_{N}. He cannot guess x_{0} and
T_{0}, 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
x_{j}, 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:

*T*_{5} = T_{7}
− x_{6} + x_{4}

*T*_{6} = 2* T_{6} − x_{5} + x_{7} − T_{4}

*T*_{7} = T_{5} − x_{4} + x_{6} + T_{5} − *T*_{5}

Bob then decodes

*x*_{5} = D{*T*_{5} −x_{4}}

= D{T_{7} − x_{6} + x_{4
}− x_{4}}− T_{4}

= D{T_{7} − x_{6}}− T_{4}

= x_{7} + T_{6} − T_{4}

*x*_{6} = D{*T*_{6}
− *x*_{5}} − *T*_{5}

= D{T_{6} − x_{5} + x_{7} + T_{6} − T_{4}
− *x*_{5}} − *T*_{5}

= D{T_{6} − x_{5}} − *T*_{5}

= x_{6} + T_{5} − *T*_{5}

*x*_{7} = D{*T*_{7}
− *x*_{6}} − *T*_{6}

= D{T_{5} − x_{4} + x_{6} + T_{5} − *T*_{5}
− *x*_{6}} − *T*_{6}

= D{T_{5} − x_{4}} − *T*_{6}

= x_{5} + T_{4} − *T*_{6}

= x_{5} + T_{4} − 2* T_{6} − x_{5} + x_{7} − T_{4}

= x_{7} − 2* T_{6}

If the 2* T_{6} 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* T_{6} will always be all zeroes, but if one instead uses addition modulo 2^{128}, no problem, or rather problems will be so rare that Malcolm in the Middle is unlikely to bother watching.

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
2^{128} 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.

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 T_{j}

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 x_{1}, x_{2}, x_{3} …
x_{N} be the data packets of the message.

Then in JABM mode, Ann generates T_{1}, T_{2}, T_{3} … T_{N} by

C_{j} = E{x_{j}+C_{j−1}} + x_{j−1} + C_{j−1}

T_{j} = C_{j} + T_{j-1}

T_{0}, C_{0} and x_{0} 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 x_{1}, x_{2}, x_{3}
… x_{N} by

C_{j} = T_{j} − C_{j−1}

x_{j} = D{C_{j} − x_{j−1} − C_{j−1}} − C_{j−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 T_{N} 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 x_{N} 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 T_{1}, T_{2}, T_{3} … T_{K-1}, T_{K}

Malcolm in the Middle's fake message agrees for the first M-1 blocks, but the Kth block is different:
T_{1}, T_{2}, T_{3} … T_{K-1}, T'

When Bob decrypts Malcolm in the Middle's fake message, he will decrypt:

C_{j} = T_{j} − C_{j−1}

x_{j} = D{C_{j} − x_{j−1} − C_{j−1}} − C_{j−1}

for 0 < j < K

but for the Kth block, Bob's attempted decryption yields:

C'_{K} = T' − C_{K−1}

x'_{K} = D{C'_{K} − x_{K−1} − C_{K−1}} − C_{K−1}

Where:

x'_{K} ≠ x_{K}

and

C'_{K} − x_{K−1} − C_{K−1} = C_{J} − x_{J−1} − C_{J−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 x_{0}, C_{0}, and T_{0} there is more than one possible value for T' consistent with the known to Malcolm in the Middle values of x_{1}, x_{2}, x_{3} … x_{N} and T_{1}, T_{2}, T_{3} … T_{N}

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

x_{0}, C_{0}, and T_{0}, 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

x_{1} = 0x48

x_{2} = 0x65

x_{3} = 0x6C

x_{3} = 0x6C

x_{3} = 0x6F

x_{3} = 0x00

Which is a null terminated “Hello” in UTF-8
All additions and substractions are modulo 2^{8}, whereas normally they would be 2^{128}

******************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. *******************

C_{1} = E{x_{1}+C_{0}} + x_{0} + C_{0}

T_{1} = C_{1} + T_{0}

C_{2} = E{x_{2}+C_{2}} + x_{1} + C_{1}

T_{2} = C_{2} + T_{2}

C_{3} = E{x_{3}+C_{3}} + x_{2} + C_{2}

T_{3} = C_{3} + T_{3}

C_{4} = E{x_{4}+C_{4}} + x_{3} + C_{3}

T_{4} = C_{4} + T_{4}

C_{5} = E{x_{5}+C_{5}} + x_{4} + C_{4}

T_{5} = C_{5} + T_{5}

C_{6} = E{x_{6}+C_{6}} + x_{5} + C_{5}

T_{6} = C_{6} + T_{6}

C_{1} = E{x_{1}+C_{-1}) = E{0x48+0xE7} = 0x77

T_{1} = C_{1} + C_{0} = 0x77+0x7D = 0xF4

C_{2} = E{x_{2}+C_{0}} = E{0x65+0x7D} = 0xF2

T_{2} = C_{2} + C_{1} = 0xF2+0x77 = 0x69

C_{3} = E{x_{3}+C_{1}} = E{0x6C+0x77} = 0xC4

T_{3} = C_{3} + C_{2} = 0xC4+0xF2 = 0xB6

C_{4} = E{x_{4}+C_{2}} = E{0x6C+0xF2} = 0x13

T_{4} = C_{4} + C_{3} = 0x13+0xC4 = 0xD7

C_{5} = E{x_{5}+C_{3}} = E{0x6F+0xC4} = 0x51

T_{5} = C_{5} + C_{4} = 0x51+0x13 = 0x64

C_{6} = E{x_{6}+C_{4}} = E{0x00+0x13} = 0x5F

T_{6} = C_{6} + C_{5} = 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:

C_{1} = T_{1} - C_{0} = 0xF4 - 0x7D = 0x77

x_{1} = D{C_{1}}− C_{−1} = D{0x77}-0xE7

C_{2} = T_{2} - C_{1} = 0x69 - 0x77 = 0xF2

x_{2} = D{C_{2}}− C_{0} = D{0xF2}-0x7D

C_{3} = T_{3} - C_{2} = 0xB6 - 0xF2 = 0xC4

x_{3} = D{C_{3}}− C_{1} = D{0xC4}-0xF4

C_{4} = T_{4} - C_{3} = 0x15 - 0xC4 = 0x51

And now Malcolm in the Middle fools Bob into using a codebook entry Ann used, but out of order

x_{4} = D{C_{4}}− C_{2} = D{0x51}-0xF2

…

But Malcolm in the Middle knows nothing about the code book or the secret values C_{0} 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 C_{0} 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 C_{0} 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

C_{1} = E{x_{1}+C_{-1}} = E{0x48+0xE7} = 0x78

T_{1} = C_{1} + C_{0} = 0x78+0x7C = 0xF4

C_{2} = E{x_{2}+C_{0}} = E{0x65+0x7C} = 0xF1

T_{2} = C_{2} + C_{1} = 0xF1+0x78 = 0x69

C_{3} = E{x_{3}+C_{1}} = E{0x6C+0x78} = 0xC5

T_{3} = C_{3} + C_{2} = 0xC5+0xF1 = 0xB6

C_{4} = E{x_{4}+C_{2}} = E{0x6C+0xF1} = 0x12

T_{4} = C_{4} + C_{3} = 0x12+0xC5 = 0xD7

C_{5} = E{x_{5}+C_{3}} = E{0x6F+0xC5} = 0x52

T_{5} = C_{5} + C_{4} = 0x52+0x12 = 0x64

C_{6} = E{x_{6}+C_{4}} = E{0x00+0x12} = 0x5E

T_{6} = C_{6} + C_{5} = 0x5E+0x52 = 0xB0

We are assuming the codebook is different in a way that results in the exact same encoded message T_{1} … T_{6} 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:

C_{1} = T_{1} - C_{0} = 0xF4 - 0x7C = 0x78

x_{1} = D{C_{1}}− C_{−1} = D{0x78}-0xE7

C_{2} = T_{2} - C_{1} = 0x69 - 0x78 = 0xF1

x_{2} = D{C_{2}}− C_{0} = D{0xF1}-0x7D

C_{3} = T_{3} - C_{2} = 0xB6 - 0xF1 = 0xC5

x_{3} = D{C_{3}}− C_{1} = D{0xC5}-0x78

C_{4} = T_{4} - C_{3} = 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.

x_{4} = D{C_{4}}− C_{2} = 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 2^{K} 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 C_{0} 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