Interview: Professor M Kreuzer

This is a special stream cipher. Stream ciphers are used, for instance, for mobile communication, also for any kind of communication where you have a stream of data that you want to encrypt.

KCipher-2 is the recommended cipher on the Japanese government cipher list. Two sources of good ciphers: one is called the eSTREAM portfolio, which was made in Europe, and then this other list is this Japanese government list, and it contains two stream ciphers. The most recommended one is KCipher-2.

Of course, when it was analyzed, it was thought to be secure against this kind of fault attack, but now, my student and I, we describe an attack which can really break this cipher.

Well, it’s called a guess-and-determine attack, so you try to guess one of the unknown bits. So the unknown bit could be zero or one, and you try to solve for the system of equations that you get for the cipher in this way. But then maybe you cannot solve it, so you have to guess a second bit. Then the problem is how to choose the bits that you want to guess, so this is called a guess-and-determine attack.

To find a good order in which to guess these bits, we want to maximize the information gain for these guesses. So you have to describe, somehow, if you solve for one bit then what can you get from information for this bit for another one. And we describe this using certain logic formulas, and then we have to find something which is called the optimal guessing path, so you have to find the best path to choose the information that you want to get next. And for this we use a method from computer algebra, and this is called the method of Gröbner basis. So, we bring together different approaches coming from logic and from computer algebra to solve this question about the security of the stream cipher, K-Cipher 2.

For me, it is very interesting to integrate the methods of computer algebra, where I’m the most specialized in, with the methods of logic and other areas of mathematics to solve this kind of polynomial system. It’s called a Boolean polynomial system that you get when you analyze the security of crypto tools. So, you can, of course, formalize in this way all kinds of attacks against cryptographic devices. Some are called algebraic attacks. You just attack the full algorithm, or you can do this kind of hardware attack that you will induce a fault and you try to create extra equations, which are called fault equations. So, you get very special types of polynomial systems. Of course, solving polynomial systems is one of the main tasks of computer algebra.

But here, I’m very interested in using the special properties of these systems that you get from cryptography because, in general, to solve polynomial systems is really, really difficult and we should not expect to be able to solve polynomial systems with many hundred or even thousands of unknowns. But, here, in this special case for the cryptographic devices, we get special systems with properties and can try to use these properties and find new algorithms combining the classical methods of logic and also the methods of computer algebra to solve these special types. So, this is something that interests me a lot, of course, because it also helps us to develop new applications of computer algebra, and it helps us also to develop new secure cryptographic algorithms.

I think it is already doing a very good job in this direction because it is already a journal which is also read by computer scientists, not just mathematicians. If you publish this kind of work in journals only about computer algebra, or about logic, then maybe you don’t reach the good audience.

So, as I said, I think that it is very important to make people in computer science, in engineering, who really devise those chips and those algorithms, aware of the mathematical possibilities of analyzing those things. So, this journal, I think, is very well positioned to disseminate new mathematical algorithms and new mathematical methods through the good audience.