Categories::

• Root (136)
  • cryptography (42)
  • debian (13)
  • dev (22)
  • openbsd (2)
  • personal (12)
  • sage (41)

Projects::

Stuff::

MiniMe::

Martin Kreuzer on Algebraic Attacks

The article seems to be good overview of the area (I only skimmed it so far).
Table of Contents

• Introduction
• Cryptosystems
• From Cryptosystems to Polynomial Systems
• Attack Methods Based on Polynomials
• The XL, XSL and MutantXL Attacks
• The Gröbner Basis Attack
• The Border Basis Attack
• The Integer Programming Attack

I wonder how his IP approach relates to “Bivium as a Mixed-Integer Linear Programming Problem” by Julia Borghoff, Lars R. Knudsen and Mathias Stolpe.

posted at: 01:39 :: permanent link

OpenPGP

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.

posted at: 12:46 :: permanent link

SAT Solving Pointers

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

• Michael Brickenstein provides an alternative approach for ANF to CNF conversion in his PolyBoRi scripts collection.
• Mate Soos makes his changes to MiniSat available on his website. Those changes are meant to make it more suitable for cryptographic applications, hence the name CryptoMiniSat.

Have fun.

posted at: 12:06 :: permanent link

Algebraic Attacks and CNF

Since the seminal papers [1] and [2] by Bard, Courtois and Jefferson it seems accepted wisdom that the right thing to do for constructing a CNF representation of a block cipher is to construct an algebraic system of equations first (cf. [3]). This system of equations is then converted to CNF using some ANF to CNF converted (e.g. [4]) which deals with the negative impact of the XORs just introduced via the ANF. On the other hand, it is straight forward to compute some CNF for a given S-Box directly by considering its truth table. Sage now contains code which does this for you:

sage: sr = mq.SR(1,1,1,4,gf2=True,polybori=True)
sage: S = sr.sbox()
sage: print S.cnf()

I am not claiming that this naive approach produces an optimal representation, it seems more compact than what ANF to CNF converters produce, though.

posted at: 14:43 :: permanent link

Geometric XL

The paper by Sean Murphy and Maura Paterson has been around for quite some time now (same for my toy implementation). Gröbner basis algorithms and related methods like XL are algebraic in nature. In particular, their complexity is not invariant under a linear change of coordinates. For example consider Cyclic-6

    
    sage: P.<a,b,c,d,e,f,h> = PolynomialRing(GF(32003))
    sage: I = sage.rings.ideal.Cyclic(P,6).homogenize(h)
    sage: J = Ideal(I.groebner_basis())

The generators of J are a Gröbner basis and we can use this property to find a common root for these generators. Now, consider the same equations but permute the variables in the ring.

    sage: P.<a,b,c,d,e,f,h> = PolynomialRing(GF(32003),order='lex')
    sage: I = sage.rings.ideal.Cyclic(P,6).homogenize(h)
    sage: J = Ideal(I.groebner_basis())
    sage: R = PolynomialRing(GF(32003),P.ngens(),list(reversed(P.variable_names())),order='lex')
    sage: H = Ideal([R(str(f)) for f in J.gens()])

The generators of H do not form a Gröbner basis in R which is just P with its variables reversed. If we are only trying to solve a system of equations choosing the right permutation of variables might have a significant impact on the performance of our Gröbner basis algorithm:

    sage: t = cputime()
    sage: gb = H.groebner_basis('libsingular:std')
    sage: gb[-1].degree()
    19
    sage: cputime(t) # output random-ish
    25.36...

While in this example it is easy to see which variable permutation is the cheapest one, this is not necessarily the case in general. The GeometricXL algorithm is invariant under any linear change of coordinates and has the following property:

Let D be the degree reached by the XL algorithm to solve a given system of equations under the optimal linear change of coordinates. Then GeometricXL will also solve this system of equations for the degree D, without applying this optimal linear change of coordinates first.

The above behaviour holds under two assumptions:

• the characteristic of the base field K is bigger than D and
• the system of equations has one over “very few” solution.

To demonstrate this behaviour, consider the synthetic benchmark available here which is a Gröbner basis under a linear change of coordinates:

    sage: e,h = random_example(n=6)

e is the original easy system while h is the “rotated” system

    sage: e.basis_is_groebner()
    True

    sage: max([f.total_degree() for f in e.gens()])
    2

    sage: h.basis_is_groebner()
    False

    sage: max([f.total_degree() for f in h.gens()])
    2

GeometricXL recovers linear factors and thus candidates for common roots at D=2:

    sage: hH = h.homogenize()
    sage: f = GeometricXL(hH, D=2); f.factor(False)
    0.0...s -- 1. D: 2
    ...
    (-2684) 
    * (-1056*x5 - 2964*x4 - 177*x3 + 6206*x2 + 376*x1 + 6257*x0 + h) 
    * (2957*x5 - 792*x4 - 4323*x3 - 14408*x2 - 2750*x1 - 8823*x0 + h)

While any Gröbner basis algorithm would have to reach at least degree 64:

    sage: gb = h.groebner_basis('libsingular:slimgb')
    sage: gb[-1].degree()
    64

While my toy implementation is neither robust not efficient, the following table (using the same synthetic benchmark as above) should give some indication that for some problems GeometricXL is a good choice:

While the benchmark is synthetical and unrealistic, there are a few problems in multivariate quadratic public key cryptography which might be tackled using an idea similar to the GeometricXL algorithm. Also, note that constructing a GeometricMatrixF5 algorithm is straight forward by replacing the first step of the algorithm.

posted at: 14:10 :: permanent link

SSH Paper Available Online

Our paper on plaintext recovery attacks against SSH is now available online both locally and on Kenny’s website. Btw. contrary to popular belief the paper is not on an implementation error in OpenSSH but on a design flaw in the SSHv2 specification which enables a variety of attacks against various implementations of the standard.

posted at: 20:43 :: permanent link

A Simple Bitslice Implementation of PRESENT

I had a hunch the other day which required $2^{36}$ plaintext—ciphertext pairs to be tested. While the hunch turned out to be wrong, at least I got a simple bitslice implementation of PRESENT (in pure C99) out of it. The implementation is far from optimal:

• it is pure C but critical paths should be pushed down to assembly,
• it doesn’t use SSE2’s 128-bit instructions but it should, and
• the S-Box is hardly optimised (it is simply ANF).

Still, it is better than what I found on the web via a quick Google search. On my 2.33 Ghz Core2Duo Macbook Pro it seems to run at 28 cycles per byte for long messages (not counting the key schedule). For comparison, I think the current speed of AES in bit slice mode is like 10 cycles per byte on the Core2. If I need some performance in the future, I might sit down and improve the implementation (such that it doesn’t totally suck) but for now I have to attend to other projects.

posted at: 13:02 :: permanent link

Attacking Cryptographic Schemes Based on “Perturbation Polynomials”

“We show attacks on several cryptographic schemes that have recently been proposed for achieving various security goals in sensor networks. Roughly speaking, these schemes all use “perturbation polynomials” to add “noise” to polynomial-based systems that offer information-theoretic security, in an attempt to increase the resilience threshold while maintaining efficiency. We show that the heuristic security arguments given for these modified schemes do not hold, and that they can be completely broken once we allow even a slight extension of the parameters beyond those achieved by the underlying information-theoretic schemes. Our attacks apply to the key predistribution scheme of Zhang et al. (MobiHoc~2007), the access-control schemes of Subramanian et al. (PerCom~2007), and the authentication schemes of Zhang et~al. (INFOCOM~2008).”

That’s the abstract of a paper of Craig Gentry, Shai Halevi, Jonathan Katz and myself which just appeared on eprint. The source code for the experiments conducted in that work is available at bitbucket.

posted at: 12:31 :: permanent link

Semi-Regular Bits and Pieces

John Perry’s slides from his talk at Sage Days 12 in San Diego are available on the Sage wiki.

In my Diplomarbeit I had an algorithm for computing Gröbner bases of block ciphers called “Gröbner surfing”: “Instead of computing a reduced Gröbner basis for all rounds $rgb_F$ it computes the reduced Gröbner basis $rgb_{i+1}$ up to round $i + 1$ recursively as $$rgb_{i+1} = rgb(gb_i + round_{i+1})$$ with $rgb_0 = rgb(round_0)$ where $$rgb(round_i)$$ denotes any algorithm returning a reduced Gröbner basis for a given finite set of polynomials $round_i$.” This obviously is a tiny subset of what $F_5$ does: computing the Gröbner basis for $\langle f_i,\dots,f_m \rangle$ from the Gröbner basis of $\langle f_{i+1},\dots,f_m \rangle$. So nothing new here, move along.

I’m going to the Fast Software Encryption (FSE) 2009 workshop in Leuven to present our paper “Algebraic Techniques in Differential Cryptanalysis”. The full list of accepted papers is available online.

posted at: 11:46 :: permanent link

F5 Sans Rewriting

In his PhD thesis Justin Gash writes: “Rewritten gives us information to be used as an additional criterion for eliminating critical pairs. … In short, we could remove all discussion of rules and Rewritten and F5 would work fine. (But it would work much more slowly.)”

This motivated an implementation of F5SansRewriting which removes all mentions of Rewriting to make it easier to solely focus on the F5 criterion first. Of course the result is horribly inefficient. Cyclic-5 over $Z_{32003}$ takes 0.15 seconds using F5 and 81520.64 seconds using F5SansRewriting … well, at least it gives correct results and hopefully helps somehow.

posted at: 17:46 :: permanent link

PhD Thesis on F5

May I point my dear reader’s attention to Justin Gash’s PhD thesis on F5. It is mainly referred to because it points out an error in the proof of termination in the original F5 paper. I started reading the thesis today (in preparation of SD12 in San Diego) and it already helped me a lot to understand the algorithm. As a consequence I added a bunch of comments from Justin’s thesis to my toy F5 implementation which should explain a bit what is going on.

However, since Justin’s pseudocode is not identical with John Perry’s pseudocode (on which my implementation is based) things don’t match up perfectly. For instance, I still need to figure out what the differences in critical_pair exactly come down to.

posted at: 19:03 :: permanent link

Reactions to CPNI-957037: Vulnerability in SSH

• OpenSSH published a “Statement on ‘Plaintext Recovery Attack Against SSH’ (CPNI-957037)” and committed a first fix. Both the statement and the bugfix only address the OpenSSH specific attack from the advisory. “A variant of the attack against OpenSSH in the standard configuration can verifiably recover 14 bits of plaintext with probability $2^{-14}$.” (CPNI-957037)
• SunSSH’s Jan Pechanec writes: “For the first time we increased SunSSH version in OpenSolaris just because of a security vulnerability, to 1.3”. However, it seems they only fixed the $2^{-14}$ attack. Sun also issued a security advisory.
• SSH.com issued a security advisory and acknowledged that their products are vulnerable. However, no probabilities are given. The company claims to have fixed the issue in their latest line of products. I don’t know what their fix is.
• WinSSHD acknowledged that their product is vulnerable and issued an update which successfully (as far as I know) prevents the attack: “Our mitigation in WinSSHD 5.03 attempts to thwart this attack by denying the attacker any means of distinguishing a successful attempt from an unsuccessful one. This only protects data flowing in the direction to WinSSHD (e.g. the client’s password). Clients which do not implement similar mitigation can still allow this attack to succeed, when CBC is used, for data flowing from WinSSHD.”
• Dropbear’s 0.52 release added “counter mode cipher support, which avoids some security problems with the standard CBC mode.” on November 12th.

Update:The US-Cert vulnerability note is VU#958563.

posted at: 17:39 :: permanent link

Talk on Matrix F5

“We will describe the ‘Matrix F5’ algorithm. Although not presented as an algorithm there, this algorithm appears on the first pages of Jean-Charles Faugere’s famous F5 paper to explain the main idea of F5 itself. It was later described in several French PhD theses but never formally published in English. The talk is titled ‘for the working cryptographer’ because we are going to start from the relatively well known XL algorithm and extend it to Matrix F5.”

posted at: 11:56 :: permanent link

CPNI-957037: Vulnerability in SSH

Abstract:Vulnerability found in the network protocol SSH (Secure Shell), that allows data to be exchanged using a secure channel between two networked devices. A design flaw in the SSH specification allows an attacker with control over the network to recover up to 32 bits of plaintext from an SSH-protected connection in the standard configuration. The success probability in recovering 32 plaintext bits is $2^{-18}$ when attacking the OpenSSH implementation of the SSH RFCs. A variant of the attack against the OpenSSH implementation verifiably recovers 14 plaintext bits with probability $2^{-14}$. The recovered bits come from an arbitrary, attacker-selected block of ciphertext. The success probabilities for other implementations are unknown (but are potentially much higher).

See also: SSH.com

Update: Added “verifiably” for the 14-bit attack to point out that this attack is strictly better than guessing 14 bits. CPNI will probably update the advisory too.

posted at: 18:03 :: permanent link

Algebraic Attacks against Block Ciphers

That’s the title of the 15 minute talk I gave yesterday at Cambridge to Part 3 students. It is basically a refurbished version of a talk I gave in March 2007 in Seattle. Also, I was asked to forward this:

“Beyond Part III will take place over 16-18 April 2009 at the Centre for Mathematical Sciences, University of Cambridge.

Our aim is to develop a stronger network between mathematics graduate communities in the UK and internationally. We would like to emphasise that Beyond Part III is open to all mathematical researchers at the start of their career, whether or not they did Part III. The majority of participants are likely to be those who began a PhD in mathematics within the last five years, but this is a guideline only.

A dozen sessions covering different research areas will be run for one and a half days. Most participants will present work and each session will also include a keynote talk from a more senior researcher in that field. Beyond Part III will enable young mathematicians working in similar areas to form new links, and so plenty of social events are also planned. …”

posted at: 11:49 :: permanent link

Equation System Generator for DES

I’ve uploaded an equation system generator for the “Data Encryption Standard” (DES) hoping to spare others the tedious work of writing one. As far as I know only equation systems but no flexible generators are floating around the net. I implemented three S-Box representations (following Courtois’ and Bard’s paper Algebraic Cryptanalysis of DES): fully cubic equations, quadratic equations with added variables (Matthew Kwan’s bitslice representation) and the former with pre-computed Gröbner bases.

# loading the file
sage: attach des.py

# two rounds only, see DES? for help on the constructor
sage: des = DES(Nr=2)

# default S-Box representation is opns_gb
sage: F,s = des.polynomial_system()
Pre-computing Groebner bases for S-Boxes, this might take a moment.

sage: %time gb = F.groebner_basis()
CPU times: user 15.39 s, sys: 0.03 s, total: 15.42 s
Wall time: 15.78 s

# verify correctness
sage: gb[:14]
[k55, k54, k52, k51 + 1, k50 + 1, k49, k48 + 1, k47 + 1, k46 + 1, k45 + 1, k44 + 1, k43, k42, k41 + 1]
sage: s[des.k[55]]
0
sage: s[des.k[51]]
1

Let me know if you run into any trouble.

posted at: 13:26 :: permanent link

New Papers on eCrypt

Ann Hibner Koblitz (Women and Gender Studies Program, Arizona State University), Neal Koblitz (Dept. of Mathematics, Univ. of Washington), and Afred Menezes (Dept. of Combinatorics & Optimization, Univ. of Waterloo) published an interesting history of elliptic curve cryptography (ECC) titled: Elliptic Curve Cryptography: The Serpentine Course of a Paradigm Shift. They briefly introduce the math but the main part is their presentation and discussion how ECC became widely accepted (which apparently is not just because researchers agreed on a scientific basis). I only skimmed it, but it seems certainly worth a read. Speaking of Neal Koblitz and Alfred Menezis: Here are their papers on “provable security” which caused a fair amount of controversy: Another Look at “Provable Security” and Another Look at “Provable Security” II

Itai Dinur and Adi Shamir put a pre-print of their much hyped and discussed paper Cube Attacks on Tweakable Black Box Polynomials on ePrint. See also David Wagner’s summary.

posted at: 13:01 :: permanent link

AES Equation Systems

From time to time either I or Carlos receive requests for AES and/or BES equation systems. This post is an attempt to score high enough on Google so that others can find out about the AES equation system generator that is in Sage by default. For a while now Sage shippes a generator for AES and BES equation systems and their small scale variants (called “SR”). The generator supports both $GF(2)$ and $GF(2^e)$ for $e \in \{4,8\}$.

# Help for generator.
sage: mq.SR?
# We construct SR(1,1,1,4) over GF(2^4).
sage: sr = mq.SR(1,1,1,4)
SR(1,1,1,4)
# The constructor may fail due to zero inversions.
sage: F,s = sr.polynomial_system()
---------------------------------------------------------------------------
<type 'exceptions.ZeroDivisionError'>     Traceback (most recent call last)
...
<type 'exceptions.ZeroDivisionError'>: A zero inversion occurred during an 
encryption or key schedule.
# So we try again.
sage: F,s = sr.polynomial_system(); F
Polynomial System with 40 Polynomials in 20 Variables
# The object F is a polynomial system and the object s a solution
# dictionary. Help about F can be found via tab completion.
sage: F.<tab>

# F can be exported to Magma.
sage: sage: F._magma_()
Ideal of Polynomial ring of rank 20 over GF(2^4)
Graded Reverse Lexicographical Order
Variables: k100, k101, k102, k103, x100, x101, x102, x103, w100, w101, w102, 
w103, s000, s001, s002, s003, k000, k001, k002, k003
Basis:
[
w100 + k000 + $.1^4,
w101 + k001 + $.1^8,
w102 + k002 + $.1,
w103 + k003 + $.1^2,
k000^2 + k001,
....
....
....

# F can be exported to Singular.
sage: F._singular_()
w100+k000+(a+1),
w101+k001+(a^2+1),
w102+k002+(a),
w103+k003+(a^2),
k000^2+k001,
k001^2+k002,
k002^2+k003,
...

# Or we can use those systems transparently in the background.
sage: F.groebner_basis() # Singular in the background
[k002 + (a^3 + 1)*k003 + (a^2), k001 + (a^3 + a^2)*k003 + (a^3), k000 + 
(a^2)*k003 + (a^3 + a^2), s003 + (a^3 + a)*k003 + (a^3 + a^2 + a), s002 + 
(a^3 + a^2 + a)*k003 + (a^2), s001 + (a^3 + a^2 + a + 1)*k003 + (a + 1), s000 
+ (a^2 + a)*k003 + 1, w103 + k003 + (a^2), w102 + (a^3 + 1)*k003 + (a^2 + a), 
w101 + (a^3 + a^2)*k003 + (a^3 + a^2 + 1), w100 + (a^2)*k003 + (a^3 + a^2 + a 
+ 1), x103 + (a^3 + a)*k003, x102 + (a^3 + a^2 + a)*k003 + (a^3 + 1), x101 + 
(a^3 + a^2 + a + 1)*k003 + (a^3 + a), x100 + (a^2 + a)*k003 + (a^3 + a), k103 
+ (a^3 + a + 1)*k003 + 1, k102 + (a^2 + a + 1)*k003 + (a^3 + a^2), k101 + (a 
+ 1)*k003 + (a + 1), k100 + (a)*k003 + (a^2 + a + 1), k003^2 + (a^2)*k003 + 
(a^3 + a^2)]
sage: F.groebner_basis(algorithm='magma:GroebnerBasis') # Magma
[k003^2 + (a^2)*k003 + (a^3 + a^2), k100 + (a)*k003 + (a^2 + a + 1), k101 + (a 
+ 1)*k003 + (a + 1), k102 + (a^2 + a + 1)*k003 + (a^3 + a^2), k103 + (a^3 + a 
+ 1)*k003 + 1, x100 + (a^2 + a)*k003 + (a^3 + a), x101 + (a^3 + a^2 + a + 
1)*k003 + (a^3 + a), x102 + (a^3 + a^2 + a)*k003 + (a^3 + 1), x103 + (a^3 + 
a)*k003, w100 + (a^2)*k003 + (a^3 + a^2 + a + 1), w101 + (a^3 + a^2)*k003 + 
(a^3 + a^2 + 1), w102 + (a^3 + 1)*k003 + (a^2 + a), w103 + k003 + (a^2), s000 
+ (a^2 + a)*k003 + 1, s001 + (a^3 + a^2 + a + 1)*k003 + (a + 1), s002 + (a^3 
+ a^2 + a)*k003 + (a^2), s003 + (a^3 + a)*k003 + (a^3 + a^2 + a), k000 + 
(a^2)*k003 + (a^3 + a^2), k001 + (a^3 + a^2)*k003 + (a^3), k002 + (a^3 + 
1)*k003 + (a^2)]

# We can also construct equation systems over GF(2).
sage: sr = mq.SR(2,1,1,4,gf2=True)
sage: F,s = sr.polynomial_system()

# For those we can use PolyBoRi to compute the Groebner basis.
sage: R= F.ring()
sage: B = BooleanPolynomialRing(R.ngens(), R.variable_names(), order="lex")
sage: F2 = B.ideal([B(f) for f in F]) 
sage: F2.groebner_basis()
[k200 + k001 + k003 + 1, k201 + k001, k202 + 1, k203 + k000, x200 + k003, x201 
+ k000 + k001, x202 + k000 + k001 + k003, x203 + k000 + k003, w200 + k000 + 
k003 + 1, w201 + k001 + k003 + 1, w202 + k001 + 1, w203, s100 + k003 + 1, 
s101 + k000 + k001, s102 + k000 + k001 + k003, s103 + k000 + k003, k100 + 1, 
k101 + k001 + k003, k102 + k000 + 1, k103 + k003, x100 + k001 + k003 + 1, 
x101 + k000 + k001 + k003 + 1, x102 + k001 + 1, x103 + k000, w100 + k000 + 1, 
w101 + k001 + 1, w102 + k003, w103 + k003 + 1, s000 + k000 + k001 + k003, 
s001 + k000 + k001, s002 + k000 + k003, s003 + k001 + 1, k000*k001 + k000 + 
k001 + 1, k000*k003 + k000 + k003 + 1, k001*k003 + k001, k002 + k003]

Happy attacking.

posted at: 12:20 :: permanent link

Algebraic Techniques in Differential Cryptanalysis

Finally, our paper on algebraic techniques in differential cryptanalysis is available as pre-print. From the abstract:

“In this paper we propose a new cryptanalytic method against block ciphers, which combines both algebraic and statistical techniques. More specifically, we show how to use algebraic relations arising from differential characteristics to speed up and improve key-recovery differential attacks against block ciphers in some situations. To illustrate the new technique, we apply it to reduced round versions of the cipher PRESENT, an ultra lightweight block cipher proposed at CHES 2007, particularly suitable for deployment in RFID tags.”

Since the results of that paper rely on experimental data, we also publish the source code used to execute our experiments. I’m going to present this paper at SCC 2008, whichs schedule is now available, btw.

posted at: 13:22 :: permanent link

“Algebraic Techniques in Differential Cryptanalysis”

That is the title of the talk I am going to give tomorrow at the ISG Research Seminar:

Abstract: We propose a new cryptanalytic method against block ciphers, which combines both algebraic and statistical techniques. More specifically, we show how to use algebraic relations arising from differential characteristics to speed up and improve key-recovery differential attacks against block ciphers in some situations. To illustrate the new technique, we apply it to reduced round versions of the cipher PRESENT, an ultra lightweight block cipher proposed at CHES 2007, particularly suitable for deployment in RFID tags.

posted at: 14:28 :: permanent link

CFP: First International Conference on Symbolic Computation and Cryptography

I was asked to forward this announcement a while ago and finally get around to do so:

“SCC 2008 is the first of a new series of conferences where research and development in symbolic computation and cryptography may be presented and discussed. It is organized in response to the growing interest in applying and developing methods, techniques, and software tools of symbolic computation for cryptography. The use of lattice reduction algorithms in cryptology and the application of Groebner bases in the context of algebraic attacks are typical examples of explored applications.

SCC 2008 aims at providing an interactive forum for interested researchers to exchange ideas and views, to present research results and progress, and to learn and discuss recent developments and emerging problems on

• the design, modeling, and analysis of cryptographic systems and protocols for which symbolic computation may be used or needed, and
• the design, implementation, and analysis of algorithms and software
• tools of symbolic computation that may have potential applications in cryptography.

TOPICS

Specific topics for SCC 2008 include, but are not limited to:

• Multivariate cryptography, braid group cryptography, noncommutative cryptography, and quantum cryptography
• Code-based, factorization-based, and lattice-based cryptography
• Algebraic attacks for block ciphers, stream ciphers, and hash functions
• Design and analysis of algebraic, elliptic, and embedded cryptographic systems and protocols
• Groebner basis techniques in cryptology, algebraic number theory, and coding theory
• Triangular sets and new techniques for solving algebraic systems over finite fields
• Algorithms and software for symbolic computation in cryptography

INVITED SPEAKERS

Bruno Buchberger (Johannes Kepler Universitaet Linz, Austria)
Arjen K. Lenstra (Ecole Polytechnique Federale de Lausanne, Switzerland) (to be confirmed)
Adi Shamir (Weizmann Institute of Science, Israel)
Xiaoyun Wang (Tsinghua University and Shandong University, China)
…”

posted at: 13:58 :: permanent link

Small Scale AES MQ Generator

I’ve just filled a SAGE trac ticket which has my implementation of a small scale AES polynomial system generator attached. It supports all SR sizes, systems over $GF(2)$ and $GF(2^e)$, and $SR*$ both as specified and in AES mode, i.e. such that $SR*(10,4,4,8)$ is AES. The patch also contains a base class called MPolynomialSystemGenerator which is supposed to be a common plattform for similar constructors for other ciphers. I would appreciate feedback on that. The generator spits out an instance of MPolynomialSystem which I’ve written of before: “I am planing to provide a class for SAGE for polynomial systems (over $GF(2)$ and $GF(2^e)$) and would appreciate input what kind of constructions should be possible with this class. As a working title I call it MPolynomialSystem (done) and it will provide methods to construct stuff like coefficient matrices, ideals etc.(done) This by itself is not that exciting, but I am planing to subclass this to allow more fine grade access to e.g. block cipher rounds. (done) Also, MPolynomialSystem classes over $GF(2^e)$ should be convertible to ideal bases over GF(2) (done) and so on.”

A little example session:

sage: sr = mq.SR(1,1,1,4,gf2=True)
sage: sr
SR(1,1,1,4)
sage: P = sr.random_state_array(); P
[a^2 + a + 1]
sage: K = sr.random_state_array(); K
[a + 1]
sage: sr(P,K)
[a^2 + a + 1]
sage: F,s = sr.polynomial_system(P,K)
sage: F
Polynomial System with 56 Polynomials in 20 Variables
sage: type(F)
<class 'sage.crypto.mq.mpolynomialsystem.MPolynomialSystem_gf2'>
sage: s
{k003: 1, k002: 1, k001: 0, k000: 0}
sage: gb = F.groebner_basis()

sage: sr = mq.SR(1,1,1,4,gf2=False)
sage: F,s = sr.polynomial_system(P,K)
sage: type(F)
<class 'sage.crypto.mq.mpolynomialsystem.MPolynomialSystem_gf2e'>
sage: gb = F.groebner_basis()
sage: F2 = F.change_ring(GF(2))
sage: F2
Polynomial System with 240 Polynomials in 80 Variables
sage: type(F2)
<class 'sage.crypto.mq.mpolynomialsystem.MPolynomialSystem_gf2'>

Comments? Feedback? Rants?

posted at: 19:16 :: permanent link

Those Early Wild Days of Crypto

From an article by Neil Koblitz in the Notices of the AMS:

“The free-spirited tone of the meetings in those years [early 80s, malb] reflected the colorful and eccentric personalities of some of the founders of and early researchers in public key cryptography. One such person was Whit Diffie, a brilliant, offbeat, and unpredictable libertarian who in 1976 had coauthored (with Martin Hellman) the most famous paper in the history of cryptography. Diffie used to run the ‘rump session’, where informal, irreverent, and often humorous presentations were the norm. There was heckling, and at one point Whit had to impose some restrictions on what could be thrown at a speaker (empty beer cans were okay, but not full ones).”

posted at: 14:02 :: permanent link

CTC Equation Systems

Due to popular demand ;-) , I put together a little archive with CTC equation systems. Included in the archive are all combinations of B and Nr up to 5 respectively. For each configuration up to three systems are given: The first is as given by Courtois in [CTC], the second is substituted using linear relations, and the third is subsituted using all relations (including the S-Box). This third subsitution is only performed if Nr<3 as my substitution code is so slow. Details about these subsitutions (and some experiments with them) may be found in my Diplomarbeit.

Please note: These systems are not CTC2 systems; Nicolas Courtois published a closed-source equation system generator for CTC2. If you are desperate and refuse to run his closed-source generate drop me a note and I will generate some CTC2 equation systems.

posted at: 14:32 :: permanent link

CTC2

Nicolas Courtois published a new paper yesterday which describes CTC2, an improved version of CTC, and some experimental results with it. As the original CTC can be successfully attacked using linear cryptanalysis the revisited CTC is supposed to fix that design flaw. The major differences are:

• The diffusion layer does not contain a bit anymore with $Z_{i,j}=Y_{m,n}$.
• The new specification allows block sizes and key sizes to differ.

Additionally, Nicolas Courtois states that he will offer a closed-source, public-domain ctc.exe to construct CTC equation systems. However, this program doesn’t seem to be available yet. I will also update my open-source implementation to allow the construction of CTC2 polynomial systems for SAGE.

Speaking of constructors for polynomial systems. I am planing to provide a class for SAGE for polynomial systems (over GF(2) and GF(2^e)) and would appreciate input what kind of constructions should be possible with this class. As a working title I call it MPolynomialSystem and it will provide methods to construct stuff like coefficient matrices, ideals etc. This by itself is not that exciting, but I am planing to subclass this to allow more fine grade access to e.g. block cipher rounds. Also, MPolynomialSystem classes over $GF(2^e)$ should be convertible to ideal bases over $GF(2)$ and so on. So, if you are dealing with solving polynomial systems over finite fields and would like to do so with SAGE, I would like to hear from you. Also, somebody should hook the MiniSat solver to SAGE (or any free CAS which supports multivariate polynomials), i.e. implement this paper. Maybe somebody reading this post has time at hand, I would gladly provide whatever support is needed.

posted at: 15:42 :: permanent link

Random Numbers

A lot of work has been devoted to linear algebra in SAGE recently. To benchmark and test the results random matrices are generated. If we are working mod p this looks somewhat like this:

for i from 0 <= i < self._nrows*self._ncols:
    self._entries[i] =  random() % self.p

Now consider two 1000x1000 random matrices over GF(2).

sage: A = random_matrix(GF(2),1000,1000)
sage: A.rank()
496

sage: B = random_matrix(GF(2),1000,1000)
sage: B.rank()
496

Fair enough, as a random matrix over GF(2) is supposed to have full rank with probability 0.2888. The whole business pf both having exactly the same rank is kind of worrisome, though. The matrices, however, are different.

sage: A == B
False

Now the fun part:

sage: A.echelon_form() == B.echelon_form()
True

Consequently, they both span the same space, i.e. either I screwed up badly or the default C random number generator is really lame with respect to the last bit.I would appreciate if somebody could come forward with an explanation. Btw. the higher-order bits seem to be fine.

Update:Carl Witty pointed me to this website for an explanation.

posted at: 23:28 :: permanent link

Errata

My Diplomarbeit/thesis contains at least these two errors:

• p.21 The shape lemma is given incorrectly. The polynomials $g_0 \dots g_{n-1}$ are obviously not in $k[x_n]$ but in $k[x_{n-1}]$. There is no $k[x_n]$.
• p.41 “Given a finite list F of polynomials in R, call the (reduced) Gröbner basis of these polynomials Ft. A coefficient matrix At may be constructed for Ft. This matrix At is the (reduced) row echelon form of A and Ft is called the row echelon basis of F.” This sentence misses the crucial information that this is true with respect to a linear system only, i.e. Gaussian elimination and Gröbner basis calculation is equivalent for linear systems. This limitation does not apply to Theorem 4.1.1, however.

Oh, I gave a talk on this stuff today. Guess when I spotted those errors.

posted at: 03:06 :: permanent link

Cryptanalysis

There is a new blog on the block dedicated to cryptanalysis. It’s address is http://www.cryptanalysis.eu. From the website:

“This site is a platform for people interested in both practical and theoretical cryptanalysis of modern-day cryptography. We operate several (moderated) mailing lists for researchers working in the field of cryptanalysis:

• symmetric@cryptanalysis.eu - for all things relating to the cryptanalysis of secret-key primitives and schemes
• pubkey@cryptanalysis.eu - for discussions on the cryptanalysis of public key primitives
• protocol@cryptanalysis.eu - is the place where cryptanalysis of cryptographic protocol is discussed

You can subscribe to these mailing lists by sending a mail with the single word subscribe either in the subject or the body of the message.”

Don’t ask me about the .eu, though.

Elsewhere: NIST announced a hash function competition.

posted at: 03:26 :: permanent link

Talks

I gave two talks on algebraic attacks on the Courtois Toy Cipher recently. One in Kaiserslautern and one in Darmstadt. Both were way too short but someone might enjoy the slides anyway. The Darmstadt talk also covered SAGE a bit more.

posted at: 13:49 :: permanent link

Hell Freezes Over: Diplomarbeit 1.ooohhh

I’ve just handed in my thesis with the title “Algebraic Attacks on the Courtois Toy Cipher”. It features the usual mathematical background, a zero-dimensional Gröbner basis for CTC [Cou04] ideal without a single polynomial reduction [BPW05], open-source implementations of F4 [Fau99], DR [TF05], and XL [CKPS00] (all in SAGE), timing experiments with CTC, and a little new algorithm called “Gröbner Surfing”.

Sidenote: Back in the old days 1.0 was really cool, but in times like these, it is neither adventurous nor advanced. So I should brand it “Diplomarbeit NX” or so.

posted at: 14:30 :: permanent link

CTC Graphs

As stated earlier SAGE now includes NetworkX for graph theory. To play with it I’ve generated some graphs for CTC equation systems as shown below. The nodes are variables and they are connected by an edge if two variables appear in the same equation. The layout is NetworkX’s spring layout. A thread which explains how to improve the results of the layout by changing the iteration number may be found here.

www.flickr.com

posted at: 11:20 :: permanent link

Government Trojans

Some clarification on the government issued Trojans. It is definitely planned (DE) to allow German secret agencies to install malware on a suspects computer. This does not only relate to the state of Nordrhein-Westfalen but also the federal government. Apparently, the BKA (federal police) already installed (DE) malware on some suspects computers, though it is still illegal.

However, the detail that system updates are to be used to inject the malware seems to be a speculation. Also, it seems highly unlikely that this would work as apparently Microsoft digitally signs (EN) every update. So, without Microsoft’s approval, this attack doesn’t work. PS: Microsoft doesn’t owe Nordrhein-Westfalen a thing.

Also, my claim that digital signatures offer some kind of protection against the attack, was criticized by Hagen. Of course, if the government is able to bribe, extort, or otherwise force the signer to sign the malware, digital signatures become worthless. Also, the government could hack the signer’s computer etc. However, this is an attack of a much larger scale and much more likely to be detected. The attack of injecting malware into an update stream at the ISP is tackled with digital signatures. Knowing another attack, which is not prevented, does not falsify this claim.

Finally, if you cannot trust your ISP (which you can’t) try TOR.

posted at: 13:56 :: permanent link

Conditional Jumps Considered Harmful

Disclaimer: This stuff is amateur level cryptography as I don’t know much about side-channel attacks. In fact, I read exactly one paper.

If you are “raised” as a C developer you try to avoid conditional jumps because of their performance impact. Because of all the crazy pipelining going on in modern CPUs a conditional jump slows things down as the CPU doesn’t know in advance what to pipeline. Consequently branch prediction was introduced which basically means that the CPU guesses which jump is most likely and shuffles the data for that branch to the pipeline. If the guess was wrong things slow down but if the guess was right everything is nice and fast.

Now there is a new reason to avoid conditional jumps. Consider exponentiation of a message M by a secret key d. The naive approach would be:

def power1(M,d):
  S = 1
  i = 0
  while i < d:
    S *= M
    i = i + 1
  return S

As this has a complexity of O(d) this might take forever because we are dealing with pretty large degrees. Fortunately, there is a much faster way of doing this with a complexity of O(log_2(d)).

def power2(M,d):
  S = 1
  i = 0
  while (d>>i) > 0:
    if (d>>i) & 1: 
      S = S * M
    M = M * M
    i = i + 1
  return S

Now, here’s the problem: As there is a conditional jump in power2 the CPU makes branch predictions. For this it (i.e. in this case a P4) uses a cache of target addresses of conditional jumps. This buffer is meant to speed things up so that the address doesn’t have to read from main memory. As this buffer is finite and shared by all processes on the same CPU a spy process may basically fill up this table by repeated conditional jumps. If the spy process measures the time it takes to execute these jumps it may know if its branch prediction was evicted from the branch prediction table. This means that the exponentiation process just performed a conditional jump which in turn means that there is a bit 1 in d. So the fact that conditional jumps are executed in dependence of secret key bits reveals secret key bits to an attacker allowed to run a process on the same machine. So far the simplified attack description as described in a recent paper by Onur Aciicmez, Cetin Kaya Koc, and Jean-Pierre Seifert.

In my amateurish mind I would prevent this kind of attack by avoiding conditional jumps:

def power3(M,d):
  choice = [1,M]
  S = 1
  i = 0
  while (d>>i) > 0:
    S = S * choice[(d>>i) & 1]
    choice[1] = choice[1] * choice[1]
    i = i + 1
  return S

This idea introduces probably more problems than it fixes as now three variables are needed (S,M, and 1) and thus data loading times might become a bigger issue i.e. an attack vector for timing attacks.

posted at: 20:33 :: permanent link

Diplomarbeit 0.9 or “crypto is soooo kewl”

As someone I knew only via e-mail exchange was under the impression that my skills when it comes to cryptography match those of a 16 year old kid screaming “crypt is soooo kewl” I figured that my online appearance might support this judgment. Here is your chance to find out: I just decided that my Diplomarbeit (~ master thesis) is finished. It is titled “Algebraic Attacks on the Courtois Toy Cipher” and all it needs is proof reading. Anybody interested in proof reading my English?

posted at: 18:31 :: permanent link

ATM Security

Bruce Schneier reported on a hack of an ATM machine where someone reprogrammed it to spit out $20s instead of five dollar bills (and the machine only charged the five dollar bills).

Apparently this hack was possible by simply reading the reference manual of the ATM which may be obtained from the manufacturer. The default password was 1,2,3, and (now hold it) 4 and isn’t changed by many smaller banks at all. passivemode.net even put up a list of default passwords of ATMs. While elsewhere Mike Bond and Piotr Zielinski of Cambridge University wrote a paper on how to reveal a PIN in 15 trials.

posted at: 22:21 :: permanent link

Old Slides

I need a blog post to move the long sources.list listing below the right sidebar and wanted to post these old slides anyway:

• Slides from a (very superficial) presentation on the Courtois Toy Cipher.
• Slides from a (German) talk on RSA at a surgeon’s conference (I was part of the entertainment program).

posted at: 00:01 :: permanent link

“How Fast can be (sic!) Algebraic Attacks on Block Ciphers?”

As reported earlier Nicolas Courtois, the guy behind XL and XSL, is going to demonstrate an algebraic attack on a toy cipher with 512 S-Boxes on the May 26th 2006. Now he published a paper on e-print with the title “How Fast can be Algebraic Attacks on Block Ciphers?” which describes the attacked algorithm which he calls Courtois Toy Cipher (CTC). The paper gives no details on the actual attack - called “Fast Algebraic Attack on Block Ciphers” - but states that the attack is a specialized Gröbner Bases algorithm for systems of polynomial equations derived from block ciphers. The reason no details are provided are given as follows:

“In order to protect the United States government, the financial institutions, mobile phone operators, and hundreds of millions of other people that use AES, from criminals and terrorists, the exact description of the attack will for some time not be published. Public demonstrations of the effectiveness of the attack will be organised instead. However one should understand that the attack is quite simple and fatally will be re-discovered (and published).”

What we do know about the attack is that it takes approx. 60 minutes on a 2.8 Ghz PC with 2GB of RAM and the attacked CTC configuration is B=85, Nr=6.

Of course every kid on the block (i.e. me) tries to “re-discover” the attack (and of course every kid on the block (i.e. me) will fail). Here are some random remarks on CTC:

• I believe there is a typo in Fig.1: The first K_1 should read K_0 but the author disagrees. However to quote from the paper: “With all these notations, the linear equations from the key schedule are as follows: X_{i+1,j} = Z_{i,j} + K_{i,j} for all i = 0 \dots Nr”.
• I’ve implemented/hacked up CTC (“implemented with a minimal effort”) in SAGE.
• Calculating a lexicographical Gröbner Basis for the parameters B=1 and Nr=60 takes 76 seconds on my home PC (3.0Ghz, 1.5GB RAM). The calculation is performed using Singular’s stdfglm() command.
• Calculating a lexicographical Gröbner Basis for B=3, Nr=3 using Singular’s stdfglm() command takes 23 seconds on my home PC.
• Stating the obvious: The special structure of ideals derived from block ciphers might be related to the fact that polynomials from different non-neighbouring rounds won’t share any terms.

Elsewhere:My hard drive died today so I lost 120GB worth of data.

posted at: 21:10 :: permanent link

Algebraic Attack on 200 S-boxes

“Quo Vadis 4 Conference, Friday 26 May 2006, Warsaw, Poland, (just before Eurocrypt) will host an exceptional event, that, if works as well as it seems, could be an important and unique breaktrough in cryptology. Nicolas T. Courtois has announced that he will make a public demonstration of an algebraic attack that breaks a toy block cipher with about 200 S-boxes (nearly as many as in AES), by solving a system of algebraic equations derived from very few (only 4) plaintexts, ciphertext pairs. The cipher has good diffusion, no special structure that could make it weak, and no known weakness (and probably no weakness whatsoever) other than the low I/O degree of its S-boxes.” (from http://www.cryptosystem.net/aes/)

posted at: 09:54 :: permanent link

Illegal Primes

I was pointed to the illegal prime article on Wikipedia which describes how a prime number was constructed to contain the DeCSS source code which might therefor be illegal to posses. So here is my trivial implementation to construct your own (short) illegal prime in SAGE (using Pari’s next_prime() function). Use it like this:

sage: illegal_prime("My illegal statement")

This will return a prime number which contains the C-string of your message (big endian offcourse)

def illegal_prime(s):
    sx = [ hex(ord(ch))[2:] for ch in s] + ["00"]
    p = 0
    while not (hex(p)[2:]).lower().startswith("".join(sx)):
        ret = "".join(["0x"]+ sx + [hex(randint(0,10000000))[2:]] )    
        p =  next_prime(int(ret,16))
    return p

Update: added check whether a prime was found in the given range. All this is not very effective and the clean way would be to increase the random range that much that not finding a prime is more unlikely than a sack of gold materializing in front of you.

posted at: 16:44 :: permanent link

Even though not directly cryptography

I want to point the reader’s interrest towards two nice papers on Matt Blaze’s website. The first one is on safe cracking (yes the ones where you store money in) and the second is on wiretapping prevention (yes the one the feds do). Enjoy.

posted at: 11:19 :: permanent link