Generalized Linear and Differential Cryptanalysis Check for any Block Cipher — R.C.Bose Summer Research Internship ISI,Kol 2019
Much interested in Theoretical Computer Science, I had applied for the Summer Internship Program that R.C. Bose Centre for Cryptology and Security at the Indian Statistical Institute,Kolkata offers. They take around 30 students every year from the country, where you get to work with a few of the best researchers in the country in the field of Cryptography and Information Security, and try to bring up something very new within that intense research period of 2 months. Being a maths enthusiast, this was a good break for me to delve into the application field of mathematics and computer science and learn how they are applied in the real world scenario.
This is just an informal internship experience/report. You might want to continue if you’re up for a casual blog-read :D
Note: The underlined sentences are direct links to the related topics/persons.
Initial Reading Project under Prof. Bimal Roy and Dr. Mridul Nandi
Initially, I started stepping into the world of modern cryptography under the guidance of Padma Shri Prof. Bimal Roy, as he introduced me to certain classical (through Stinson’s epic book Cryptography: Theory and Practice) methodologies of encoding followed by modern real-world problem scenarios like statistical measures of e-voting and it’s security,etc. He encouraged me to learn the basics initially and slowly try to figure out what topics I might be interested to work on. To be honest, never had I seen a professor as brilliant as Prof. Roy before. His capabilities to explain extremely complicated problem statements and their solutions, like maybe a hard Z-K Proof problem, in such simple manner,like a story, in his cabin,with extremely non-trivial yet such simple solutions, left as awe-struck and intrigued for even hours after our interactions.
During this time I tried implementing all the classical encryption and decryption algorithms on my own that were used in earlier days(they are pretty much useless nowadays though) like Shift cipher, Vigenere cipher, Affine cipher,etc. The codes can be seen here: https://github.com/swastikbanerjee07/Classical-Cryptanalysis-Methods-of-Basic-Ciphertexts-using-CPP-
After that, I was supervised by Dr. Mridul Nandi while reading about Block Ciphers and natures of SPN (Substitution-Permutation Networks) structures in details. I was given the task of reading about AES(Advanced Encryption Standard) and it’s modes of operations, and asked to give special attention to GCM(Galois Counter Mode of operation) and try to implement it in an optimized way in hardware(ARM architecture)!
Trust me, with not even two weeks properly into the field of cryptographic research and me being asked to optimize AES in assembly level language, I was literally going through a brainstorm for the first few days, trying to figure out what the heck all these mean. But that’s how all researchers have started their life I guess xD , so yeah it was pretty fun and challenging to be honest!
Special thanks to my friend Rishav Kundu for introducing me to godbolt.org. It’s an awesome site, you should try it!
Slowly, I started getting an idea soon about how the ciphers were working with the way they were designed. Cristof Paar was to the rescue, explaining quite complicated chapters in such an easy-to-grasp manner in a few hours, from GF Fields to the story of The Fall of DES, and then again the rise of Rijndael, you can find all his lectures here: https://www.youtube.com/channel/UC1usFRN4LCMcfIV7UjHNuQg/videos . These things are pretty basics in crypto, but trust me, if you don’t know them, you won’t know why you might want to take up cryptography as your research field.
During this time, when I was frantically searching for papers from where I could understand the working principles of block ciphers, especially AES in details, this blog came to be very useful for me: https://blog.nindalf.com/posts/implementing-aes/. From A Stick Figure Guide to AES, to FIPS-197 Document(the best in my opinion amongst all if you ever want to understand AES in details) with elaborated algorithm of each step of AES, I finally started feeling I could implement AES on my own now from scratch.
However, during implementation, I couldn’t get much help from the net ‘cause most of the implementations of AES have used some kind of libraries or the other, either cryptlib, or Crypto++ or OpenSSL, etc. and literally there are no implementations from scratch, which I was pretty amazed to see!(if you find one, do share me the link). So, it was kinda a unique thing to implement AES from scratch on my own.
Here is the implementation, in a repo where I probably plan to implement a few more ciphers in future from scratch(Midori is in my head, what do’ya think? Any more suggestions?) : https://github.com/swastikbanerjee07/Implementation-of-a-few-basic-ciphers-from-scratch
After that I was given a task to try to optimize GCM for software instructions and compare it with existing optimized codes of GCM.
But later my supervisor asked me to keep this as a future task and gave me something else to work on.
Final Project Under Dr. Nilanjan Datta and Mr. Ashwin Jha
For the last 3 weeks till July 5th, I worked along with Suvraneel Chatterjee on something very specific: Linear and Differential Cryptanalysis check for Block Ciphers using Mixed Integer Linear Programming and extending it for all ciphers using concepts of OOPs so that it works like an API.
My mentors were two of the most amazing persons I’ve met till date: Dr. Nilanjan Datta and Mr. Ashwin Jha. We spent hours in the CRG Lab of ISI ASU Block,8th floor in S.N. Bose Building together with them, trying to figure out a better optimization technique or scratching our heads out to find out a bug, and when we could solve them together, that sheer reflection of ‘as if a ‘victory’ ’ in the face of even our supervisors were a proof of how passionate these people were about the art of problem solving!
Okay, so I’ll try to give a li’l bit of detailed insight about the work I took up as my final project:
My task was to study the linear and non-linear properties of Block Ciphers with SPN(Substitution-Permutation Network) structure and exploit those to find the number of Active S-Boxes in each round of the cipher using Mixed Integer Linear Programming, and then using the relation between Differential Probability and the Differential Characteristics of the cipher, find out whether the cipher would be resistant against linear and differential cryptanalysis or not. N Mouha in his paper had written a code to find the minimum number of S-boxes for AES using LP instructions, but we found out it doesn’t work for all SPN structures. So we updated the code into something more generalized to work for any block cipher. I have mailed Mouha citing this, but didn’t get a reply yet :P
Since the project has further scope to be built upon from where it stands today, most of the work has been instructed to be kept as private(in the hope that perhaps this seed might bore some fruit someday and bloom into a paper :P )
Apart from AES, we checked our outputs for the cipher Midori also upto 7 rounds, and we got pretty accurate results within around 2 seconds.
Hehe That Pretty Much Sums It Up!
Further Readings
- This project has a lot of scope to be built further and implemented in hardware.
- I’d like to work on the side-project that became a task to be completed in future during the internship,i.e. Optimized Implementation of AES GCM in Hardware and Software.
- https://eprint.iacr.org/2016/714.pdf This is a good paper on Hardware implementation of AES and it’s optimization.
- There were quite a few other materials too that we were given from R.C. Bose that we are instructed not to post publicly. If you’d like to read about them, do hit me up. I’d be glad to help with some maybe, personally! :)
That’s it for this blog on my first summer research internship as an undergrad. I’ll try to write further blogs on my attempts at solving Cryptopals Crypto Challenges in future(if I be able to make any attempt in the right direction at all! :P).
Till then, ciao !
