FW: security, predictable seeds for SessionID generation in Tomcat

[Jon Stevens <jo...@latchkey.com>]

Dunno why he is sending this privately to the group he picked...but
whatever...

Funny thing is that he quotes a reference to Ian Goldberg who is a good
personal friend of mine. LOL.

-jon

------ Forwarded Message
From: fubob@cisco.com
Date: Fri, 13 Jul 2001 15:29:29 -0400
To: duncan@eng.sun.com, jhunter@acm.org, jon@latchkey.com, shai@brm.com
Cc: fubob@cisco.com
Subject: security, predictable seeds for SessionID generation in Tomcat

Hi there,

The SessionIdGenerator.java code in
jakarta-tomcat-3.2.2-src/src/share/org/apache/tomcat/util/ appears to
seed the SessionID generator with a predictable value.  Below I
explain the predictability and suggest a fix.

The session ID consists of 6 random characters and then some
predictable data.  This provides at most 42 bits of security because
of 7-bit ASCII values.  However, the random number generator is seeded
by the time of day and (new Object()).toString() instead of Java's
built-in seeding routine.  We know from history that mixing in the
time of day does not add security [1, 2].

So I printed out some sample (new Object()).toString() output:

   java.lang.Object@3d4722
   java.lang.Object@720eeb

The only possibly random part is the 3-byte memory address.  If the
Tomcat code functions similarly to my test code, there are at most 24
bits of randomness in Object.toString.  Between separate executions of
my test code, the memory addresses were consistently either 3d4722 or
720eeb.  This leads me to believe that there is very Very VERY little
entropy here.  At least 1 bit, but not necessarily more.

Hence, an adversary only needs to guess at least 1 bit and at most 24
bits and the approximate time the server started to predict SessionIDs
and hence log in as any recently authenticated user.  On a reasonable
machine making 1000 guesses a second, it should take at most 4 hours
and expected time of about 2 hours to guess the seed.

According to http://java.oreilly.com/bite-size/java_1197.html  :

           Self-seeding

            If you don't specify a seed value when you construct a
            SecureRandom, one will be generated for you. This is
            where it gets confusing. The SecureRandom class has a
            static member variable, also a SecureRandom, called the
            seed generator. It is used to generate seed values for new
            SecureRandom instances. So every time you create a
            SecureRandom using new SecureRandom(), the seed
            generator is used to seed your SecureRandom instance.

            So how does the seed generator get seeded?
            SecureRandom uses an algorithm based on the timing of
            threads on the system to generate some supposedly random
            data. It uses this data to seed the seed generator itself.

            Thus, real random seed generation only occurs once, the
            first time you construct a SecureRandom. It has two
            disadvantages:

               It takes a few seconds (5-10 seconds on my Pentium
               90).
               As Sun says, the thread-timing algorithm is neither
               thoroughly tested nor widely deployed. It may have
               weaknesses that cryptanalysts could exploit.

Because you seed SecureRandom with the time of day and object memory
address, you might actually get a worse seed than the default.

Here are some suggestions to get better randomness without much work.
What do you think?

* If /dev/urandom exists, seed with 32 bytes.  Otherwise
  if /dev/random exists, seed with 32 bytes (this could block).
  Otherwise seed by XORing the default SecureRandom seed with your
  original object memory address and time of day.  /dev/random is
  commonly found on *BSD and Linux operating systems.  It collects
  entropy from various devices such as IDE hard drives,
  keyboard, mouse, and other sources.

* Just use the default SecureRandom seed which collects entropy
  by timing threads.

[1] Ian Goldberg, David Wagner.  Randomness in the Netscape Browser.
http://www.cs.berkeley.edu/~daw/netscape-randomness.html

[2] Peter Gutmann.  Software Generation of Practically Strong Random
Numbers, 7th USENIX Security Symposium, 1998.
http://www.usenix.org/publications/library/proceedings/sec98/gutmann.html

java.security.SecureRandom.generateSeed

public byte[] generateSeed(int numBytes)

    Returns the given number of seed bytes, computed using the seed
        generation algorithm that this class uses to seed
        itself. This call may be used to seed other random number
        generators.

    Parameters:
        numBytes - the number of seed bytes to generate.
    Returns:
        the seed bytes.

--------
Kevin E. Fu (fubob@cisco.com)

------ End of Forwarded Message