CRYPTO …1

Taking up where we left from previous blog post: CRYPTO 101 we will now discuss the other two attacks on RSA namely as common modulus & side-channel(timing attack). While the first attacks the math behind the cryptosystem the latter attacks the implementation rather than the actual math of the cryptosystem.

1. Common Modulus attack:

We will take this example common_modulus_question. Suppose there is a similar message encrypted with the keys issued to the employees by the organization such that the modulus n of the keys is same  with different exponent e such that gcd(e1,e2)=1 and their respective different private components d. Can we decrypt the message? Let’s see 😉 with a little bit of math behind it.
In RSA reverting back to previous blog post, the encrypted message are such that: c1=m^e1mod n  & c2=m^e2mod n – (i)
If we have two numbers x and y such that (e1 . x) + (e2 . y) = 1 then we can decrypt the message as ( c1 ^x) . (c2 ^x) mod n = m. Let’s put the values in (i) we will get m^{(e1 . x + e2 . y)} = m ¹ = m.Therefore (e1 . x) + (e2 . y) = gcd(e1,e2). To calculate y we need to do i as modular multiplicative inverse of c2 w.r.t. n hence: let i^-y = c2^y since y comes out as negative. So finally we have m = (c1^x) . i^-y mod n to get the plain text (check above link if you need more explanation on maths). Now some juicy part again we will go with python :-).
We will implement Euclid’s algorithm: Let’s first calculate the gcd.

def gcd(a,b):
 while (b! = 0):
  c = a%b
  a = b
  b = c
 return(a)

now to get euclid’s constant the function xgcd as:

def xgcd(x,y):
 if y == 0:
  return [1,0,x]
 else:
  x1,y1,d = xgcd(y, x%y)
  return [y1, x1 - (x//y)*y1, d]

Finally the modular-inverse as:

def modInverse(a, m):

    if gcd(a, m) != 1:
        return None # no mod inverse if a & m aren't relatively prime

    u1, u2, u3 = 1, 0, a
    v1, v2, v3 = 0, 1, m
    while v3 != 0:
        q = u3 // v3 # // is integer division operator for python3 / for python2
        v1, v2, v3, u1, u2, u3 = (u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3
return u1 % m

Finally putting the whole code together with parameters (c1, c2, e1, e2, n) as: Common_modulus_attack.py can be run with above parameters supplied to the program in long decimal values to get the decrypted plain-text message.
Note: this attack was possible again by choosing ill keys and more importantly same modulus for the keys and can be easily avoided!

2. Side Channel attack(timing):

This type of  attack arises due to the hardware implementation of the cryptosystem and is not limited to RSA many other systems such as hashing, Diffie-Helleman etc..etc.. well almost any cryptosystem that utilizes the hardware resources at a certain extreme point may suffer from this kind of attack. More the attacker knows about the underlying hardware and resources available for crypting/hashing, more chances are that he will likely to succeed in the attack. We will look over a very simple form of this kind of attack called as the service-timing attack there are different versions of side-channel attack which even I don’t know all and most importantly have not tested them but you’re most welcome to further research here side_channel_attack and do link me to others in comment if you find them implemented elsewhere 🙂 .

The timing attack is a pretty simple yet very useful attack from perspective of the attacker since the underlying maths of the system remain intact while the attacker is successful in stealing the key or the password for the system. It requires some patience that’s all ;-). Suppose from the Wikipedia page for timing attack we have the following code snippet in V-basic that check’s the password provided by the attacker:

Function InsecureCompare(StrA As String, StrB As String, length As Integer) As Boolean
Dim result As Boolean
For i = 1 To length
If Mid(StrA, i, 1) <> Mid(StrB, i, 1) Then Exit For
Next
InsecureCompare = (i > length)
End Function
Here we can see that if the attacker supplied ABCD where the password contains characters ABCD except C at position ABxD then due to the implementation of the code it will iterate through the loop 3 times and then comes out therefore attacker will know the character C is not the correct one in password hence in this way one-by-one with patience the attacker can guess the whole key just by looking at the time taken to check the string/character sent by him/her. There are many different Ctf’s challenges for the same attack, although it can be done manually we will use python as well as some manual handling to make this to work and a lot of patience.

import time               # for checking the time taken to return our query
import socket
charset="adcdef+,?/}{[]" # for checking
dic={}                   # to store timing difference response
ch = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
ch.connect((server,port))
for c in charset:
  start_time=time.time()
  ch.send(bytes(c.'utf-8')) # if via internet
  finish_time=time.time() - start_time
  print("--- %s seconds for %s" % (finish_time, c))
  dic[c] = finish_time
print('\n')
guess=max(dic.keys(), key=(lambda key: dic[key]))#to get the one response with max time
print("probable-guess for key: %s" % guess)

The snippet can be modified as per need and is very simple to understand. The timing response from each query is measured and stored in a dictionary and at last the response which took maximum time to execute is probably the correct response from all. Hence one-by-one we can decrypt the entire key or password used to encrypt the communication or system.

Note: The underlying system should not be based on the security through obscurity since sooner or later the attacker can reverse-engineer the underlying hardware implemented in the system therefore the code should be written in such a way that a  proper rather constant timing response should be generated by the system even in case of false or correct input by the attacker.

Whoah!! that’s enough crypto for one day. Next we will try and learn other crypto based attacks as I learned and more importantly solve them. Will be back with more after a few days. Some scripts and context is mine while some is taken from numerous repos. and blogs.

Comment if you see something wrong or need more clarifications on the topics and thanks for stopping-by. Until next time! 🙂