PROV: Add the beginning of a DER writing library

This library is meant to be small and quick.  It's based on WPACKET,
which was extended to support DER writing.  The way it's used is a
bit unusual, as it's used to write the structures backward into a
given buffer.  A typical quick call looks like this:

    /*
     * Fill in this structure:
     *
     * something ::= SEQUENCE {
     *     id OBJECT IDENTIFIER,
     *     x [0] INTEGER OPTIONAL,
     *     y [1] BOOLEAN OPTIONAL,
     *     n INTEGER
     * }
     */
    unsigned char buf[nnnn], *p = NULL;
    size_t encoded_len = 0;
    WPACKET pkt;
    int ok;

    ok =   WPACKET_init_der(&pkt, buf, sizeof(buf)
        && DER_w_start_sequence(&pkt, -1)
        && DER_w_bn(&pkt, -1, bn)
        && DER_w_boolean(&pkt, 1, bool)
        && DER_w_precompiled(&pkt, -1, OID, sizeof(OID))
        && DER_w_end_sequence(&pkt, -1)
        && WPACKET_finish(&pkt)
        && WPACKET_get_total_written(&pkt, &encoded_len)
        && (p = WPACKET_get_curr(&pkt)) != NULL;

Reviewed-by: Matt Caswell <matt@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/11450)

9 files changed, 532 insertions, 1 deletions

diff --git a/crypto/build.info b/crypto/build.info
index baa31ee8e1..864506a18d 100644
--- a/crypto/build.info
+++ b/crypto/build.info
@@ -71,7 +71,7 @@ $UTIL_COMMON=\
         cryptlib.c params.c params_from_text.c bsearch.c ex_data.c o_str.c \
         ctype.c threads_pthread.c threads_win.c threads_none.c initthread.c \
         context.c sparse_array.c asn1_dsa.c packet.c param_build.c $CPUIDASM \
-        param_build_set.c
+        param_build_set.c der_writer.c
 $UTIL_DEFINE=$CPUIDDEF
 
 SOURCE[../libcrypto]=$UTIL_COMMON \
diff --git a/crypto/der_writer.c b/crypto/der_writer.c
new file mode 100644
index 0000000000..26fd88592d
--- /dev/null
+++ b/crypto/der_writer.c
@@ -0,0 +1,142 @@
+/*
+ * Copyright 2020 The OpenSSL Project Authors. All Rights Reserved.
+ *
+ * Licensed under the Apache License 2.0 (the "License").  You may not use
+ * this file except in compliance with the License.  You can obtain a copy
+ * in the file LICENSE in the source distribution or at
+ * https://www.openssl.org/source/license.html
+ */
+
+#include <stdlib.h>
+#include <string.h>
+#include "internal/cryptlib.h"
+#include "internal/der.h"
+#include "crypto/bn.h"
+
+static int int_start_context(WPACKET *pkt, int tag)
+{
+    if (tag < 0)
+        return 1;
+    if (!ossl_assert(tag <= 30))
+        return 0;
+    return WPACKET_start_sub_packet(pkt);
+}
+
+static int int_end_context(WPACKET *pkt, int tag)
+{
+    if (tag < 0)
+        return 1;
+    if (!ossl_assert(tag <= 30))
+        return 0;
+    return WPACKET_close(pkt)
+        && WPACKET_put_bytes_u8(pkt, DER_C_CONTEXT | tag);
+}
+
+int DER_w_precompiled(WPACKET *pkt, int tag,
+                      const unsigned char *precompiled, size_t precompiled_n)
+{
+    return int_start_context(pkt, tag)
+        && WPACKET_memcpy(pkt, precompiled, precompiled_n)
+        && int_end_context(pkt, tag);
+}
+
+int DER_w_boolean(WPACKET *pkt, int tag, int b)
+{
+    return int_start_context(pkt, tag)
+        && WPACKET_start_sub_packet(pkt)
+        && (!b || WPACKET_put_bytes_u8(pkt, 0xFF))
+        && !WPACKET_close(pkt)
+        && !WPACKET_put_bytes_u8(pkt, DER_P_BOOLEAN)
+        && int_end_context(pkt, tag);
+}
+
+static int int_der_w_integer(WPACKET *pkt, int tag,
+                             int (*put_bytes)(WPACKET *pkt, const void *v,
+                                              unsigned int *top_byte),
+                             const void *v)
+{
+    unsigned int top_byte = 0;
+
+    return int_start_context(pkt, tag)
+        && WPACKET_start_sub_packet(pkt)
+        && put_bytes(pkt, v, &top_byte)
+        && ((top_byte & 0x80) == 0 || WPACKET_put_bytes_u8(pkt, 0))
+        && WPACKET_close(pkt)
+        && WPACKET_put_bytes_u8(pkt, DER_P_INTEGER)
+        && int_end_context(pkt, tag);
+}
+
+static int int_put_bytes_ulong(WPACKET *pkt, const void *v,
+                               unsigned int *top_byte)
+{
+    const unsigned long *value = v;
+    unsigned long tmp = *value;
+    size_t n = 0;
+
+    while (tmp != 0) {
+        n++;
+        *top_byte = (tmp & 0xFF);
+        tmp >>= 8;
+    }
+    if (n == 0)
+        n = 1;
+
+    return WPACKET_put_bytes__(pkt, *value, n);
+}
+
+/* For integers, we only support unsigned values for now */
+int DER_w_ulong(WPACKET *pkt, int tag, unsigned long v)
+{
+    return int_der_w_integer(pkt, tag, int_put_bytes_ulong, &v);
+}
+
+static int int_put_bytes_bn(WPACKET *pkt, const void *v,
+                            unsigned int *top_byte)
+{
+    unsigned char *p = NULL;
+    size_t n = BN_num_bytes(v);
+
+    /* The BIGNUM limbs are in LE order */
+    *top_byte =
+        ((bn_get_words(v) [(n - 1) / BN_BYTES]) >> (8 * ((n - 1) % BN_BYTES)))
+        & 0xFF;
+
+    if (!WPACKET_allocate_bytes(pkt, n, &p))
+        return 0;
+    if (p != NULL)
+        BN_bn2bin(v, p);
+    return 1;
+}
+
+int DER_w_bn(WPACKET *pkt, int tag, const BIGNUM *v)
+{
+    if (v == NULL || BN_is_negative(v))
+        return 0;
+    if (BN_is_zero(v))
+        return DER_w_ulong(pkt, tag, 0);
+
+    return int_der_w_integer(pkt, tag, int_put_bytes_bn, v);
+}
+
+int DER_w_null(WPACKET *pkt, int tag)
+{
+    return int_start_context(pkt, tag)
+        && WPACKET_start_sub_packet(pkt)
+        && WPACKET_close(pkt)
+        && WPACKET_put_bytes_u8(pkt, DER_P_NULL)
+        && int_end_context(pkt, tag);
+}
+
+/* Constructed things need a start and an end */
+int DER_w_begin_sequence(WPACKET *pkt, int tag)
+{
+    return int_start_context(pkt, tag)
+        && WPACKET_start_sub_packet(pkt);
+}
+
+int DER_w_end_sequence(WPACKET *pkt, int tag)
+{
+    return WPACKET_close(pkt)
+        && WPACKET_put_bytes_u8(pkt, DER_F_CONSTRUCTED | DER_P_SEQUENCE)
+        && int_end_context(pkt, tag);
+}
diff --git a/doc/internal/man3/DER_w_begin_sequence.pod b/doc/internal/man3/DER_w_begin_sequence.pod
new file mode 100644
index 0000000000..3d221a942f
--- /dev/null
+++ b/doc/internal/man3/DER_w_begin_sequence.pod
@@ -0,0 +1,48 @@
+=pod
+
+=head1 NAME
+
+DER_w_begin_sequence, DER_w_end_sequence
+- internal DER writers for DER constructed elements
+
+=head1 SYNOPSIS
+
+ #include "internal/der.h"
+
+ int DER_w_begin_sequence(WPACKET *pkt, int tag);
+ int DER_w_end_sequence(WPACKET *pkt, int tag);
+
+=head1 DESCRIPTION
+
+All functions described here are wrappers for constructed structures,
+i.e. the ASN.1 SEQUENCE, SET and CHOICE specifications.  They all come
+in pairs, as noted by the function names containing the words C<begin>
+and B<end>.
+
+When using these, special care must be taken to ensure that the ASN.1 tag
+value I<tag> is the same in the matching C<begin> and C<end> function calls.
+
+DER_w_begin_sequence() and DER_w_end_sequence() begins and ends a
+SEQUENCE.
+
+=head1 RETURN VALUES
+
+All the functions return 1 on success and 0 on failure.  Failure may
+mean that the buffer held by the I<pkt> is too small, but may also
+mean that the values given to the functions are invalid, such as the provided
+I<tag> value being too large for the implementation.
+
+=head1 SEE ALSO
+
+L<DERlib(7)>
+
+=head1 COPYRIGHT
+
+Copyright 2020 The OpenSSL Project Authors. All Rights Reserved.
+
+Licensed under the Apache License 2.0 (the "License").  You may not use
+this file except in compliance with the License.  You can obtain a copy
+in the file LICENSE in the source distribution or at
+L<https://www.openssl.org/source/license.html>.
+
+=cut
diff --git a/doc/internal/man3/DER_w_bn.pod b/doc/internal/man3/DER_w_bn.pod
new file mode 100644
index 0000000000..c51223f71a
--- /dev/null
+++ b/doc/internal/man3/DER_w_bn.pod
@@ -0,0 +1,56 @@
+=pod
+
+=head1 NAME
+
+DER_w_boolean, DER_w_ulong, DER_w_bn, DER_w_null
+- internal DER writers for DER primitives
+
+=head1 SYNOPSIS
+
+ #include "internal/der.h"
+
+ int DER_w_boolean(WPACKET *pkt, int tag, int b);
+ int DER_w_ulong(WPACKET *pkt, int tag, unsigned long v);
+ int DER_w_bn(WPACKET *pkt, int tag, const BIGNUM *v);
+ int DER_w_null(WPACKET *pkt, int tag);
+
+=head1 DESCRIPTION
+
+All functions described here behave the same way, they prepend
+(remember that DER writers are used backwards) the DER encoding of
+their respective value to the already written output buffer held by
+I<pkt>.
+
+DER_w_boolean() writes the primitive BOOLEAN using the value I<b>.
+Any value that evaluates as true will render a B<true> BOOLEAN,
+otherwise a B<false> BOOLEAN.
+
+DER_w_ulong() and DER_w_bn() both write the primitive INTEGER using
+the value I<v>.
+
+=for comment Other similar functions for diverse C integers should be
+added.
+
+DER_w_null() writes the primitive NULL.
+
+=head1 RETURN VALUES
+
+All the functions return 1 on success and 0 on failure.  Failure may
+mean that the buffer held by the I<pkt> is too small, but may also
+mean that the values given to the functions are invalid, such as the provided
+I<tag> value being too large for the implementation.
+
+=head1 SEE ALSO
+
+L<DERlib(7)>
+
+=head1 COPYRIGHT
+
+Copyright 2020 The OpenSSL Project Authors. All Rights Reserved.
+
+Licensed under the Apache License 2.0 (the "License").  You may not use
+this file except in compliance with the License.  You can obtain a copy
+in the file LICENSE in the source distribution or at
+L<https://www.openssl.org/source/license.html>.
+
+=cut
diff --git a/doc/internal/man3/DER_w_precompiled.pod b/doc/internal/man3/DER_w_precompiled.pod
new file mode 100644
index 0000000000..81a92526af
--- /dev/null
+++ b/doc/internal/man3/DER_w_precompiled.pod
@@ -0,0 +1,48 @@
+=pod
+
+=head1 NAME
+
+DER_w_precompiled
+- internal DER writers for precompiled DER blobs
+
+=head1 SYNOPSIS
+
+ #include "internal/der.h"
+
+ int DER_w_precompiled(WPACKET *pkt, int tag,
+                       const unsigned char *precompiled,
+                       size_t precompiled_n);
+
+=head1 DESCRIPTION
+
+There may be already existing DER blobs that can simply be copied to
+the buffer held by I<pkt>.  For example, precompiled values, such as
+OIDs (for example, C<id-sha256>) or complete AlgorithmIdentifiers
+(for example, C<sha256Identifier>).  To add those as an element in a
+structure being DER encoded, use DER_w_precompiled().
+
+DER_w_precompiled() will simply take the DER encoded blob given as
+I<precompiled> with length I<precompiled_n> and add it to the buffer
+held by I<pkt>.
+
+=head1 RETURN VALUES
+
+DER_w_precompiled() returns 1 on success and 0 on failure.  Failure
+may mean that the buffer held by the I<pkt> is too small, but may also
+mean that the values given to the functions are invalid, such as the provided
+I<tag> value being too large for the implementation.
+
+=head1 SEE ALSO
+
+L<DERlib(7)>
+
+=head1 COPYRIGHT
+
+Copyright 2020 The OpenSSL Project Authors. All Rights Reserved.
+
+Licensed under the Apache License 2.0 (the "License").  You may not use
+this file except in compliance with the License.  You can obtain a copy
+in the file LICENSE in the source distribution or at
+L<https://www.openssl.org/source/license.html>.
+
+=cut
diff --git a/doc/internal/man7/DERlib.pod b/doc/internal/man7/DERlib.pod
new file mode 100644
index 0000000000..7b0e7225f0
--- /dev/null
+++ b/doc/internal/man7/DERlib.pod
@@ -0,0 +1,148 @@
+=pod
+
+=head1 NAME
+
+DERlib - internal OpenSSL DER library
+
+=head1 DESCRIPTION
+
+OpenSSL contains an internal small DER reading and writing library,
+as an alternative to the publically known i2d and d2i functions.  It's
+solely constituted of functions that work as building blocks to create
+more similar functions to encode and decode larger structures.
+
+All these functions have similar function signatures (C<something>
+will vary depending on what the function will encode):
+
+    int DER_w_something(WPACKET *pkt, int tag, ...);
+
+=begin comment
+
+When readers are added, add this:
+
+    int DER_r_something(PACKET *pkt, int tag, ...);
+
+=end comment
+
+I<pkt> is the packet context used, and I<tag> should be the
+context-specific tag value of the element being handled, or -1 if there
+is no tag number for that element (you may use the convenience macro
+B<DER_NO_CONTEXT> instead of -1).  Any argument following is the C
+variable that's being encoded or decoded.
+
+=head2 DER writers / encoders
+
+DER writers are based in L<WPACKET(3)>, a generic packet writing
+library, so before using any of them, I<pkt> must be initialized
+using L<WPACKET_init_der(3)> or L<WPACKET_init_null_der(3)>
+
+DER writers must be used in reverse order, except for the wrapping
+functions that implement a constructed element.  The latter are easily
+recognised by their function name including the words C<begin> and
+C<end>.  As an example, we can look at the DSA signature structure,
+which is defined like this in ASN.1 terms:
+
+    -- Copied from RFC 3279, section 2.2.2
+    Dss-Sig-Value  ::=  SEQUENCE  {
+            r       INTEGER,
+            s       INTEGER  }
+
+With the DER library, this is the correspoding code, given two OpenSSL
+B<BIGNUM>s I<r> and I<s>:
+
+    int ok = DER_w_begin_sequence(pkt, -1)
+          && DER_w_bn(pkg, -1, s)
+          && DER_w_bn(pkg, -1, r)
+          && DER_w_end_sequence(pkt, -1);
+
+As an example of the use of I<tag>, an ASN.1 element like this:
+
+    v [1] INTEGER OPTIONAL
+
+Would be encoded like this:
+
+    DER_w_bn(pkt, 1, v)
+
+=begin comment
+
+=head2 DER readers / decoders
+
+TBA
+
+=end comment
+
+=head1 EXAMPLES
+
+A more complex example, encoding the AlgorithmIdentifier with
+RSASSA-PSS values.
+
+As a reminder, the AlgorithmIdentifier is specified like this:
+
+    -- From RFC 3280, section 4.1.1.2
+    AlgorithmIdentifier  ::=  SEQUENCE  {
+         algorithm               OBJECT IDENTIFIER,
+         parameters              ANY DEFINED BY algorithm OPTIONAL  }    
+
+And the RSASSA-PSS OID and parameters are specified like this:
+
+    -- From RFC 3279, section 3.1
+    id-RSASSA-PSS  OBJECT IDENTIFIER  ::=  { pkcs-1 10 }
+
+    RSASSA-PSS-params  ::=  SEQUENCE  {
+       hashAlgorithm      [0] HashAlgorithm DEFAULT
+                                 sha1Identifier,
+       maskGenAlgorithm   [1] MaskGenAlgorithm DEFAULT
+                                 mgf1SHA1Identifier,
+       saltLength         [2] INTEGER DEFAULT 20,
+       trailerField       [3] INTEGER DEFAULT 1  }
+
+The value we want to encode, written in ASN.1 syntax:
+
+    {
+        algorithm               id-RSASSA-PSS,
+        parameters {
+            hashAlgorithm       sha256Identifier,
+            maskGenAlgorithm    mgf1SHA256Identifier,
+            saltLength          20  -- unnecessarily explicit
+        }
+    }
+
+Assuming that we have precompiled constants for C<id-RSASSA-PSS>,
+C<sha256Identifier> and C<mgf1SHA256Identifier>, the DER writing code
+looks as follows. This is a complete function to write that specific
+value:
+
+    int DER_w_AlgorithmIdentifier_RSASSA_PSS_special(WPACKET *pkt,
+                                                     int tag,
+                                                     RSA *rsa)
+    {
+        return DER_w_begin_sequence(pkt, tag)
+            && (DER_w_begin_sequence(pkt, DER_NO_CONTEXT)
+                && DER_w_ulong(pkt, 2, 20)
+                && DER_w_precompiled(pkt, 1,
+                                     der_mgf1SHA256Identifier,
+                                     sizeof(der_mgf1SHA256Identifier))
+                && DER_w_precompiled(pkt, 0,
+                                     der_sha256Identifier,
+                                     sizeof(der_sha256Identifier))
+                && DER_w_end_sequence(pkt, DER_NO_CONTEXT))
+            && DER_w_precompiled(pkt, DER_NO_CONTEXT,
+                                 der_id_RSASSA_PSS,
+                                 sizeof(der_id_RSASSA_PSS))
+            && DER_w_end_sequence(pkt, tag);
+    }
+
+=head1 SEE ALSO
+
+L<DER_w_bn(3)>, L<DER_w_begin_sequence(3)>, L<DER_w_precompiled(3)>
+
+=head1 COPYRIGHT
+
+Copyright 2020 The OpenSSL Project Authors. All Rights Reserved.
+
+Licensed under the Apache License 2.0 (the "License").  You may not use
+this file except in compliance with the License.  You can obtain a copy
+in the file LICENSE in the source distribution or at
+L<https://www.openssl.org/source/license.html>.
+
+=cut
diff --git a/include/internal/der.h b/include/internal/der.h
new file mode 100644
index 0000000000..118aa9857c
--- /dev/null
+++ b/include/internal/der.h
@@ -0,0 +1,84 @@
+/*
+ * Copyright 2020 The OpenSSL Project Authors. All Rights Reserved.
+ *
+ * Licensed under the Apache License 2.0 (the "License").  You may not use
+ * this file except in compliance with the License.  You can obtain a copy
+ * in the file LICENSE in the source distribution or at
+ * https://www.openssl.org/source/license.html
+ */
+
+#include <openssl/bn.h>
+#include "internal/packet.h"
+
+/*
+ * NOTE: X.690 numbers the identifier octet bits 1 to 8.
+ * We use the same numbering in comments here.
+ */
+
+/* Well known primitive tags */
+
+/*
+ * DER UNIVERSAL tags, occupying bits 1-5 in the DER identifier byte
+ * These are only valid for the UNIVERSAL class.  With the other classes,
+ * these bits have a different meaning.
+ */
+#define DER_P_EOC                       0 /* BER End Of Contents tag */
+#define DER_P_BOOLEAN                   1
+#define DER_P_INTEGER                   2
+#define DER_P_BIT_STRING                3
+#define DER_P_OCTET_STRING              4
+#define DER_P_NULL                      5
+#define DER_P_OBJECT                    6
+#define DER_P_OBJECT_DESCRIPTOR         7
+#define DER_P_EXTERNAL                  8
+#define DER_P_REAL                      9
+#define DER_P_ENUMERATED               10
+#define DER_P_UTF8STRING               12
+#define DER_P_SEQUENCE                 16
+#define DER_P_SET                      17
+#define DER_P_NUMERICSTRING            18
+#define DER_P_PRINTABLESTRING          19
+#define DER_P_T61STRING                20
+#define DER_P_VIDEOTEXSTRING           21
+#define DER_P_IA5STRING                22
+#define DER_P_UTCTIME                  23
+#define DER_P_GENERALIZEDTIME          24
+#define DER_P_GRAPHICSTRING            25
+#define DER_P_ISO64STRING              26
+#define DER_P_GENERALSTRING            27
+#define DER_P_UNIVERSALSTRING          28
+#define DER_P_BMPSTRING                30
+
+/* DER Flags, occupying bit 6 in the DER identifier byte */
+#define DER_F_PRIMITIVE              0x00
+#define DER_F_CONSTRUCTED            0x20
+
+/* DER classes tags, occupying bits 7-8 in the DER identifier byte */
+#define DER_C_UNIVERSAL              0x00
+#define DER_C_APPLICATION            0x40
+#define DER_C_CONTEXT                0x80
+#define DER_C_PRIVATE                0xC0
+
+/*
+ * Run-time constructors.
+ *
+ * They all construct DER backwards, so care should be taken to use them
+ * that way.
+ */
+
+/* This can be used for all items that don't have a context */
+#define DER_NO_CONTEXT  -1
+
+int DER_w_precompiled(WPACKET *pkt, int tag,
+                      const unsigned char *precompiled, size_t precompiled_n);
+
+int DER_w_boolean(WPACKET *pkt, int tag, int b);
+int DER_w_ulong(WPACKET *pkt, int tag, unsigned long v);
+int DER_w_bn(WPACKET *pkt, int tag, const BIGNUM *v);
+int DER_w_null(WPACKET *pkt, int tag);
+
+/*
+ * All constructors for constructed elements have a begin and a end function
+ */
+int DER_w_begin_sequence(WPACKET *pkt, int tag);
+int DER_w_end_sequence(WPACKET *pkt, int tag);
diff --git a/providers/common/build.info b/providers/common/build.info
index ccc99e515b..b6495d343a 100644
--- a/providers/common/build.info
+++ b/providers/common/build.info
@@ -1,3 +1,5 @@
+SUBDIRS=der
+
 SOURCE[../libcommon.a]=provider_err.c bio_prov.c
 $FIPSCOMMON=provider_util.c
 SOURCE[../libnonfips.a]=$FIPSCOMMON nid_to_name.c
diff --git a/util/missingcrypto.txt b/util/missingcrypto.txt
index dbe4ef55f9..d6d30912f3 100644
--- a/util/missingcrypto.txt
+++ b/util/missingcrypto.txt
@@ -1274,6 +1274,9 @@ WHIRLPOOL_BitUpdate(3)
 WHIRLPOOL_Final(3)
 WHIRLPOOL_Init(3)
 WHIRLPOOL_Update(3)
+WPACKET(3)
+WPACKET_init_der(3)
+WPACKET_init_null_der(3)
 X509V3_EXT_CRL_add_conf(3)
 X509V3_EXT_CRL_add_nconf(3)
 X509V3_EXT_REQ_add_conf(3)