From 7fccdcbeb508a3e9e271c1d882692672e0d21b86 Mon Sep 17 00:00:00 2001 From: Nikos Mavrogiannopoulos Date: Fri, 10 Jun 2016 23:14:03 +0200 Subject: dtls: imported Fridolin's DTLS sliding window implementation This simplifies the current code, and reduces the memory needed. --- lib/Makefile.am | 2 +- lib/constate.c | 3 +- lib/dtls-sw.c | 105 ++++++++++++++++++++++++++++++++++++ lib/dtls-window.c | 159 ------------------------------------------------------ lib/dtls.h | 2 +- lib/gnutls_int.h | 13 +++-- lib/record.c | 12 ++--- lib/state.c | 2 +- 8 files changed, 122 insertions(+), 176 deletions(-) create mode 100644 lib/dtls-sw.c delete mode 100644 lib/dtls-window.c diff --git a/lib/Makefile.am b/lib/Makefile.am index 0b50082797..ec549e848c 100644 --- a/lib/Makefile.am +++ b/lib/Makefile.am @@ -77,7 +77,7 @@ COBJECTS = range.c record.c compress.c debug.c cipher.c \ system_override.c crypto-backend.c verify-tofu.c pin.c tpm.c fips.c \ safe-memfuncs.c inet_pton.c atfork.c atfork.h randomart.c \ system-keys.h urls.c urls.h prf.c auto-verify.c dh-session.c \ - cert-session.c handshake-checks.c dtls-window.c + cert-session.c handshake-checks.c dtls-sw.c if WINDOWS COBJECTS += system-keys-win.c diff --git a/lib/constate.c b/lib/constate.c index 16ca0ae791..f4f28c2e62 100644 --- a/lib/constate.c +++ b/lib/constate.c @@ -34,6 +34,7 @@ #include #include #include +#include "dtls.h" static int _gnutls_set_kx(gnutls_session_t session, gnutls_kx_algorithm_t algo); @@ -378,7 +379,7 @@ int _gnutls_epoch_set_keys(gnutls_session_t session, uint16_t epoch) if (ret < 0) return gnutls_assert_val(ret); - params->record_sw_size = 0; + _dtls_reset_window(params); _gnutls_record_log("REC[%p]: Epoch #%u ready\n", session, params->epoch); diff --git a/lib/dtls-sw.c b/lib/dtls-sw.c new file mode 100644 index 0000000000..616bd5a868 --- /dev/null +++ b/lib/dtls-sw.c @@ -0,0 +1,105 @@ +/* + * Copyright (C) 2016 Red Hat, Inc. + * + * Authors: Fridolin Pokorny + * Nikos Mavrogiannopoulos + * + * This file is part of GNUTLS. + * + * The GNUTLS library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public License + * as published by the Free Software Foundation; either version 2.1 of + * the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with this program. If not, see + * + */ + +/* Functions that relate to DTLS sliding window handling. + */ + +#ifndef DTLS_SW_NO_INCLUDES +#include "gnutls_int.h" +#include "errors.h" +#include "debug.h" +#include "dtls.h" +#include "record.h" +#endif + +/* + * DTLS sliding window handling + */ +#define DTLS_EPOCH_SHIFT (6*CHAR_BIT) +#define DTLS_SEQ_NUM_MASK 0x0000FFFFFFFFFFFF +#define DTLS_WINDOW_HAVE_RECV_PACKET(W) ((W)->dtls_sw_have_recv != 0) + +#define DTLS_WINDOW_INIT_AT(W, S) (W)->dtls_sw_bits = ((W)->dtls_sw_have_recv) = 0; (W)->dtls_sw_start = (S&DTLS_SEQ_NUM_MASK) +#define DTLS_WINDOW_INIT(W) DTLS_WINDOW_INIT_AT(W, 0) + +#define DTLS_WINDOW_INSIDE(W, S) ((((S) & DTLS_SEQ_NUM_MASK) > (W)->dtls_sw_start) && \ + (((S) & DTLS_SEQ_NUM_MASK) - (W)->dtls_sw_start <= (sizeof((W)->dtls_sw_bits) * CHAR_BIT))) + +#define DTLS_WINDOW_OFFSET(W, S) ((((S) & DTLS_SEQ_NUM_MASK) - (W)->dtls_sw_start) - 1) + +#define DTLS_WINDOW_RECEIVED(W, S) (((W)->dtls_sw_bits & ((uint64_t) 1 << DTLS_WINDOW_OFFSET(W, S))) != 0) + +#define DTLS_WINDOW_MARK(W, S) ((W)->dtls_sw_bits |= ((uint64_t) 1 << DTLS_WINDOW_OFFSET(W, S))) + +#define DTLS_WINDOW_UPDATE(W) while ((W)->dtls_sw_bits & (uint64_t) 1) { \ + (W)->dtls_sw_bits = (W)->dtls_sw_bits >> 1; \ + (W)->dtls_sw_start++; \ + } + +#define LOAD_UINT64(out, ubytes) \ + for (i = 0; i < 8; i++) { \ + out <<= 8; \ + out |= ubytes[i] & 0xff; \ + } + +void _dtls_reset_window(struct record_parameters_st *rp) +{ + DTLS_WINDOW_INIT(rp); +} + +/* Checks if a sequence number is not replayed. If a replayed + * packet is detected it returns a negative value (but no sensible error code). + * Otherwise zero. + */ +int _dtls_record_check(struct record_parameters_st *rp, uint64 * _seq) +{ + uint64_t seq_num = 0; + unsigned i; + + LOAD_UINT64(seq_num, _seq->i); + + if ((seq_num >> DTLS_EPOCH_SHIFT) != rp->epoch) { + return gnutls_assert_val(-1); + } + + if (!DTLS_WINDOW_HAVE_RECV_PACKET(rp)) { + DTLS_WINDOW_INIT_AT(rp, seq_num); + rp->dtls_sw_have_recv = 1; + return 0; + } + + /* are we inside sliding window? */ + if (!DTLS_WINDOW_INSIDE(rp, seq_num)) { + return gnutls_assert_val(-2); + } + + /* already received? */ + if (DTLS_WINDOW_RECEIVED(rp, seq_num)) { + return gnutls_assert_val(-3); + } + + DTLS_WINDOW_MARK(rp, seq_num); + DTLS_WINDOW_UPDATE(rp); + + return 0; +} diff --git a/lib/dtls-window.c b/lib/dtls-window.c deleted file mode 100644 index dd0be5d5ae..0000000000 --- a/lib/dtls-window.c +++ /dev/null @@ -1,159 +0,0 @@ -/* - * Copyright (C) 2009-2016 Free Software Foundation, Inc. - * Copyright (C) 2013-2016 Nikos Mavrogiannopoulos - * - * Authors: Jonathan Bastien-Filiatrault - * Nikos Mavrogiannopoulos - * - * This file is part of GNUTLS. - * - * The GNUTLS library is free software; you can redistribute it and/or - * modify it under the terms of the GNU Lesser General Public License - * as published by the Free Software Foundation; either version 2.1 of - * the License, or (at your option) any later version. - * - * This library is distributed in the hope that it will be useful, but - * WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - * Lesser General Public License for more details. - * - * You should have received a copy of the GNU Lesser General Public License - * along with this program. If not, see - * - */ - -/* Functions that relate to DTLS window handling. - */ - -#include "gnutls_int.h" -#include "errors.h" -#include "debug.h" -#include "dtls.h" -#include "record.h" -#include -#include -#include -#include -#include - -#define window_table rp->record_sw -#define window_size rp->record_sw_size -#define window_head_idx rp->record_sw_head_idx - -#define LOAD_UINT48(out, ubytes) \ - for (i = 2; i < 8; i++) { \ - out <<= 8; \ - out |= ubytes[i] & 0xff; \ - } - -void _dtls_reset_window(gnutls_session_t session, uint8_t _seq[8]) -{ - record_parameters_st *rp; - int ret; - unsigned i; - uint64_t seq = 0; - - ret = - _gnutls_epoch_get(session, EPOCH_READ_CURRENT, &rp); - if (ret < 0) - return; - - LOAD_UINT48(seq, _seq); - - if (seq == 0) { - window_size = 0; - window_head_idx = 0; - return; - } - - window_size = 1; - window_head_idx = 0; - window_table[window_head_idx] = seq - 1; -} - -static void slide_window(struct record_parameters_st *rp, - unsigned int places) -{ - unsigned int old_head = window_head_idx; - - if (places < window_size) { - window_head_idx += places; - window_head_idx %= DTLS_RECORD_WINDOW_SIZE; - - window_table[window_head_idx] = - window_table[old_head] + places; - } else { - unsigned int last_idx = - (window_head_idx + window_size - 1) % window_size; - window_table[window_head_idx] = window_table[last_idx]; - } -} - -/* Checks if a sequence number is not replayed. If replayed - * returns a negative error code, otherwise zero. - */ -int _dtls_record_check(struct record_parameters_st *rp, uint64 * _seq) -{ - uint64_t seq = 0, diff; - unsigned int i, offset = 0; - unsigned int last_idx; - - LOAD_UINT48(seq, _seq->i); - - /* only two values allowed in window_size */ - if (window_size == 0) { - window_size = 1; - window_head_idx = 0; - last_idx = window_size - 1; - window_table[last_idx] = window_table[window_head_idx] = - seq; - return 0; - } - - last_idx = (window_head_idx + window_size - 1) % window_size; - - if (seq <= window_table[window_head_idx]) { - return -1; - } - - if (seq <= window_table[last_idx]) { - /* is between first and last */ - diff = window_table[last_idx] - seq; - - if (diff >= window_size) { - return -1; - } - - if (diff > last_idx) { - diff = diff - last_idx; - offset = window_size - 1 - diff; - } else - offset = last_idx - diff; - - if (window_table[offset] == seq) { - return -1; - } else - window_table[offset] = seq; - } else { /* seq > last */ - - diff = seq - window_table[last_idx]; - - if (window_size + diff <= DTLS_RECORD_WINDOW_SIZE) { - window_size += diff; - } else { - if (window_size < DTLS_RECORD_WINDOW_SIZE) { - offset = - DTLS_RECORD_WINDOW_SIZE - window_size; - window_size = DTLS_RECORD_WINDOW_SIZE; - diff -= offset; - } - - /* diff > 0 */ - slide_window(rp, diff); - } - - offset = (window_head_idx + window_size - 1) % window_size; - window_table[offset] = seq; - } - return 0; -} diff --git a/lib/dtls.h b/lib/dtls.h index d5c8e1df88..e49a8a1344 100644 --- a/lib/dtls.h +++ b/lib/dtls.h @@ -32,7 +32,7 @@ int _dtls_transmit(gnutls_session_t session); int _dtls_record_check(struct record_parameters_st *rp, uint64 * _seq); void _dtls_reset_hsk_state(gnutls_session_t session); -void _dtls_reset_window(gnutls_session_t session, uint8_t sequence[8]); +void _dtls_reset_window(struct record_parameters_st *rp); #define MAX_DTLS_TIMEOUT 60000 diff --git a/lib/gnutls_int.h b/lib/gnutls_int.h index 744261ffc2..bb3739c04e 100644 --- a/lib/gnutls_int.h +++ b/lib/gnutls_int.h @@ -1,6 +1,6 @@ /* - * Copyright (C) 2000-2015 Free Software Foundation, Inc. - * Copyright (C) 2015 Red Hat, Inc. + * Copyright (C) 2000-2016 Free Software Foundation, Inc. + * Copyright (C) 2015-2016 Red Hat, Inc. * * Author: Nikos Mavrogiannopoulos * @@ -123,7 +123,6 @@ typedef struct { #define GNUTLS_RANDOM_SIZE 32 /* DTLS */ -#define DTLS_RECORD_WINDOW_SIZE 64 #define DTLS_RETRANS_TIMEOUT 1000 /* TLS Extensions */ @@ -620,10 +619,10 @@ struct record_parameters_st { bool etm; const mac_entry_st *mac; - /* for DTLS */ - uint64_t record_sw[DTLS_RECORD_WINDOW_SIZE]; - unsigned int record_sw_head_idx; - unsigned int record_sw_size; + /* for DTLS sliding window */ + uint64_t dtls_sw_bits; + uint64_t dtls_sw_start; /* The starting point of the sliding window without epoch */ + unsigned dtls_sw_have_recv; /* whether at least a packet has been received */ record_state_st read; record_state_st write; diff --git a/lib/record.c b/lib/record.c index ad60967662..4e462b9eac 100644 --- a/lib/record.c +++ b/lib/record.c @@ -1,6 +1,6 @@ /* - * Copyright (C) 2000-2013 Free Software Foundation, Inc. - * Copyright (C) 2012,2013 Nikos Mavrogiannopoulos + * Copyright (C) 2000-2016 Free Software Foundation, Inc. + * Copyright (C) 2012-2016 Nikos Mavrogiannopoulos * * Author: Nikos Mavrogiannopoulos * @@ -1194,6 +1194,7 @@ _gnutls_recv_in_buffers(gnutls_session_t session, content_type_t type, if (bufel == NULL) return gnutls_assert_val(GNUTLS_E_INTERNAL_ERROR); + /* We allocate the maximum possible to allow few compressed bytes to expand to a * full record. Moreover we add space for any pad and the MAC (in case * they are encrypted). @@ -1229,11 +1230,10 @@ _gnutls_recv_in_buffers(gnutls_session_t session, content_type_t type, goto sanity_check_error; } - /* check for duplicates. We check after the message - * is processed and authenticated to avoid someone - * messing with our windows. - */ if (IS_DTLS(session)) { + /* check for duplicates. We check after the message + * is processed and authenticated to avoid someone + * messing with our windows. */ if (likely(!(session->internals.flags & GNUTLS_NO_REPLAY_PROTECTION))) { ret = _dtls_record_check(record_params, packet_sequence); if (ret < 0) { diff --git a/lib/state.c b/lib/state.c index f96f43319b..b45237680f 100644 --- a/lib/state.c +++ b/lib/state.c @@ -1313,7 +1313,7 @@ gnutls_record_set_state(gnutls_session_t session, memcpy(UINT64DATA(record_state->sequence_number), seq_number, 8); if (IS_DTLS(session)) { - _dtls_reset_window(session, seq_number); + _dtls_reset_window(record_params); } return 0; -- cgit v1.2.1