Abstracting primitives and modes of operation

Question

I am developing a symmetric crypto library and have reached a roadblock. Looking at block ciphers, it is quite obvious that all block ciphers are trivially abstractable as a simple primitive consisting of:

• a key schedule
• a permutation function (which takes as an input a key, possibly a "tweak" and a data input)

This makes all block ciphers easy to use in any mode of operation, and makes it easy to "swap out" various algorithms in favor of others without needing to rewrite extensive amounts of code - only the above components differ between algorithms.

I am having trouble observing the same level of abstraction with hash functions. They are described by their compression function (straightforward) but also seem to have a built-in mode of operation which, while often shared between various hash functions, is not meant to be changed, for instance nobody uses the MD5 compression function with a Davies-Meyer construction, it is always used with Merkle-Damgård because that is what MD5, as a whole, is.

And these modes of operation are not quite the same, for instance Merkle-Damgård applies some simple padding at the end of the message to hash and then divides the message into blocks and processes it like that, whereas the UBI construction uses an extra "configuration input" in its compression function which requires the message to be handled quite differently.

So my question is: is there a way to nicely abstract hash functions in a specific framework as elegantly as with block ciphers, without needing to specifically write every hash function in a different way, so as to achieve optimal code reuse?

The best compromise I could come with is categorizing different hash functions in groups depending on what mode of operation they use (such as MD5, SHA1, SHA2, RIPEMD, etc.. would all go into the Merkle-Damgård category, whereas Skein would go in the UBI category, and so on), which would have code related to message padding and handling being reused when necessary, but also increases code complexity slightly.

This is also an issue for HMAC constructions. There is a fully abstract HMAC construction which works with any hash function regardless of its internals, however newer hash functions are starting to provide their own specific HMAC designs (for instance, Skein and its HMAC configuration block) which are more efficient than the "standard" method.

Answer 1

It is not a good idea to try and find abstractions at places where there is no fundamental reason for them to exist. That there is some "accidental" structure in the way encryption or hash methods are build up does not say anything about future encryption or hash functions.

Besides, you may need to apply specific protections against e.g. side channel attacks. It would be a shame if your carefully build software design would be in the way of creating a more secure library.

Note that if there is no fundamental reason for specific abstractions, there may not be any advantage in creating them. E.g. you would not see too many advantages regarding code duplication.

Many algorithms have specific naming conventions and reference implementations. You should not want to shoehorn those into your design.

Answer 2

I have successfully made the abstraction that you want. You should not abstract on internal implementation details but rather the interfaces. The internal implementation can be resued in several ways, but is not the point of abstract. I have included some excerpts that shows how this works.

Here is a (slightly edited) portion of a header file that shows the class relationships. I have removed details that aren't important, including templates.

struct Binary;      // This is an array of bytes and inherits from a "string".
struct   Digest;
struct     Digestor;
struct       BlockDigestor;
struct         Md2Digestor;
struct         Md4Digestor;
struct         Md5Digestor;
struct         RipeMd128Digestor;
struct         RipeMd160Digestor;
struct         RipeMd256Digestor;
struct         RipeMd320Digestor;
struct         RipeMdDigestor;
struct         Sha160Digestor;
struct         Sha256Digestor;
struct         Sha512Digestor;
struct     Encryptor;
struct       Angerona;
struct       BlockEncryptor;
struct         Des;
struct         Rijndael;
struct         Tdea;

Here is part of the header for Digest

struct Digest : Binary
   {
   public:
      Digest();
      Digest(Digest const & digest);
     ~Digest();

      void operator=(Digest const & digest);

      void consume(unsigned4 n);                 ///< Consume the first n bytes of the encryption buffer.
      using Binary::erase;
      using Binary::extent;
      using Binary::length;
      using Binary::size;

      virtual void      erase();                ///< Erase transformation data.
      virtual unsigned4 extent() const;         ///< Return the length of the transformed data.
      virtual unsigned4 length() const;         ///< Return the length of the transformed data.
      virtual unsigned4 size() const;           ///< Return the length of the transf ormed data.
      virtual void      swap(Digest & digest);  ///< Swap contents with another digest.
      };

And for Digestor (with comments because it is the key abstraction)...

/**
 *    This is an abstract base class for all dynamic classes which
 * "digest" a buffer resulting in a "digest". The general framework
 * is modeled as follows...
 *
 *    1. Segmentation
 *
 *          The input is divided into a number of blocks of equal
 *          length and the last, generally incomplete, block is
 *          padded in a unique and reversible way.
 *
 *    2. Initialization
 *
 *          The initial chaining state is set equal to a value fixed
 *          by the specification.
 *
 *    3. Iteration
 *
 *          The chaining state is updated sequentially by a chaining
 *          transformation for all blocks.
 *
 *    4. Result
 *
 *          The digest is obtained from the final chaining state by
 *          the output transformation.
 *
 * This model is realized by the following protocol.
 *
 *    1. Immediately following construction or a call to digest() the
 *       internal state is such that calls to digest(buffer,n) will
 *       perform (2).
 *
 *    2. Zero or more calls to digest(buffer,n) will perform (1) and
 *       (3). An internal buffer will contain any undigested input
 *       which is the result of partial segmentation.
 *
 *    3. Calls to digest() will treat any undigested input as an
 *       incomplete final block and pad that block appropriately. It
 *       will then perform (4) so that the digestor is a final digest.
 *       Referencing the digest is an error before digest() has been
 *       called.
 *
 *    4. Calls to digest(buffer) will effectively call digest(buffer,n)
 *       and then digest().
 */ 

struct Digestor : Digest
   {
   public:
      virtual Digestor const & digest() = 0;                                  ///< Finalize digest.
      virtual Digestor const & digest(void const * buffer, unsigned4 n) = 0;  ///< Digest raw buffer.

     template <class Data> Digestor const & digest(Data const & buffer);     ///< Digest data buffer.

      Digestor const & operator()();
      Digestor const & operator()(void const * buffer, unsigned4 n);

      template <class Data> Digestor const & operator()(Data const & buffer); ///< Digest data buffer.

      virtual unsigned4    blockSize() const = 0;                             ///< Return length of block.
      virtual Byte const * digestData() const = 0;                            ///< Return pointer to digest.
      virtual unsigned4    digestSize() const = 0;                            ///< Return length of digest.

      void hmac(                                                              ///< Generate keyed Hash Message Authentication Code (HMAC).
         void const * key,
         unsigned4    keyLength,
         void const * message,
         unsigned4    messageLength);

      static Digestor * digestor(HashDigestor hash);                          ///< Return a new digestor.
   };

BlockDigestor implements the interface needed for block based algorithms.

/**
 *    A BlockDigestor is a Digestor which digests its input in blocks.
 * Each block is N bytes long. The final block will contain a length
 * field which is M bytes long and contains the number of input blocks.
 * M is either 8 or 16. The length of the final digest is L bytes.
 */

template <unsigned4 N, unsigned4 M, unsigned4 L, bool littleEndian>
   struct BlockDigestor : Digestor
      {
      public:
         template <class Data> Digestor const & digest(Data const * string); ///< Digest string.
         template <class Data> Digestor const & digest(Data const & buffer); ///< Digest data buffer.

         Digestor const & digest();
         Digestor const & digest(void const * buffer, unsigned4 n);

      protected:
         virtual void digestBlock(void const * buffer) = 0; ///< Digest block.
         virtual void finalize();                           ///< Finalize digest.
         virtual void initialize() = 0;                     ///< Initialize digest.

         unsigned8 digested$;
             Byte      buffer$[N];
      };
  }

And (finially) here is the header for SHA 256 that shows how everything comes together.

/**
 *    An Sha256Digestor instance is a digest which is the cryptographically
 * secure, one-way hash of a buffer based on the SHA-2 federal standard
 * (FIPS 180-2 issued by NIST).
 *
 * Note: If this class is instantiated where N has any value other than
 *       224 or 256 then a link error will result. This is intentional.
 */

template <unsigned4 N>
   struct Sha256Digestor : BlockDigestor<64,8,N/8,false>
      {
      public:
         Sha256Digestor();
         Sha256Digestor(Sha256Digestor<N> const & digest);

         void operator=(Sha256Digestor<N> const & digest);

      protected:
         void digestBlock(void const * buffer); ///< Digest block.
         void finalize();                       ///< Finalize digest.
         void initialize();                     ///< Initialize digest.

         enum
            {
            wordWidth$    =  4,           ///< Number of bytes in each word - 4 (SHA-1, SHA-256) or 8 (SHA-384, SHA-512).
                blockSize$    = 64,           ///< Number of bytes in block.
            lengthOffset$ = 56,           ///< Offset in block to length field.
                digestSize$   = N / 8,        ///< Size of digest in bytes.
            digestPad$    = (256 - N) / 8 ///< Length of additional internal state.
            };

         union
            {
            unsigned1 digest1$[32];       ///< digestSize$ + digestPad$
                unsigned4 digest4$[32/4];
            };

      private:
         static unsigned4 mixer0(unsigned4 x);
         static unsigned4 mixer1(unsigned4 x);
         static unsigned4 mixer2(unsigned4 x);
         static unsigned4 mixer3(unsigned4 x);
         static void      roundA(unsigned4 * w, unsigned4 & h0, unsigned4 & h1, unsigned4 & h2, unsigned4 & h3, unsigned4 & h4, unsigned4 & h5, unsigned4 & h6, unsigned4 & h7, unsigned i, unsigned4 const * b);
         static void      roundB(unsigned4 * w, unsigned4 & h0, unsigned4 & h1, unsigned4 & h2, unsigned4 & h3, unsigned4 & h4, unsigned4 & h5, unsigned4 & h6, unsigned4 & h7, unsigned i);
      };
namespace ShaConstants
   {
   extern unsigned4 sha32Constants[64];
   }

typedef DigestorFinal<Sha256Digestor<224> > Sha224;
typedef DigestorFinal<Sha256Digestor<256> > Sha256;