Implement heuristic for matching broken Heimdal sequence number encodings

ticket: 1263
target_version: 1.3
tags: pullup
status: open

git-svn-id: svn://anonsvn.mit.edu/krb5/trunk@15479 dc483132-0cff-0310-8789-dd5450dbe970

5 files changed, 184 insertions, 2 deletions

diff --git a/src/lib/krb5/krb/ChangeLog b/src/lib/krb5/krb/ChangeLog
index 42010819a1..0b7e9d94fe 100644
--- a/src/lib/krb5/krb/ChangeLog
+++ b/src/lib/krb5/krb/ChangeLog
@@ -1,3 +1,15 @@
+2003-05-22  Tom Yu  <tlyu@mit.edu>
+
+	* auth_con.c (krb5int_auth_con_chkseqnum): New function; implement
+	heuristic for broken Heimdal sequence number encoding.
+	(chk_heimdal_seqnum): Auxiliary function for above.
+
+	* auth_con.h: Add flags for sequence number heuristic.
+
+	* rd_priv.c: Use krb5int_auth_con_chkseqnum.
+
+	* rd_safe.c: Use krb5int_auth_con_chkseqnum.
+
 2003-05-22  Sam Hartman  <hartmans@mit.edu>
 
 	* gic_pwd.c (krb5int_populate_gic_opt): returns void
diff --git a/src/lib/krb5/krb/auth_con.c b/src/lib/krb5/krb/auth_con.c
index bc26774a6c..cd3acf176c 100644
--- a/src/lib/krb5/krb/auth_con.c
+++ b/src/lib/krb5/krb/auth_con.c
@@ -1,6 +1,8 @@
 #include "k5-int.h"
 #include "auth_con.h"
 
+static krb5_boolean chk_heimdal_seqnum(krb5_ui_4, krb5_ui_4);
+
 static krb5_error_code
 actx_copy_addr(krb5_context context, const krb5_address *inad, krb5_address **outad)
 {
@@ -395,3 +397,167 @@ krb5_auth_con_get_checksum_func( krb5_context context,
   *data = auth_context->checksum_func_data;
   return 0;
 }
+
+/*
+ * krb5int_auth_con_chkseqnum
+ *
+ * We use a somewhat complex heuristic for validating received
+ * sequence numbers.  We must accommodate both our older
+ * implementation, which sends negative sequence numbers, and the
+ * broken Heimdal implementation (at least as of 0.5.2), which
+ * violates X.690 BER for integer encodings.  The requirement of
+ * handling negative sequence numbers removes one of easier means of
+ * detecting a Heimdal implementation, so we resort to this mess
+ * here.
+ *
+ * X.690 BER (and consequently DER, which are the required encoding
+ * rules in RFC1510) encode all integer types as signed integers.
+ * This means that the MSB being set on the first octet of the
+ * contents of the encoding indicates a negative value.  Heimdal does
+ * not prepend the required zero octet to unsigned integer encodings
+ * which would otherwise have the MSB of the first octet of their
+ * encodings set.
+ *
+ * Our ASN.1 library implements a special decoder for sequence
+ * numbers, accepting both negative and positive 32-bit numbers but
+ * mapping them both into the space of positive unsigned 32-bit
+ * numbers in the obvious bit-pattern-preserving way.  This maintains
+ * compatibility with our older implementations.  This also means that
+ * encodings emitted by Heimdal are ambiguous.
+ *
+ * Heimdal counter value	received uint32 value
+ *
+ * 0x00000080			0xFFFFFF80
+ * 0x000000FF			0xFFFFFFFF
+ * 0x00008000			0xFFFF8000
+ * 0x0000FFFF			0xFFFFFFFF
+ * 0x00800000			0xFF800000
+ * 0x00FFFFFF			0xFFFFFFFF
+ * 0xFF800000			0xFF800000
+ * 0xFFFFFFFF			0xFFFFFFFF
+ *
+ * We use two auth_context flags, SANE_SEQ and HEIMDAL_SEQ, which are
+ * only set after we can unambiguously determine the sanity of the
+ * sending implementation.  Once one of these flags is set, we accept
+ * only the sequence numbers appropriate to the remote implementation
+ * type.  We can make the determination in two different ways.  The
+ * first is to note the receipt of a "negative" sequence number when a
+ * "positive" one was expected.  The second is to note the receipt of
+ * a sequence number that wraps through "zero" in a weird way.  The
+ * latter corresponds to the receipt of an initial sequence number in
+ * the ambiguous range.
+ *
+ * There are 2^7 + 2^15 + 2^23 + 2^23 = 16810112 total ambiguous
+ * initial Heimdal counter values, but we receive them as one of 2^23
+ * possible values.  There is a ~1/256 chance of a Heimdal
+ * implementation sending an intial sequence number in the ambiguous
+ * range.
+ *
+ * We have to do special treatment when receiving sequence numbers
+ * between 0xFF800000..0xFFFFFFFF, or when wrapping through zero
+ * weirdly (due to ambiguous initial sequence number).  If we are
+ * expecting a value corresponding to an ambiguous Heimdal counter
+ * value, and we receive an exact match, we can mark the remote end as
+ * sane.
+ */
+krb5_boolean
+krb5int_auth_con_chkseqnum(
+    krb5_context ctx,
+    krb5_auth_context ac,
+    krb5_ui_4 in_seq)
+{
+    krb5_ui_4 exp_seq;
+
+    exp_seq = ac->remote_seq_number;
+
+    /*
+     * If sender is known to be sane, accept _only_ exact matches.
+     */
+    if (ac->auth_context_flags & KRB5_AUTH_CONN_SANE_SEQ)
+	return in_seq == exp_seq;
+
+    /*
+     * If sender is not known to be sane, first check the ambiguous
+     * range of received values, 0xFF800000..0xFFFFFFFF.
+     */
+    if ((in_seq & 0xFF800000) == 0xFF800000) {
+	/*
+	 * If expected sequence number is in the range
+	 * 0xFF800000..0xFFFFFFFF, then we can't make any
+	 * determinations about the sanity of the sending
+	 * implementation.
+	 */
+	if ((exp_seq & 0xFF800000) == 0xFF800000 && in_seq == exp_seq)
+	    return 1;
+	/*
+	 * If sender is not known for certain to be a broken Heimdal
+	 * implementation, check for exact match.
+	 */
+	if (!(ac->auth_context_flags & KRB5_AUTH_CONN_HEIMDAL_SEQ)
+	    && in_seq == exp_seq)
+	    return 1;
+	/*
+	 * Now apply hairy algorithm for matching sequence numbers
+	 * sent by broken Heimdal implementations.  If it matches, we
+	 * know for certain it's a broken Heimdal sender.
+	 */
+	if (chk_heimdal_seqnum(exp_seq, in_seq)) {
+	    ac->auth_context_flags |= KRB5_AUTH_CONN_HEIMDAL_SEQ;
+	    return 1;
+	}
+	return 0;
+    }
+
+    /*
+     * Received value not in the ambiguous range?  If the _expected_
+     * value is in the range of ambiguous Hemidal counter values, and
+     * it matches the received value, sender is known to be sane.
+     */
+    if (in_seq == exp_seq) {
+	if ((   exp_seq & 0xFFFFFF80) == 0x00000080
+	    || (exp_seq & 0xFFFF8000) == 0x00008000
+	    || (exp_seq & 0xFF800000) == 0x00800000)
+	    ac->auth_context_flags |= KRB5_AUTH_CONN_SANE_SEQ;
+	return 1;
+    }
+
+    /*
+     * Magic wraparound for the case where the intial sequence number
+     * is in the ambiguous range.  This means that the sender's
+     * counter is at a different count than ours, so we correct ours,
+     * and mark the sender as being a broken Heimdal implementation.
+     */
+    if (exp_seq == 0
+	&& !(ac->auth_context_flags & KRB5_AUTH_CONN_HEIMDAL_SEQ)) {
+	switch (in_seq) {
+	case 0x100:
+	case 0x10000:
+	case 0x1000000:
+	    ac->auth_context_flags |= KRB5_AUTH_CONN_HEIMDAL_SEQ;
+	    exp_seq = in_seq;
+	    return 1;
+	default:
+	    return 0;
+	}
+    }
+    return 0;
+}
+
+static krb5_boolean
+chk_heimdal_seqnum(krb5_ui_4 exp_seq, krb5_ui_4 in_seq)
+{
+    if (( exp_seq & 0xFF800000) == 0x00800000
+	&& (in_seq & 0xFF800000) == 0xFF800000
+	&& (in_seq & 0x00FFFFFF) == exp_seq)
+	return 1;
+    else if ((  exp_seq & 0xFFFF8000) == 0x00008000
+	     && (in_seq & 0xFFFF8000) == 0xFFFF8000
+	     && (in_seq & 0x0000FFFF) == exp_seq)
+	return 1;
+    else if ((  exp_seq & 0xFFFFFF80) == 0x00000080
+	     && (in_seq & 0xFFFFFF80) == 0xFFFFFF80
+	     && (in_seq & 0x000000FF) == exp_seq)
+	return 1;
+    else
+	return 0;
+}
diff --git a/src/lib/krb5/krb/auth_con.h b/src/lib/krb5/krb/auth_con.h
index 362909ce77..9543de355e 100644
--- a/src/lib/krb5/krb/auth_con.h
+++ b/src/lib/krb5/krb/auth_con.h
@@ -30,5 +30,7 @@ struct _krb5_auth_context {
 #define KRB5_AUTH_CONN_INITIALIZED	0x00010000
 #define KRB5_AUTH_CONN_USED_W_MK_REQ	0x00020000
 #define KRB5_AUTH_CONN_USED_W_RD_REQ	0x00040000
+#define KRB5_AUTH_CONN_SANE_SEQ		0x00080000
+#define KRB5_AUTH_CONN_HEIMDAL_SEQ	0x00100000
 
 #endif
diff --git a/src/lib/krb5/krb/rd_priv.c b/src/lib/krb5/krb/rd_priv.c
index 180559cc23..cf74807793 100644
--- a/src/lib/krb5/krb/rd_priv.c
+++ b/src/lib/krb5/krb/rd_priv.c
@@ -246,7 +246,8 @@ krb5_rd_priv(krb5_context context, krb5_auth_context auth_context, const krb5_da
     }
 
     if (auth_context->auth_context_flags & KRB5_AUTH_CONTEXT_DO_SEQUENCE) {
-	if (auth_context->remote_seq_number != replaydata.seq) {
+	if (!krb5int_auth_con_chkseqnum(context, auth_context,
+					replaydata.seq)) {
 	    retval =  KRB5KRB_AP_ERR_BADORDER;
 	    goto error;
 	}
diff --git a/src/lib/krb5/krb/rd_safe.c b/src/lib/krb5/krb/rd_safe.c
index 3194229a39..41c2596b7a 100644
--- a/src/lib/krb5/krb/rd_safe.c
+++ b/src/lib/krb5/krb/rd_safe.c
@@ -239,7 +239,8 @@ krb5_rd_safe(krb5_context context, krb5_auth_context auth_context, const krb5_da
     }
 
     if (auth_context->auth_context_flags & KRB5_AUTH_CONTEXT_DO_SEQUENCE) {
-	if (auth_context->remote_seq_number != replaydata.seq) {
+	if (!krb5int_auth_con_chkseqnum(context, auth_context,
+					replaydata.seq)) {
 	    retval =  KRB5KRB_AP_ERR_BADORDER;
 	    goto error;
 	}