Interview: Professor M Kreuzer

From cyber security to algebraic equations, scroll to hear the real-world impact Martin’s work has had on the field of computer mathematics

Martin Kreuzer, mathematics professor at the University of Passau, Germany, chatted with editor in chief Delaram Kahrobaei about his research.

They discuss his research area, the logic behind his findings, and the article’s impact on the field of computer mathematics.

Martin’s article is free to read for a limited time only. You can access the full piece here: A fault attack on KCipher-2.

Click the video below to meet Martin and get his answer to, what exactly is a fault attack?

Keep scrolling to read, and listen to, the rest of the interview with Martin and find out what KCipher-2 is all about.

In his own words, he reveals his and his doctoral student’s code-breaking discovery and how mathematics is used practically to solve real-life problems.

So Martin, tell us, what is KCipher-2?

  • 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.

Click play to hear Martin’s answer

How did you 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.

Click play to reveal Martin’s answer

What is the impact of your work on real-life applications?

      Online safety and security
      • Having good ciphers available is important for secure communication, government communication, but also commercial communication, and even private communication – you want to have some privacy and security.

        Then, of course, when some new cryptosystems are proposed, people are analyzing these to find out if they are reasonably secure against the known attacks and also if there are new attacks that you can devise to attack such cryptosystems.

        For instance, in our case, some people have picked up on this new method and they made a tool, this is called Autoguess, and it was developed at the University of Graz in Austria, and they made a tool for finding these guess-and-determine attacks. For instance, it turned out that our proposed method is also very good to do something which is called the KeyBRIDGE, to find certain secret keys in key recovery attacks for block ciphers, so for a different kind of encryption.

        So, these new methods to break a cryptosystem can be applied to different kinds of ciphers and we should really check very carefully if the new proposals for new ciphers are secure against them.

      Click play to reveal Martin’s answer

      Where do you see the direction of your work going?

      • 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.

      Click play to reveal Martin’s answer

      What do you want people to take away from your research?

        Blackboard with chalk algebraic calculations written on it
        • In the long run, these algebraic methods, also combining algebra and logic, I think they have been a little bit underestimated. I think people should not just use the classical tools in computer science, but they should also pay attention a little bit more to the mathematical possibilities, that you can really analyze ciphers with mathematical tools more than is maybe done at the moment. This could be a starting point for bigger projects to use methods of computer algebra in cryptography.

        Click play to reveal Martin’s answer

        How does this interdisciplinary journal help to disseminate the work of researchers?

        • 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.

        Click play to reveal Martin’s answer

        Martin published his article under the International Journal of Computer Mathematics: Computer Systems Theory. Click the button below to read the journal’s full aims and scope. Here, you can find out more on the types of research typically accepted for publication. You can also browse current articles and the topics that have been published so far.

        Like Martin, you could be making a real-world impact with your research. Start your journey with us today and discover the possibilities.

        Find the latest posts from @tandfSTEM