DES-OFB Writeup (Boston Key Party CTF)

Challenge

Category: Crypto Points: 2 Description:

Decrypt the message, find the flag, and then marvel at how broken everything is. The challenge gave us a Cipher text file and a python script implementing Data Encryption Standard (DES) in Output Feedback (OFB) mode as shown below:

from Crypto.Cipher import DES

f = open(‘key.txt’, ‘r’)
key_hex = f.readline()[:-1] # discard newline
f.close()
KEY = key_hex.decode(“hex”)
IV = ‘13245678’
a = DES.new(KEY, DES.MODE_OFB, IV)

f = open(‘plaintext’, ‘r’)
plaintext = f.read()
f.close()

ciphertext = a.encrypt(plaintext)
f = open(‘ciphertext’, ‘w’)
f.write(ciphertext)
f.close()

Solution

This overall was a fairly straightforward crypto problem requiring a little maneuvering. There is a little math involved but I promise it ain’t too hard and makes solving the problem so much easier. In order to make this comprehensive, here is a brief about DES in OFB:

OFB_encryption

Mathematically, this could be written as:

 Cj = Pj ⊕ Oj            —— (1)

Oj  = Ek(Ij)             —— (2)

Ij = O(j-1)                —— (3)

I0  = IV                    —— (4)

where  Cj  = jth ciphertext block, Pj = jth plaintext block, IV = Initialization vector

and Oj = jth encrypted input vector.

Using (2) and (3) we can also get:

Oj  = Ek(O(j-1) )       —— (5)

Now since we know that an xor (⊕) operation is symmetric in nature, from (1) we have:

 Pj=  Cj ⊕ Oj            —— (6)

Again using (2) and (6) we have:

 Pj=  Cj ⊕ Ek(Ij)       —— (7)

Lets consider (7) for j =0 and using (4):

         P0=  C0 ⊕ Ek(IV)       —— (8)

Again consider (6) for j =1, then using (5), followed by (2) & then finally (4):

         P1=  C1 ⊕ O1   =  C1 ⊕ Ek(O0)  =  C1 ⊕ Ek(Ek(I0))  =  C1 ⊕ Ek(Ek(IV))   —— (9a)

Again consider (6) for j=2, similarly we have:

       P2=  C2 ⊕ O2   =  C2 ⊕ Ek(O1)  =  C1 ⊕ Ek(Ek(Ek(I0)))  =  C1 ⊕Ek(Ek(Ek(IV)))   —— (9b)

Using (8), (9a) & (9b) we can generalize the formulae for odd(starting with 1) blocks and even(starting with 0) blocks:

Peven =  Ceven ⊕ (odd number of times Eof (IV))      —— (10)

Podd   = Codd  ⊕ (even number of times Eof (IV))      —— (11)

Considering the clue in question as to marvel on how broken everything is, I assumed DES weak keys, meaning the encryption and decryption operation are identical. Hence (10) and (11) could further be reduced to:

Peven =  Ceven ⊕ E(IV)

Podd   = Codd  ⊕ IV

Since from the given python script for the challenge we know IV = ‘13245678’, thus we can solve and get the value plaintext blocks for all odd(starting with 1) blocks. Since we don’t have the key value, we cant just yet get even blocks but its a start. So I quickly wrote a script for the same as shown below:

from Crypto.Cipher import DES, XOR
import operator
block_size = DES.block_size

IV = ‘13245678’
f = open(‘ciphertext’, ‘r’)
ciphertext = f.read()
f.close()

plainblocks = ”

i=0

while True:

cj = ciphertext[(i*block_size):((i+1)*block_size)]
if not cj:                                                 # the last iteration was the last block
break

xor = XOR.new(cj)
if (operator.mod(i+1,2)==0):
plainblock = xor.decrypt(IV)
else:
plainblock = cj

i = i+1
plainblocks = plainblocks + plainblock

print plainblocks

Running this python script using the ciphertext gives us the following broken output:

p+{��’S�r not to&>��t is the5.��n:
WhethA6{��b�Nobler iJd/��+�nd to suB”>��_� Slings E*?��y�ws of ouP6:��d� FortunN��take ArmWd:��b�t a Sea K”{��d�les,
And&”��{�sing end03��1S�o die, tKd(��n�No more;%5��i
�a sleep,04��j
�we end
TL!{œj�-ache, aJ {��nS�housand j%/��j�shocks
TL%/��g�h is heiVd/��+T�is a conW16��n
DevoutH={��+� wished.4��b� to sleeThQٙ+�eep, perG,:��nS�o Dream;%”��+�ere’s thAd)��’y�or in thE0{��n� of deatLh{��j�dreams mE={��f�
When we,:��+�uffled oB”{��b�mortal cK-7��F�t give uWd+��x� There’s03��y�pect
ThaPd6��n�Calamity+=��dS�ong lifeN��+�o would F!:�� Whips aJ {ޕd�s of timAhQٞnS�ppressor7{��d�, the prK1?��j�s ContumA(“��_� pangs oBd?��{�ed Love,03��G�’s delE=w��c�insolencAd4��D�ice, and03��X�rns
That4:��n� merit oBd/��+�worthy tE/>��$�en he hiI7>��+�ght his u12��~�make
WitLd:��j� Bodkin?3��|�ld FardeH7{��j�
To grunPd:��+�eat undeVd:��n�y life,
f1/��c� the dreE {��+�mething E”/��+�ath,
The15��x�vered CoQ*/�S�rom whosAd9��y�No TraveH(>��y�urns, Pu^>7��+�e will,
e*?��j�s us ratL!)��n� those iH((��nS�ave,
ThaJd=�� others P,:��|�know not+=��_�s ConsciA*8��o�s make CK3:��xS�f us aN��+�us the NE02��+�e of ResK(.��d�Is sicklM!?��,�, with tL!{��g�cast of p,4��c�
And entA6+��x� of greaPd+��h�and momeJ0w��b� this reC%)��ir CurreJ0(��~� awry,
AJ {��x�the name+=��h�on. Soft=4��e�,
The faM6{†c�ia? NympLh{��+�y OrisonWN��j� my sins6>��f�red. BKPg��d,�ts_just_E�y�repeatinC4��*�

Considering it closely this is text from the play Hamlet Act 3 scene 1. And its start aligns with “To be, or not to be?” from original text. Using this information I now have P0 and C0 blocks and thus can calculate the value of Ek(IV). Hence I can decrypt all the even blocks as well. The refined final python script highlighting the update is given below:

from Crypto.Cipher import DES, XOR
import operator
block_size = DES.block_size

IV = ‘13245678’
f = open(‘ciphertext’, ‘r’)
ciphertext = f.read()
f.close()

hint = ‘To be, or not to be? That is the question’

p0 = hint[:block_size]

c0 = ciphertext[:block_size]

xor = XOR.new(c0)

ek = xor.decrypt(p0)

plainblocks = ”

i=0

while True:

cj = ciphertext[(i*block_size):((i+1)*block_size)]
if not cj: # the last iteration was the last block
break

xor = XOR.new(cj)
if (operator.mod(i+1,2)==0):
plainblock = xor.decrypt(IV)
else:
plainblock = xor.decrypt(ek)

i = i+1
plainblocks = plainblocks + plainblock

print plainblocks
f = open(‘output’, ‘w’)
f.write(plainblocks)
f.close()

And when we run this script, Voila !  (#flag is write at the end).

To be, or not to be, that is the question:
Whether ’tis Nobler in the mind to suffer
The Slings and Arrows of outrageous Fortune,
Or to take Arms against a Sea of troubles,
And by opposing end them: to die, to sleep
No more; and by a sleep, to say we end
The Heart-ache, and the thousand Natural shocks
That Flesh is heir to? ‘Tis a consummation
Devoutly to be wished. To die, to sleep,
To sleep, perchance to Dream; aye, there’s the rub,
For in that sleep of death, what dreams may come,
When we have shuffled off this mortal coil,
Must give us pause. There’s the respect
That makes Calamity of so long life:
For who would bear the Whips and Scorns of time,
The Oppressor’s wrong, the proud man’s Contumely,
The pangs of despised Love, the Law’s delay,
The insolence of Office, and the Spurns
That patient merit of the unworthy takes,
When he himself might his Quietus make
With a bare Bodkin? Who would Fardels bear,
To grunt and sweat under a weary life,
But that the dread of something after death,
The undiscovered Country, from whose bourn
No Traveller returns, Puzzles the will,
And makes us rather bear those ills we have,
Than fly to others that we know not of.
Thus Conscience does make Cowards of us all,
And thus the Native hue of Resolution
Is sicklied o’er, with the pale cast of Thought,
And enterprises of great pitch and moment,
With this regard their Currents turn awry,
And lose the name of Action. Soft you now,
The fair Ophelia? Nymph, in thy Orisons
Be all my sins remembered. BKPCTF{so_its_just_a_short_repeating_otp!}