Cryptographic hashes

In the weeks finds, John Baez comes up to speed with the cryptographic community on the broken state of SHA-1 and MD-5. Now, this is a drama that has been developing with quite some speed during the last 1-1½ years. It all began heating up seriously early 2005 when Wang, Yin and Yu presented a paper detailing a serious attack against SHA-1. Since then, more and more tangible evidence for the inadvisability of MD-5 and upcoming problems with SHA-1 have arrived - such as several example objects with different contents and identical MD-5 hashes: postscript documents (Letter of Recommendation and Access right granting), X.509 certificates et.c.

The attacks that occur are what is called collision attacks by those in the trade. They find data [tex]x[/tex] and [tex]y[/tex] such that [tex]H(x)=H(y)[/tex]. The other serious attack is the preimage attack, where to a specific hash [tex]y[/tex], a message [tex]x[/tex] is found such that [tex]H(x)=y[/tex]. Once preimages can be found, it's time to bail ship quickly. Up until then, it may possibly be enough to pack the life boats and look toward the horizon for possible rescues or deserted islands.

Very interesting reads and link sources for this can be found, as with most things cryptographic, with Bruce Schneier.

Topology of computation

John Baez talks about some lectures he gave at the Geometry of Computation conference in the section of Universal Algebra and Diagrammatic Reasoning. Reading through what he did and looking over the conference as such, I realize I would very much have wanted to be there. They're doing linguistics and algebraic topology together, for one!

John Baez' talk (well worth to review the slides! Go do it!) goes through a lot of the themes I'm busying myself with from the vantage point of computer science and computation theory. He talks about PROPs, about PROs, about Monads and categorical monoids, about diagrams and algebraic theories et.c. Most of it very interesting, and rather close to my own work. If I now can work out some good method to display that the Koszul resolutions of PROPs are the same kind of resolutions that Baez uses to get simplicial objects representing computations, I might just close in to something that may give a good explanation as to why the things I like are relevant.

I will bring my post on Operads and PROPs at some point in the future. As will I bring my expose over Koszulness. But not today.

Geometry of roots

The third eye-catcher I found was an absolutely gorgeous picture of all roots of polynomials of degree at most 5 and with integer coefficients in [tex][-4,4][/tex]. It makes me want to build more pictures. Now, if I may. Dunno if this is what I -should- be spending the processor cycles of my workplace on, but damn, they are gorgeous!

I wonder how hard it would be to hack a Pari/GP script that spews out coordinates and colour tags for this with coefficients in [tex][-5,5][/tex] in a format amenable to producing pretty graphs. Some chosen thoughts awake with the comments from John Baez - among other things, he states that

Odlyzko and Poonen proved some interesting things about the set of all roots of all polynomials with coefficients 0 or 1. If we define a fancier Christensen set [tex]C_{d,p,q}[/tex] to be the set of roots of all polynomials of degree [tex]d[/tex] with coefficients ranging from [tex]p[/tex] to [tex]q[/tex], Odlyzko and Poonen are studying [tex]C_{d,0,1}[/tex] in the limit [tex]d\to\infty[/tex]. They mention some known results and prove some new ones: this set is contained in the half-plane [tex]Re(z) < 3/2[/tex] and contained in the annulus [tex]1/\phi < |z| < \phi[/tex] where [tex]\phi[/tex] is the golden ratio [tex](\sqrt5 + 1)/2[/tex]. In fact they trap it, not just between these circles, but between two subtler curves. They also show that the closure of this set is path connected but not simply connected.

Now, if the set isn't simply connected, then I'm immediately growing interested in the homology and homotopy of the set.