SAGE UW Seminar 2006--2007

* Thur, Mar 1, 4-5pm: Martin Albrecht in B027:

Algebraic Attacks against Block Ciphers

In recent years a new attack technique against block ciphers has been discovered/proposed involving commutative algebra. I will briefly state the main ideas behind this technique, which often boils down to calculating a reduced lexicographical Gröbner basis for an ideal spanned by an equation system derived from the encryption algorithm.

Also, I will give examples of such attacks using SAGE, give an overview about the state of the art and present my 5-line "algorithm" "Gröber Surfing".


Brendan McKay has written what many people agree to be the world's fastest automorphism computation package, "nauty." The package is given a labelled graph G and an ordered partition P, and it outputs the partition stabilizer subgroup of the automorphism group and, optionally, the canonical label C(G,P). If P is the unit partition, this means the whole automorphism group and the canonical label C(G). Canonical labels are in one-to-one correspondence with isomorphism classes.

The package has a restrictive license, which excludes it from use in the open source community. The algorithm is described in McKay's paper, "Practical Graph Isomorphism," and luckily, academic Journals are amongst the most open of sources. The big picture of the algorithm will be explained, and reproductions of a few subroutines will be demonstrated.


Things Martin Albrecht may talk about during his visit:

Hi everybody, 
this is a list of stuff I could talk about. I didn't think those through, just 
stuff that came to mind.
 * Pyrex/SageX (I know e.g. Robert Miller wants to start hacking Pyrex to 
    speed up the graph stuff)
 * Wrap up of what happened at the MSRI workshop
 * Algebraic attacks on block ciphers and Groebner bases in SAGE 

Fridays 4-5pm in C401, at least -- probably more frequently!

Talks are all in the communications building, B027, except on Tuesday, Feb 13:

sage-uw/2006-2007 (last edited 2008-11-14 13:42:03 by localhost)