cr.yp.to update

 2005-501.html      |   35 +++++++++++++++++++++++++++++++++++
 hardware/x86.html  |    2 +-
 streamciphers.html |   22 +++++++++++++++++-----
 3 files changed, 53 insertions(+), 6 deletions(-)
diff -ru .old-crypto/2005-501.html cr.yp.to/2005-501.html
--- .old-crypto/2005-501.html	2005-09-09 22:40:41.000000000 -0400
+++ cr.yp.to/2005-501.html	2005-09-13 02:56:48.000000000 -0400
@@ -229,5 +229,40 @@
 multiply each bit of the first integer u
 by the second integer v, and add the results.
 5-bit example.
+<h2>12 September 2005</h2>
+Today's class material:
+Multiplication algorithm parallelizes easily.
+Tree of sums achieves depth n^{o(1)}.
+Simple tree layout:
+area n^{2+o(1)}, including wires;
+depth n^{0+o(1)}, not counting wire delay;
+time n^{1+o(1)}, counting wire delay.
+If massively parallel computation is so great,
+why don't existing CPUs provide it?
+Answer: for multiplication, they do!
+Notes on Duron multiplication performance.
+Atrubin 1-dimensional mesh:
+area n^{1+o(1)}, no long wires;
+time n^{1+o(1)}.
+We'll see Preparata 2-dimensional mesh:
+area n^{1+o(1)}, no long wires;
+time n^{0.5+o(1)}.
+The Brent-Kung ``area-time theorem'':
+every circuit for n-bit integer multiplication
+has area depth^2 larger than a constant times n^2;
+here area includes wire area,
+while depth does not include wire delay.
+Optimality of the Preparata mesh.
+<p>
+If you're interested in learning more about the Brent-Kung area-time theorem,
+read the
+<a href="2005-590/brent.pdf">original paper</a>.
+<p>
+If you're interested in the Atrubin mesh,
+look for it in Section 4.3.3 of Knuth's <i>Art of Computer Programming</i>.
+<p>
+If you're interested in achieving multiplication depth Theta(lg n)
+rather than Theta((lg n)^2),
+look up ``Wallace trees.''
 </body>
 </html>
diff -ru .old-crypto/hardware/x86.html cr.yp.to/hardware/x86.html
--- .old-crypto/hardware/x86.html	2001-10-13 03:35:17.000000000 -0400
+++ cr.yp.to/hardware/x86.html	2005-09-13 04:02:18.000000000 -0400
@@ -93,7 +93,7 @@
 To read the cycle counter, use machine-language bytes 15 and 49;
 the result is put into EAX/EDX.
 <h2>Code measurement tools</h2>
-Intel's Vtune Analayzer
+Intel's Vtune Analyzer
 includes a Pentium simulator and a Pentium II simulator,
 but it isn't free.
 <p>
diff -ru .old-crypto/streamciphers.html cr.yp.to/streamciphers.html
--- .old-crypto/streamciphers.html	2005-09-07 11:43:16.000000000 -0400
+++ cr.yp.to/streamciphers.html	2005-09-13 01:48:18.000000000 -0400
@@ -175,6 +175,11 @@
 Quite conservative.
 Salsa20 is faster than AES,
 but I was expecting it to be the slowest stream-cipher submission.
+<p>
+My paper
+<a href="snuffle/anping-disproof.pdf">``Disproof of Li An-Ping's
+claims regarding Salsa20''</a> discusses a bogus claim of an attack
+against Salsa20.
 <h2>Notes on Phelix</h2>
 Authors report,
 for a Pentium M,
@@ -269,6 +274,7 @@
 ``If a key is used with about 2^61 random IVs,
 and 20,000 keystream bytes are generated from each IV,
 then the key could be recovered easily.''
+<b>No response yet from the author.</b>
 <h2>Notes on YAMB</h2>
 Key as large as 32 bytes.
 Nonce as large as 16 bytes.
@@ -286,7 +292,7 @@
 ``There is a distinguishing attack on Yamb.
 It requires about $2^{58}$ outputs
 and about $2^{55}$ simple operations (32-bit addition or subtraction).''
-No response from the authors.
+<b>No response yet from the authors.</b>
 <h2>Notes on Py</h2>
 Authors report, for a Pentium III,
 2727 cycles to load a key;
@@ -364,7 +370,7 @@
 <p>
 Jaulmes and Muller report several attacks,
 such as a distinguishing attack using 2^34 nonces.
-No response from the authors.
+<b>No response yet from the authors.</b>
 <h2>Notes on F-FCSR-H</h2>
 10-byte key.
 <h2>Notes on Mosquito</h2>
@@ -379,7 +385,7 @@
 <p>
 Courtois writes: ``Sfinks broken by fast algebraic attacks.''
 I disagree; Courtois's attack is slower than brute force.
-No response from the authors.
+<b>No response yet from the authors.</b>
 <h2>Notes on Edon80</h2>
 10-byte key.
 10-byte nonce.
@@ -389,6 +395,12 @@
 16-byte key.
 14-byte nonce.
 Authors report approximately 1400 cycles/byte on a 2800MHz Pentium 4.
+<p>
+Carlos Cid, Henri Gilbert, and Thomas Johansson write:
+``We show how to mount a chosen IV attack to recover the secret key
+of Pomaranch with complexity much lower than the one expected with
+128-bit keys.''
+<b>No response yet from the authors.</b>
 <h2>Notes on MICKEY</h2>
 10-byte key.
 10-byte nonce.
@@ -441,7 +453,7 @@
 ``We present a very simple distinguishing attack ... on MAG,
 requiring only 129 successive bytes of known keystream,
 computation and memory are negligible.''
-No response from the author.
+<b>No response yet from the author.</b>
 <hr>
 <h2>Notes on Rabbit (patented)</h2>
 Authors report, for a Pentium III-1000,
@@ -531,7 +543,7 @@
 <p>
 Khazaei writes: ``... a distinguishing attack
 with data, time and memory complexities of O(2^32) could be applied.''
-No response from the authors.
+<b>No response yet from the authors.</b>
 <h2>Notes on DECIM version 1 (patented) (withdrawn)</h2>
 10-byte key.
 8-byte nonce.