From 632f5e9a34e79245895ded44887ccae475319198 Mon Sep 17 00:00:00 2001
Message-Id: <632f5e9a34e79245895ded44887ccae475319198.1714437728.git.mdw@distorted.org.uk>
From: Mark Wooding <mdw@chiark.greenend.org.uk>
Date: Sun, 16 Jul 2017 16:07:29 +0100
Subject: [PATCH] README: Include some useful documentation.
Organization: Straylight/Edgeware

From: Mark Wooding <mdw@distorted.org.uk>

---
 Makefile |   2 +
 README   | 132 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 134 insertions(+)
 create mode 100644 README

diff --git a/Makefile b/Makefile
index ccfe86d..433f808 100644
--- a/Makefile
+++ b/Makefile
@@ -251,6 +251,8 @@ dlraes512.verbose: ocbgen Makefile
 
 all:: $(TARGETS)
 
+DIST			+= README
+
 DISTDIR			 = ocb-tv
 
 dist: all
diff --git a/README b/README
new file mode 100644
index 0000000..0f9c4f0
--- /dev/null
+++ b/README
@@ -0,0 +1,132 @@
+OCB3 test vectors for larger block sizes
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+This distribution contains (what I intend to be) a reference
+implementation for OCB3 with unusual block sizes (i.e., not 128 bits).
+
+
+Extending OCB3
+
+Unfortunately, defining OCB3 for a new block size is not trivial.  Here
+are the details which need to be addressed for a new block size w.
+
+  * OCB3 does arithmetic in the finite field GF(2^w).  It consistently
+    uses a polynomial basis representation, so GF(2^w) =~
+    GF(2)[x]/(p(x)) for an irreducible polynomial p.  Choose p to be the
+    lexicographically earliest of those irreducible polynomials with
+    smallest degree.
+
+  * OCB3 uses a strongly XOR-universal hash to amortize the overhead of
+    encrypting nonces over several messages.  This hash stretches a
+    w-bit string x into a 2 w bit string x || (x XOR x << c), and then
+    picks out i overlapping w-bit windows starting at position i, for 0
+    <= i < D for a limit D.  For w = 128, D = 64 and c = 8.  In the
+    general case, D is the largest power of two such that c exists, and
+    c is the largest possible value out of those for which c mod 8 is
+    minimal -- i.e., we prefer shifts which are byte-aligned over ones
+    which aren't, and subjet to that we prefer larger shifts to smaller
+    ones.
+
+  * OCB3 encodes the intended tag length t into the leftmost bits of the
+    nonce.  The number of bits available for encoding the tag size is
+    ceil(log_2(w)): if w is a power of two, then t = w won't fit, and is
+    encoded as zero.
+
+
+Example block ciphers
+
+Not everyone necessarily has Rijndael-256 knocking about, so here's a
+simple block cipher for testing.  It's four-round Luby--Rackoff with AES
+as the round function, but with all of the details specified.  Four
+rounds is enough for strong-PRP security, but don't use this to extend
+block size in real life because you lose when there are internal
+collisions in the Luby--Rackoff construction, and that happens much
+earlier than you'd hope for a blockcipher of this width.  Also, it's
+slow.
+
+As usual, let || denote concatenation of bitstrings.  For an integer a
+in {0, 1, ..., 2^w - 1}, let [a]_w be w-bit big-endian encoding of a,
+i..e, the unique bitstring a_{w-1} || ... || a_1 || a_0 such that a =
+SUM_{0<=i<w} a_i 2^i and each a_i in {0, 1} is a bit.  For a bitstring
+x, let l(x) be the length of x; if 0 <= i <= j <= l(x), then x[i..j] is
+the (j - i)-bit substring of x, starting from position i, where the
+leftmost bit is at position 0; hence, x = x[0..i] || x[i..j] ||
+x[j..l(x)].
+
+Let w be the width of the blockcipher E that you already have, in bits.
+Let w' <= 2 w be the width you wanted; I'm going to assume that w' is
+even.  Let K be a key suitable for E, and let k = l(K) be the length of
+K in bits.  Set n = ceil(k/w) and define K_i = (E(K; [n i]_w) ||
+E(K; [n i + 1]_w) || ... || E(K; [n i + n - 1]_w))[0..k] for
+0 <= i < 4.
+
+Given a w'-bit block x, set L_0 = x[0..w'/2], R_0 = x[w'/2..w'], and
+then
+
+       L_{i+1} = R_i XOR E(K_i; L_i || 0^{w-w'/2})[0..w'/2]
+       R_{i+1} = L_i
+
+Then E'(K, x) = R_4 || L_4.  (As usual, there's no final swap in this
+Feistel network.)
+
+Define LRAESw' to be E', with the given w' and E = AES (so w = 128).
+Examples with intermediate results are included in the tarball, as
+`lraesW.verbose'.  Furthermore, to obtain a 512-bit block cipher, define
+DLRAESw'' to be E'', with the given w'', w' = 256, and E = AES (so w =
+128).
+
+
+Test vector files
+
+I used the following blockciphers:
+
+ * 64-bit: 3DES and LRAES64;
+ * 96-bit: LRAES96;
+ * 128-bit: AES, Kalyna-128, and LRAES128;
+ * 192-bit: Rijndael-192 and LRAES192; and
+ * 256-bit: Rijndael-256, Kalyna-256, and LRAES256.
+ * 512-bit: Kalyna-512, and DLRAES512.
+
+For each blockcipher B, I made the following files:
+
+ * ocb3-B-tT-nN.kat: A list of simple known-answer tests, using similar
+   input patterns to RFC7539, using blockcipher B with T-bit tag and
+   N-bit nonce.  In particular, ocb3-aes-t128-n96.kat matches RFC7539.
+   It was just as easy for me to make a complete collection for the
+   alternative tag size, so ocb3-aes-t96-n96.kat has a complete
+   collection including the example from RFC7539, rather than just the
+   one selection.
+
+ * ocb3-B-tT-nN.verbose: a worked example of one of the known-answer
+   tests, showing intermediate results.  This differs in a few respects
+   from RFC7539: I picked a different example so as to demonstrate the
+   action of the `Auth' function (essentially PMAC3, I think); it
+   includes the augmented nonce with padding and the tag-length
+   indicator; and the order of the outputs is changed.
+
+ * ocb3-B-nN.mct: the Monte--Carlo test, using blockcipher B with N-bit
+   nonce.  The algorithm is as for RFC7539 (and, in particular,
+   ocb3-aes-n96.mct contains the same values as RFC7539), with the
+   following generalizations: the nonce is now variable-size, because a
+   96-bit nonce is impossible for a 64-bit blockcipher; the initial
+   K-bit key is simply the K-bit big-endian encoding of the chosen tag
+   length T (which is equivalent to the RFC7539 algorithm when T <
+   256), adjusted for odd parity for DES3 (thereby introducing some
+   ambiguity, which I have ignored).
+
+I made some arbitrary decisions about the various lengths to test.  It's
+quite possible that I failed to understand something important.
+
+ * For a W-bit blockcipher, I picked W and 3/4 W bits as the tag
+   lengths to test.
+
+ * For a W-bit blockcipher, I picked 3/4 W bits as the nonce length.
+   96 bits is (presumably because of GCM) the IETF's official
+   nonce-length selection, but it certainly won't work with 64- or
+   96-bit blockciphers (with OCB3), and seems immensely wasteful at
+   larger block sizes.  Of the decisions I took, this seems like the
+   one I'm most likely to have to change.  That's fine.
+
+ * For a W-bit blockcipher, I picked i/2 W (for 0 < i < 6) as the
+   message and header lengths to test, so as to test a decent mix of
+   block-aligned and non-block-aligned input lengths.
-- 
[mdw]