Crypto Forum Research Group A. Cope Internet-Draft Google Intended status: Informational December 21, 2016 Expires: June 24, 2017 Hash-Encrypt-Hash, a block cipher mode of operation draft-cope-heh-01 Abstract This memo describes a block cipher mode of operation known as Hash- Encrypt-Hash (HEH). 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 http://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 June 24, 2017. Copyright Notice Copyright (c) 2016 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 (http://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 the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Cope Expires June 24, 2017 [Page 1] Internet-Draft HEH December 2016 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1. Requirements Language . . . . . . . . . . . . . . . . . . 3 2. Notation . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3.1. Key size . . . . . . . . . . . . . . . . . . . . . . . . 4 3.2. Block cipher . . . . . . . . . . . . . . . . . . . . . . 4 3.3. Nonce and AAD . . . . . . . . . . . . . . . . . . . . . . 4 4. GF(2^128) math . . . . . . . . . . . . . . . . . . . . . . . 4 4.1. GF(2^128) . . . . . . . . . . . . . . . . . . . . . . . . 4 4.2. Multiplication in GF(2^128) . . . . . . . . . . . . . . . 4 4.3. Addition in GF(2^128) . . . . . . . . . . . . . . . . . . 5 5. Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 5 5.1. generate_keys . . . . . . . . . . . . . . . . . . . . . . 5 5.2. generate_betas . . . . . . . . . . . . . . . . . . . . . 6 5.3. poly_hash . . . . . . . . . . . . . . . . . . . . . . . . 6 5.4. HEH_hash . . . . . . . . . . . . . . . . . . . . . . . . 7 5.5. HEH_hash_inv . . . . . . . . . . . . . . . . . . . . . . 8 5.6. CTS_2ECB_encrypt . . . . . . . . . . . . . . . . . . . . 9 5.7. CTS_2ECB_decrypt . . . . . . . . . . . . . . . . . . . . 9 5.8. HEH_encrypt . . . . . . . . . . . . . . . . . . . . . . . 10 5.9. HEH_decrypt . . . . . . . . . . . . . . . . . . . . . . . 10 6. HEH as an AEAD . . . . . . . . . . . . . . . . . . . . . . . 10 6.1. HEH_AEAD_encrypt . . . . . . . . . . . . . . . . . . . . 10 6.2. HEH_AEAD_decrypt . . . . . . . . . . . . . . . . . . . . 11 7. Security considerations . . . . . . . . . . . . . . . . . . . 11 7.1. Security implementations of nonce use . . . . . . . . . . 11 7.2. Authentication . . . . . . . . . . . . . . . . . . . . . 12 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 12 8.1. Normative References . . . . . . . . . . . . . . . . . . 12 8.2. Informative References . . . . . . . . . . . . . . . . . 12 Appendix A. Test Vectors . . . . . . . . . . . . . . . . . . . . 12 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 15 1. Introduction This memo describes the implementation of the Hash Encrypt Hash (HEH) block cipher mode of operation as both an encryption algorithm and an AEAD. The primary benefit of HEH is that it extends the strong pseudorandom permutation property of block ciphers to arbitrary- length messages. This means that if any bit of the plaintext is flipped, each bit in the ciphertext will flip with 50% probability. No block cipher mode of operation that is currently in widespread use has this property. Additionally, HEH is more resistant to misuse than commonly-used block cipher modes of operation. For example, if nonces are reused, CTR fails catastrophically, and CBC will leak Cope Expires June 24, 2017 [Page 2] Internet-Draft HEH December 2016 common prefixes of the underlying block size. HEH has neither of those problems. 1.1. Requirements Language The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC2119]. 2. Notation ecb_key - key for the underlying ecb block cipher calls, generated by generate_keys. block - 16 bytes. buffer[i] - block i of buffer. Defined for 0 <= i < N. buffer[N+] - bytes 16 * N until the end of buffer. The unpadded partial block. EMPTY - buffer of length 0. GF(2^128) - The Galois field of 2^128 elements, as defined in section 4.1. msg - shorthand for message, a buffer that is an input to a function. N - FLOOR(msg_length / 16), number of full blocks of msg. out_msg - buffer that is a transformation of msg. out_msg_length = msg_length unless otherwise explicitly specified. prf_key - pseudo-random function key. The key passed as input to HEH. tau_key - 16 byte key used to compute the hash, generated by generate_keys. XOR - bitwise exclusive-or. XXXX_length - length of XXXX in bytes. * - Multiplication in GF(2^128) as defined in section 4.2. + - Addition in GF(2^128) as defined in section 4.3. Cope Expires June 24, 2017 [Page 3] Internet-Draft HEH December 2016 0^i - buffer of i zero bytes. || - concatenation. 3. Overview 3.1. Key size The HEH key is a single key of the same length as the underlying block cipher key. HEH uses CMAC to derive subkeys from the HEH key. 3.2. Block cipher HEH MUST use a block cipher with a block size of 128-bits. 3.3. Nonce and AAD HEH SHOULD support a 16-byte nonce. Support for other nonce lengths between 0 and 2^32-1 (inclusive) bytes is OPTIONAL. Support for additional authenticated data (AAD) and support for varying AAD lengths between 0 and 2^32-1 (inclusive) bytes is OPTIONAL. Security implications are discussed in section 7.1 4. GF(2^128) math 4.1. GF(2^128) GF(2^128) is the Galois field of 2^128 elements defined by the irreducible polynomial x^128 + x^7 + x^2 + x + 1. Elements in the field are converted to and from 128-bit strings by taking the least-significant bit of the first byte to be the coefficient of x^0, the most-significant bit of the first byte to the the coefficient of x^7, and so on, until the most-significant bit of the last byte is the coefficient of x^127 [AES-GCM-SIV]. Examples: 10000111 || 0^15 = x^7 + x^2 + x + 1 0^15 || 00000001 = x^120. 0^15 || 10000000 = x^127. 4.2. Multiplication in GF(2^128) Input Two 128-bit elements X, Y Output 128-bit element X * Y Cope Expires June 24, 2017 [Page 4] Internet-Draft HEH December 2016 Multiplication is defined on 128-bit blocks by converting them to polynomials as described above, and then computing the resulting product modulo x^128 + x^7 + x^2 + x + 1. 4.3. Addition in GF(2^128) Input Two 128-bit elements X, Y Output 128-bit element X + Y For any two 128-bit elements X, Y in the Galois field, X + Y is defined as X XOR Y. The operations + and XOR are interchangeable within this document. For consistency we use + on 128-bit strings and XOR if the arguments are not 128-bits long. 5. Algorithm When appropriate, we will explain the output as both a mathematical formula and in pseudo-code. This information is redundant, and it exists to provide additional clarity. Implementations need not implement the exact algorithm specified by the pseudocode, so long as the output matches what the pseudocode would produce. 5.1. generate_keys ecb_key and tau_key are generated from prf_key by taking the CMAC as defined in [CMAC] of fixed one-block messages. The input to the CMAC used to generate ecb and tau key will never collide with the input used to generate any beta_key, because when generating a beta_key, the last 4 bytes of the input are always zero. Input msg, prf_key Output tau_key = CMAC(key = prf_key, message = 0x00...01) ecb_key = CMAC(key = prf_key, message = 0x00...02) || CMAC(key = prf_key, message = 0x00...03) truncated to perf_key_length bytes Cope Expires June 24, 2017 [Page 5] Internet-Draft HEH December 2016 5.2. generate_betas To generate the beta_keys needed by HEH_hash, we take the CMAC as defined in [CMAC] of the nonce, AAD, nonce_length, AAD_length and plaintext_length. We use CMAC because it is a pseudorandom function on variable length inputs. Input prf_key, nonce, AAD, plaintext_length Output beta1_key = CMAC(key = prf_key, message = pad_16(nonce) || pad_16(AAD) || pad_16(nonce_length | | AAD_length || plaintext_length)) beta2_key = x * beta1_key return beta1_key, beta2_key Where pad_16(X) = X right-padded with 0s up to a multiple of 16 bytes. If X is already a multiple of 16 bytes (including if X is 0 bytes), this is a no-op. The following MUST be true in order to generate conformant ciphertext: o nonce_length, AAD_length, and plaintext_length MUST be 4 bytes long. o nonce_length, AAD_length, and plaintext_length MUST be stored in little-endian format. o The input to CMAC MUST be right-padded with 0x00 bytes up to a multiple of 16 bytes. o CMAC MUST use the same block cipher that is used in CTS_2ECB_encrypt. o CMAC MUST be implemented as described in [CMAC]. In particular, if CMAC is being reimplemented for HEH, be advised that there is a multiply-by-x substep of CMAC that uses a different finite field representation than the one described in section 4. 5.3. poly_hash Poly_hash treats each block of msg as a coefficient to a polynomial in GF(2^128), and evaluates that polynomial at tau_key to create a hash. Poly_hash is called as a subroutine of HEH_hash so that any minor change to msg will result in every block being changed in HEH_hash with high probability. Note that the coefficients of Cope Expires June 24, 2017 [Page 6] Internet-Draft HEH December 2016 m_{N-1} and m_N are flipped if there is a partial block. This is done to simplify the implementation of HEH_hash_inv. Input msg, tau_key Output if (no partial block) k^{N-1} * m_0 + ... + k * m_{N-2} + m_{N-1} else if (partial block) k^N * m_0 + ... + k^2 * m_{N-2} + k * m_N + m_{N-1} Where k = tau_key, m_i = msg[i], for i = 0 to N-1, m_N = msg[N+] right padded up to 16 bytes with a 0x00 bytes. Undefined when msg_length is a multiple of 16 pseudo-code: p = 0^16 For i = 0 to N - 2 p *= tau_key p += msg[i] if msg_length % 16 != 0 p *= tau_key p += m_N // as defined above p *= tau_key p += msg[N-1] return p 5.4. HEH_hash HEH_hash is the hash step in Hash-Encrypt-Hash. It is an invertible hash function used to ensure any change to msg will result in every full block being modified with high probability. Cope Expires June 24, 2017 [Page 7] Internet-Draft HEH December 2016 Input msg, beta_key, tau_key Output out_msg = (m_0 + R, ..., m_{N-2} + R, R, m_N) + (xb, x^2b, ..., x^{N-1}b, b, 0) where m_i = msg[i] for i = 0 to N-1, m_N = msg[N+], R = out_msg of poly_hash, b = beta_key, x is the element x in GF(2^128). pseudo-code: R = poly_hash(msg, tau_key) e = beta_key * x For i = 0 to N-2 out_msg[i] = msg[i] + R + e e = e * x out_msg[N-1] = R + beta_key out_msg[N+] = msg[N+] return out_msg 5.5. HEH_hash_inv Inverse of HEH_hash Input msg, beta_key, tau_key Output out_msg pseudo-code R = msg[N-1] + beta_key e = beta_key * x For i = 0 to N-2 out_msg[i] = msg[i] + R + e e = e * x out_msg[N+] = msg[N+] out_msg[N-1] = 0^16 // now all blocks in out_msg are correct except for // out_msg[N-1], which is all zeroes R_without_constant_term = poly_hash(out_msg, tau_key) out_msg[N-1] = R + R_without_constant_term return out_msg Cope Expires June 24, 2017 [Page 8] Internet-Draft HEH December 2016 5.6. CTS_2ECB_encrypt The encryption step of Hash-Encrypt-Hash. CTS_2ECB_encrypt uses a modification of CTS-ECB. Because HEH_hash is the identity function on partial blocks, we encrypt the partial block by xoring it with a pad created by encrypting the last full block of plaintext XOR the last full block ciphertext Input msg, ecb_key Output out_msg pseudo-code For i = 0 to N-1 out_msg[i] = block_cipher_encrypt(ecb_key, msg[i]) if msg_length % 16 != 0 partial_block_pad = block_cipher_encrypt(ecb_key, out_msg[N-1] XOR msg[N-1]) // XOR the partial block with the first k bytes of // partial_block_pad, where k is the number of bytes // in the partial block out_msg[N+] = msg[N+] XOR partial_block_pad return out_msg 5.7. CTS_2ECB_decrypt Inverse of CTS_2ECB_encrypt. CTS_2ECB_decrypt is identical to CTS_2ECB_encrypt except the initial block_cipher_encrypt calls are now block_cipher_decrypt calls Input msg, ecb_key Output out_msg pseudo-code For i = 0 to N-1 out_msg[i] = block_cipher_decrypt(ecb_key, msg[i]) if msg_length % 16 != 0 partial_block_pad = block_cipher_encrypt(ecb_key, out_msg[N-1] XOR msg[N-1]) // XOR the partial block with the first k bytes of // partial_block_pad, where k is the number of bytes // in the partial block out_msg[N+] = msg[N+] XOR partial_block_pad return out_msg Cope Expires June 24, 2017 [Page 9] Internet-Draft HEH December 2016 5.8. HEH_encrypt Core encryption function of HEH. Input prf_key, ecb_key, tau_key, nonce, AAD, msg Output out_msg pseudo-code beta1_key, beta2_key = generate_betas(prf_key, nonce, AAD, msg_length) out_msg = HEH_hash(msg, beta1_key, tau_key) out_msg = CTS_2ECB_encrypt(out_msg, ecb_key) out_msg = HEH_hash_inv(out_msg, beta2_key, tau_key) return out_msg 5.9. HEH_decrypt Core decryption function of HEH. Input prf_key, ecb_key, tau_key, nonce, AAD, msg Output out_msg pseudo-code beta1_key, beta2_key = generate_betas(prf_key, nonce, AAD, msg_length) out_msg = HEH_hash(msg, beta2_key, tau_key) out_msg = CTS_2ECB_decrypt(out_msg, ecb_key) out_msg = HEH_hash_inv(out_msg, beta1_key, tau_key) return out_msg 6. HEH as an AEAD Because HEH is a strong pseudorandom permutation, it can also provide authentication with minimal modification. Support for authentication is OPTIONAL. To provide authentication, append 16 zero bytes to the end of the plaintext, then encrypt. When decrypting, we can determine authenticity of the message by verifying that the final 16 bytes of the plaintext are the expected zero bytes. 6.1. HEH_AEAD_encrypt The authenticated encryption function of HEH. HEH_AEAD_encrypt returns ciphertext which is 16 bytes longer than plaintext msg. Cope Expires June 24, 2017 [Page 10] Internet-Draft HEH December 2016 Input prf_key, ecb_key, tau_key, nonce, AAD, msg Output padded_out_msg pseudo-code // append a full block of zeroes padded_msg = msg || 0^16 return HEH_encrypt(prf_key, ecb_key, tau_key, nonce, AAD, padded_msg) 6.2. HEH_AEAD_decrypt The authenticated decryption function of HEH. HEH_AEAD_decrypt returns either plaintext which is 16 bytes shorter than msg or indication of inauthenticity FAIL. Input prf_key, ecb_key, tau_key, nonce, AAD, msg, Output unpadded_out_msg or FAIL pseudo-code out_msg = HEH_DECRYPT(prf_key, ecb_key, tau_key, nonce, AAD, msg) // If final block is not all zeros, FAIL if out_msg[(out_msg_length - 16):out_msg_length] != 0^16 return FAIL // Drop the zero-block that was added in HEH_AEAD_encrypt unpadded_out_msg = out_msg[0:(out_msg_length - 16)] return unpadded_out_msg 7. Security considerations The minimum length of the plaintext for HEH is 16 bytes. The maximum length is 2^32 - 1 bytes. When using HEH as an AEAD, this minimum and maximum apply to padded_msg. 7.1. Security implementations of nonce use If no nonce is used (or, equivalently, if a 'nonce' is re-used for multiple messages) then HEH is a strong pseudorandom permutation. Of course, if the same plaintext, nonce, and key are used together more than once, the ciphertext will collide. Cope Expires June 24, 2017 [Page 11] Internet-Draft HEH December 2016 If a unique nonce is used for each plaintext and key combination, then HEH is semantically secure. We make no claim that using randomly-generated nonces or using longer nonces generates additional security. 7.2. Authentication As HEH is a strong pseudorandom permutation, [AUTH] shows that authentication can be provided by appending a known authentication code to the plaintext and then encrypting. 8. References 8.1. Normative References [CMAC] National Institute of Standards and Technology, "NIST Special Publication 800-38B", 2005. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, . 8.2. Informative References [AES-GCM-SIV] Gueron, S., Langley, A., and Y. Lindell, "AES-GCM-SIV: Nonce Misuse-Resistant Authenticated Encryption. draft- gueron-gcmsiv-03", 2016. [AUTH] Bellare, M. and P. Rogaway, "Encode-then-encipher encryption: How to exploit nonces or redundancy in plaintexts for efficient cryptography", 2000. [HEH] Sarkar, P., "Efficient Tweakable Enciphering Schemes from (Block-Wise) Universal Hash Functions", 2008. [NIST.500-20.1977] National Institute of Standards and Technology, "Validating the Correctness of Hardware Implementations of the NBS Data Encryption Standard", NIST 500-20, November 1977. Appendix A. Test Vectors AES-128 was used as the block cipher for all of the test vectors. Cope Expires June 24, 2017 [Page 12] Internet-Draft HEH December 2016 key = 00000000000000000000000000000000 nonce = EMPTY AAD = EMPTY plaintext = 00000000000000000000000000000000 ciphertext = a1726260d1450ae4aba906e79e584e07 key = 000102030405060708090A0B0C0D0E0F nonce = EMPTY AAD = EMPTY plaintext = 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 000000000000000000000000000000 ciphertext = f5eec4375cefa15fc3eff7a271779231 ce03afa9eeacf9ad060a62602e6dc202 3598944729eb848d13f9b7d362e6d5f6 4e648e38553415f44ff37752954da7 key = 000102030405060708090A0B0C0D0E0F nonce = EMPTY AAD = EMPTY plaintext = 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000001 000000000000000000000000000000 ciphertext = 4efc731cacbbaa2713a051e663ddaeb0 4c1b25a3ee7aa4c125c9547154c74923 90b5f7fac503f527b8cdffe21bb96201 b0dc409fed9e9123379e5a6f101bd2 key = 000102030405060708090A0B0C0D0E0F nonce = 00000000000000000000000000000000 AAD = EMPTY plaintext = 000102030405060708090A0B0C0D0E0F ciphertext = d8bd40bfcae5ee810f3d1f1fae890755 key = a8da249b5efa13c2c194bf32ba38a377 nonce = 4d4761372b4786f0d647b5c2e8cf8527 AAD = EMPTY plaintext = b8ee29e4a5d1e755d0fde722637636e2 f80cf8fe6576e7cac142f5ca5aa8ac2a ciphertext = 59f2784e1094f95c2223782a30481197 b1fe70c4efdf04ef163904cfc0959a98 Cope Expires June 24, 2017 [Page 13] Internet-Draft HEH December 2016 key = 000102030405060708090A0B0C0D0E0F nonce = 00000000000000000000000000000000 AAD = EMPTY plaintext = 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000000 000000000000000000000000000000 ciphertext = e040ebe952be6560e46868a37375b852 ef386a872525f604e58ebe148b02141f a973b7ad15be9ca0d28a2cdcd4e30555 0af5f851eee562a571a77c155d7a9e key = 000102030405060708090A0B0C0D0E0F nonce = 00000000000000000000000000000000 AAD = EMPTY plaintext = 00000000000000000000000000000000 00000000000000000000000000000000 00000000000000000000000000000001 000000000000000000000000000000 ciphertext = 4b1a15a0af086d70f0a797b5314b8cc3 4df27a9dddd4159957adc6b13569f56a 2d70e49749b29f71de22b5708c6924d3 ad80584890e4edba763d717c572587 key = 000102030405060708090A0B0C0D0E0F nonce = 000102030405060708090A0B0C0D0E0F AAD = 000102030405060708090A0B0C0D0E0F plaintext = 00000000000000000000000000000000 00000000000000000000000000000000 ciphertext = 16c3f198c970dd0db9b25beedbacb615 b2ee9c51ece5d2426b9f5420be8b1b19 key = 000102030405060708090A0B0C0D0E0F nonce = 000102030405060708090A0B0C0D0E0F 000102030405 AAD = 0102030405060708090A0B0C0D0E0F00 010203 plaintext = 00000000000000000000000000000000 00000000000000000000000000000000 ciphertext = 2aa635491098bc45b711a5d950cc4988 1d110f20056c9d220d125fabfd7ab941 Cope Expires June 24, 2017 [Page 14] Internet-Draft HEH December 2016 key = 36DAF975AAE45061AF88079422E5E6A9 nonce = 4164A1FFAEEF4B23324C47279AFB02E8 AAD = 948F6D03EA0BDE71A0233AC87753F10E plaintext = 6A2EDA8E07C10918507F0B5E4F32053C 335D179A8F476ED1D08A458C00726F63 6365BF26A7003F43C0270BBB44EC780E 6119FA19AA99F0265850BD29C49E2436 A9 ciphertext = d3312031380deb46e7f56220c934a759 55a95fc750f3e535ada7d371ad60b3a7 c6406389a62b1e66be371baa8adba267 225d522936c3829c035ab109526d296f 12 key = 880D8B115BA55842FF4505C5E45F78F6 nonce = 131D6E569B5CCB6E563D2CED8616E6AC AAD = 01BD52F7065A35A07EE70D9A881EDDB4 plaintext = 00000000000000000000000000000000 B1E0CC8A07264432823C68B2EF59E592 D271271029F6364CEEE577D9FDA8E5C4 131D6E569B5CCB6E563D2CED8616E6AC C6 ciphertext = 395f5d80788231bd0cc055ef1fd83941 7501a2b4d9c42952ffcbd98be6393305 41968ef42d589e5eb807054af2557905 12bb5dda5be418335ae9b7e9d18c8ce8 f7 key = 880D8B115BA55842FF4505C5E45F78F6 nonce = 131D6E569B5CCB6E563D2CED8616E6AC AAD = 01BD52F7065A35A07EE70D9A881EDDB4 plaintext = 01000000000000000000000000000000 B1E0CC8A07264432823C68B2EF59E592 D271271029F6364CEEE577D9FDA8E5C4 131D6E569B5CCB6E563D2CED8616E6AC C6 ciphertext = e6807e6ba3f4fba237c996f91bf6beba bf243915da3e8ab4c73c5ed9c0a8136b 00dc6d7b4994b7c8551b5bf1a042c2f2 2da1129fcbe45e310f880552a27b3f5b 84 Author's Address Cope Expires June 24, 2017 [Page 15] Internet-Draft HEH December 2016 Alex Cope Google 747 6th St S Kirkland, WA 98033 USA Email: alexcope@google.com Cope Expires June 24, 2017 [Page 16]