Subject: [Cfrg] OCB test vectors reusing nonces

From: "Manger, James" <[email-masked]>
Date: Thu, 23 Jan 2014 17:13:40 +1100

I have implemented OCB authenticated encryption as per draft-irtf-cfrg-ocb-05.
I concur with the sample results in Appendix A.

The sample results include 16 { aad, plaintext, ciphertext} tuples, but they are all for a tag length of 128.
It would be nice to include 1 similar sample with another tag length (in addition to the final section of Appendix A that does include results for other tag lengths, but only after a more complex combination of 385 encryptions).

The first 16 samples all use the same key and nonce.
The last 9 samples involve reusing key & nonce pairs 3 times.
A crucial feature of OCB is that a key & nonce pair MUST NOT be reused.
The sample results should not violate this crucial condition.
The samples might actually be hard to run in some implementations that take strong measures to prevent nonce reuse.

I suggest using incrementing nonces for the samples:
OLD

   Each of the following (A,P,C) triples show the ciphertext C that

   results from OCB-ENCRYPT(K,N,A,P) when K and N are fixed with the

   values

   K : 000102030405060708090A0B0C0D0E0F

   N : 000102030405060708090A0B

   An empty entry indicates the empty string.

     A:

     P:

     C: 197B9C3C441D3C83EAFB2BEF633B9182

     A: 0001020304050607

     P: 0001020304050607

     C: 92B657130A74B85A16DC76A46D47E1EAD537209E8A96D14E

   ...

NEW

   Each of the following (N,A,P,C) tuples show the ciphertext C that

   results from OCB-ENCRYPT(K,N,A,P) when K is fixed with the

   value

   K : 000102030405060708090A0B0C0D0E0F

   An empty entry indicates the empty string. The nonces are incrementing.

     N: BBAA99887766554433221100

     A:

     P:

     C: 785407BFFFC8AD9EDCC5520AC9111EE6

     N: BBAA99887766554433221101

     A: 0001020304050607

     P: 0001020304050607

     C: 6820B3657B6F615A5725BDA0D3B4EB3A257C9AF1F8F03009

   ...

OLD

   K = zeros(KEYLEN)                  // Keylength of AES in use

   C = <empty string>

   for i = 0 to 127 do

      S = zeros(8i)                   // i bytes of zeros

      N = zeros(88) || num2str(i,8)   // 11 byte zero then 1 byte i

      C = C || OCB-ENCRYPT(K,N,S,S)

      C = C || OCB-ENCRYPT(K,N,<empty string>,S)

      C = C || OCB-ENCRYPT(K,N,S,<empty string>)

   end for

   N = zeros(96)

   Output : OCB-ENCRYPT(K,N,C,<empty string>)

NEW

   K = zeros(KEYLEN)                  // Keylength of AES in use

   C = <empty string>

   for i = 0 to 127 do

      S = zeros(8i)                   // i bytes of zeros

      N = zeros(80) || num2str(i,8) || num2str(1,8)

      C = C || OCB-ENCRYPT(K,N,S,S)

      N = zeros(80) || num2str(i,8) || num2str(2,8)

      C = C || OCB-ENCRYPT(K,N,<empty string>,S)

      N = zeros(80) || num2str(i,8) || num2str(3,8)

      C = C || OCB-ENCRYPT(K,N,S,<empty string>)

   end for

   N = zeros(96)

   Output : OCB-ENCRYPT(K,N,C,<empty string>)

   ...and change the results accordingly...

Other than these tweak to the samples, the OCB spec looks great.

--
James Manger

---

From: Matt Caswell <[email-masked]>
Date: Thu, 23 Jan 2014 23:28:13 +0000

On 23 January 2014 06:13, Manger, James <[email-masked]> wrote:
> It would be nice to include 1 similar sample with another tag length (in
> addition to the final section of Appendix A that does include results for
> other tag lengths, but only after a more complex combination of 385
> encryptions).

For info, in my own OCB implementation I used the following additional
sample result with alternative tag length (96 bits). This was
generated using the reference implementation. Key and nonce as per the
other samples:

A: 000102030405060708090A0B0C0D0E0F1011121314151617
18191A1B1C1D1E1F2021222324252627
P: 000102030405060708090A0B0C0D0E0F1011121314151617
18191A1B1C1D1E1F2021222324252627
C:09A4FD29DE949D9A9AA9924248422097AD4883B4713E6C21
4FF6567ADA08A96766FC4E2EE3E3A5A11B6C44F34E3ABB3CBF8976E7

I have validated this against my own implementation (a patch for
OpenSSL) available here:

https://rt.openssl.org/Ticket/Display.html?id=3181&user=guest&pass=guest

Regards

Matt

---

From: Ted Krovetz <[email-masked]>
Date: Thu, 23 Jan 2014 17:22:32 -0800

Thanks James for verifying the vectors. 

I'm reluctant to modify the draft this substantially at this point in the process. Such a change might significantly delay its progress.

Although I agree that your selection of tests is probably better than those in the draft, I also believe that the vectors in the draft along with reference implementations is sufficient to produce a correct implementation.

-Ted

On Jan 22, 2014, at 10:13 PM, Manger, James <[email-masked]> wrote:

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: "Manger, James" <[email-masked]>
Date: Fri, 24 Jan 2014 16:54:23 +1100

> From: Ted Krovetz [mailto:[email-masked]]
> 
> I'm reluctant to modify the draft this substantially at this point in
> the process. Such a change might significantly delay its progress.
> 
> Although I agree that your selection of tests is probably better than
> those in the draft, I also believe that the vectors in the draft along
> with reference implementations is sufficient to produce a correct
> implementation.

8 of the ciphertexts in appendix A start identically (BEA5E8798DB...) and 2 others start identically (92B657130A7...).
This does not look good. It causes confusion.
That is exactly the sort of behaviour that is supposed to be prevented by the provable security OCB enjoys.

OCB has a nice design feature that allows the AES operation applied to the nonce to be avoided 63 out of 64 times, if using incrementing nonces.
It is far more likely that this design feature will be tested if appendix A uses incrementing nonces (particularly for the 385 operations in each of the last tests).

For the above two reasons I think it would be worth updating the test vectors, despite some risk of causing a slight delay. Surely the draft doesn’t have to repeat much of the vetting process if only sample results change. I am willing to confirm new test vectors quickly.

Earlier I suggested nonces such as:
  N = zeros(80) || num2str(i,8) || num2str(1,8) 
  N = zeros(80) || num2str(i,8) || num2str(2,8) 
  N = zeros(80) || num2str(i,8) || num2str(3,8) 

If you do make a change, it would be even better for the nonces to be:
  N = num2str(3*i+1,96)
  N = num2str(3*i+2,96)
  N = num2str(3*i+3,96)

Or phrase it as:
  N = zeros(96)      // incremented before each use
  for i = 0 to 127 do
     S = zeros(8i)                   // i bytes of zeros
     N = N + 1
     C = C || OCB-ENCRYPT(K,N,S,S)
     N = N + 1
     C = C || OCB-ENCRYPT(K,N,<empty string>,S)
     N = N + 1
     C = C || OCB-ENCRYPT(K,N,S,<empty string>)
  end for
  N = N + 1          // 00...0181 after 385 increments
  Output : OCB-ENCRYPT(K,N,C,<empty string>)

--
James Manger

> > The sample results include 16 { aad, plaintext, ciphertext} tuples,
> but they are all for a tag length of 128.
> > It would be nice to include 1 similar sample with another tag length
> (in addition to the final section of Appendix A that does include
> results for other tag lengths, but only after a more complex
> combination of 385 encryptions).
> >
> > The samples might actually be hard to run in some implementations
> that take strong measures to prevent nonce reuse.
> >

---

From: Ted Krovetz <[email-masked]>
Date: Sun, 26 Jan 2014 07:11:13 -0800

> For the above two reasons I think it would be worth updating the test vectors, despite some risk of causing a slight delay. Surely the draft doesn’t have to repeat much of the vetting process if on…

This makes sense. I'll do it. In the coming days I'll update the OCB vectors as James suggested, he and I will confirm the results, and I'll update the draft for others to verify.

-Ted

---

From: David McGrew <[email-masked]>
Date: Sun, 26 Jan 2014 10:19:01 -0500

Hi Ted,

> This makes sense. I'll do it. In the coming days I'll update the OCB vectors as James suggested, he and I will confirm the results, and I'll update the draft for others to verify.

that's great, thanks for being so responsive.

If anyone else would be able to independently verify the text cases 
between now and February 7, please contact Ted directly, and thanks in 
advance.

David

---

From: Stephen Farrell <[email-masked]>
Date: Sun, 26 Jan 2014 15:23:18 +0000

On 01/26/2014 03:19 PM, David McGrew wrote:
>>> For the above two reasons I think it would be worth updating the test
>>> vectors, despite some risk of causing a slight delay. Surely the
>>> draft doesn’t have to repeat much of the vetting process if only
>>> sample results change. I am willing to confirm new test vectors quickly.
>> This makes sense. I'll do it. In the coming days I'll update the OCB
>> vectors as James suggested, he and I will confirm the results, and
>> I'll update the draft for others to verify.
> 

I won't be able to do that, but can confirm that this wouldn't
affect my IRSG review etc. And it does seem like a good idea.

S.

---

From: "Manger, James" <[email-masked]>
Date: Tue, 28 Jan 2014 16:21:30 +1100

Ted,

Attached is my version of the updated test vectors for appendix A of draft-irtf-cfrg-ocb.

The first 16 {N,A,P,C} tuples use incrementing nonces.

I added one example with a 96-bit tag and a separate key (since we recommend using a single tag length with any given key). It uses the same nonce as the 128-bit tag example with the same A and P.

The final examples use incrementing nonces.

I made minor changes to the text.

--
James Manger

> -----Original Message-----
> From: Cfrg [mailto:[email-masked]] On Behalf Of Ted Krovetz
> Sent: Monday, 27 January 2014 2:11 AM
> To: [email-masked]
> Subject: Re: [Cfrg] OCB test vectors reusing nonces
> 
> 
> vectors, despite some risk of causing a slight delay. Surely the draft
> doesn’t have to repeat much of the vetting process if only sample
> results change. I am willing to confirm new test vectors quickly.
> 
> vectors as James suggested, he and I will confirm the results, and I'll
> update the draft for others to verify.
> 
> -Ted

---

From: Matt Caswell <[email-masked]>
Date: Tue, 28 Jan 2014 22:58:23 +0000

> I made minor changes to the text.

I have successfully managed to verify all of these proposed test
vectors with my implementation of OCB.

However, I understood that one of your objectives for proposing a
change to the test vectors was to not reuse the same key and nonce
within the tests. This objective has not been achieved in the final
set of 9 more complex tests. Whilst you have incremented the nonce
between each encryption within a test, each test starts with an all
zero nonce and a fixed key.

Also - a more minor nit - your notation for incrementing the nonce
seems odd to me. The nonce is defined as a string of bytes - whereas
in your notation it is treated as an integer which can be incremented.

Matt

---

From: "Manger, James" <[email-masked]>
Date: Wed, 29 Jan 2014 12:06:07 +1100

Matt,

> > I added one example with a 96-bit tag and a separate key (since we
> recommend using a single tag length with any given key). It uses the
> same nonce as the 128-bit tag example with the same A and P.
> >

> vectors with my implementation of OCB.

Great!

> zero nonce and a fixed key.

True, the final 9 more complex tests don't quite meet the security recommendations. Nonces do get reused, though only with different tag lengths (or different keys). I'm sure that isn't a security problem as the tag length and nonce are combined into a 128-bit "internal nonce" (which is not repeated for the same key), but I guess it isn't ideal.
The same key is used with 3 different tag lengths. That does go against a security recommendation.

One solution is to change the key for each tag length, giving 9 distinct keys for the 9 cases.

   K = num2str(TAGLEN, KEYLEN)    // eg 00..0040 when TAGLEN == 64

I then get:

   AEAD_AES_128_OCB_TAGLEN128 Output: 67E944D23256C5E0B6C61FA22FDF1EA2
   AEAD_AES_192_OCB_TAGLEN128 Output: F673F2C3E7174AAE7BAE986CA9F29E17
   AEAD_AES_256_OCB_TAGLEN128 Output: D90EB8E9C977C88B79DD793D7FFA161C
   AEAD_AES_128_OCB_TAGLEN96 Output : 77A3D8E73589158D25D01209
   AEAD_AES_192_OCB_TAGLEN96 Output : 05D56EAD2752C86BE6932C5E
   AEAD_AES_256_OCB_TAGLEN96 Output : 5458359AC23B0CBA9E6330DD
   AEAD_AES_128_OCB_TAGLEN64 Output : 192C9B7BD90BA06A
   AEAD_AES_192_OCB_TAGLEN64 Output : 0066BC6E0EF34E24
   AEAD_AES_256_OCB_TAGLEN64 Output : 7D4EA5D445501CBE

> in your notation it is treated as an integer which can be incremented.

I think "N = N + 1" is more obvious than "N = num2str(3*i + 1, 96)", even if it does mix byte strings and arithmetic.

--
James Manger

---

From: Matt Caswell <[email-masked]>
Date: Wed, 29 Jan 2014 19:50:16 +0000

>    AEAD_AES_256_OCB_TAGLEN64 Output : 7D4EA5D445501CBE

I have successfully verified these.

> I think "N = N + 1" is more obvious than "N = num2str(3*i + 1, 96)", even if it does mix byte strings and arithmetic.

Agreed. One possibility is just to use the convention used elsewhere
in the draft and define a function for this purpose, e.g. "N =
incrementstr(N)".

Matt

---

From: Ted Krovetz <[email-masked]>
Date: Thu, 30 Jan 2014 10:45:43 -0800

James,

I've updated the OCB draft to include all your changes in the test vector section and have verified the results. Thank you very much for the suggestions and hard work implementing them.

The one suggestion I did not include was N = N + 1 in the final vector algorithm. I felt that that might suggest an implementation as a simple counter, which can easily cause mistakes (either because of endian issues or the fact that the counter exceeds a byte), so I just kept it specified using num2str.

Thanks Matt Caswell, too, for verifying the vectors. With three independent implementations all agreeing, I have pretty good confidence in their correctness.

-Ted