Subject: [kitten] Random-IV and short-plaintexts (Re: Comments on draft-ietf-kitten-aes-cts-hmac-sha2-00)

From: Nico Williams <[email-masked]>
Date: Tue, 28 May 2013 14:34:50 -0500

On Mon, May 20, 2013 at 5:37 PM, Tom Yu <[email-masked]> wrote:
> I think CTS will work if you are willing to modify the "IV" sent when
> the plaintext length is less than or equal to the block size;
> basically treat the IV as the next to last block of CBC ciphertext,
> truncating it to the length of the plaintext, and send the final block
> of CBC ciphertext as the "IV".

I really like this.  It might even be possible to minimize the code
path difference for short plaintexts too.

So the short-pt encryption case becomes:

 - pad pt with zeros
 - XOR with IV (cipherState XOR nonce)
 - encrypt (it's just ECB here, as it's only one block)
 - truncate the pad count of bytes from the ciphertext block and
replace the corresponding bytes of the nonce with those
 - apply the HMAC to the modified nonce and short ciphertext

The short-pt decryption case is trivial to work out from the above:

 - first verify the integrity tag
 - then reconstitute the block of ciphertext
 - decrypt
 - XOR with the nonce (which still has pad-count bytes from the ciphertext)
 - reconstitute the nonce (using pad-count bytes from the plaintext
resulting from the decryption)
 - update cipherState
 - truncate the plaintext to the original length

Note that 0-length and 1-block-long plaintexts are degenerate cases of
this.  And there's enough similarity to CTS that it might be possible
to make the code path differences for short and long plaintexts
minute.

Re-writing this to fit in section 6 notation:

   L(x) = length of x
   < = less-than operator; true == 1, false == 0
   zeroblock = one block (length c) of zeros
   o[start:len] = sub-string operation returning the substring of length
                  len of string o starting at byte start (zero-based)

encryption function       PC = (L(P) < c) * (c - L(P))
                          P' = P | zeroblock[0:PC]
                          N = random nonce of length c (128 bits)
                          IV = N XOR cipherState
                          C = E(Ke, P', IV)
                              using CBC-CS3-Encrypt defined
                              in [SP800-38A+]
                          N' = N[0:c - PC] | C[c - PC:PC]
                          H = HMAC(Ki, N' | C)
                          ciphertext =  N' | C | H[1..h]
                          cipherState = N

decryption function       (N', C, H) = ciphertext
                          PC = (L(C) < c) * (c - L(C))
                          if (H != HMAC(Ki, N' | C)[1..h])
                              stop, report error
                          if (PC > 0)
                              IV = zeroblock
                          else
                              IV = N' XOR cipherState
                          P' = D(Ke, C, IV)
                              using CBC-CS3-Decrypt defined
                              in [SP800-38A+]
                          if (PC > 0)
                              IV = (N'[0:c - PC] | P'[c - PC:PC])
                              N = IV XOR cipherState
                              P = (P' XOR IV)[0:c - PC]
                          else
                              P = P'
                              N = N'
                          cipherState = N

Style nit: the I-D refers to "cipher state", "cipherstate", and
"cipherState", but all seem to be the same thing.  This is confusing.
Pick a single spelling and stick with it.  I recommend "cipherState"
as that makes it clearer that we're talking about a quantity that's
specific to this enctype.

Style nit: using "+" to mean XOR and then having a parenthetical to
clarify this seems silly.  Might as well just say XOR :)

Nico
--

---

From: Kelley Burgin <[email-masked]>
Date: Wed, 29 May 2013 10:50:05 -0400

This looks good to me, with a couple of comments below. 

>                          N' = N[0:c - PC] | C[c - PC:PC]

Shouldn't you mac and send C[0:c - PC] instead of C? (L(C) = c since L(P') = c)

>                          if (H != HMAC(Ki, N' | C)[1..h])

If you do only send C[0:c - PC], you'll have to reconstruct C before you get here.
C' = C | N'[c - PC:PC]

>                              using CBC-CS3-Decrypt defined

Unless I've missed something, or confused myself with notation, at this point:
P' = P xor IV[0:c - PC] | IV[c - PC:PC]. (this is the real IV)

>                              IV = (N'[0:c - PC] | P'[c - PC:PC])

So here, IV = N[0:c - PC | IV[c - PC:PC]

>                              N = IV XOR cipherState

and here N = IV[0:c - PC] | N[c - PC:PC].

You could fix this by doing:
P'' = P' XOR cipherState (= P+N[0:c - PC] | N[c - PC:PC]
P = P''[0:c - PC] xor N'[0:c - PC] (these two lines could be combined into one)
N = (P | zeroblock[0:PC]) xor P''

> clarify this seems silly.  Might as well just say XOR :)

Sounds good - thanks.

---

From: Nico Williams <[email-masked]>
Date: Wed, 29 May 2013 12:14:30 -0500

> This looks good to me, with a couple of comments below.

Oh dear, I meant to define C' and use that in the HMAC input.  Dunno
how I forgot.

> Shouldn't you mac and send C[0:c - PC] instead of C? (L(C) = c since L(P') = c)

Yes.  I got sloppy there.

+>>                          C' = C[0:c - PC]
->>                          H = HMAC(Ki, N' | C)
+>>                          H = HMAC(Ki, N' | C')

->>                          ciphertext =  N' | C | H[1..h]
+>>                          ciphertext =  N' | C' | H[1..h]
>>                          cipherState = N

I also had to be consistent about matching ' usage in the encrypt and
decrypt side.  Let's make N', P', and C' match on both side, and let's
add an IV' on the decrypt side

->>decryption function       (N', C, H) = ciphertext
+>>decryption function       (N', C', H) = ciphertext
->>                          PC = (L(C) < c) * (c - L(C))
+>>                          PC = (L(C') < c) * (c - L(C'))
->>                          if (H != HMAC(Ki, N' | C)[1..h])
+>>                          if (H != HMAC(Ki, N' | C')[1..h])
 >>                          if (PC > 0)
->>                              IV = zeroblock
+>>                              IV' = zeroblock
+>>                              C = C' | N[c - PC:PC]
 >>                              IV = N' XOR cipherState
+>>                              C = C'
 >>                          P' = D(Ke, C, IV)
+>>                          if (PC > 0)
 >>                              P = P'[0:c - PC]

> So here, IV = N[0:c - PC | IV[c - PC:PC]

Earlier if PC > 0 we set IV to be the zeroblock, so that's not quite
right.  We're reversing the encryption side where we encrypted a
zero-padded plaintext, and since XOR zero is the identity function the
trailing c-PC:PC bytes of P' will be the trailing bytes of the
original IV (which we still need so we can recover N and update the
cipherState).

Let me see if I can put this together without errors this time, and
maybe I can clarify the IV recovery:

   L(x) = length of x

                          C' = C[0:c - PC]
                          H = HMAC(Ki, N' | C')
                          ciphertext =  N' | C' | H[1..h]
                          cipherState = N

decryption function       (N', C', H) = ciphertext
                          PC = (L(C') < c) * (c - L(C'))
                          if (H != HMAC(Ki, N' | C')[1..h])
                              stop, report error
                          if (PC > 0)
                              IV' = zeroblock
                              C = C' | N[c - PC:PC]
                          else
                              IV' = N' XOR cipherState
                              C = C'
                          P' = D(Ke, C, IV')
                              using CBC-CS3-Decrypt defined
                              in [SP800-38A+]
                          if (PC > 0)
                              // IV = (N'[0:c - PC] | zeroblock[c - PC:PC]) XOR
                              //      (zeroblock[0:c - PC] | P'[c - PC:PC])
                              IV = (N'[0:c - PC] | P'[c - PC:PC])
                              N = IV XOR cipherState
                              P = (P' XOR IV)[0:c - PC]
                          else
                              IV = IV'   // but we no longer need this
                              P = P'
                              N = N'
                          cipherState = N

The decrypt side is tricky to get right :)

Have at it.  I'm sure I still slipped up.

Nico
--

---

From: Kelley Burgin <[email-masked]>
Date: Wed, 29 May 2013 13:35:54 -0400

I still have a question about the decrypt: seems like 

IV = (N'[0:c - PC] | P'[c - PC:PC]) is really N[0:c - PC] | IV[c - PC:PC]), not the original IV. Did I miss something? 

As you point out, we don't actually need to recover the IV (just N), so we can compute the plaintext P directly from P' by (if I didn't mess up):

P = (P' XOR cipherState XOR N')[0:c - PC]

---

From: Nico Williams <[email-masked]>
Date: Wed, 29 May 2013 12:49:50 -0500

> IV = (N'[0:c - PC] | P'[c - PC:PC]) is really N[0:c - PC] | IV[c - PC:PC]), not the original IV. Did I miss something?

IV is not set at this point, so we can't refer to it in computing it.
And IV' is the zeroblock in the case of short-plaintexts.

> P = (P' XOR cipherState XOR N')[0:c - PC]

We don't need to recover IV as a discrete element in this case.  We do
need to update cipherState, and there's simple re-writes of the above
pseudo-code; I thought my verbose rendition should be preferable to
something more concise, but maybe concise is better?

---

From: Kelley Burgin <[email-masked]>
Date: Wed, 29 May 2013 14:08:49 -0400

All this notation is confusing...

I was meaning to say that when you decrypt C using the all zeros IV', the value you get out is 

P' = (P XOR N[0:c - PC] XOR cipherState[0:c - PC]) | (N[c - PC:PC] XOR cipherState[c - PC:PC])

and 

where N is the nonce generated by the encryptor.

So to define IV = N'[0:c - PC] | P'[c - PC:PC] will not define the same IV the encryptor used.

---

From: Nico Williams <[email-masked]>
Date: Wed, 29 May 2013 13:23:55 -0500

> So to define IV = N'[0:c - PC] | P'[c - PC:PC] will not define the same
IV the encryptor used.

Right, but it's just XORed after the one block operation, so we can fix it
with another XOR.  I didn't want to use an E() with no IV, that's all :)

---

From: Nico Williams <[email-masked]>
Date: Wed, 29 May 2013 14:29:01 -0500

> with another XOR.  I didn't want to use an E() with no IV, that's all :)

Let me try to write clearer pseudo-code, but also more verbose :(  And
yes, there had been two bugs that I just noticed: 1) the encrypt side
didn't quite handle non-short plaintexts, 2) I was missing an XOR of
cipherState in the decrypt side.

   L(x) = length of x

encryption function
                      if (L(P) >= c)
                          PC = 0
                          P' = P
                      else
                          PC = c - L(P)
                          P' = P | zeroblock[0:PC]
                      N = random nonce of length c (128 bits)
                      IV = N XOR cipherState
                      C = E(Ke, P', IV)
                          // using CBC-CS3-Encrypt defined
                          // in [SP800-38A+]
                      if (PC > 0)
                          N' = N[0:c - PC] | C[c - PC:PC]
                          C' = C[0:c - PC]
                      else
                          N' = N
                          C' = C
                      H = HMAC(Ki, N' | C')
                      ciphertext =  N' | C' | H[1..h]
                      cipherState = N

decryption function
                      (N', C', H) = ciphertext

                      if (L(C') >= c)
                          // Not short-plaintext
                          IV = N' XOR cipherState
                          P = D(Ke, C', IV)
                              // using CBC-CS3-Decrypt defined
                              // in [SP800-38A+]
                          cipherState = N'
                          stop, output P, success

                      // Short plaintext
                      PC = c - L(C')
                      C = C' | N[c - PC:PC]
                      P' = D(Ke, C, zeroblock) // basically no IV
                           // using CBC-CS3-Decrypt defined
                           // in [SP800-38A+], but equivalent to ECB
                           // with no IV; we have to fix up P' below
                      // We need to compute the IV to recover P
                      // with and cipherState
                      //
                      // N' had been N[0:c - PC] | C[c - PC:PC] and
                      // we'd taken c-PC bytes from the original N to
                      // make P'.  First we reconstruct N:
                      N = N'[0:c - PC] | P'[c - PC:PC]

                      // Then use N to recover the IV (as above)
                      IV = N XOR cipherState

                      // XOR P' with the IV (because we used a zero IV
                      // in D above, so we have to handle that here;
                      // it's just one block, so this works), truncate
                      // the result, and update the cipherState
                      P = (P' XOR IV)[0:c - PC]
                      cipherState = N
                      stop, output P, success

---

From: Nico Williams <[email-masked]>
Date: Wed, 29 May 2013 15:52:04 -0500

Greg points out that for the short plaintext case I really have to
clarify that E() and D() are ECB mode.

   L(x) = length of x

encryption function
                      if (L(P) > c)
                          C = E(Ke, P' XOR IV)
                              // using ECB mode

decryption function
                      (N', C', H) = ciphertext

                      if (L(C') >= c)
                          // Not short-plaintext
                          IV = N' XOR cipherState
                          P = D(Ke, C', IV)

                      // Short plaintext
                      PC = c - L(C')
                      C = C' | N[c - PC:PC]
                      P' = D(Ke, C)
                           // using ECB mode

---

From: Nico Williams <[email-masked]>
Date: Thu, 30 May 2013 14:57:11 -0500

Kelly points out that the decrypt side I posted doesn't update
cipherState properly and offers example inputs to work the code
through.  This should fix it (example below):

decryption function
                      (N', C', H) = ciphertext

                      if (L(C') >= c)
                          // Not short-plaintext
                          IV = N' XOR cipherState
                          P = D(Ke, C', IV)

                      // Short plaintext
                      PC = c - L(C')
                      C = C' | N[c - PC:PC]
                      P' = D(Ke, C)
                           // using ECB mode

                      // P' here == (P | zeroblock[0:PC]) XOR IV
                      // so IV[c - PC:PC] == P'[c - PC:PC]
                      // In the non-short-pt case we'd recover
                      // IV as N XOR cipherState, but here we only know
                      // a head of N and tail of IV.

                      N = N'[0:c -PC] | (P' XOR cipherState)[c - PC:PC]
                      IV = N XOR cipherState

                      P = (P' XOR IV)[0:PC]
                      cipherState = N
                      stop, output P, success

Kelly proposes that we "suppose P = 1111, N = 10101010...., and
cipherState = 010101010.... so that IV = 1111111.... (where the ...
means the pattern repeats to fill out the block). Then the value
encrypted is P+IV = 000011111111... which is the same value the
decryptor ends up with as P'. N' is also defined to be 1010******
where the ***** is ciphertext".

In Kelly's example PC = 12 (16 - 4).  We need substring operations
[0:4] and [4:12]

So on the decrypt side N[0:4] == 1010, P'[0:4] = 0000, while P'[4:12]
== 111111... == IV[4:12].  We have to recover either N[4:12] or
IV[0:4], and then we can recover the other by XORing with cipherState.
 With the above pseudo code then we have:

   N = 1010 | (1111... XOR cipherState)[4:12]
   N = 1010 | 1111...[4:12] XOR 0101...[4:12]
   N = 10101010...
   IV = N XOR cipherState == 1111...
   P = (P' XOR IV)[0:4] == 11110000...[0:4] == 1111

So we recover the P correctly, and because we recover N correctly we
then set cipherState correctly.

Note that this:

   N = N'[0:PC] | (P' XOR cipherState)[c - PC:PC]
   IV = N XOR cipherState

is equivalent to this:

   IV = (N' XOR cipherState)[0:PC] | P'[c - PC:PC]
   N = IV XOR cipherState

If we plug data into that we get:

   IV = (1010****... XOR cipherState)[0:4] | P'[4:12]
   IV = 1010 XOR 0101 | 1111...
   IV = 1111 | 1111... == 1111..
   N = 1111... XOR 0101... == 1010...

and then P and cipherState come out the same as above.

Nico
--

---

From: Kelley Burgin <[email-masked]>
Date: Fri, 31 May 2013 11:59:59 -0400

This looks great. 

Last comment (I think): The encrypt side considers the case L(P) = c to be short-plaintext, whereas the decrypt side considers it not short ("L(P) > c" vs "L(C') >= c"). 

Also, guess C = C' | N[c - PC:PC] in the short-plaintext decrypt should use N'.

Kelley

---

From: Nico Williams <[email-masked]>
Date: Fri, 31 May 2013 15:45:27 -0500

> This looks great.

Awesome.

> Last comment (I think): The encrypt side considers the case L(P) = c to be short-plaintext, whereas the decrypt side considers it not short ("L(P) > c" vs "L(C') >= c").

Let's call that a typo :)  It should be > in both cases.

> Also, guess C = C' | N[c - PC:PC] in the short-plaintext decrypt should use N'.

Also a typo.

Nico
--