Category Archives: Cryptography

Polynomial Interpolation

I have been reading “How to Share a Secret” in detail for the past few weeks, a revolutionary research paper by Adi Shamir. This paper applies some of the concepts of Number Theory and Algebra, one of which is polynomial interpolation, and has been used to construct a secure and reliable key management system. The theorem is simple and easy to understand, and has been applied in the best way one ever could.

Theorem: (Uniqueness of Polynomial Interpolation)

Consider n+1 unequal coordinates (x0,y0),(x1,y1),(x2,y2),…..,(xn,yn). According to the theorem of uniqueness of polynomial interpolation, there exists at most one polynomial p of degree less than or equal to such that:

p(xi) = yi;         i=0,…..,n

Remember the uniqueness for the satisfying polynomial is only for a particular degree. There can exist two polynomials of different degrees which contain all of these points.

Proof:

We are going to prove this theorem by contradiction.

Let us assume that there exist two polynomials p1 and p2 of degree less than or equal to n, that satisfying

p1(xi) = p2(xi) = yi;          i=0,…..,n

This implies: All the points lie on the graphs of p1 and p2. So, one can conclude that at these points, the difference between the polynomials is zero since the value is same for both of the polynomials on that point. We can generalize this as:

q(xi) = p1(xi) – p2(xi);          i=0,…..,n

The degree of the polynomial q(xi) is same as that of p1 and p2 i.e. less than or equal to n. We can conclude from the above that:

q(xi) = 0;          i=0,…..,n

Clearly, the polynomial has n+1 zeros. How is it possible? How can a polynomial of degree <= n have n+1 zeros? Yes, it can happen only when the polynomial q(xi) is a zero polynomial i.e. value of q is zero at all points of x in the Cartesian Plane.

Now, since q is a zero polynomial, from the above equations we have:

q(xi) = p1(xi) – p2(xi)

0 = p1(xi) – p2(xi)

p2(xi) = p1(xi); i=0,…..,n

Thus we have proved that the polynomials p2 and p1 are identical polynomials, making our assumption wrong. Hence, we have proved the theorem mentioned above by method of contradiction!

CBC Bit-Flipping Attack

In this blog post, the attack on CBC mode of block cipher encryption will be discussed and in the end, detailed writeup for the 16th challenge of Matasano-Crypto-Challenge i.e. about the Bit Flipping Attack in AES-CBC will be provided with explanation!

I want the reader to go through these concepts discussed in the following blog posts, before actually understanding how the CBC Bit-Flipping Attack works:

  1.  AES Mode Detection Oracle
  2.  AES Block Size Detection Oracle

We will list down all the information one must have access to, in order to initiate this attack:

  1. Cipher text
  2. Encryption Oracle as E(“random string” || payload || “another random string”)
    • Here, in this function, the attacker is allowed to supply input to the encryption function as payload. This function is literally the heart of the attack. All the arguments for the attack will be supplied here.
  3. Decryption Oracle

What is Bit Flipping Attack?

Bit Flipping Attack requires the mode of encryption used for encryption to be CBC(Cipher Block Chaining) about which is described in the previous blogs.

This attack is usually in scenarios where the encryption function takes in some input as a payload, prepends a random string, appends another string to it before encrypting it. There are cases where the encryption function escapes some characters or character sequences from the payload supplied, before encrypting it. For example let us consider this function:

def encrypt(payload):
    obj = AES.new(key, AES.MODE_CBC, iv)
    for i in xrange(len(payload)):
        if payload[i] == ";" or payload[i] == "=":
            payload = payload.replace(payload[i], "?")
    str1 = "comment1=cooking%20MCs;userdata=" + payload + ";comment2=%20like%20a%20pound%20of%20bacon"
    str1 = padding(str1)
    ciphertext = obj.encrypt(str1)
    return ciphertext

The function escapes “;” and “=” characters from the payload and then prepends and appends strings. It then encrypts the resultant string(concatenation of prepend string, payload and appended string).

The decryption function:

def decrypt(ciphertext):
    obj1 = AES.new(key,AES.MODE_CBC,iv)
    plaintext = obj1.decrypt(ciphertext)
    if ";admin=true;" in plaintext:
        print "Yes, you did it"
    else:
        print "Nope, you didn't"

The given decryption function checks if “;admin=true;” is still present in the decrypted string. If yes, then the payload leads to successful login as the admin. But the problem here is: during the encryption since the “;” and “=” characters are escaped from the payload, one cannot directly give “;admin=true;” as payload since the encryption function will change it to “?admin?true?” before encryption.

Brief summary:

  1. The encryption function takes in payload.
  2. Escapes some characters from payload; appends and prepends random string to the payload -> resultant string.
  3. Encrypts the resultant string and returns the cipher text.
  4. Decryption function decrypts the cipher text returned by the encryption function and checks if “;admin=true;” is present in the decrypted text. Since “;” and “=” are no longer present beside “admin”(due to escaping of characters), the decryption function does not allow login as the admin!

To understand the attack, we need to closely look how decryption takes place in this mode:

The decryption in CBC mode takes place as:

601px-CBC_decryption.svg

Let us suppose our “?admin?true?” is in the second block of plain text. This plain text block, is a result of XORing of cipher text of the same block and cipher text of the previous block, as we can see from the figure given above. Pay attention closely now. What I am in control of, are the cipher text blocks. The attacker can manipulate them, before sending them as a parameter to the decryption function. A rule says that whenever one changes one byte(call this “flips”) at an offset in a cipher text block, the same offset is changed in the next plain text block (See the figure below!). Of course, when one flips one byte in a cipher text block, plain text of the corresponding block also changes; but we are not worried about the flip in the plain text block where the “random bytes” of the prepend string are present. What we are focusing now is the second plain text block, which essentially contains our “?admin?true?”.

082113_1459_CBCByteFlip3

Let us consider,

  • The plain text block containing “?admin?true?” to be ‘P’.
  • The cipher text block next to which we have the plain text block containing “?admin?true?” to be ‘A’.
  • The cipher text block of the corresponding plain text block containing “?admin?true?” to be ‘B’.

Then we can write, (refer to the figure above)

A = P xor BlockCipherDecryption(B)

“BlockCipherDecryption” is the large block present in the figure as “Block Cipher Decryption” which decrypts a cipher text block based upon the standard encryption used. BlockCipherDecryption(B) is a constant since we are not flipping bits in “B” (Remember this!). For the nth byte of each block we can thus write,

A[n] = P[n] xor BlockCipherDecryption(B[n])    ——–> 1.

BlockCipherDecryption(B[n]) can be written as:

BlockCipherDecryption(B[n]) = A[n] xor P[n]     ——–> 2.

Value at 2. is fixed. We know that we want P[n] in 1. to be of our desired value(Let this be ‘PD’) whereas P[n] in 2. is the actual value of the plain text (Let this be ‘PA’) after the decryption of cipher text without flipping any of them. So, A[n] then becomes:

A[n] = PD xor A[n] xor PA

or A[n] = A[n] xor (PD xor PA)

PD xor PA —> XOR of the desired plain text byte with the actual byte present in the plain text block.

So, we simply XOR the result (PD xor PA) with the actual value of the A[n]. The result is the value we should give at that byte in the cipher text block previous to the plain text containing “?admin?true?”. Repeat this for all other blocks.

Cryptopals Challenge 16:

In this challenge, “;” and “=” are replaced by “?”. Here in this case, the desired value is “;” or “=”. XORing each with the actual value of plain text “?”, we get 4 and 2 respectively. Now we XOR this result with the offset in the actual cipher text block (A[n]). Repeat this for each byte to be manipulated. This gives the value to be supplied in the same offset so that the resultant plain text contains “;admin=true;” instead of “?admin?true?”. Here is the exploit:

cipher_list = []
payload = ";admin=true;"
ciphertext = encrypt(payload)
i = 0
while i*16 <= len(ciphertext):
    cipher_list.append(ciphertext[i*16: 16 + (i*16)])
    i += 1
cipher_list.remove(cipher_list[6])

attack_on_block = cipher_list[1]
list1 = list(attack_on_block)
list1[0] = chr(ord(list1[0]) ^ ord("?") ^ ord(";"))
list1[6] = chr(ord(list1[6]) ^ ord("?") ^ ord("="))
list1[11] = chr(ord(list1[11]) ^ ord("?") ^ ord(";"))
cipher_list[1] = ''.join(list1)
ciphertext = ''.join(cipher_list)

decrypt(ciphertext)

The entire solver script for this challenge can be found here: https://github.com/ashutosh1206/Matasano-Crypto-Challenges/blob/master/set2/p16/exploit.py

References:

  1. https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation
  2. Bit Flipping

All hail Cryptography!

Block-size Detection

In the previous blog, “Detecting the mode of block cipher being used” was discussed. In this blog, the second step in the attacking of a block cipher i.e. detecting the block size of the cipher, will be discussed. Link to the implementation script has been given at the end of this post which is written in python.

We need to closely look at the padding implementation in the block cipher in order to get the size of the block used. It is good that we list down the key points: the ones that are given and the ones that are needed to be found out, before jumping to the padding function:

Given:

  1. The mode used for encryption.
  2. The standard block cipher encryption used.
  3. The encryption function.
  4. The padding function.

One needs to find out the size of block used, having access to the above things. If  you closely looks at how padding is implemented in any oracle function, you can observe that the number of bytes to be padded is the minimum number of bytes required to be added to the plaintext string, such that the length of the padded string becomes a multiple of the block-size. But a thing to be mentioned here is that the number of bytes to be padded should have a minimum value of 1 and maximum value equal to the block-size.

For example, let the block-size of the cipher be 16 bytes and length of input string be 7 bytes. This gives the number of bytes to be padded equal to 16 – 7 = 8. When the input string is 18 bytes long then the number of bytes to be padded is equal to 16*2 – 18 = 14. When the input string is 16 then the number of bytes to be padded is 16. Generalizing it:


padlen = n - (l % n)

where “padlen” is the number of bytes to be padded, “n” is the block size and “l” is the length of the original unpadded string.

When one encrypts this padded string, the length of the ciphertext remains the same. One catch in the padding function, the length of the ciphertext remains the same when one increases the length of the input string by one each time, until the length of the input string becomes a multiple of the block-size because then an entire block will be added to the plain-text string having length equal to the block-size.

So, to detect the size of the block cipher, one can simply call the encryption function each time, giving a single character as an input and noting the length of the ciphertext for each time. Keep on appending single characters to the input string each time and note down the length of ciphertext each time and checking if the length of the ciphertext generated in the current iteration is equal to the one generated in the previous iteration or not. If not, then one can conclude that an entire block has been added to the original string, and hence the size of the block is equal to the difference between the length of the original string when the length of the ciphertext just changed and the length of its corresponding ciphertext.

Here is the implementation of the exploit:

https://github.com/ashutosh1206/Cryptography-Python/blob/master/blocksizedetect.py

Cheers! All Hail Cryptography!

AES Mode Detection Oracle

In a series of blogs, attacks on AES- Advanced Encryption Standard, will be discussed. There are a number of steps involved to break a block cipher (AES being one of them):

  1. Recognizing the mode of block cipher being used.
  2. Finding the size of the block being used in the block cipher.
  3. Implementing a suitable attack according the mode of block cipher and the standard encryption used.

In this post, the first step in the attacking of block cipher will be discussed.

According to Shannon’s Theory of Communication, a cipher can be regarded as a perfectly secure cipher if the cipher text reveals no information about the plaintext being encrypted. So, the entire idea behind the attack lies in finding patterns in ciphertext that loosens up the framework on which the encryption standard is based.

There are different modes of encryption being used in a block cipher, but only on ECB (Electronic Code Book) and CBC (Cipher Block Chaining) will be focused as for now.

ECB mode of encryption:

This is the most insecure mode of encryption and one will realize it looking at this representation of ECB mode:

601px-ECB_encryption

In this mode, same key is used to generate ciphertext block of the corresponding plaintext block. This exposes one vulnerability: since the key and the block cipher encryption algorithm remain the same across the entire process of encryption of plaintext, two plaintext blocks containing the same text, will have the same set of ciphertext blocks. So, in case two of the ciphertext blocks have the same value, the attacker can easily recognize that the plaintext contains a group of characters that are being repeated. This reveals some information about the plaintext and hence, according to Shannon, AES in ECB mode is not a perfectly secure cipher!

For example, let us assume the encryption used is AES and the block size is 16 bytes. Let the plaintext be “abcdefghijklmnopabcdefghijklmnop”. After padding there are three (Three, because the size of the original plaintext is exactly a multiple of block size, thus one more block of padded data has to be added due to reasons of security) blocks in the padded plaintext. What is peculiar about the plaintext is that two of the blocks contain the same data in them, i.e. “abcdefghijklmnop” is the content of two of the blocks! They then generate the same 16-byte ciphertext block!

So, to recognize whether a block cipher uses ECB or CBC mode of encryption, we just need to supply the input in the plaintext such that two plaintext blocks contain the same contents and then observe the corresponding ciphertext. If two of the ciphertext blocks have the same value, the encryption used is ECB otherwise another mode of encryption is used! (CBC in this case as only two modes are being discusses here)

CBC mode of encryption:

This mode of encryption has nullified the vulnerability that is present in the ECB mode of encryption. This mode of encryption is vulnerable to Padding Oracle Attacks and Bit Flipping Attacks which will be discussed in the next few blog posts. The encryption in the CBC mode looks like this:

601px-CBC_encryption

Although the key used is same for every block, there is an additional step when compared to ECB and that is XORing of the padded plaintext block with a value and then encrypting it using a key. For the first block, the value is generated in a pseudo-random way for the first plaintext block, for the next block onwards, the value is the ciphertext block generated in the previous step.

So, using these essential characterstics peculiar to each mode, we are now able to decide if the cipher is encrypted using a particular mode (ECB or CBC). Following is the link to the python code for detecting this:

https://github.com/ashutosh1206/Cryptography-Python/blob/master/detectmode.py

See you until next time!