[ECOS] dhcp XID generation

[ECOS] dhcp XID generation

[Robin Farine]

Hi,

In a system with a single power supply but many independent boards running eCos
and using the DHCP client, switching the system on sometimes results into some
boards configured with the *same* parameters (IP address, ...).

The problem resides in the method used to generate the DHCP request's XID
field. A solution that seems to work for us follows:

<Changelog>
2001-05-03  Robin Farine  <acnrf@dial.eunet.ch>

	* src/lib/dhcp_prot.c (do_dhcp): Uses arc4random() instead of
	cyg_current_time() to generate the XID field to improve randomness.
</Changelog>

<patch>
Index: packages/net/tcpip/current/src/lib/dhcp_prot.c
===================================================================
RCS file: /usr/cvs/eCos/packages/net/net/tcpip/current/src/lib/dhcp_prot.c,v
retrieving revision 1.1.1.1
retrieving revision 1.2
diff -r1.1.1.1 -r1.2
397c397
<         xid = (cyg_uint32)res + (cyg_uint32)(0xffffffff & cyg_current_time());
---
>         xid = (cyg_uint32)res + (cyg_uint32)arc4random();
</patch>

Robin

Re: [ECOS] dhcp XID generation

[Hugo Tyson]

Robin Farine <acnrf@dial.eunet.ch> writes:
> In a system with a single power supply but many independent boards
> running eCos and using the DHCP client, switching the system on sometimes
> results into some boards configured with the *same* parameters (IP
> address, ...).

...and all using the same application binary, so (int)res is the same,
right, I can see that would be a problem.

> The problem resides in the method used to generate the DHCP request's XID
> field. A solution that seems to work for us follows:
> 
> <Changelog>
> 2001-05-03  Robin Farine  <acnrf@dial.eunet.ch>
> 
> 	* src/lib/dhcp_prot.c (do_dhcp): Uses arc4random() instead of
> 	cyg_current_time() to generate the XID field to improve randomness.
> </Changelog>
> 
> <patch>
> Index: packages/net/tcpip/current/src/lib/dhcp_prot.c
> ===================================================================
> RCS file: /usr/cvs/eCos/packages/net/net/tcpip/current/src/lib/dhcp_prot.c,v
> retrieving revision 1.1.1.1
> retrieving revision 1.2
> diff -r1.1.1.1 -r1.2
> 397c397
> <         xid = (cyg_uint32)res + (cyg_uint32)(0xffffffff & cyg_current_time());
> ---
> >         xid = (cyg_uint32)res + (cyg_uint32)arc4random();
> </patch>

Is that really random enough?  (Yes, I know the question has no meaning to
a true mathematician).  Yeah, the clock is free-running fast, in general.

You could just pick up the ESA from ifr.ifr_hwaddr.sa_data at that point, I
believe, to salt the token further.  It was set in bring_half_up(), as well
as later on in the routine.

	- Huge

Re: [ECOS] dhcp XID generation

[Robin Farine]

Hugo Tyson <hmt@redhat.com> writes:

> Robin Farine <acnrf@dial.eunet.ch> writes:
> > In a system with a single power supply but many independent boards
> > running eCos and using the DHCP client, switching the system on sometimes
> > results into some boards configured with the *same* parameters (IP
> > address, ...).
> 
> ...and all using the same application binary, so (int)res is the same,
> right, I can see that would be a problem.
> 
> > The problem resides in the method used to generate the DHCP request's XID
> > field. A solution that seems to work for us follows:
> > 
> > <Changelog>
> > 2001-05-03  Robin Farine  <acnrf@dial.eunet.ch>
> > 
> > 	* src/lib/dhcp_prot.c (do_dhcp): Uses arc4random() instead of
> > 	cyg_current_time() to generate the XID field to improve randomness.
> > </Changelog>
> > 
> > <patch>
> > Index: packages/net/tcpip/current/src/lib/dhcp_prot.c
> > ===================================================================
> > RCS file: /usr/cvs/eCos/packages/net/net/tcpip/current/src/lib/dhcp_prot.c,v
> > retrieving revision 1.1.1.1
> > retrieving revision 1.2
> > diff -r1.1.1.1 -r1.2
> > 397c397
> > <         xid = (cyg_uint32)res + (cyg_uint32)(0xffffffff & cyg_current_time());
> > ---
> > >         xid = (cyg_uint32)res + (cyg_uint32)arc4random();
> > </patch>
> 
> Is that really random enough?  (Yes, I know the question has no meaning to
> a true mathematician).  Yeah, the clock is free-running fast, in general.
> 
> You could just pick up the ESA from ifr.ifr_hwaddr.sa_data at that point, I
> believe, to salt the token further.  It was set in bring_half_up(), as well
> as later on in the routine.

Yes right, we could use the two most significant bytes of the ESA as the most
significant 16 bits of the XID and the 16 least significant bits of the
arc4random() result as the 16 least significant bits of the XID. Something like:

<patch>
Index: packages/net/tcpip/current/src/lib/dhcp_prot.c
===================================================================
RCS file: /usr/cvs/eCos/packages/net/net/tcpip/current/src/lib/dhcp_prot.c,v
retrieving revision 1.1.1.1
retrieving revision 1.2
diff -r1.1.1.1 -r1.2
397c397,399
<         xid = (cyg_uint32)res + (cyg_uint32)(0xffffffff & cyg_current_time());
---
>         xid = ((cyg_uint32)ifr.ifr_hwaddr.sa_data[5] << 24) |
> 	  ((cyg_uint32)ifr.ifr_hwaddr.sa_data[4] << 16) |
> 	  ((cyg_uint32)arc4random() & 0xffff);
</patch>

<Changelog>
2001-05-03  Robin Farine  <acnrf@dial.eunet.ch>

	* src/lib/dhcp_prot.c (do_dhcp): Decreases the probability that
	two clients on a given IP subnet generate the same XID.
</Changelog>

Robin

Re: [ECOS] dhcp XID generation

[Robin Farine]

Hi Hugo,

If the method to generate the XID seems suitable then here follows trial
number 3 (hopefully correct this time :-/):

<patch>
Index: packages/net/tcpip/current/src/lib/dhcp_prot.c
===================================================================
RCS file: /usr/cvs/eCos/packages/net/net/tcpip/current/src/lib/dhcp_prot.c,v
retrieving revision 1.1
diff -r1.1 dhcp_prot.c
395a396
> 
397d397
<         xid = (cyg_uint32)res + (cyg_uint32)(0xffffffff & cyg_current_time());
399,400d398
<     else
<         xid = res->bp_xid; // use what's there already
446a445,446
>     xid = res->bp_xid; // default to what's there already;
> 
487a488,496
>             }
> 
>             // generates a new XID
>             {
>                 unsigned char* xp = (unsigned char*)&xid;
> 
>                 *xp++ = ifr.ifr_hwaddr.sa_data[5];
>                 *xp++ = ifr.ifr_hwaddr.sa_data[4];
>                 *((cyg_uint16*)xp) = (cyg_uint16)(arc4random() & 0xffff);
</patch>

Robin

Re: [ECOS] dhcp XID generation

[Hugo Tyson]

Robin Farine <acnrf@dial.eunet.ch> writes:

> Hi Hugo,
> 
> If the method to generate the XID seems suitable then here follows trial
> number 3 (hopefully correct this time :-/):

Nice one, thanks Robin; here's what I actually committed.  Your patch plus
a hack to arc4random().

	- Huge

Index: net/tcpip/current//ChangeLog
===================================================================
RCS file: /home/cvs/ecc/ecc/net/tcpip/current/ChangeLog,v
retrieving revision 1.122
diff -u -5 -p -r1.122 ChangeLog
--- net/tcpip/current//ChangeLog	2001/05/09 16:35:12	1.122
+++ net/tcpip/current//ChangeLog	2001/05/09 17:15:03
@@ -1,8 +1,21 @@
 2001-05-09  Robin Farine <acnrf@dial.eunet.ch>
 2001-05-09  Hugo Tyson  <hmt@redhat.com>
 
+	* src/lib/dhcp_prot.c (do_dhcp): In DHCPSTATE_INIT case, create a
+	new xid.  Servers apparantly can use *only* this to distinguish
+	machines, even with different MAC addresses!  Therefore we use
+	both the most sensitive randomizer available (arc4random()) which
+	in reality uses a finegrain clock, and salt the value further with
+	the MAC address itself.  Thanks again Robin.
+
+	* src/ecos/support.c (arc4random): Make arc4random not always be a
+	multiple of 256; stir the clock into the low bits also.
+
+2001-05-09  Robin Farine <acnrf@dial.eunet.ch>
+2001-05-09  Hugo Tyson  <hmt@redhat.com>
+
 	* src/sys/net/if_bridge.c: Patch from Robin; the route aging
 	process took twice as long to timeout because an entry requires
 	*two* executions of bridge_rtage() to actually get removed.
 	Record the timeout over 2 to fix that and also define
 	BRIDGE_RTABLE_TIMEOUT as 300s that the standard specifies as
Index: net/tcpip/current//src/ecos/support.c
===================================================================
RCS file: /home/cvs/ecc/ecc/net/tcpip/current/src/ecos/support.c,v
retrieving revision 1.24
diff -u -5 -p -r1.24 support.c
--- net/tcpip/current//src/ecos/support.c	2001/01/08 02:41:04	1.24
+++ net/tcpip/current//src/ecos/support.c	2001/05/09 17:15:03
@@ -341,11 +341,11 @@ int cyg_net_get_mem_stats( int which, cy
             cyg_mempool_fix_get_info( net_clusters, p );
             break;
         default:
             return 0;
         }
-    return p;
+    return (int)p;
 }
 
 int
 cyg_mtocl(u_long x)
 {
@@ -382,14 +382,14 @@ net_memset(void *s, int v, int n)
 int
 arc4random(void)
 {
     cyg_uint32 res;
     static unsigned long seed = 0xDEADB00B;
-    HAL_CLOCK_READ(&res);  // Not so bad...
-    seed = ((seed & 0x07F00FF) << 7) ^
-        (seed & 0xF80FF00) ^ 
-        (res << 13);
+    HAL_CLOCK_READ(&res);  // Not so bad... (but often 0..N where N is small)
+    seed = ((seed & 0x007F00FF) << 7) ^
+        ((seed & 0x0F80FF00) >> 8) ^ // be sure to stir those low bits
+        (res << 13) ^ (res >> 9);    // using the clock too!
     return (int)seed;
 }
 
 void 
 get_random_bytes(void *buf, size_t len)
Index: net/tcpip/current//src/lib/dhcp_prot.c
===================================================================
RCS file: /home/cvs/ecc/ecc/net/tcpip/current/src/lib/dhcp_prot.c,v
retrieving revision 1.6
diff -u -5 -p -r1.6 dhcp_prot.c
--- net/tcpip/current//src/lib/dhcp_prot.c	2001/01/03 18:45:17	1.6
+++ net/tcpip/current//src/lib/dhcp_prot.c	2001/05/09 17:15:04
@@ -391,15 +391,13 @@ do_dhcp(const char *intf, struct bootp *
          || DHCPSTATE_FAILED == oldstate
          || 0                == oldstate ) {
         // either explicit init state or the beginning of time or retry
         if ( ! bring_half_up( intf, &ifr ) )
             return false;
+
         *pstate = DHCPSTATE_INIT;
-        xid = (cyg_uint32)res + (cyg_uint32)(0xffffffff & cyg_current_time());
     }
-    else
-        xid = res->bp_xid; // use what's there already
 
     s = socket(AF_INET, SOCK_DGRAM, 0);
     if (s < 0) {
         perror("socket");
         return false;
@@ -442,10 +440,12 @@ do_dhcp(const char *intf, struct bootp *
     // be the neatest way to do it; it returns from within the switch arms
     // when all is well, or utterly failed.
 
     reset_timeout( &tv, &timeout_scratch );
 
+    xid = res->bp_xid; // default to what's there already;
+
     while ( 1 ) {
 
         // If we are active rather than in the process of shutting down,
         // check for any lease expiry every time round, so that alarms
         // *can* change the course of events even when already renewing,
@@ -483,10 +483,19 @@ do_dhcp(const char *intf, struct bootp *
             // Send the DHCPDISCOVER packet
 
             if (ioctl(s, SIOCGIFHWADDR, &ifr) < 0) { /* get MAC address */
                 perror("SIOCGIFHWADDR 2");
                 return false;
+            }
+
+            // generates a new XID
+            {
+                unsigned char* xp = (unsigned char*)&xid;
+
+                *xp++ = ifr.ifr_hwaddr.sa_data[5];
+                *xp++ = ifr.ifr_hwaddr.sa_data[4];
+                *((cyg_uint16*)xp) = (cyg_uint16)(arc4random() & 0xffff);
             }
 
             // Fill in the BOOTP request - DHCPDISCOVER packet
             bzero(xmit, sizeof(*xmit));
             xmit->bp_op = BOOTREQUEST;