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_