From patchwork Mon Nov 9 16:50:47 2009 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: William Allen Simpson X-Patchwork-Id: 37978 X-Patchwork-Delegate: davem@davemloft.net Return-Path: X-Original-To: patchwork-incoming@ozlabs.org Delivered-To: patchwork-incoming@ozlabs.org Received: from vger.kernel.org (vger.kernel.org [209.132.176.167]) by ozlabs.org (Postfix) with ESMTP id 857A3B70B3 for ; Tue, 10 Nov 2009 03:51:04 +1100 (EST) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754152AbZKIQuu (ORCPT ); Mon, 9 Nov 2009 11:50:50 -0500 Received: (majordomo@vger.kernel.org) by vger.kernel.org id S1754340AbZKIQuu (ORCPT ); Mon, 9 Nov 2009 11:50:50 -0500 Received: from mail-bw0-f227.google.com ([209.85.218.227]:59412 "EHLO mail-bw0-f227.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753947AbZKIQut (ORCPT ); Mon, 9 Nov 2009 11:50:49 -0500 Received: by bwz27 with SMTP id 27so3659515bwz.21 for ; Mon, 09 Nov 2009 08:50:53 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:message-id:date:from :user-agent:mime-version:to:cc:subject:references:in-reply-to :content-type; bh=fz82nQitmEEM1h8jPGEf41Jrz2SRJSDJdk6EhyCXv1I=; b=TJubdZvRKFnI44f+1bGSenUUSyzZRuub0u3HC3FZvD0hWl+QjKKHOgXauzP92ffYze 4KuFdIq6ivwaPi7OupUzliIUCCPEdIV9nqub8ur3XFpRPJMjhwOPZDdHqY4USEf8sDS4 /OxTGuqPnmK+h0ZXjK9zyMu4IuKgHTuvXXAkA= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=message-id:date:from:user-agent:mime-version:to:cc:subject :references:in-reply-to:content-type; b=H+98hHpYXgfdol2jzKCRQ0SnoAatsmvInY+/aULsj4VN4wRKKNDKDvsTmwD31xtHip 8upuKcdu2hbVICMrvQcLsn2ofxlBg1UDSqxl9b1fh0pDvGTKrFJI0bfsraWt3YRgsYZw KNaA/xbRHGlF9XFQSK40JwRMcx++bkChp2UhM= Received: by 10.204.32.209 with SMTP id e17mr8824234bkd.84.1257785453502; Mon, 09 Nov 2009 08:50:53 -0800 (PST) Received: from Wastrel.local (c-68-42-73-61.hsd1.mi.comcast.net [68.42.73.61]) by mx.google.com with ESMTPS id 15sm688777bwz.8.2009.11.09.08.50.50 (version=TLSv1/SSLv3 cipher=RC4-MD5); Mon, 09 Nov 2009 08:50:51 -0800 (PST) Message-ID: <4AF84867.7010802@gmail.com> Date: Mon, 09 Nov 2009 11:50:47 -0500 From: William Allen Simpson User-Agent: Thunderbird 2.0.0.23 (Macintosh/20090812) MIME-Version: 1.0 To: Linux Kernel Network Developers CC: Eric Dumazet , "Paul E. McKenney" Subject: [net-next-2.6 PATCH v5 4/5 RFC] TCPCT part1d: generate Responder Cookie References: <4AF83E2D.1050401@gmail.com> In-Reply-To: <4AF83E2D.1050401@gmail.com> Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org Define (missing) hash message size for SHA1. Define hashing size constants specific to TCP cookies, and add new function. Maintain global secret values for tcp_cookie_generator(). This is a significantly revised implementation of earlier (15-year-old) Photuris [RFC-2522] code for the KA9Q cooperative multitasking platform. Linux RCU technique appears to be well-suited to this application, though neither of the circular queue items are freed. These functions will also be used in subsequent patches that implement additional features. Signed-off-by: William.Allen.Simpson@gmail.com --- include/linux/cryptohash.h | 1 + include/net/tcp.h | 8 +++ net/ipv4/tcp.c | 146 ++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 155 insertions(+), 0 deletions(-) diff --git a/include/linux/cryptohash.h b/include/linux/cryptohash.h index c118b2a..ec78a4b 100644 --- a/include/linux/cryptohash.h +++ b/include/linux/cryptohash.h @@ -2,6 +2,7 @@ #define __CRYPTOHASH_H #define SHA_DIGEST_WORDS 5 +#define SHA_MESSAGE_BYTES (512 /*bits*/ / 8) #define SHA_WORKSPACE_WORDS 80 void sha_init(__u32 *buf); diff --git a/include/net/tcp.h b/include/net/tcp.h index f15924b..702fd0a 100644 --- a/include/net/tcp.h +++ b/include/net/tcp.h @@ -1474,6 +1474,14 @@ struct tcp_request_sock_ops { #endif }; +/* Using SHA1 for now, define some constants. + */ +#define COOKIE_DIGEST_WORDS (SHA_DIGEST_WORDS) +#define COOKIE_MESSAGE_WORDS (SHA_MESSAGE_BYTES / 4) +#define COOKIE_WORKSPACE_WORDS (COOKIE_DIGEST_WORDS + COOKIE_MESSAGE_WORDS) + +extern int tcp_cookie_generator(u32 *bakery); + extern void tcp_v4_init(void); extern void tcp_init(void); diff --git a/net/ipv4/tcp.c b/net/ipv4/tcp.c index e0cfa63..3ae01bf 100644 --- a/net/ipv4/tcp.c +++ b/net/ipv4/tcp.c @@ -264,6 +264,7 @@ #include #include #include +#include #include #include @@ -2842,6 +2843,141 @@ EXPORT_SYMBOL(tcp_md5_hash_key); #endif +/** + * Each Responder maintains up to two secret values concurrently for + * efficient secret rollover. Each secret value has 4 states: + * + * Generating. (tcp_secret_generating != tcp_secret_primary) + * Generates new Responder-Cookies, but not yet used for primary + * verification. This is a short-term state, typically lasting only + * one round trip time (RTT). + * + * Primary. (tcp_secret_generating == tcp_secret_primary) + * Used both for generation and primary verification. + * + * Retiring. (tcp_secret_retiring != tcp_secret_secondary) + * Used for verification, until the first failure that can be + * verified by the newer Generating secret. At that time, this + * cookie's state is changed to Secondary, and the Generating + * cookie's state is changed to Primary. This is a short-term state, + * typically lasting only one round trip time (RTT). + * + * Secondary. (tcp_secret_retiring == tcp_secret_secondary) + * Used for secondary verification, after primary verification + * failures. This state lasts no more than twice the Maximum Segment + * Lifetime (2MSL). Then, the secret is discarded. + */ +struct tcp_cookie_secret { + /* The secret is divided into two parts. The digest part is the + * equivalent of previously hashing a secret and saving the state, + * and serves as an initialization vector (IV). The message part + * serves as the trailing secret. + */ + u32 secrets[COOKIE_WORKSPACE_WORDS]; + unsigned long expires; +}; + +#define TCP_SECRET_1MSL (HZ * TCP_PAWS_MSL) +#define TCP_SECRET_2MSL (HZ * TCP_PAWS_MSL * 2) +#define TCP_SECRET_LIFE (HZ * 600) + +static struct tcp_cookie_secret tcp_secret_one; +static struct tcp_cookie_secret tcp_secret_two; + +/* Essentially a circular list, without dynamic allocation. */ +static struct tcp_cookie_secret *tcp_secret_generating; +static struct tcp_cookie_secret *tcp_secret_primary; +static struct tcp_cookie_secret *tcp_secret_retiring; +static struct tcp_cookie_secret *tcp_secret_secondary; + +static DEFINE_SPINLOCK(tcp_secret_locker); + +/* Select a random word in the cookie workspace. + */ +static inline u32 tcp_cookie_work(const u32 *ws, const int n) +{ + return ws[COOKIE_DIGEST_WORDS + ((COOKIE_MESSAGE_WORDS-1) & ws[n])]; +} + +/* Fill bakery[COOKIE_WORKSPACE_WORDS] with generator, updating as needed. + * Called in softirq context. + * Returns: 0 for success. + */ +int tcp_cookie_generator(u32 *bakery) +{ + unsigned long jiffy = jiffies; + + if (unlikely(time_after_eq(jiffy, tcp_secret_generating->expires))) { + spin_lock_bh(&tcp_secret_locker); + if (!time_after_eq(jiffy, tcp_secret_generating->expires)) { + /* refreshed by another */ + spin_unlock_bh(&tcp_secret_locker); + memcpy(bakery, + &tcp_secret_generating->secrets[0], + sizeof(tcp_secret_generating->secrets)); + } else { + u32 secrets[COOKIE_WORKSPACE_WORDS]; + + /* still needs refreshing */ + get_random_bytes(secrets, sizeof(secrets)); + + /* The first time, paranoia assumes that the + * randomization function isn't as strong. But, + * this secret initialization is delayed until + * the last possible moment (packet arrival). + * Although that time is observable, it is + * unpredictably variable. Mash in the most + * volatile clock bits available, and expire the + * secret extra quickly. + */ + if (unlikely(tcp_secret_primary->expires == + tcp_secret_secondary->expires)) { + struct timespec tv; + + getnstimeofday(&tv); + secrets[COOKIE_DIGEST_WORDS+0] ^= + (u32)tv.tv_nsec; + + tcp_secret_secondary->expires = jiffy + + TCP_SECRET_1MSL + + (0x0f & tcp_cookie_work(secrets, 0)); + } else { + tcp_secret_secondary->expires = jiffy + + TCP_SECRET_LIFE + + (0xff & tcp_cookie_work(secrets, 1)); + tcp_secret_primary->expires = jiffy + + TCP_SECRET_2MSL + + (0x1f & tcp_cookie_work(secrets, 2)); + } + memcpy(&tcp_secret_secondary->secrets[0], + &secrets[0], + sizeof(secrets)); + + rcu_assign_pointer(tcp_secret_generating, + tcp_secret_secondary); + rcu_assign_pointer(tcp_secret_retiring, + tcp_secret_primary); + spin_unlock_bh(&tcp_secret_locker); + /* Neither call_rcu() or synchronize_rcu() are needed. + * Retiring data is not freed. It is replaced after + * further (locked) pointer updates, and a quiet time + * (minimum 1MSL, maximum LIFE - 2MSL). + */ + memcpy(bakery, + &secrets[0], + sizeof(secrets)); + } + } else { + rcu_read_lock_bh(); + memcpy(bakery, + &rcu_dereference(tcp_secret_generating)->secrets[0], + sizeof(tcp_secret_generating->secrets)); + rcu_read_unlock_bh(); + } + return 0; +} +EXPORT_SYMBOL(tcp_cookie_generator); + void tcp_done(struct sock *sk) { if (sk->sk_state == TCP_SYN_SENT || sk->sk_state == TCP_SYN_RECV) @@ -2876,6 +3012,7 @@ void __init tcp_init(void) struct sk_buff *skb = NULL; unsigned long nr_pages, limit; int order, i, max_share; + unsigned long jiffy = jiffies; BUILD_BUG_ON(sizeof(struct tcp_skb_cb) > sizeof(skb->cb)); @@ -2969,6 +3106,15 @@ void __init tcp_init(void) tcp_hashinfo.ehash_mask + 1, tcp_hashinfo.bhash_size); tcp_register_congestion_control(&tcp_reno); + + memset(&tcp_secret_one.secrets[0], 0, sizeof(tcp_secret_one.secrets)); + memset(&tcp_secret_two.secrets[0], 0, sizeof(tcp_secret_two.secrets)); + tcp_secret_one.expires = jiffy; /* past due */ + tcp_secret_two.expires = jiffy; /* past due */ + tcp_secret_generating = &tcp_secret_one; + tcp_secret_primary = &tcp_secret_one; + tcp_secret_retiring = &tcp_secret_two; + tcp_secret_secondary = &tcp_secret_two; } EXPORT_SYMBOL(tcp_close);