krb5 commit: Sort principal key_data retrieved from KDB module

[Greg Hudson]

https://github.com/krb5/krb5/commit/44ad57d8d38efc944f64536354435f5b721c0ee0
commit 44ad57d8d38efc944f64536354435f5b721c0ee0
Author: Sarah Day <sarahday at mit.edu>
Date:   Thu Jan 21 11:16:21 2016 -0500

    Sort principal key_data retrieved from KDB module
    
    Some krb5 code expects principal keys to be sorted by kvno in
    descending order.  To make sure this is followed in all KDB
    implementations, sort the keys in libkdb5 after principals are
    retrieved.

 src/include/kdb.h           |   17 +++++++++++-
 src/lib/kdb/kdb5.c          |   61 ++++++++++++++++++++++++++++++++++++++++--
 src/lib/kdb/libkdb5.exports |    1 +
 3 files changed, 75 insertions(+), 4 deletions(-)

diff --git a/src/include/kdb.h b/src/include/kdb.h
index 9d3bf9d..71546af 100644
--- a/src/include/kdb.h
+++ b/src/include/kdb.h
@@ -1,6 +1,6 @@
 /* -*- mode: c; c-basic-offset: 4; indent-tabs-mode: nil -*- */
 /*
- * Copyright 1990,1991 by the Massachusetts Institute of Technology.
+ * Copyright 1990, 1991, 2016 by the Massachusetts Institute of Technology.
  * All Rights Reserved.
  *
  * Export of this software from the United States of America may
@@ -209,6 +209,8 @@ typedef struct _krb5_db_entry_new {
 
     krb5_principal        princ;                /* Length, data */
     krb5_tl_data        * tl_data;              /* Linked list */
+
+    /* key_data must be sorted by kvno in descending order. */
     krb5_key_data       * key_data;             /* Array */
 } krb5_db_entry;
 
@@ -683,6 +685,19 @@ krb5_error_code krb5_db_check_allowed_to_delegate(krb5_context kcontext,
                                                   const krb5_db_entry *server,
                                                   krb5_const_principal proxy);
 
+/**
+ * Sort an array of @a krb5_key_data keys in descending order by their kvno.
+ * Key data order within a kvno is preserved.
+ *
+ * @param key_data
+ *     The @a krb5_key_data array to sort.  This is sorted in place so the
+ *     array will be modified.
+ * @param key_data_length
+ *     The length of @a key_data.
+ */
+void
+krb5_dbe_sort_key_data(krb5_key_data *key_data, size_t key_data_length);
+
 /* default functions. Should not be directly called */
 /*
  *   Default functions prototype
diff --git a/src/lib/kdb/kdb5.c b/src/lib/kdb/kdb5.c
index 50daf74..deafed1 100644
--- a/src/lib/kdb/kdb5.c
+++ b/src/lib/kdb/kdb5.c
@@ -1,6 +1,7 @@
 /* -*- mode: c; c-basic-offset: 4; indent-tabs-mode: nil -*- */
 /*
- * Copyright 2006, 2009, 2010 by the Massachusetts Institute of Technology.
+ * Copyright 2006, 2009, 2010, 2016 by the Massachusetts Institute of
+ * Technology.
  * All Rights Reserved.
  *
  * Export of this software from the United States of America may
@@ -752,7 +753,15 @@ krb5_db_get_principal(krb5_context kcontext, krb5_const_principal search_for,
         return status;
     if (v->get_principal == NULL)
         return KRB5_PLUGIN_OP_NOTSUPP;
-    return v->get_principal(kcontext, search_for, flags, entry);
+    status = v->get_principal(kcontext, search_for, flags, entry);
+    if (status)
+        return status;
+
+    /* Sort the keys in the db entry as some parts of krb5 expect it to be. */
+    if ((*entry)->key_data != NULL)
+        krb5_dbe_sort_key_data((*entry)->key_data, (*entry)->n_key_data);
+
+    return 0;
 }
 
 void
@@ -942,6 +951,26 @@ krb5_db_delete_principal(krb5_context kcontext, krb5_principal search_for)
     return status;
 }
 
+/*
+ * Use a proxy function for iterate so that we can sort the keys before sending
+ * them to the callback.
+ */
+struct callback_proxy_args {
+    int (*func)(krb5_pointer, krb5_db_entry *);
+    krb5_pointer func_arg;
+};
+
+static int
+sort_entry_callback_proxy(krb5_pointer func_arg, krb5_db_entry *entry)
+{
+    struct callback_proxy_args *args = (struct callback_proxy_args *)func_arg;
+
+    /* Sort the keys in the db entry as some parts of krb5 expect it to be. */
+    if (entry && entry->key_data)
+        krb5_dbe_sort_key_data(entry->key_data, entry->n_key_data);
+    return args->func(args->func_arg, entry);
+}
+
 krb5_error_code
 krb5_db_iterate(krb5_context kcontext, char *match_entry,
                 int (*func)(krb5_pointer, krb5_db_entry *),
@@ -949,13 +978,20 @@ krb5_db_iterate(krb5_context kcontext, char *match_entry,
 {
     krb5_error_code status = 0;
     kdb_vftabl *v;
+    struct callback_proxy_args proxy_args;
 
     status = get_vftabl(kcontext, &v);
     if (status)
         return status;
     if (v->iterate == NULL)
         return KRB5_PLUGIN_OP_NOTSUPP;
-    return v->iterate(kcontext, match_entry, func, func_arg, iterflags);
+
+    /* Use the proxy function to sort key data before passing entries to
+     * callback. */
+    proxy_args.func = func;
+    proxy_args.func_arg = func_arg;
+    return v->iterate(kcontext, match_entry, sort_entry_callback_proxy,
+                      &proxy_args, iterflags);
 }
 
 /* Return a read only pointer alias to mkey list.  Do not free this! */
@@ -2564,3 +2600,22 @@ krb5_db_check_allowed_to_delegate(krb5_context kcontext,
         return KRB5_PLUGIN_OP_NOTSUPP;
     return v->check_allowed_to_delegate(kcontext, client, server, proxy);
 }
+
+void
+krb5_dbe_sort_key_data(krb5_key_data *key_data, size_t key_data_length)
+{
+    size_t i, j;
+    krb5_key_data tmp;
+
+    /* Use insertion sort as a stable sort. */
+    for (i = 1; i < key_data_length; i++) {
+        j = i;
+        while (j > 0 &&
+               key_data[j - 1].key_data_kvno < key_data[j].key_data_kvno) {
+            tmp = key_data[j];
+            key_data[j] = key_data[j - 1];
+            key_data[j - 1] = tmp;
+            j--;
+        }
+    }
+}
diff --git a/src/lib/kdb/libkdb5.exports b/src/lib/kdb/libkdb5.exports
index cb4c3df..68ac537 100644
--- a/src/lib/kdb/libkdb5.exports
+++ b/src/lib/kdb/libkdb5.exports
@@ -99,3 +99,4 @@ ulog_get_sno_status
 ulog_replay
 ulog_set_last
 xdr_kdb_incr_update_t
+krb5_dbe_sort_key_data