"Liberate" dtls from BN dependency. Fix bug in replay/update.
authorAndy Polyakov <appro@openssl.org>
Tue, 7 Jun 2005 22:21:14 +0000 (22:21 +0000)
committerAndy Polyakov <appro@openssl.org>
Tue, 7 Jun 2005 22:21:14 +0000 (22:21 +0000)
crypto/pqueue/pq_compat.h
crypto/pqueue/pqueue.c
crypto/pqueue/pqueue.h
ssl/d1_both.c
ssl/d1_lib.c
ssl/d1_pkt.c
ssl/dtls1.h
ssl/s3_lib.c
ssl/ssl3.h

index 6538453..bd86efc 100644 (file)
@@ -1,3 +1,4 @@
+#error "to be deleted"
 /* crypto/pqueue/pqueue_compat.h */
 /* 
  * DTLS implementation written by Nagendra Modadugu
index e3eb836..b881ed2 100644 (file)
@@ -68,13 +68,12 @@ typedef struct _pqueue
        } pqueue_s;
 
 pitem *
-pitem_new(PQ_64BIT priority, void *data)
+pitem_new(unsigned char *prio64be, void *data)
        {
        pitem *item = (pitem *) OPENSSL_malloc(sizeof(pitem));
        if (item == NULL) return NULL;
 
-       pq_64bit_init(&(item->priority));
-       pq_64bit_assign(&item->priority, &priority);
+       memcpy(item->priority,prio64be,sizeof(item->priority));
 
        item->data = data;
        item->next = NULL;
@@ -87,7 +86,6 @@ pitem_free(pitem *item)
        {
        if (item == NULL) return;
 
-       pq_64bit_free(&(item->priority));
        OPENSSL_free(item);
        }
 
@@ -124,7 +122,10 @@ pqueue_insert(pqueue_s *pq, pitem *item)
                next != NULL;
                curr = next, next = next->next)
                {
-               if (pq_64bit_gt(&(next->priority), &(item->priority)))
+               /* we can compare 64-bit value in big-endian encoding
+                * with memcmp:-) */
+               int cmp = memcmp(next->priority, item->priority,8);
+               if (cmp > 0)            /* next > item */
                        {
                        item->next = next;
 
@@ -135,8 +136,8 @@ pqueue_insert(pqueue_s *pq, pitem *item)
 
                        return item;
                        }
-               /* duplicates not allowed */
-               if (pq_64bit_eq(&(item->priority), &(next->priority)))
+               
+               else if (cmp == 0)      /* duplicates not allowed */
                        return NULL;
                }
 
@@ -164,7 +165,7 @@ pqueue_pop(pqueue_s *pq)
        }
 
 pitem *
-pqueue_find(pqueue_s *pq, PQ_64BIT priority)
+pqueue_find(pqueue_s *pq, unsigned char *prio64be)
        {
        pitem *next, *prev = NULL;
        pitem *found = NULL;
@@ -175,7 +176,7 @@ pqueue_find(pqueue_s *pq, PQ_64BIT priority)
        for ( next = pq->items; next->next != NULL; 
                  prev = next, next = next->next)
                {
-               if ( pq_64bit_eq(&(next->priority), &priority))
+               if ( memcmp(next->priority, prio64be,8) == 0)
                        {
                        found = next;
                        break;
@@ -183,7 +184,7 @@ pqueue_find(pqueue_s *pq, PQ_64BIT priority)
                }
        
        /* check the one last node */
-       if ( pq_64bit_eq(&(next->priority), &priority))
+       if ( memcpy(next->priority, prio64be,8) ==0)
                found = next;
 
        if ( ! found)
@@ -199,7 +200,6 @@ pqueue_find(pqueue_s *pq, PQ_64BIT priority)
        return found;
        }
 
-#if PQ_64BIT_IS_INTEGER
 void
 pqueue_print(pqueue_s *pq)
        {
@@ -207,11 +207,14 @@ pqueue_print(pqueue_s *pq)
 
        while(item != NULL)
                {
-               printf("item\t%lld\n", item->priority);
+               printf("item\t%02x%02x%02x%02x%02x%02x%02x%02x\n",
+                       item->priority[0],item->priority[1],
+                       item->priority[2],item->priority[3],
+                       item->priority[4],item->priority[5],
+                       item->priority[6],item->priority[7]);
                item = item->next;
                }
        }
-#endif
 
 pitem *
 pqueue_iterator(pqueue_s *pq)
index 02386d1..7a293c8 100644 (file)
 #include <stdlib.h>
 #include <string.h>
 
-#include <openssl/pq_compat.h>
-
 typedef struct _pqueue *pqueue;
 
 typedef struct _pitem
        {
-       PQ_64BIT priority;
+       unsigned char priority[8]; /* 64-bit value in big-endian encoding */
        void *data;
        struct _pitem *next;
        } pitem;
 
 typedef struct _pitem *piterator;
 
-pitem *pitem_new(PQ_64BIT priority, void *data);
+pitem *pitem_new(unsigned char *prio64be, void *data);
 void   pitem_free(pitem *item);
 
 pqueue pqueue_new(void);
@@ -86,7 +84,7 @@ void   pqueue_free(pqueue pq);
 pitem *pqueue_insert(pqueue pq, pitem *item);
 pitem *pqueue_peek(pqueue pq);
 pitem *pqueue_pop(pqueue pq);
-pitem *pqueue_find(pqueue pq, PQ_64BIT priority);
+pitem *pqueue_find(pqueue pq, unsigned char *prio64be);
 pitem *pqueue_iterator(pqueue pq);
 pitem *pqueue_next(piterator *iter);
 
index 92661a9..dfe2bab 100644 (file)
@@ -442,7 +442,7 @@ dtls1_buffer_handshake_fragment(SSL *s, struct hm_header_st* msg_hdr)
 {
     hm_fragment *frag = NULL;
     pitem *item = NULL;
-       PQ_64BIT seq64;
+    unsigned char seq64be[8];
 
     frag = dtls1_hm_fragment_new(msg_hdr->frag_len);
     if ( frag == NULL)
@@ -453,15 +453,14 @@ dtls1_buffer_handshake_fragment(SSL *s, struct hm_header_st* msg_hdr)
 
     memcpy(&(frag->msg_header), msg_hdr, sizeof(*msg_hdr));
 
-    pq_64bit_init(&seq64);
-    pq_64bit_assign_word(&seq64, msg_hdr->seq);
+    memset(seq64be,0,sizeof(seq64be));
+    seq64be[6] = (unsigned char)(msg_hdr->seq>>8);
+    seq64be[7] = (unsigned char)(msg_hdr->seq);
 
-    item = pitem_new(seq64, frag);
+    item = pitem_new(seq64be, frag);
     if ( item == NULL)
         goto err;
 
-    pq_64bit_free(&seq64);
-
     pqueue_insert(s->d1->buffered_messages, item);
     return 1;
 
@@ -1043,7 +1042,7 @@ dtls1_buffer_message(SSL *s, int is_ccs)
     {
     pitem *item;
     hm_fragment *frag;
-       PQ_64BIT seq64;
+    unsigned char seq64be[8];
 
     /* this function is called immediately after a message has 
      * been serialized */
@@ -1071,11 +1070,11 @@ dtls1_buffer_message(SSL *s, int is_ccs)
     frag->msg_header.frag_len = s->d1->w_msg_hdr.msg_len;
     frag->msg_header.is_ccs = is_ccs;
 
-    pq_64bit_init(&seq64);
-    pq_64bit_assign_word(&seq64, frag->msg_header.seq);
+    memset(seq64be,0,sizeof(seq64be));
+    seq64be[6] = (unsigned char)(frag->msg_header.seq>>8);
+    seq64be[7] = (unsigned char)(frag->msg_header.seq);
 
-    item = pitem_new(seq64, frag);
-    pq_64bit_free(&seq64);
+    item = pitem_new(seq64be, frag);
     if ( item == NULL)
         {
         dtls1_hm_fragment_free(frag);
@@ -1101,7 +1100,7 @@ dtls1_retransmit_message(SSL *s, unsigned short seq, unsigned long frag_off,
     pitem *item;
     hm_fragment *frag ;
     unsigned long header_length;
-       PQ_64BIT seq64;
+    unsigned char seq64be[8];
 
     /*
       OPENSSL_assert(s->init_num == 0);
@@ -1109,11 +1108,11 @@ dtls1_retransmit_message(SSL *s, unsigned short seq, unsigned long frag_off,
      */
 
     /* XDTLS:  the requested message ought to be found, otherwise error */
-    pq_64bit_init(&seq64);
-    pq_64bit_assign_word(&seq64, seq);
+    memset(seq64be,0,sizeof(seq64be));
+    seq64be[6] = (unsigned char)(seq>>8);
+    seq64be[7] = (unsigned char)seq;
 
-    item = pqueue_find(s->d1->sent_messages, seq64);
-    pq_64bit_free(&seq64);
+    item = pqueue_find(s->d1->sent_messages, seq64be);
     if ( item == NULL)
         {
         fprintf(stderr, "retransmit:  message %d non-existant\n", seq);
index 458ce54..ea0dbf4 100644 (file)
@@ -132,16 +132,6 @@ int dtls1_new(SSL *s)
        memset(d1,0, sizeof *d1);
 
        /* d1->handshake_epoch=0; */
-#if defined(OPENSSL_SYS_VMS) || defined(VMS_TEST)
-       d1->bitmap.length=64;
-#else
-       d1->bitmap.length=sizeof(d1->bitmap.map) * 8;
-#endif
-       pq_64bit_init(&(d1->bitmap.map));
-       pq_64bit_init(&(d1->bitmap.max_seq_num));
-       
-       pq_64bit_init(&(d1->next_bitmap.map));
-       pq_64bit_init(&(d1->next_bitmap.max_seq_num));
 
        d1->unprocessed_rcds.q=pqueue_new();
        d1->processed_rcds.q=pqueue_new();
@@ -208,12 +198,6 @@ void dtls1_free(SSL *s)
         }
        pqueue_free(s->d1->sent_messages);
 
-       pq_64bit_free(&(s->d1->bitmap.map));
-       pq_64bit_free(&(s->d1->bitmap.max_seq_num));
-
-       pq_64bit_free(&(s->d1->next_bitmap.map));
-       pq_64bit_free(&(s->d1->next_bitmap.max_seq_num));
-
        OPENSSL_free(s->d1);
        }
 
index 892b889..e4c194b 100644 (file)
 #include <openssl/buffer.h>
 #include <openssl/pqueue.h>
 
+/* mod 256 saturating subtract of two 64-bit values in big-endian order */
+static int satsub64be(const unsigned char *v1,const unsigned char *v2)
+       {
+       int i;
+       unsigned char c1,c2;
+
+       for (i=0;i<8;i++,v1++,v2++)
+               {
+               c1=*v1; c2=*v2;
+               if (c1!=c2) break;
+               }
+       if (i==8)       return 0;
+       else if (i==7)  return (int)c1-(int)c2;
+       else if (c1>c2) return 256;
+       else            return -256;
+       }
+
 static int have_handshake_fragment(SSL *s, int type, unsigned char *buf, 
        int len, int peek);
 static int dtls1_record_replay_check(SSL *s, DTLS1_BITMAP *bitmap,
-       PQ_64BIT *seq_num);
+       unsigned char *seq_num);
 static void dtls1_record_bitmap_update(SSL *s, DTLS1_BITMAP *bitmap);
 static DTLS1_BITMAP *dtls1_get_bitmap(SSL *s, SSL3_RECORD *rr, 
     unsigned int *is_next_epoch);
@@ -133,7 +150,7 @@ static int dtls1_record_needs_buffering(SSL *s, SSL3_RECORD *rr,
        unsigned short *priority, unsigned long *offset);
 #endif
 static int dtls1_buffer_record(SSL *s, record_pqueue *q,
-       PQ_64BIT priority);
+       unsigned char *priority);
 static int dtls1_process_record(SSL *s);
 #if PQ_64BIT_IS_INTEGER
 static PQ_64BIT bytes_to_long_long(unsigned char *bytes, PQ_64BIT *num);
@@ -161,9 +178,9 @@ dtls1_copy_record(SSL *s, pitem *item)
 
 
 static int
-dtls1_buffer_record(SSL *s, record_pqueue *queue, PQ_64BIT priority)
-{
-    DTLS1_RECORD_DATA *rdata;
+dtls1_buffer_record(SSL *s, record_pqueue *queue, unsigned char *priority)
+       {
+       DTLS1_RECORD_DATA *rdata;
        pitem *item;
 
        rdata = OPENSSL_malloc(sizeof(DTLS1_RECORD_DATA));
@@ -200,7 +217,7 @@ dtls1_buffer_record(SSL *s, record_pqueue *queue, PQ_64BIT priority)
        ssl3_setup_buffers(s);
        
        return(1);
-    }
+       }
 
 
 static int
@@ -482,15 +499,15 @@ int dtls1_get_record(SSL *s)
        unsigned char *p;
        short version;
        DTLS1_BITMAP *bitmap;
-    unsigned int is_next_epoch;
+       unsigned int is_next_epoch;
 
        rr= &(s->s3->rrec);
        sess=s->session;
 
-    /* The epoch may have changed.  If so, process all the
-     * pending records.  This is a non-blocking operation. */
-    if ( ! dtls1_process_buffered_records(s))
-        return 0;
+       /* The epoch may have changed.  If so, process all the
+        * pending records.  This is a non-blocking operation. */
+       if ( ! dtls1_process_buffered_records(s))
+            return 0;
 
        /* if we're renegotiating, then there may be buffered records */
        if (dtls1_get_processed_record(s))
@@ -518,7 +535,7 @@ again:
                ssl_minor= *(p++);
                version=(ssl_major<<8)|ssl_minor;
 
-        /* sequence number is 64 bits, with top 2 bytes = epoch */ 
+               /* sequence number is 64 bits, with top 2 bytes = epoch */ 
                n2s(p,rr->epoch);
 
                memcpy(&(s->s3->read_sequence[2]), p, 6);
@@ -590,7 +607,7 @@ again:
                }
 
        /* check whether this is a repeat, or aged record */
-       if ( ! dtls1_record_replay_check(s, bitmap, &(rr->seq_num)))
+       if ( ! dtls1_record_replay_check(s, bitmap, rr->seq_num))
                {
                s->packet_length=0; /* dump this record */
                goto again;     /* get another record */
@@ -599,20 +616,21 @@ again:
        /* just read a 0 length packet */
        if (rr->length == 0) goto again;
 
-    /* If this record is from the next epoch (either HM or ALERT), buffer it
-     * since it cannot be processed at this time.
-     * Records from the next epoch are marked as received even though they are 
-     * not processed, so as to prevent any potential resource DoS attack */
-    if (is_next_epoch)
-        {
-        dtls1_record_bitmap_update(s, bitmap);
-        dtls1_buffer_record(s, &(s->d1->unprocessed_rcds), rr->seq_num);
-        s->packet_length = 0;
-        goto again;
-        }
+       /* If this record is from the next epoch (either HM or ALERT),
+        * buffer it since it cannot be processed at this time. Records
+        * from the next epoch are marked as received even though they
+        * are not processed, so as to prevent any potential resource
+        * DoS attack */
+       if (is_next_epoch)
+               {
+               dtls1_record_bitmap_update(s, bitmap);
+               dtls1_buffer_record(s, &(s->d1->unprocessed_rcds), rr->seq_num);
+               s->packet_length = 0;
+               goto again;
+               }
 
-    if ( ! dtls1_process_record(s))
-        return(0);
+       if ( ! dtls1_process_record(s))
+               return(0);
 
        dtls1_clear_timeouts(s);  /* done waiting */
        return(1);
@@ -1451,110 +1469,49 @@ err:
 
 
 static int dtls1_record_replay_check(SSL *s, DTLS1_BITMAP *bitmap,
-       PQ_64BIT *seq_num)
+       unsigned char *seq_num)
        {
-#if PQ_64BIT_IS_INTEGER
-       PQ_64BIT mask = 0x0000000000000001L;
-#endif
-       PQ_64BIT rcd_num, tmp;
-
-       pq_64bit_init(&rcd_num);
-       pq_64bit_init(&tmp);
-
-       /* this is the sequence number for the record just read */
-       pq_64bit_bin2num(&rcd_num, s->s3->read_sequence, 8);
-
-       
-       if (pq_64bit_gt(&rcd_num, &(bitmap->max_seq_num)) ||
-               pq_64bit_eq(&rcd_num, &(bitmap->max_seq_num)))
-               {
-               pq_64bit_assign(seq_num, &rcd_num);
-               pq_64bit_free(&rcd_num);
-               pq_64bit_free(&tmp);
-               return 1;  /* this record is new */
-               }
-
-       pq_64bit_sub(&tmp, &(bitmap->max_seq_num), &rcd_num);
-
-       if ( pq_64bit_get_word(&tmp) > bitmap->length)
-               {
-               pq_64bit_free(&rcd_num);
-               pq_64bit_free(&tmp);
-               return 0;  /* stale, outside the window */
-               }
+       int cmp;
+       unsigned int shift;
+       const unsigned char *seq = s->s3->read_sequence;
 
-#if PQ_64BIT_IS_BIGNUM
-       {
-       int offset;
-       pq_64bit_sub(&tmp, &(bitmap->max_seq_num), &rcd_num);
-       pq_64bit_sub_word(&tmp, 1);
-       offset = pq_64bit_get_word(&tmp);
-       if ( pq_64bit_is_bit_set(&(bitmap->map), offset))
+       cmp = satsub64be(seq,bitmap->max_seq_num);
+       if (cmp > 0)
                {
-               pq_64bit_free(&rcd_num);
-               pq_64bit_free(&tmp);
-               return 0;
+               memcpy (seq_num,seq,8);
+               return 1; /* this record in new */
                }
-       }
-#else
-       mask <<= (bitmap->max_seq_num - rcd_num - 1);
-       if (bitmap->map & mask)
+       shift = -cmp;
+       if (shift >= sizeof(bitmap->map)*8)
+               return 0; /* stale, outside the window */
+       else if (bitmap->map & (1UL<<shift))
                return 0; /* record previously received */
-#endif
-       
-       pq_64bit_assign(seq_num, &rcd_num);
-       pq_64bit_free(&rcd_num);
-       pq_64bit_free(&tmp);
+
        return 1;
        }
 
 
 static void dtls1_record_bitmap_update(SSL *s, DTLS1_BITMAP *bitmap)
        {
+       int cmp;
        unsigned int shift;
-       PQ_64BIT rcd_num;
-       PQ_64BIT tmp;
-       PQ_64BIT_CTX *ctx;
-
-       pq_64bit_init(&rcd_num);
-       pq_64bit_init(&tmp);
+       const unsigned char *seq = s->s3->read_sequence;
 
-       pq_64bit_bin2num(&rcd_num, s->s3->read_sequence, 8);
-
-       /* unfortunate code complexity due to 64-bit manipulation support
-        * on 32-bit machines */
-       if ( pq_64bit_gt(&rcd_num, &(bitmap->max_seq_num)) ||
-               pq_64bit_eq(&rcd_num, &(bitmap->max_seq_num)))
+       cmp = satsub64be(seq,bitmap->max_seq_num);
+       if (cmp > 0)
                {
-               pq_64bit_sub(&tmp, &rcd_num, &(bitmap->max_seq_num));
-               pq_64bit_add_word(&tmp, 1);
-
-               shift = (unsigned int)pq_64bit_get_word(&tmp);
-
-               pq_64bit_lshift(&(tmp), &(bitmap->map), shift);
-               pq_64bit_assign(&(bitmap->map), &tmp);
-
-               pq_64bit_set_bit(&(bitmap->map), 0);
-               pq_64bit_add_word(&rcd_num, 1);
-               pq_64bit_assign(&(bitmap->max_seq_num), &rcd_num);
-
-               pq_64bit_assign_word(&tmp, 1);
-               pq_64bit_lshift(&tmp, &tmp, bitmap->length);
-               ctx = pq_64bit_ctx_new(&ctx);
-               pq_64bit_mod(&(bitmap->map), &(bitmap->map), &tmp, ctx);
-               pq_64bit_ctx_free(ctx);
+               shift = cmp;
+               if (shift < sizeof(bitmap->map)*8)
+                       bitmap->map <<= shift, bitmap->map |= 1UL;
+               else
+                       bitmap->map = 1UL;
+               memcpy(bitmap->max_seq_num,seq,8);
                }
-       else
-               {
-               pq_64bit_sub(&tmp, &(bitmap->max_seq_num), &rcd_num);
-               pq_64bit_sub_word(&tmp, 1);
-               shift = (unsigned int)pq_64bit_get_word(&tmp);
-
-               pq_64bit_set_bit(&(bitmap->map), shift);
+       else    {
+               shift = -cmp;
+               if (shift < sizeof(bitmap->map)*8)
+                       bitmap->map |= 1UL<<shift;
                }
-
-       pq_64bit_free(&rcd_num);
-       pq_64bit_free(&tmp);
        }
 
 
@@ -1715,17 +1672,8 @@ dtls1_reset_seq_numbers(SSL *s, int rw)
                {
                seq = s->s3->read_sequence;
                s->d1->r_epoch++;
-
-               pq_64bit_assign(&(s->d1->bitmap.map), &(s->d1->next_bitmap.map));
-               s->d1->bitmap.length = s->d1->next_bitmap.length;
-               pq_64bit_assign(&(s->d1->bitmap.max_seq_num), 
-                       &(s->d1->next_bitmap.max_seq_num));
-
-               pq_64bit_free(&(s->d1->next_bitmap.map));
-               pq_64bit_free(&(s->d1->next_bitmap.max_seq_num));
+               memcpy(&(s->d1->bitmap), &(s->d1->next_bitmap), sizeof(DTLS1_BITMAP));
                memset(&(s->d1->next_bitmap), 0x00, sizeof(DTLS1_BITMAP));
-               pq_64bit_init(&(s->d1->next_bitmap.map));
-               pq_64bit_init(&(s->d1->next_bitmap.max_seq_num));
                }
        else
                {
index b377cc5..284e531 100644 (file)
@@ -90,9 +90,11 @@ extern "C" {
 
 typedef struct dtls1_bitmap_st
        {
-       PQ_64BIT map;
-       unsigned long length;     /* sizeof the bitmap in bits */
-       PQ_64BIT max_seq_num;  /* max record number seen so far */
+       unsigned long map;              /* track 32 packets on 32-bit systems
+                                          and 64 - on 64-bit systems */
+       unsigned char max_seq_num[8];   /* max record number seen so far,
+                                          64-bit value in big-endian
+                                          encoding */
        } DTLS1_BITMAP;
 
 struct hm_header_st
index 4585ac3..3f2c004 100644 (file)
 #include "kssl_lcl.h"
 #include <openssl/md5.h>
 #include <openssl/dh.h>
-#include <openssl/pq_compat.h>
 
 const char *ssl3_version_str="SSLv3" OPENSSL_VERSION_PTEXT;
 
@@ -1442,8 +1441,8 @@ int ssl3_new(SSL *s)
        memset(s3,0,sizeof *s3);
        EVP_MD_CTX_init(&s3->finish_dgst1);
        EVP_MD_CTX_init(&s3->finish_dgst2);
-       pq_64bit_init(&(s3->rrec.seq_num));
-       pq_64bit_init(&(s3->wrec.seq_num));
+       memset(s3->rrec.seq_num,0,sizeof(s3->rrec.seq_num));
+       memset(s3->wrec.seq_num,0,sizeof(s3->wrec.seq_num));
 
        s->s3=s3;
 
@@ -1478,8 +1477,6 @@ void ssl3_free(SSL *s)
                sk_X509_NAME_pop_free(s->s3->tmp.ca_names,X509_NAME_free);
        EVP_MD_CTX_cleanup(&s->s3->finish_dgst1);
        EVP_MD_CTX_cleanup(&s->s3->finish_dgst2);
-       pq_64bit_free(&(s->s3->rrec.seq_num));
-       pq_64bit_free(&(s->s3->wrec.seq_num));
 
        OPENSSL_cleanse(s->s3,sizeof *s->s3);
        OPENSSL_free(s->s3);
index 1e762f2..0684f05 100644 (file)
 #include <openssl/buffer.h>
 #include <openssl/evp.h>
 #include <openssl/ssl.h>
-#include <openssl/pq_compat.h>
 
 #ifdef  __cplusplus
 extern "C" {
@@ -296,7 +295,7 @@ typedef struct ssl3_record_st
 /*rw*/ unsigned char *input;   /* where the decode bytes are */
 /*r */ unsigned char *comp;    /* only used with decompression - malloc()ed */
 /*r */  unsigned long epoch;    /* epoch number, needed by DTLS1 */
-/*r */  PQ_64BIT seq_num;       /* sequence number, needed by DTLS1 */
+/*r */  unsigned char seq_num[8]; /* sequence number, needed by DTLS1 */
        } SSL3_RECORD;
 
 typedef struct ssl3_buffer_st