All posts by Ashutosh Ahelleya

s0rc3r3r, 19, CSE 2nd Year Undergrad at Amrita University: Amritapuri Campus, India. Cryptanalyst at bi0s CTF team, Avid Reader, Security Researcher and Enthusiast.

Finite Fields- Number Theory

This blog post covers one of the most important Mathematical Structures for Cryptography- Fields. It is used in both Symmetric and Asymmetric key Cryptography. This blog post gives a basic introduction to Finite Fields and arithmetic operations on it, but I hope the purpose of it is served- to make people, who don’t have basic knowledge about this, understand a few upcoming CTF write-ups, that are based on Finite Fields.

Field

A set F of elements with an operation o that combines two elements of F using the following criteria:

    1. Closure: If A and B are two elements belonging to Field F, then the result of the operation A o B must also belong to F.
    2. Associative: If A, B and C are elements belong to F, then (A o B) o C = A o (B o C)
  1. Identity Element: There exists an element e in F such that for any A belonging to F, A o e = A, where o can be + or *
  2. Additive Inverse: For every element A in F, there exists A-1 in F such that                  A + A-1 = 0
  3. Multiplicative Inverse: For every element A except 0 in F, there exists A-1 in F such that A * A-1 = 1
  4. Distributive

Theorem of Finite Fields: Finite Fields only exist if they have pm elements, where p is a prime number and m is a positive integer → p>=2

  1. For example: GF(11**1), GF(81) = GF(3**4), GF(256) = GF(2**8)
  2. Note that finite fields with p = 2 are of very importance
  3. GF(256 = 2**8) is used in AES

Classification of Finite Fields:

  1. m = 1, GF(p) → Prime Fields
  2. m > 1, GF(pm) → Extension Fields

Extension Fields are of importance in crypto (For example GF(2**8))

Prime Field Arithmetic:

  1. Elements of a prime field GF(p) are the integers {0,1,…,p-1}, where is a prime number
  2. Addition, subtraction, multiplication
    1. For a,b belonging to GF(p) = {0,1,…,p-1}
    2. a o b congruent to c over mod p, where o can be +,-,*
  3. Inversion
    1. For a belonging to GF(p), then a-1 must satisfy a o a-1 congruent to 1 mod p (Multiplicative Inverse). Multiplicative inverse can be calculated using Euclid’s Extended Algorithm
    2. For a belonging to GF(p), then a-1 must satisfy a o a-1 congruent to 0 mod p (Additive Inverse)

Extension Field Arithmetic GF(2m):

  1. Element Representation
    1. The elements of GF(2m) are polynomials am-1xm-1 + … + a1x + a0
    2. ai belongs to the prime field GF(2) = {0,1}
    3. Example: GF(23) = a2x2 + a1x + a0 = (a2, a1, a0) → A vector
      1. Since the value of ai can only be 0 or 1, we can enumerate all the possible values to get the Galois Field.
      2. GF(23) = {0, 1, x, x+1, x2, x2+1, x2+x, x2+x+1}
  2. Computing the polynomials i.e. the elements of Galois Field
    1. Addition and Subtraction in GF(2m)
      1. Let A(x) and B(x) be elements belonging to GF(2m). Then
        1. C(x) = A(x) +/- B(x) = cix, for i = 0,…,m-1,                                                   ci = (ai +/- bi) mod 2 = (ai + bi) mod 2
      2. GF(23): A(x) = x2 + x + 1, B(x) = x2 + 1, Compute A(x) + B(x)
        1. C(x) = ((1+1)%2)x2 + ((1+0)%2)x + ((1+1)%2)
        2. C(x) = x
    2. Multiplication in GF(2m)
      1. Let A(x) and B(x) be elements belonging to GF(23). Then
        1. C’(x) = A(x)*B(x) = (x2+x+1)*(x2+1)
        2. C’(x) = x4+x3+x2+x2+x+1 = x4+x3+x+1
        3. The present C’(x) we have does not belong to the Galois Field, so we divide it by a polynomial that behaves like a prime (so that it cannot be factored). These polynomials are called irreducible polynomials.
        4. P(x) = pixi, pi belongs to GF(2)
          1. C(x) = A(x).B(x) mod P(x) where P(x) is an irreducible polynomial.
          2. P(x) in this case is x3+x+1
          3. Therefore, C(x) = x2+x is congruent to A(x).B(x) mod P(x)
      2. For every field, GF(2m) there are several irreducible polynomials. Therefore, the irreducible polynomial has to be given in the first place.
    3. Inversion in GF(2m)
      1. For A(x) in GF(2m), A-1(x) can be calculated by Extended Euclidean Algorithm

 

 

 

Advertisements

ASIS Finals CTF 2017- Gracias Writeup

 

Points: 287    Solves: 9    CategoryCrypto
Description: Some people think that combination of cryptographic systems will definitely improve the security. That’s your turn to prove them wrong.

This challenge is a bit simpler than it looks like. It is a multi-prime RSA challenge where we are given an encryption script, which has two functions, one that generates public and private keys and another that encrypts using the public key generated from the first function.

The function that generates public and private keys:

def make_pubpri(nbit):
    p, q, r = [ getPrime(nbit) for _ in xrange(3)]
    n = p * q * r
    phi = (p-1)*(q-1)*(r-1)
    l = min([p, q, r])
    d = getPrime(1)
    e = inverse(d, phi)
    a = gensafeprime.generate(2*nbit)
    while True:
        g = getRandomRange(2, a)
        if pow(g, 2, a) != 1 and pow(g, a/2, a) != 1:
            break
    return (n, e, a, g), (n, d, a, g)

There are three-512 bit primes- p, q, r being generated in this RSA Encryption instead of two. The decryption exponent d, is generated as a 256-bit prime. The function is returning n, e, a, g as the public key.

The following is the encryption function:

def encrypt(m, pub):
    n, e, a, g = pub
    k = getRandomRange(2, a)
    K = pow(g, k, a)
    c1, c2 = pow(k, e, n), (m * K) % a
    return c1, c2

Unlike the conventional RSA encryption, here the message is not encrypted using RSA; instead of that, k is encrypted using the public key exponent e, the ciphertext of which is c1. There is another ciphertext variable returned in the function along with c1 that is:

c2 = (m * K) % a

K = pow(g, k, a)

So, the flow of attack on this challenge is as follows:

  1. Decrypt the ciphertext c1 to get k.
  2. Use this to generate as given in the code and then simply multiply c2 with multiplicative inverse of over modulus a, to get the message m.

Here are the values of public key variables given:

n = 1696852658826990842058316561963467335977986730245296081842693913454799128341723605666024757923000936875008280288574503060506225324560725525210728761064310034604441130912702077320696660565727540525259413564999213382434231194132697630244074950529107794905761549606578049632101483460345878198682237227139704889943489709170676301481918176902970896183163611197618458670928730764124354693594769219086662173889094843054787693685403229558143793832013288487194871165461567L

e = 814161885590044357190593282132583612817366020133424034468187008267919006610450334193936389251944312061685926620628676079561886595567219325737685515818965422518820810326234612624290774570873983198113409686391355443155606621049101005048872030700143084978689888823664771959905075795440800042648923901406744546140059930315752131296763893979780940230041254506456283030727953969468933552050776243515721233426119581636614777596169466339421956338478341355508343072697451L

The first thought that comes to my mind to solve step-1 in the flow of attack is Wiener’s Attack. By just looking at n and e values, we can suspect it to be vulnerable to Wiener’s Attack (Number of digits in each is almost the same, consider it a guess). I verified the criteria for it to be vulnerable to Wiener’s Attack (i.e. d<(1/3)*(N1/4)  or   e>N3/2) and found that e, i.e. the public key exponent, is a few bits smaller than N3/2, which made me conclude that d, i.e. the private key exponent, must be a few bits greater than (1/3)*(N1/4). So, the values fail to fall under the conventional criteria of Wiener’s Attack, by a few bits. But I wrote this script implementing Wiener’s Attack in python-sage to check if it really works.

Note that k is encrypted instead of message m, thus I used a temporary message m=12345, encrypted it using the same public key exponent e and modulus n, and finally tried Wiener’s Attack on this; thus the script:

from sage.all import continued_fraction, Integer
def wiener(e, n):
	m = 12345
	c = pow(m, e, n)

	list1 = continued_fraction(Integer(e)/Integer(n))
	conv = list1.convergents()
	for i in conv:
		d = int(i.denominator())
		m1 = pow(c, d, n)
		if m1 == m:
			return d
pubkey = (1696852658826990842058316561963467335977986730245296081842693913454799128341723605666024757923000936875008280288574503060506225324560725525210728761064310034604441130912702077320696660565727540525259413564999213382434231194132697630244074950529107794905761549606578049632101483460345878198682237227139704889943489709170676301481918176902970896183163611197618458670928730764124354693594769219086662173889094843054787693685403229558143793832013288487194871165461567L, 814161885590044357190593282132583612817366020133424034468187008267919006610450334193936389251944312061685926620628676079561886595567219325737685515818965422518820810326234612624290774570873983198113409686391355443155606621049101005048872030700143084978689888823664771959905075795440800042648923901406744546140059930315752131296763893979780940230041254506456283030727953969468933552050776243515721233426119581636614777596169466339421956338478341355508343072697451L, 171012227587318507773834753911094468358648971527111097308935888531930900156798659257578479378777764146070352809723708236353390208094909385240006920137781562826981091183813955039359863361624869703055918575613667858215532572602435432258750639197322091887713402631456113333645709142822182724397962837201266977523L, 96969753191136466007366303619618019752521508403657426306543836447071659732926802256183021740376016065813234292694535879838415771865207311953800116203362150588941093508091412441933752168889516206420588410478242229762908362637083786338280959547015086176046206126019992386890758970740552952647510652431386064722L)
n, e, a, g = pubkey
print wiener(e, n)

As expected, the function did not return anything. I could not find any other vulnerability in the code except the Wiener’s Attack and the close values of e and n suggested that there must be some kind of a Wiener’s Attack vulnerability, although not the conventional one. I found another variant of Wiener’s Attack upon searching more about it. There is a paper by Andrej Dujella on a variant of Wiener’s Attack and it works well when the size of d is just a few bits greater than N1/4.

You can check the paper here: A Variant of Wiener’s Attack on RSA

Here is a conclusion of the paper which is significant in our attack:

  1. Along with d being the denominator of the convergent of the continued fraction of (e/n), the decryption exponent can also be written in the form:
    1. a.    d = r*qm+1 + s*qm

Here qm+1 and qm are the (m+1)th and mth denominators of the convergents of the continued fraction of (e/n) respectively.

I assigned q0 = 1 and q1 as the first denominator of the convergent of continued fraction of (e/n). Here is the exploit for Step-1 where I implemented the Wiener’s Attack using the conclusion from the paper I described above:

def wiener(e, n):
	m = 12345
	c = pow(m, e, n)
	q0 = 1

	list1 = continued_fraction(Integer(e)/Integer(n))
	conv = list1.convergents()
	for i in conv:
		k = i.numerator()
		q1 = i.denominator()

		for r in range(20):
			for s in range(20):
				d = r*q1 + s*q0
				m1 = pow(c, d, n)
				if m1 == m:
					return d
		q0 = q1

pubkey = (1696852658826990842058316561963467335977986730245296081842693913454799128341723605666024757923000936875008280288574503060506225324560725525210728761064310034604441130912702077320696660565727540525259413564999213382434231194132697630244074950529107794905761549606578049632101483460345878198682237227139704889943489709170676301481918176902970896183163611197618458670928730764124354693594769219086662173889094843054787693685403229558143793832013288487194871165461567L, 814161885590044357190593282132583612817366020133424034468187008267919006610450334193936389251944312061685926620628676079561886595567219325737685515818965422518820810326234612624290774570873983198113409686391355443155606621049101005048872030700143084978689888823664771959905075795440800042648923901406744546140059930315752131296763893979780940230041254506456283030727953969468933552050776243515721233426119581636614777596169466339421956338478341355508343072697451L, 171012227587318507773834753911094468358648971527111097308935888531930900156798659257578479378777764146070352809723708236353390208094909385240006920137781562826981091183813955039359863361624869703055918575613667858215532572602435432258750639197322091887713402631456113333645709142822182724397962837201266977523L, 96969753191136466007366303619618019752521508403657426306543836447071659732926802256183021740376016065813234292694535879838415771865207311953800116203362150588941093508091412441933752168889516206420588410478242229762908362637083786338280959547015086176046206126019992386890758970740552952647510652431386064722L)
c = (1569733526826523065259704222721381245770313117205865099913421859731162526943498524936251685846967970606251353344665893442015804015671457823645874503670136308040791285744658847419176471348768113798503897694020110157476679833746227801224812046930570487233225157924912272791212802495997329083436189937249314855532400635293522270501567950040825794060896420481676398789310029592608176167251882124182145471818654414925639589921023176070657483148482403065241178276749773L, 139537660044872985880471632333334179976891152860359271230202507995985566816703080930428310461057387079799847266510420206696052591677854190150642820963140050439023069266243433278700748622126726137374130247097863526461696642750021196138340072411724739383716017406022211953417323065831672315854246554523225039827L)

n, e, a, g = pubkey
c1, c2 = c

d = wiener(e, n)
print d

This finally gave me the decryption exponent:

d = 100556095937036905102538523179832446199526507742826168666218687736467897968451

Now that the significant part of the challenge to get the decryption exponent is done, we can get k, then K and then finally the message m. This is Step-2 and the final step in the exploit:

from Crypto.Util.number import *

k = pow(c1, d, n)
K = pow(g, k, a)
print long_to_bytes(c2 * inverse(K, a) % a)

Which gives us the flag:
ASIS{Wiener_at7ack_iN_mUlt1_Prim3_RSA_iZ_f34sible_t0O!}

Here is the final exploit script:

from sage.all import continued_fraction, Integer
from Crypto.Util.number import *

def wiener(e, n):
	m = 12345
	c = pow(m, e, n)
	q0 = 1

	list1 = continued_fraction(Integer(e)/Integer(n))
	conv = list1.convergents()
	for i in conv:
		k = i.numerator()
		q1 = i.denominator()

		for r in range(20):
			for s in range(20):
				d = r*q1 + s*q0
				m1 = pow(c, d, n)
				if m1 == m:
					return d
		q0 = q1

pubkey = (1696852658826990842058316561963467335977986730245296081842693913454799128341723605666024757923000936875008280288574503060506225324560725525210728761064310034604441130912702077320696660565727540525259413564999213382434231194132697630244074950529107794905761549606578049632101483460345878198682237227139704889943489709170676301481918176902970896183163611197618458670928730764124354693594769219086662173889094843054787693685403229558143793832013288487194871165461567L, 814161885590044357190593282132583612817366020133424034468187008267919006610450334193936389251944312061685926620628676079561886595567219325737685515818965422518820810326234612624290774570873983198113409686391355443155606621049101005048872030700143084978689888823664771959905075795440800042648923901406744546140059930315752131296763893979780940230041254506456283030727953969468933552050776243515721233426119581636614777596169466339421956338478341355508343072697451L, 171012227587318507773834753911094468358648971527111097308935888531930900156798659257578479378777764146070352809723708236353390208094909385240006920137781562826981091183813955039359863361624869703055918575613667858215532572602435432258750639197322091887713402631456113333645709142822182724397962837201266977523L, 96969753191136466007366303619618019752521508403657426306543836447071659732926802256183021740376016065813234292694535879838415771865207311953800116203362150588941093508091412441933752168889516206420588410478242229762908362637083786338280959547015086176046206126019992386890758970740552952647510652431386064722L)
c = (1569733526826523065259704222721381245770313117205865099913421859731162526943498524936251685846967970606251353344665893442015804015671457823645874503670136308040791285744658847419176471348768113798503897694020110157476679833746227801224812046930570487233225157924912272791212802495997329083436189937249314855532400635293522270501567950040825794060896420481676398789310029592608176167251882124182145471818654414925639589921023176070657483148482403065241178276749773L, 139537660044872985880471632333334179976891152860359271230202507995985566816703080930428310461057387079799847266510420206696052591677854190150642820963140050439023069266243433278700748622126726137374130247097863526461696642750021196138340072411724739383716017406022211953417323065831672315854246554523225039827L)

n, e, a, g = pubkey
c1, c2 = c

print "e: ", e
print "n: ", n

d = wiener(e, n)

print "d: ", d

k = pow(c1, d, n)
K = pow(g, k, a)
m = long_to_bytes(c2 * inverse(K, a) % a)
print m

Blinding Attack on RSA Digital Signatures

This blog primarily focuses on Blinding Attack- an elementary vulnerability in RSA cryptosystem used to forge Digital Signatures. The working and properties of Digital Signatures will be described before directly jumping onto the attack. In the end, we discuss ways to prevent this attack.

Digital Signature using RSA

RSA is a kind of “Trapdoor One-way Function“. Wikipedia describes a one-way function as a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, “easy” and “hard” are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems. A trapdoor one-way function can only be inverted with the help of a “trapdoor” i.e. our ‘d’, the private key in public key encryption. This method has been used in Digital Transactions and authentication of electronic data.

Let ‘N‘ be the modulus, ‘e‘ be the public key and ‘d‘ be the private key.

The relation between the three is as follows:

ed \equiv 1 mod N -> 1

Digital Signature is used for authentication of electronic data. Let Alice and Bob be two generic parties wishing to communicate with each other and Marvin be the eavesdropper, trying to tamper the data transfer between the two parties. The scenario here is as follows: Alice is trying to get signature of Bob over a message ‘M\in Z*N. To get a signature Alice sends the message ‘M‘ where Bob signs the message M as follows:

S = Md mod N -> 2

Here S becomes the signature of the message M. In the above step, Bob applies his private key to the message and obtains a signature S. Bob then sends this S to Alice or any other authentic party which needs the signature of Bob on M. Since public key of Bob, as the name suggests, is known to the parties, the signature can be easily verified if it is generated from Bob or not by simply calculating

Se = M mod N -> 3

We have used two simple properties, 1 and 2 to arrive at 3. Only Bob has his private key and so the parties can conclude that the signature is authenticate and legible. In the next session we discuss some vulnerabilities in the above method.

Blinding Attack

Consider the same scenario here, except for the fact that this time Marvin wants the signature of Bob over a message M which Bob refuses, being no fool knowing the significance of Digital Signature. So instead of the signature on M, Marvin asks for the signature of “innocent looking”  M’ which is calculated as following:

M’ = reM mod N

Bob agrees to sign this message M’. Let S’ be the signature generated in case of M’. We can write S’ as:

S’ = (M’)d mod N

Upon receiving the signature S’, Marvin can then easily forge the signature to get the signature for message M as follows:

Step 1: Se = (S’)e/re

Step 2: (S’)e/re = (M’)ed/re

Step 3: (M’)ed/re \equiv M’/re = M mod N
(from 1, ed \equiv 1 mod N )

Step 4: Se = M mod N

Here r is any random integer in the same interval as M. The term re mod N is known as blinding factor.

So without actually getting the signature on M, Marvin could successfully manipulate the signature S’ to gain the signature of M i.e. S. This technique allows an attacker to get signature on a message of his choice without the consent of the one who is signing it.

The question which arises now is, what could be the possible measures to prevent such attacks? If you closely look at the way Blinding Attack is implemented, you will get the catch in Step #3. If the signatory signs the Hash of the message M instead of signing the message itself, all the four steps in the attack would make no sense since M’ would then be replaced by H(M’) (The hash function) and hence it cannot be divided by blinding factor to get back M. Another advantage of using hash of the message instead of using the message is that a cryptographic hash can take an arbitrarily long message, and ‘compress’ it into a short string, in such a way that we cannot find two messages that hash to the same value. Hence, signing the hash is just as good as signing the original message, without the length restrictions we would have if we didn’t use a hash. This overcomes the size problem in RSA operation where the key has to be very large in order to sign smaller messages!

 

Resource

[1] https://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf

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!

A Tale of Resurrection

“It is difficult to fight against anger, for a man will buy revenge with his soul”

This is a tale of resurrection. Resurrection, not of any human soul or body, but resurrection of ideas. Ideas that still have the potential to petrify every human present on this planet. It has often been observed that terrorist groups often origin in a reaction of death of an infamous idol which the terrorists worship as their master or another terrorist group which was their ally. Even terrorists are humans. They too seek revenge upon the murder of their idol or master. There seems to be only one significant difference between humans and terrorists. Terrorists seek revenge upon the entire human race and humans seek revenge only upon the murderer. The names are different. The motive is same. Revenge. Believe me if I say that humans can go to any extent to seek revenge. It doesn’t give them happiness. It keeps them moving forward. The cycle goes on and surely it never finishes up. I kill you, your loved ones kill me, my loved ones find and kill yours. It never stops and never will. Until we reach the end of humanity.

Take the case of Peshawar School Attacks. The sole reason for the terrorists attacking the school was they wanted vengeance for the murder of their kids by Pakistan Army in the name of tearing away the terrorist settlements. The Army killed their kids; knowingly or unknowingly. The terrorist killed theirs, knowingly. Islam pictures children as the embodiment of Allah, every religion does. It doesn’t matter when it comes to retaliation. Humans are strange.

This is a story of the most powerful terrorist group in this world. This is a story of ISIS. The story dates back to 2006, during the period of De-Ba’athification, when Saddam Hussein was killed by the US Army. According to Iraqis, Syrians and analysts who study the group, almost all of ISIS’ leaders—including the members of its military and security committees and the majority of its emirs and princes—are former Iraqi officers, specifically former members of Saddam Hussein’s Bath government who lost their jobs and pensions in the De-Ba’athification process after that regime was overthrown.

It is interesting to note that some of the officials have admitted that there would have been no ISIS if US Army had not invaded Iraq. So you see, the motive was, to seek revenge! The cycle went on; they conquered places, the army fought, they conquered again, the army retaliated again. It went on. Neither of them cared about the innocent people. Both the sides were dissatisfied with what they achieved each time, like every human.

Let us dig deep into the functioning of ISIS and their ideals:

  1. Working structure: The group works exactly like any government. Abu Bakr Al Baghdadi heads the group and every body of their group is answerable to him. They have a wing which handles the health of their members, another wing handles the finances and so on. Each wing has a head for each province conquered who is answer to Baghdadi.
  2. Propaganda: It has established the Al-Furqan Foundation for Media Production, which produces CDs, DVDs, posters, pamphlets, and web-related propaganda products and official statements. FBI Director James Comey has described ISIS’ “propaganda is unusually slick,” noting that, “They are broadcasting… in something like 23 languages”. The fact that they are broadcasting in 23 languages reflects that they have been quite successful in spreading their ideas.
  3. Finances:According to a 2015 study by the Financial Action Task Force, ISIS’ five primary sources of revenue are as followed :
    • proceeds from the occupation of territory (including control of banks, oil and gas reservoirs, taxation, extortion, and robbery of economic assets)
    • kidnapping for ransom
    • donations from Saudi Arabia and Gulf states, often disguised as meant for “humanitarian charity”
    • material support provided by foreign fighters
    • fund raising through modern communication networks.
      Mind me if I say that there might me secret funding from organisations which we have never thought about would it. Trust is a non existent word in business. Everything comes with an agreement which compromises the social condition of people living in this world.
  4. Idealogy: The members of ISIS follow the extremist version of the Quran and Wahhabism. They are destroying everything in the name of Jihad. It regards Muslims who do not follow the interpretations as infidels. The Black Standard variant of the legendary battle flag of Prophet Muhammad that it has adopted: the flag shows the Seal of Muhammad within a white circle, with the phrase above it, “There is no God but Allah”. Such symbolism has been said to point to ISIS’ belief that it represents the restoration of the caliphate (Khalifa!) of early Islam, with all the political, religious and eschatological ramifications that this would imply. We would discuss about eschatology later in this article. According to some observers, ISIS emerged from the ideology of the Muslim Brotherhood, the first post-Ottoman Islamist group dating back to the late 1920s in Egypt. Again you see, RESURRECTION OF IDEAS!
  5. Eschatology: One difference between ISIS and other Islamist and jihadist movements, including al-Qaeda, is the group’s emphasis on eschatology and apocalypticism – that is, a belief in a final Day of Judgment by God.
  6. Goals: A significant goal of the group has been the foundation of a Sunni Islamic state. Specifically, ISIS has sought to establish itself as a caliphate, an Islamic state led by a group of religious authorities under a supreme leader – the caliph (Khalifa!) – who is believed to be the successor to Prophet Muhammad.

It is high time that we look at both sides of the coin. Pay attention. BOTH SIDES OF THE COIN. The United Nations Commission on Human Rights has stated that ISIS:

“seeks to subjugate civilians under its control and dominate every aspect of their lives through terror, indoctrination, and the provision of services to those who obey”

Now the other side. What the army is doing is terrorism too; it is retaliation. When we look just at one side of the coin, what we become is called blind. Blind in trusting what the government is doing. Now read the quote again, assuming you belong to a family of terrorists of ISIS. So the army:

“seeks to subjugate civilians under its control and dominate every aspect of their lives through terror, indoctrination, and the provision of services to those who obey”

It is all a matter of perspective. For the family of terrorists, they are civilians and for the army men fighting, their families are. Both have the right to live. But peacefully. It could hurt when I say that peace might be a state of mind. Maybe we can never achieve peace in this state of war, of mankind. Maybe the ultimate peace we get is DEATH. Think about it.

What is the definition of terror? Ask yourself this question again and again. If it is about someone killing your loved ones then what the government is doing to the terrorists is terrorism too, in the name of justice. If it is about bomb blasts then think about it again. Two wrongs don’t make a right.

The question which arises now is: Who is going to stop this? I am sure that neither the army is going to put down its arms nor the group is going to. Something will vanish. Most things won’t. Ideas are one among them. Is this what life is all about? Do you all want to leave behind a legacy? Think about it. Do we have to wait till what ISIS believes as eschatology or some apocalypse to decide who among us is wrong. I guess everybody is wrong here. Because nobody is going to step down.

The ideas will never vanish. NEVER. Maybe the army is going to take down all the members of ISIS and the group no longer would exist. But, MARK MY WORDS, there will be a new group emerging from somewhere out there and we will have to fight against it, again. They will fight in the name of Jihad. We will fight in the name of Justice. It will never stop. I will never stop. Neither will you. Nor will they. There will be no peace. Maybe peace is just a state of mind. Maybe we cannot get it. Somebody has to stop. Who will? You, me, they? Who? Ask yourself. Over and Over again.

“Seek and you shall find the repulsive things you hope to find”

 

 

Resources: ISIS (Only factual data is collected from this site)

 

 

 

RC3 CTF Writeup – Salad(Crypto 100)

Being a part of bi0s, this was the first time I was able to decode a cipher while the CTF was still going on and the feeling was amazing! I feel extremely lucky to be a part of bi0s with such great seniors who are experienced exploit experts and mentor like Vipin Sir!

Its been more than a month I have joined bi0s, and I am pretty sure that Cryptography will the field I am going to focus upon in Computer Science for the rest of my life, I mean for my Masters and if possible then PhD. My blog from now will primarily focus upon the new ideas that emerge in the field of Cryptography, along with the topics which I learn.

Of Course, I won’t stop writing critical thoughts and ideas of mine!

The question stated:

Salad

Category: Cryptography              Points: 100

Description:

“The fault, dear Brutus, is not in our stars, but in ourselves.” (I.ii.141) Julius Caesar in William Shakespeare’s Julius Caesar

Cipher Text: 7sj-ighm-742q3w4t

At the first glance, the question looks like one encoded with Caesar(Shift) cipher but it is kinda not so. It involves applying Substitution cipher along with Caesar to get the flag.

So here we go,

Since each flag in the CTF had to start with RC3-2016, it struck me at a point of time if even the encoded message contains RC3-2016, but in encoded form! This forced me to find a relation between the letters and the digits using the first 7 encoded digits and RC3-2016. The pattern that I could make out was this:

0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ
KLMNOPQRSTUVWXYZ0123456789ABCDEFGHIJ 

7sj-ighm-742q3w4t
RC3-2016-ROMANGOD

Here is the flag: RC3-2016-ROMANGOD

Looking forward to exploring and solving more questions in Cryptography!

Meeting beyond Borders

In the beginning it felt like every other day: repeated hours of technical classes and then coming back to the hostel again. But, it turned out to be completely different. That day, our last period was SaH(Serve an Hour). An hour before SaH, I was tired because the topics taught that day were too complex to be fed into my brain. As I was walking across the floor, it felt my legs were ready for a rebellion to resist my flow but I had the strength to resist the pain. I kept deceiving my mind, it would just be a matter of one hour and then I could finally take some rest(Although we had our FOSS club too, I was fooling I said!). We were told that our main project was to create various presentations on a social topic, visit a school nearby and teach them about it in detail.

As I entered the SaH hall, I saw various foreigners sitting on the seats which looked unusual. Various thoughts were hitting my mind: “What have they come for? Who are they? Where have they come from?” et cetera. As I settled myself on a chair, I saw a long haired, tall, blonde guy who had a professional camera suspended on his neck which amazed me(Conceptual Photography is my hobby and so, it amazed me!). The guy introduced himself, he told his name was Maximilian Teufel and he lived near The Alps, in Germany. Europe has been a paradise for Photography since ages and it has produced quite famous photographers. So it was obvious that I started talking to him. We had a brief talk on how he felt coming to India and the answer was a mixed expression which was exactly I felt about my country.

I asked him questions, he answered them accurately, just the way I want people to answer my questions. We share common interest and common answering method. Like most of the professional photographers, he had a completely different way of looking at things which I could make it out when he was clicking the activities we were doing. Foreigners are usually astonished at the way Indians have the attitude towards the social issues that exist in this world, and so was he.

He had come with his team of Ayudh Europe . All of them came from different places: Netherlands, Austria, Germany, Italy but there was one motive which bound them all; making the society a better place to live and inspiring people to care for the Mother Nature.

I couldn’t cease myself going to him after the class. I was very excited to watch his clicks after arriving here and I was surprised to see that the way he clicked some of his photos was similar to that of mine. I took his contact number, his Facebook id, Instagram id literally everything! I contacted him the same night, sharing him my blogs and how we shared common interests. The most observable characteristic of that guy I remember is his long hair! 🙂 I met the next day itself in the Indian Canteen coincidentally, when I was passing by. This time we talked about Indian Cuisine- Chhole, Puri and what not!

I shared my blog with him that night and we talked like we were a part of the same family!

What urged me to write this blog is how people can have same perspective, even when they are living “Beyond the Borders!”. Day before Yesterday, he posted a photo on his Instagram account and to my surprise it was the same photo I had clicked a month before! It is not a sunset, its a portrait of a person who is meditating on the seashore.

Have a look at this!

This slideshow requires JavaScript.

You maybe from one country and your friend maybe from another but we all humans emerged from the same origin, it is we who created the boundaries in our Mother Earth.

We all are the same, change the perspective and the differences will disappear!

Long Live Humanity!