Re: Duplicate session IDs are *common*
It doesn't matter how improbable it is that a conflict will occur. If it's at all possible for a conflict to occur, then you need to perform an explicit uniqueness check. Any conflict, no matter how improbable is unacceptable. Jon - Original Message - From: Eric Rescorla [EMAIL PROTECTED] To: Tomcat Developers List [EMAIL PROTECTED] Sent: Friday, January 10, 2003 1:34 PM Subject: Re: Duplicate session IDs are *common* Glenn Olander [EMAIL PROTECTED] writes: I think you may have misunderstood. I'm just pointing out that, from a user's perspective, a good solution requires two elements: 1) a good PRNG, such as secureRandom 2) a uniqueness guarantee I'm not saying a PRNG is unneeded. I'm just saying a good one like PRNG is good enough as long as it is accompanied by a uniqueness guarantee. Are you saying you want to remove the uniqueness guarantee? I'm saying that a strong PRNG with a sufficiently wide session ID provides a statistical probability of collision so low that there is no need to explicitly check for uniqueness. -Ekr -- [Eric Rescorla [EMAIL PROTECTED] http://www.rtfm.com/ -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED] - To unsubscribe, e-mail: [EMAIL PROTECTED] For additional commands, e-mail: [EMAIL PROTECTED]
Re: Duplicate session IDs are *common*[GFI-T105-3E21F8D3D7B6FFDE]
Impressive. Could you make a small modification and run the same test with 20 concurent threads ? I checked the code and we have plenty of syncs, but you never know. Interesting - java.util.Random is not synchronized, so it is very likely that 2 threads calling the method at the same time will get a collision. java.security.SecureRandom seems ok. Most random sources use some natural entropy ( time, number of interrupts, etc ) and some alghoritm to derive the next number. If 2 calls are too close to each other, we'll not have enough entropy and without the right synchronization you may get the same result ( if the seed wasn't updated ). I did check the code and it looks ok - plenty of synchronized() blocks. But who knows ? Costin Phil Steitz wrote: Using a modified version of Tim Funk's Collide.java, I ran the following dispersion test (using Sun's Linux jdk's 1.3.1_03 and 1.4.1_01): 1. Generate n session id's. 2. For each pair of generated id's, count the number of matching characters in the two strings (i.e., the number of positions where the hex digits are the same). 3. Compare the distribution of matches to the binomial distribution B(16,1/16). The results of one run of 1 (using 1.4.1_01) are attached (along with the code). They show close agreement with the expected distribution. I did several runs with 10-30k sample sizes. Of course, this doesn't *prove* anything; but it does support the hypothesis that p(exact match among two session IDs) ~ 1/2^128. -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*[GFI-T105-3E21F8D3D7B6FFDE]
Costin Manolache wrote: Could you make a small modification and run the same test with 20 concurent threads ? I checked the code and we have plenty of syncs, but you never know. OK -- for this I went to the horse's (or maybe I should say, cat's) mouth with the same result -- collisions still look very unlikely. Here is what I did (using unpatched tomcat 4.1.18, Sun's linux JDK 1.3.1_03): 1. Put a jsp that does nothing but get a session and then invalidate it (sessionTest.jsp) in /webapps/examples; 2. Set up a jmeter test with 20 threads, no delay, hitting sessionTest.jsp 500 times each (SessionTest.jmx); 3. grep 'Created' localhost_examples_log.date.txt sessions.txt; 4. Run DispersionCheck.java (attached) to grab the generated session IDs from sessions.txt and do the comparisons as before. Output is attached as DispersionCheckOut.txt. Note that among the 199,990,000 pairs of session ID's examined, none agreed in more than 13 of 32 hex digits. BTW, I noticed that in my original tests, I was only comparing the first half of the strings (forgot that the hex conversion doubles the length - DOH!). I have attached a corrected version of the standalone program DispersionCheck.java that does all of the comparisons and compares the distribution to B(32,1/16) instead of B(16,1/16). Results are as expected. -Phil I did check the code and it looks ok - plenty of synchronized() blocks. But who knows ? If there is a problem, it could be protection, not just synchronization (which just guarantees serialization). I notice that the valid flag is used to protect sessions from being updated while they are expiring, etc. I posted a (probably insignificant) bug report a couple of weeks ago (http://nagoya.apache.org/bugzilla/show_bug.cgi?id=15746) indicating that a session being recycled could in theory have attributes added by other threads still holding references to it between the time that its attributes are cleared and when its isValid flag is set to false. The result would be that a dirty session would be reused. I have been trying to make this (or other similar things) to happen using jmeter tests to no avail; but I will keep trying. Costin ?xml version=1.0 encoding=UTF-8? node testelement class=org.apache.jmeter.testelement.TestPlan testelement class=org.apache.jmeter.config.Arguments name=TestPlan.user_defined_variables property xml:space=preserve name=TestElement.gui_classorg.apache.jmeter.config.gui.ArgumentsPanel/property property xml:space=preserve name=TestElement.test_classorg.apache.jmeter.config.Arguments/property collection class=java.util.ArrayList name=Arguments.arguments/ property xml:space=preserve name=TestElement.nameArgument List/property /testelement property xml:space=preserve name=TestElement.gui_classorg.apache.jmeter.control.gui.TestPlanGui/property collection class=java.util.LinkedList name=TestPlan.thread_groups/ property xml:space=preserve name=TestElement.test_classorg.apache.jmeter.testelement.TestPlan/property property xml:space=preserve name=TestElement.nameSessionTest/property property xml:space=preserve name=TestPlan.functional_modefalse/property /testelement node testelement class=org.apache.jmeter.threads.ThreadGroup property xml:space=preserve name=TestElement.gui_classorg.apache.jmeter.threads.gui.ThreadGroupGui/property property xml:space=preserve name=TestElement.test_classorg.apache.jmeter.threads.ThreadGroup/property testelement class=org.apache.jmeter.control.LoopController name=ThreadGroup.main_controller property xml:space=preserve name=TestElement.gui_classorg.apache.jmeter.control.gui.LoopControlPanel/property property xml:space=preserve name=LoopController.loops500/property property xml:space=preserve name=TestElement.test_classorg.apache.jmeter.control.LoopController/property property xml:space=preserve name=TestElement.nameLoop Controller/property property xml:space=preserve name=LoopController.continue_foreverfalse/property /testelement property xml:space=preserve name=TestElement.nameThread Group/property property xml:space=preserve name=ThreadGroup.num_threads40/property property xml:space=preserve name=ThreadGroup.ramp_time20/property /testelement node testelement class=org.apache.jmeter.protocol.http.sampler.HTTPSampler property xml:space=preserve name=HTTPSampler.mimetype/ property xml:space=preserve name=TestElement.gui_classorg.apache.jmeter.protocol.http.control.gui.HttpTestSampleGui/property property xml:space=preserve name=HTTPSampler.path/examples/sessionTest.jsp/property collection class=java.util.ArrayList name=AbstractSampler.assertions/ property xml:space=preserve name=HTTPSampler.FILE_FIELD/ property xml:space=preserve name=TestElement.test_classorg.apache.jmeter.protocol.http.sampler.HTTPSampler/property property xml:space=preserve name=HTTPSampler.methodGET/property property xml:space=preserve name=TestElement.nameHTTP Request/property property xml:space=preserve
Re: Duplicate session IDs are *common*
On Fri, 10 Jan 2003, Phil Steitz wrote: Except that hash( i++ . secret).i is generally a lot cheaper and easier to Unfortunately, hashing blows away guaranteed uniqueness (one-way = not 1-1), so if your last step is a hash, you will need to keep the Hence the concatenation with 'i'. Or 'i' and the local ipaddress/port. Dw. -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
On Fri, 10 Jan 2003, Costin Manolache wrote: I find it amazing that 2 people reported beeing hit by meteors (duplicate session ids ) in the same week. Make that 3; I've seen this as well; I suspect this is becauce tomcat saves the sessions across restarts; and then happens to re-generate them in the same way on the second startup. You're right - a counter is better than time. It'll duplicate the counter if tomcat is restarted - so probably the initial value of the counter should be random or derived from time. Well counter + time-of-tomcatstart + ip + port is very unique provided the ip is in the public space. Dw. -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
On Sat, 11 Jan 2003, Phil Steitz wrote: Sorry, missed that. You are correct (also about hashing being a cheap way to get randomization). No, no; just unpredictability. An interesting challenge is how to keep the uniqueness bits either short enough so that the random bits give strong unpredictability by themselves; or to let the uniqueness bits somehow contribute to the unpredictability. Ack; by feeding it into a cryptographic one way function which has a large enough space; as surmized; 128 bits is propably enough. protection and security. My personal opinion is that the best approach is to leave the keys purely random and to leave the recently added patch to test for duplicates in place. Ack. In addition I personlly like the scheme where you can 'check' the ID for validness; i.e. the scheme where you use ID=hash( counter + secret + hisip ).counter so you can short circuit naughty people if the hash does not match. As I've seen many an abuse of this test of duplicates and seen it turned into a DOS due to too much expensive database work at the back. You can augement the above by adding the time of issuance, etc. Dw. -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
on 2003/1/9 10:28 PM, Remy Maucherat [EMAIL PROTECTED] wrote: I can't reproduce an id collision so far. Remy I'm sure you aren't running the same level of concurrency that say a company like Maxis is running. Duplicate the environment and the problems become clear. -jon -- StudioZ.tv /\ Bar/Nightclub/Entertainment 314 11th Street @ Folsom /\ San Francisco http://studioz.tv/ -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*[GFI-T105-3E21F8D3D7B6FFDE]
Using a modified version of Tim Funk's Collide.java, I ran the
following dispersion test (using Sun's Linux jdk's 1.3.1_03 and 1.4.1_01):
1. Generate n session id's.
2. For each pair of generated id's, count the number of matching
characters in the two strings (i.e., the number of positions where the
hex digits are the same).
3. Compare the distribution of matches to the binomial distribution
B(16,1/16).
The results of one run of 1 (using 1.4.1_01) are attached (along
with the code). They show close agreement with the expected
distribution. I did several runs with 10-30k sample sizes. Of course,
this doesn't *prove* anything; but it does support the hypothesis that
p(exact match among two session IDs) ~ 1/2^128.
Matches Count Observed pctExpected pct
0 178039870.3561153515351535 0.3560741304517928
1 189886070.3798101210121012 0.37981240581524567
2 9492989 0.18987876787678767 0.18990620290762283
3 2953095 0.0590678067806780640.05908192979348266
4 640277 0.0128068206820682070.01280108478858791
5 102349 0.0020471847184718470.0020481735661740655
6 12445 2.4892489248924893E-4 2.50332324754608E-4
7 11682.3362336233623362E-5 2.3841173786153143E-5
8 80 1.6001600160016002E-6 1.7880880339614857E-6
9 3 6.000600060006E-8 1.0596077238290286E-7
10 0 0.0 4.944836044535467E-9
11 0 0.0 1.798122198012897E-10
12 0 0.0 4.994783883369158E-12
13 0 0.0 1.0245710529988017E-13
14 0 0.0 1.463672932855431E-15
15 0 0.0 1.3010426069826053E-17
16 0 0.0 5.421010862427522E-20
/*
*
*
* The Apache Software License, Version 1.1
*
* Copyright (c) 1999 The Apache Software Foundation. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
*notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
*notice, this list of conditions and the following disclaimer in
*the documentation and/or other materials provided with the
*distribution.
*
* 3. The end-user documentation included with the redistribution, if
*any, must include the following acknowlegement:
* This product includes software developed by the
*Apache Software Foundation (http://www.apache.org/).
*Alternately, this acknowlegement may appear in the software itself,
*if and wherever such third-party acknowlegements normally appear.
*
* 4. The names The Jakarta Project, Tomcat, and Apache Software
*Foundation must not be used to endorse or promote products derived
*from this software without prior written permission. For written
*permission, please contact [EMAIL PROTECTED]
*
* 5. Products derived from this software may not be called Apache
*nor may Apache appear in their names without prior written
*permission of the Apache Group.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*
*
* This software consists of voluntary contributions made by many
* individuals on behalf of the Apache Software Foundation. For more
* information on the Apache Software Foundation, please see
* http://www.apache.org/.
*
* [Additional notices, if required by prior licensing conditions]
*
*/
import java.io.IOException;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Random;
public class DispersionTest {
protected MessageDigest digest = null;
protected String entropy = null;
protected Random random = null;
protected String randomClass = java.security.SecureRandom;
protected static final String DEFAULT_ALGORITHM = MD5;
protected static final int SESSION_ID_BYTES = 16;
protected static final int
Re: Duplicate session IDs are *common*
I was unable to reproduce a collision too. I took ManagerBase and
converted it to a standalone java program (by stripping out code) to see
if I might get duplicates. But I keep running out of memory near 1
million sessions.
java Collide 1
Generates 1 ids. (Change the number to change the number of sessions
to create)
In case someone is really bored ...
-Tim
Remy Maucherat wrote:
Schnitzer, Jeff wrote:
I've already patched the 4.1.12 version we are running with the fix that
is currently in CVS. Unfortunately our only notification of when the
problem occurs is when users notice (which they probably wouldn't unless
they acquired an administrative session) and choose to inform us. I
won't know the fix worked without waiting some number of weeks.
You could icrement a variable to list the number of duplicates detected.
The patch should guarantee uniqueness of the ids, and this is supposed
to fix the issue.
One thing to contemplate is that if you have 100,000 sessions and you
get 10 new sessions created every second, that's the equivalent of 1
million inadvertent hack attempts every single second. Granted that's
still small compared to the total size of a truly randomly generated
128-bit number, but I wouldn't run a banking application on it.
In theory, the odds are so small it just cannot happen. I can't
reproduce an id collision so far.
Remy
--
To unsubscribe, e-mail:
mailto:[EMAIL PROTECTED]
For additional commands, e-mail:
mailto:[EMAIL PROTECTED]
/*
*
*
* The Apache Software License, Version 1.1
*
* Copyright (c) 1999 The Apache Software Foundation. All rights
* reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
*notice, this list of conditions and the following disclaimer.
*
* 2. Redistributions in binary form must reproduce the above copyright
*notice, this list of conditions and the following disclaimer in
*the documentation and/or other materials provided with the
*distribution.
*
* 3. The end-user documentation included with the redistribution, if
*any, must include the following acknowlegement:
* This product includes software developed by the
*Apache Software Foundation (http://www.apache.org/).
*Alternately, this acknowlegement may appear in the software itself,
*if and wherever such third-party acknowlegements normally appear.
*
* 4. The names The Jakarta Project, Tomcat, and Apache Software
*Foundation must not be used to endorse or promote products derived
*from this software without prior written permission. For written
*permission, please contact [EMAIL PROTECTED]
*
* 5. Products derived from this software may not be called Apache
*nor may Apache appear in their names without prior written
*permission of the Apache Group.
*
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*
*
* This software consists of voluntary contributions made by many
* individuals on behalf of the Apache Software Foundation. For more
* information on the Apache Software Foundation, please see
* http://www.apache.org/.
*
* [Additional notices, if required by prior licensing conditions]
*
*/
import java.io.IOException;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Random;
public class Collide {
protected MessageDigest digest = null;
protected String entropy = null;
protected Random random = null;
protected String randomClass = java.security.SecureRandom;
protected static final String DEFAULT_ALGORITHM = MD5;
protected static final int SESSION_ID_BYTES = 16;
protected String algorithm = DEFAULT_ALGORITHM;
/**
* Return the MessageDigest object to be used for calculating
* session identifiers. If none has been created yet, initialize
* one the first time this method is called.
*/
public
RE: Duplicate session IDs are *common*
On Thu, 9 Jan 2003, Schnitzer, Jeff wrote: One thing to contemplate is that if you have 100,000 sessions and you get 10 new sessions created every second, that's the equivalent of 1 million inadvertent hack attempts every single second. Granted that's still small compared to the total size of a truly randomly generated 128-bit number, but I wouldn't run a banking application on it. Am I right to understand that what is needed is only: - an unguessible ID ? - which is unique within a certain realm ? If that is the case one can tailor the ID to do exactly that. And, espcially, not a bit more. Dw -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
RE: Duplicate session IDs are *common*
Note that you would need 1 million sessions that are active at the same time - if a session expires and the id is reused there is no harm. If I leave my browser open and go for lunch and someone else gets my expired session id, I return and continue browsing, wouldn't that cause problems? Martin -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
Here's a follow-up on the bug report I submitted that started this thread. 1) We confirmed the problem is a duplicate session id. Luckily we were logging session id's. It took a lot of hunting through access logs, but we did indeed find two sessions which were started a couple of minutes apart, with a number of intervening sessions, which had duplicate session id's. The pair of sessions corresponded to the user report of seeing someone else's session data. We're using 4.1.12. 2) I don't believe this is *common* The problem hasn't been duplicated in our app, so I'm not sure I'd call this a common problem, but that's a subjective term. 3) I believe this is a serious vulnerability There should probably be some sort of an alert delivered to tomcat users to let them know of this problem. 4) A simple patch is available It is not necessary to use the head version of tomcat to fix the problem. Simply install your own manager class, which subclasses StandardManager, which has the duplicate session id checking implemented. In other words, a simple patch on an existing tomcat installation can fix this. 5) The strength of the PRNG is largely irrelevant As a user, I wouldn't trust any solution which lacks a check for duplicate session id's, regardless of the strength of the PRNG. The head revision now includes such a check, so I believe the problem has been solved. Even the weakest of PRNG's would generate a collision only rarely, so I wouldn't worry about improving its strength. - Glenn -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
Glenn Olander [EMAIL PROTECTED] writes: 5) The strength of the PRNG is largely irrelevant As a user, I wouldn't trust any solution which lacks a check for duplicate session id's, regardless of the strength of the PRNG. This doesn't seem to me to be a plausible position in view of the fact that all of our security mechanisms absolutely depend on statistical uniqueness of randomly generated large numbers. -Ekr -- [Eric Rescorla [EMAIL PROTECTED]] http://www.rtfm.com/ -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
Jim Jagielski [EMAIL PROTECTED] writes: Eric Rescorla wrote: Glenn Olander [EMAIL PROTECTED] writes: 5) The strength of the PRNG is largely irrelevant As a user, I wouldn't trust any solution which lacks a check for duplicate session id's, regardless of the strength of the PRNG. This doesn't seem to me to be a plausible position in view of the fact that all of our security mechanisms absolutely depend on statistical uniqueness of randomly generated large numbers. These are 2 different points I think. If you randomly generate numbers between 1 and 1,000,000 you will, after a point in time, have duplicate numbers. Yes, but if you randomly generate numbers between 1 and 2^128, you'll have to generate roughly 2^64 random numbers to have a good chance of getting a duplicate. Sure, over time you'll get a duplicate, but in this context over time needs to be measured over a time scale far in excess of the time scale that is interesting. -Ekr -- [Eric Rescorla [EMAIL PROTECTED]] http://www.rtfm.com/ -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
At 10:42 AM -0800 1/10/03, Eric Rescorla wrote: Jim Jagielski [EMAIL PROTECTED] writes: Eric Rescorla wrote: Glenn Olander [EMAIL PROTECTED] writes: 5) The strength of the PRNG is largely irrelevant As a user, I wouldn't trust any solution which lacks a check for duplicate session id's, regardless of the strength of the PRNG. This doesn't seem to me to be a plausible position in view of the fact that all of our security mechanisms absolutely depend on statistical uniqueness of randomly generated large numbers. These are 2 different points I think. If you randomly generate numbers between 1 and 1,000,000 you will, after a point in time, have duplicate numbers. Yes, but if you randomly generate numbers between 1 and 2^128, you'll have to generate roughly 2^64 random numbers to have a good chance of getting a duplicate. Sure, over time you'll get a duplicate, but in this context over time needs to be measured over a time scale far in excess of the time scale that is interesting. Of course, as you said, it depends on the range and the timespan. But it doesn't change the fact that randomness != uniqueness, which is what Glenn's point was I think. -- === Jim Jagielski [|] [EMAIL PROTECTED] [|] http://www.jaguNET.com/ A society that will trade a little liberty for a little order will lose both and deserve neither - T.Jefferson -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
The check will verify that the session id doesn't duplicate another active session. If the session expires - it is still possible ( even if extremely unlikely ) that a user will reuse the same browser window and get into someone's else session. I think this is as likely as someone using a random session ID ( for any decent random generator, the fact that a number has been generated before shouldn't affect the probability of having it generated again - AFAIK ) We could completely eliminate this chance by including the time - so each sessionID will have the start time included in it ( that may be used for other purpose eventually ). Costin Glenn Olander wrote: Here's a follow-up on the bug report I submitted that started this thread. 1) We confirmed the problem is a duplicate session id. Luckily we were logging session id's. It took a lot of hunting through access logs, but we did indeed find two sessions which were started a couple of minutes apart, with a number of intervening sessions, which had duplicate session id's. The pair of sessions corresponded to the user report of seeing someone else's session data. We're using 4.1.12. 2) I don't believe this is *common* The problem hasn't been duplicated in our app, so I'm not sure I'd call this a common problem, but that's a subjective term. 3) I believe this is a serious vulnerability There should probably be some sort of an alert delivered to tomcat users to let them know of this problem. 4) A simple patch is available It is not necessary to use the head version of tomcat to fix the problem. Simply install your own manager class, which subclasses StandardManager, which has the duplicate session id checking implemented. In other words, a simple patch on an existing tomcat installation can fix this. 5) The strength of the PRNG is largely irrelevant As a user, I wouldn't trust any solution which lacks a check for duplicate session id's, regardless of the strength of the PRNG. The head revision now includes such a check, so I believe the problem has been solved. Even the weakest of PRNG's would generate a collision only rarely, so I wouldn't worry about improving its strength. - Glenn -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
Eric Rescorla wrote: Jim Jagielski [EMAIL PROTECTED] writes: Eric Rescorla wrote: Glenn Olander [EMAIL PROTECTED] writes: 5) The strength of the PRNG is largely irrelevant As a user, I wouldn't trust any solution which lacks a check for duplicate session id's, regardless of the strength of the PRNG. This doesn't seem to me to be a plausible position in view of the fact that all of our security mechanisms absolutely depend on statistical uniqueness of randomly generated large numbers. These are 2 different points I think. If you randomly generate numbers between 1 and 1,000,000 you will, after a point in time, have duplicate numbers. Yes, but if you randomly generate numbers between 1 and 2^128, you'll have to generate roughly 2^64 random numbers to have a good chance of getting a duplicate. Sure, over time you'll get a duplicate, but in this context over time needs to be measured over a time scale far in excess of the time scale that is interesting. Adding the startup time doesn't hurt. Or enough bits of the startup time to guarantee a duplicate won't happen in our life. We'll still have the probability that 2 random number generated at the same time ( same millis ) will be identical. :-) Costin -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
On Fri, 10 Jan 2003, Jim Jagielski wrote: But it doesn't change the fact that randomness != uniqueness, which is what Glenn's point was I think. Just as an example; doing on issue syncronized count++; id = count.ipaddr add port if you must :-) gives you a rather unique (but predictable) session id. The uniqueness of the ipaddres obviously relies on the registry function of iana/ripe/et.al. combined with your site/provider IP management. or if it must be un-prediable do something like: on init seed = true-rand... or config-file-entry on issue id = md5( seed . count . ipaddr ); or if you do not trust md5's or find them too expensive id = hash(seed.count.ipaddr).count.ipaddr with hash = md4, md5, sha1, crypt, .. as long as it is one way -and- seed is truly random or manually choosen to be proper. OR if you want to check a session id prior to spending (lookup) cycles on them to counter DoS0-s then do something like id = hash(seed.count.hisip.ipaddr).count.ipaddr.hisip and on accept do hisip = from-accept-stack-info() s,c,i1,i2 = splice(id) i2 == hisip ? i1 == myip ? hash(seed.c.hisip.myip) == s ? now do the expensive stuff add a time-of-issue if needed if you are worried about that. Obviously now the seed -must- be a config secret; as otherwise you cannot restart your server without blowing all sessions out of the water. Dw. -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
I think you may have misunderstood. I'm just pointing out that, from a user's perspective, a good solution requires two elements: 1) a good PRNG, such as secureRandom 2) a uniqueness guarantee I'm not saying a PRNG is unneeded. I'm just saying a good one like PRNG is good enough as long as it is accompanied by a uniqueness guarantee. Are you saying you want to remove the uniqueness guarantee? - Glenn Eric Rescorla [EMAIL PROTECTED] writes: Glenn Olander [EMAIL PROTECTED] writes: 5) The strength of the PRNG is largely irrelevant As a user, I wouldn't trust any solution which lacks a check for duplicate session id's, regardless of the strength of the PRNG. This doesn't seem to me to be a plausible position in view of the fact that all of our security mechanisms absolutely depend on statistical uniqueness of randomly generated large numbers. -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
Jim Jagielski [EMAIL PROTECTED] writes: Of course, as you said, it depends on the range and the timespan. But it doesn't change the fact that randomness != uniqueness, which is what Glenn's point was I think. Perhaps not from a theoretical persective, but from a practical perspective it does. With a sufficiently large session ID, the probability of a collision can be made vastly less than the probability that some sort of programming error (or a hardware error) making an invalid session appear valid. As I said previously, the entire practice of modern security depends on this. -Ekr -- [Eric Rescorla [EMAIL PROTECTED]] http://www.rtfm.com/ -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
Glenn Olander [EMAIL PROTECTED] writes: I think you may have misunderstood. I'm just pointing out that, from a user's perspective, a good solution requires two elements: 1) a good PRNG, such as secureRandom 2) a uniqueness guarantee I'm not saying a PRNG is unneeded. I'm just saying a good one like PRNG is good enough as long as it is accompanied by a uniqueness guarantee. Are you saying you want to remove the uniqueness guarantee? I'm saying that a strong PRNG with a sufficiently wide session ID provides a statistical probability of collision so low that there is no need to explicitly check for uniqueness. -Ekr -- [Eric Rescorla [EMAIL PROTECTED]] http://www.rtfm.com/ -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
Costin Manolache [EMAIL PROTECTED] writes: Eric Rescorla wrote: Jim Jagielski [EMAIL PROTECTED] writes: Eric Rescorla wrote: Glenn Olander [EMAIL PROTECTED] writes: 5) The strength of the PRNG is largely irrelevant As a user, I wouldn't trust any solution which lacks a check for duplicate session id's, regardless of the strength of the PRNG. This doesn't seem to me to be a plausible position in view of the fact that all of our security mechanisms absolutely depend on statistical uniqueness of randomly generated large numbers. These are 2 different points I think. If you randomly generate numbers between 1 and 1,000,000 you will, after a point in time, have duplicate numbers. Yes, but if you randomly generate numbers between 1 and 2^128, you'll have to generate roughly 2^64 random numbers to have a good chance of getting a duplicate. Sure, over time you'll get a duplicate, but in this context over time needs to be measured over a time scale far in excess of the time scale that is interesting. Adding the startup time doesn't hurt. Or enough bits of the startup time to guarantee a duplicate won't happen in our life. No, it doesn't hurt. I just don't think it adds much value. Why not use a simple counter, though? -Ekr -- [Eric Rescorla [EMAIL PROTECTED]] http://www.rtfm.com/ -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
I saw another problem that had similar symptoms to duplicate session ID's. My application was getting collisions between different users having the same session ID using tomcat 4.0.5. I found that the request headers were not being cleared out when they were recycled so that cookies from a current request were added to the cookies on the previous request. Since only the first JSESSIONID cookie is used to obtain the session id both users ended up with the same session id. I solved this in my application by using rewritten URLs instead of cookies. I was unable to find a bug in examining the tomcat code. I did not check the mod_jk code. Steve __ Do you Yahoo!? Yahoo! Mail Plus - Powerful. Affordable. Sign up now. http://mailplus.yahoo.com -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
On Fri, 10 Jan 2003, Glenn Olander wrote: 1) a good PRNG, such as secureRandom Why does it need to be securely random; surely unpredicatable is good enough ? 2) a uniqueness guarantee count++ +:+myip+:+myport is also quite unqiue :-) DW. -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
ID provides a statistical probability of collision so low that there is no need to explicitly check for uniqueness. Or just add a syncronized i++ to make sure. Dw. -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
Dirk-Willem van Gulik [EMAIL PROTECTED] writes: On Fri, 10 Jan 2003, Glenn Olander wrote: 1) a good PRNG, such as secureRandom Why does it need to be securely random; surely unpredicatable is good enough ? Securely random and unpredictable are effectively the same thing. -Ekr -- [Eric Rescorla [EMAIL PROTECTED]] http://www.rtfm.com/ -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
Dirk-Willem van Gulik [EMAIL PROTECTED] writes: ID provides a statistical probability of collision so low that there is no need to explicitly check for uniqueness. Or just add a syncronized i++ to make sure. Yes. There's nothing wrong with what you propose, but it's sort of like saying maybe I should wear a helmet at all times because a meteor might drop on my head. Sure, it could happen, btu it's not the thing I'd worry about. -Ekr -- [Eric Rescorla [EMAIL PROTECTED]] http://www.rtfm.com/ -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
Securely random and unpredictable are effectively the same thing. Depends on your definition; one-way-function((count++) + (secret)) is quite unpredictable; expcet for those knowing the secret. Secure random generators give you a value which is unpredictable for all. And are a lot more expensive generally. Dw -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
On 10 Jan 2003, Eric Rescorla wrote: There's nothing wrong with what you propose, but it's sort of like saying maybe I should wear a helmet at all times because a meteor might drop on my head. Sure, it could happen, btu it's not the thing I'd worry about. Except that hash( i++ . secret).i is generally a lot cheaper and easier to code cross platform than using a true cryptographic random generator with the right tie in with hardware. And it happens to have a hard-hat aspect thrown in as a freebee. Dw -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
Eric Rescorla wrote: Dirk-Willem van Gulik [EMAIL PROTECTED] writes: ID provides a statistical probability of collision so low that there is no need to explicitly check for uniqueness. Or just add a syncronized i++ to make sure. Yes. There's nothing wrong with what you propose, but it's sort of like saying maybe I should wear a helmet at all times because a meteor might drop on my head. Sure, it could happen, btu it's not the thing I'd worry about. I find it amazing that 2 people reported beeing hit by meteors (duplicate session ids ) in the same week. You're right - a counter is better than time. It'll duplicate the counter if tomcat is restarted - so probably the initial value of the counter should be random or derived from time. Costin -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
Costin Manolache wrote: I find it amazing that 2 people reported beeing hit by meteors (duplicate session ids ) in the same week. I find it odd that it actually happened ... You're right - a counter is better than time. It'll duplicate the counter if tomcat is restarted - so probably the initial value of the counter should be random or derived from time. Yes, since sessions are saved and then reloaded by Tomcat on restart. Anyway, as far as I am concerned, I don't see any security problem so far, so I won't make any security bulletin. I'll compile the list of changes since 4.1.18 early next week, for maybe a new alpha release. Remy -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
Combining two messages... Dirk-Willem van Gulik [EMAIL PROTECTED] writes: Securely random and unpredictable are effectively the same thing. Depends on your definition; one-way-function((count++) + (secret)) is quite unpredictable; expcet for those knowing the secret. Secure random generators give you a value which is unpredictable for all. And are a lot more expensive generally. ... Securely random and unpredictable are effectively the same thing. Depends on your definition; one-way-function((count++) + (secret)) is quite unpredictable; expcet for those knowing the secret. Secure random generators give you a value which is unpredictable for all. And are a lot more expensive generally. What you've just described is a form of cryptographically secure PRNG called a message digest in counter mode. This isn't exactly what I would use but it's roughly equivalent. -Ekr -- [Eric Rescorla [EMAIL PROTECTED]] http://www.rtfm.com/ -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
Costin Manolache [EMAIL PROTECTED] writes: Eric Rescorla wrote: Dirk-Willem van Gulik [EMAIL PROTECTED] writes: ID provides a statistical probability of collision so low that there is no need to explicitly check for uniqueness. Or just add a syncronized i++ to make sure. Yes. There's nothing wrong with what you propose, but it's sort of like saying maybe I should wear a helmet at all times because a meteor might drop on my head. Sure, it could happen, btu it's not the thing I'd worry about. I find it amazing that 2 people reported beeing hit by meteors (duplicate session ids ) in the same week. I do too. Something is wrong but I don't know what it is yet. However, the solution isn't to add a bandaid, but rather to examine the code and figure out what's broken. -Ekr -- [Eric Rescorla [EMAIL PROTECTED]] http://www.rtfm.com/ -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
Dirk-Willem van Gulik wrote: On 10 Jan 2003, Eric Rescorla wrote: There's nothing wrong with what you propose, but it's sort of like saying maybe I should wear a helmet at all times because a meteor might drop on my head. Sure, it could happen, btu it's not the thing I'd worry about. Except that hash( i++ . secret).i is generally a lot cheaper and easier to code cross platform than using a true cryptographic random generator with the right tie in with hardware. And it happens to have a hard-hat aspect thrown in as a freebee. Dw Unfortunately, hashing blows away guaranteed uniqueness (one-way = not 1-1), so if your last step is a hash, you will need to keep the meteor helmets handy. The uniqueness bits need to be either left alone or encrypted to preserve uniqueness of the result. I strongly agree with Eric, however, that it is *incredibly* unlikely that the multiple reports of apparent collisions are in fact due to Tomcat's (unpatched) session key generation algorithm. I ran some tests last year on an algorithm very similar to what Tomcat uses (using SHA-1 instead of MD5 after adding some other stuff to the bytes from SecureRandom) and I found that the empirical probablility distribution of the number of matching bytes in pairs of generated strings followed the expected binomial distribution almost exactly. Among other things, this implies that the probability of an exact match among two such strings really is 1/2^n where n is the number of bits in the strings. It also supports the expectation that if you generate m strings, the probability that any two of them are identical is less than C(m,2)/2^n (where C(m,2) = m(m-1)/2 -- the number of pairs that you can make among the m strings). To illustrate how silly the helmets look, here are some examples: n = 128, m = 1 = p(collision) 1.5 E-31 n = 128, m = 10 = p(collision) 1.5 E-29 n = 128, m = 100 = p(collision) 1.5 E-27 n = 64, m = 100 = p(collision) 2.7 E-8 ... n = 128, m = 2^64 ~ 3.4 E+38 = p(collision) .5 (Eric's reasonable chance threshold) If end users are reporting session collisions, this means that they must be happening with frequency too large to reasonably attribute to chance. Therefore, either the applications or Tomcat itself must have some concurrency problems independent of the session ID generation. -Phil -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED] -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
Craig R. McClanahan wrote: On Wed, 8 Jan 2003, Aditya wrote: Date: Wed, 08 Jan 2003 22:36:58 -0800 From: Aditya [EMAIL PROTECTED] Reply-To: Tomcat Developers List [EMAIL PROTECTED] To: Tomcat Developers List [EMAIL PROTECTED] Subject: Re: Duplicate session IDs are *common* On Wed, 08 Jan 2003 19:37:28 -0800, Costin Manolache [EMAIL PROTECTED] said: The default is java.security.SecureRandom - and should give enough randomness. There is a change on head ( that would work with 5.0 - but it can be backported ) that allow you to use /dev/urandom ( or another source - it can be a pipe or something like that ). what about hashing the random part with System.currentTimeMillis() so that even the vanishingly small probability of a collision is avoided? Or would that be too expensive? The better check is the one that has been implemented -- if whatever session id you just calculated (for a new session) is already in use, pick another one. I think that is done in ManagerBase.java Adi Craig -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED] -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
Schnitzer, Jeff wrote: For whatever reason, be it the seed algorithm or the hashing algorithm or something else that degenerates the randomness - the duplicate session ID problem is very, very common. I discovered this problem because a few of our users suddenly found themselves with the sessions from administrative accounts. Luckily they alerted us instead of causing mayhem. There were at least three separate occasions of this in the last week - that we heard about. We have also seen this a number of times with other game components - users suddenly finding themselves logged in as other people. It probably explains the recent post to tomcat-user included below. Here at my company this problem caused about as much panic as a wildfire breaking out in the machine room (read: LOTS). I humbly suggest raising the level of concern a bit; post a security bulletin, etc. We have to make sure the problem is real before putting out any advisory. You should patch the ManagerBase class to the latest version to see if it helps (compile the latest version, and put it in $CATALINA_HOME/server/classes/org/apache/catalina/session). A compiled version is attached to this email if you can't get it easily. However: - We did not have any reports before 4.1.18 that the algorithm used was weak; it was actually believed it was not, and it had been around for a long time (I do not believe it was touched at all for months). - A MD5 hash occurs after getting the SecureRandom. This looks like a mistake, and decreases the quality of the random a lot, but given the quality of MD5, that shouldn't be noticeable in the real world. - If collisions *do* actyually happen, then it is a security problem and the patch to the StandardManager should fix it. However, it would also indicate that the ids generated can likely be guessed by an attacker, so we also have to fix the algorithm. Remy ManagerBase.class Description: Binary data -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
Remy Maucherat [EMAIL PROTECTED] writes: - A MD5 hash occurs after getting the SecureRandom. This looks like a mistake, and decreases the quality of the random a lot, but given the quality of MD5, that shouldn't be noticeable in the real world. I think that the MD5 is pointless but it shouldn't decrease the quality of the randomness to any interesting degree. -Ekr -- [Eric Rescorla [EMAIL PROTECTED]] http://www.rtfm.com/ -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
On 9 Jan 2003, Eric Rescorla wrote: Remy Maucherat [EMAIL PROTECTED] writes: - A MD5 hash occurs after getting the SecureRandom. This looks like a mistake, and decreases the quality of the random a lot, but given the quality of MD5, that shouldn't be noticeable in the real world. I think that the MD5 is pointless but it shouldn't decrease the quality of the randomness to any interesting degree. It makes the value less predictible. But as it adds no information (and one could argule only looses it if the initial information had more than 128bits of randonm (which is highly unlikely)) it does not change the 'randomness' itself. You propably want to argue -what- sort of randomness you want - unpredicable session id's - a unique session id - always a guaranteed different session id. - session id with no information. Pick one, pick two, but if you pick three or more you are going to have a hard time. Dw -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
Dirk-Willem van Gulik [EMAIL PROTECTED] writes: On 9 Jan 2003, Eric Rescorla wrote: Remy Maucherat [EMAIL PROTECTED] writes: - A MD5 hash occurs after getting the SecureRandom. This looks like a mistake, and decreases the quality of the random a lot, but given the quality of MD5, that shouldn't be noticeable in the real world. I think that the MD5 is pointless but it shouldn't decrease the quality of the randomness to any interesting degree. It makes the value less predictible. Not if the initial value came out of SecureRandom in the first place. You propably want to argue -what- sort of randomness you want - unpredicable session id's - a unique session id - always a guaranteed different session id. - session id with no information. Pick one, pick two, but if you pick three or more you are going to have a hard time. If you use a cryptographically secure PRNG you can get 1,2,4 and 3 with very high probability. The probability of two properly randomly generated 128-bit numbers colliding is negligible. -Ekr -- [Eric Rescorla [EMAIL PROTECTED]] http://www.rtfm.com/ -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
RE: Duplicate session IDs are *common*
I've already patched the 4.1.12 version we are running with the fix that is currently in CVS. Unfortunately our only notification of when the problem occurs is when users notice (which they probably wouldn't unless they acquired an administrative session) and choose to inform us. I won't know the fix worked without waiting some number of weeks. One thing to contemplate is that if you have 100,000 sessions and you get 10 new sessions created every second, that's the equivalent of 1 million inadvertent hack attempts every single second. Granted that's still small compared to the total size of a truly randomly generated 128-bit number, but I wouldn't run a banking application on it. Jeff Schnitzer -Original Message- From: Remy Maucherat Subject: Re: Duplicate session IDs are *common* Date: Thu, 09 Jan 2003 02:57:23 -0800 We have to make sure the problem is real before putting out any advisory. You should patch the ManagerBase class to the latest version to see if it helps (compile the latest version, and put it in $CATALINA_HOME/server/classes/org/apache/catalina/session). A compiled version is attached to this email if you can't get it easily. However: - We did not have any reports before 4.1.18 that the algorithm used was weak; it was actually believed it was not, and it had been around for a long time (I do not believe it was touched at all for months). - A MD5 hash occurs after getting the SecureRandom. This looks like a mistake, and decreases the quality of the random a lot, but given the quality of MD5, that shouldn't be noticeable in the real world. - If collisions *do* actyually happen, then it is a security problem and the patch to the StandardManager should fix it. However, it would also indicate that the ids generated can likely be guessed by an attacker, so we also have to fix the algorithm. -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
Schnitzer, Jeff wrote: I've already patched the 4.1.12 version we are running with the fix that is currently in CVS. Unfortunately our only notification of when the problem occurs is when users notice (which they probably wouldn't unless they acquired an administrative session) and choose to inform us. I won't know the fix worked without waiting some number of weeks. You could icrement a variable to list the number of duplicates detected. The patch should guarantee uniqueness of the ids, and this is supposed to fix the issue. One thing to contemplate is that if you have 100,000 sessions and you get 10 new sessions created every second, that's the equivalent of 1 million inadvertent hack attempts every single second. Granted that's still small compared to the total size of a truly randomly generated 128-bit number, but I wouldn't run a banking application on it. In theory, the odds are so small it just cannot happen. I can't reproduce an id collision so far. Remy -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
RE: Duplicate session IDs are *common*
Schnitzer, Jeff wrote: I've already patched the 4.1.12 version we are running with the fix that is currently in CVS. Unfortunately our only notification of when the problem occurs is when users notice (which they probably wouldn't unless they acquired an administrative session) and choose to inform us. I won't know the fix worked without waiting some number of weeks. One thing to contemplate is that if you have 100,000 sessions and you get 10 new sessions created every second, that's the equivalent of 1 million inadvertent hack attempts every single second. Granted that's still small compared to the total size of a truly randomly generated 128-bit number, but I wouldn't run a banking application on it. I would check the application too - Craig had a very good point. Even with java.util.Random it is very unlikely to generate 2 identical numbers close enough for 2 current sessions to be swaped. It's easy to add a log line when a duplicate is detected. One think is pretty sure - with the patch applied you can't have duplicated IDs. Note that you would need 1 million sessions that are active at the same time - if a session expires and the id is reused there is no harm. Costin Jeff Schnitzer -Original Message- From: Remy Maucherat Subject: Re: Duplicate session IDs are *common* Date: Thu, 09 Jan 2003 02:57:23 -0800 We have to make sure the problem is real before putting out any advisory. You should patch the ManagerBase class to the latest version to see if it helps (compile the latest version, and put it in $CATALINA_HOME/server/classes/org/apache/catalina/session). A compiled version is attached to this email if you can't get it easily. However: - We did not have any reports before 4.1.18 that the algorithm used was weak; it was actually believed it was not, and it had been around for a long time (I do not believe it was touched at all for months). - A MD5 hash occurs after getting the SecureRandom. This looks like a mistake, and decreases the quality of the random a lot, but given the quality of MD5, that shouldn't be noticeable in the real world. - If collisions *do* actyually happen, then it is a security problem and the patch to the StandardManager should fix it. However, it would also indicate that the ids generated can likely be guessed by an attacker, so we also have to fix the algorithm. -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
Schnitzer, Jeff wrote: For whatever reason, be it the seed algorithm or the hashing algorithm or something else that degenerates the randomness - the duplicate session ID problem is very, very common. I discovered this problem because a few of our users suddenly found themselves with the sessions from administrative accounts. Luckily they alerted us instead of causing mayhem. There were at least three separate occasions of this in the last week - that we heard about. We have also seen this a number of times with other game components - users suddenly finding themselves logged in as other people. It probably explains the recent post to tomcat-user included below. Here at my company this problem caused about as much panic as a wildfire breaking out in the machine room (read: LOTS). I humbly suggest raising the level of concern a bit; post a security bulletin, etc. What version of tomcat ? Are you on Linux ? What randomClass are you using ? How many sessions are usually generated ? The default is java.security.SecureRandom - and should give enough randomness. There is a change on head ( that would work with 5.0 - but it can be backported ) that allow you to use /dev/urandom ( or another source - it can be a pipe or something like that ). Costin -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
On Wed, 8 Jan 2003, Costin Manolache wrote: Date: Wed, 08 Jan 2003 19:37:28 -0800 From: Costin Manolache [EMAIL PROTECTED] Reply-To: Tomcat Developers List [EMAIL PROTECTED] To: [EMAIL PROTECTED] Subject: Re: Duplicate session IDs are *common* Schnitzer, Jeff wrote: For whatever reason, be it the seed algorithm or the hashing algorithm or something else that degenerates the randomness - the duplicate session ID problem is very, very common. I discovered this problem because a few of our users suddenly found themselves with the sessions from administrative accounts. Luckily they alerted us instead of causing mayhem. There were at least three separate occasions of this in the last week - that we heard about. We have also seen this a number of times with other game components - users suddenly finding themselves logged in as other people. It probably explains the recent post to tomcat-user included below. Here at my company this problem caused about as much panic as a wildfire breaking out in the machine room (read: LOTS). I humbly suggest raising the level of concern a bit; post a security bulletin, etc. What version of tomcat ? Are you on Linux ? What randomClass are you using ? How many sessions are usually generated ? The default is java.security.SecureRandom - and should give enough randomness. There is a change on head ( that would work with 5.0 - but it can be backported ) that allow you to use /dev/urandom ( or another source - it can be a pipe or something like that ). Even though duplicate session ids are *possible* (because Tomcat doesn't check for it), the 99.9% cause of this kind of a problem is application programming errors like using an instance (or static) variable in a servlet to store per-request state information. That only works if the servlet never processes more than one request at a time. Based on my experience, I don't believe this is a *common* problem, but it is a problem that needs to be addressed. Costin Craig -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
On Wed, 08 Jan 2003 19:37:28 -0800, Costin Manolache [EMAIL PROTECTED] said: The default is java.security.SecureRandom - and should give enough randomness. There is a change on head ( that would work with 5.0 - but it can be backported ) that allow you to use /dev/urandom ( or another source - it can be a pipe or something like that ). what about hashing the random part with System.currentTimeMillis() so that even the vanishingly small probability of a collision is avoided? Or would that be too expensive? Adi -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs are *common*
On Wed, 8 Jan 2003, Aditya wrote: Date: Wed, 08 Jan 2003 22:36:58 -0800 From: Aditya [EMAIL PROTECTED] Reply-To: Tomcat Developers List [EMAIL PROTECTED] To: Tomcat Developers List [EMAIL PROTECTED] Subject: Re: Duplicate session IDs are *common* On Wed, 08 Jan 2003 19:37:28 -0800, Costin Manolache [EMAIL PROTECTED] said: The default is java.security.SecureRandom - and should give enough randomness. There is a change on head ( that would work with 5.0 - but it can be backported ) that allow you to use /dev/urandom ( or another source - it can be a pipe or something like that ). what about hashing the random part with System.currentTimeMillis() so that even the vanishingly small probability of a collision is avoided? Or would that be too expensive? The better check is the one that has been implemented -- if whatever session id you just calculated (for a new session) is already in use, pick another one. Adi Craig -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs?
Bill Barker wrote: Schnitzer, Jeff [EMAIL PROTECTED] writes: The standard fix for this is to use a cryptographic pseudo-random number generator, such as Java's SecureRandom. SecureRandom automatically seeds itself from allegedly random system data. the probability that two sufficiently long random numbers (e.g. 16 bytes) will collide is vanishing. (E.g. with a 16-byte session ID, you'd have to generate 2^60 session IDs to have a reasonable chance of collision. Nice to have you back Eric :-) As far as I can tell, ManagerBase could really use your expertise on this. The current algorithm is really bad :-( Yes, it would be nice to have a new one for Tomcat 5. Remy -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs?
I can also report that I've seen this happen when the system is under load. We had a user log in and gain access to another user's session. I'm sure you can understand that makes it a very serious bug for security-sensitive applications, perhaps even deserving some kind of security alert announcement. Tim's patch is robust and seems like a good candidate for inclusion in the source at the earliest opportunity since it ensures that no duplicate session id's will be commisioned (and ManagerBase already uses SecureRandom). Eric Rescorla wrote: The standard fix for this is to use a cryptographic pseudo-random number generator, such as Java's SecureRandom. SecureRandom automatically seeds itself from allegedly random system data. the probability that two sufficiently long random numbers (e.g. 16 bytes) will collide is vanishing. (E.g. with a 16-byte session ID, you'd have to generate 2^60 session IDs to have a reasonable chance of collision. -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs?
Glenn Olander wrote: I can also report that I've seen this happen when the system is under load. We had a user log in and gain access to another user's session. I'm sure you can understand that makes it a very serious bug for security-sensitive applications, perhaps even deserving some kind of security alert announcement. Tim's patch is robust and seems like a good candidate for inclusion in the source at the earliest opportunity since it ensures that no duplicate session id's will be commisioned (and ManagerBase already uses SecureRandom). Bill enabled the (ugly but very safe) code for getting rid of duplicates. That will be in 4.1.x, at least for now. Experimentation on new and cleaner algorithms should happen in the 5.0.x branch first (and then it may be ported, although I'd say it shouldn't as the current code gets the job done relatively well and is tested). Remy -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs?
fyi, the version he checked in contains a bug. It should append jvmRoute
within
the loop. It should look like this:
String sessionId = generateSessionId();
String jvmRoute = getJvmRoute();
// @todo Move appending of jvmRoute generateSessionId()???
if (jvmRoute != null) {
sessionId += '.' + jvmRoute;
}
synchronized (sessions) {
while (sessions.get(sessionId) != null){// Guarantee
uniqueness
sessionId = generateSessionId();
if (jvmRoute != null) {
sessionId += '.' + jvmRoute;
}
}
}
session.setId(sessionId);
return (session);
Remy Maucherat wrote:
Glenn Olander wrote:
I can also report that I've seen this happen when the system is
under load. We had a
user log in and gain access to another user's session. I'm sure
you can understand that
makes it a very serious bug for security-sensitive applications,
perhaps even deserving
some kind of security alert announcement.
Tim's patch is robust and seems like a good candidate for
inclusion in the source
at the earliest opportunity since it ensures that no duplicate
session id's will be
commisioned (and ManagerBase already uses SecureRandom).
Bill enabled the (ugly but very safe) code for getting rid of
duplicates. That will be in 4.1.x, at least for now.
--
To unsubscribe, e-mail: mailto:[EMAIL PROTECTED]
For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs?
This looks true by the looks of:
http://cvs.apache.org/viewcvs/jakarta-tomcat-4.0/catalina/src/share/org/apache/catalina/session/ManagerBase.java?rev=1.15content-type=text/vnd.viewcvs-markup
The while loop is looking for one session ID, and if JVM route is set, a
different session ID is saved. (Since jvmRoute is attached AFTER dup check)
What is missing is the addition of jvmRoute to generateSessionId()
Attached is a patch against the HEAD of ManagerBase.java.
My original patch also provided a debug message and diff against
LocalStrings.properties to log that a dup sessionId was created. I would
be curious if that piece of code would ever be run. Personally - I doubt
it. But we'd have proof that a duplicate sessionID was created with the
debug message. If your want that patch instead - I can provide that on
demand.
-Tim
Glenn Olander wrote:
fyi, the version he checked in contains a bug. It should append jvmRoute
within
the loop. It should look like this:
String sessionId = generateSessionId();
String jvmRoute = getJvmRoute();
// @todo Move appending of jvmRoute generateSessionId()???
if (jvmRoute != null) {
sessionId += '.' + jvmRoute;
}
synchronized (sessions) {
while (sessions.get(sessionId) != null){// Guarantee
uniqueness
sessionId = generateSessionId();
if (jvmRoute != null) {
sessionId += '.' + jvmRoute;
}
}
}
session.setId(sessionId);
return (session);
Index: ManagerBase.java
===
RCS file:
/home/cvspublic/jakarta-tomcat-4.0/catalina/src/share/org/apache/catalina/session/ManagerBase.java,v
retrieving revision 1.15
diff -r1.15 ManagerBase.java
138,139c138,139
---
293,294c293,294
---
588,593d587
String jvmRoute = getJvmRoute();
// @todo Move appending of jvmRoute generateSessionId()???
if (jvmRoute != null) {
sessionId += '.' + jvmRoute;
session.setId(sessionId);
}
693a688,693
String jvmRoute = getJvmRoute();
if (jvmRoute != null) {
result.append('.').append(jvmRoute);
}
--
To unsubscribe, e-mail: mailto:[EMAIL PROTECTED]
For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs?
Bill Barker [EMAIL PROTECTED] 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: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs?
Good catch!
I'll apply the patch (if somebody doesn't beat me to it).
- Original Message -
From: Glenn Olander [EMAIL PROTECTED]
To: Tomcat Developers List [EMAIL PROTECTED]
Sent: Monday, December 30, 2002 8:05 AM
Subject: Re: Duplicate session IDs?
fyi, the version he checked in contains a bug. It should append jvmRoute
within
the loop. It should look like this:
String sessionId = generateSessionId();
String jvmRoute = getJvmRoute();
// @todo Move appending of jvmRoute generateSessionId()???
if (jvmRoute != null) {
sessionId += '.' + jvmRoute;
}
synchronized (sessions) {
while (sessions.get(sessionId) != null){// Guarantee
uniqueness
sessionId = generateSessionId();
if (jvmRoute != null) {
sessionId += '.' + jvmRoute;
}
}
}
session.setId(sessionId);
return (session);
Remy Maucherat wrote:
Glenn Olander wrote:
I can also report that I've seen this happen when the system is
under load. We had a
user log in and gain access to another user's session. I'm sure
you can understand that
makes it a very serious bug for security-sensitive applications,
perhaps even deserving
some kind of security alert announcement.
Tim's patch is robust and seems like a good candidate for
inclusion in the source
at the earliest opportunity since it ensures that no duplicate
session id's will be
commisioned (and ManagerBase already uses SecureRandom).
Bill enabled the (ugly but very safe) code for getting rid of
duplicates. That will be in 4.1.x, at least for now.
--
To unsubscribe, e-mail:
mailto:[EMAIL PROTECTED]
For additional commands, e-mail:
mailto:[EMAIL PROTECTED]
--
To unsubscribe, e-mail: mailto:[EMAIL PROTECTED]
For additional commands, e-mail: mailto:[EMAIL PROTECTED]
RE: Duplicate session IDs?
Yes that's true if the monotonically increasing value is added to the random number _before_ the hash... and even worse, there is nothing that guarantees that two numbers won't hash to the same value so we're back to the duplicate session id problem. What I was suggesting is adding the integer to the session id _after_ hashing: ASDFASFDASFDASF00012 [hashed random][counter] This would guarantee that every session id is unique, and wouldn't require any synchronization (operator ++ on any integer smaller than a long is guaranteed atomic, right?). Jeff Schnitzer [EMAIL PROTECTED] The Sims Online -Original Message- From: Tim Funk Subject: Re: Duplicate session IDs? Date: Wed, 25 Dec 2002 05:54:27 -0800 Any kind of monotonic increase is bad security. Since everyone can view the source, everyone knows the algorithm. With enough brute force, someone can guess session ids. -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs?
Schnitzer, Jeff [EMAIL PROTECTED] writes: Yes that's true if the monotonically increasing value is added to the random number _before_ the hash... and even worse, there is nothing that guarantees that two numbers won't hash to the same value so we're back to the duplicate session id problem. What I was suggesting is adding the integer to the session id _after_ hashing: ASDFASFDASFDASF00012 [hashed random][counter] This would guarantee that every session id is unique, and wouldn't require any synchronization (operator ++ on any integer smaller than a long is guaranteed atomic, right?). The standard fix for this is to use a cryptographic pseudo-random number generator, such as Java's SecureRandom. SecureRandom automatically seeds itself from allegedly random system data. the probability that two sufficiently long random numbers (e.g. 16 bytes) will collide is vanishing. (E.g. with a 16-byte session ID, you'd have to generate 2^60 session IDs to have a reasonable chance of collision. -Ekr -- [Eric Rescorla [EMAIL PROTECTED]] http://www.rtfm.com/ -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs?
- Original Message - From: Eric Rescorla [EMAIL PROTECTED] To: Tomcat Developers List [EMAIL PROTECTED] Sent: Sunday, December 29, 2002 10:05 PM Subject: Re: Duplicate session IDs? Schnitzer, Jeff [EMAIL PROTECTED] writes: Yes that's true if the monotonically increasing value is added to the random number _before_ the hash... and even worse, there is nothing that guarantees that two numbers won't hash to the same value so we're back to the duplicate session id problem. What I was suggesting is adding the integer to the session id _after_ hashing: ASDFASFDASFDASF00012 [hashed random][counter] This would guarantee that every session id is unique, and wouldn't require any synchronization (operator ++ on any integer smaller than a long is guaranteed atomic, right?). The standard fix for this is to use a cryptographic pseudo-random number generator, such as Java's SecureRandom. SecureRandom automatically seeds itself from allegedly random system data. the probability that two sufficiently long random numbers (e.g. 16 bytes) will collide is vanishing. (E.g. with a 16-byte session ID, you'd have to generate 2^60 session IDs to have a reasonable chance of collision. Nice to have you back Eric :-) As far as I can tell, ManagerBase could really use your expertise on this. The current algorithm is really bad :-( -Ekr -- [Eric Rescorla [EMAIL PROTECTED]] http://www.rtfm.com/ -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED] -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs?
Eric Rescorla wrote: Schnitzer, Jeff [EMAIL PROTECTED] writes: Yes that's true if the monotonically increasing value is added to the random number _before_ the hash... and even worse, there is nothing that guarantees that two numbers won't hash to the same value so we're back to the duplicate session id problem. What I was suggesting is adding the integer to the session id _after_ hashing: ASDFASFDASFDASF00012 [hashed random][counter] This would guarantee that every session id is unique, and wouldn't require any synchronization (operator ++ on any integer smaller than a long is guaranteed atomic, right?). The standard fix for this is to use a cryptographic pseudo-random number generator, such as Java's SecureRandom. SecureRandom automatically seeds itself from allegedly random system data. the probability that two sufficiently long random numbers (e.g. 16 bytes) will collide is vanishing. (E.g. with a 16-byte session ID, you'd have to generate 2^60 session IDs to have a reasonable chance of collision. -Ekr The hashed random above is generated using SecureRandom. (Apparently) for added security, the resulting byte array is then hashed, replaced with the (truncated down to 16 bytes) hash and converted to a hex string. Some attempt is made to make the original seed used by SecureRandom hard to recover, so one could ask why the hash needs to be applied at all. While hashing blows away the more or less guaranteed long period of the random number generator, the result should still have very good dispersion properties making it remarkable that people are reporting collisions. Makes you wonder if there is something else going on I agree with Jeff that it would certainly be cleaner to dedicate a segment of the session ID to guarantee uniqueness than to check for collisions after the fact. One way to do this would be to encyrpt (not hash) host/JVM identifer + a time stamp or counter + random bytes from SecureRandom and use this (padded as necessary) as the session ID. Encryption will preserve both uniqueness and dispersion. The encryption key could be randomly generated at server startup time. -Phil -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs?
Any kind of monotonic increase is bad security. Since everyone can view the source, everyone knows the algorithm. With enough brute force, someone can guess session ids. Lets start in the simple scenario: first session_id = 1, next session_id = 2, ... Too simple, yes. But tomcat digests the incoming random number (in this scenario, its not random, its sequential) using SHA1. So the incoming random number is transformed into a wicked long string. The string can't be transformed into its original number because ... well thats the way message digesting works. I don't understand the math theory behind it. (Thankfully - I don't have to) So in this scenario, tomcat generates (hypothecially): 1 -- A3BED12F80B5CF1CB8C3A9359888BBD9 2 -- 898EF7B975B13E527856E8F3C6F30DAC .. The nice thing about the digester is similar incoming data 1,2,3,or timmy,tommy,tammy will all be transformed into vastly different looking strings. Without knowing the algorthim that performs the transformation, using a sequential number as the source input is reasonably OK. Security through obscurity - woohoo. But tomcat is open source (or lets say someone peeks at the source). Now someone knows the algorithm. There is only one way to determine the source random number: brute force (since the transformed string can't be un-digested into its source input). Since I know the algorithm - I can brute force all numbers until I get a sessionId match. I can make things easier by guessing where to start my guessing of numbers by estimating your site traffic. Or the source code might provide hints on where to start. (Seed sequential number to 0 on restart - or current time in milliseconds on restart) Creating a new session id is not extremely cpu intensive, so I could probably determine the source number pretty quick. From there I would try to obtain another session id. Then use brute force that to get derive the second input source number. From there I can start guestimating what sessions are available. And if I keep enough notes, future attacks will be easier because I would have good estimations on where your source input number is. By using a using a random number, my attacker can brute force the sessionid to get the source random number. But the next number out of the randon number gen is ... random. So the attacker can't easily guess session ids. But this is also based on the assumption the random number generator does is a good one since all computer random number generators are not random. (Use google to get more info on that). Anyone - please slap me up side the head if this is in anyway incorrect. -Tim Jon Scott Stevens wrote: on 2002/12/24 5:52 AM, Tim Funk [EMAIL PROTECTED] wrote: I hope you were joking about the monotonic increase of sessionIds. If that were done - it would be trivial to steal another's sessionId by guessing. How is that? laskdfowifjwo2i3jofij2oi3jofwjieogih934htwo4i1 io2oiwejofiwjoijr9238jr9iejofij2oi3jro23ij2i32 Aslkdjfalskdjflaksjdflkasjdflkjlsdkjflaskjdfl3 lakdjflkasjdflkjwoeirjowiejo2ij4o3ij4o2i4o3jo4 flaksjdflksajdflkjsdlfkjsdlkfalsdjflasdkflksd5 laksdfjlkasjdflaskjdflksjdfowiejreowiefjowiee6 The only problem with it is that the session id would grow in length as more digits are added. I don't see how adding a number would make things more easily to steal (as long as the first part is unique random garbage), but maybe I'm missing something. It would be best to do something like this: SHA1(laskdfowifjwo2i3jofij2oi3jofwjieogih934htwo4i1) SHA1(io2oiwejofiwjoijr9238jr9iejofij2oi3jro23ij2i32) SHA1(Aslkdjfalskdjflaksjdflkasjdflkjlsdkjflaskjdfl3) SHA1(lakdjflkasjdflkjwoeirjowiejo2ij4o3ij4o2i4o3jo4) SHA1(flaksjdflksajdflkjsdlfkjsdlkfalsdjflasdkflksd5) ... SHA1(laksdfjlkasjdflaskjdflksjdfowiejreowiefjowiee600) So that you always have a uniform length. Just trying to learn... -jon -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs?
I agree that there is a tiny chance this could happen. It seems the
original uniquenes code had a bug in it because it did not attach the
jvmRoute after re-generating the sessionId. Thats why it was probably
commented out.
I hope you were joking about the monotonic increase of sessionIds. If
that were done - it would be trivial to steal another's sessionId by
guessing.
Anyhoo, attached is patch which does the following:
- Moves the appending of jvmRoute into generateSessionId()
- uncomments the duplicate session check
- When debug is turned ON (=1) it complains a dup sessionId was created
when the occurance happens
If there is interest in this - I can throw it into bugzilla so it
doesn't get lost.
-Tim
Schnitzer, Jeff wrote:
What prevents Tomcat from issuing duplicate session IDs? From the code
in ManagerBase, it doesn't look like anything prevents it - the only
unique value in the ID is a random number. In fact, the code which
would guarantee uniqueness is commented out.
I believe we have seen a problem with duplicate session ids on our
production (high-traffic) site. It's hard to say exactly because the
problem is very rare, but we have had at least two reports from users
that they log in and see data from other people's accounts.
If Tomcat is generating session ids randomly, this is a _HUGE_ problem.
Why not just include a monotonically increasing integer in the session
string?
Thanks,
Jeff Schnitzer
[EMAIL PROTECTED]
The Sims Online
Index: ManagerBase.java
===
RCS file:
/home/cvspublic/jakarta-tomcat-4.0/catalina/src/share/org/apache/catalina/session/ManagerBase.java,v
retrieving revision 1.12
diff -r1.12 ManagerBase.java
138,139c138,139
---
293,294c293,294
---
582,588c582
String jvmRoute = getJvmRoute();
// @todo Move appending of jvmRoute generateSessionId()???
if (jvmRoute != null) {
sessionId += '.' + jvmRoute;
session.setId(sessionId);
}
/*
---
590c584
while (sessions.get(sessionId) != null)// Guarantee uniqueness
---
while (sessions.get(sessionId) != null){// Guarantee uniqueness
591a586,588
if (debug = 1)
log(sm.getString(managerBase.duplicateSessionId));
}
593c590
*/
---
693a691,696
String jvmRoute = getJvmRoute();
if (jvmRoute != null) {
result.append('.').append(jvmRoute);
}
Index: LocalStrings.properties
===
RCS file:
/home/cvspublic/jakarta-tomcat-4.0/catalina/src/share/org/apache/catalina/session/LocalStrings.properties,v
retrieving revision 1.11
diff -r1.11 LocalStrings.properties
22a23
managerBase.duplicateSessionId=Created duplicate sessionId. Regenerating another
sessionId now.
63a65
--
To unsubscribe, e-mail: mailto:[EMAIL PROTECTED]
For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs?
on 2002/12/24 5:52 AM, Tim Funk [EMAIL PROTECTED] wrote: I hope you were joking about the monotonic increase of sessionIds. If that were done - it would be trivial to steal another's sessionId by guessing. How is that? laskdfowifjwo2i3jofij2oi3jofwjieogih934htwo4i1 io2oiwejofiwjoijr9238jr9iejofij2oi3jro23ij2i32 Aslkdjfalskdjflaksjdflkasjdflkjlsdkjflaskjdfl3 lakdjflkasjdflkjwoeirjowiejo2ij4o3ij4o2i4o3jo4 flaksjdflksajdflkjsdlfkjsdlkfalsdjflasdkflksd5 laksdfjlkasjdflaskjdflksjdfowiejreowiefjowiee6 The only problem with it is that the session id would grow in length as more digits are added. I don't see how adding a number would make things more easily to steal (as long as the first part is unique random garbage), but maybe I'm missing something. It would be best to do something like this: SHA1(laskdfowifjwo2i3jofij2oi3jofwjieogih934htwo4i1) SHA1(io2oiwejofiwjoijr9238jr9iejofij2oi3jro23ij2i32) SHA1(Aslkdjfalskdjflaksjdflkasjdflkjlsdkjflaskjdfl3) SHA1(lakdjflkasjdflkjwoeirjowiejo2ij4o3ij4o2i4o3jo4) SHA1(flaksjdflksajdflkjsdlfkjsdlkfalsdjflasdkflksd5) ... SHA1(laksdfjlkasjdflaskjdflksjdfowiejreowiefjowiee600) So that you always have a uniform length. Just trying to learn... -jon -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
Re: Duplicate session IDs?
I wasn't suggesting making the whole session id a monotonically increasing integer, but to include such a value in the id along with the random part. Thanks for the patch - I'll apply it to my cluster. Please see it into the official distribution! You can imagine the trouble that could be caused if someone was using Tomcat for a banking application... Jeff Schnitzer [EMAIL PROTECTED] The Sims Online --- From: Tim Funk Subject: Re: Duplicate session IDs? Date: Tue, 24 Dec 2002 05:53:33 -0800 --- I agree that there is a tiny chance this could happen. It seems the original uniquenes code had a bug in it because it did not attach the jvmRoute after re-generating the sessionId. Thats why it was probably commented out. I hope you were joking about the monotonic increase of sessionIds. If that were done - it would be trivial to steal another's sessionId by guessing. Anyhoo, attached is patch which does the following: - Moves the appending of jvmRoute into generateSessionId() - uncomments the duplicate session check - When debug is turned ON (=1) it complains a dup sessionId was created when the occurance happens If there is interest in this - I can throw it into bugzilla so it doesn't get lost. -Tim Schnitzer, Jeff wrote: What prevents Tomcat from issuing duplicate session IDs? From the code in ManagerBase, it doesn't look like anything prevents it - the only unique value in the ID is a random number. In fact, the code which would guarantee uniqueness is commented out. I believe we have seen a problem with duplicate session ids on our production (high-traffic) site. It's hard to say exactly because the problem is very rare, but we have had at least two reports from users that they log in and see data from other people's accounts. If Tomcat is generating session ids randomly, this is a _HUGE_ problem. Why not just include a monotonically increasing integer in the session string? Thanks, Jeff Schnitzer [EMAIL PROTECTED] The Sims Online -- To unsubscribe, e-mail: mailto:[EMAIL PROTECTED] For additional commands, e-mail: mailto:[EMAIL PROTECTED]
