Re: [PATCH] OpenBSD Networking-related randomization port

On Fri, 28 Jan 2005 21:47:45 +0100, Arjan van de Ven said:

as for obsd_get_random_long().. would it be possible to use the
get_random_int() function from the patches I posted the other day? They
use the existing random.c infrastructure instead of making a copy...

I still don't understand why you need a obsd_rand.c and can't use the
normal random.c

Note that obsd_rand.c started off life as a BSD-licensed file - I was told
that was a show-stopper when I submitted basically the same patch a while back.

So re-working it to use get_random_int()  would be a good idea, I think....

On Sat, Jan 29, 2005 at 04:15:43AM -0500, Valdis.Kletnieks@vt.edu wrote:

On Fri, 28 Jan 2005 21:47:45 +0100, Arjan van de Ven said:

quoted

as for obsd_get_random_long().. would it be possible to use the
get_random_int() function from the patches I posted the other day? They
use the existing random.c infrastructure instead of making a copy...

I still don't understand why you need a obsd_rand.c and can't use the
normal random.c

Note that obsd_rand.c started off life as a BSD-licensed file - I was told
that was a show-stopper when I submitted basically the same patch a while back.
...

At least the three clause BSD license is GPL compatible.

cu
Adrian

-- 

       "Is there not promise of rain?" Ling Tan asked suddenly out
        of the darkness. There had been need of rain for many days.
       "Only a promise," Lao Er said.
                                       Pearl S. Buck - Dragon Seed

El lun, 31-01-2005 a las 17:50 +0100, Adrian Bunk escribió:

On Sat, Jan 29, 2005 at 04:15:43AM -0500, Valdis.Kletnieks@vt.edu wrote:

quoted

On Fri, 28 Jan 2005 21:47:45 +0100, Arjan van de Ven said:

quoted

as for obsd_get_random_long().. would it be possible to use the
get_random_int() function from the patches I posted the other day? They
use the existing random.c infrastructure instead of making a copy...

I still don't understand why you need a obsd_rand.c and can't use the
normal random.c

Note that obsd_rand.c started off life as a BSD-licensed file - I was told
that was a show-stopper when I submitted basically the same patch a while back.
...

At least the three clause BSD license is GPL compatible.

Yes, AFAIK :)

I will try to follow Arjan's recommendations on using his functions
instead of obsd ones, even if I think it should be alone in the current
file.
Also I will split up the patch.

I will do it as soon as I get time for it, I need first to work out a
cleaner vsec (no more code in headers and such) and also a sys_chroot()
hook that I requested yesterday on the bugzilla, among the SELinux 2.4
backport which needs several fixes due to last 2.6 bk-commits reports.

Thanks for the comments,
Cheers.
-- 
Lorenzo Hernández García-Hierro [off-list ref] 
[1024D/6F2B2DEC] & [2048g/9AE91A22][http://tuxedo-es.org]

* Lorenzo Hernández García-Hierro [off-list ref] wrote:

quoted

At least the three clause BSD license is GPL compatible.

Yes, AFAIK :)

I will try to follow Arjan's recommendations on using his functions
instead of obsd ones, even if I think it should be alone in the
current file. Also I will split up the patch.

could you please also react to this feedback:

  http://marc.theaimsgroup.com/?l=linux-kernel&m=110698371131630&w=2

to quote a couple of key points from that very detailed security
analysis:

" I'm not sure how the OpenBSD code is better in any way.  (Notice that
  it uses the same "half_md4_transform" as Linux; you just added another
  copy.) Is there a design note on how the design was chosen? "

that mail also includes a much smaller patch to random.c.

( Obviously the more fundamental questions have to be solved prior
solving code-level problems, patch splitup and patch ordering - often
one ends up having a much smaller patch to work with, by thinking more
about the fundamentals. )

	Ingo

could you please also react to this feedback:

  http://marc.theaimsgroup.com/?l=linux-kernel&m=110698371131630&w=2

to quote a couple of key points from that very detailed security
analysis:

" I'm not sure how the OpenBSD code is better in any way.  (Notice that
  it uses the same "half_md4_transform" as Linux; you just added another
  copy.) Is there a design note on how the design was chosen? "

Just note that, in addition to the security aspects, there are also a
whole set of multiprocessor issues.  OpenBSD added SMP support in June
2004, and it looks like this code dates back to before that.  It might
be worth looking at what OpenBSD does now.

Note that I have NOT looked at the patch other than the TCP ISN
generation.  However, given the condition of the ISN code, I am inclined
to take a "guilty until proven innocent" view of the rest of it.
Don't merge it until someone has really grokked it, not just kibitzed
about code style issues.

(The homebrew 15-bit block cipher in this code does show how much the
world needs a small block cipher for some of these applications.)

*Sigh*.  This thread is heading into the weeds.

I have things I should be doing instead, but since nobody seems to
actually be looking at what the patch *does*, I guess I'll have
to dig into it a bit more...

Yes, licensing issues need to be resolved before a patch can go in.
Yes, code style standards needs to be kept up.
And yes, SMP-locking issues need to be looked at.
(And yes, ipv6 needs to be looked at, too!)

But before getting sidetracked into the fine details, could
folks please take a step back from the trees and look at the forest?

Several people have asked (especially when the first patch came out),
but I haven't seen any answers to the Big Questions:

1) Does this patch improve Linux's networking behaviour in any way?
2) Are the techniques in this patch a good way to achieve those
   improvements?


Let's look at the various parts of the change:

- Increases the default random pool size.
  Opinion: whatever.  No real cost, except memory.  Increases the
  maximum amount that can be read from /dev/random without blocking.
  Note that this is already adjustable at run time, so the question
  is why put it in the kernel config.

  If you want this, I'd suggest instead an option under CONFIG_EMBEDDED to
  shrink the pools and possibly get rid of the run-time changing code,
  then you could increase the default with less concern.

- Changes the TCP ISN generation algorithm.
  I have't seen any good side to this.  The current algorithm can be
  used for OS fingerprinting based on starting two TCP connections from
  different sources (ports or IPs) and noticing that the ISNs
  only differ in the low 24 bits, but is that a serious issue?
  If it is, there are better ways to deal with it that still preserve
  the valuable timer property.

  I point out that the entire reason for the cryptographically
  marginal half_md4_transform oprtation was that a full MD5 was a very
  noticeable performance bottleneck; the hash was only justified by
  the significant real-world attacks.  obsd_get_random uses two calls
  to half_md4_transform.  Which is the same cost as a full MD4 call.
  Frankly, they could just change half_md4_transform to return 64 bits
  instead of 32 and make do with one call.

- Changes to the IP ID generation algorithm.
  All it actually does is change the way the initial inet->id is
  initialized for the inet_opt structure associated with the TCP socket.
  And if you look at ip_output.c:ip_push_pending_frames(), you'll see
  that, if DF is set (as is usual for a TCP connection), iph->id (the
  actual IP header ID) is set to htons(inet->id++).  So it's still
  an incrementing sequence.

  This is in fact (see the comment in ip.h:ip_select_ident()) a workaround
  for a Microsoft VJ compression bug.  The fix was added in 2.4.4 (via
  DaveM's zerocopy-beta-3 patch); before that, Linux 2.4 sent a constant
  zero as the IP ID of DF packets.  See discussion at
	http://www.postel.org/pipermail/end2end-interest/2001-May/thread.html
	http://tcp-impl.lerc.nasa.gov/tcp-impl/list/archive/2378.html
  I'm not finding the diagnosis of the problem.  I saw one report at
	http://oss.sgi.com/projects/netdev/archive/2001-01/msg00006.html
  and Dave Miller is pretty much on top of it when he posts
	http://marc.theaimsgroup.com/?l=linux-kernel&m=98275316400452&w=2
  but I haven't found the actual debugging leading to the conclusion.

  This also led to some discussion of the OpenBSD IP ID algorithm that
  I haven't fully waded through at
	http://mail-index.netbsd.org/tech-net/2003/11/

  If the packet is fragmentable (the only time the IP ID is really
  needed by the receiver), it's done by route.c:__ip_select_ident().
  Wherein the system uses inet_getid to assign p->ip_id_count++
  based on the route cache's struct inet_peer *p.

  (If the route cache is OOM, the system falls back on random IP ID
  assignment.)

  This latter technique nicely prevents the sort of stealth port
  scanning that was mentioned earlier in this thread, and prevents
  a person at address A from guessing the IP ID range I'm using to
  talk to address B.  So note that the boast about "Randomized IP IDs"
  in the grsecurity description at
	http://www.gentoo.org/proj/en/hardened/grsecurity.xml
  is, as far as I can tell from a quick look at the code, simply false.

  As for the algorithm itself, it's described at
	http://www.usenix.org/events/usenix99/full_papers/deraadt/deraadt_html/node18.html
  but it's not obvious to me that it'd be hard to cryptanalyze given
  a stream of consecutive IDs.  You need to recover:
  - The n value for each inter-ID gap,
  - The LCRNG state ru_a, ru_x, ru_b,
  - The 15-bit XOR masks ru_seed and ru_seed2, and
  - The discrete log generator ru_j (ru_g = 2^ru_j mod RU_N).
    Which is actually just a multiplier (mod RU_N-1  = 32748) on
    the input to the pmod() operation.

  So the IP ID generation can be summarized as:

  ru_x = (ru_a * ru_x + ru_b) % 31104;	/* Repeated 1..4 times */
  exp = ((ru_x ^ ru_seed2) + ru_j) % 32748;
  return ru_seed ^ pmod(2, exp, 32749);

  Now, if you can guess ru_seed, then the pmod() operation is simply a
  bijection that can be looked up in a table, and then it's just
  a matter of untangling a slightly elaborated LCRNG.

- Changes the sun RPC XID allocation algorithm.
  Note that each connection is already initialized with a secure random
  number; the only change is whether the IDs used are simply incrementing
  from there or randomized each time one is needed.

  First of all and very importantly, obsd_get_random_long() does
  indeed generate a *random* number, which could be the *same* number as
  the last one.  This could be VERY BAD for RPC XIDs, which have to be
  unique so the client can match the reply with the request.  Note that
  Theo de Raadt knows better than do do that:
	http://www.usenix.org/events/usenix99/full_papers/deraadt/deraadt_html/node18.html
  Looking at the OpenBSD code at
	http://www.openbsd.org/cgi-bin/cvsweb/src/sys/nfs/
  you can see that the NFS code in nfs_subs.c:nfsm_rpchead() generates
  a random starting xid and increments it by a random number 1..255
  each time.  The more general RPC code in krpc_subr.c:krpc_call()
  generates a fully random XID, constrained only to differ from the
  previous one.  This is because the call is synchronous and does
  not permit more than one outstanding request at a time.
  
  Anyway, if you wanted to do this, you'd have to add some checking
  to ensure that a request with that ID isn't already on the rq_list.
  Also, there appear to be some retransmit issues that mitigate against
  recycling them too fast (which is why OpenBSD forbids adjacent
  duplicates), but I haven't studied that in detail.


So in summary:
- Random pool: Few security issues, but on the other hand, why bother?
  It's run-time tunable already.
- TCP ISN: Proposed patch increases chance of TPC ISN reuse by breaking
  timer-based design specified in TCP RFC.  It doesn't appear to have
  any more cryptographic security.
- IP ID: Doesn't change the uses where it matters (DF flag clear).
  Doesn't change the fact that the IDs are still consecutive.  What's the
  freaking point?  And all that modular exponentiation that OpenBSD does
  is a pretty dubious security improvement.
- RPC XID: Broken; don't use.  And what's wrong with incrementing from
  a random start?  If an attacker can see your requests, he can generate
  a fake reply no matter what algorithm you use, and if he can't, then
  the random start is all you need to limit his chances.  The only thing
  a fully random sequence prevents against is that if an attacker can
  somehow tell when they've succeeded, an incrementing sequence lets
  them spoof furter replies easily.  You could apply a first level of
  protection by incrementing them by a random odd number rather than 1,
  but even then, why bother?

And, of ocurse, all of this has performance implications.  Linux is
justifiably proud of keeping down performance bloat by not wasting cycles
on fast paths if it can possibly be helped.  If we *do* find something to
improve, we should look at the goals and design the fastest way possible
to achieve that.  It's not at all clear that the current code patch is
the right implementation even if it *did* do something useful.

Before worrying about the small stuff, could we take a good look at the
Big Stuff?


I like to try to be polite to people contributing patches.  It's a lot
of work and I don't want to dishearten someone just starting.  I'd like
to be polite and encouraging when rejecting patches.

But everyone is so busy ignoring the elephant in the kitchen that I
shall have to forego politeness and shout a little.

It doesn't matter what the license is or whether it's against the Linus
tree or -mm or how the functions are names.

	 ********************************************** 
	************************************************
	*****                                      *****
	****  THIS PATCH DOESN'T FREAKING WORK!!!!  ****
	*****                                      *****
	************************************************
	 ********************************************** 

Ignoring all the *implementation* brokenness, it breaks the network
protocols, doesn't do what it claims to do, and what it tries to do
isn't of any benefit over the existing code.  It's not resting, it's not
stunned, and it's not pining for the fjords.  It just plain doesn't work.

If there are any claimed benefits that you want, the first thing to do
is throw it away, go back to square one, and come up with an algorithm
that actually achieves that benefit.

I keep hearing people boast about how the many eyes reviewing open
source code improves the code quality and makes it harder to insert
back doors into the system.  If something this bad can get this many
comments without anyone pointing out the emperor's clothing arrangements,
the situation is pretty pitiful.


There *are* things in OpenBSD, like randomized port assignment (as opposed
to the linear scan in tcp_v4_get_port()) that would be worth emulating.
Maybe worry about that first?

El mié, 02-02-2005 a las 17:17 +0000, linux@horizon.com escribió:

There *are* things in OpenBSD, like randomized port assignment (as opposed
to the linear scan in tcp_v4_get_port()) that would be worth emulating.
Maybe worry about that first?

Completely agreed with you, I was just trying to help with split up
patches, but, as your analysis shows, it's more a weak implementation
than a real security improvement.

All I can say, just ignore the patch.I will work on other (worthy)
issues that are in a bigger need.

Maybe I would work something out on randomized source ports, as soon as
I get time for it.

Note also that Brad fixed obsd_rand.c code this week, I've added him to
the CC list because there are things that may concern grSecurity he
should be able to comment further on it and discuss whatever concerns
*his* work (which is, BTW, a good thing (tm) to have in mind even if he
didn't send split up patches for each feature, which I really don't
know).

I've just ported it out of grsecurity.

Thanks for your meaningful comments,
Cheers.
-- 
Lorenzo Hernández García-Hierro [off-list ref] 
[1024D/6F2B2DEC] & [2048g/9AE91A22][http://tuxedo-es.org]

On Wed, 02 Feb 2005 18:38:37 +0100
Lorenzo Hernández García-Hierro [off-list ref] wrote:

El mié, 02-02-2005 a las 17:17 +0000, linux@horizon.com escribió:

quoted

There *are* things in OpenBSD, like randomized port assignment (as opposed
to the linear scan in tcp_v4_get_port()) that would be worth emulating.
Maybe worry about that first?

Recent 2.6 does a more advanced form of port randomization already
using address hash at connect time.  tcp_v4_get_port is only used for the case
of applications that explicitly bind to port zero to find a free port.

So the sequence:
	socket(); connect(); 
will assign a random port in a manner similar to sequence number creation

The sequence:
	socket(); bind(); connect();
assigns a simple linear increasing port value.  It could be randomized, but
most applications don't bother binding, so the first case is sufficient.

-- 
Stephen Hemminger	[off-list ref]

On Thu, Feb 03, 2005 at 11:51:27AM -0800, Stephen Hemminger wrote:

Recent 2.6 does a more advanced form of port randomization already
using address hash at connect time.  tcp_v4_get_port is only used for
the case of applications that explicitly bind to port zero to find a
free port.

Is any such randomisation done or planned for UDP?


--L