chiark - git - mdw - ocb-tv/blob - README

   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.