Internet DRAFT - draft-krovetz-ocb-wideblock
draft-krovetz-ocb-wideblock
Internet Engineering Task Force T. Krovetz
Internet-Draft Sacramento State
Updates: 7523 (if approved) May 11, 2018
Intended status: Informational
Expires: November 12, 2018
OCB For Block Ciphers Without 128-Bit Blocks
draft-krovetz-ocb-wideblock-00
Abstract
The OCB authenticated-encryption algorithm is specified in RFC 7523,
but only for blockciphers with 128-bit blocks such as AES. This
document extends RFC 7523 by specifying how OCB is used with
blockciphers of any blocklength. When the blocklength is 128 bits,
this specification and that in RFC 7523 are identical.
Status of This Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on November 12, 2018.
Copyright Notice
Copyright (c) 2018 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
Krovetz Expires November 12, 2018 [Page 1]
Internet-Draft OCB for non-128-bit cipher blocks May 2018
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Notation and Basic Operations . . . . . . . . . . . . . . . . 3
3. OCB Global Parameters . . . . . . . . . . . . . . . . . . . . 4
3.1. Constants Derived From BLOCKLEN . . . . . . . . . . . . . 5
4. OCB Algorithms . . . . . . . . . . . . . . . . . . . . . . . 5
4.1. Associated-Data Processing: HASH . . . . . . . . . . . . 5
4.2. Encryption: OCB-ENCRYPT . . . . . . . . . . . . . . . . . 8
4.3. Decryption: OCB-DECRYPT . . . . . . . . . . . . . . . . . 9
5. Security Considerations . . . . . . . . . . . . . . . . . . . 11
5.1. Nonce Requirements . . . . . . . . . . . . . . . . . . . 13
6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 13
7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 13
8. References . . . . . . . . . . . . . . . . . . . . . . . . . 14
8.1. Normative References . . . . . . . . . . . . . . . . . . 14
8.2. Informative References . . . . . . . . . . . . . . . . . 14
Appendix A. Sample Results . . . . . . . . . . . . . . . . . . . 14
A.1. Example 1: 64-bit Blockcipher, 0-byte Input . . . . . . . 15
A.2. Example 2: 64-bit Blockcipher, 4-byte Input . . . . . . . 15
A.3. Example 3: 64-bit Blockcipher, 8-byte Input . . . . . . . 16
A.4. Example 4: 64-bit Blockcipher, 20-byte Input . . . . . . 17
A.5. Example 5: 256-bit Blockcipher, 80-byte Input . . . . . . 19
A.6. Example 6: Extended Tests . . . . . . . . . . . . . . . . 21
Appendix B. Generating RESIDUE, SHIFT, MASKLEN, TAGREP Constants 22
B.1. Sage Script For Generating MASKLEN and SHIFT . . . . . . 23
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 24
1. Introduction
OCB is a shared-key, blockcipher-based authentication scheme
specified in [RFC7523]. It was designed with the AES blockcipher in
mind and thus envisioned only being used with 128-bit blockciphers.
The resulting RFC 7523 does not allow blockciphers with larger or
smaller blocklengths. This document respecifies OCB in a more
general manner, eliminating the expectation that a 128-bit
blockcipher is used. This update is consistent with RFC 7523 and
does not contradict it in any way. For applications using 128-bit
blockciphers, RFC 7523 should be preferred because it is simpler,
self-contained, and has more applicable test vectors.
Changing the blocklength used in OCB is not a simple matter. There
are non-trivially defined constants used in OCB that must be
recalculated for each different blocklength. What follows is largely
Krovetz Expires November 12, 2018 [Page 2]
Internet-Draft OCB for non-128-bit cipher blocks May 2018
a copy of the algorithms from RFC 7523, made more general by using
blocklength-dependent symbolic constants.
The security of OCB continues to follow a birthday bound. Both the
confidentiality and the authenticity properties of OCB degrade as per
s^2 / 2^b, where s is the total number of blocks that the adversary
acquires and b is the number of bits per blockcipher block. Note
that this means security degrades rapidly when using a blockcipher
with a small to moderate blocklength.
2. Notation and Basic Operations
There are two types of variables used in this specification, strings
and integers. Although strings processed by most implementations of
OCB will be strings of bytes, bit-level operations are used
throughout this specification document for defining OCB. String
variables are always written with an initial upper-case letter while
integer variables are written in all lower-case. Following C's
convention, a single equals ("=") indicates variable assignment and
double equals ("==") is the equality relation. Whenever a variable
is followed by an underscore ("_"), the underscore is intended to
denote a subscript, with the subscripted expression requiring
evaluation to resolve the meaning of the variable. For example, when
i == 2, then P_i refers to the variable P_2.
c^i The integer c raised to the i-th power.
bitlen(S) The length of string S in bits (eg, bitlen(001) == 3).
zeros(n) The string made of n zero-bits.
ntz(n) The number of trailing zero bits in the base-2
representation of the positive integer n. More
formally, ntz(n) is the largest integer x for which 2^x
divides n.
S xor T The string that is the bitwise exclusive-or of S and T.
Strings S and T will always have the same length.
S[i] The i-th bit of the string S (indices begin at 1, so if
S is 011 then S[1] == 0, S[2] == 1, S[3] == 1).
S[i..j] The substring of S consisting of bits i through j,
inclusive.
S || T String S concatenated with string T (eg, 000 || 111 ==
000111).
Krovetz Expires November 12, 2018 [Page 3]
Internet-Draft OCB for non-128-bit cipher blocks May 2018
str2num(S) The base-2 interpretation of bitstring S (eg,
str2num(1110) == 14).
num2str(i,n) The n-bit string whose base-2 interpretation is i (eg,
num2str(14,4) == 1110 and num2str(1,2) == 01).
double(S) If S[1] == 0 then double(S) == (S[2..bitlen(S)] || 0);
otherwise double(S) == (S[2..bitlen(S)] || 0) xor
num2str(RESIDUE,bitlen(S)) where RESIDUE is defined in
Section 3.1 or Appendix B.
3. OCB Global Parameters
To be complete, the algorithms in this document require specification
of two global parameters: a blockcipher and the length of
authentication tags in use.
Specifying a blockcipher implicitly defines the following symbols.
BLOCKLEN The blockcipher's blocklength, in bits.
KEYLEN The blockcipher's key length, in bits.
ENCIPHER(K,P) The blockcipher function mapping BLOCKLEN-bit
plaintext block P to its corresponding ciphertext
block using KEYLEN-bit key K.
DECIPHER(K,C) The inverse blockcipher function mapping BLOCKLEN-bit
ciphertext block C to its corresponding plaintext
block using KEYLEN-bit key K.
The TAGLEN parameter specifies the length of authentication tag used
by OCB and may be any positive value up to, and including, the
smaller of BLOCKLEN or 256.
As an example, if 128-bit authentication tags and AES with 192-bit
keys are to be used, then BLOCKLEN is 128, KEYLEN is 192, ENCIPHER
refers to the AES-192 cipher, DECIPHER refers to the AES-192 inverse
cipher, and TAGLEN is 128.
Greater values for TAGLEN provide greater assurances of authenticity,
but ciphertexts produced by OCB are longer than their corresponding
plaintext by TAGLEN bits. See Section 5 for details about TAGLEN and
security.
Krovetz Expires November 12, 2018 [Page 4]
Internet-Draft OCB for non-128-bit cipher blocks May 2018
3.1. Constants Derived From BLOCKLEN
Each value of BLOCKLEN gives rise to constants that need careful
choosing to ensure OCB security and efficiency. The value RESIDUE is
used in the definition of double given in Section 2, and the values
SHIFT, MASKLEN, and TAGREP are used in the OCB-ENCRYPT and OCB-
DECRYPT functions given in Section 4.
The following table lists these constants for a collection of
blockcipher blocklengths. If a blocklength is needed that is not in
the table, Appendix B gives the criteria and algorithm used to
determine the constants given here. The same criteria and algorithm
should be used to generate other constants for other blocklengths.
Note that there are attacks on OCB with success proportional to a
birthday bound related to BLOCKLEN. This means that using small
values of BLOCKLEN may lead quickly to poor security. See Section 5
for more information on the security bounds of OCB.
+----------+---------+-------+---------+--------+
| BLOCKLEN | RESIDUE | SHIFT | MASKLEN | TAGREP |
+----------+---------+-------+---------+--------+
| 32 | 141 | 17 | 4 | 5 |
| 64 | 27 | 25 | 5 | 6 |
| 96 | 1601 | 33 | 6 | 7 |
| 128 | 135 | 8 | 6 | 7 |
| 192 | 135 | 40 | 7 | 8 |
| 256 | 1061 | 1 | 8 | 8 |
| 384 | 4109 | 80 | 8 | 8 |
| 512 | 293 | 176 | 8 | 8 |
| 768 | 655377 | 160 | 9 | 8 |
| 1024 | 524355 | 352 | 9 | 8 |
| 1600 | 18435 | 192 | 10 | 8 |
+----------+---------+-------+---------+--------+
4. OCB Algorithms
OCB is described in this section using pseudocode. Given any
collection of inputs of the required types, following the pseudocode
description for a function will produce the correct output of the
promised type.
4.1. Associated-Data Processing: HASH
OCB has the ability to authenticate unencrypted associated data at
the same time that it provides for authentication and encrypts a
plaintext. The following hash function is central to providing this
functionality. If an application has no associated data, then the
Krovetz Expires November 12, 2018 [Page 5]
Internet-Draft OCB for non-128-bit cipher blocks May 2018
associated data should be considered to exist and to be the empty
string. HASH, conveniently, always returns zeros(BLOCKLEN) when the
associated data is the empty string.
Krovetz Expires November 12, 2018 [Page 6]
Internet-Draft OCB for non-128-bit cipher blocks May 2018
Function name:
HASH
Input:
K, string of KEYLEN bits // Key
A, string of any length // Associated data
Output:
Sum, string of BLOCKLEN bits // Hash result
Sum is defined as follows.
//
// Key-dependent variables
//
L_* = ENCIPHER(K, zeros(BLOCKLEN))
L_$ = double(L_*)
L_0 = double(L_$)
L_i = double(L_{i-1}) for every integer i > 0
//
// Consider A as a sequence of BLOCKLEN-bit blocks
//
Let m be the largest integer so that m * BLOCKLEN <= bitlen(A)
Let A_1, A_2, ..., A_m and A_* be strings so that
A == A_1 || A_2 || ... || A_m || A_*, and
bitlen(A_i) == BLOCKLEN for each 1 <= i <= m.
Note: A_* may possibly be the empty string.
//
// Process any whole blocks
//
Sum_0 = zeros(BLOCKLEN)
Offset_0 = zeros(BLOCKLEN)
for each 1 <= i <= m
Offset_i = Offset_{i-1} xor L_{ntz(i)}
Sum_i = Sum_{i-1} xor ENCIPHER(K, A_i xor Offset_i)
end for
//
// Process any final partial block; compute final hash value
//
if bitlen(A_*) > 0 then
Offset_* = Offset_m xor L_*
Zerofill = zeros(BLOCKLEN-(1+bitlen(A_*)))
CipherInput = (A_* || 1 || Zerofill) xor Offset_*
Sum = Sum_m xor ENCIPHER(K, CipherInput)
else
Sum = Sum_m
end if
Krovetz Expires November 12, 2018 [Page 7]
Internet-Draft OCB for non-128-bit cipher blocks May 2018
4.2. Encryption: OCB-ENCRYPT
This function computes a ciphertext (which includes a bundled
authentication tag) when given a plaintext, associated data, nonce
and key. For each invocation of OCB-ENCRYPT using the same key K,
the value of the nonce input N must be distinct.
Function name:
OCB-ENCRYPT
Input:
K, string of KEYLEN bits // Key
N, string of up to BLOCKLEN-(TAGREP+1) bits // Nonce
A, string of any length // Associated data
P, string of any length // Plaintext
Output:
C, string of length bitlen(P) + TAGLEN bits // Ciphertext
C is defined as follows.
//
// Key-dependent variables
//
L_* = ENCIPHER(K, zeros(BLOCKLEN))
L_$ = double(L_*)
L_0 = double(L_$)
L_i = double(L_{i-1}) for every integer i > 0
//
// Consider P as a sequence of BLOCKLEN-bit blocks
//
Let m be the largest integer so that m * BLOCKLEN <= bitlen(P)
Let P_1, P_2, ..., P_m and P_* be strings so that
P == P_1 || P_2 || ... || P_m || P_*, and
bitlen(P_i) == BLOCKLEN for each 1 <= i <= m.
Note: P_* may possibly be the empty string.
//
// Nonce-dependent and per-encryption variables
//
Zerofill = zeros(BLOCKLEN-(TAGREP+1+bitlen(N)))
Nonce = num2str(TAGLEN mod BLOCKLEN, TAGREP) || Zerofill || 1 || N
bottom = str2num(Nonce[BLOCKLEN-MASKLEN+1..BLOCKLEN])
Ktop = ENCIPHER(K, Nonce[1..BLOCKLEN-MASKLEN] || zeros(MASKLEN))
ShiftedKtop = Ktop[1..BLOCKLEN-SHIFT] xor Ktop[1+SHIFT..BLOCKLEN]
Stretch = Ktop || ShiftedKtop
Offset_0 = Stretch[1+bottom..BLOCKLEN+bottom]
Checksum_0 = zeros(BLOCKLEN)
Krovetz Expires November 12, 2018 [Page 8]
Internet-Draft OCB for non-128-bit cipher blocks May 2018
//
// Process any whole blocks
//
for each 1 <= i <= m
Offset_i = Offset_{i-1} xor L_{ntz(i)}
C_i = Offset_i xor ENCIPHER(K, P_i xor Offset_i)
Checksum_i = Checksum_{i-1} xor P_i
end for
//
// Process any final partial block and compute raw tag
//
if bitlen(P_*) > 0 then
Offset_* = Offset_m xor L_*
Pad = ENCIPHER(K, Offset_*)
C_* = P_* xor Pad[1..bitlen(P_*)]
PaddedP = P_* || 1 || zeros(BLOCKLEN-(bitlen(P_*)+1))
Checksum_* = Checksum_m xor PaddedP
Tag = ENCIPHER(K, Checksum_* xor Offset_* xor L_$) xor HASH(K,A)
else
C_* = <empty string>
Tag = ENCIPHER(K, Checksum_m xor Offset_m xor L_$) xor HASH(K,A)
end if
//
// Assemble ciphertext
//
C = C_1 || C_2 || ... || C_m || C_* || Tag[1..TAGLEN]
4.3. Decryption: OCB-DECRYPT
This function computes a plaintext when given a ciphertext,
associated data, nonce and key. An authentication tag is embedded in
the ciphertext. If the tag is not correct for the ciphertext,
associated data, nonce and key, then an INVALID signal is produced.
Function name:
OCB-DECRYPT
Input:
K, string of KEYLEN bits // Key
N, string of up to BLOCKLEN-(TAGREP+1) bits // Nonce
A, string of any length // Associated data
C, string of at least TAGLEN bits // Ciphertext
Output:
P, string of length bitlen(C) - TAGLEN bits, // Plaintext
or INVALID indicating authentication failure
P is defined as follows.
Krovetz Expires November 12, 2018 [Page 9]
Internet-Draft OCB for non-128-bit cipher blocks May 2018
//
// Key-dependent variables
//
L_* = ENCIPHER(K, zeros(BLOCKLEN))
L_$ = double(L_*)
L_0 = double(L_$)
L_i = double(L_{i-1}) for every integer i > 0
//
// Consider C as a sequence of BLOCKLEN-bit blocks
//
Let m be the largest integer so m * BLOCKLEN <= bitlen(C) - TAGLEN
Let C_1, C_2, ..., C_m, C_* and T be strings so that
C == C_1 || C_2 || ... || C_m || C_* || T,
bitlen(C_i) == BLOCKLEN for each 1 <= i <= m, and
bitlen(T) == TAGLEN.
Note: C_* may possibly be the empty string.
//
// Nonce-dependent and per-decryption variables
//
Zerofill = zeros(BLOCKLEN-(TAGREP+1+bitlen(N)))
Nonce = num2str(TAGLEN mod BLOCKLEN, TAGREP) || Zerofill || 1 || N
bottom = str2num(Nonce[BLOCKLEN-MASKLEN+1..BLOCKLEN])
Ktop = ENCIPHER(K, Nonce[1..BLOCKLEN-MASKLEN] || zeros(MASKLEN))
ShiftedKtop = Ktop[1..BLOCKLEN-SHIFT] xor Ktop[1+SHIFT..BLOCKLEN]
Stretch = Ktop || ShiftedKtop
Offset_0 = Stretch[1+bottom..BLOCKLEN+bottom]
Checksum_0 = zeros(BLOCKLEN)
//
// Process any whole blocks
//
for each 1 <= i <= m
Offset_i = Offset_{i-1} xor L_{ntz(i)}
P_i = Offset_i xor DECIPHER(K, C_i xor Offset_i)
Checksum_i = Checksum_{i-1} xor P_i
end for
//
// Process any final partial block and compute raw tag
//
if bitlen(C_*) > 0 then
Offset_* = Offset_m xor L_*
Pad = ENCIPHER(K, Offset_*)
P_* = C_* xor Pad[1..bitlen(C_*)]
PaddedP = P_* || 1 || zeros(BLOCKLEN-bitlen(P_*)-1)
Checksum_* = Checksum_m xor PaddedP
Krovetz Expires November 12, 2018 [Page 10]
Internet-Draft OCB for non-128-bit cipher blocks May 2018
Tag = ENCIPHER(K, Checksum_* xor Offset_* xor L_$) xor HASH(K,A)
else
P_* = <empty string>
Tag = ENCIPHER(K, Checksum_m xor Offset_m xor L_$) xor HASH(K,A)
end if
//
// Check for validity and assemble plaintext
//
if (Tag[1..TAGLEN] == T) then
P = P_1 || P_2 || ... || P_m || P_*
else
P = INVALID
end if
5. Security Considerations
What follows is a duplicate of the Security Considerations section of
RFC 7523 with numeric literals replaced by their symbolic
equivalents. With the ability to change BLOCKLEN comes two important
additional considerations. The amount of data that can safely be
processed using a single key is related to BLOCKLEN: a larger
BLOCKLEN allows more data whereas a smaller BLOCKLEN allows less.
Also, authentication tag lengths are limited to BLOCKLEN bits, which
means that using OCB with a small BLOCKLEN forces the use of small
tags. In all cases, but especially when reducing BLOCKLEN, a careful
evaluation of an application's security requirements should be
conducted and only if OCB, with a particular BLOCKLEN, meets those
requirements should it be used.
OCB achieves two security properties, confidentiality and
authenticity. Confidentiality is defined via "indistinguishability
from random bits", meaning that an adversary is unable to distinguish
OCB-outputs from an equal number of random bits. Authenticity is
defined via "authenticity of ciphertexts", meaning that an adversary
is unable to produce any valid nonce-ciphertext pair that it has not
already acquired. The security guarantees depend on the underlying
blockcipher being secure in the sense of a strong pseudorandom
permutation. Thus if OCB is used with a blockcipher that is not
secure as a strong pseudorandom permutation, the security guarantees
vanish. The need for the strong pseudorandom permutation property
means that OCB should be used with a conservatively designed, well-
trusted blockcipher, such as AES.
Both the confidentiality and the authenticity properties of OCB
degrade as per s^2 / 2^BLOCKLEN, where s is the total number of
blocks that the adversary acquires. The consequence of this formula
is that the proven security disappears when s becomes as large as
Krovetz Expires November 12, 2018 [Page 11]
Internet-Draft OCB for non-128-bit cipher blocks May 2018
2^(BLOCKLEN/2). Thus the user should never use a key to generate an
amount of ciphertext that is near to, or exceeds, 2^(BLOCKLEN/2)
blocks. In order to ensure that s^2 / 2^BLOCKLEN remains less than
about 1/2^32, a given key should be used to encrypt at most
2^(BLOCKLEN/2-16) blocks, including the associated data. To ensure
these limits are not crossed, automated key management is recommended
in systems exchanging large amounts of data [RFC4107].
When a ciphertext decrypts as INVALID it is the implementor's
responsibility to make sure that no information beyond this fact is
made adversarially available.
OCB encryption and decryption produce an internal BLOCKLEN-bit
authentication tag. The parameter TAGLEN determines how many bits of
this internal tag are included in ciphertexts and used for
authentication. The value of TAGLEN has two impacts: An adversary
can trivially forge with probability 2^{-TAGLEN}, and ciphertexts are
TAGLEN bits longer than their corresponding plaintexts. It is up to
the application designer to choose an appropriate value for TAGLEN.
Long tags cost no more computationally than short ones.
Normally, a given key should be used to create ciphertexts with a
single tag length, TAGLEN, and an application should reject any
ciphertext that claims authenticity under the same key but a
different tag length. While the ciphertext core and all of the bits
of the tag do depend on the tag length, this is done for added
robustness against misuse and should not suggest that receivers
accept ciphertexts employing variable tag lengths under a single key.
Timing attacks are not a part of the formal security model and an
implementation should take care to mitigate them in contexts where
this is a concern. To render timing attacks impotent, the amount of
time to encrypt or decrypt a string should be independent of the key
and the contents of the string. The only explicitly conditional OCB
operation that depends on private data is double(), which means that
using constant-time blockcipher and double() implementations
eliminates most (if not all) sources of timing attacks on OCB.
Power-usage attacks are likewise out of scope of the formal model,
and should be considered for environments where they are threatening.
The OCB encryption scheme reveals in the ciphertext the length of the
plaintext. Sometimes the length of the plaintext is a valuable piece
of information that should be hidden. For environments where
"traffic analysis" is a concern, techniques beyond OCB encryption
(typically involving padding) would be necessary.
Defining the ciphertext that results from OCB-ENCRYPT to be the pair
(C_1 || C_2 || ... || C_m || C_*, Tag[1..TAGLEN]) instead of the
Krovetz Expires November 12, 2018 [Page 12]
Internet-Draft OCB for non-128-bit cipher blocks May 2018
concatenation C_1 || C_2 || ... || C_m || C_* || Tag[1..TAGLEN]
introduces no security concerns. Because TAGLEN is fixed, both
versions allow ciphertexts to be parsed unambiguously.
5.1. Nonce Requirements
It is crucial that, as one encrypts, one does not repeat a nonce.
The inadvertent reuse of the same nonce by two invocations of the OCB
encryption operation, with the same key, but with distinct plaintext
values, undermines the confidentiality of the plaintexts protected in
those two invocations, and undermines all of the authenticity and
integrity protection provided by that key. For this reason, OCB
should only be used whenever nonce uniqueness can be provided with
certainty. Note that it is acceptable to input the same nonce value
multiple times to the decryption operation. We emphasize that the
security consequences are quite serious if an attacker observes two
ciphertexts that were created using the same nonce and key values,
unless the plaintext and AD values in both invocations of the encrypt
operation were identical. First, a loss of confidentiality ensues
because the attacker will be able to infer relationships between the
two plaintext values. Second, a loss of authenticity ensues because
the attacker will be able to recover secret information used to
provide authenticity, making subsequent forgeries trivial. Note that
there are AEAD schemes, particularly SIV [RFC5297], appropriate for
environments where nonces are unavailable or unreliable. OCB is not
such a scheme.
Nonces need not be secret, and a counter may be used for them. If
two parties send OCB-encrypted plaintexts to one another using the
same key, then the space of nonces used by the two parties must be
partitioned so that no nonce that could be used by one party to
encrypt could be used by the other to encrypt (eg, odd and even
counters).
6. IANA Considerations
The Internet Assigned Numbers Authority (IANA) has defined a registry
for Authenticated Encryption with Associated Data parameters. This
document does not specify any concrete AEAD schemes, so contributes
nothing to the registry. Any AEAD scheme based on this document,
where a permanently registered identifier would be useful, should
register such identifier with IANA [RFC5116].
7. Acknowledgements
During a short period of 2017 three people inquired about extending
OCB to blockciphers with blocklengths other than 128-bits. Thanks go
to Jeffrey Walton, Mark Wooding, and Uri Blumenthal for providing the
Krovetz Expires November 12, 2018 [Page 13]
Internet-Draft OCB for non-128-bit cipher blocks May 2018
motivation for this work. Mark Wooding has been especially helpful,
providing the basis for the code in Appendix B and corroborating test
vectors by writing an independent implementation.
8. References
8.1. Normative References
[Polys] Seroussi, G., "Table of low-weight binary irreducible
polynomials", Hewlett-Packard technical report HPL-98-135,
August 1998.
[RFC7523] Krovetz, T. and P. Rogaway, "The OCB authenticated-
encryption algorithm", RFC 7523, May 2014.
8.2. Informative References
[OCB] Krovetz, T. and P. Rogaway, "The software performance of
authenticated-encryption modes", in Fast Software
Encryption - FSE 2011, Springer, 2011.
[RC6] Rivest, R., Robshaw, M., Sidney, R., and Y. Yin, "The RC6
block cipher", Posted on RSA Data Security website August
20, 1998.
[RFCRC6] Krovetz, T., "RC6 and RC5 test vectors for multiple block
sizes", RFC XXXX, November 2018.
[RFC4107] Bellovin, S. and R. Housley, "Guidelines for cryptographic
key management", RFC 4107, June 2005.
[RFC5116] McGrew, D., "An interface and algorithms for authenticated
encryption", RFC 5116, January 2008.
[RFC5297] Harkins, D., "Synthetic Initialization Vector (SIV)
authenticated encryption using the Advanced Encryption
Standard (AES)", RFC 5297, October 2008.
[Sage] The Sage Developers, "SageMath, the Sage Mathematics
Software System (Version 7.6)", DOI 10.5281/zenodo.820864,
2017, <http://www.sagemath.org/>.
Appendix A. Sample Results
This section gives sample outputs for various inputs using OCB and
blockciphers with blocklengths other than 128. In each case, an
instance of RC6 is used for the blockcipher [RC6]. The name RC6-w/r/
Krovetz Expires November 12, 2018 [Page 14]
Internet-Draft OCB for non-128-bit cipher blocks May 2018
b refers to RC6 with a 4w-bit blocklength, r internal rounds, and a
b-byte key.
There are too many possible cases to consider for this section to be
exhaustive. Instead a small number of examples are shown in detail
with many significant variable assignments in the pseudocode shown.
This will help an implementor find most basic errors. Further
validation could then be accomplished by comparison with a reference
implementation over a much more thorough selection of inputs.
Each of the following entries indicates the blockcipher and tag
length used followed by the values K, N, A, P, C, indicating that
plaintext P with associated data A when encrypted using OCB with key
K, and nonce N, yields ciphertext C (which includes the tag). All
strings are represented in hexadecimal (eg, 0F represents the
bitstring 00001111). An empty entry indicates the empty string.
A.1. Example 1: 64-bit Blockcipher, 0-byte Input
K: 000102030405060708090A0B0C0D0E0F
N: 000102030405
A:
P:
C: 474D57A4043E
Assignments during HASH(K,A)
L_*: 39EF0C3FF4475894
L_$: 73DE187FE88EB128
Sum: 0000000000000000
Assignments during OCB-ENCRYPT
L_*: 39EF0C3FF4475894
L_$: 73DE187FE88EB128
Nonce: C001000102030405
bottom: 5
Ktop: 8298E905914FB488
Stretch: 8298E905914FB48889BA766C814FB488
Offset_0: 531D20B229F69111
Tag: 474D57A4043E7768
A.2. Example 2: 64-bit Blockcipher, 4-byte Input
Krovetz Expires November 12, 2018 [Page 15]
Internet-Draft OCB for non-128-bit cipher blocks May 2018
RC6-16/16/16 (64-bit blocks), 48-bit tags
K: 000102030405060708090A0B0C0D0E0F
N: 000102030405
A: 00010203
P: 00010203
C: B75BF470BB0B354C5B92
Assignments during HASH(K,A)
L_*: 39EF0C3FF4475894
L_$: 73DE187FE88EB128
Offset_*: 39EF0C3FF4475894
CipherInput: 39EE0E3C74475894
Sum: 48068A4FD12ABB4C
Assignments during OCB-ENCRYPT
L_*: 39EF0C3FF4475894
L_$: 73DE187FE88EB128
Nonce: C001000102030405
bottom: 5
Ktop: 8298E905914FB488
Stretch: 8298E905914FB48889BA766C814FB488
Offset_0: 531D20B229F69111
Offset_*: 6AF22C8DDDB1C985
Pad: B75AF6732D339D4B
PaddedP: 0001020380000000
Checksum_*: 0001020380000000
C_*: B75BF470
Tag: BB0B354C5B92CBAA
A.3. Example 3: 64-bit Blockcipher, 8-byte Input
Krovetz Expires November 12, 2018 [Page 16]
Internet-Draft OCB for non-128-bit cipher blocks May 2018
RC6-16/16/16 (64-bit blocks), 48-bit tags
K: 000102030405060708090A0B0C0D0E0F
N: 000102030405
A: 0001020304050607
P: 0001020304050607
C: 882A4FFE11B0E540D41F335172BD
Assignments during HASH(K,A)
L_*: 39EF0C3FF4475894
L_$: 73DE187FE88EB128
L_0: E7BC30FFD11D6250
Offset_1: E7BC30FFD11D6250
Sum_1: E3549C18B6F398EB
Sum: E3549C18B6F398EB
Assignments during OCB-ENCRYPT
L_*: 39EF0C3FF4475894
L_$: 73DE187FE88EB128
Nonce: C001000102030405
bottom: 5
Ktop: 8298E905914FB488
Stretch: 8298E905914FB48889BA766C814FB488
Offset_0: 531D20B229F69111
L_0: E7BC30FFD11D6250
Offset_1: B4A1104DF8EBF341
Checksum_1: 0001020304050607
C_1: 882A4FFE11B0E540
Tag: D41F335172BD43B7
A.4. Example 4: 64-bit Blockcipher, 20-byte Input
Krovetz Expires November 12, 2018 [Page 17]
Internet-Draft OCB for non-128-bit cipher blocks May 2018
RC6-16/16/16 (64-bit blocks), 48-bit tags
K: 000102030405060708090A0B0C0D0E0F
N: 000102030405
A: 000102030405060708090A0B0C0D0E0F10111213
P: 000102030405060708090A0B0C0D0E0F10111213
C: 882A4FFE11B0E540F218C902D76A601F90DF1E27BD403C47DF4E
Assignments during HASH(K,A)
L_*: 39EF0C3FF4475894
L_$: 73DE187FE88EB128
L_0: E7BC30FFD11D6250
Offset_1: E7BC30FFD11D6250
Sum_1: E3549C18B6F398EB
L_1: CF7861FFA23AC4BB
Offset_2: 28C451007327A6EB
Sum_2: FADB0507B1DA1433
Offset_*: 112B5D3F8760FE7F
CipherInput: 013A4F2C0760FE7F
Sum: D761B0AFAA584CF7
Assignments during OCB-ENCRYPT
L_*: 39EF0C3FF4475894
L_$: 73DE187FE88EB128
Nonce: C001000102030405
bottom: 5
Ktop: 8298E905914FB488
Stretch: 8298E905914FB48889BA766C814FB488
Offset_0: 531D20B229F69111
L_0: E7BC30FFD11D6250
Offset_1: B4A1104DF8EBF341
Checksum_1: 0001020304050607
C_1: 882A4FFE11B0E540
L_1: CF7861FFA23AC4BB
Offset_2: 7BD971B25AD137FA
Checksum_2: 0808080808080808
C_2: F218C902D76A601F
Offset_*: 42367D8DAE966F6E
Pad: 80CE0C34E04B0990
PaddedP: 1011121380000000
Checksum_*: 18191A1B88080808
C_*: 90DF1E27
Tag: BD403C47DF4ED926
Krovetz Expires November 12, 2018 [Page 18]
Internet-Draft OCB for non-128-bit cipher blocks May 2018
A.5. Example 5: 256-bit Blockcipher, 80-byte Input
RC6-64/16/16 (256-bit blocks), 256-bit tags
K: 000102030405060708090A0B0C0D0E0F
N: 000102030405060708090A0B
A: 000102030405060708090A0B0C0D0E0F
101112131415161718191A1B1C1D1E1F
202122232425262728292A2B2C2D2E2F
303132333435363738393A3B3C3D3E3F
404142434445464748494A4B4C4D4E4F
P: 000102030405060708090A0B0C0D0E0F
101112131415161718191A1B1C1D1E1F
202122232425262728292A2B2C2D2E2F
303132333435363738393A3B3C3D3E3F
404142434445464748494A4B4C4D4E4F
C: 5327CF07146F7B51A5D7AABA93D7F626
2F65ED3931815A5EF681217EBBF2BB13
F464772416E08D4BEAC37DFD8F614D98
AD7D58B1A63A24BB1CFE491D02AE28ED
BC6D07CF935C31FC81361EA46FBF568F
E4E72EE35BBD8FBBD04B2FCDB9656044
A9EFE1140327CEBB9A1750CDBD1BD3EC
Assignments during HASH(K,A)
L_*: 6E75A413F50216C512AD330BFABE641B
50E88C29BE5980AA2A09E43990125CBB
L_$: DCEB4827EA042D8A255A6617F57CC836
A1D118537CB301545413C8732024B976
L_0: B9D6904FD4085B144AB4CC2FEAF9906D
43A230A6F96602A8A82790E6404976C9
Offset_1: B9D6904FD4085B144AB4CC2FEAF9906D
43A230A6F96602A8A82790E6404976C9
Sum_1: B1836672FE03B925800743FF4DE116B3
C09C00B396CB20B058FAD1AEC4171F57
L_1: 73AD209FA810B6289569985FD5F320DA
8744614DF2CC0551504F21CC8092E9B7
Offset_2: CA7BB0D07C18ED3CDFDD54703F0AB0B7
C4E651EB0BAA07F9F868B12AC0DB9F7E
Sum_2: C16F97D1E09FA431655057CF582E8F32
FAE7971E00DB1EA56E7BA4AC493ECD8F
Offset_*: A40E14C3891AFBF9CD70677BC5B4D4AC
940EDDC2B5F38753D261551350C9C3C5
CipherInput: E44F5680CD5FBDBE85392D3089F99AE3
140EDDC2B5F38753D261551350C9C3C5
Sum: 964A5EA730124E1EA6CD7874A58F449C
5C3B2ED878115CC292A021FAF261B4FD
Krovetz Expires November 12, 2018 [Page 19]
Internet-Draft OCB for non-128-bit cipher blocks May 2018
Assignments during OCB-ENCRYPT
L_*: 6E75A413F50216C512AD330BFABE641B
50E88C29BE5980AA2A09E43990125CBB
L_$: DCEB4827EA042D8A255A6617F57CC836
A1D118537CB301545413C8732024B976
Nonce: 00000000000000000000000000000000
00000001000102030405060708090A0B
bottom: 11
Ktop: 67DB009692E6C7CCEFBFE4F9B810544E
DBD469326F0CBA90F94D02A6A85C7C9B
Stretch: 67DB009692E6C7CCEFBFE4F9B810544E
DBD469326F0CBA90F94D02A6A85C7C9B
A86D01BBB72B485530C02D0AC830FCD3
6C7CBB56B115CFB10BD707EBF8E485AD
Offset_0: D804B497363E677DFF27CDC082A276DE
A349937865D487CA68153542E3E4DD43
L_0: B9D6904FD4085B144AB4CC2FEAF9906D
43A230A6F96602A8A82790E6404976C9
Offset_1: 61D224D8E2363C69B59301EF685BE6B3
E0EBA3DE9CB28562C032A5A4A3ADAB8A
Checksum_1: 000102030405060708090A0B0C0D0E0F
101112131415161718191A1B1C1D1E1F
C_1: 5327CF07146F7B51A5D7AABA93D7F626
2F65ED3931815A5EF681217EBBF2BB13
L_1: 73AD209FA810B6289569985FD5F320DA
8744614DF2CC0551504F21CC8092E9B7
Offset_2: 127F04474A268A4120FA99B0BDA8C669
67AFC2936E7E8033907D8468233F423D
Checksum_2: 20202020202020202020202020202020
20202020202020202020202020202020
C_2: F464772416E08D4BEAC37DFD8F614D98
AD7D58B1A63A24BB1CFE491D02AE28ED
Offset_*: 7C0AA054BF249C843257AABB4716A272
37474EBAD0270099BA746051B32D1E86
Pad: FC2C458CD71977BBC97F54EF23F218C0
7C6AD1938FDE8374AF27960469595171
PaddedP: 404142434445464748494A4B4C4D4E4F
80000000000000000000000000000000
Checksum_*: 606162636465666768696A6B6C6D6E6F
A0202020202020202020202020202020
C_*: BC6D07CF935C31FC81361EA46FBF568F
Tag: E4E72EE35BBD8FBBD04B2FCDB9656044
A9EFE1140327CEBB9A1750CDBD1BD3EC
Krovetz Expires November 12, 2018 [Page 20]
Internet-Draft OCB for non-128-bit cipher blocks May 2018
A.6. Example 6: Extended Tests
The following VALIDATE[B] algorithm tests a wider variety of inputs.
Parameter B indicates that throughout the validation RC6-(B/4)/16/16
(ie, RC6 with B-bit blocklength, 16 rounds, and 16-byte keys) is the
blockcipher used. Please note that when B is not a power of two,
then the non-standard version of RC6 documented in [RFCRC6] is used.
In all cases TAGLEN is min(B, 256).
Function name:
VALIDATE[B]
Output:
Y, string of length min(B, 256) bits
Y is defined as follows.
K = 000102030405060708090A0B0C0D0E0F
C = <empty string>
for i = 0 to 127 do
S = (0x00 || 0x01 || 0x02 || ...)[1..8i]
N = num2str(3i+1,16)
C = C || OCB-ENCRYPT(K,N,S,S)
N = num2str(3i+2,16)
C = C || OCB-ENCRYPT(K,N,<empty string>,S)
N = num2str(3i+3,16)
C = C || OCB-ENCRYPT(K,N,S,<empty string>)
end for
N = num2str(385,16)
Y = OCB-ENCRYPT(K,N,C,<empty string>)
Iteration i of the loop adds 2i + (3 * TAGLEN / 8) bytes to C,
resulting in an ultimate length for C of 16256 + 48 * TAGLEN bytes.
The final OCB-ENCRYPT has an empty plaintext component, so serves
only to authenticate C. The output values should be:
Krovetz Expires November 12, 2018 [Page 21]
Internet-Draft OCB for non-128-bit cipher blocks May 2018
VALIDATE[32] == 5A126BD4
VALIDATE[64] == 21CE70BE54BDD72D
VALIDATE[96] == 1014F0D84D8060DC47752BAA
VALIDATE[128] == 7F9A12DE01C2C3150EBB2593D6531EA4
VALIDATE[192] == 9A078741E919C04D27D788225F4EDC99
EB0864E3AA36C194
VALIDATE[256] == 4D40016D7A255F603110AF8157863D4C
C392A2A2026C3CADF275583659389A84
VALIDATE[384] == 64973A1E77815999A50E9B2A0BAFE802
F00F821D5B34E1F63E0D4DF6BA50F600
VALIDATE[512] == 2CE8DA2D843D7373FA138C663305EC25
88FBCCE30DE426E99644E777F3FBCFD5
VALIDATE[768] == 37848B8A255C73CE0EE3BE5C8277340C
BE64B54178B8731E052ECEC6BE9E5A07
VALIDATE[1024] == 439667F8BFFFC9D4C16E5CB3DE921F7D
AD0B76463AB56321EDB68F2D1D2AEEC0
VALIDATE[1600] == 794CCD79BC11854275C924DF56CB82F2
C443631EF9F9F90251DC6DDC2CCF7F08
Appendix B. Generating RESIDUE, SHIFT, MASKLEN, TAGREP Constants
OCB, as defined in [RFC7523] and [OCB], uses several "magic numbers"
when manipulating 128-bit blocks (135, 8, 6 and 7 for RESIDUE, SHIFT,
MASKLEN and TAGREP). These constants are carefully chosen and depend
on BLOCKLEN. A table in Section 3.1 gives values for other assorted
blocklengths and this section describes how to produce the values for
more blocklengths if needed.
Finding MASKLEN and SHIFT for a particular BLOCKLEN begins by
following the process described in Section 4.1 of [OCB]. The result
of that process is the domain size for every possible shift, 1
through BLOCKLEN-1, in the stretch-then-shift hash used internally by
OCB. With that information, MASKLEN and SHIFT are determined as
follows. Define MASKLEN as the floor of the base-2 logarithm of the
largest domain size found. Keep as SHIFT candidates all shifts with
domain sizes of at least 2^MASKLEN. These all provide equal
security, but we want a shift that allows efficient implementation
too. A shift equal to a large power-of-two would be ideal, but not
all BLOCKLEN values produce candidate shifts with that property. Of
all the shifts with domains of at least 2^MASKLEN, we continue to
keep as candidates those shift values that are minimal modulo 8 (if
this minima is equal to zero, then shifts can be performed using byte
manipulations). Finally, we prefer shifts that are close to a large
power-of-two, so of the remaining candidates, we choose for SHIFT one
whose value modulo 8 and modulo 2^k is equal for the largest k, and
if more than one has this property we settle on the smallest of those
that do. The Sage script at the end of this section makes explicit
this process and was run using SageMath 7.6 to generate all of the
Krovetz Expires November 12, 2018 [Page 22]
Internet-Draft OCB for non-128-bit cipher blocks May 2018
MASKLEN and SHIFT values given in Section 3.1 [Sage]. Its list of
blocklengths can be edited and the script rerun to determine other
MASKLEN and SHIFT values.
For the other two constants, TAGREP is defined as min(8, t) where t
is the smallest integer making 2^t >= BLOCKLEN, and RESIDUE is
extracted from [Polys]. To determine a RESIDUE for BLOCKLEN, find
the entry whose largest number is BLOCKLEN and let S be the set of
numbers other than BLOCKLEN in this entry. Then, RESIDUE = 1 +
sum({2^x | x in S}). For example, when BLOCKLEN is 122 we find the
entry "122,6,2,1" making S == {6,2,1}. In this case RESIDUE == 1 +
2^6 + 2^2 + 2^1 == 71.
B.1. Sage Script For Generating MASKLEN and SHIFT
Krovetz Expires November 12, 2018 [Page 23]
Internet-Draft OCB for non-128-bit cipher blocks May 2018
<CODE BEGINS>
# w will iterate over these blocklengths. Edit list as you wish.
for w in [32, 64, 96, 128, 192, 256, 384, 512, 768, 1024, 1600]:
domsize = [0] # domsize[i] will contain domain size of shift i
# Find domain size for each possible shift c in 1..w-1
for c in range(1, w):
# Build A matrix as specified in Section 4.1 of [OCB]
I_rows = [[j == i for j in range(w)] for i in range(w)]
J_rows = [[j == i or j == i + c for j in range(w)]
for i in range(w)]
IJ = matrix(GF(2), I_rows + J_rows)
A = [IJ[i:i + w, 0:w] for i in range(w)]
# Find number of qualifying sub-matrices (ie, domain size)
i = 0 # increase i until not full-rank
dom = w # Set dom=i ends loop & sets dom to domain size
while i < dom:
if A[i].rank() < w: dom=i
j = 0
while j < i and i < dom:
if (A[i] + A[j]).rank() < w: dom=i
j = j + 1
i = i + 1
domsize.append(dom) # set domsize[c] = dom
# Generate shifts that are secure, in preference order
domain_bits = floor(log(max(domsize), 2))
candidates = (k for i in range(8)
for j in range(floor(log(w, 2)),2,-1)
for k in range(i,w,2**j)
if domsize[k] >= 2**domain_bits)
# Print the first one found, or -1 if none
print("block bits: %d, mask bits: %d, shift bits: %d" %
(w, domain_bits, next(candidates,-1)))
<CODE ENDS>
Author's Address
Krovetz Expires November 12, 2018 [Page 24]
Internet-Draft OCB for non-128-bit cipher blocks May 2018
Ted Krovetz
Computer Science Department
California State University
6000 J Street
Sacramento, CA 95819-6021
USA
Email: ted@krovetz.net
Krovetz Expires November 12, 2018 [Page 25]
