Return-Path: Delivered-To: apmail-jakarta-tomcat-dev-archive@apache.org Received: (qmail 39512 invoked from network); 30 Dec 2002 17:52:00 -0000 Received: from exchange.sun.com (192.18.33.10) by daedalus.apache.org with SMTP; 30 Dec 2002 17:52:00 -0000 Received: (qmail 13250 invoked by uid 97); 30 Dec 2002 17:52:43 -0000 Delivered-To: qmlist-jakarta-archive-tomcat-dev@jakarta.apache.org Received: (qmail 13086 invoked by uid 97); 30 Dec 2002 17:52:42 -0000 Mailing-List: contact tomcat-dev-help@jakarta.apache.org; run by ezmlm Precedence: bulk List-Unsubscribe: List-Subscribe: List-Help: List-Post: List-Id: "Tomcat Developers List" Reply-To: "Tomcat Developers List" Delivered-To: mailing list tomcat-dev@jakarta.apache.org Received: (qmail 13052 invoked by uid 98); 30 Dec 2002 17:52:41 -0000 X-Antivirus: nagoya (v4218 created Aug 14 2002) Sender: ekr@romeo.rtfm.com To: "Bill Barker" Cc: "Tomcat Developers List" Subject: Re: Duplicate session IDs? References: <00ed01c2afd0$f356b700$d2b32b04@dslverizon.net> Reply-To: EKR From: Eric Rescorla Date: 30 Dec 2002 09:55:44 -0800 In-Reply-To: <00ed01c2afd0$f356b700$d2b32b04@dslverizon.net> Message-ID: Lines: 64 User-Agent: Gnus/5.0808 (Gnus v5.8.8) XEmacs/21.1 (Cuyahoga Valley) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Spam-Rating: daedalus.apache.org 1.6.2 0/1000/N X-Spam-Rating: daedalus.apache.org 1.6.2 0/1000/N "Bill Barker" writes: > As far as I can tell, ManagerBase could really use your expertise on this. > The current algorithm is really bad :-( Ok. I've read the current code, which, as you say, is rather complicated. As far as I can tell, here's how it works: INITIALIZATION (1) Generate an entropy value E which is the ManagerBase instance toString()ed. (2) Get the current time T using system.getCurrentTimeMillis() (3) Mix E and T using XOR, wrapping E appropriately if it's longer T. [0]. Call the output S (4) Generate a new SecureRandom() and seed it using setSeed(S) If this fails, a new Random() is generated and seeded using setSeed(S). [1] SESSION ID GENERATION (1) Fill a 16-byte buffer with Random data from the random generator. (2) Digest the buffer (likely with MD5). (3) Hexify the value [2] SESSION CREATION (1) Generate a session ID. (2) If it already exists, go to (1). So, what's wrong with this code: (1) It's over-complicated. There's no need to hash the output of SecureRandom()--especially when you look at SecureRandom and see that it's hashes on the inside. :) (2) The entropy source isn't very good. There are really two sources of entropy, the initial time value and the toString() value of ManagerBase. The time value can generally be determined to within a few minutes. So, if we say 10 minutes, then there is 16 bits of entropy there. I haven't tested it, but the toString() value is probably an object handle of some kind. On FreeBSD with JDK 1.3, it looks to be the class name followed by a 32-bit ID. Since the class name is known, there are only 32 bits of entropy at best (assuming that the IDs aren't predictable). So, at best there are 48 bits of entropy. Not heartwarming. An attacker can presumably exhaustively search the entire RNG seed space with an effort of 2^48 ops. That said, this algorithm shouldn't repeat. No matter how crappy the seed is, cryptographically secure PRNGs (which SecureRandom supposedly is) generate white output. If you're seeing repeats with this algorithm, then something is very wrong. One possibility is that you're actually falling back to Random, which, as I mentioned above, the code allows for. It's possible you'd see more collisions with such a PRNG, though they should still be pretty rare. -Ekr [0] Note that I haven't verified this algorithm. [1] I don't know how often this happens. [2] I haven't verified this code either. -- To unsubscribe, e-mail: For additional commands, e-mail: