| 1 | OCB3 test vectors for larger block sizes |
| 2 | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| 3 | |
| 4 | This distribution contains (what I intend to be) a reference |
| 5 | implementation for OCB3 with unusual block sizes (i.e., not 128 bits). |
| 6 | |
| 7 | |
| 8 | Extending OCB3 |
| 9 | |
| 10 | Unfortunately, defining OCB3 for a new block size is not trivial. Here |
| 11 | are the details which need to be addressed for a new block size w. |
| 12 | |
| 13 | * OCB3 does arithmetic in the finite field GF(2^w). It consistently |
| 14 | uses a polynomial basis representation, so GF(2^w) =~ |
| 15 | GF(2)[x]/(p(x)) for an irreducible polynomial p. Choose p to be the |
| 16 | lexicographically earliest of those irreducible polynomials with |
| 17 | smallest degree. |
| 18 | |
| 19 | * OCB3 uses a strongly XOR-universal hash to amortize the overhead of |
| 20 | encrypting nonces over several messages. This hash stretches a |
| 21 | w-bit string x into a 2 w bit string x || (x XOR x << c), and then |
| 22 | picks out i overlapping w-bit windows starting at position i, for 0 |
| 23 | <= i < D for a limit D. For w = 128, D = 64 and c = 8. In the |
| 24 | general case, D is the largest power of two such that c exists, and |
| 25 | c is the largest possible value out of those for which c mod 8 is |
| 26 | minimal -- i.e., we prefer shifts which are byte-aligned over ones |
| 27 | which aren't, and subjet to that we prefer larger shifts to smaller |
| 28 | ones. |
| 29 | |
| 30 | * OCB3 encodes the intended tag length t into the leftmost bits of the |
| 31 | nonce. The number of bits available for encoding the tag size is |
| 32 | ceil(log_2(w)): if w is a power of two, then t = w won't fit, and is |
| 33 | encoded as zero. |
| 34 | |
| 35 | |
| 36 | Example block ciphers |
| 37 | |
| 38 | Not everyone necessarily has Rijndael-256 knocking about, so here's a |
| 39 | simple block cipher for testing. It's four-round Luby--Rackoff with AES |
| 40 | as the round function, but with all of the details specified. Four |
| 41 | rounds is enough for strong-PRP security, but don't use this to extend |
| 42 | block size in real life because you lose when there are internal |
| 43 | collisions in the Luby--Rackoff construction, and that happens much |
| 44 | earlier than you'd hope for a blockcipher of this width. Also, it's |
| 45 | slow. |
| 46 | |
| 47 | As usual, let || denote concatenation of bitstrings. For an integer a |
| 48 | in {0, 1, ..., 2^w - 1}, let [a]_w be w-bit big-endian encoding of a, |
| 49 | i..e, the unique bitstring a_{w-1} || ... || a_1 || a_0 such that a = |
| 50 | SUM_{0<=i<w} a_i 2^i and each a_i in {0, 1} is a bit. For a bitstring |
| 51 | x, let l(x) be the length of x; if 0 <= i <= j <= l(x), then x[i..j] is |
| 52 | the (j - i)-bit substring of x, starting from position i, where the |
| 53 | leftmost bit is at position 0; hence, x = x[0..i] || x[i..j] || |
| 54 | x[j..l(x)]. |
| 55 | |
| 56 | Let w be the width of the blockcipher E that you already have, in bits. |
| 57 | Let w' <= 2 w be the width you wanted; I'm going to assume that w' is |
| 58 | even. Let K be a key suitable for E, and let k = l(K) be the length of |
| 59 | K in bits. Set n = ceil(k/w) and define K_i = (E(K; [n i]_w) || |
| 60 | E(K; [n i + 1]_w) || ... || E(K; [n i + n - 1]_w))[0..k] for |
| 61 | 0 <= i < 4. |
| 62 | |
| 63 | Given a w'-bit block x, set L_0 = x[0..w'/2], R_0 = x[w'/2..w'], and |
| 64 | then |
| 65 | |
| 66 | L_{i+1} = R_i XOR E(K_i; L_i || 0^{w-w'/2})[0..w'/2] |
| 67 | R_{i+1} = L_i |
| 68 | |
| 69 | Then E'(K, x) = R_4 || L_4. (As usual, there's no final swap in this |
| 70 | Feistel network.) |
| 71 | |
| 72 | Define LRAESw' to be E', with the given w' and E = AES (so w = 128). |
| 73 | Examples with intermediate results are included in the tarball, as |
| 74 | `lraesW.verbose'. Furthermore, to obtain a 512-bit block cipher, define |
| 75 | DLRAESw'' to be E'', with the given w'', w' = 256, and E = AES (so w = |
| 76 | 128). |
| 77 | |
| 78 | |
| 79 | Test vector files |
| 80 | |
| 81 | I used the following blockciphers: |
| 82 | |
| 83 | * 64-bit: 3DES and LRAES64; |
| 84 | * 96-bit: LRAES96; |
| 85 | * 128-bit: AES, Kalyna-128, and LRAES128; |
| 86 | * 192-bit: Rijndael-192 and LRAES192; and |
| 87 | * 256-bit: Rijndael-256, Kalyna-256, and LRAES256. |
| 88 | * 512-bit: Kalyna-512, and DLRAES512. |
| 89 | |
| 90 | For each blockcipher B, I made the following files: |
| 91 | |
| 92 | * ocb3-B-tT-nN.kat: A list of simple known-answer tests, using similar |
| 93 | input patterns to RFC7539, using blockcipher B with T-bit tag and |
| 94 | N-bit nonce. In particular, ocb3-aes-t128-n96.kat matches RFC7539. |
| 95 | It was just as easy for me to make a complete collection for the |
| 96 | alternative tag size, so ocb3-aes-t96-n96.kat has a complete |
| 97 | collection including the example from RFC7539, rather than just the |
| 98 | one selection. |
| 99 | |
| 100 | * ocb3-B-tT-nN.verbose: a worked example of one of the known-answer |
| 101 | tests, showing intermediate results. This differs in a few respects |
| 102 | from RFC7539: I picked a different example so as to demonstrate the |
| 103 | action of the `Auth' function (essentially PMAC3, I think); it |
| 104 | includes the augmented nonce with padding and the tag-length |
| 105 | indicator; and the order of the outputs is changed. |
| 106 | |
| 107 | * ocb3-B-nN.mct: the Monte--Carlo test, using blockcipher B with N-bit |
| 108 | nonce. The algorithm is as for RFC7539 (and, in particular, |
| 109 | ocb3-aes-n96.mct contains the same values as RFC7539), with the |
| 110 | following generalizations: the nonce is now variable-size, because a |
| 111 | 96-bit nonce is impossible for a 64-bit blockcipher; the initial |
| 112 | K-bit key is simply the K-bit big-endian encoding of the chosen tag |
| 113 | length T (which is equivalent to the RFC7539 algorithm when T < |
| 114 | 256), adjusted for odd parity for DES3 (thereby introducing some |
| 115 | ambiguity, which I have ignored). |
| 116 | |
| 117 | I made some arbitrary decisions about the various lengths to test. It's |
| 118 | quite possible that I failed to understand something important. |
| 119 | |
| 120 | * For a W-bit blockcipher, I picked W and 3/4 W bits as the tag |
| 121 | lengths to test. |
| 122 | |
| 123 | * For a W-bit blockcipher, I picked 3/4 W bits as the nonce length. |
| 124 | 96 bits is (presumably because of GCM) the IETF's official |
| 125 | nonce-length selection, but it certainly won't work with 64- or |
| 126 | 96-bit blockciphers (with OCB3), and seems immensely wasteful at |
| 127 | larger block sizes. Of the decisions I took, this seems like the |
| 128 | one I'm most likely to have to change. That's fine. |
| 129 | |
| 130 | * For a W-bit blockcipher, I picked i/2 W (for 0 < i < 6) as the |
| 131 | message and header lengths to test, so as to test a decent mix of |
| 132 | block-aligned and non-block-aligned input lengths. |