idnits 2.17.1
draft-atkins-openpgp-albegraic-eraser-00.txt:
Checking boilerplate required by RFC 5378 and the IETF Trust (see
https://trustee.ietf.org/license-info):
----------------------------------------------------------------------------
No issues found here.
Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt:
----------------------------------------------------------------------------
No issues found here.
Checking nits according to https://www.ietf.org/id-info/checklist :
----------------------------------------------------------------------------
No issues found here.
Miscellaneous warnings:
----------------------------------------------------------------------------
== The copyright year in the IETF Trust and authors Copyright Line does not
match the current year
-- The document date (September 09, 2014) is 3488 days in the past. Is
this intentional?
Checking references for intended status: Proposed Standard
----------------------------------------------------------------------------
(See RFCs 3967 and 4897 for information about using normative references
to lower-maturity documents in RFCs)
-- Possible downref: Non-RFC (?) normative reference: ref. 'AAGL'
** Obsolete normative reference: RFC 5226 (Obsoleted by RFC 8126)
== Outdated reference: A later version (-04) exists of
draft-atkins-openpgp-device-certificates-00
Summary: 1 error (**), 0 flaws (~~), 2 warnings (==), 2 comments (--).
Run idnits with the --verbose option for more detailed information about
the items above.
--------------------------------------------------------------------------------
2 Internet Engineering Task Force D. Atkins
3 Internet-Draft SecureRF Corporation
4 Intended status: Standards Track September 09, 2014
5 Expires: March 13, 2015
7 Using Algebraic Eraser in OpenPGP
8 draft-atkins-openpgp-albegraic-eraser-00
10 Abstract
12 The Algebraic Eraser(TM) is an encryption engine that supports, among
13 other configurations, a Diffie-Hellman-like key agreement protocol.
14 This draft specifies how to encode, store, share, and use Algebraic
15 Eraser Key Agreement Protocol keys in OpenPGP.
17 Status of This Memo
19 This Internet-Draft is submitted in full conformance with the
20 provisions of BCP 78 and BCP 79.
22 Internet-Drafts are working documents of the Internet Engineering
23 Task Force (IETF). Note that other groups may also distribute
24 working documents as Internet-Drafts. The list of current Internet-
25 Drafts is at http://datatracker.ietf.org/drafts/current/.
27 Internet-Drafts are draft documents valid for a maximum of six months
28 and may be updated, replaced, or obsoleted by other documents at any
29 time. It is inappropriate to use Internet-Drafts as reference
30 material or to cite them other than as "work in progress."
32 This Internet-Draft will expire on March 13, 2015.
34 Copyright Notice
36 Copyright (c) 2014 IETF Trust and the persons identified as the
37 document authors. All rights reserved.
39 This document is subject to BCP 78 and the IETF Trust's Legal
40 Provisions Relating to IETF Documents
41 (http://trustee.ietf.org/license-info) in effect on the date of
42 publication of this document. Please review these documents
43 carefully, as they describe your rights and restrictions with respect
44 to this document. Code Components extracted from this document must
45 include Simplified BSD License text as described in Section 4.e of
46 the Trust Legal Provisions and are provided without warranty as
47 described in the Simplified BSD License.
49 Table of Contents
51 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2
52 2. The Algebraic Eraser . . . . . . . . . . . . . . . . . . . . 3
53 2.1. E-Multiplication . . . . . . . . . . . . . . . . . . . . 3
54 2.2. AEKAP Keyset Parameters . . . . . . . . . . . . . . . . . 3
55 2.3. Generating Key Pairs . . . . . . . . . . . . . . . . . . 4
56 3. Encoding of Public and Private Keys . . . . . . . . . . . . . 4
57 3.1. Encoding Bit-Strings . . . . . . . . . . . . . . . . . . 5
58 3.1.1. Encoding Techniques . . . . . . . . . . . . . . . . . 5
59 3.1.2. Multi-Byte Entries . . . . . . . . . . . . . . . . . 6
60 3.2. Encoding Public Keys . . . . . . . . . . . . . . . . . . 6
61 3.3. Encoding Private Keys . . . . . . . . . . . . . . . . . . 7
62 4. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 7
63 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 7
64 6. Security Considerations . . . . . . . . . . . . . . . . . . . 7
65 7. References . . . . . . . . . . . . . . . . . . . . . . . . . 8
66 7.1. Normative References . . . . . . . . . . . . . . . . . . 8
67 7.2. Informative References . . . . . . . . . . . . . . . . . 8
68 Appendix A. Test Vectors . . . . . . . . . . . . . . . . . . . . 9
69 A.1. Sample key . . . . . . . . . . . . . . . . . . . . . . . 9
70 A.2. Sample key agreement . . . . . . . . . . . . . . . . . . 10
71 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 11
73 1. Introduction
75 The OpenPGP specification in [RFC4880] defines the use of RSA,
76 Elgamal, and DSA public key algorithms. [RFC6637] adds support for
77 Elliptic Curve Cryptography and specifies the ECDSA and ECDH
78 algorithms.
80 The Algebraic Eraser was first introduced in Key agreement, the
81 Algebraic Eraser, and lightweight cryptography [AAGL] published by
82 the American Mathematical Society in 2004. It describes "a new key
83 agreement protocol suitable for implementation on low-cost platforms
84 which constrain the use of computational resources." This document
85 specifies how to encode, store, and use the Algebraic Eraser(TM) Key
86 Agreement Protocol (AEKAP) in OpenPGP.
88 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
89 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
90 document are to be interpreted as described in RFC 2119 [RFC2119].
92 2. The Algebraic Eraser
94 The Algebraic Eraser brings together the Braid Group, Matrices, and
95 operations over small Finite Fields to produce an algorithm that
96 executes linear in time with the increase in key size.
98 A complete description of the Algebraic Eraser is available in
99 [AAGL].
101 2.1. E-Multiplication
103 The Algebraic Eraser defines an operation called "E-Multiplication"
104 upon which the algorithm is based (see [AAGL]). E-Multiplication
105 (denoted herein by *) takes one matrix (M0) and permutation (S0) and
106 operates on a second matrix (M1) and permutation (S1), resulting in
107 another matrix (M2) and permutation (S2). In other words: (M0,S0) *
108 (M1,S1) = (M2,S2).
110 2.2. AEKAP Keyset Parameters
112 AEKAP Keyset Parameters are similar to Diffie-Hellman cyclic groups
113 of prime order or ECC curves. Just as users must choose the same DH
114 prime or ECC curve in order to communicate, similarly participants in
115 the AEKAP must be using the same Keyset Parameters.
117 The first basic set of parameters is the chosen Braid Group and Field
118 Size, BnFq, where n is the number of strands in the chosen braid
119 (also called the braid index) and q is the size of the field in use.
120 The field size, q, must be a power of a prime. Generally it is 2^r
121 (where r is a small integer) although this is not a requirement. For
122 example, one might choose B10F8 or B16F32. This is like choosing how
123 many bits to use when generating a prime for Diffie-Hellman.
125 Once the BnFq space is chosen then the Keyset Parameters can be
126 generated by a trusted third party (TTP). First they generate an
127 n-by-n matrix (M) where each entry in the matrix is a member of the
128 field Fq. Then the TTP generates at least two sets of braid
129 conjugates, Ca and Cb, where each conjugate in Ca commutes with each
130 conjugate in Cb. The conjugates are lists of "braid words", or
131 "Artin generators" within the Bn braid group. The TTP generates La
132 conjugates for set Ca and Lb conjugates for set Cb, where the numbers
133 La and Lb MAY be different. The public Keyset Parameters are the
134 Matrix and conjugate sets and must be available to generate keys that
135 can communicate. These Keysets MAY be published and named, but MUST
136 be numbered with an OID.
138 For two users to execute the AEKAP they MUST generate keys from the
139 same Keyset and they MUST choose from different conjugate sets within
140 that Keyset. I.e., for Alice and Bob to complete the AEKAP Alice
141 must generate her key from Ca and Bob must generate his key from Cb.
143 This document does not specify any particular Keyset Parameters that
144 MUST be implemented.
146 2.3. Generating Key Pairs
148 The Algebraic Eraser has a two-part Private Key and a two-part Public
149 Key. The Public key is then generated from the two Private Keys.
151 To generate the 1st private key you generate a random polynomial and
152 apply that to the public matrix from the keyset within the keyset
153 field. This results in an nxn matrix where each entry in the matrix
154 is a member of the field Fq. The key search space for the 1st
155 private key is 2^nr (where q=2^r).
157 To generate the 2nd private key you choose a random set of conjugates
158 (and inverses) and string them together. This results in a long
159 string of Artin generators (and inverses). You MAY reduce the string
160 if you so choose using the Dehornoy reduction [Dehornoy]. The search
161 space of the 2nd private key is (2k)^l (where k is the number of
162 published conjugates, and l the number of chosen conjugates and
163 inverses).
165 The Public Key is computed by an E-Multiplication of the 1st private
166 key and the 2nd private key, where the 2nd private key is iteratively
167 processed. Each Artin generator in the 2nd private key is associated
168 to a specific Colored Burau (CB) matrix and permutation (see [AAGL]).
169 The E-multiplication occurs after you substitute the T-values in the
170 CB Matrix with the values in the existing permutation. The result
171 (the public key) is an nxn matrix of Fq and another permutation.
173 Note that the last row of the Public Key Matrix is all zero except
174 for the last entry. When encoding the Public Key you SHOULD ignore
175 those zeros.
177 3. Encoding of Public and Private Keys
179 Each portion of a key can be reduced to a byte-string (or, more
180 accurately, multiple byte strings). Each matrix can be encoded by
181 stringing together each field element in each row and then stringing
182 each row together. A permutation can be encoded by stringing
183 together each element in the list. The conjugates are also encoded
184 by stringing together each element.
186 The following public key algorithm IDs are added to expand section
187 9.1 of [RFC4880], "Public-Key Algorithms":
189 +------+----------------------------+
190 | ID | Description of Algorithm |
191 +------+----------------------------+
192 | TBD1 | AEKAP public key algorithm |
193 +------+----------------------------+
195 Encoding of Public and Private keys MUST use the version 4 packet
196 format (or newer).
198 3.1. Encoding Bit-Strings
200 The Algebraic eraser uses matrices, fields, and braids that are
201 denoted in bits, particular strings of bits. These objects need to
202 be encoded into bit strings for storage and transmission. The most
203 simplistic method of encoding is to take each field as a byte (or
204 multi-byte word) and string them together. The following sections
205 detail multiple (alternate) ways these bit strings can be encoded to
206 possibly reduce the space used.
208 3.1.1. Encoding Techniques
210 Depending on the number of bits used per element (which is defined by
211 the braid index and field size), using different encodings of these
212 strings may result in reducing storage space by dropping extra bits
213 and combining elements.
215 For example, when using the finite field F16 each entry can be
216 encoded in exactly one nibble of four (4) bits, so you can easily
217 combine two entries into a single 8-bit byte (called nibble-
218 encoding). This technique could also be used for entries smaller
219 than a nibble, although then you would still have extra (unused)
220 bits. When using the nibble-encoding of an odd number of nibbles the
221 encoding rules MUST specify whether the extra nibble is at the
222 leading or trailing byte.
224 Another encoding option is bit-stealing. This merges all bits
225 together and then cuts it up into 8-bit bytes. For example if the
226 entries are 5 bits each you might steal 3 bits from the second entry
227 to merge into the first, then shift the remaining 2 bits of the
228 second entry, combine with the next 5 bits from the third, and then
229 steal one bit from the fourth entry, and so on, until you've reached
230 the end. This could end up with unused bits at the end of the
231 string.
233 Yet another option is the reverse-bit-stealing, where you start at
234 the end of the string and work your way to the front. This could
235 leave you with unused bits a the front of the string.
237 Assume you require five (5) bits to encode your numbers, the
238 following table shows how you could could use bit stealing and
239 reverse bit stealing to encode them (where a, b, c, and d are the
240 bits in the first, second, third, and fourth entries)
242 +-----------------------+----------+----------+----------+----------+
243 | Full Bytes: | 000aaaaa | 000bbbbb | 000ccccc | 000ddddd |
244 +-----------------------+----------+----------+----------+----------+
245 | Bit stealing: | aaaaabbb | bbcccccd | dddd0000 | |
246 +-----------------------+----------+----------+----------+----------+
247 | Reverse bit stealing: | 0000aaaa | abbbbbcc | cccddddd | |
248 +-----------------------+----------+----------+----------+----------+
250 Any unused bits MUST be left as zero (and MUST be checked to be
251 zero).
253 The actual encoding method MUST be defined by the Keyset parameter
254 definition and may change from one keyset parameter to another.
256 The row of zeros in the matrix SHOULD be assumed to "not exist".
257 When using these encoding techniques you SHOULD just tack the last
258 entry of the final row onto the end of the list of entries of the
259 rest of the matrix. This could result in an odd number of entries
260 depending on your n and q choices potentially requiring passing at
261 the start or end of the bit string.
263 3.1.2. Multi-Byte Entries
265 In the case of entries wider than 8 bits (e.g. a Field parameter
266 greater than 256), the bits are combined in network byte order.
267 However they can still be merged together using the same encoding
268 algorithms from Section 3.1.1 in the case of entries that are not
269 8-bit multiples. For example, a 12-bit field (F4096) could be
270 combined a nibble at a time, or a 10-bit field (F1024) could use bit-
271 stealing.
273 3.2. Encoding Public Keys
275 The following algorithm specific packets are added to Section 5.5.2
276 of [RFC4880], "Public-Key Packet Formats", to support AEKAP:
278 o a variable length field containing a keyset parameter OID,
279 formatted as follows (see [RFC6637] for a full description of the
280 OID encoding method):
282 * a one-octet size of the following field; values 0 and 0xFF are
283 reserved for future extensions,
285 * octets representing a keyset parameter OID
287 o one byte denoting from which set of conjugates in the keyset this
288 key was generated (e.g. the Alice set or the Bob set)
290 o MPI of the public key matrix
292 o MPI of the public key permutation
294 3.3. Encoding Private Keys
296 The following algorithm specific packets are added to Section 5.5.3
297 of [RFC4880], "Secret-Key Packet Formats", to support AEKAP:
299 o MPI of the 1st private key (matrix)
301 o MPI of the 2nd private key (conjugate string)
303 4. Acknowledgements
305 The term "Algebraic Eraser" is a trademark of SecureRF Corporation
306 and is used herein with permission.
308 The author would like to thank Paul Gunnells and Dorian Goldfeld for
309 their tireless efforts to review this document, suggest improvements,
310 and explain to me how to improve my description of how AE works.
312 5. IANA Considerations
314 IANA is requested to assign an algorithm number from the OpenPGP
315 Public-Key Algorithms range, or the "namespace" in the terminology of
316 [RFC5226], that was created by [RFC4880]. See Section 3.
318 +------+----------------------------+-----------+
319 | ID | Algorithm | Reference |
320 +------+----------------------------+-----------+
321 | TBD1 | AEKAP public key algorithm | This doc |
322 +------+----------------------------+-----------+
324 [Notes to RFC-Editor: Please remove the table above on publication.
325 It is desirable not to reuse old or reserved algorithms because some
326 existing tools might print a wrong description. A higher number is
327 also an indication for a newer algorithm. As of now 22 is the next
328 free number.]
330 6. Security Considerations
331 The security considerations of [RFC4880] apply accordingly.
333 AEKAP will generate the same session key when used with the same two
334 public/private key pairs. The authors of AE generally recommend that
335 at least one party use an ephemeral key pair in order to prevent the
336 same session key being generated every time.
338 AEKAP is an encryption-only algorithm, therefore it cannot self-
339 certify a key. To have an AEKAP master key you MUST implement
340 [I-D.atkins-openpgp-device-certificates].
342 When using the generated session key, you MUST only use the bits
343 included in the protocol. You should MUST NOT use any always-zero
344 bits, including those in the last row of the matrix.
346 7. References
348 7.1. Normative References
350 [AAGL] Anshel, I., Anshel, M., Goldfeld, D., and S. Lemieux, "Key
351 agreement, the Algebraic Eraser, and lightweight
352 cryptography", 2004, .
354 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
355 Requirement Levels", BCP 14, RFC 2119, March 1997.
357 [RFC4880] Callas, J., Donnerhacke, L., Finney, H., Shaw, D., and R.
358 Thayer, "OpenPGP Message Format", RFC 4880, November 2007.
360 [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an
361 IANA Considerations Section in RFCs", BCP 26, RFC 5226,
362 May 2008.
364 [RFC6637] Jivsov, A., "Elliptic Curve Cryptography (ECC) in
365 OpenPGP", RFC 6637, June 2012.
367 7.2. Informative References
369 [Dehornoy]
370 Dehornoy, P., "A fast method for comparing braids",
371 Advances in Mathematics 123, 1997,
372 .
374 [I-D.atkins-openpgp-device-certificates]
375 Atkins, D., "OpenPGP Extensions for Device Certificates",
376 draft-atkins-openpgp-device-certificates-00 (work in
377 progress), August 2014.
379 Appendix A. Test Vectors
381 To help implementing this specification a non-normative example is
382 provided. This example assumes:
384 o the algorithm id for AEKAP will be 22
386 o the keyset OID 1.3.6.1.4.1.44196.1.0.0, which defines:
388 * the braid/field as B10F8
390 * the public key packing is nibble-packed with trailing zeros
392 * the 2nd private key is not bit-packed; it uses bit 7 to define
393 "inverse" and bits 3-0 to define the Artin generator.
395 and gets encoded with length 11 and the following hex bytes: 2B 06
396 01 04 01 82 D9 24 01 00 00
398 A.1. Sample key
400 The secret key used for this example is:
402 1st Private Key Matrix:
404 4 2 7 4 1 2 7 7 3 5
405 1 1 5 4 0 5 0 0 3 1
406 2 7 5 3 4 0 6 0 0 4
407 6 1 0 7 4 7 7 4 1 1
408 1 1 7 6 6 2 4 6 5 7
409 7 5 4 1 7 3 7 5 0 7
410 1 6 0 7 3 6 4 2 5 6
411 7 2 3 6 6 6 4 2 7 7
412 3 7 5 2 2 2 0 7 5 2
413 6
415 2nd Private key (in hex):
417 060481820304050384840506028304050682838485810203048506878807880984
418 858384828384858383838485068708070809868788888887880586078809080987
419 880788090809878809030485850384848583838483848506070809878809060506
420 070809878788860788090687080983040506070809030405060708090203840506
421 070405060708838484858583848384858586870687080102030405060708098586
422 878888858586838485858182828282828181828203048586878809080907080607
423 080984858586860283040586868601820304858586878787870808098102038485
424 860102030405860708878787878787088181828384858687080607070606060706
425 070809090607880988090687880907088787080986878809090607080987888687
426 878888078806078809868788888886878788888787888807880987880607880909
427 068708070809098686878807078809090987888686878809880988090906878807
428 880906878888078806060687880987080808080708098687880909888788090987
429 880607060607070788090809878809060708098787888686868787878809880909
430 090607080906878809888888090987880909078809878807880909098788090708
431 098687880607880908098788888888880909878886078888090607080986878886
432 868787888809090809878888090607080987888806878809870809868788090607
433 080987878809880907080987068708090708098686878788888686868686860788
434 880987880987870687888788860788068788078886078806878888078809868787
435 878788078806078886070707070788098708080986868607088787870886870886
436 878708090707088687878787878787080806070886868708090906070809868788
437 078809090809870809870809870809868788060788090906878809090707880986
438 878888888788090807080907860788090987080808090908080808080987880707
439 860707880909098788090986878888880909868788090981828384858687880906
440 070506050606078607070707048304858607070782038485860781028384850606
441 070707080809098401828384050607880909040506870881828384858687088708
442 080102030485060701020384050607080802020101020202020283848586870182
443 838485868708038485860706070809888809098788098687880485860788090905
444 060708090708868708098182838485868788078809878807880987880788090403
445 040303040405068708080985868788090607080806070583040303030304058602
446 03040584058683048582038485010203040485860582838483840201
448 The key was created on 2014-09-08 15:24:20 from the tag conjugates
449 (type 1), and thus the fingerprint of the OpenPGP key is:
451 176D 1360 FBB7 036C C281 8696 8741 94EC A3DF FA7E
453 and the entire public key packet is:
455 98 4a 04 54 0e 02 64 16 0b 2b 06 01 04 01 82 d9
456 24 01 00 00 01 01 6e 26 44 05 46 10 02 50 43 37
457 56 66 37 42 40 10 72 06 14 44 16 67 13 02 70 73
458 11 00 30 27 47 21 75 35 76 13 13 31 00 60 52 75
459 24 50 57 23 60 00 25 12 35 76 a8 94
461 A.2. Sample key agreement
463 The key agreement is created using the sample key against a second
464 (reader) public key. The reader public key has the following data:
466 Matrix (in nibbled-packed hex with trailing zeros):
468 24 14 13 22 14 67 30 02 20 23 11 26 26 51 20 11
469 67 40 56 57 60 77 01 04 66 56 71 35 21 27 57 00
470 55 75 16 40 07 75 05 12 31 35 75 45 66 40
472 Permutation (in nibble-packed hex): 32 14 56 78 9a
474 Which results in the following shared secret:
476 Matrix:
478 4 0 6 5 2 3 0 5 6 0
479 6 5 5 0 2 0 1 7 5 5
480 2 0 2 1 1 1 2 7 2 0
481 4 0 1 2 5 6 6 6 1 2
482 5 0 1 0 7 4 3 3 3 4
483 5 1 2 5 3 3 5 5 7 1
484 1 0 7 1 6 3 4 0 2 1
485 2 7 5 4 6 7 1 4 7 4
486 7 1 5 5 3 6 1 4 1 6
487 5
489 Permutation (decimal): 3 2 1 5 7 6 10 8 9 4
491 Author's Address
493 Derek Atkins
494 SecureRF Corporation
495 100 Beard Sawmill Rd, Suite 350
496 Shelton, CT 06484
497 US
499 Phone: +1 617 623 3745
500 Email: datkins@securerf.com, derek@ihtfp.com