![[malb]](http://www.informatik.uni-bremen.de/~malb/images/blog.png "back to main"){kind=small}
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.”
Fri, 14. Nov 2008CPNI-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.
Thu, 30. Oct 2008Algebraic 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. …”
Thu, 18. Sep 2008Equation 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.
Tue, 16. Sep 2008New 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.
Tue, 03. Jun 2008AES 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.
Thu, 17. Apr 2008Algebraic 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.
Wed, 20. Feb 2008“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.
Sun, 20. Jan 2008CFP: 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)
…”
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?
Fri, 10. Aug 2007Those 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).”
Mon, 07. May 2007CTC 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.
Thu, 26. Apr 2007CTC2
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.
Fri, 02. Mar 2007Random 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.
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.
Tue, 13. Feb 2007Cryptanalysis
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.
Sun, 21. Jan 2007Talks
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.
Tue, 19. Dec 2006Hell 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.
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.
Fri, 15. Dec 2006Government 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.
Wed, 22. Nov 2006Conditional 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.
Sun, 05. Nov 2006Diplomarbeit 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?
Sun, 01. Oct 2006ATM 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.
Fri, 15. Sep 2006Old 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).
Sat, 20. May 2006
“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.
Thu, 27. Apr 2006Algebraic 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/)
Tue, 18. Apr 2006Illegal 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.
Wed, 14. Dec 2005Even 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.
Tue, 25. Oct 2005del.icio.us/malb
I’ve moved the algebraic cryptanalysis literature/link list to http://del.icio.us/malb so I can easily add stuff when I stumble across it.
Mon, 24. Oct 2005Some Literature on Algebraic Attacks
The paper on XL by Nicolas Courtois, Alexander Klimov , Jacques Patarin, and Adi Shamir should be well known so as the paper on XSL by Nicolas Courtois and Josef Pieprzyk. Furthermore the translation of AES to BES by S.P. Murphy and M.J.B. Robshaw (errate ) is widely discussed. While the F4 algorithm by Jean-Charles Faugere isn’t that much discussed when talking about attacks on AES it’s power has been demonstrated in the Hidden Field Encryption crypto challenge.
But there is more: A.J.M. Seegers wrote his master thesis on XL and F4 “from a Gröbner Basis perspective” showing that XL is a Gröbner Base algorithm and Elizabeth Kleiman wrote her on an attack against a 16-bit “Baby AES”.
