Implementing RSA in Python from Scratch (Part 3)
Please note that it is essential for me to emphasize that the code and techniques presented here are intended solely for educational purposes and should never be employed in real-world applications without careful consideration and expert guidance.
At the same time, understanding the principles of RSA cryptography and exploring various implementations is valuable for educational purposes and understanding how to code encryption methods, building secure encryption systems for practical use requires adherence to industry standards, best practices, and thorough security assessments. An inadequate implementation or improper usage of cryptographic techniques can lead to severe vulnerabilities, jeopardizing the confidentiality and integrity of sensitive data.
In case you missed it, Part 1 and Part 2 are also available for reading if you are interested in the full series of articles which we provide on Implementing RSA in Python from Scratch.
TheLastTechie
TheLastTechie
Side-Channel Attacks
The first 2 articles focused mainly on the idea and implementation of RSA. As such they left out a relevant topic in modern encryption. Side-channel attacks take advantage of data we'd usually brush off as gibberish, such as hardware sounds, electromagnetic waves and timing. Timing attacks are most common because they are the easiest to perform and can be performed on long-distance computers such as online servers.
Timing Attacks
To be able to perform a timing attack, the attacker must have the power to choose which message will be decrypted by the target device. This often is the case, especially in case of an online server, where the attacker doesn't even have to be near the computer to steal sensitive information from it.
Understanding Timing Attack
The attack was first concieved by Paul Kocher and is based on the following:
Many systems will speed up the modulo operation `a % b` by checking whether `a` is less than `b`. This also means that if `a` is bigger than `b`, the operation will take more time. How can this be exploited? Let's look at the following exponentiation with modulo implementation.
def modpow(b, e, n):
# find length of e in bits
tst = 1
siz = 0
while e >= tst:
tst <<= 1
siz += 1
siz -= 1
# calculate the result
r = 1
for i in range(siz, -1, -1):
r = (r * r) % n
if (e >> i) & 1:
r = (r * b) % n
return rAfter the operation at the position of the first non-zero bit (d0), this value (stored in r) will be squared and, if the second bit of d (d1) equals 1, it will be multiplied by m. This means that we can discover the value of d1 if we can craft 2 messages a and b such that on one a modulo operation needs to be calculated and on the other it can be avoided, we can find out whether this operation takes place or not.
These a and b need to be such that a2 < N < a3 and b3 < N. Encryption of message a should, on average, take longer than encryption of message b if d1 equals 1.
Now that we know bit d1 we know the temporary value that will be squared and possibly multiplied by m depending on the value of the second bit d2. In other words, we repeat the same process but this time we choose a and b such that temp_val(a)2 < N < temp_val(a)2 * a and temp_val(b)2 * b < N, temp_val(x) being the mentioned temporary value for a given x.
The Implementation
Initial a and bare relatively easy to find with a binary search approximation method, but every next one is not so easy because we have temp_val which depends on a and b and computing it involves modulo (temp_val(x) = xcurrently_known_bits % N) so instead the program will take a 1 000 000 randomly chosen numbers between 1 and N and out of those pick the ones that satisfy conditions for a and b.
Then the program will calculate average times for a and b to decrypt and then check if a > b + f to know whether the current bit is 1. f can be determined empirically.
After 1024 repetitions all bits will be found and all that is left to do is to determine the number of leading zeros. This can be done by simply shifting the 1024-bit result to the right and checking it's validity by choosing a random message and exponentiating it with the product of encryption key and the result until the correct value for d has been found.
Protection Against Attacks
There is a commonly used method called RSA binding. Given a message to be decrypted m:
- Pick a random
r - Calculate the value
x = C * re - Calculate
xd * r-1
Using this approach, attacker doesn't know which value will be given to the fast exponentiation function, which is a prerequisite for this attack to occur.
The Conclusion
It seems that even though the mathematical background is strong and steady, side-channels can make various implementations insecure and unreliable. When writing software that will deal with sensitive data, one should always consider the possibility of side-channels being exploited.
Do you like what you're reading from the CoderOasis Technology Blog? We recommend reading our Hacktivism: Social Justice by Data Leaks and Defacements as your next choice.
ExiledTech
The CoderOasis Community
Did you know we have a Community Forums and Discord Server? which we invite everyone to join us? Want to discuss this article with other members of our community? Want to join a laid back place to chill and discuss topics like programming, cybersecurity, web development, and Linux? Consider joining us today!
