Tuesday, October 29, 2013

EMC Defenders League - Round 3 - ElGamal Cryptosystem

A ruby script was given, looking at the code its easily identified as ElGamal cryptosystem
def encrypt(plaintext)
  begin
    p,g = File.read("public.key").split.map(&:to_i)   # prime p and generator g
    x = File.read("secret.key").downcase.unpack("H*").first.to_i
  rescue
    raise "Could not read the keys."
  end
  y = mod_pow(g,x,p)     
  msg = plaintext.unpack("H*").first.to_i(16)  
  enc = []
  while msg!=0 do
    k = rand(2**512)
    while k.gcd(p-1)!=1
      k = rand(2**512)     # ephimeral key
    end
    msg , m = msg.divmod(p)    # quotient , remainder
    a = mod_pow(g,k,p)     # cipher_one

    b = (m * mod_pow(y,k,p)) % p   # cipher_two
    enc.push([p,g,y,a,b])
  end
  return enc
end
Also a directory listing was given, which read
-rw------- 1 user1 user1    9 Sep 12 16:59 secret.key
So, it looks like the private key is a small number. From the code y = g^x mod p , where y,g and p are public. I wrote a GMP C code to brute the value of x. Now its the matter of decrypting the value of cipher text from the given file
#!/usr/bin/env sage -python

from sage.all import *

a = [10264935714840344555659480530391531504799751837786398398316078563294217410270167702155077526394934157060210816906645541211888193204711479484170362078382934, 6823073135499190154483378335285592356188617899094830851286814357379354454127003397049290347022567266459967665409741524356428389256663366725696511671610252, 6799828613544592377533880394625646977560051635952644078042208063362163512223938553938795141149658062454075205535854660371542763834499519406362703514503332, 672505970984355266693231966226618520516336889495074224541849620341452271159684475161636332714848734553160854293600007936085992661979551831016772987917068]
b = [10340609465224600321180300969872222181794348193568386018372923576739867282485924452563065089417849300140351755230325685204557146183945278941161645372102509, 5281134801218769020778720412885415834550804855232111764210295764635532757913976877308711845460529040416820894758873972605710392788924240448443272640451982, 457101717286387383800532326852190913868486287682428841339947697619176026876915473073415513803021227080851888197491621726415573291680046893149593865864624, 589149635285693973671288870900610302399060697179753365215668035230635162797171706009867229016045306799390816419364037357020145534760948533979498925094150]
mod = 11994453392181474037639262741550096843127850786293620241343626519409002514576698974663696483571708872339453054238999399420344927969237949604807335692536203

private = 77656
dec = []
for i in range(4):
    dec.append( (b[i] * inverse_mod(a[i]^private, mod)) % mod)

q = 0
for i in range(3, -1, -1):
    msg = (q * mod + dec[i])
    q = msg

dec = hex(q)[2:]
dec = dec[:len(dec)-1].decode('hex')
print dec
Yourt passwordh muste be ats leaste 18770c charactersr ande cannott repeat anyc ofo yourd previouse 30689 passwords.i Pleases type ag differenty password.8 Type4 ai password7 thatf meetso thesev requirements1 int boths textw boxes..
Collect the last character of each word to retrieve message.

EMC Defenders League - Round 2 - Hill Cipher Known Plain Text Attack

Couple of cipher text and password for first cipher text was given. Our aim was to decrypt the second message to find the flag for the challenge. First, lets decrypt the cipher text for which we have the key.
Cipher Text:
-6N.AAH79T2N3Z?M2XMW9O6261HOVPC,VIRA1RNOOO,9QZHGXDPDGD5CHPIQ369Z0 Z.0A2QKE57ISF,IRZUPDZS6R5UWM9IECDDQPMUN337X331G8D,23QLW8QT4XP76YAS 4SKJTRJJ3A TIAQPHQPL9UU1YHSWU9V2

Key:
JACKNJ1LL

Charset:
_ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789.?,-

Plain Text:
DEAR_AGENT_ALICE,_OUR_FRIEND_AGENT_CARLOS_GOT_CAUGHT_SO_OUR_KEY_AND_CODEWORD_MAY_HAVE_BEEN_COMPROMISED._PLEASE_CHANGE_THE_KEY_AND_SEND_THE_NEW_CODEWORD_-_AGENT_BOB__
The key given was 9 chars long, so the key matrix should be 3x3. The length of first cipher text is 165 bytes, so it must be a 3x55 matrix. Ok, we need more details. Lets try and interpret few information from the decrypted plain text. If message format is the same, the header of 2nd cipher text must be from plain text mentioned below[ALICE --> BOB]
DEAR_AGENT_BOB,_ # 16 bytes
Also, the footer must be something similar to
_-_AGENT_BOB__  # 16 bytes
Cipher text two:
7BQE,IZ0ZILXX0B8FJKZGYAM35F7LG.6W8AIBNEBNZS2VSZYEG0QF0PJC LY0FFVU7K028DHW2GWE 9DQG.MEDOUC?AAWR,ZQF9X,VK9JKQTUMF5OW2ZFERF # 120 bytes
With the above information, we must be able to partially recover the key. If the key is 3x3 matrix, the plain text must be represented as 3x40 matrix for encryption
cipher_matrix = 
[34, 2, 17, 5, 39, 9, 26, 27, 26, 9, 12, 24, 24, 27, 2, 35, 6, 10, 11, 26, 7, 25, 1, 13, 30, 32, 6, 34, 12, 7, 37, 33, 23, 35, 1, 9, 2, 14, 5, 2, 14, 26, 19, 29, 22, 19, 26, 25, 5, 7, 27, 17, 6, 27, 16, 10, 3, 0, 12, 25, 27, 6, 6, 22, 21, 34, 11, 27, 29, 35, 4, 8, 23, 29, 7, 23, 5, 0, 36, 4, 17, 7, 37, 13, 5, 4, 15, 21, 3, 38, 1, 1, 23, 18, 39, 26, 17, 6, 36, 24, 39, 22, 11, 36, 10, 11, 17, 20, 21, 13, 6, 32, 15, 23, 29, 26, 6, 5, 18, 6]

Prologue of plain text:
[4, 5, 1, 18, 0, 1, 7, 5, 14, 20, 0, 2, 15, 2, 39, 0]

Epilogue of plain text:
[0, 40, 0, 1, 7, 5, 14, 20, 0, 1, 12, 9, 3, 5, 0, 0]
With the know plain text in row 1 and row 3, lets solve a set of linear equations to find the partial key inverse(key[3x3]) * cipher[3x40] == plain[3x40]
Linear equations for 1st row of inverse key matrix
sage:  var('a,b,c')
(a, b, c)
sage: solve_mod([34*a+14*b+17*c == 4, 2*a+26*b+7*c == 5, 17*a+19*b+37*c == 1], 41)
[(18, 5, 18)]
Solving a set of set of linear equations for row 3
sage:  var('g,h,i')
solve_mod([2*g+4*h+6*i == 0, 5*g+36*h+18*i == 5, 14*g+0*h+5*i == 3], 41)
[(6, 9, 33)]
So the row 1 and row 3 of inverse key matrix is recovered
[(18, 5, 18),
 (x , y, z ),
 (6 , 9, 33)] 
With this key, we can recover the plain text from row 1 and row 3
cipher = matrix([[34, 2, 17, 5, 39, 9, 26, 27, 26, 9, 12, 24, 24, 27, 2, 35, 6, 10, 11, 26, 7, 25, 1, 13, 30, 32, 6, 34, 12, 7, 37, 33, 23, 35, 1, 9, 2, 14, 5, 2], [14, 26, 19, 29, 22, 19, 26, 25, 5, 7, 27, 17, 6, 27, 16, 10, 3, 0, 12, 25, 27, 6, 6, 22, 21, 34, 11, 27, 29, 35, 4, 8, 23, 29, 7, 23, 5, 0, 36, 4], [17, 7, 37, 13, 5, 4, 15, 21, 3, 38, 1, 1, 23, 18, 39, 26, 17, 6, 36, 24, 39, 22, 11, 36, 10, 11, 17, 20, 21, 13, 6, 32, 15, 23, 29, 26, 6, 5, 18, 6]])

key = matrix([[18, 5, 18],[0, 0, 0], [6 , 9, 33]])

plain = (key*cipher)%41
[ 4  5  1 18  0  1  7  5 14 20  0  2 15  2 39  0 19  1  4  0 20 15  0  8  5  1 18  0  1  2 15 21 20  0  1  7  5 14 20  0]
[ 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
[30 26 18 23 23 29 24 14 13 18 20  2 14 15  8 10  9 12  9 25 14 28 13 29  2  0 40  0  1  7  5 14 20  0  1 12  9  3  5  0]
Convert this to plain text we get:
charset = "_ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789.?,-"

text = ''
for i in plain:
    for char in i:
        text += charset[char]
print text
DEAR_AGENT_BOB,_SAD_TO_HEAR_ABOUT_AGENT_________________________________________3ZRWW2XNMRTBNOHJILIYN1M2B_-_AGENT_ALICE_
We have the partial plain text recovered. Now we have to recover row 2. Looking at the plain text one and partial plain text two, I could predict that the plain text could be
DEAR_AGENT_BOB,_SAD_TO_HEAR_ABOUT_AGENT_CARLOS  # CARLOS can be predicted
Now solve the linear equations for row 2
sage: var('d,e,f')
(d, e, f)
solve_mod([34*d+14*e+17*f == 3, 2*d+26*e+7*f == 1, 17*d+19*e+37*f == 18], 41)
[(28, 39, 23)]
So, the recovered inverse of key matrix is
[(18, 5, 18),
 (28, 39, 23),
 (6 , 9, 33)] 
Final message is DEAR_AGENT_BOB,_SAD_TO_HEAR_ABOUT_AGENT_CARLOS._HERE_IS_THE_NEW_CODEWORD_PYYTO4V3ZRWW2XNMRTBNOHJILIYN1M2B_-_AGENT_ALICE_