» Wednesday, 16 December A.D. 2009

using reinitialize-instance

In my “code that will eventually go into Ironclad” directory, I had the following function:

(defmethod derive-key ((kdf pbkdf1) passphrase salt iteration-count key-length)
  (unless (plusp iteration-count)
    (error 'invalid-iteration-count))
  (loop with digest-name = (kdf-digest kdf)
     with digest-length = (ironclad:digest-length digest-name)
     with key = (make-array 20 :element-type '(unsigned-byte 8))
     initially
       (let ((d (ironclad:make-digest digest-name)))
         (update-digest d passphrase)
         (update-digest d salt)
         (produce-digest d :digest key))
     for i from 1 below iteration-count
     do
       (ironclad:digest-sequence digest-name key :end digest-length :digest key)
     finally
       (return (subseq key 0 (min key-length (length key))))))

This snippet implements the algorithm of section 5.1 of RFC 2898. (We don't have to worry about the hardcoded length of 20 for the key, since PBKDF1 is specified to only work with MD2, MD5, or SHA1; the validation to make sure we do so happens elsewhere.) It's a fine implementation, except that profiling indicates entirely too much time is being spent in digest allocation/initialization. It'd be nice if we could just construct the required digest once (since we're using the same digest algorithm throughout the loop) and reset it to its original state each time we needed to hash something.

Fortunately, the designers of Common Lisp anticipated this situation and built in a standard way of addressing it: the reinitialize-instance generic function. The idea behind it is very simple. When you create new instances of a class, you say:

(defparameter *c* (make-instance 'myclass [...initargs...]))

At some later point, when you decide that you really need *C* to be slightly different, but you don't want to allocate another instance of MYCLASS, you say:

(reinitialize-instance *c* [...other initargs...])

and the appropriate computations take place to make it as if you had said:

(setf *c* (make-instance 'myclass [...other initargs...]))

except without the extra allocation and with the benefit that anybody holding references to *C* now sees the updated version.

reinitialize-instance will automagically work with all CLOS instances. You do have to pay careful attention to how it works if you do fancy things with object initialization; I'll write about playing nice with reinitialize-instance in a future post. Also, since it's a generic function, you can define methods on it for structures as well as classes. (One of the fun things about Common Lisp is that you can use classes without using generic functions and vice versa.) Which is handy for Ironclad, since all of its digest objects are implemented as structures for speed.

All this is to say that the above code can be rewritten to be more efficient:

(defmethod derive-key ((kdf pbkdf1) passphrase salt iteration-count key-length)
  (unless (plusp iteration-count)
    (error 'invalid-iteration-count))
  (loop with digest-name = (kdf-digest kdf)
     with digest = (ironclad:make-digest digest-name)
     with digest-length = (ironclad:digest-length digest-name)
     with key = (make-array 20 :element-type '(unsigned-byte 8))
     initially
       (ironclad:update-digest digest passphrase)
       (ironclad:update-digest digest salt)
       (ironclad:produce-digest digest :digest key)
     for i from 1 below iteration-count
     do
       (reinitialize-instance digest)
       (ironclad:update-digest digest key :end digest-length)
       (ironclad:produce-digest digest :digest key)
     finally
       (return (subseq key 0 (min key-length (length key))))))

It's not a huge difference, but making sure to use reinitialize-instance and defining appropriate methods on it did make a huge difference for PBKDF2, whose less-consy definition looks like:

(defmethod derive-key ((kdf pbkdf2) passphrase salt iteration-count key-length)
  (unless (plusp iteration-count)
    (error 'invalid-argument))
  (unless (plusp (length passphrase))
    (error 'invalid-argument))
  (loop with count = 1
     with hmac = (ironclad:make-hmac passphrase (kdf-digest kdf))
     with hmac-length = (ironclad:digest-length (kdf-digest kdf))
     with key = (make-array key-length :element-type '(unsigned-byte 8)
                            :initial-element 0)
     with key-position = 0
     with count-buffer = (make-array 4 :element-type '(unsigned-byte 8))
     with hmac-out = (make-array hmac-length :element-type '(unsigned-byte 8))
     while (plusp key-length)
     do (let ((size (min hmac-length key-length)))
          (reinitialize-instance hmac :key passphrase)
          (ironclad:update-hmac hmac salt)
          (setf (ironclad:ub32ref/be count-buffer 0) count)
          (ironclad:update-hmac hmac count-buffer)
          (ironclad:hmac-digest hmac :buffer hmac-out)
          (ironclad::xor-block size hmac-out key key-position key key-position)
          (loop for i from 1 below iteration-count
             do
               (reinitialize-instance hmac :key passphrase)
               (ironclad:update-hmac hmac hmac-out)
               (ironclad:hmac-digest hmac :buffer hmac-out)
               (ironclad::xor-block size hmac-out key key-position key key-position)
             finally
               (decf key-length size)
               (incf key-position size)
               (incf count)))
     finally (return key)))

Reinitializing the HMAC instances in the loops versus simply reallocating them is a huge win, since HMAC instances also include digest instances; those digest instances don't have to be reallocated when the instance is reinitialized, but can instead be reinitialized themselves.

posted by Nate @ 1:28PM