At Cirencester Julia Borghoff, Lars R. Knudsen and Mathias Stolpe presented their paper on how to express Bivium as a MIP problem. The conversion routines they propose and discuss are more generally applicable than Bivium and thus I wrote a little converter to convert systems of boolean polynomials to a MIP problem. MIP is now relatively well supported in Sage, thanks to the work of Nathann Cohen. Btw. for small scale AES systems the “Integer Adapted Standard Conversion” seems to be better than the “Standard Conversion” method contrary to the results reported in the original paper. There are a few tricks which I didn’t implement in the converter yet, but it should give reasonable results. Oh, the code requires the Christmas edition of Sage aka 4.3.


Cool New Stuff in Recent Sage Releases

Now that Sage 4.3 was released, maybe it’s time to point out some of the cool recent developments. Of course the following list is very very biased.

  • libSingular functions interface. We now have some code which makes it possible to call any function available in Singular using the libSingular C wrapper directly, like this.
    sage: P = PolynomialRing(GF(127),10,'x')
    sage: I = Ideal(P.random_element() for _ in range(3000))
    sage: from sage.libs.singular.function import singular_function, lib
    sage: groebner = singular_function('groebner')
    sage: %time groebner(I)
    CPU times: user 0.07 s, sys: 0.00 s, total: 0.08 s
    Wall time: 0.08 s

    For comparison, the Singular pexpect interface needs almost two seconds for the same task (due to string parsing on both ends, IPC, etc.)

    sage:%time groebner_basis()
    CPU times: user 0.96 s, sys: 0.24 s, total: 1.21 s
    Wall time: 1.92 s

    Michael Brickenstein wrote a lot of this code, so three cheers to him!

  • linear algebra over F_2 got better. For once, we implemented vectors over F_2 on top of M4RI matrices (cf. #7715), which makes them much faster. Furthermore, we call more dedicated M4RI functions now instead of the generic slow functions available for all fields (cf. #3684). Finally, asymptotically fast matrix factorisation got faster again. However, we still didn’t switch to this implementation as the default implementation because of the slow-down for sparse-ish matrices: use the algorithm=’pluq’ option to force the new implementation.
  • PolyBoRi was updated to version 0.6.3 and the interface received some considerable update too during a visit to Kaiserslautern. Please, please, please report any regressions etc. either to me, to [sage-support] or to [polybori-discuss]. didn’t make it, cf. #7271
  • Linear Programming is now available in Sage (though it requires to install at least one optional package). Still, this opens up quite a few possibilities (cf. Nathann Cohen’s tutorial).

M4RI-20091101 Released

I just tagged the new release. Get it at or from We did not change that much but this release finally has our improvements from Sage Days 16 where we improved matrix elimination quite a bit.

yet another density plot

While there is still some work to do (see the bump in the plots above), this release might be a first candidate where it makes sense to switch to LQUP/PLUQ by default for matrix elimination (e.g. in PolyBoRi).


One of the nice aspects of my current occupation is that I can type OpenPGP into springerlink’s and Google Scholar’s search boxes and claim that reading every paper I deem interesting is “work”. OpenPGP is the standard which is implemented by programs like GnuPG and PGP for e-mail encryption and digital signatures. The reason I became curious is because I wanted to implement something like an OpenPGP encrypted wiki or filesystem for multiple users.

  • RFC 4880 is the current revision of the OpenPGP message format standard, addressing some of the security concerns mentioned below. It replaces RFC 1991 and RFC 2440. You have to admire that they got their hands on 4880 to replace 2440.
  • Can We Trust Cryptographic Software? Cryptographic Flaws in GNU Privacy Guard v1.2.3 by Phong Nguyen describes a few errors made in the GnuPG implementation of the OpenPGP standard. In particular some parameters used in ElGamal encryption were chosen to be small for performance reasons which allowed lattice-based attacks. Lattice-based attacks on small parameters in public-key cryptography are not new, another example is textbook RSA with say 512-bit modulus encrypting a DES 56-bit key. From the paper: “If a proprietary software claims to implement 2048-bit RSA and 128-bit AES, it does not say much about the actual cryptographic security: which RSA is being used? Could it be textbook RSA (with zero-padding) encrypting a 128-bit AES key with public exponent 3? … Open source software thus sounds like a good solution. However, the fact that a source code can be read does not necessarily imply that it is actually read, especially by cryptography experts.” The flaw was rather serious (one package was sufficient to compute the private key) but the required configuration fortunately not very wide-spread since it was never the default choice. The particular option was removed from GnuPG since then.
  • An Attack on CFB Mode Encryption as Used by OpenPGP by Serge Mister and Robert Zuccherato describes an attack on the ad-hoc modification of CFB mode. PGP does not use variable IVs but instead encrypts a random block first and then two bytes which repeat two bytes from the first block. This redundancy provides a “quick check” whether the correct symmetric key was used for decryption or not. This also instantiates an integrity-check oracle if the information whether decryption passed this test or not is made available to the attacker. She can use this oracle to decrypt two bytes from any ciphertext block. The setup costs $2^{15}$ oracle queries and each block also costs $2^{15}$ oracle queries on average. RFC4880 discourages the use of this “quick check” and I think GnuPG avoids it.
  • Adaptive-CCA on OpenPGP Revisited by Hsi-Chung Lin, Sung-Ming Yen and Guan-Ting Chen does what the title implies. It revisits older adaptive CCA attacks and evaluates their applicability to RFC2440, also some new adaptive CCA attacks with weaker assumptions are proposed. All these attacks should not apply against RFC4880 anymore.
  • Privacy in Encrypted Content Distribution Using Private Broadcast Encryption by Adam Barth, Dan Boneh and Brent Waters is not really about OpenPGP. The authors construct a system where content is distributed in encrypted form but no one can tell who is a recipient not even other recipients: private broadcast encryption. OpenPGP does not provide this feature, as pointed out in the paper. While it allows to remove the explicit tag for which key a packet is encrypted, it chooses random Diffie-Hellmann groups for each key and thus still allows to break privacy (by distinguishing groups). While this could easily be fixed too, the authors also consider active attacks where an attacker modifies an encrypted message for Alice to contain the text “please visit the following URL for free music” (that really is their example!). The attacker then waits for Alice to click on the link which can only happen if she could decrypt the original message.

The bottom line is that OpenPGP features some ad-hoc cryptography which is not up to the standards of the cryptography research community. For example, OpenPGP is most definitely not secure against chosen-ciphertext attacks (CCA). This is likely not an issue for e-mail security where a human being enters passphrases to unlock private keys and where reports of errors are not relayed to a potential attacker. However, for instance a server which automatically decrypts messages and acts based on the content of the cleartext is a whole different story … and so is my OpenPGP encrypted wiki thingy.

PS: I will be at the ECRYPT-II Workshop on Cryptology: Progress and Challenges in Leuven in two weeks.

SAT Solving Pointers

This is just a quick note to point out two SAT-solving sources relevant for cryptography.

Have fun.