ietf-openpgp
[Top] [All Lists]

[openpgp] (updated) Re: Draft review: Algebraic Eraser keys in OpenPGP

2014-09-10 09:07:36
Per responses that I received off-list, here is the -01 version of this
draft.  The main changes made:

1) Change the suggested protocol number from 22 to 23 so as to avoid
   conflict with Ed25519

2) Change the AAGL reference to a different URL that's not behind a
   paywall, and add another Informational reference regarding AEKAP.

Any additional comments, suggestions, or clarifications are welcome.

Thanks,

-derek





Internet Engineering Task Force                                D. Atkins
Internet-Draft                                      SecureRF Corporation
Intended status: Standards Track                      September 10, 2014
Expires: March 14, 2015


                   Using Algebraic Eraser in OpenPGP
                draft-atkins-openpgp-algebraic-eraser-01

Abstract

   The Algebraic Eraser(TM) is an encryption engine that supports, among
   other configurations, a Diffie-Hellman-like key agreement protocol.
   This draft specifies how to encode, store, share, and use Algebraic
   Eraser Key Agreement Protocol keys in OpenPGP.

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 March 14, 2015.

Copyright Notice

   Copyright (c) 2014 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.




Atkins                   Expires March 14, 2015                 [Page 1]

Internet-Draft        Algebraic Eraser for OpenPGP        September 2014


Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
   2.  The Algebraic Eraser  . . . . . . . . . . . . . . . . . . . .   2
     2.1.  E-Multiplication  . . . . . . . . . . . . . . . . . . . .   3
     2.2.  AEKAP Keyset Parameters . . . . . . . . . . . . . . . . .   3
     2.3.  Generating Key Pairs  . . . . . . . . . . . . . . . . . .   4
   3.  Encoding of Public and Private Keys . . . . . . . . . . . . .   4
     3.1.  Encoding Bit-Strings  . . . . . . . . . . . . . . . . . .   5
       3.1.1.  Encoding Techniques . . . . . . . . . . . . . . . . .   5
       3.1.2.  Multi-Byte Entries  . . . . . . . . . . . . . . . . .   6
     3.2.  Encoding Public Keys  . . . . . . . . . . . . . . . . . .   6
     3.3.  Encoding Private Keys . . . . . . . . . . . . . . . . . .   7
   4.  Acknowledgements  . . . . . . . . . . . . . . . . . . . . . .   7
   5.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .   7
   6.  Security Considerations . . . . . . . . . . . . . . . . . . .   8
   7.  References  . . . . . . . . . . . . . . . . . . . . . . . . .   8
     7.1.  Normative References  . . . . . . . . . . . . . . . . . .   8
     7.2.  Informative References  . . . . . . . . . . . . . . . . .   8
   Appendix A.  Test Vectors . . . . . . . . . . . . . . . . . . . .   9
     A.1.  Sample key  . . . . . . . . . . . . . . . . . . . . . . .   9
     A.2.  Sample key agreement  . . . . . . . . . . . . . . . . . .  10
   Author's Address  . . . . . . . . . . . . . . . . . . . . . . . .  11

1.  Introduction

   The OpenPGP specification in [RFC4880] defines the use of RSA,
   Elgamal, and DSA public key algorithms.  [RFC6637] adds support for
   Elliptic Curve Cryptography and specifies the ECDSA and ECDH
   algorithms.

   The Algebraic Eraser was first introduced in Key agreement, the
   Algebraic Eraser, and lightweight cryptography [AAGL] published by
   the American Mathematical Society in 2004.  It describes "a new key
   agreement protocol suitable for implementation on low-cost platforms
   which constrain the use of computational resources."  It is further
   compared to other algorithims in [AEIntro].  This document specifies
   how to encode, store, and use the Algebraic Eraser(TM) Key Agreement
   Protocol (AEKAP) in OpenPGP.

   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.  The Algebraic Eraser






Atkins                   Expires March 14, 2015                 [Page 2]

Internet-Draft        Algebraic Eraser for OpenPGP        September 2014


   The Algebraic Eraser brings together the Braid Group, Matrices, and
   operations over small Finite Fields to produce an algorithm that
   executes linear in time with the increase in key size.

   A complete description of the Algebraic Eraser is available in
   [AAGL].

2.1.  E-Multiplication

   The Algebraic Eraser defines an operation called "E-Multiplication"
   upon which the algorithm is based (see [AAGL]).  E-Multiplication
   (denoted herein by *) takes one matrix (M0) and permutation (S0) and
   operates on a second matrix (M1) and permutation (S1), resulting in
   another matrix (M2) and permutation (S2).  In other words: (M0,S0) *
   (M1,S1) = (M2,S2).

2.2.  AEKAP Keyset Parameters

   AEKAP Keyset Parameters are similar to Diffie-Hellman cyclic groups
   of prime order or ECC curves.  Just as users must choose the same DH
   prime or ECC curve in order to communicate, similarly participants in
   the AEKAP must be using the same Keyset Parameters.

   The first basic set of parameters is the chosen Braid Group and Field
   Size, BnFq, where n is the number of strands in the chosen braid
   (also called the braid index) and q is the size of the field in use.
   The field size, q, must be a power of a prime.  Generally it is 2^r
   (where r is a small integer) although this is not a requirement.  For
   example, one might choose B10F8 or B16F32.  This is like choosing how
   many bits to use when generating a prime for Diffie-Hellman.

   Once the BnFq space is chosen then the Keyset Parameters can be
   generated by a trusted third party (TTP).  First they generate an
   n-by-n matrix (M) where each entry in the matrix is a member of the
   field Fq.  Then the TTP generates at least two sets of braid
   conjugates, Ca and Cb, where each conjugate in Ca commutes with each
   conjugate in Cb.  The conjugates are lists of "braid words", or
   "Artin generators" within the Bn braid group.  The TTP generates La
   conjugates for set Ca and Lb conjugates for set Cb, where the numbers
   La and Lb MAY be different.  The public Keyset Parameters are the
   Matrix and conjugate sets and must be available to generate keys that
   can communicate.  These Keysets MAY be published and named, but MUST
   be numbered with an OID.

   For two users to execute the AEKAP they MUST generate keys from the
   same Keyset and they MUST choose from different conjugate sets within
   that Keyset.  I.e., for Alice and Bob to complete the AEKAP Alice
   must generate her key from Ca and Bob must generate his key from Cb.



Atkins                   Expires March 14, 2015                 [Page 3]

Internet-Draft        Algebraic Eraser for OpenPGP        September 2014


   This document does not specify any particular Keyset Parameters that
   MUST be implemented.

2.3.  Generating Key Pairs

   The Algebraic Eraser has a two-part Private Key and a two-part Public
   Key.  The Public key is then generated from the two Private Keys.

   To generate the 1st private key you generate a random polynomial and
   apply that to the public matrix from the keyset within the keyset
   field.  This results in an nxn matrix where each entry in the matrix
   is a member of the field Fq.  The key search space for the 1st
   private key is 2^nr (where q=2^r).

   To generate the 2nd private key you choose a random set of conjugates
   (and inverses) and string them together.  This results in a long
   string of Artin generators (and inverses).  You MAY reduce the string
   if you so choose using the Dehornoy reduction [Dehornoy].  The search
   space of the 2nd private key is (2k)^l (where k is the number of
   published conjugates, and l the number of chosen conjugates and
   inverses).

   The Public Key is computed by an E-Multiplication of the 1st private
   key and the 2nd private key, where the 2nd private key is iteratively
   processed.  Each Artin generator in the 2nd private key is associated
   to a specific Colored Burau (CB) matrix and permutation (see [AAGL]).
   The E-multiplication occurs after you substitute the T-values in the
   CB Matrix with the values in the existing permutation.  The result
   (the public key) is an nxn matrix of Fq and another permutation.

   Note that the last row of the Public Key Matrix is all zero except
   for the last entry.  When encoding the Public Key you SHOULD ignore
   those zeros.

3.  Encoding of Public and Private Keys

   Each portion of a key can be reduced to a byte-string (or, more
   accurately, multiple byte strings).  Each matrix can be encoded by
   stringing together each field element in each row and then stringing
   each row together.  A permutation can be encoded by stringing
   together each element in the list.  The conjugates are also encoded
   by stringing together each element.

   The following public key algorithm IDs are added to expand section
   9.1 of [RFC4880], "Public-Key Algorithms":

                   +------+----------------------------+
                   |  ID  |  Description of Algorithm  |



Atkins                   Expires March 14, 2015                 [Page 4]

Internet-Draft        Algebraic Eraser for OpenPGP        September 2014


                   +------+----------------------------+
                   | TBD1 | AEKAP public key algorithm |
                   +------+----------------------------+


   Encoding of Public and Private keys MUST use the version 4 packet
   format (or newer).

3.1.  Encoding Bit-Strings

   The Algebraic eraser uses matrices, fields, and braids that are
   denoted in bits, particular strings of bits.  These objects need to
   be encoded into bit strings for storage and transmission.  The most
   simplistic method of encoding is to take each field as a byte (or
   multi-byte word) and string them together.  The following sections
   detail multiple (alternate) ways these bit strings can be encoded to
   possibly reduce the space used.

3.1.1.  Encoding Techniques

   Depending on the number of bits used per element (which is defined by
   the braid index and field size), using different encodings of these
   strings may result in reducing storage space by dropping extra bits
   and combining elements.

   For example, when using the finite field F16 each entry can be
   encoded in exactly one nibble of four (4) bits, so you can easily
   combine two entries into a single 8-bit byte (called nibble-
   encoding).  This technique could also be used for entries smaller
   than a nibble, although then you would still have extra (unused)
   bits.  When using the nibble-encoding of an odd number of nibbles the
   encoding rules MUST specify whether the extra nibble is at the
   leading or trailing byte.

   Another encoding option is bit-stealing.  This merges all bits
   together and then cuts it up into 8-bit bytes.  For example if the
   entries are 5 bits each you might steal 3 bits from the second entry
   to merge into the first, then shift the remaining 2 bits of the
   second entry, combine with the next 5 bits from the third, and then
   steal one bit from the fourth entry, and so on, until you've reached
   the end.  This could end up with unused bits at the end of the
   string.

   Yet another option is the reverse-bit-stealing, where you start at
   the end of the string and work your way to the front.  This could
   leave you with unused bits a the front of the string.





Atkins                   Expires March 14, 2015                 [Page 5]

Internet-Draft        Algebraic Eraser for OpenPGP        September 2014


   Assume you require five (5) bits to encode your numbers, the
   following table shows how you could could use bit stealing and
   reverse bit stealing to encode them (where a, b, c, and d are the
   bits in the first, second, third, and fourth entries)

   +-----------------------+----------+----------+----------+----------+
   |           Full Bytes: | 000aaaaa | 000bbbbb | 000ccccc | 000ddddd |
   +-----------------------+----------+----------+----------+----------+
   |         Bit stealing: | aaaaabbb | bbcccccd | dddd0000 |          |
   +-----------------------+----------+----------+----------+----------+
   | Reverse bit stealing: | 0000aaaa | abbbbbcc | cccddddd |          |
   +-----------------------+----------+----------+----------+----------+


   Any unused bits MUST be left as zero (and MUST be checked to be
   zero).

   The actual encoding method MUST be defined by the Keyset parameter
   definition and may change from one keyset parameter to another.

   The row of zeros in the matrix SHOULD be assumed to "not exist".
   When using these encoding techniques you SHOULD just tack the last
   entry of the final row onto the end of the list of entries of the
   rest of the matrix.  This could result in an odd number of entries
   depending on your n and q choices potentially requiring passing at
   the start or end of the bit string.

3.1.2.  Multi-Byte Entries

   In the case of entries wider than 8 bits (e.g. a Field parameter
   greater than 256), the bits are combined in network byte order.
   However they can still be merged together using the same encoding
   algorithms from Section 3.1.1 in the case of entries that are not
   8-bit multiples.  For example, a 12-bit field (F4096) could be
   combined a nibble at a time, or a 10-bit field (F1024) could use bit-
   stealing.

3.2.  Encoding Public Keys

   The following algorithm specific packets are added to Section 5.5.2
   of [RFC4880], "Public-Key Packet Formats", to support AEKAP:

   o  a variable length field containing a keyset parameter OID,
      formatted as follows (see [RFC6637] for a full description of the
      OID encoding method):

      *  a one-octet size of the following field; values 0 and 0xFF are
         reserved for future extensions,



Atkins                   Expires March 14, 2015                 [Page 6]

Internet-Draft        Algebraic Eraser for OpenPGP        September 2014


      *  octets representing a keyset parameter OID

   o  one byte denoting from which set of conjugates in the keyset this
      key was generated (e.g. the Alice set or the Bob set)

   o  MPI of the public key matrix

   o  MPI of the public key permutation

3.3.  Encoding Private Keys

   The following algorithm specific packets are added to Section 5.5.3
   of [RFC4880], "Secret-Key Packet Formats", to support AEKAP:

   o  MPI of the 1st private key (matrix)

   o  MPI of the 2nd private key (conjugate string)

4.  Acknowledgements

   The term "Algebraic Eraser" is a trademark of SecureRF Corporation
   and is used herein with permission.

   The author would like to thank Paul Gunnells and Dorian Goldfeld for
   their tireless efforts to review this document, suggest improvements,
   and explain to me how to improve my description of how AE works.  Big
   thanks also to Werner Koch and Vedaal for their comments and
   suggestions.

5.  IANA Considerations

   IANA is requested to assign an algorithm number from the OpenPGP
   Public-Key Algorithms range, or the "namespace" in the terminology of
   [RFC5226], that was created by [RFC4880].  See Section 3.

             +------+----------------------------+-----------+
             |  ID  |         Algorithm          | Reference |
             +------+----------------------------+-----------+
             | TBD1 | AEKAP public key algorithm |  This doc |
             +------+----------------------------+-----------+


   [Notes to RFC-Editor: Please remove the table above on publication.
   It is desirable not to reuse old or reserved algorithms because some
   existing tools might print a wrong description.  A higher number is
   also an indication for a newer algorithm.  As of now 22 is the next
   free number, but we request the selection of 23.]




Atkins                   Expires March 14, 2015                 [Page 7]

Internet-Draft        Algebraic Eraser for OpenPGP        September 2014


6.  Security Considerations

   The security considerations of [RFC4880] apply accordingly.

   AEKAP will generate the same session key when used with the same two
   public/private key pairs.  The authors of AE generally recommend that
   at least one party use an ephemeral key pair in order to prevent the
   same session key being generated every time.

   AEKAP is an encryption-only algorithm, therefore it cannot self-
   certify a key.  To have an AEKAP master key you MUST implement
   [I-D.atkins-openpgp-device-certificates].

   When using the generated session key, you MUST only use the bits
   included in the protocol.  You should MUST NOT use any always-zero
   bits, including those in the last row of the matrix.

7.  References

7.1.  Normative References

   [AAGL]     Anshel, I., Anshel, M., Goldfeld, D., and S. Lemieux, "Key
              agreement, the Algebraic Eraser, and lightweight
              cryptography", Contemporary Mathematics 418, 2004, <http:/
              /www.securerf.com/wp-content/uploads/2014/03/SecureRF-
              Technical-White-Paper-06-with-Appendix-A-B.pdf>.

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, March 1997.

   [RFC4880]  Callas, J., Donnerhacke, L., Finney, H., Shaw, D., and R.
              Thayer, "OpenPGP Message Format", RFC 4880, November 2007.

   [RFC5226]  Narten, T. and H. Alvestrand, "Guidelines for Writing an
              IANA Considerations Section in RFCs", BCP 26, RFC 5226,
              May 2008.

   [RFC6637]  Jivsov, A., "Elliptic Curve Cryptography (ECC) in
              OpenPGP", RFC 6637, June 2012.

7.2.  Informative References

   [AEIntro]  SecureRF Corporation, SRF., "An Introduction to
              Cryptographic Security Methods and Their Role in Securing
              Low Resource Computing Devices", 2011, <http://
              www.securerf.com/wp-content/uploads/2014/04/
              SecureRF_Security_Intro_White_Paper.pdf>.




Atkins                   Expires March 14, 2015                 [Page 8]

Internet-Draft        Algebraic Eraser for OpenPGP        September 2014


   [Dehornoy]
              Dehornoy, P., "A fast method for comparing braids",
              Advances in Mathematics 123, 1997,
              <http://www.math.unicaen.fr/~dehornoy/Papers/Dfo.pdf>.

   [I-D.atkins-openpgp-device-certificates]
              Atkins, D., "OpenPGP Extensions for Device Certificates",
              draft-atkins-openpgp-device-certificates-00 (work in
              progress), August 2014.

Appendix A.  Test Vectors

   To help implementing this specification a non-normative example is
   provided.  This example assumes:

   o  the algorithm id for AEKAP will be 23

   o  the keyset OID 1.3.6.1.4.1.44196.1.0.0, which defines:

      *  the braid/field as B10F8

      *  the public key packing is nibble-packed with trailing zeros

      *  the 2nd private key is not bit-packed; it uses bit 7 to define
         "inverse" and bits 3-0 to define the Artin generator.

      and gets encoded with length 11 and the following hex bytes: 2B 06
      01 04 01 82 D9 24 01 00 00

A.1.  Sample key

   The secret key used for this example is:

   1st Private Key Matrix:

      4 2 7 4 1 2 7 7 3 5
      1 1 5 4 0 5 0 0 3 1
      2 7 5 3 4 0 6 0 0 4
      6 1 0 7 4 7 7 4 1 1
      1 1 7 6 6 2 4 6 5 7
      7 5 4 1 7 3 7 5 0 7
      1 6 0 7 3 6 4 2 5 6
      7 2 3 6 6 6 4 2 7 7
      3 7 5 2 2 2 0 7 5 2
                        6


   2nd Private key (in hex):



Atkins                   Expires March 14, 2015                 [Page 9]

Internet-Draft        Algebraic Eraser for OpenPGP        September 2014


      060481820304050384840506028304050682838485810203048506878807880984
      858384828384858383838485068708070809868788888887880586078809080987
      880788090809878809030485850384848583838483848506070809878809060506
      070809878788860788090687080983040506070809030405060708090203840506
      070405060708838484858583848384858586870687080102030405060708098586
      878888858586838485858182828282828181828203048586878809080907080607
      080984858586860283040586868601820304858586878787870808098102038485
      860102030405860708878787878787088181828384858687080607070606060706
      070809090607880988090687880907088787080986878809090607080987888687
      878888078806078809868788888886878788888787888807880987880607880909
      068708070809098686878807078809090987888686878809880988090906878807
      880906878888078806060687880987080808080708098687880909888788090987
      880607060607070788090809878809060708098787888686868787878809880909
      090607080906878809888888090987880909078809878807880909098788090708
      098687880607880908098788888888880909878886078888090607080986878886
      868787888809090809878888090607080987888806878809870809868788090607
      080987878809880907080987068708090708098686878788888686868686860788
      880987880987870687888788860788068788078886078806878888078809868787
      878788078806078886070707070788098708080986868607088787870886870886
      878708090707088687878787878787080806070886868708090906070809868788
      078809090809870809870809870809868788060788090906878809090707880986
      878888888788090807080907860788090987080808090908080808080987880707
      860707880909098788090986878888880909868788090981828384858687880906
      070506050606078607070707048304858607070782038485860781028384850606
      070707080809098401828384050607880909040506870881828384858687088708
      080102030485060701020384050607080802020101020202020283848586870182
      838485868708038485860706070809888809098788098687880485860788090905
      060708090708868708098182838485868788078809878807880987880788090403
      040303040405068708080985868788090607080806070583040303030304058602
      03040584058683048582038485010203040485860582838483840201

   The key was created on 2014-09-09 16:35:36 from the tag conjugates
   (type 1), and thus the fingerprint of the OpenPGP key is:

      8020 A772 BA18 EA47 3501 B8CE EABE 1082 56BB 5D64

   and the entire public key packet is:

      98 4a 04 54 0f 64 98 17  0b 2b 06 01 04 01 82 d9
      24 01 00 00 01 01 6e 26  44 05 46 10 02 50 43 37
      56 66 37 42 40 10 72 06  14 44 16 67 13 02 70 73
      11 00 30 27 47 21 75 35  76 13 13 31 00 60 52 75
      24 50 57 23 60 00 25 12  35 76 a8 94


A.2.  Sample key agreement





Atkins                   Expires March 14, 2015                [Page 10]

Internet-Draft        Algebraic Eraser for OpenPGP        September 2014


   The key agreement is created using the sample key against a second
   (reader) public key.  The reader public key has the following data:

   Matrix (in nibbled-packed hex with trailing zeros):

      24 14 13 22 14 67 30 02  20 23 11 26 26 51 20 11
      67 40 56 57 60 77 01 04  66 56 71 35 21 27 57 00
      55 75 16 40 07 75 05 12  31 35 75 45 66 40


   Permutation (in nibble-packed hex): 32 14 56 78 9a

   Which results in the following shared secret:

   Matrix:

      4 0 6 5 2 3 0 5 6 0
      6 5 5 0 2 0 1 7 5 5
      2 0 2 1 1 1 2 7 2 0
      4 0 1 2 5 6 6 6 1 2
      5 0 1 0 7 4 3 3 3 4
      5 1 2 5 3 3 5 5 7 1
      1 0 7 1 6 3 4 0 2 1
      2 7 5 4 6 7 1 4 7 4
      7 1 5 5 3 6 1 4 1 6
                        5


   Permutation (decimal): 3 2 1 5 7 6 10 8 9 4

Author's Address

   Derek Atkins
   SecureRF Corporation
   100 Beard Sawmill Rd, Suite 350
   Shelton, CT  06484
   US

   Phone: +1 617 623 3745
   Email: datkins(_at_)securerf(_dot_)com, derek(_at_)ihtfp(_dot_)com











Atkins                   Expires March 14, 2015                [Page 11]

-- 
       Derek Atkins                 617-623-3745
       derek(_at_)ihtfp(_dot_)com             www.ihtfp.com
       Computer and Internet Security Consultant
_______________________________________________
openpgp mailing list
openpgp(_at_)ietf(_dot_)org
https://www.ietf.org/mailman/listinfo/openpgp
<Prev in Thread] Current Thread [Next in Thread>