Sharif CTF 2018 Crypto Writeups

1. DES- 60 points

Solved by: s0rc3r3r

In this challenge, we are given pairs of plaintext-ciphertext encrypted in DES-ECB using the same value of the key. The plaintext-ciphertext pairs are given in “known-plaintext.txt”. When we look closely at the values in the file, we can observe that for some pairs, the following characteristic exists:

E(E(m)) = m, where E() is the encryption function and m is the message

This peculiar vulnerability exists only in DES and exists only for a set of key values, that are known as weak keys. You can read about weak keys here: https://en.wikipedia.org/wiki/Weak_key#Weak_keys_in_DES

So the set of plaintexts are encrypted using a weak key. Now that number of weak keys is less, we can iterate over each weak key list and check if decryption of a ciphertext value in the file gives its corresponding plaintext.

Wrote the following script to implement it:

from Crypto.Cipher import DES

# Reading plaintext-ciphertext pairs
obj1 = open("known_plaintexts.txt",'r')
pt_ct_list = obj1.read().split("\n")[:-1]
pt_ct_list = [i.rstrip("\r").replace(" ","") for i in pt_ct_list]

# Weak key list
key = ["0101010101010101", "FEFEFEFEFEFEFEFE", "E0E0E0E0F1F1F1F1", "1F1F1F1F0E0E0E0E"]

for i in key:
    key_obj = DES.new(i.decode("hex"), DES.MODE_ECB)
    # Taking one ciphertext from file
    ct = pt_ct_list[0][:16].decode("hex")
    # Corresponding plaintext from file
    pt = pt_ct_list[0][18:].decode("hex")
    # Potential plaintext
    pot_pt = key_obj.decrypt(ct)
    if pot_pt == pt:
        print "Key: ", i

Key: “E0E0E0E0F1F1F1F1”

We got the first blood for this challenge, pretty easy! >_<

 

2. OSS-Signature- 100 points

Solved by: s0rc3r3r

We are given m1, m2, x1, y1, x2, y2, k and n which satisfy the given equations:

–> Equation-1
–> Equation-2

The task is to express m1*m2 using a similar representation ie.

and hence, we have to find the value of s1 and s2.

We can find s1 and s2 from the following:
1. Multiply Equation-1 and Equation-2, we will have:


We can make it a perfect square by adding and subtracting 2*x1*x2*k*y1*y2, we will then have:

And hence,

Where s1 = x1*x2 + k*y1*y2 and s2 = x2*y1 – x1*y2

Wrote the following code to implement it:

term1 = x1**2 + k*(y1**2)
term2 = x2**2 + k*(y2**2)
assert (term1*term2) % n == 5141
s1 = x1*x2 + k*y1*y2
s2 = x2*y1 - x1*y2
assert (s1**2 + k*(s2**2)) % n == 5141
# Modulo reduction
print "s1: ", s1 % n
print "s2: ", s2 % n

And we get the values of s1 and s2 that satisfy the conditions:

s1 = 3228192414578958851010842513154275809496752450843437198583166196901565071578144066800517210864829309956656172864622172889502523814134130877601254638400747755883616155295299435314390972047946113969350548381594633322779945307216665767237995638888452882989503186673207123359630734140939449837354851424900356484212983667331443801108560693455298625538140549843770730178132648956596007707374948190919655158210892858713252214782069457662864873988983041011930880072395421594443371267339482128681654521226571357238152202622389403367075320562466814355917951666554746996134626758309948472069549094989922908904448493268680406656

s2 = 24484535381781389323074470421911819639042225964435602473611268830778094454640680950247904607938498485547308794156596530048036709040042946833357706925382417888065011049859098805247309143606836121648675503265954564725192812735457023952534691595036622842908877779999269095789286247447026022826317754191340149168483076749534241533561701691035224125146103048048656077931512856242523043968028811895609749316745020908526817848861116370125504641363458061292626411114312230260298354677312266199167460831130312481867664446125836465876792580053773528992613465690017628197218948554388712333570191622746063799279773801301923351131

3. fHash – 200 points

Solved by: v4d3r and s0rc3r3r

Optimised Brute Force:

import os
from hashlib import md5

def foo(h, m):
    return md5(h.encode('utf-8') + m.encode('utf-8')).hexdigest()[:4]

def round(hl, m, hr):
    #print foo(hl,m), foo(hr,m)
    return foo(hl, m), foo(hr, m)

def fHash(hl, hr, M):
    message = list(map(''.join, zip(*[iter(M)] * 4)))
    for m in message:
	#print "for message part :" + m
	#print hl, hr
        hl, hr = round(hl, m, hr)
    return hl + hr

if __name__ == '__main__':
    h = (fHash('7575', 'A8A8', '7368617269666374'))
    print (fHash('7575', 'A8A8', '7368617269666374'))
    #l=5958
    #r=433b
    print (fHash('5958', '433b', '7368617269666300'))

 #the bruteforce goes here
#We assume the hash exist for message with last byte changed to \x00
    print (fHash('7575', 'A8A9', '7368617269666300'))
    left=""
    right=""
    #to get all ascii chars
    a=""
    for i in range(126):
	a+=chr(i)
    for i in a:
	print "i passed :" + str(ord(i)*100/126) +"%"  # to get % completion
	for j in a:
	    for k in a:
		for l in a:
		    left=(i+j).encode("hex")
		    right=(k+l).encode("hex")
		    if (fHash(left, right, '7368617269666300'))==h:
			print "found: Left is " + left + " and Right is " + right
			break