Path: gmdzi!unido!fauern!ira.uka.de!sol.ctr.columbia.edu!spool.mu.edu!think.com!redsox!campbell
From: campb...@redsox.bsw.com (Larry Campbell)
Newsgroups: alt.folklore.computers
Subject: Tenex hackery (was Re: Command Completion...)
Message-ID: <1991Jun12.025714.616@redsox.bsw.com>
Date: 12 Jun 91 02:57:14 GMT
References: <1991Jun04.215617.11849@corpane.uucp> <1991Jun5.110340.21634@athena.mit.edu> <1991Jun06.222446.19951@corpane.uucp>
Reply-To: campb...@redsox.bsw.com (Larry Campbell)
Organization: The Boston Software Works, Inc.
Lines: 107

Okay, folks, now for some Real Folklore (tm):

In article <1991Jun06.222446.19...@corpane.uucp> her...@corpane.uucp (Harry Herman) writes:
-
->Speaking of completions, I seem to recall hearing from an old
->housemate (hello, Brian, I know you're out there) about a system
->which idiotically added completion to passwords, thereby allowing
->someone to break into someone else's account with at most 26 (well,
->I don't know what char system was used -- say 128) tries!

I never heard of such a system, but this sounds like it might be a slightly
garbled explanation of a Really Neat security bug in Tenex.

For you younger folks out there, Tenex was a nifty operating system written
by BBN for the DEC PDP-10 (with a BBN-built paging box addon).  Tenex was
*much* nicer than DEC's operating system (called the PDP-10 Monitor back
then, and TOPS-10 later), as it had demand paging, a nice file system with
long file names and a hierarchical directory structure, a process tree
structure not unlike UNIX, and a nice command language with command and
filename completion.  This was, oh, around 1969.

Tenex provided users with lots of control over the address space.  You could
read all, and write some, of the hardware page access bits, to make pages
read-only, to create no-access guard pages (for stack limits), etc.

In Tenex, the system call roughly equivalent to chdir(2), called CNDIR I
think, could optionally take a password argument, which you would supply if
trying to connect to a directory that was password-protected against you.
If the password supplied was incorrect, the CNDIR would sensibly do a
three-second non-interruptible sleep before returning the "invalid password"
error, to prevent the obvious exhaustive attacks.

Now, the security bug worked like this.  The clever programmer would set up
a CNDIR call to the targeted directory, and make the first byte of the
password string be the last byte on a page.  He would then request that the
following page be made nonexistent, and then try the CNDIR.  CNDIR would
fetch the first byte of the password supplied, and compare it against the
first byte of the actual password.  (Passwords were not encrypted in
Tenex.)  If they didn't match, the CNDIR would stop right there, do its
three-second wait, and report the error.  If they did match, though, CNDIR
would fetch the next byte of the password.

Remember that the next byte is the first byte of a nonexistent page.
Attempting to fetch this byte would cause a page fault.  The standard action
the kernel took for a "nonexistent page" fault was to create a new,
writeable page full of zeroes.  So the CNDIR would fetch a null byte, this
would fail to match the second byte of the password, and a three-second
sleep followed by an error return would happen.

Now, in both cases, we've gotten an "invalid password" error return (unless
the password was only one byte long and we guessed right the first time).
But if the first byte matched, the page containing the second byte will no
longer be marked "nonexistent", since the kernel has just created a page
full of zeroes.  If the first byte didn't match, the page will still be
marked nonexistent.  A simple system call to retrieve the relevant page
status bits, and we now know whether the first character matched.  Once we
get a match, we move the password string one byte back, so the second
character is the last byte on a page, and so forth.

Each try took three seconds, so to entertain the onlooker, the program would
print out each attempted password, once every three seconds, like this
(assuming the password is BABBLE):

	A
	B
	BA
	BAA
	BAB
	BABA
	BABB
	BABBA
	BABBB
	BABBC
	BABBD
	BABBE
	BABBF
	... etc.


THE LEGEND OF THE DISCOVERY OF THIS BUG AT XEROX PARC

Here comes the folklore part.  Legend has it that this bug was discovered,
not on a PDP-10 at all, but on a PDP-10 clone built at Xerox PARC, which is
an interesting story in itself.

Around 1973 (I think) some researchers at Xerox PARC wanted to buy a PDP-10
to run Tenex.  The problem was that, at the time, Xerox was in the computer
business and made a machine called the XDS-940 (originally the SDS-940,
built by Scientific Data System, which Xerox acquired); the XDS-940 was
comparable to and competitive with the PDP-10.  So management nixed the
PDP-10 purchase.

Never ones to be daunted by managerial dicta, the PARC people decided to
build their own PDP-10.  And they did.  They built a machine, called the
MAXC, that was a PDP-10 with BBN paging, and I believe it was both smaller
and faster than the real DEC equivalent.  Getting Tenex for it was no
problem, because Tenex's development had been funded by ARPA (now DARPA),
and so was in the public domain.

And one day, someone discovered this nifty security bug on the MAXC.  The
bug also existed on a true-blue Tenex system, as well as in the early
internal versions of TOPS-20, DEC's enhanced version of Tenex, which is
where I saw it demonstrated.  DEC did fix the bug before version 1.0 of
TOPS-20 was shipped, but I don't know when -- if ever -- Tenex got the fix.
-- 
Larry Campbell             The Boston Software Works, Inc., 120 Fulton Street
campb...@redsox.bsw.com    Boston, Massachusetts 02109 (USA)