cr.yp.to update

 critbit.html    |  157 +++++++++++++++++++++++++++++++++++++++++++-------------
 papers.html     |   40 +++++++++-----
 serverinfo.html |  118 +++++++++++++++++++++++++-----------------
 3 files changed, 221 insertions(+), 94 deletions(-)
diff -ru .old-crypto/critbit.html cr.yp.to/critbit.html
--- .old-crypto/critbit.html	2004-12-08 20:11:54.000000000 -0500
+++ cr.yp.to/critbit.html	2011-09-13 17:57:26.000000000 -0400
@@ -13,13 +13,16 @@
 for example,
 or a set of variable-length 0-terminated byte strings.
 <p>
-A crit-bit tree supports the following operations at high speed:
+A crit-bit tree supports the following operations (and more!) at high speed:
 <ul>
 <li>See whether a string x is in the tree.
 <li>Add x to the tree.
 <li>Remove x from the tree.
 <li>Find the lexicographically smallest string in the tree larger than x,
 if there is one.
+<li>Find all suffixes of x in the tree, i.e., all strings in the tree that have x as a prefix.
+Of course, this can take a long time if there are many such strings,
+but each string is found quickly.
 </ul>
 <p>
 A crit-bit tree can be used as a high-speed associative array.
@@ -38,40 +41,126 @@
 identifying the position of the <b>critical bit</b> (<b>crit bit</b>)
 that follows x.
 <p>
-This idea was introduced by Morrison in 1968 under the name PATRICIA,
-and independently by Gwehenberger at about the same time.
-<p>
-As with other binary trees,
-it's sometimes useful to augment the internal nodes to include
-parent pointers, child counts, etc.
-<h2>Crit-bit trees versus other data structures</h2>
-Compared to a hash table,
-a crit-bit tree has comparable speed and two big advantages.
-The first advantage is that a crit-bit tree supports more fast operations:
-finding the smallest string, for example.
-The second advantage is that a crit-bit tree <i>guarantees</i> good performance:
-it doesn't have any tricky slowdowns for unusual (or malicious) data.
-<p>
-Crit-bit trees are faster than
-comparison-based structures such as AVL trees and B-trees.
-They're also simpler, especially for variable-length strings.
-<p>
-Crit-bit trees have the disadvantage of not (yet!) being widely appreciated.
-Very few textbooks explain them,
-and very few libraries implement them.
-Literature:
+Each internal node in a pure crit-bit tree is stored as three components:
 <ul>
-<li>Morrison 1968.
-<li>Gwehenberger 1968.
-<li>Sklower 1993.
-<li>Knuth spends a few pages describing crit-bit trees.
-He explains suffix searching and (in an exercise) insertion.
-He doesn't mention that crit-bit trees support fast deletion
-and lexicographic operations.
-<li>Sedgewick says more but, at least in the first two editions,
-doesn't get the algorithms right... I should add details here.
+<li>Left: A pointer to the left child node, if that node is internal;
+otherwise the string at the left child node.
+<li>Length: An integer, the crit-bit position.
+<li>Right: A pointer to the right child node, if that node is internal;
+otherwise the string at the right child node.
+</ul>
+The total overhead, on top of the strings stored,
+is one pointer down to each internal node,
+and one integer at each internal node;
+in other words, one pointer and one integer for each string.
+<p>
+Strings need to be visibly distinguishable from pointers,
+but this costs at most one extra bit per string.
+The simplest general approach is
+to incorporate these two internal/external selector bits into the length,
+to have the left string stretching out to the left of the length in memory,
+and to have the right string stretching out to the right of the length in memory;
+all of the usual string-termination options,
+including counters and 0-termination and known fixed lengths, are applicable.
+Of course, pointing to this node means pointing to the length field in the middle.
+If strings are actually expressed as pointers to a separate storage pool,
+with at least 2-byte alignment for each pointer,
+then another option is to use the bottom bit of the pointer as the internal/external selector bit.
+<h2>Variants of crit-bit trees</h2>
+People are often tempted to augment the internal nodes in binary trees
+to include parent pointers, sibling pointers, child counts, etc.
+However, these modifications consume more space than a pure crit-bit tree,
+and I haven't seen any serious applications where the modifications provide speedups
+that outweigh the general slowdown caused by using more memory.
+<p>
+The basic idea of critical bits
+was introduced in 1968 by Morrison and independently Gwehenberger,
+but in retrospect their data structures were unnecessarily augmented
+beyond pure crit-bit trees.
+Subsequent variants
+differ in the amount of augmentation,
+in the algorithms provided,
+and in the correctness of those algorithms:
+<br>
+<table border>
+<tr><th>Overhead on top of each string stored</th><th>Literature</th></tr>
+<tr><td>5 control words: pointer, pointer, pointer, integer, integer</td><td>1968 Morrison;
+"PATRICIA"; no mention that fast deletion is possible</td></tr>
+<tr><td>3 control words: pointer, pointer, integer</td><td>1968 Gwehenberger;
+no mention that fast deletion is possible</td></tr>
+<tr><td>4 control words: pointer, pointer, pointer, integer</td><td>1973 Knuth;
+algorithms provided for suffix searching and (in an exercise) insertion;
+no mention of fast deletion and lexicographic operations</td></tr>
+<tr><td>3 control words: pointer, pointer, integer</td><td>1983 Sedgewick;
+mentions that deletion is possible but does not state a deletion algorithm;
+at least in the first two editions,
+states an insertion algorithm that fails when it inserts a new root
+(pointed out by Tim Lee)</td></tr>
+<tr><td>3 control words: pointer, pointer, integer</td><td>1991 Sklower;
+only for short fixed-length strings;
+implementations of insertion, deletion, and lexicographic searching</td></tr>
+<tr><td>2 control words: pointer, integer</td><td>2004 Bernstein;
+"crit-bit trees";
+implementations (posted in 2006)
+of insertion, deletion, exact searching, and suffix searching</td></tr>
+</table>
+<br>
+Most people don't seem to realize how fast crit-bit trees can be;
+most people don't seem to realize how small crit-bit trees can be;
+most people don't seem to realize that crit-bit trees
+support all of the standard data-structure operations.
+PATRICIA is often dismissed as being large and complicated,
+but pure crit-bit trees are actually quite small and simple.
+<h2>Putting crit-bit trees to work</h2>
+The standard strategy
+for many years has been to store searchable data sets as hash tables,
+in applications that need exact searches
+but not lexicographic searches;
+or as heaps, in applications that need to search for the minimum;
+or as AVL trees, red-black trees, etc. in applications
+that do not fit the restrictions of hash tables and heaps.
+<p>
+In Python, for example,
+the built-in "dict" data type is a hash table.
+Hash tables don't provide fast access to the smallest entry,
+so there's also a standard "heapq" library providing heaps.
+Heaps don't provide fast lookups of other entries,
+so there are various add-on libraries providing AVL trees and so on.
+A programmer who's happy creating a "dict" will simply do so,
+but then another programmer who wants fancier operations on the resulting database
+has to do an expensive conversion of the "dict" to a fancier data structure.
+<p>
+I have become convinced that this strategy should change.
+The revised strategy is much simpler:
+there should be one fundamental set-storage type, namely a crit-bit tree.
+Here's how a crit-bit tree stacks up against the competition:
+<ul>
+<li>
+A hash table supports insertion, deletion, and exact searches.
+A crit-bit tree supports insertion, deletion, exact searches,
+<i>and</i> ordered operations such as finding the minimum.
+Another advantage is that a crit-bit tree <i>guarantees</i> good performance:
+it doesn't have any tricky slowdowns for unusual (or malicious) data.
+<li>
+A heap supports insertion, deletion, and finding the minimum.
+A crit-bit tree supports insertion, deletion, finding the minimum,
+<i>and</i> exact searches, <i>and</i> general suffix searches.
+<li>
+General-purpose comparison-based structures such as AVL trees and B-trees
+support exactly the same operations as a crit-bit tree.
+However,
+crit-bit trees are faster and simpler, especially for variable-length strings.
+B-trees advertise a memory layout that's friendly to your disk,
+but with less effort one can use a similar "clustering" organization
+for nodes in a crit-bit tree.
 </ul>
-I'm switching to crit-bit trees in my software,
-and writing a paper with complete proofs.
+If you're designing a programming language,
+imagine how much happier your programmers will be
+if your basic built-in data type
+allows not just looking up x,
+but also enumerating the strings after x in sorted order.
+You can't do this with hash tables.
+You could do it with an AVL tree,
+but your operations will be simpler and faster if you use a crit-bit tree.
 </body>
 </html>
diff -ru .old-crypto/papers.html cr.yp.to/papers.html
--- .old-crypto/papers.html	2011-08-18 03:13:15.000000000 -0400
+++ cr.yp.to/papers.html	2011-09-15 09:01:33.000000000 -0400
@@ -128,6 +128,7 @@
 <tr><td><a href="#expandxor">expandxor</a></td><td> What output size resists collisions in a xor of independent expansions?</td></tr>
 <tr><td><a href="#broken">broken</a></td><td> Which eSTREAM ciphers have been broken?</td></tr>
 <tr><td><a href="#wild">wild</a></td><td> Wild McEliece</td></tr>
+<tr><td><a href="#wild2">wild2</a></td><td> Wild McEliece incognito</td></tr>
 <tr><td><a href="#phase3speed">phase3speed</a></td><td> Which phase-3 eSTREAM ciphers provide the best software speeds?</td></tr>
 </table>
 <h2>Papers by date</h2>
@@ -1817,19 +1818,6 @@
 ISBN 978-3-642-20900-0.
 <hr></td></tr>
 
-<tr><td valign=top><a name="simplelist">http://cr.yp.to/papers.html#simplelist</a></td>
-<td valign=top>17pp</td>
-<td valign=top>2011.03.20</td>
-<td valign=top></td>
-<td valign=top></td>
-<td valign=top>2011.03.20
-[<a href="codes/simplelist-20110320.pdf">PDF</a>]
-[<a href="codes.html#simplelist">more</a>]
-</td></tr><tr><td colspan="6">
-Daniel J. Bernstein.
-``Simplified high-speed high-distance list decoding for alternant codes.''
-<hr></td></tr>
-
 <tr><td valign=top><a name="rfsb">http://cr.yp.to/papers.html#rfsb</a></td>
 <td valign=top>19pp</td>
 <td valign=top>2011.02.14</td>
@@ -1858,6 +1846,32 @@
 Proceedings of CHES 2011, to appear.
 <hr></td></tr>
 
+<tr><td valign=top><a name="wild">http://cr.yp.to/papers.html#wild2</a></td>
+<td valign=top>13pp</td>
+<td valign=top>2011.09.15</td>
+<td valign=top>refereed</td>
+<td valign=top></td>
+<td valign=top>2011.09.15
+[<a href="codes/wild2-20110915.pdf">PDF</a>]
+[<a href="codes.html#wild2">more</a>]
+</td></tr><tr><td colspan="6">
+Daniel J. Bernstein, Tanja Lange, Christiane Peters.
+``Wild McEliece incognito''.
+<hr></td></tr>
+
+<tr><td valign=top><a name="simplelist">http://cr.yp.to/papers.html#simplelist</a></td>
+<td valign=top>17pp</td>
+<td valign=top>2011.03.20</td>
+<td valign=top>refereed</td>
+<td valign=top></td>
+<td valign=top>2011.09.15
+[<a href="codes/simplelist-20110915.pdf">PDF</a>]
+[<a href="codes.html#simplelist">more</a>]
+</td></tr><tr><td colspan="6">
+Daniel J. Bernstein.
+``Simplified high-speed high-distance list decoding for alternant codes.''
+<hr></td></tr>
+
 <tr><td valign=top><a name="decoco">http://cr.yp.to/papers.html#decoco</a></td>
 <td valign=top></td>
 <td valign=top></td>
diff -ru .old-crypto/serverinfo.html cr.yp.to/serverinfo.html
--- .old-crypto/serverinfo.html	2011-08-13 13:35:02.000000000 -0400
+++ cr.yp.to/serverinfo.html	2011-09-04 10:38:49.000000000 -0400
@@ -3,24 +3,41 @@
 <a href="djb.html">D. J. Bernstein</a>
 <h1>The <tt>cr.yp.to</tt> servers</h1>
 <h2>Physical location</h2>
-The <tt>cr.yp.to</tt> servers
-are located
+For many years the <tt>cr.yp.to</tt> servers were located
 in the Department of Mathematics, Statistics, and Computer Science
 at the University of Illinois at Chicago.
-Outages are usually, although not always, the fault of the
-Academic Computing and Communications Center
+They then moved to the security lab in the Department of Computer Science,
+and finally to an air-conditioned server room.
+<p>
+Internet connectivity is provided by the
+Academic Computing and Communications Center (ACCC)
 at the University of Illinois at Chicago.
+ACCC's network is, in general, extremely fragile&mdash;not because
+the hardware is particularly bad,
+but because ACCC's Ed Zawacki
+has deployed a series of network drones
+whose entire function is to make the network fragile.
+These drones are remarkably trigger-happy,
+continuously operating even when Zawacki is asleep,
+and not subject to any human oversight;
+on several occasions critical portions of the <tt>cr.yp.to</tt> network infrastructure
+have been blasted away by those drones
+and rebuilt only with manual effort.
+Zawacki claims that this is somehow helping security.
+<p>
+Some <tt>cr.yp.to</tt> services are now transparently replicated on servers in Europe.
 <h2>Software</h2>
 DNS service, HTTP/FTP service, and mail service
 are powered by
 <a href="djbdns.html">djbdns</a>,
 <a href="publicfile.html">publicfile</a>,
-and <a href="qmail.html">qmail</a> respectively,
-on various computers running a mixture of
-<a href="http://www.ubuntu.com">Ubuntu</a>,
-<a href="http://www.freebsd.org">FreeBSD</a>,
-and
-<a href="http://www.openbsd.org">OpenBSD</a>.
+and <a href="qmail.html">qmail</a> respectively.
+Servers running
+<a href="http://www.openbsd.org">OpenBSD</a>
+were replaced by servers running
+<a href="http://www.freebsd.org">FreeBSD</a>
+and then by servers running
+<a href="http://www.ubuntu.com">Ubuntu</a>.
 <h2>Network disasters</h2>
 Mail bounced during these incidents.
 If you ever see mail bounce because <tt>cr.yp.to</tt> doesn't exist,
@@ -31,7 +48,7 @@
 <p>
 2000-11-16:
 The <tt>.to</tt> administrators destroy <tt>yp.to</tt>,
-for reasons that have not been explained.
+for reasons that have never been explained.
 They try to fix the problem quickly,
 but it persists for many hours, thanks to BIND's
 <a href="djbdns/tcp.html#intro-axfr">obsolete zone-transfer protocol</a>.
@@ -43,7 +60,7 @@
 The underlying Internet protocols
 know the difference between nonexistent servers and unreachable servers.
 <p>
-The <tt>cr.yp.to</tt> web pages were unreachable during these outages.
+The <tt>cr.yp.to</tt> web pages were unreachable during most of these outages.
 If your browser's error messages
 misled you into believing that <tt>cr.yp.to</tt> didn't exist,
 complain to your browser vendor.
@@ -75,11 +92,11 @@
 2000-01-01 04:00 GMT:
 UIC's network goes down for four hours.
 This is a PHB problem, not a Y2K problem.
-As explained by Ahmed Kassem two weeks earlier:
-``UIC's campus network has been tested ...
+As explained by ACCC's Ahmed Kassem two weeks earlier:
+"UIC's campus network has been tested ...
 we fully expect the network to remain completely operational ...
-we will disconnect UIC's network from the outside world ...''
-That's an interesting definition of ``completely operational.''
+we will disconnect UIC's network from the outside world ..."
+That's an interesting definition of "completely operational."
 <p>
 2000-01-10 ~02:00 GMT:
 Scheduled upgrade to OpenBSD 2.6.
@@ -144,10 +161,10 @@
 <p>
 2001-07-30 ~19:30 GMT through ~23:30 GMT:
 Network outage at UIC.
-The computer center is more informative than usual:
-``There is a hardware problem with the ATM link leaving campus.
+ACCC is more informative than usual:
+"There is a hardware problem with the ATM link leaving campus.
 We do not yet know the exact cause or when our external link
-will be fully operational.''
+will be fully operational."
 <p>
 2001-08-26 ~04:00 GMT through ~19:00 GMT:
 OpenBSD crash. Cause undetermined.
@@ -168,14 +185,14 @@
 <p>
 2002.03.09 09:39 GMT through 17:02 GMT:
 Power outage at UIC.
-Didn't hit this building, amazingly enough,
-but did take down our Internet connection.
+Didn't hit the building with the <tt>cr.yp.to</tt> servers, amazingly enough,
+but did take down the campus Internet connection.
 Didn't quite match the previous eight-hour record.
 <p>
 2002.03.24 ~10:00 GMT:
 Network outage at UIC.
 For at least the first hour,
-the computer center claims that everything is just fine.
+ACCC claims that everything is just fine.
 <p>
 2002.08.27 through 01:59 GMT next day:
 Crash. Cause undetermined.
@@ -201,20 +218,21 @@
 No explanation of why this takes four hours.
 <p>
 2003.10.11:
-My DNS cache is actively disabled by the idiots at the UIC computer center
-because it is ``scanning remote hosts on port 53.''
+Zawacki's trigger-happy drones obliterate the network connection
+to my DNS cache.
+They say that the machine is "scanning remote hosts on port 53."
 <p>
 2003.10.14:
 Network outage at UIC.
 <p>
 2004.09.14 09:30 GMT through 2004.09.15 17:30 GMT:
 Massive power outage at UIC.
-(``A water main break flooded electrical vaults on the east campus.'')
+("A water main break flooded electrical vaults on the east campus.")
 The power outage lasted roughly 12 hours;
 the rest of the delay was caused by a UNIX filesystem
 that had blocks written in an incorrect order.
 (This could have been a bug in the disk hardware,
-such as the idiotic idea of disk-write caching,
+such as the idiotic idea of hardware disk-write caching,
 or it could have been a bug in the filesystem software.)
 <p>
 2004.12.07 19:05 GMT through 19:15 GMT:
@@ -230,17 +248,19 @@
 Equipment upgrades are being stymied by UIC's incompetent grant management.
 <p>
 2005.08.14 about an hour:
-My web server is actively disabled by the idiots at the UIC computer center
-because my machine is running a ``rogue FTP server.''
+Zawacki's trigger-happy drones obliterate the network connection
+for my web server.
+They say that the machine is running a "rogue FTP server."
 <p>
 2005.10.12 about two hours:
-My web server is actively disabled by the idiots at the UIC computer center
-because my machine is ``compromised''
-and is ``scanning on port 25.''
+Zawacki's trigger-happy drones obliterate the network connection
+for my web server.
+They say that the machine is "compromised" and is "scanning on port 25."
 <p>
 2006.03.16 about 16 hours:
-My mail server is actively disabled by the idiots at the UIC computer center.
-Could some masochist please hire Ed Zawacki
+Zawacki's trigger-happy drones obliterate the network connection
+for my mail server.
+Could some masochist please hire Zawacki
 so that I can stop dealing with his incompetence?
 <p>
 2007.01.09 about 12 hours:
@@ -251,7 +271,8 @@
 Scheduled outage to move servers.
 <p>
 2007.03.20 ~23:00 GMT?:
-My mail server is actively disabled by the idiots at the UIC computer center.
+Zawacki's trigger-happy drones obliterate the network connection
+for my mail server.
 <p>
 2007.09.29 ~04:00 GMT:
 Another multiple-hour power outage at UIC.
@@ -265,7 +286,8 @@
 the computer center still wasn't aware that there had been an outage.
 <p>
 2008.05.05:
-One of my servers is actively disabled by the idiots at the UIC computer center.
+Zawacki's trigger-happy drones obliterate the network connection
+for one of my servers.
 <p>
 2008.11.08 ~13:30 GMT to ~17:20 GMT:
 Intentional multiple-hour power outage at UIC,
@@ -283,24 +305,26 @@
 <p>
 2010.08.15:
 Hardware failure on main mail/web server.
-Working on a replacement.
 <p>
 2011.08.11:
-Failure on replacement mail/web server.
-Working on a new replacement (and some replication).
+Long-lasting power outage affecting replacement mail/web server.
 <p>
 2011.08.12:
 Scheduled 3-hour network outage at UIC for a router upgrade, plus the expected fallout.
+<p>
+2011.08.20:
+Zawacki's trigger-happy drones obliterate the network connection
+for one server.
+They say that the server is "infected with mass mailing worm."
+<p>
+2011.08.21:
+Zawacki's trigger-happy drones again obliterate the network connection
+for that server.
 <h2>Network overloads</h2>
 The effects of these incidents
 range from slight delays to apparent outages.
 Mail does not bounce in any case.
 <p>
-I am interested in hearing price quotes from Chicago ISPs
-for independently providing a wire to the math building
-with various levels of network service.
-We're at 851 S. Morgan.
-<p>
 2000-09 through 2000-11:
 UIC is paying its ISP for only 14Mbps,
 and is hitting that limit more and more frequently.
@@ -316,7 +340,7 @@
 2002.11.04 through 2002.11.07:
 More reports of overloads.
 The UIC computer center issues a statement:
-``Over the past two days the University has
+"Over the past two days the University has
 experienced degraded network connectivity ...
 Initially, this was the result of
 an unsanctioned and unannounced network experiment
@@ -332,19 +356,19 @@
 including hardware replacement,
 the decision was made to completely redo the way this router
 connects to the University backbone.
-Only then was the problem completely resolved.''
+Only then was the problem completely resolved."
 <p>
 2002.11.13:
 Horrible network performance at the edge of the UIC network;
 no packets lost, but ping times up to 2 seconds.
 In the evening, periods of complete outages.
 The UIC computer center issues a statement:
-``Over the past 2 days, we have been having enormous difficulties
+"Over the past 2 days, we have been having enormous difficulties
 in dealing with a Denial of Service attack
 that affected our ability to route traffic off of campus.
 After working with our two primary ISPs,
 we have finally been able to resolve the routing issue,
-and traffic is now leaving campus normally.''
+and traffic is now leaving campus normally."
 Outages continue for a little while after that statement.
 <p>
 2005.11.22: