Tags: sat crypto
Rating:
The challenge provides two files:
As we can see in the python code, the plaintext consists in a pair of permutations.
Additionally, there's another permutation that acts as a key.
The encryption consists in a series repeated operations on the plaintext using the key.
Finally, the ciphertext consists in the resulting permutations,
from which the plaintext can be recovered with the key permutation.
We are provided two plaintext / ciphertext pairs, encrypted with the same key,
which is a randomly generated permutation, and not provided.
We are expected to recover the key, to generate the flag.
Looking at the encryption process we can see that encryption process consists only in three operation rounds,
so it may be feasible to solve it using a solver,
so we create the model and extract the plaintext and ciphertext from the data.txt file and add it as the input and constraints.
The final code is available at horst.pi.
We run it to obtain the key:
$ picat horst.pi
[59,2,50,29,55,15,43,30,27,6,57,22,7,26,3,35,24,40,53,46,49,10,16,12,41,47,60,11,51,58,4,1,56,28,52,19,39,9,33,36,37,63,14,0,61,13,25,17,8,54,44,34,18,23,48,62,32,42,20,45,31,5,38,21]
Once we have the key, we just need to construct the key as specified in the python code:
$ python2 -c "from horst import Permutation;from hashlib import sha1;print 'The flag is: PCTF{%s}' % sha1(str(Permutation([59,2,50,29,55,15,43,30,27,6,57,22,7,26,3,35,24,40,53,46,49,10,16,12,41,47,60,11,51,58,4,1,56,28,52,19,39,9,33,36,37,63,14,0,61,13,25,17,8,54,44,34,18,23,48,62,32,42,20,45,31,5,38,21]))).hexdigest()";
The flag is: PCTF{69f4153d282560cdaab05e14c9f1b7e0a5cc74d1}
