1 | XOF Design
|
---|
2 | ==========
|
---|
3 |
|
---|
4 | XOF Definition
|
---|
5 | --------------
|
---|
6 |
|
---|
7 | An extendable output function (XOF) is defined as a variable-length hash
|
---|
8 | function on a message in which the output can be extended to any desired length.
|
---|
9 |
|
---|
10 | At a minimum an XOF needs to support the following pseudo-code
|
---|
11 |
|
---|
12 | ```text
|
---|
13 | xof = xof.new();
|
---|
14 | xof.absorb(bytes1);
|
---|
15 | xof.absorb(bytes2);
|
---|
16 | xof.finalize();
|
---|
17 | out1 = xof.squeeze(10);
|
---|
18 | out2 = xof.squeeze(1000);
|
---|
19 | ```
|
---|
20 |
|
---|
21 | ### Rules
|
---|
22 |
|
---|
23 | - absorb can be called multiple times
|
---|
24 | - finalize ends the absorb process (by adding padding bytes and doing a final
|
---|
25 | absorb). absorb must not be called once the finalize is done unless a reset
|
---|
26 | happens.
|
---|
27 | - finalize may be done as part of the first squeeze operation
|
---|
28 | - squeeze can be called multiple times.
|
---|
29 |
|
---|
30 | OpenSSL XOF Requirements
|
---|
31 | ------------------------
|
---|
32 |
|
---|
33 | The current OpenSSL implementation of XOF only supports a single call to squeeze.
|
---|
34 | The assumption exists in both the high level call to EVP_DigestFinalXOF() as
|
---|
35 | well as in the lower level SHA3_squeeze() operation (Of which there is a generic
|
---|
36 | c version, as well as assembler code for different platforms).
|
---|
37 |
|
---|
38 | A decision has to be made as to whether a new API is required, as well as
|
---|
39 | considering how the change may affect existing applications.
|
---|
40 | The changes introduced should have a minimal affect on other related functions
|
---|
41 | that share the same code (e.g SHAKE and SHA3 share functionality).
|
---|
42 | Older providers that have not been updated to support this change should produce
|
---|
43 | an error if a newer core is used that supports multiple squeeze operations.
|
---|
44 |
|
---|
45 | API Discussion of Squeeze
|
---|
46 | -------------------------
|
---|
47 |
|
---|
48 | ### Squeeze
|
---|
49 |
|
---|
50 | Currently EVP_DigestFinalXOF() uses a flag to check that it is only invoked once.
|
---|
51 | It returns an error if called more than once. When initially written it also did
|
---|
52 | a reset, but that code was removed as it was deemed to be incorrect.
|
---|
53 |
|
---|
54 | If we remove the flag check, then the core code will potentially call low level
|
---|
55 | squeeze code in a older provider that does not handle returning correct data for
|
---|
56 | multiple calls. To counter this the provider needs a mechanism to indicate that
|
---|
57 | multiple calls are allowed. This could just be a new gettable flag (having a
|
---|
58 | separate provider function should not be necessary).
|
---|
59 |
|
---|
60 | #### Proposal 1
|
---|
61 |
|
---|
62 | Change EVP_DigestFinalXOF(ctx, out, outlen) to handle multiple calls.
|
---|
63 | Possibly have EVP_DigestSqueeze() just as an alias method?
|
---|
64 | Changing the code at this level should be a simple matter of removing the
|
---|
65 | flag check.
|
---|
66 |
|
---|
67 | ##### Pros
|
---|
68 |
|
---|
69 | - New API is not required
|
---|
70 |
|
---|
71 | ##### Cons
|
---|
72 |
|
---|
73 | - Final seems like a strange name to call multiple times.
|
---|
74 |
|
---|
75 | #### Proposal 2 (Proposed Solution)
|
---|
76 |
|
---|
77 | Keep EVP_DigestFinalXOF() as a one shot function and create a new API to handle
|
---|
78 | the multi squeeze case e.g.
|
---|
79 |
|
---|
80 | ```text
|
---|
81 | EVP_DigestSqueeze(ctx, out, outlen).
|
---|
82 | ```
|
---|
83 |
|
---|
84 | ##### Pros
|
---|
85 |
|
---|
86 | - Seems like a better name.
|
---|
87 | - The existing function does not change, so it is not affected by logic that
|
---|
88 | needs to run for the multi squeeze case.
|
---|
89 | - The behaviour of the existing API is the same.
|
---|
90 | - At least one other toolkit uses this approach.
|
---|
91 |
|
---|
92 | ##### Cons
|
---|
93 |
|
---|
94 | - Adds an extra API.
|
---|
95 | - The interaction between the 2 API's needs to be clearly documented.
|
---|
96 | - A call to EVP_DigestSqueeze() after EVP_DigestFinalXOF() would fail since
|
---|
97 | EVP_DigestFinalXOF() indicates no more output can be retrieved.
|
---|
98 | - A call to EVP_DigestFinalXOF() after the EVP_DigestSqueeze() would fail.
|
---|
99 |
|
---|
100 | #### Proposal 3
|
---|
101 |
|
---|
102 | Create a completely new type e.g. EVP_XOF_MD to implement XOF digests
|
---|
103 |
|
---|
104 | ##### Pros
|
---|
105 |
|
---|
106 | - This would separate the XOF operations so that the interface consisted
|
---|
107 | mainly of Init, Absorb and Squeeze API's
|
---|
108 | - DigestXOF could then be deprecated.
|
---|
109 |
|
---|
110 | ##### Cons
|
---|
111 |
|
---|
112 | - XOF operations are required for Post Quantum signatures which currently use
|
---|
113 | an EVP_MD object. This would then complicate the Signature API also.
|
---|
114 | - Duplication of the EVP_MD code (although all legacy/engine code would be
|
---|
115 | removed).
|
---|
116 |
|
---|
117 | Choosing a name for the API that allows multiple output calls
|
---|
118 | -------------------------------------------------------------
|
---|
119 |
|
---|
120 | Currently OpenSSL only uses XOF's which use a sponge construction (which uses
|
---|
121 | the terms absorb and squeeze).
|
---|
122 | There will be other XOF's that do not use the sponge construction such as Blake2.
|
---|
123 |
|
---|
124 | The proposed API name to use is EVP_DigestSqueeze.
|
---|
125 | The alternate name suggested was EVP_DigestExtract.
|
---|
126 | The terms extract and expand are used by HKDF so I think this name would be
|
---|
127 | confusing.
|
---|
128 |
|
---|
129 | API Discussion of other XOF API'S
|
---|
130 | ---------------------------------
|
---|
131 |
|
---|
132 | ### Init
|
---|
133 |
|
---|
134 | The digest can be initialized as normal using:
|
---|
135 |
|
---|
136 | ```text
|
---|
137 | md = EVP_MD_fetch(libctx, "SHAKE256", propq);
|
---|
138 | ctx = EVP_MD_CTX_new();
|
---|
139 | EVP_DigestInit_ex2(ctx, md, NULL);
|
---|
140 | ```
|
---|
141 |
|
---|
142 | ### Absorb
|
---|
143 |
|
---|
144 | Absorb can be done by multiple calls to:
|
---|
145 |
|
---|
146 | ```text
|
---|
147 | EVP_DigestUpdate(ctx, in, inlen);
|
---|
148 | ```
|
---|
149 |
|
---|
150 | #### Proposal:
|
---|
151 |
|
---|
152 | Do we want to have an Alias function?
|
---|
153 |
|
---|
154 | ```text
|
---|
155 | EVP_DigestAbsorb(ctx, in, inlen);
|
---|
156 | ```
|
---|
157 |
|
---|
158 | (The consensus was that this is not required).
|
---|
159 |
|
---|
160 | ### Finalize
|
---|
161 |
|
---|
162 | The finalize is just done as part of the squeeze operation.
|
---|
163 |
|
---|
164 | ### Reset
|
---|
165 |
|
---|
166 | A reset can be done by calling:
|
---|
167 |
|
---|
168 | ```text
|
---|
169 | EVP_DigestInit_ex2(ctx, NULL, NULL);
|
---|
170 | ```
|
---|
171 |
|
---|
172 | ### State Copy
|
---|
173 |
|
---|
174 | The internal state can be copied by calling:
|
---|
175 |
|
---|
176 | ```text
|
---|
177 | EVP_MD_CTX_copy_ex(ctx, newctx);
|
---|
178 | ```
|
---|
179 |
|
---|
180 | Low Level squeeze changes
|
---|
181 | --------------------------
|
---|
182 |
|
---|
183 | ### Description
|
---|
184 |
|
---|
185 | The existing one shot squeeze method is:
|
---|
186 |
|
---|
187 | ```text
|
---|
188 | SHA3_squeeze(uint64_t A[5][5], unsigned char *out, size_t outlen, size_t r)
|
---|
189 | ```
|
---|
190 |
|
---|
191 | It contains an opaque object for storing the state B<A>, that can be used to
|
---|
192 | output to B<out>. After every B<r> bits, the state B<A> is updated internally
|
---|
193 | by calling KeccakF1600().
|
---|
194 |
|
---|
195 | Unless you are using a multiple of B<r> as the B<outlen>, the function has no
|
---|
196 | way of knowing where to start from if another call to SHA_squeeze() was
|
---|
197 | attempted. The method also avoids doing a final call to KeccakF1600() currently
|
---|
198 | since it was assumed that it was not required for a one shot operation.
|
---|
199 |
|
---|
200 | ### Solution 1
|
---|
201 |
|
---|
202 | Modify the SHA3_squeeze code to accept a input/output parameter to track the
|
---|
203 | position within the state B<A>.
|
---|
204 | See <https://github.com/openssl/openssl/pull/13470>
|
---|
205 |
|
---|
206 | #### Pros
|
---|
207 |
|
---|
208 | - Change in C code is minimal. it just needs to pass this additional parameter.
|
---|
209 | - There are no additional memory copies of buffered results.
|
---|
210 |
|
---|
211 | #### Cons
|
---|
212 |
|
---|
213 | - The logic in the c reference has many if clauses.
|
---|
214 | - This C code also needs to be written in assembler, the logic would also be
|
---|
215 | different in different assembler routines due to the internal format of the
|
---|
216 | state A being different.
|
---|
217 | - The general SHA3 case would be slower unless code was duplicated.
|
---|
218 |
|
---|
219 | ### Solution 2
|
---|
220 |
|
---|
221 | Leave SHA3_squeeze() as it is and buffer calls to the SHA3_squeeze() function
|
---|
222 | inside the final. See <https://github.com/openssl/openssl/pull/7921>
|
---|
223 |
|
---|
224 | #### Pros
|
---|
225 |
|
---|
226 | - Change is mainly in C code.
|
---|
227 |
|
---|
228 | #### Cons
|
---|
229 |
|
---|
230 | - Because of the one shot nature of the SHA3_squeeze() it still needs to call
|
---|
231 | the KeccakF1600() function directly.
|
---|
232 | - The Assembler function for KeccakF1600() needs to be exposed. This function
|
---|
233 | was not intended to be exposed since the internal format of the state B<A>
|
---|
234 | can be different on different platform architectures.
|
---|
235 | - When should this internal buffer state be cleared?
|
---|
236 |
|
---|
237 | ### Solution 3
|
---|
238 |
|
---|
239 | Perform a one-shot squeeze on the original absorbed data and throw away the
|
---|
240 | first part of the output buffer,
|
---|
241 |
|
---|
242 | #### Pros
|
---|
243 |
|
---|
244 | - Very simple.
|
---|
245 |
|
---|
246 | #### Cons
|
---|
247 |
|
---|
248 | - Incredibly slow.
|
---|
249 | - More of a hack than a real solution.
|
---|
250 |
|
---|
251 | ### Solution 4 (Proposed Solution)
|
---|
252 |
|
---|
253 | An alternative approach to solution 2 is to modify the SHA3_squeeze() slightly
|
---|
254 | so that it can pass in a boolean that handles the call to KeccakF1600()
|
---|
255 | correctly for multiple calls.
|
---|
256 |
|
---|
257 | #### Pros
|
---|
258 |
|
---|
259 | - C code is fairly simple to implement.
|
---|
260 | - The state data remains as an opaque blob.
|
---|
261 | - For larger values of outlen SHA3_squeeze() may use the out buffer directly.
|
---|
262 |
|
---|
263 | #### Cons
|
---|
264 |
|
---|
265 | - Requires small assembler change to pass the boolean and handle the call to
|
---|
266 | KeccakF1600().
|
---|
267 | - Uses memcpy to store partial results for a single blob of squeezed data of
|
---|
268 | size 'r' bytes.
|
---|