On Thu, Nov 29, 2018 at 8:37 AM Christof Schulze
<[email protected]> wrote:
>
> On Wed, Nov 28, 2018 at 10:28:50PM -0800, Dave Taht wrote:
> >Dave Taht <[email protected]> writes:
> >
> >> Juliusz Chroboczek <[email protected]> writes:
>
> >>>> Why not? If it's not MTI you risk the case where you get to pick between
> >>>> "good performance on weak devices" and "interoperability with RFC-only
> >>>> implementations".
>
> >>> Is there any evidence that there are devices that can reasonably run Babel
> >>> and that are too weak to use SHA256 for protecting control traffic?
>
> >>> I don't have an ARM device handy right now, but a 450MHz MIPS 24Kc is able
> >>> to SHA256 on the order of 16MB/s. That's 10000 full-size frames per
> >>> second,
> >>> or on the order of 600000 Babel updates per second.
> >
> >I've been meaning to poke into this a while:
> >
> >https://code.fb.com/connectivity/open-r-open-routing-for-modern-networks/
> >
> >But I do take your point. It would be good to know that on a given
> >10,000 route 200 router babel network that hashing overhead accounted
> >for .0X% of the 100% of cpu in use.
> As it is we are having trouble to achieve that figure even without
> hashing. Doesn't this mean this should be priority?
Heh. You spotted the cynicism. :)
The two goals are kind of congruent in the long term. Picking a good,
fast hash function for auth, and then possibly re-using the heck out
of it elsewhere in babel's hash tables if it's fast enough. [1] If it
lives in icache/dcache, it stays fast. [2]
Recently I stumbled across this paper:
https://arxiv.org/pdf/0903.0391.pdf
Skip all the math and go to fig 5. the world is full of algorithms
that have great averages but really pathological behavior on the
outliers - including most hash table designs I've seen. This one,
doesn't. (or at least, claims to) Constant worst case times are
something that fill me with joy, I'm perpetually worrying about my
"go" driven steering wheel controller going into garbage collection at
precisely the wrong time.
He goes into more detail in his thesis:
https://sites.google.com/site/yuriyarbitman/Home/de-amortizedcuckoohashing
as for - as best as I can tell - nobody's yet looked at the typical
distribution of source specific ipv6 addresses. Ipv6 is weird, lots of
0 bits..
https://softwareengineering.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed
And for all I know I'm overthinking it... (but I like pretty pictures
like the above, and really want to dump the BGP route table into
it)... as a constant reminder to myself to stop doing assembly
language optimizations, I got myself the following poster for
christmas:
http://bigocheatsheet.com/
Anyway, attached is a *broken*, 2AM, 40 minutes attempt at tossing
blake into the hmac-challenge branch. To use, apply the patch, and do
a
git submodule add https://github.com/BLAKE2/BLAKE2.git
then a make, then add
key id key1 type blake2s value deadbeefdeadbeefdeadbeefdeadbeefdeadbeef
default enable-timestamps true unicast true hmac key1 # unicast false hmac key1
It briefly will swap routes, and then crash. I didn't quite "get" how
to specify key length right or digest size, my principal purpose was
to find something small (it is) and cross compilable (it does). Or
for all I know I have another bug elsewhere. I don't have time to get
back to it this week.
it adds a mere 4k to the binary.
[1] things like spookyhash seem faster but perhaps not good enough for
that cuckoo hash method
[2] this is one of lua's performance secrets
>
> viele Grüße
>
> Christof
>
> >
> >You are reasonable to assume that sha256 would be low overhead relative
> >to other factors, I think. Still, would like to go measure.
> >
> >Aside: Where does the 300ms figure for re-attempting a challenge and
> >response come from?
> >
> >
> >_______________________________________________
> >Babel-users mailing list
> >[email protected]
> >https://alioth-lists.debian.net/cgi-bin/mailman/listinfo/babel-users
>
> --
> () ascii ribbon campaign - against html e-mail
> /\ against proprietary attachments
>
> _______________________________________________
> Babel-users mailing list
> [email protected]
> https://alioth-lists.debian.net/cgi-bin/mailman/listinfo/babel-users--
Dave Täht
CTO, TekLibre, LLC
http://www.teklibre.com
Tel: 1-831-205-9740
diff --git a/BLAKE2 b/BLAKE2
--- a/BLAKE2
+++ b/BLAKE2
@@ -1 +1 @@
-Subproject commit 320c325437539ae91091ce62efec1913cd8093c2
+Subproject commit 320c325437539ae91091ce62efec1913cd8093c2-dirty
diff --git a/Makefile b/Makefile
index 0003bf0..d7ae6c5 100644
--- a/Makefile
+++ b/Makefile
@@ -1,22 +1,27 @@
PREFIX = /usr/local
MANDIR = $(PREFIX)/share/man
-CDEBUGFLAGS = -Os -g -Wall
+CDEBUGFLAGS = -Os -g -Wall -DHAVE_BLAKE2S
DEFINES = $(PLATFORM_DEFINES)
CFLAGS = $(CDEBUGFLAGS) $(DEFINES) $(EXTRA_DEFINES)
-LDLIBS = -lrt -lcrypto -lssl
+LDLIBS =
SRCS = babeld.c net.c kernel.c util.c interface.c source.c neighbour.c \
route.c xroute.c message.c hmac.c resend.c configuration.c \
- local.c disambiguation.c rule.c
+ local.c disambiguation.c rule.c
OBJS = babeld.o net.o kernel.o util.o interface.o source.o neighbour.o \
route.o xroute.o message.o hmac.o resend.o configuration.o \
local.o disambiguation.o rule.o
+BLAKESRC = BLAKE2/ref/blake2s-ref.c
+BLAKEOBJ = blake2s.o
+
+OBJS += $(BLAKEOBJ)
+
babeld: $(OBJS)
$(CC) $(CFLAGS) $(LDFLAGS) -o babeld $(OBJS) $(LDLIBS)
@@ -26,6 +31,9 @@ local.o: local.c version.h
kernel.o: kernel_netlink.c kernel_socket.c
+$(BLAKEOBJ): $(BLAKESRC)
+ $(CC) $(CFLAGS) $(BLAKESRC) -c -o $(BLAKEOBJ)
+
version.h:
./generate-version.sh > version.h
diff --git a/configuration.c b/configuration.c
index 1d92172..2db1bab 100644
--- a/configuration.c
+++ b/configuration.c
@@ -745,10 +745,10 @@ parse_key(int c, gnc_t gnc, void *closure, struct key **key_return)
goto error;
if(strcmp(auth_type, "none") == 0) {
key->type = AUTH_TYPE_NONE;
- } else if(strcmp(auth_type, "sha1") == 0) {
- key->type = AUTH_TYPE_SHA1;
- } else if(strcmp(auth_type, "ripemd") == 0) {
- key->type = AUTH_TYPE_RIPEMD;
+ } else if(strcmp(auth_type, "sha256") == 0) {
+ key->type = AUTH_TYPE_SHA256;
+ } else if(strcmp(auth_type, "blake2s") == 0) {
+ key->type = AUTH_TYPE_BLAKE2S;
} else {
key->type = 0;
free(auth_type);
@@ -1189,10 +1189,11 @@ parse_config_line(int c, gnc_t gnc, void *closure,
if(key->id == NULL)
goto fail;
switch(key->type) {
- case AUTH_TYPE_SHA1:
- case AUTH_TYPE_RIPEMD:
+ case AUTH_TYPE_SHA256:
+ case AUTH_TYPE_BLAKE2S:
if(key->len != 20) {
- free(key);
+ fprintf(stderr,"Wrong size key\n");
+ free(key);
goto fail;
}
break;
diff --git a/configuration.h b/configuration.h
index f949e53..3454df0 100644
--- a/configuration.h
+++ b/configuration.h
@@ -30,8 +30,8 @@ THE SOFTWARE.
#define CONFIG_ACTION_NO 5
#define AUTH_TYPE_NONE 0
-#define AUTH_TYPE_SHA1 1
-#define AUTH_TYPE_RIPEMD 2
+#define AUTH_TYPE_SHA256 1
+#define AUTH_TYPE_BLAKE2S 2
struct filter_result {
unsigned int add_metric; /* allow = 0, deny = INF, metric = <0..INF> */
diff --git a/hmac.c b/hmac.c
index 51156de..e19a080 100644
--- a/hmac.c
+++ b/hmac.c
@@ -36,6 +36,10 @@ THE SOFTWARE.
#include "configuration.h"
#include "message.h"
+#ifdef HAVE_BLAKE2S
+#include "BLAKE2/ref/blake2.h"
+#endif
+
struct key **keys = NULL;
int numkeys = 0, maxkeys = 0;
@@ -111,14 +115,46 @@ add_key(char *id, int type, int len, unsigned char *value)
}
static int
-compute_hmac(const unsigned char *src, const unsigned char *dst,
+compute_hmac_blake2s(struct key *key, const unsigned char *src, const unsigned char *dst,
unsigned char *packet_header, unsigned char *hmac,
- const unsigned char *body, int bodylen, struct key *key)
+ const unsigned char *body, int bodylen)
+{
+#ifndef HAVE_BLAKE2S
+ return -1;
+#else
+ blake2s_state S;
+ unsigned short port;
+ int err;
+ int i;
+ DO_HTONS(&port, (unsigned short)protocol_port);
+ if ((err = blake2s_init_key(&S, DIGEST_LEN, key->value, DIGEST_LEN)) < 0) goto fail;
+ /* Hash the pseudo header. */
+ if ((err = blake2s_update(&S, src, 16)) < 0) goto fail;
+ if ((err = blake2s_update(&S, &port, 2)) < 0) goto fail;
+ if ((err = blake2s_update(&S, dst, 16)) < 0) goto fail;
+ if ((err = blake2s_update(&S, &port, 2)) < 0) goto fail;
+
+ if ((err = blake2s_update(&S, packet_header, 4)) < 0) goto fail;
+ if ((err = blake2s_update(&S, body, bodylen)) < 0) goto fail;
+ if ((err = blake2s_final(&S, hmac, key->len)) < 0) goto fail;
+ return DIGEST_LEN;
+
+fail: fprintf(stderr,"Hashing key with blake2s failed\n");
+ return -1;
+
+#endif
+}
+
+static int
+compute_hmac_sha256(struct key *key, const unsigned char *src, const unsigned char *dst,
+ unsigned char *packet_header, unsigned char *hmac,
+ const unsigned char *body, int bodylen)
{
+#ifndef HAVE_SHA256
+ return -1;
+#else
SHA_CTX inner_ctx;
- RIPEMD160_CTX inner_ctx2;
SHA_CTX outer_ctx;
- RIPEMD160_CTX outer_ctx2;
unsigned char inner_hash[SHA_DIGEST_LENGTH];
unsigned char key_hash[SHA_DIGEST_LENGTH];
@@ -129,11 +165,9 @@ compute_hmac(const unsigned char *src, const unsigned char *dst,
int i;
DO_HTONS(&port, (unsigned short)protocol_port);
- switch(key->type) {
- case 1:
- memcpy(key_hash, key->value, SHA_DIGEST_LENGTH);
- for(i = 0; i < SHA_DIGEST_LENGTH; i++) {
- inner_key_pad[i] = key_hash[i]^0x36;
+ memcpy(key_hash, key->value, SHA_DIGEST_LENGTH);
+ for(i = 0; i < SHA_DIGEST_LENGTH; i++) {
+ inner_key_pad[i] = key_hash[i]^0x36;
}
for(i = SHA_DIGEST_LENGTH; i < SHA1_BLOCK_SIZE; i++) {
inner_key_pad[i] = 0x36;
@@ -162,41 +196,20 @@ compute_hmac(const unsigned char *src, const unsigned char *dst,
SHA1_Update(&outer_ctx, inner_hash, SHA_DIGEST_LENGTH);
SHA1_Final(hmac, &outer_ctx);
return SHA_DIGEST_LENGTH;
- case 2:
- memcpy(key_hash, key->value, RIPEMD160_DIGEST_LENGTH);
- for(i = 0; i < RIPEMD160_DIGEST_LENGTH; i++) {
- inner_key_pad[i] = key_hash[i]^0x36;
- }
- for(i = RIPEMD160_DIGEST_LENGTH; i < RIPEMD160_BLOCK_SIZE; i++) {
- inner_key_pad[i] = 0x36;
- }
- RIPEMD160_Init(&inner_ctx2);
- RIPEMD160_Update(&inner_ctx2, inner_key_pad, RIPEMD160_BLOCK_SIZE);
-
- /* Hashing the pseudo header. */
- RIPEMD160_Update(&inner_ctx2, dst, 16);
- RIPEMD160_Update(&inner_ctx2, &port, 2);
- RIPEMD160_Update(&inner_ctx2, src, 16);
- RIPEMD160_Update(&inner_ctx2, &port, 2);
-
- RIPEMD160_Update(&inner_ctx2, packet_header, 4);
- RIPEMD160_Update(&inner_ctx2, body, bodylen);
- RIPEMD160_Final(inner_hash, &inner_ctx2);
+#endif
+}
- for(i = 0; i < RIPEMD160_DIGEST_LENGTH; i++) {
- outer_key_pad[i] = key_hash[i]^0x5c;
- }
- for(i = RIPEMD160_DIGEST_LENGTH; i < RIPEMD160_BLOCK_SIZE; i++) {
- outer_key_pad[i] = 0x5c;
- }
- RIPEMD160_Init(&outer_ctx2);
- RIPEMD160_Update(&outer_ctx2, outer_key_pad, RIPEMD160_BLOCK_SIZE);
- RIPEMD160_Update(&outer_ctx2, inner_hash, RIPEMD160_DIGEST_LENGTH);
- RIPEMD160_Final(hmac, &outer_ctx2);
- RIPEMD160(body, bodylen, hmac);
- return RIPEMD160_DIGEST_LENGTH;
- default:
- return -1;
+static int
+compute_hmac(const unsigned char *src, const unsigned char *dst,
+ unsigned char *packet_header, unsigned char *hmac,
+ const unsigned char *body, int bodylen, struct key *key)
+{
+ switch(key->type) {
+ case 1: return compute_hmac_sha256(key, src, dst, packet_header, hmac,
+ body, bodylen);
+ case 2: return compute_hmac_blake2s(key, src, dst, packet_header, hmac,
+ body, bodylen);
+ default: return -1;
}
}
@@ -250,7 +263,7 @@ compare_hmac(const unsigned char *src, const unsigned char *dst,
true_hmaclen = compute_hmac(src, dst, packet_header, true_hmac,
packet + 4, bodylen, keys[i]);
if(true_hmaclen != hmaclen) {
- fprintf(stderr, "Length inconsistency of two hmacs.\n");
+ fprintf(stderr, "Length inconsistency of two hmacs - %d != %d \n", true_hmaclen, hmaclen);
return -1;
}
if(memcmp(true_hmac, hmac, hmaclen) == 0)
diff --git a/hmac.h b/hmac.h
index 4ccfe81..2bcb966 100644
--- a/hmac.h
+++ b/hmac.h
@@ -22,7 +22,7 @@ THE SOFTWARE.
#define DIGEST_LEN 20
#define SHA1_BLOCK_SIZE 64
-#define RIPEMD160_BLOCK_SIZE 64
+#define BLAKE2S_BLOCK_SIZE 64
struct key *find_key(const char *id);
struct key *retain_key(struct key *key);
diff --git a/message.c b/message.c
index f65a49a..38abb6b 100644
--- a/message.c
+++ b/message.c
@@ -462,6 +462,8 @@ parse_packet(const unsigned char *from, struct interface *ifp,
to) != 1) {
fprintf(stderr, "Received wrong hmac.\n");
return;
+ } else {
+ fprintf(stderr,"Recieved right hmac!!!\n");
}
}
_______________________________________________
Babel-users mailing list
[email protected]
https://alioth-lists.debian.net/cgi-bin/mailman/listinfo/babel-users
