From 8515bbba069347de07a452586d7e49a2e8bdf151 Mon Sep 17 00:00:00 2001 From: David Llewellyn-Jones Date: Sun, 19 Apr 2020 19:18:30 +0300 Subject: [PATCH] Add initial crypto functionality Adds the functionality from the crypto spec: 1. Generate random Tracing Keys. 2. Generate Daily Tracing Keys. 3. Generate Rolling Proximity Identifiers. 4. Match a list of collected beacons (RPIs) with a list of downloaded diagnosis keys (DTKs). Includes unit tests, but these don't currently use the official test vectors because I don't yet know how I can get hold of them. --- include/contrac/contrac.h | 31 +++ include/contrac/contrac_private.h | 38 ++++ include/contrac/dtk.h | 45 +++++ include/contrac/dtk_list.h | 46 +++++ include/contrac/log.h | 36 ++++ include/contrac/match.h | 52 +++++ include/contrac/rpi.h | 50 +++++ include/contrac/rpi_list.h | 47 +++++ include/contrac/utils.h | 51 +++++ src/Makefile.am | 2 +- src/contrac.c | 174 +++++++++++++++- src/dtk.c | 139 +++++++++++++ src/dtk_list.c | 101 ++++++++++ src/log.c | 52 +++++ src/match.c | 191 ++++++++++++++++++ src/rpi.c | 141 +++++++++++++ src/rpi_list.c | 102 ++++++++++ src/utils.c | 69 +++++++ tests/test_contrac.c | 316 ++++++++++++++++++++++++++++++ 19 files changed, 1676 insertions(+), 7 deletions(-) create mode 100644 include/contrac/contrac_private.h create mode 100644 include/contrac/dtk.h create mode 100644 include/contrac/dtk_list.h create mode 100644 include/contrac/log.h create mode 100644 include/contrac/match.h create mode 100644 include/contrac/rpi.h create mode 100644 include/contrac/rpi_list.h create mode 100644 include/contrac/utils.h create mode 100644 src/dtk.c create mode 100644 src/dtk_list.c create mode 100644 src/log.c create mode 100644 src/match.c create mode 100644 src/rpi.c create mode 100644 src/rpi_list.c create mode 100644 src/utils.c diff --git a/include/contrac/contrac.h b/include/contrac/contrac.h index 48f5e64..9478054 100644 --- a/include/contrac/contrac.h +++ b/include/contrac/contrac.h @@ -17,10 +17,41 @@ #ifndef __CONTRAC_H #define __CONTRAC_H +// Includes + +#include +#include + +// Defines + +// Data sizes in bytes +#define TK_SIZE (32) +#define TK_SIZE_BASE64 (44) + +// Structures + typedef struct _Contrac Contrac; +// Function prototypes + Contrac * contrac_new(); void contrac_delete(Contrac * data); +bool contrac_generate_tracing_key(Contrac * data); +bool contrac_set_day_number(Contrac * data, uint32_t day_number); +bool contrac_set_time_interval_number(Contrac * data, uint8_t time_interval_number); +bool contrac_get_initialised(Contrac const * data); + +const unsigned char * contrac_get_tracing_key(Contrac const * data); +void contrac_get_tracing_key_base64(Contrac const * data, char * base64); + +const unsigned char * contrac_get_daily_key(Contrac const * data); +void contrac_get_daily_key_base64(Contrac const * data, char * base64); + +const unsigned char * contrac_get_proximity_id(Contrac const * data); +void contrac_get_proximity_id_base64(Contrac const * data, char * base64); + +// Function definitions + #endif // __CONTRAC_H diff --git a/include/contrac/contrac_private.h b/include/contrac/contrac_private.h new file mode 100644 index 0000000..68d5aad --- /dev/null +++ b/include/contrac/contrac_private.h @@ -0,0 +1,38 @@ +/** \ingroup contrac + * @file + * @author David Llewellyn-Jones + * @version $(VERSION) + * + * @section LICENSE + * + * + * + * @brief + * @section DESCRIPTION + * + * + * + */ + +#ifndef __CONTRAC_PRIVATE_H +#define __CONTRAC_PRIVATE_H + +// Includes + +#include "contrac/contrac.h" + +// Defines + +// Data sizes in bytes + +// Structures + +// Function prototypes + +void contrac_set_tracing_key(Contrac * data, unsigned char const * tracing_key); +bool contrac_set_tracing_key_base64(Contrac * data, char const * tracing_key); + +// Function definitions + +#endif // __CONTRAC_PRIVATE_H + diff --git a/include/contrac/dtk.h b/include/contrac/dtk.h new file mode 100644 index 0000000..1525ebb --- /dev/null +++ b/include/contrac/dtk.h @@ -0,0 +1,45 @@ +/** \ingroup contrac + * @file + * @author David Llewellyn-Jones + * @version $(VERSION) + * + * @section LICENSE + * + * + * + * @brief + * @section DESCRIPTION + * + * + * + */ + +#ifndef __DTK_H +#define __DTK_H + +// Includes + +// Defines + +#define DTK_SIZE (16) +#define DTK_SIZE_BASE64 (24) + +// Structures + +typedef struct _Dtk Dtk; + +// Function prototypes + +Dtk * dtk_new(); +void dtk_delete(Dtk * data); + +bool contrac_generate_daily_key(Dtk * data, Contrac const * contrac, uint32_t day_number); +const unsigned char * dtk_get_daily_key(Dtk const * data); +uint32_t dtk_get_day_number(Dtk const * data); +void dtk_assign(Dtk * data, unsigned char const * dtk_bytes, uint32_t day_number); + +// Function definitions + +#endif // __DTK_H + + diff --git a/include/contrac/dtk_list.h b/include/contrac/dtk_list.h new file mode 100644 index 0000000..2eacb68 --- /dev/null +++ b/include/contrac/dtk_list.h @@ -0,0 +1,46 @@ +/** \ingroup contrac + * @file + * @author David Llewellyn-Jones + * @version $(VERSION) + * + * @section LICENSE + * + * + * + * @brief + * @section DESCRIPTION + * + * + * + */ + +#ifndef __DTK_LIST_H +#define __DTK_LIST_H + +// Includes + +#include "contrac/contrac.h" +#include "contrac/dtk.h" + +// Defines + +// Structures + +typedef struct _DtkList DtkList; +typedef struct _DtkListItem DtkListItem; + +// Function prototypes + +DtkList * dtk_list_new(); +void dtk_list_delete(DtkList * data); + +void dtk_list_append(DtkList * data, Dtk * dtk); +DtkListItem const * dtk_list_first(DtkList const * data); +DtkListItem const * dtk_list_next(DtkListItem const * data); +Dtk const * dtk_list_get_dtk(DtkListItem const * data); + +// Function definitions + +#endif // __DTK_LIST_H + + diff --git a/include/contrac/log.h b/include/contrac/log.h new file mode 100644 index 0000000..0e7abee --- /dev/null +++ b/include/contrac/log.h @@ -0,0 +1,36 @@ +/** \ingroup contrac + * @file + * @author David Llewellyn-Jones + * @version $(VERSION) + * + * @section LICENSE + * + * + * + * @brief + * @section DESCRIPTION + * + * + * + */ + +#ifndef __LOG_H +#define __LOG_H + +// Includes + +#include + +// Defines + +#define LOG(level, ...) log_priority(level, __VA_ARGS__); + +// Structures + +// Function prototypes + +void log_priority(int priority, const char *format, ...); + +// Function definitions + +#endif // __LOG_H diff --git a/include/contrac/match.h b/include/contrac/match.h new file mode 100644 index 0000000..fe38c74 --- /dev/null +++ b/include/contrac/match.h @@ -0,0 +1,52 @@ +/** \ingroup contrac + * @file + * @author David Llewellyn-Jones + * @version $(VERSION) + * + * @section LICENSE + * + * + * + * @brief + * @section DESCRIPTION + * + * + * + */ + +#ifndef __MATCH_H +#define __MATCH_H + +// Includes + +#include "contrac/contrac.h" +#include "contrac/dtk.h" + +// Defines + +// Structures + +typedef struct _MatchList MatchList; +typedef struct _MatchListItem MatchListItem; + +// Function prototypes + +MatchList * match_list_new(); +void match_list_delete(MatchList * data); + +void match_list_clear(MatchList * data); +size_t match_list_count(MatchList * data); + +uint32_t match_list_get_day_number(MatchListItem const * data); +uint8_t match_list_get_time_interval_number(MatchListItem const * data); + +MatchListItem const * match_list_first(MatchList const * data); +MatchListItem const * match_list_next(MatchListItem const * data); + +void match_list_find_matches(MatchList * data, RpiList * beacons, DtkList * diagnosis_keys); + +// Function definitions + +#endif // __MATCH_H + + diff --git a/include/contrac/rpi.h b/include/contrac/rpi.h new file mode 100644 index 0000000..9da8e62 --- /dev/null +++ b/include/contrac/rpi.h @@ -0,0 +1,50 @@ +/** \ingroup contrac + * @file + * @author David Llewellyn-Jones + * @version $(VERSION) + * + * @section LICENSE + * + * + * + * @brief + * @section DESCRIPTION + * + * + * + */ + +#ifndef __RPI_H +#define __RPI_H + +// Includes + +#include "contrac/contrac.h" +#include "contrac/dtk.h" + +// Defines + +#define RPI_SIZE (16) +#define RPI_INTERVAL_MAX (144) +#define RPI_SIZE_BASE64 (24) + +// Structures + +typedef struct _Rpi Rpi; + +// Function prototypes + +Rpi * rpi_new(); +void rpi_delete(Rpi * data); + +bool rpi_generate_proximity_id(Rpi * data, Dtk const * dtk, uint8_t time_interval_number); +const unsigned char * rpi_get_proximity_id(Rpi const * data); +uint8_t rpi_get_time_interval_number(Rpi const * data); +void rpi_assign(Rpi * data, unsigned char const * rpi_bytes, uint8_t time_interval_number); +bool rpi_compare(Rpi const * data, Rpi const * comparitor); + +// Function definitions + +#endif // __RPI_H + + diff --git a/include/contrac/rpi_list.h b/include/contrac/rpi_list.h new file mode 100644 index 0000000..7814708 --- /dev/null +++ b/include/contrac/rpi_list.h @@ -0,0 +1,47 @@ +/** \ingroup contrac + * @file + * @author David Llewellyn-Jones + * @version $(VERSION) + * + * @section LICENSE + * + * + * + * @brief + * @section DESCRIPTION + * + * + * + */ + +#ifndef __RPI_LIST_H +#define __RPI_LIST_H + +// Includes + +#include "contrac/contrac.h" +#include "contrac/rpi.h" + +// Defines + +// Structures + +typedef struct _RpiList RpiList; +typedef struct _RpiListItem RpiListItem; + +// Function prototypes + +RpiList * rpi_list_new(); +void rpi_list_delete(RpiList * data); + +void rpi_list_append(RpiList * data, Rpi * rpi); + +RpiListItem const * rpi_list_first(RpiList const * data); +RpiListItem const * rpi_list_next(RpiListItem const * data); +Rpi const * rpi_list_get_rpi(RpiListItem const * data); + +// Function definitions + +#endif // __RPI_LIST_H + + diff --git a/include/contrac/utils.h b/include/contrac/utils.h new file mode 100644 index 0000000..38b0c3f --- /dev/null +++ b/include/contrac/utils.h @@ -0,0 +1,51 @@ +/** \ingroup contrac + * @file + * @author David Llewellyn-Jones + * @version $(VERSION) + * + * @section LICENSE + * + * + * + * @brief + * @section DESCRIPTION + * + * + * + */ + + +#ifndef __UTILS_H +#define __UTILS_H + +// Includes + +// Defines + +#define MAX(a,b) \ + ({ __typeof__ (a) _a = (a); \ + __typeof__ (b) _b = (b); \ + _a > _b ? _a : _b; }) + +#define MIN(a,b) \ + ({ __typeof__ (a) _a = (a); \ + __typeof__ (b) _b = (b); \ + _a < _b ? _a : _b; }) + +// Structures + +// Function prototypes + +size_t base64_encode_size(size_t binary_input); +size_t base64_decode_size(size_t base64_input); +void base64_encode_binary_to_base64(unsigned char const *input, size_t input_size, unsigned char *output, size_t *output_size); +void base64_decode_base64_to_binary(unsigned char const *input, size_t input_size, unsigned char *output, size_t *output_size); + +// Function definitions + +#endif // __UTILS_H + + + + + diff --git a/src/Makefile.am b/src/Makefile.am index c21f1a8..739874c 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -1,7 +1,7 @@ lib_LIBRARIES = ../libcontrac.a pkginclude_HEADERS = ../include/contrac/*.h -___libcontrac_a_SOURCES = contrac.c +___libcontrac_a_SOURCES = contrac.c rpi.c log.c utils.c dtk.c rpi_list.c dtk_list.c match.c ___libcontrac_a_CFLAGS = -std=gnu99 -fPIC -Wall -Werror -I"../include" @LIBCONTRAC_CFLAGS@ ARFLAGS = cr AR_FLAGS = cr diff --git a/src/contrac.c b/src/contrac.c index 4c97ae0..47070d3 100644 --- a/src/contrac.c +++ b/src/contrac.c @@ -16,20 +16,42 @@ // Includes -#include #include +#include #include -#include +#include + #include +#include +#include + +#include "contrac/log.h" +#include "contrac/utils.h" +#include "contrac/rpi.h" #include "contrac/contrac.h" // Defines +#define STATUS_TK (1 << 0) +#define STATUS_DTK (1 << 1) +#define STATUS_RPI (1 << 2) + +#define STATUS_INITIALISED (STATUS_TK | STATUS_DTK | STATUS_RPI) // Structures struct _Contrac { - int version; + // Tracing key + unsigned char tk[TK_SIZE]; + // Daily key + Dtk * dtk; + // Rolling proximity identifier + Rpi * rpi; + + uint32_t day_number; + uint8_t time_interval_number; + + uint32_t status; }; // Function prototypes @@ -38,17 +60,157 @@ struct _Contrac { Contrac * contrac_new() { Contrac * data; - + data = calloc(sizeof(Contrac), 1); - data->version = 0; - + data->dtk = dtk_new(); + data->rpi = rpi_new(); + return data; } void contrac_delete(Contrac * data) { if (data) { + dtk_delete(data->dtk); + rpi_delete(data->rpi); + + // Clear the data for security + memset(data, 0, sizeof(Contrac)); + free(data); } } +bool contrac_generate_tracing_key(Contrac * data) { + int result; + + // tk <- CRNG(32) + result = RAND_bytes(data->tk, TK_SIZE); + + if (result == 1) { + data->status |= STATUS_TK; + } + else { + LOG(LOG_ERR, "Error generating tracing key: %lu\n", ERR_get_error()); + } + + return (result == 1); +} + +bool contrac_set_day_number(Contrac * data, uint32_t day_number) { + bool result; + + result = ((data->status & STATUS_TK) != 0); + + if (result) { + result = contrac_generate_daily_key(data->dtk, data, day_number); + } + + if (result) { + data->day_number = day_number; + data->status |= STATUS_DTK; + } + + return result; +} + +bool contrac_set_time_interval_number(Contrac * data, uint8_t time_interval_number) { + bool result; + + result = ((data->status & STATUS_DTK) != 0); + + if (result) { + result = rpi_generate_proximity_id(data->rpi, data->dtk, time_interval_number); + } + + if (result) { + data->time_interval_number = time_interval_number; + data->status |= STATUS_RPI; + } + + return result; +} + +bool contrac_get_initialised(Contrac const * data) { + return ((data->status & STATUS_INITIALISED) == STATUS_INITIALISED); +} + +void contrac_set_tracing_key(Contrac * data, unsigned char const * tracing_key) { + memcpy(data->tk, tracing_key, TK_SIZE); + data->status |= STATUS_TK; +} + +const unsigned char * contrac_get_tracing_key(Contrac const * data) { + return data->tk; +} + +// base64 buffer must be at least 45 bytes (TK_SIZE_BASE64 + 1) +void contrac_get_tracing_key_base64(Contrac const * data, char * base64) { + size_t size = TK_SIZE_BASE64 + 1; + base64_encode_binary_to_base64(data->tk, TK_SIZE, (unsigned char *)base64, &size); + + if (size != (TK_SIZE_BASE64 + 1)) { + LOG(LOG_ERR, "Base64 tracing key has incorrect size of %d bytes.\n", size); + } +} + +// tracing_key input must be 44 bytes long +bool contrac_set_tracing_key_base64(Contrac * data, char const * tracing_key) { + bool result = true; + unsigned char tk[TK_SIZE]; + size_t size; + + if (strlen(tracing_key) != TK_SIZE_BASE64) { + LOG(LOG_ERR, "Base64 tracing key has incorrect size. Should be %d bytes.\n", TK_SIZE_BASE64); + result = false; + } + + if (result) { + size = TK_SIZE; + base64_decode_base64_to_binary((unsigned char *)tracing_key, TK_SIZE_BASE64, tk, &size); + + if (size < TK_SIZE) { + LOG(LOG_ERR, "Base64 tracking key output is too short %d bytes.\n", size); + result = false; + } + } + + if (result) { + contrac_set_tracing_key(data, tk); + } + + return result; +} + +const unsigned char * contrac_get_daily_key(Contrac const * data) { + return dtk_get_daily_key(data->dtk); +} + +// base64 buffer must be at least 25 bytes (DTK_SIZE_BASE64 + 1) +void contrac_get_daily_key_base64(Contrac const * data, char * base64) { + size_t size = DTK_SIZE_BASE64 + 1; + base64_encode_binary_to_base64(dtk_get_daily_key(data->dtk), DTK_SIZE, (unsigned char *)base64, &size); + + if (size != (DTK_SIZE_BASE64 + 1)) { + LOG(LOG_ERR, "Base64 daily key has incorrect size of %d bytes.\n", size); + } +} + +const unsigned char * contrac_get_proximity_id(Contrac const * data) { + return rpi_get_proximity_id(data->rpi); +} + +// base64 buffer must be at least 25 bytes (RPI_SIZE_BASE64 + 1) +void contrac_get_proximity_id_base64(Contrac const * data, char * base64) { + size_t size = RPI_SIZE_BASE64 + 1; + base64_encode_binary_to_base64(rpi_get_proximity_id(data->rpi), RPI_SIZE, (unsigned char *)base64, &size); + + if (size != (RPI_SIZE_BASE64 + 1)) { + LOG(LOG_ERR, "Base64 proximity id has incorrect size of %d bytes.\n", size); + } +} + + + + + diff --git a/src/dtk.c b/src/dtk.c new file mode 100644 index 0000000..3febd9f --- /dev/null +++ b/src/dtk.c @@ -0,0 +1,139 @@ +/** \ingroup contrac + * @file + * @author David Llewellyn-Jones + * @version $(VERSION) + * + * @section LICENSE + * + * + * + * @brief + * @section DESCRIPTION + * + * + * + */ + +// Includes + +#include +#include +#include +#include + +#include +#include +#include +#include + +#include "contrac/contrac.h" +#include "contrac/utils.h" +#include "contrac/log.h" + +#include "contrac/dtk.h" + +// Defines + +#define DTK_INFO_PREFIX "CT-DTK" + +// Structures + +struct _Dtk { + // Daily key + unsigned char dtk[DTK_SIZE]; + uint32_t day_number; +}; + +// Function prototypes + +// Function definitions + +Dtk * dtk_new() { + Dtk * data; + + data = calloc(sizeof(Dtk), 1); + + return data; +} + +void dtk_delete(Dtk * data) { + if (data) { + // Clear the data for security + memset(data, 0, sizeof(Dtk)); + + free(data); + } +} + +bool contrac_generate_daily_key(Dtk * data, Contrac const * contrac, uint32_t day_number) { + int result = 1; + char encode[sizeof(DTK_INFO_PREFIX) + sizeof(day_number)]; + size_t out_length = 0; + EVP_PKEY_CTX *pctx = NULL; + const unsigned char * tk; + + // dtk_i <- HKDF(tk, NULL, (UTF8("CT-DTK") || D_i), 16) + + if (result > 0) { + // Produce Info sequence UTF8("CT-DTK") || D_i) + // From the spec it's not clear whether this is string or byte concatenation. + // Here we use byte, but it might have to be changed + memcpy(encode, DTK_INFO_PREFIX, sizeof(DTK_INFO_PREFIX)); + ((uint32_t *)(encode + sizeof(DTK_INFO_PREFIX)))[0] = day_number; + + pctx = EVP_PKEY_CTX_new_id(EVP_PKEY_HKDF, NULL); + + result = EVP_PKEY_derive_init(pctx); + } + + if (result > 0) { + result = EVP_PKEY_CTX_set_hkdf_md(pctx, EVP_sha256()); + } + + if (result > 0) { + result = EVP_PKEY_CTX_set1_hkdf_salt(pctx, NULL, 4); + } + + if (result > 0) { + tk = contrac_get_tracing_key(contrac); + result = EVP_PKEY_CTX_set1_hkdf_key(pctx, tk, TK_SIZE); + } + + if (result > 0) { + result = EVP_PKEY_CTX_add1_hkdf_info(pctx, encode, sizeof(encode)); + } + + if (result > 0) { + out_length = DTK_SIZE; + result = EVP_PKEY_derive(pctx, data->dtk, &out_length); + } + + if ((result > 0) && (out_length == DTK_SIZE)) { + data->day_number = day_number; + result = 1; + } + + if (result <= 0) { + LOG(LOG_ERR, "Error generating daily key: %lu\n", ERR_get_error()); + } + + // Freeing a NULL value is safe + EVP_PKEY_CTX_free(pctx); + + return (result > 0); +} + +const unsigned char * dtk_get_daily_key(Dtk const * data) { + return data->dtk; +} + +uint32_t dtk_get_day_number(Dtk const * data) { + return data->day_number; +} + +void dtk_assign(Dtk * data, unsigned char const * dtk_bytes, uint32_t day_number) { + memcpy(data->dtk, dtk_bytes, DTK_SIZE); + data->day_number = day_number; +} + + diff --git a/src/dtk_list.c b/src/dtk_list.c new file mode 100644 index 0000000..9ef41f7 --- /dev/null +++ b/src/dtk_list.c @@ -0,0 +1,101 @@ +/** \ingroup contrac + * @file + * @author David Llewellyn-Jones + * @version $(VERSION) + * + * @section LICENSE + * + * + * + * @brief + * @section DESCRIPTION + * + * + * + */ + +// Includes + +#include +#include +#include +#include + +#include "contrac/contrac.h" +#include "contrac/utils.h" +#include "contrac/log.h" + +#include "contrac/dtk_list.h" + +// Defines + +// Structures + +struct _DtkListItem { + Dtk * dtk; + DtkListItem * next; +}; + +struct _DtkList { + DtkListItem * first; + DtkListItem * last; +}; + +// Function prototypes + +// Function definitions + +DtkList * dtk_list_new() { + DtkList * data; + + data = calloc(sizeof(DtkList), 1); + + return data; +} + +void dtk_list_delete(DtkList * data) { + DtkListItem * item; + DtkListItem * next; + + if (data) { + item = data->first; + while (item) { + next = item->next; + dtk_delete(item->dtk); + free(item); + item = next; + } + + free(data); + } +} + +void dtk_list_append(DtkList * data, Dtk * dtk) { + DtkListItem * item; + + item = calloc(sizeof(DtkListItem), 1); + item->dtk = dtk; + + if (data->last == NULL) { + data->first = item; + data->last = item; + } + else { + data->last->next = item; + data->last = item; + } +} + +DtkListItem const * dtk_list_first(DtkList const * data) { + return data->first; +} + +DtkListItem const * dtk_list_next(DtkListItem const * data) { + return data->next; +} + +Dtk const * dtk_list_get_dtk(DtkListItem const * data) { + return data->dtk; +} + + diff --git a/src/log.c b/src/log.c new file mode 100644 index 0000000..599b945 --- /dev/null +++ b/src/log.c @@ -0,0 +1,52 @@ +/** \ingroup contrac + * @file + * @author David Llewellyn-Jones + * @version $(VERSION) + * + * @section LICENSE + * + * + * + * @brief + * @section DESCRIPTION + * + * + * + */ + +// Includes + +#include +#include +#include +#include + +#include "contrac/log.h" + +// Defines + +// Structures + +// Function prototypes + +void log_priority(int priority, const char *format, ...) { + va_list args; + int length; + char *buffer; + + va_start(args, format); + length = vsnprintf(NULL, 0, format, args); + va_end(args); + + buffer = malloc(sizeof(char) * (length + 1)); + + va_start(args, format); + length = vsnprintf(buffer, length + 1, format, args); + va_end(args); + buffer[length] = 0; + + syslog(priority, "%s", buffer); +} + +// Function definitions + diff --git a/src/match.c b/src/match.c new file mode 100644 index 0000000..c65da52 --- /dev/null +++ b/src/match.c @@ -0,0 +1,191 @@ +/** \ingroup contrac + * @file + * @author David Llewellyn-Jones + * @version $(VERSION) + * + * @section LICENSE + * + * + * + * @brief + * @section DESCRIPTION + * + * + * + */ + +// Includes + +#include +#include +#include +#include + +#include +#include +#include + +#include "contrac/contrac.h" +#include "contrac/utils.h" +#include "contrac/log.h" +#include "contrac/rpi_list.h" +#include "contrac/dtk_list.h" + +#include "contrac/match.h" + +// Defines + +// Structures + +struct _MatchListItem { + uint32_t day_number; + uint8_t time_interval_number; + + MatchListItem * next; +}; + +struct _MatchList { + size_t count; + MatchListItem * first; + MatchListItem * last; +}; + +// Function prototypes + +MatchListItem * match_list_item_new(); +void match_list_item_delete(MatchListItem * data); +void match_list_append(MatchList * data, MatchListItem * item); + +// Function definitions + +MatchList * match_list_new() { + MatchList * data; + + data = calloc(sizeof(MatchList), 1); + + return data; +} + +void match_list_delete(MatchList * data) { + if (data) { + match_list_clear(data); + + free(data); + } +} + +MatchListItem * match_list_item_new() { + MatchListItem * data; + + data = calloc(sizeof(MatchListItem), 1); + + return data; +} + +void match_list_item_delete(MatchListItem * data) { + if (data) { + free(data); + } +} + +void match_list_clear(MatchList * data) { + MatchListItem * item; + MatchListItem * next; + + item = data->first; + while (item) { + next = item->next; + match_list_item_delete(item); + item = next; + } + + data->first = NULL; + data->last = NULL; + data->count = 0; +} + +size_t match_list_count(MatchList * data) { + return data->count; +} + +MatchListItem const * match_list_first(MatchList const * data) { + return data->first; +} + +MatchListItem const * match_list_next(MatchListItem const * data) { + return data->next; +} + + +uint32_t match_list_get_day_number(MatchListItem const * data) { + return data->day_number; +} + +uint8_t match_list_get_time_interval_number(MatchListItem const * data) { + return data->time_interval_number; +} + +void match_list_append(MatchList * data, MatchListItem * item) { + if (data->last == NULL) { + data->first = item; + data->last = item; + } + else { + data->last->next = item; + data->last = item; + } + data->count++; +} + +void match_list_find_matches(MatchList * data, RpiList * beacons, DtkList * diagnosis_keys) { + // For each diagnosis key, generate the RPIs and compare them against the captured RPI beacons + DtkListItem const * dtk_item; + RpiListItem const * rpi_item; + uint8_t interval; + bool result; + Rpi * generated; + MatchListItem * match; + Dtk const * diagnosis_key; + Rpi const * rpi; + + dtk_item = dtk_list_first(diagnosis_keys); + generated = rpi_new(); + + while (dtk_item != NULL) { + diagnosis_key = dtk_list_get_dtk(dtk_item); + // Generate all possible RPIs for this dtk and compare agsinst the beacons + for (interval = 0; interval < RPI_INTERVAL_MAX; ++interval) { + result = rpi_generate_proximity_id(generated, diagnosis_key, interval); + if (result) { + // Check against all beacons + rpi_item = rpi_list_first(beacons); + while (rpi_item != NULL) { + rpi = rpi_list_get_rpi(rpi_item); + result = rpi_compare(rpi, generated); + + if (result) { + if (interval != rpi_get_time_interval_number(rpi)) { + result = false; + LOG(LOG_DEBUG, "Matched beacons don't match intervals\n"); + } + } + + if (result) { + match = match_list_item_new(); + match->day_number = dtk_get_day_number(diagnosis_key); + match->time_interval_number = interval; + match_list_append(data, match); + } + + rpi_item = rpi_list_next(rpi_item); + } + } + } + + dtk_item = dtk_list_next(dtk_item); + } + + rpi_delete(generated); +} + + diff --git a/src/rpi.c b/src/rpi.c new file mode 100644 index 0000000..7523ba4 --- /dev/null +++ b/src/rpi.c @@ -0,0 +1,141 @@ +/** \ingroup contrac + * @file + * @author David Llewellyn-Jones + * @version $(VERSION) + * + * @section LICENSE + * + * + * + * @brief + * @section DESCRIPTION + * + * + * + */ + +// Includes + +#include +#include +#include +#include + +#include +#include +#include + +#include "contrac/contrac.h" +#include "contrac/utils.h" +#include "contrac/log.h" + +#include "contrac/rpi.h" + +// Defines + +#define RPI_INFO_PREFIX "CT-RPI" + +// Structures + +struct _Rpi { + // Rolling proximity identifier + unsigned char rpi[RPI_SIZE]; + uint8_t time_interval_number; +}; + +// Function prototypes + +// Function definitions + +Rpi * rpi_new() { + Rpi * data; + + data = calloc(sizeof(Rpi), 1); + + return data; +} + +void rpi_delete(Rpi * data) { + if (data) { + // Clear the data for security + memset(data, 0, sizeof(Rpi)); + + free(data); + } +} + +bool rpi_generate_proximity_id(Rpi * data, Dtk const * dtk, uint8_t time_interval_number) { + int result = 1; + unsigned char encode[sizeof(RPI_INFO_PREFIX) + sizeof(uint16_t)]; + unsigned char output[EVP_MAX_MD_SIZE]; + unsigned int out_length = 0; + unsigned int pos; + unsigned int min; + unsigned char const * daily_key; + + // RPI_{i, j} <- Truncate(HMAC(dkt_i, (UTF8("CT-RPI") || TIN_j)), 16) + + if (result > 0) { + // Produce Info sequence UTF8("CT-DTK") || D_i) + // From the spec it's not clear whether this is string or byte concatenation. + // Here we use byte, but it might have to be changed + memcpy(encode, RPI_INFO_PREFIX, sizeof(RPI_INFO_PREFIX)); + ((uint8_t *)(encode + sizeof(RPI_INFO_PREFIX)))[0] = time_interval_number; + out_length = sizeof(output); + + daily_key = dtk_get_daily_key(dtk); + HMAC(EVP_sha256(), daily_key, DTK_SIZE, encode, sizeof(encode), output, &out_length); + + _Static_assert ((EVP_MAX_MD_SIZE >= 16), "HMAC buffer size too small"); + + // Truncate and copy the result + min = MIN(out_length, 16); + for (pos = 0; pos < min; ++pos) { + data->rpi[pos] = output[pos]; + } + // Zero out padding if there is any + for (pos = min; pos < 16; ++pos) { + data->rpi[pos] = 0; + } + } + + if (result > 0) { + data->time_interval_number = time_interval_number; + } + + if (result <= 0) { + LOG(LOG_ERR, "Error generating rolling proximity id: %lu\n", ERR_get_error()); + } + + return (result > 0); +} + +const unsigned char * rpi_get_proximity_id(Rpi const * data) { + return data->rpi; +} + +uint8_t rpi_get_time_interval_number(Rpi const * data) { + return data->time_interval_number; +} + + +void rpi_assign(Rpi * data, unsigned char const * rpi_bytes, uint8_t time_interval_number) { + memcpy(data->rpi, rpi_bytes, RPI_SIZE); + data->time_interval_number = time_interval_number; +} + +bool rpi_compare(Rpi const * data, Rpi const * comparitor) { + unsigned char left[RPI_SIZE_BASE64 + 1]; + unsigned char right[RPI_SIZE_BASE64 + 1]; + size_t size; + + size = RPI_SIZE_BASE64 + 1; + base64_encode_binary_to_base64(data->rpi, RPI_SIZE, left, &size); + + size = RPI_SIZE_BASE64 + 1; + base64_encode_binary_to_base64(comparitor->rpi, RPI_SIZE, right, &size); + + return (memcmp(data, comparitor, RPI_SIZE) == 0); +} + + diff --git a/src/rpi_list.c b/src/rpi_list.c new file mode 100644 index 0000000..fb482ba --- /dev/null +++ b/src/rpi_list.c @@ -0,0 +1,102 @@ +/** \ingroup contrac + * @file + * @author David Llewellyn-Jones + * @version $(VERSION) + * + * @section LICENSE + * + * + * + * @brief + * @section DESCRIPTION + * + * + * + */ + +// Includes + +#include +#include +#include +#include + +#include "contrac/contrac.h" +#include "contrac/utils.h" +#include "contrac/log.h" +#include "contrac/dtk_list.h" + +#include "contrac/rpi_list.h" + +// Defines + +// Structures + +struct _RpiListItem { + Rpi * rpi; + RpiListItem * next; +}; + +struct _RpiList { + RpiListItem * first; + RpiListItem * last; +}; + +// Function prototypes + +// Function definitions + +RpiList * rpi_list_new() { + RpiList * data; + + data = calloc(sizeof(RpiList), 1); + + return data; +} + +void rpi_list_delete(RpiList * data) { + RpiListItem * item; + RpiListItem * next; + + if (data) { + item = data->first; + while (item) { + next = item->next; + rpi_delete(item->rpi); + free(item); + item = next; + } + + free(data); + } +} + +void rpi_list_append(RpiList * data, Rpi * rpi) { + RpiListItem * item; + + item = calloc(sizeof(RpiListItem), 1); + item->rpi = rpi; + + if (data->last == NULL) { + data->first = item; + data->last = item; + } + else { + data->last->next = item; + data->last = item; + } +} + +RpiListItem const * rpi_list_first(RpiList const * data) { + return data->first; +} + +RpiListItem const * rpi_list_next(RpiListItem const * data) { + return data->next; +} + +Rpi const * rpi_list_get_rpi(RpiListItem const * data) { + return data->rpi; +} + + diff --git a/src/utils.c b/src/utils.c new file mode 100644 index 0000000..1fbb716 --- /dev/null +++ b/src/utils.c @@ -0,0 +1,69 @@ +/** \ingroup contrac + * @file + * @author David Llewellyn-Jones + * @version $(VERSION) + * + * @section LICENSE + * + * + * + * @brief + * @section DESCRIPTION + * + * + * + */ + +// Includes + +#include + +// Defines + +// Structures + +// Function prototypes + +// Function definitions + +// Function definitions + +size_t base64_encode_size(size_t binary_input) { + return (((size_t)((binary_input + 2) / 3)) * 4) + 1; +} + +size_t base64_decode_size(size_t base64_input) { + return (((size_t)((base64_input + 3) / 4)) * 3) + 1; +} + +void base64_encode_binary_to_base64(unsigned char const *input, size_t input_size, unsigned char *output, size_t *output_size) { + size_t size_in; + size_t size_out; + + size_in = input_size; + size_out = base64_encode_size(input_size); + + if (size_out > *output_size) { + size_in = base64_decode_size(*output_size - 1) - 1; + } + *output_size = base64_encode_size(size_in); + + EVP_EncodeBlock(output, input, size_in); +} + +void base64_decode_base64_to_binary(unsigned char const *input, size_t input_size, unsigned char *output, size_t *output_size) { + size_t size_in; + size_t size_out; + + size_in = input_size; + size_out = base64_decode_size(input_size); + + if (size_out > *output_size) { + size_in = base64_encode_size(*output_size - 1) - 1; + } + *output_size = base64_decode_size(size_in); + + EVP_DecodeBlock(output, input, size_in); +} + + diff --git a/tests/test_contrac.c b/tests/test_contrac.c index aa81384..ffa09c1 100644 --- a/tests/test_contrac.c +++ b/tests/test_contrac.c @@ -17,8 +17,16 @@ // Includes #include +#include #include "contrac/contrac.h" +#include "contrac/contrac_private.h" +#include "contrac/utils.h" +#include "contrac/dtk.h" +#include "contrac/rpi.h" +#include "contrac/dtk_list.h" +#include "contrac/rpi_list.h" +#include "contrac/match.h" // Defines @@ -28,8 +36,312 @@ // Function definitions +START_TEST (check_base64) { + //bool result; + //int pos; + char *string[4] = { + "This is a string", // 16 + "Maybe upon a time", // 17 + "And then there was", // 18 + "In the end there is", // 19 + }; + char *base64[4] = { + "VGhpcyBpcyBhIHN0cmluZw==", // 24 + "TWF5YmUgdXBvbiBhIHRpbWU=", // 24 + "QW5kIHRoZW4gdGhlcmUgd2Fz", // 24 + "SW4gdGhlIGVuZCB0aGVyZSBpcw==", // 24 + }; + size_t size; + char * output; + int pos; + + for (pos = 0; pos < 4; ++pos) { + // Encode + size = base64_encode_size(strlen(string[pos])); + + ck_assert(size == (strlen(base64[pos]) + 1)); + output = calloc(sizeof(char), size); + + base64_encode_binary_to_base64((unsigned char *)string[pos], strlen(string[pos]), (unsigned char *)output, &size); + + ck_assert(size == (strlen(base64[pos]) + 1)); + ck_assert_str_eq(output, base64[pos]); + + // Decode + size = base64_decode_size(strlen(base64[pos])); + + ck_assert(size >= (strlen(string[pos]) + 1)); + ck_assert(size < (strlen(string[pos]) + 4)); + output = calloc(sizeof(char), size + 1); + + base64_decode_base64_to_binary((unsigned char *)base64[pos], strlen(base64[pos]), (unsigned char *)output, &size); + + ck_assert(size >= (strlen(string[pos]) + 1)); + ck_assert(size < (strlen(string[pos]) + 4)); + ck_assert_str_eq(output, string[pos]); + } +} +END_TEST + START_TEST (check_contrac) { + bool result; + unsigned char const *tk; + int pos; + + // Generate some keys, check the results + Contrac * contrac; + + contrac = contrac_new(); + ck_assert(contrac != NULL); + + result = contrac_get_initialised(contrac); + ck_assert(result == false); + + tk = contrac_get_tracing_key(contrac); + // The tracing key will initialise to zero by default + for (pos = 0; pos < TK_SIZE; ++pos) { + ck_assert(tk[pos] == 0); + } + + result = contrac_generate_tracing_key(contrac); + ck_assert(result == true); + + result = contrac_get_initialised(contrac); + ck_assert(result == false); + + // The random generator could generate all zeros, but we'll take the risk + tk = contrac_get_tracing_key(contrac); + result = false; + for (pos = 0; pos < TK_SIZE; ++pos) { + if (tk[pos] != 0) { + result = true; + } + } + ck_assert(result == true); + + result = contrac_get_initialised(contrac); + ck_assert(result == false); + + result = contrac_set_day_number(contrac, 23); + ck_assert(result == true); + + result = contrac_get_initialised(contrac); + ck_assert(result == false); + + result = contrac_set_time_interval_number(contrac, 76); + ck_assert(result == true); + + result = contrac_get_initialised(contrac); + ck_assert(result == true); + + // Clean up + contrac_delete(contrac); +} +END_TEST + +START_TEST (check_dtk) { + bool result; + char const *tracing_key_base64 = "3UmKrtcQ2tfLE8UPSXHb4PtgRfE0E2xdSs+PGVIS8cc="; + char tk_base64[TK_SIZE_BASE64 + 1]; + char dtk_base64[DTK_SIZE_BASE64 + 1]; + + // Generate some keys, check the results + Contrac * contrac; + + contrac = contrac_new(); + ck_assert(contrac != NULL); + + contrac_set_tracing_key_base64(contrac, tracing_key_base64); + + contrac_get_tracing_key_base64(contrac, tk_base64); + ck_assert_int_eq(strlen(tk_base64), TK_SIZE_BASE64); + ck_assert_str_eq(tracing_key_base64, tk_base64); + + // Check the Daily Tracing Keys are generated correctly + // Should use the standard test vectors when they're available + + result = contrac_set_day_number(contrac, 12); + ck_assert(result); + contrac_get_daily_key_base64(contrac, dtk_base64); + ck_assert_int_eq(strlen(dtk_base64), DTK_SIZE_BASE64); + ck_assert_str_eq(dtk_base64, "AzZ389DsGecAjZqby1sLNQ=="); + + + result = contrac_set_day_number(contrac, 0); + ck_assert(result); + contrac_get_daily_key_base64(contrac, dtk_base64); + ck_assert_int_eq(strlen(dtk_base64), DTK_SIZE_BASE64); + ck_assert_str_eq(dtk_base64, "p7LrsTReTw3k721eIWDjRw=="); + + result = contrac_set_day_number(contrac, 143); + ck_assert(result); + contrac_get_daily_key_base64(contrac, dtk_base64); + ck_assert_int_eq(strlen(dtk_base64), DTK_SIZE_BASE64); + ck_assert_str_eq(dtk_base64, "f6RZL/2wGCzxSBzZc9xVNQ=="); + + // Clean up + contrac_delete(contrac); +} +END_TEST + +START_TEST (check_rpi) { + bool result; + char const *tracing_key_base64[2] = { + "3UmKrtcQ2tfLE8UPSXHb4PtgRfE0E2xdSs+PGVIS8cc=", + "U3CgpSjF0qFW8DNSTHVWF99few5FOW7RV7kA9j6LFTc=", + }; + char rpi_base64[RPI_SIZE_BASE64 + 1]; + + // Generate some keys, check the results + Contrac * contrac; + + contrac = contrac_new(); + ck_assert(contrac != NULL); + + contrac_set_tracing_key_base64(contrac, tracing_key_base64[0]); + + result = contrac_set_day_number(contrac, 9); + ck_assert(result); + + // Check the Rolling Proximity Identifiers are generated correctly + // Should use the standard test vectors when they're available + + result = contrac_set_time_interval_number(contrac, 0); + ck_assert(result); + contrac_get_proximity_id_base64(contrac, rpi_base64); + ck_assert_int_eq(strlen(rpi_base64), RPI_SIZE_BASE64); + ck_assert_str_eq(rpi_base64, "++ucH9hoIkGwCzM+J09faQ=="); + + result = contrac_set_time_interval_number(contrac, 82); + ck_assert(result); + contrac_get_proximity_id_base64(contrac, rpi_base64); + ck_assert_int_eq(strlen(rpi_base64), RPI_SIZE_BASE64); + ck_assert_str_eq(rpi_base64, "GrqeroryZQ+Uvhx10zfKWw=="); + + result = contrac_set_time_interval_number(contrac, 143); + ck_assert(result); + contrac_get_proximity_id_base64(contrac, rpi_base64); + ck_assert_int_eq(strlen(rpi_base64), RPI_SIZE_BASE64); + ck_assert_str_eq(rpi_base64, "+9eL1UlYZ9buUCFF5qRDUA=="); + + contrac_set_tracing_key_base64(contrac, tracing_key_base64[1]); + + result = contrac_set_day_number(contrac, 500); + ck_assert(result); + + result = contrac_set_time_interval_number(contrac, 1); + ck_assert(result); + contrac_get_proximity_id_base64(contrac, rpi_base64); + ck_assert_int_eq(strlen(rpi_base64), RPI_SIZE_BASE64); + ck_assert_str_eq(rpi_base64, "XmePWi0HlgHyBcVUb0KhjQ=="); + + result = contrac_set_time_interval_number(contrac, 27); + ck_assert(result); + contrac_get_proximity_id_base64(contrac, rpi_base64); + ck_assert_int_eq(strlen(rpi_base64), RPI_SIZE_BASE64); + ck_assert_str_eq(rpi_base64, "LlPznz6D044ZKYsY3sHJew=="); + + result = contrac_set_time_interval_number(contrac, 143); + ck_assert(result); + contrac_get_proximity_id_base64(contrac, rpi_base64); + ck_assert_int_eq(strlen(rpi_base64), RPI_SIZE_BASE64); + ck_assert_str_eq(rpi_base64, "QDG50cy9NTXZ3zDAUGkePQ=="); + + // Clean up + contrac_delete(contrac); +} +END_TEST + +START_TEST (check_match) { + bool result; + char const *tracing_key_base64 = "3UmKrtcQ2tfLE8UPSXHb4PtgRfE0E2xdSs+PGVIS8cc="; + RpiList * beacon_list; + DtkList * diagnosis_list; + // There are four matches in amongst this lot + // (day, time) = (12, 15), (1175, 142), (1175, 67), (12, 93) + uint32_t beacon_days[8] = {55, 12, 0, 8787, 1175, 1175, 187, 12}; + uint8_t beacon_times[8] = {1, 15, 5, 101, 142, 67, 51, 93}; + uint32_t diagnosis_days[2] = {1175, 12}; + // Summarise the four matches + uint32_t match_days[4] = {12, 1175, 1175, 12}; + uint8_t match_times[4] = {15, 142, 67, 93}; + int pos; + const unsigned char * rpi_bytes; + const unsigned char * dtk_bytes; + Rpi * rpi; + Dtk * dtk; + MatchList * matches; + MatchListItem const * match; + int match_count; + + // Generate some keys, check the results + Contrac * contrac; + + contrac = contrac_new(); + ck_assert(contrac != NULL); + + contrac_set_tracing_key_base64(contrac, tracing_key_base64); + + // Generate some beacons (as if collected over BlueTooth) + + beacon_list = rpi_list_new(); + + for (pos = 0; pos < 8; ++pos) { + result = contrac_set_day_number(contrac, beacon_days[pos]); + ck_assert(result); + + result = contrac_set_time_interval_number(contrac, beacon_times[pos]); + ck_assert(result); + + rpi_bytes = contrac_get_proximity_id(contrac); + rpi = rpi_new(); + rpi_assign(rpi, rpi_bytes, beacon_times[pos]); + + rpi_list_append(beacon_list, rpi); + } + + // Generate some diagnosis data (as if provided by a diagnosis server) + + diagnosis_list = dtk_list_new(); + for (pos = 0; pos < 2; ++pos) { + result = contrac_set_day_number(contrac, diagnosis_days[pos]); + ck_assert(result); + + dtk_bytes = contrac_get_daily_key(contrac); + dtk = dtk_new(); + dtk_assign(dtk, dtk_bytes, diagnosis_days[pos]); + + dtk_list_append(diagnosis_list, dtk); + } + + // Check that the matching algorithm identifies the beacons that match + + matches = match_list_new(); + match_list_find_matches(matches, beacon_list, diagnosis_list); + + match = match_list_first(matches); + + match_count = 0; + while (match) { + result = false; + for (pos = 0; pos < 4; ++pos) { + if ((match_list_get_day_number(match) == match_days[pos]) && (match_list_get_time_interval_number(match) == match_times[pos])) { + result = true; + } + } + + ck_assert(result); + + match_count++; + match = match_list_next(match); + } + ck_assert_int_eq(match_count, 4); + // Clean up + match_list_delete(matches); + rpi_list_delete(beacon_list); + dtk_list_delete(diagnosis_list); + contrac_delete(contrac); } END_TEST @@ -42,7 +354,11 @@ int main(void) { s = suite_create("libcontrac"); tc = tcase_create("Contrac"); + tcase_add_test(tc, check_base64); tcase_add_test(tc, check_contrac); + tcase_add_test(tc, check_dtk); + tcase_add_test(tc, check_rpi); + tcase_add_test(tc, check_match); suite_add_tcase(s, tc); sr = srunner_create(s); -- 2.25.1