The MOO Accounting Problem Paper Brian W. Gordon While reading "The UNIX Time-Sharing System" paper, a sentence and reference caught my eye. I have spent considerable amounts of time researching this particular statement, and this paper contains the details of my findings. The statement follows: "Because anyone may set the set-user-ID bit on one of his own files, this mechanism is generally available without administrative intervention. For example, this protection scheme easily solves the MOO accounting problem posed by ``Aleph-null.'' [8] 8. Aleph-null, `Computer Recreations,' Software Practice and Experience, 1 2, April-June 1971, pp. 201-204. First I will describe known facts. Aleph-null is a mathematical definition for the smallest infinite integer. George Cantor who lived from 1845 - 1918 proved something similar to the statement "any infinite set can be expanded to make a larger infinite set". Aleph-null is therefore the smallest infinite set. MOO is the name of a console-based game that was created on one of the traditional Unix Timesharing system at Cambridge. The game consisted of the computer choosing four random decimal digits where position is important. As the player guesses the number, the computer informs the player how many digits are correct and in the proper position. Also the computer notifies the player how many digits are correct, but not in the proper position. Ken Thompson developed a strategy for playing Moo and wrote this strategy in a large notebook. It consisted of a game tree. The root of the tree stated the first guess should be 1234, depending upon the correctness of the guess, you would be directed to make further guesses. According to Dennis Ritchie, Ken Thompson's strategy was good, but apparently, not an optimal strategy. The article described by the footnote does not exist. The journal ends at page 200, however the article claims to be pages 201 through 204. The table of contents for that journal consists of the following information (http://joinus.comeng.chungnam.ac.kr/~dolphin/db/journals/spe/ spe1.html): Software - Practice and Experience (SPE), Volume 1, 1971 Volume 1, Number 2, April-June 1971 * Donald E. Knuth: An Empirical Study of FORTRAN Programs. 105-133 * M. Richards: The Portability of the BCPL Compiler. 135-146 * Jacob Katzenelson: Documentation and the Management of a Software Project - A Case Study. 147-157 * W. R. Jones: A MACRO Facility for Interactive Display. 159-166 * B. Landy, Roger M. Needham: Software Engineering Techniques used in the Development of the Cambridge Multiple-Access System. 167-173 * M. J. Rees: Some Improvements to the MINIMOP Multi-Access Operating System. 175-188 * M. D. Oestreicher: The Design of the Internal Structure of the ICL GEORGE 3 Operating System. 189-200 The version of the UNIX Time-sharing paper from Dennis Ritchies bell lab site contains the exact same statement. See http://cm.bell-labs.com/cm/cs/who/dmr/cacm.html The paper also states that the paper was written and formatted on the UNIX Time-Sharing machine. At various locations on the web, the reference is number 7, not number 8. See http://www.cs.berkeley.edu/~brewer/cs262/unix.pdf Now I will speculate about what this all may mean. The CS481 Teacher Assistant stated to me that the name "aleph-null" is an old-school hacker nickname. I find it interesting that the statement occurs next to the description of the set-user-id permission bit. One interpretation of this is that a hacker using the name "aleph-null" may have found a way to exploit the suid functionality and gained unauthorized access to the UNIX machine and changed the paper prior to publication. The statement that it solved an accounting problem may hint that "aleph-null" could not afford his/her own PDP type machine. The statement that it was a "MOO" accounting problem may indicate that this entire statement is just a joke. I have written both authors of "The UNIX Time-Sharing System" for clarification on this unusual sentence. (dmr@bell-labs.com and ken@entrisphere.com) Please find the attached response from Dennis Ritchie. This issue now makes more sense. A high-score file for the game Moo was maintained. However, the high score file needs to be trusted, and updateable in a controlled fashion. The high score file was owned by Moo and therefore by setting the set-user-id bit anyone who ran Moo had the permissions of Moo while running the game. This allowed any player to modify/update the high-score file only by playing Moo. I visited CSEL, despite the referenced table of contents, and was able to find the paper. The paper must have been submitted late, or for some other reason, left out of the table of contents. The paper discusses the problem surrounding how to make a secure version of Moo that does not allow the operator to create a core dump and analyze the dump for the answer. Preventing cheating was a fruitful endeavor for the beginnings of security research. --------- > I am working towards my masters degree at the University of New > Mexico. > I was assigned to read your CACM "The Unix Time-Sharing System" paper. > I tend to question things I don't understand. > Can you help me to understand how the set-user-id bit easily solves > the MOO accounting problem? The needed thing is for the game to keep a score file that is updated when a user plays, but this user (nor any others) cannot manipulate the score file file except by playing. So the idea is that the moo binary is suid to the moo owner and otherwise not acessable. > By MOO do you mean guess a 4 digit number? Was Aleph-null able to > use the > suid bit to gain root access? Did this help his financial accounting > problem of buying a PDP-11/70? Am I inventing things? I think the original Aleph-null paper (which I don't have any more) mentioned as an issue the problem of keeping the score file safe. I don't remember how the issue was posed; the paper (in my memory) was more about the game and the score file question was an aside. There's a bit more about the game itself at http://www.cs.bell-labs.com/who/dmr/ken-games.html . Yes, the game had to do with choosing a 4-digit number, opponent picks another number and is told "so many bulls, so many cows," keeps guessing, and tries to zero on on the chosen number. Aleph-null probably didn't have 11/70s or financial accounting in mind! On the other hand, suid these days seems to be a fairly blunt and dangerous instrument. > Thank you for everything you have done for the world. Your work has > benefited us all. Thanks much for these kind words. Regards and best wishes, Dennis