[Click] Little element, random dropper...
Nicholas Weaver
nweaver at ICSI.Berkeley.EDU
Tue Jul 26 13:18:15 EDT 2005
For testing, I hacked up a simple little packet-dropper
(sysadmin is having some problems, and needs a debugging tool to
increase loss in a link). It uses a 32 bit pRNG (RC5/3 round/32 bit)
to decide whether to randomly drop a packet.
Since it might be useful for others as well, I'm sending it to
the list.
The files:
rand_drop.{cc,hh} the element itself
rc5.{cc,hh} RC5 as a support file.
--
Nicholas C. Weaver nweaver at icsi.berkeley.edu
This message has been ROT-13 encrypted twice for higher security.
-------------- next part --------------
// -*- c-basic-offset: 4 -*-
/*
* rand_drop.{cc,hh} -- A randomized packet dropper.
* Nicholas Weaver
*
* Copyright (c) 2005 ICSI. No warantee. Released under a BSD liscence
*
*/
#include <click/config.h>
#include <click/confparse.hh>
#include <click/error.hh>
#include <click/straccum.hh>
#include <clicknet/icmp.h>
#include <clicknet/tcp.h>
#include <clicknet/udp.h>
#include "rand_drop.hh"
#include "rc5.hh"
CLICK_DECLS
RandomDrop::RandomDrop()
{
MOD_INC_USE_COUNT;
}
RandomDrop::~RandomDrop()
{
MOD_DEC_USE_COUNT;
}
void
RandomDrop::notify_ninputs(int i)
{
set_ninputs(i);
}
void
RandomDrop::notify_noutputs(int i)
{
set_noutputs(i);
}
void
RandomDrop::push(int port, Packet *p)
{
if((rc5_encrypt(rc5_index++,rc5_key) <= drop_int)
&& ( drop_int != 0)){
drop_count++;
p->kill();
} else {
pass_count++;
output(port).push(p);
}
// if(drop_count % 100 == 0)
// click_chatter("%u dropped, %u passed\n", drop_count, pass_count);
}
int
RandomDrop::configure(Vector<String> &conf, ErrorHandler *errh){
rc5_seed = 0xCAFEBABE;
drop_fraction = 655; // Drop ~1% by default.
drop_count = 0;
pass_count = 0;
if( cp_va_parse(conf, this, errh,
cpKeywords,
"DROP_FRACTION", cpUnsignedReal2,
"Fraction of packets to drop", 16, &drop_fraction,
"RC5_KEY", cpInteger,
"RC5 initial key", &rc5_seed,
cpEnd
) < 0
){
click_chatter("Arguments Parse Failure\n");
return -1;
}
// click_chatter("Arguments Parsed\n");
if(ninputs() != noutputs()){
return
errh->error("The number of inputs and outputs must be identical");
}
if( drop_fraction > 0x10000){
return
errh->error("Drop fraction 0 <= fract <= 1");
}
rc5_key = rc5_keygen(rc5_seed);
// click_chatter("RC5 key is %x\n", rc5_seed);
// click_chatter("RC5 encrypt of 0xFEEDFACE is %x\n",
// rc5_encrypt(0xFEEDFACE, rc5_key));
// click_chatter("RC5 D(E(x)) of 0xFEEDFACE is %x\n",
// rc5_decrypt(rc5_encrypt(0xFEEDFACE, rc5_key),
// rc5_key));
// click_chatter("Dropping fraction is %i\n",
// drop_fraction);
drop_int = (uint32_t) (drop_fraction << 16);
if(drop_fraction == 0) drop_int = 0;
if(drop_fraction == 0x10000) drop_int = 0xffffffff;
// click_chatter("Dropping fraction integer approximation is %x\n",
// drop_int);
return 0;
}
CLICK_ENDDECLS
ELEMENT_REQUIRES(rc5)
EXPORT_ELEMENT(RandomDrop)
-------------- next part --------------
// -*- c-basic-offset: 4 -*-
#ifndef NW_RANDOMDROP_HH
#define NW_RANDOMDROP_HH
#include <click/element.hh>
CLICK_DECLS
/*
* =c
* RandomDrop([N])
*
* =s dropping
* Randomly drops packets
*
* =d
* Random drops packets. Its currently push only (based on the template
* I used to make it). Default is to drop .01 (1%) packets, and the
* default seed for the pRNG (RC5/3/32) is 0xCAFEBABE.
*
* This uses RC5 3round, 32 bit as its pRNG.
*
* Keword arguments are:
*
* =item DROP_FRACTION
*
* The fraction of packets to drop, from 0 to 1. Note that since it
* is a fixed point number (16 bits), it is imprecise for fractions less
* than .001, and won't work well/at all for fractions less than .0001.
*
* =item RC5_KEY
*
* The key to use for the pRNG
*
*/
class RandomDrop : public Element { public:
RandomDrop();
~RandomDrop();
const char *class_name() const { return "RandomDrop"; }
const char *processing() const { return PUSH; }
int configure(Vector<String> &conf, ErrorHandler *errh);
void notify_ninputs(int);
void notify_noutputs(int);
void push(int port, Packet *p);
private:
uint16_t *rc5_key;
uint32_t rc5_seed;
unsigned drop_fraction;
uint32_t rc5_index;
uint32_t drop_int;
uint32_t drop_count;
uint32_t pass_count;
};
CLICK_ENDDECLS
#endif
-------------- next part --------------
#include <click/config.h>
#include <click/confparse.hh>
#include <click/error.hh>
#include <click/straccum.hh>
#include <clicknet/icmp.h>
#include <clicknet/tcp.h>
#include <clicknet/udp.h>
#include "rc5.hh"
// Implementation for RC5, 32 bit, 3 rounds, 32 bit key (RC5/32/3/32)
// which is what's used as the random permutation for the address
// table, and for the pRNG for the random dropper. This is a WEAK
// cypher, but as the attacker doesn't really have insight into the
// table state, AND since blowing out the table really doesn't buy
// much unless the attacker has tons of IPs, this isn't a problem.
// Modified from applied crypto, and my simple sim
#define RC5_ROUNDS 3
#define ROTR16(x,c) ((uint16_t) (((x)>>((c) & 0xf))|((x)<<(16-((c) & 0xf)))))
#define ROTL16(x,c) ((uint16_t) (((x)<<((c) & 0xf))|((x)>>(16-((c) & 0xf)))))
CLICK_DECLS
uint16_t *rc5_keygen(uint32_t key){
uint16_t *keyArray;
uint16_t lArray[2];
int i = 0;
int j = 0;
int k = 0;
uint16_t A = 0;
uint16_t B = 0;
lArray[0] = key;
lArray[1] = key >> 16;
keyArray = (uint16_t *) malloc(sizeof(uint16_t) * 2 * (RC5_ROUNDS + 1));
keyArray[0] = 0xb7e5;
for(i = 1; i < (2 * (RC5_ROUNDS + 1)); ++i){
keyArray[i] = (keyArray[i-1] + 0x9e37);
}
i = 0; j = 0;
for(k = 0; k < 6 * (RC5_ROUNDS + 1); ++k){
A = ROTL16( keyArray[i] + A + B, 3);
keyArray[i] = A;
B = ROTL16( lArray[j] + A + B, A + B);
lArray[j] = B;
i++;
j++;
i = i % (2 * (RC5_ROUNDS + 1));
j = j % 2;
}
/* click_chatter("Key array for initial key %i is\n", key);
for(i = 0; i < (2 * (numRounds + 1)); ++i){
click_chatter("%2i 0x%4x\n",i,keyArray[i]);
} */
return keyArray;
}
uint32_t rc5_encrypt(uint32_t data, uint16_t *key){
uint16_t a, b;
uint32_t result;
int i;
a = (data & 0xffff);
b = ((data >> 16) & 0xffff);
a += key[0];
b += key[1];
for(i = 1; i <= RC5_ROUNDS; ++i){
a = a ^ b;
a = ROTL16(a,b);
a = a + key[2 * i];
b = ROTL16((b ^ a), a);
b = b + key[2 * i + 1];
}
result = b;
result = result << 16;
result = result | a;
return result;
}
uint32_t rc5_decrypt(uint32_t data, uint16_t *key){
uint16_t a, b;
uint32_t result;
int i;
a = (data & 0xffff);
b = ((data >> 16) & 0xffff);
for(i = RC5_ROUNDS; i >= 1; --i){
b = b - key [2 * i + 1];
b = ROTR16(b,a);
b = b ^ a;
a = a - key [2 * i];
a = ROTR16(a,b);
a = a ^ b;
}
b = b - key[1];
a = a - key[0];
result = b;
result = result << 16;
result = result | a;
return result;
}
CLICK_ENDDECLS
ELEMENT_PROVIDES(rc5)
-------------- next part --------------
#ifndef NW_RC5_HH
#define NW_RC5_HH
#include <click/element.hh>
uint16_t * rc5_keygen(uint32_t key);
uint32_t rc5_encrypt(uint32_t data, uint16_t *key);
uint32_t rc5_decrypt(uint32_t data, uint16_t *key);
#endif
More information about the click
mailing list